Output details
11 - Computer Science and Informatics
Teesside University
Mechanisms for multi-unit combinatorial auctions with a few distinct goods
<22> This recent work won Best Paper prize for AAMAS 2013, out of 612 submissions, and has been invited, as spotlight talk, to AAAI 2013 and to a special JAIR track for award-winning papers from selected AI conferences. Combinatorial Auctions (CAs) is the paradigmatic problem in mechanism design showing the tension between computer science and economics. The techniques developed in the two disciplines seem inadequate to design a deterministic polynomial-time algorithm that guarantees best possible approximation for CAs and is part of a truthful mechanism. This paper shows that this is not the case when the items on sale are few.