[2M1-GS-7] Agents: Multi-agent system (1)

[2M1-GS-7-04] Designing Strategy-Proof and Non-Wasteful Mechanisms for Auction via Social Network

〇Takehiro Kawasaki¹, Seiji Takanashi², Taiki Todo¹, Makoto Yokoo¹ (1. Kyushu University, 2. Kyoto University)

Keywords:mechanism design, network auction, strategy-proofness, non-wastefulness

A network auction is a one of the auction models where an agent spreads information to her followers on a network by using connection among agents like SNS. By designing a mechanism with an incentive for buyers to spread information, a seller can propagate information widely through the network. From the buyers' perspective, however, forwarding the information increases the number of her rivals, which reduces the possibility that they will get the item. In this paper, we propose a mechanism in which each buyer is incentivized to forward the information to as many followers as possible and to report their valuation truthfully. We also show that a slightly modified version of this mechanism (which introduces a reservation price) has a constant inefficiency factor of 1/2.