Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network

Authors

  • Takehiro Kawasaki Kyushu University
  • Nathanael Barrot RIKEN AIP
  • Seiji Takanashi Kyoto University
  • Taiki Todo Kyushu University
  • Makoto Yokoo Kyushu University

DOI:

https://doi.org/10.1609/aaai.v34i02.5579

Abstract

Auctions via social network, pioneered by Li et al. (2017), have been attracting considerable attention in the literature of mechanism design for auctions. However, no known mechanism has satisfied strategy-proofness, non-deficit, non-wastefulness, and individual rationality for the multi-unit unit-demand auction, except for some naïve ones. In this paper, we first propose a mechanism that satisfies all the above properties. We then make a comprehensive comparison with two naïve mechanisms, showing that the proposed mechanism dominates them in social surplus, seller's revenue, and incentive of buyers for truth-telling. We also analyze the characteristics of the social surplus and the revenue achieved by the proposed mechanism, including the constant approximability of the worst-case efficiency loss and the complexity of optimizing revenue from the seller's perspective.

Downloads

Published

2020-04-03

How to Cite

Kawasaki, T., Barrot, N., Takanashi, S., Todo, T., & Yokoo, M. (2020). Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 2062-2069. https://doi.org/10.1609/aaai.v34i02.5579

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms