TY - GEN
T1 - Incentive compatible multi unit combinatorial auctions
AU - Bartal, Yair
AU - Gonen, Rica
AU - Nisan, Noam
PY - 2003/6/20
Y1 - 2003/6/20
N2 - This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to single minded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.
AB - This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to single minded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.
UR - http://www.scopus.com/inward/record.url?scp=85013990027&partnerID=8YFLogxK
U2 - 10.1145/846241.846250
DO - 10.1145/846241.846250
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:85013990027
T3 - Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2003
SP - 72
EP - 87
BT - Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2003
A2 - Tennenholtz, Moshe
PB - Association for Computing Machinery, Inc
T2 - 9th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2003
Y2 - 20 June 2003 through 22 June 2003
ER -