Almost budget-balanced VCG mechanisms to assign multiple objects

E. Anshelevich, A. Dasgupta, E. Tardos, T. Wexler, Near-optimal network design with selfish agents, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2004 M. Atlamaz, D. Yengin, Fair groves mechanisms, Mimeo, Rochester University, 2006 Bailey, 1997, The demand revealing process: To distribute the surplus, Public Choice, 91, 107, 10.1023/A:1017949922773 Baliga, 2003, Market research and market design, Adv. Theor. Econ., 3, 1, 10.2202/1534-5963.1059 R. Cavallo, Optimal decision-making with minimal waste: Strategyproof redistribution of VCG payments, in: International Conference on Autonomous Agents and Multi-agents Systems, (AAMAS) Hakodate, Japan, 2006 Y. Chen, J. Zhang, Design of price mechanisms for network resource allocation via price of anarchy, Mimeo, New York University, 2005 Deb, 2002, Welfare asymptotics of the pivotal mechanism for excludable public goods, Math. Soc. Sci., 43, 209, 10.1016/S0165-4896(01)00092-0 Deb, 1998, Maximal surplus from the pivotal mechanism: A closed form solution, Rev. Econ. Design, 3, 347, 10.1007/s100580050020 Gary-Bobo, 2000, Polling mechanisms and the demand revelation problem, J. Public Econ., 76, 203, 10.1016/S0047-2727(99)00059-6 M. Guo, V. Conitzer, Worst case optimal redistribution of VCG payments, in: Proceedings of the 8th ACM Conference on Electronic Commerce (EC-07), San Diego, CA, June 2007, pp. 30–39 M. Guo, V. Conitzer, Optimal-in-expectation redistribution mechanisms, in: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS-08), Estoril, Portugal, 2008 M. Guo, V. Conitzer, Better redistribution mechanisms through inefficient allocation, in: Proceedings of the 9th ACM Conference on Electronic Commerce (EC-08), Chicago, IL, USA, 2008, in press Goldberg, 2006, Competitive auctions, Games Econ. Behav., 55, 242, 10.1016/j.geb.2006.02.003 Green, 1979 Johari, 2004, Efficiency loss in a network resource allocation game, Math. Oper. Res., 29, 407, 10.1287/moor.1040.0091 R. Johari, J. Tsitsiklis, Efficiency of scalar parametrized mechanisms, Mimeo, Stanford, MIT, 2007 Johari, 2005, Efficiency loss in a network resource allocation game: The case of elastic supply, IEEE Trans. Automat. Control, 50, 1712, 10.1109/TAC.2005.858687 Juarez-Garcia, 2008, The worst absolute surplus loss in the problem of the commons: Random priority versus average cost, Econ. Theory, 34, 69, 10.1007/s00199-006-0165-8 E. Koutsoupias, C. Papadimitriou, Worst case equilibria, in: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, 1999, pp. 404–413 Laffont, 1979, A differential approach to expected utility maximizing mechanisms McAfee, 1992, A dominant strategy double auction, J. Econ. Theory, 56, 434, 10.1016/0022-0531(92)90091-U Moulin, 1986, Characterizations of the pivotal mechanism, J. Public Econ., 31, 53, 10.1016/0047-2727(86)90071-X Moulin, 2008, The price of anarchy of serial, average, and incremental cost sharing, Econ. Theory, 36, 379, 10.1007/s00199-007-0275-y H. Moulin, Efficient cost sharing with a cheap residual claimant, Mimeo, Rice University, 2006 H. Moulin, Auctioning or assigning an object: Some remarkable VCG mechanisms, Mimeo, Rice University, 2007 Moulin, 2001, Strategy-proof sharing of submodular costs: Budget balance versus efficiency, Econ. Theory, 18, 511, 10.1007/PL00004200 Porter, 2004, Fair imposition, J. Econ. Theory, 118, 209, 10.1016/j.jet.2003.11.005 T. Roughgarden, Te price of anarchy is independent of the network topology, in: STOC, 2002 T. Roughgarden, M. Sundararajan, Approximately efficient cost-sharing mechanisms, Mimeo, Stanford University, 2006 T. Roughgarden, M. Sundararajan, New trade-offs in cost sharing mechanisms, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 79–88 Roughgarden, 2002, How bad is selfish routing?, J. ACM, 49, 236, 10.1145/506147.506153 S. Sanghavi, B. Hajek, Optimal allocation of a divisible good to strategic buyers, in: Proceedings of the 43rd IEEE Conference on Decision and Control, 2004 M. Tennenholtz, Rational competitive analysis, in: IJCAI-01, 2001 S. Yang, B. Hajek, Revenue and stability of a mechanism for efficient allocation of a divisible good, Mimeo, University of Illinois at Urbana Champaign, 2005 L. Zhou, The failure of groves mechanisms in canonical allocation models, Mimeo, Arizona State University, 2007