Support for combinatoric auctions

[davidrpugh]

@bherd-rb and @phelps-sg A medium term goal of the project is to extend the API in order to support combinatoric/multi-dimensional auctions.

I came across this nice paper summarizing some of the basic results on combinatoric auctions. I had a quick glance through the paper and it seems that solving for the optimal allocation is NP-complete in most cases; in most all cases even approximating the optimal allocation is NP-complete; in a few cases, finding a feasible allocation is NP-complete.

[bherd-rb]

@davidrpugh @phelps-sg Thanks for the paper, that's an interesting point. Combinatorial auctions will become very important in the IoT domain. Apart from the computational challenges, I also recall naive approximations causing the auction to lose incentive compatibility. I would be interested in how we could address this problem.

[davidrpugh]

More papers on combinatoric auctions...

http://www.cramton.umd.edu/papers2005-2009/cramton-shoham-steinberg-overview-of-combinatorial-auctions.pdf http://www.cramton.umd.edu/papers2000-2004/cramton-shoham-steinberg-introduction-to-combinatorial-auctions.pdf http://www.cramton.umd.edu/papers2000-2004/combinatorial-auctions-book-public.htm

[davidrpugh]

@bherd-rb You are correct that incentive compatibility goes out the window once you start using heuristics to approximate the optimal allocation. An interesting and important question is to what extent autonomous trading agents will learn not to bid their true valuations when trading in such an auction.