Implementing a strategyproof greedy-allocation combinatorial auction and extending to ascending auction
✍ Scribed by Takayuki Ito; Makoto Yokoo; Shigeo Matsubara; Atsushi Iwasaki
- Publisher
- John Wiley and Sons
- Year
- 2007
- Tongue
- English
- Weight
- 482 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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, that is, 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. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 44–51, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20748