Putting the magic in the machine since 1980.

Friday, July 3, 2009

Best Way to Bid in a Distributed Combinatorial Auction?

During the last year Benito Mendoza examined how different bidding strategies (really, algorithms) fare under the PAUSE auction. I would like to go over these results but first, some background.

A combinatorial auction is one where there are many items for sale at the same time and bidders can place bids on multiple items. For example, a bid might be "I'll pay $10 for items A,B, and X." These bids are then sent to the auctioneer which must find the set of winning bids that maximize revenue—– problem that is NP-complete. Check out this visualization of a combinatorial auction that I developed for class.

In the PAUSE auction there is no centralized auctioneer. The auction instead proceeds in steps. At the first step we hold parallel English auctions for each item. That is, everyone bids on every item individually. Thus, at the end we will have a (temporary) winning bid for each item. At the second set there is one auction but now all bidders must place bid-sets that cover all items in the auction, but they can use bids that the other agents placed before. Also, they can place bids that cover two items. For example, an agent might place a bid-set that includes a bid from itself for items A, and B, as well as bids, from other agents, for items C, D, and F. By restricting the agents to place complete bid-sets we are, in effect, forcing the bidding agents to solve the winner-determination problem using the existing public bids.

Well, sort of, because bidders are selfish they will want to place the bid that wins them the most items, for the least money (the bid-set that maximizes their utility). Two years ago we developed the PAUSEBID algorithm which a bidder can use to find the myopically-optimal bid-set: the bid-set that, if the auction were to end at that moment, maximizes the bidders's utility. The problem is that since this is an NP-complete problem PAUSEBID cannot be used in auction with more than about a dozen items. Thus, the next year we developed approximate bidding algorithms which have linear running time (way faster). This was good.

But, it raised another question: if the other bidders are using PAUSEBID, should I also use PAUSEBID, and spend all time computing, or should I use GREEDYPAUSEBID and save all that computational time at the risk of getting a lower utility? That is, should I think a lot about my next bid or just kinda wing it? The surprising results, which have to yet been published except on Benito's thesis, are that it is better for all bidders to use GREEDYPAUSEBID. That is, if all the other agents are using PAUSEBID, thus picking their bids optimally, then I can actually expect slightly higher utility by bidding with a simple greedy algorithm (GREEDYPAUSEBID). Also, in the world where all the agents are using GREEDYPAUSEBID the bidders get higher utility than in the world where they are all using PAUSEBID. What happens is that prices drop down a bit and thus all the bidders (buyers) win a bit, of course, the sellers lose.

Even more interesting, we also found that in the world where all the other bidders are using GREEDYPAUSEBID, my best strategy is to also use GREEDYPAUSEBID. Again, I would actually lose utility by trying to myopically-optimize my bidding strategy. Putting all these together we find that the population where all bidders use GREEDYPAUSEBID is stable (is a Nash equilbrium).

These results go against our initial intuitions. But, we must remember that an auction with lazy bidders will result in a lower sale price which benefits, on average, all bidders. Also, a myopically-optimal bidder will reveal utility gains to the other lazy bidders which they will then exploit, thus raising the final price.