Sequential partition mechanism for strongly budget-balanced redistribution

ABSTRACT

We propose a new class of strategy-proof and strongly budget-balanced redistribution mechanisms called the sequential partition mechanism (SPM). Recently, studies on redistribution mechanisms have attracted increased attention in the research area of mechanism design to achieve a desirable social decision among self-interested agents. However, since no redistribution mechanism can simultaneously satisfy Pareto efficiency, strategy-proofness, individual rationality, and is strongly budget-balanced, we need to sacrifice one of these properties.

In the SPM, agents and items are divided into groups, and then a strategy-proof mechanism is sequentially applied to each group. The payments in each group are distributed among agents in the remaining groups in a predefined way. The auctioneer can dynamically determine how to divide agents and items and which mechanism to apply, based on the results of previous auctions. As an instance of the SPM, we introduce the redistribution mechanism based on a take-it-or-leave-it auction (RM-TLA) mechanism. The RM-TLA does not require agents to reveal a bidding price. Thus, the agents only have to accept/reject the offered price. Furthermore, we show that we can set the optimal reserve price so that the expected social surplus is maximized if an auctioneer knows the distribution of an agent's valuation in advance.

REFERENCES

• 1: Ruggiero Cavallo, Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160790]
• 2: B. Faltings. A budget-balanced, incentive-compatible scheme for social choice. In AMEC'04, pages 30--43, 2004.
• 3: Mingyu Guo , Vincent Conitzer, Better redistribution with inefficient allocation in multi-unit auctions with unit demand, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386825]
• 4: Mingyu Guo , Vincent Conitzer, Optimal-in-expectation redistribution mechanisms, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 5: Tuomas Sandholm , Andrew Gilpin, Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160839]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Economics, Theory

Keywords:
budget-balance, mechanism design, redistribution, strategy-proofness