How to find Best Price for a Deck of Collectible Cards?

Question

Or The Traveling Salesman plays Magic!

I think this is a rather interesting algorithmic challenge. Curious if anyone has any good suggestions for solving it, or if it is already solvable in a known way.

TCGPlayer.com sells collectible cards for a variety of games, including Magic the Gathering. Instead of just selling cards from their inventory they are actually a re-seller from multiple vendors (50+). Each vendor has a different inventory of cards and a different price per card. Each vendor also charges a flat rate for shipping (usually). Given all of that, how would one find the best price for a deck of cards (say 40 - 100 cards)?

Just finding the best price for each card doesn't work because if you order 10 cards from 10 different vendors then you pay shipping 10 times, but if you order all 10 from one vendor you only pay shipping once.

The other night I wrote a simple HTML Scraper (using HTML Agility Pack) that grabs all the different prices for each card, and then finds all the vendors that carry all the cards in the deck, totals the price of the cards from each vendor and sorts by price. That was really easy. The total prices ended up being near the total median price for all the cards.

I did notice that some of the individual cards ended up being much higher than the median price. That raises the question of splitting an order over multiple vendors, but only if enough savings could be made by splitting the order up to cover the additional shipping (each added vendor adds another shipping charge).

Logically it seems that the best price will probably only involve a few different vendors, but if the cards are expensive enough (and some are) then in theory ordering each card from a different vendor could still result in enough savings to justify all the extra shipping.

If you were going to tackle this how would you do it? Pure brute force figuring every possible combination of card / vendor combinations? A process that is more likely to be done in my lifetime would seem to involve a methodical series of estimates over a fixed number of iterations. I have a couple ideas, but am curious what others might suggest.

I am looking more for the algorithm than actual code. I am currently using .NET though, if that makes any difference.

Answer 1

I would just be greedy.

Assume that you are going to eat the shipping cost and buy from all vendors. Work out the absolute lowest price you get. Then for each vendor work out how much being able to buy some cards from them versus someone else saves you. Order the vendors by shipping - incremental savings.

Starting with the vendors who provide the least value, axe that vendor, redistribute their cards to the other vendors, and recalculate incremental savings. Wash, rinse, and repeat until your most marginal vendor is saving you money.

This should find a good solution but is not guaranteed to find the best solution. Finding the absolute best solution, though, seems likely to be NP-hard.

Answer 2

This is isomorphic to the uncapacitated facility location problem.

• card in the deck : client

• vendor : possible facility location

• vendor shipping rate : cost of opening a facility at a location

• cost of a card with a particular vendor : "distance" from a client to a facility

Facility location is a well-studied problem in the combinatorial optimization literature.