A New Strategy-Proof Greedy-Allocation Combinatorial Auction Protocol and its Extension to Open Ascending Auction Protocol

Takayuki Ito, Makoto Yokoo, Shigeo Matsubara, Atsushi Iwasaki

This paper proposes a new combinatorial auction protocol called Average-Max-Minimal-Bundle (AM-MB) protocol. The characteristics of the AM-MB protocol are as follows: (i) it is strategyproof, i.e., truth-telling is a dominant strategy, (ii) the computational overhead is very low, since it allocates bundles greedily thereby avoiding an explicit combinatorial optimization problem, and (iii) it can obtain higher social surplus and revenue than can the Max-Minimal-Bundle (M-MB) protocol, which also satisfies (i) and (ii). Furthermore, this paper extends the AM-MB protocol to an open ascending-price protocol in which straightforward bidding is an ex-post Nash equilibrium.

Content Area: 4. Auctions and Market-Based Systems

Subjects: 7.1 Multi-Agent Systems; 7. Distributed AI

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.