Conference proceeding
Positive results for mechanism design without money
Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp 1165-1166
06 May 2013
Abstract
Consider the problem of allocating multiple divisible goods to two agents in a strategy-proof fashion without the use of payments or priors. Previous work has aimed at implementing allocations that are competitive with respect to an appropriately defined measure of social welfare. These results have mostly been negative, proving that no dictatorial mechanism can achieve an approximation factor better than 0.5, and leaving open the question of whether there exists a non-dictatorial mechanism that outperforms this bound. We provide a positive answer to this question by presenting an interesting non-dictatorial mechanism that achieves an approximation factor of 2/3 for this measure of social welfare. In proving this bound we also touch on the issue of fairness: we show that the proportionally fair solution, a well known fairness concept for money-free settings, is highly competitive with respect to social welfare. We then show how to use the proportionally fair solution to design our non-dictatorial strategy-proof mechanism.
Metrics
6 Record Views
Details
- Title
- Positive results for mechanism design without money
- Creators
- Richard Cole - New York UniversityVasilis Gkatzelis - New York UniversityGagan Goel - Google
- Publication Details
- Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp 1165-1166
- Conference
- AAMAS '13: International conference on Autonomous Agents and Multi-Agent Systems, 13th (2013)
- Series
- ACM Other Conferences
- Publisher
- International Foundation for Autonomous Agents and Multiagent Systems
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991021868727504721