IDEAS home Printed from https://ideas.repec.org/p/ads/wpaper/0039.html
   My bibliography  Save this paper

The Communication Requirements of of Social Choice Rules and Supporting Budget Sets

Author

Listed:
  • Ilya Segal

    (Department of Economics, Stanford University)

Abstract

The paper examines the communication requirements of social choice rules when the (sincere) agents privately know their preferences. It shows that for a large class of choice rules, any communication verifying that an alternative is in the rule must reveal supporting budget sets for the agents such that the optimality of the proposed alternative to all agents within their respective budget set in itself verifies the alternative. We characterize the budget equilibria that are the minimally informative messages verifying a given choice rule. This characterization is used to identify the communication burden of choice rules, measured with the number of transmitted bits or real variables. Applications include efficiency in convex economies, exact or approximate surplus maximization in combinatorial auctions, the core in indivisible good economies, and stable many-to-one matchings.

Suggested Citation

  • Ilya Segal, 2004. "The Communication Requirements of of Social Choice Rules and Supporting Budget Sets," Economics Working Papers 0039, Institute for Advanced Study, School of Social Science.
    • Handle: RePEc:ads:wpaper:0039
    as

    Download full text from publisher

    File URL: http://www.sss.ias.edu/publications/papers/econpaper39.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Sen, Amartya Kumar, 1970. "The Impossibility of a Paretian Liberal," Scholarly Articles 3612779, Harvard University Department of Economics.
    2. Sen, Amartya, 1970. "The Impossibility of a Paretian Liberal," Journal of Political Economy, University of Chicago Press, vol. 78(1), pages 152-157, Jan.-Feb..
    3. Moulin, H. & Peleg, B., 1982. "Cores of effectivity functions and implementation theory," Journal of Mathematical Economics, Elsevier, vol. 10(1), pages 115-145, June.
    4. Takashi Ishikida & Thomas Marschak, 1996. "Mechanisms that efficiently verify the optimality of a proposed action," Review of Economic Design, Springer;Society for Economic Design, vol. 2(1), pages 33-68, December.
    5. Calsamiglia, Xavier, 1977. "Decentralized resource allocation and increasing returns," Journal of Economic Theory, Elsevier, vol. 14(2), pages 263-283, April.
    6. Echenique, Federico, 2007. "Counting combinatorial choice rules," Games and Economic Behavior, Elsevier, vol. 58(2), pages 231-245, February.
    7. Roth,Alvin E. & Sotomayor,Marilda A. Oliveira, 1992. "Two-Sided Matching," Cambridge Books, Cambridge University Press, number 9780521437882.
    8. Williams, Steven R, 1986. "Realization and Nash Implementation: Two Aspects of Mechanism Design," Econometrica, Econometric Society, vol. 54(1), pages 139-151, January.
    9. Jordan, J. S., 1982. "The competitive allocation process is informationally efficient uniquely," Journal of Economic Theory, Elsevier, vol. 28(1), pages 1-18, October.
    10. Mount, Kenneth & Reiter, Stanley, 1974. "The informational size of message spaces," Journal of Economic Theory, Elsevier, vol. 8(2), pages 161-192, June.
    11. Reichelstein, Stefan, 1984. "Incentive compatibility and informational requirements," Journal of Economic Theory, Elsevier, vol. 34(1), pages 32-51, October.
    12. Tomas Sjöström, 1994. "Implementation by demand mechanisms," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 343-354, December.
    13. Serrano, Roberto & Volij, Oscar, 2000. "Walrasian Allocations without Price-Taking Behavior," Journal of Economic Theory, Elsevier, vol. 95(1), pages 79-106, November.
    14. Kannai, Yakar, 1970. "Continuity Properties of the Core of a Market," Econometrica, Econometric Society, vol. 38(6), pages 791-815, November.
    15. repec:dau:papers:123456789/13220 is not listed on IDEAS
    16. Milleron, Jean-Claude, 1972. "Theory of value with public goods: A survey article," Journal of Economic Theory, Elsevier, vol. 5(3), pages 419-477, December.
    17. Eric Maskin, 1999. "Nash Equilibrium and Welfare Optimality," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 66(1), pages 23-38.
    18. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    19. Bikhchandani, Sushil & Mamer, John W., 1997. "Competitive Equilibrium in an Exchange Economy with Indivisibilities," Journal of Economic Theory, Elsevier, vol. 74(2), pages 385-413, June.
    20. McLean, Richard P. & Postlewaite, Andrew, 1989. "Excess functions and nucleolus allocations of pure exchange economies," Games and Economic Behavior, Elsevier, vol. 1(2), pages 131-143, June.
    21. Reichelstein, Stefan & Reiter, Stanley, 1988. "Game Forms with Minimal Message Spaces," Econometrica, Econometric Society, vol. 56(3), pages 661-692, May.
    22. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    23. Nisan, Noam & Segal, Ilya, 2006. "The communication requirements of efficient allocations and supporting prices," Journal of Economic Theory, Elsevier, vol. 129(1), pages 192-224, July.
    24. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    25. Sato, Fumitaka, 1981. "On the informational size of message spaces for resource allocation processes in economies with public goods," Journal of Economic Theory, Elsevier, vol. 24(1), pages 48-69, February.
    26. John W. Hatfield & Paul Milgrom, 2005. "Auctions, Matching and the Law of Aggregate Demand," Levine's Bibliography 122247000000000780, UCLA Department of Economics.
    27. Guoqiang Tian, 2004. "A Unique Informationally Efficient Allocation Mechanism In Economies With Consumption Externalities," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 45(1), pages 79-111, February.
    28. Andreu Mas-Colell, 1980. "Efficiency and Decentralization in the Pure Theory of Public Goods," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 94(4), pages 625-641.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Daron Acemoglu & Michael Golosov & Aleh Tsyvinski, 2006. "Markets Versus Governments: Political Economy of Mechanisms," Levine's Bibliography 321307000000000032, UCLA Department of Economics.
    2. Marschak, Thomas, 2006. "Organization Structure," MPRA Paper 81518, University Library of Munich, Germany.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Segal, Ilya, 2007. "The communication requirements of social choice rules and supporting budget sets," Journal of Economic Theory, Elsevier, vol. 136(1), pages 341-378, September.
    2. Nisan, Noam & Segal, Ilya, 2006. "The communication requirements of efficient allocations and supporting prices," Journal of Economic Theory, Elsevier, vol. 129(1), pages 192-224, July.
    3. Tian, Guoqiang, 2004. "On the Informational Requirements of Decentralized Pareto-Satisfactory Mechanisms in Economies with Increasing Returns," MPRA Paper 41226, University Library of Munich, Germany, revised Oct 2006.
    4. Marschak, Thomas, 2006. "Organization Structure," MPRA Paper 81518, University Library of Munich, Germany.
    5. Maskin, Eric & Sjostrom, Tomas, 2002. "Implementation theory," Handbook of Social Choice and Welfare,in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 5, pages 237-288 Elsevier.
    6. Tian, Guoqiang, 2001. "The Unique Informational Effciency of the Lindahl Allocation Process in Economies with Public Goods," MPRA Paper 41229, University Library of Munich, Germany, revised Oct 2005.
    7. Ozan Candogan & Asuman Ozdaglar & Pablo A. Parrilo, 2015. "Iterative Auction Design for Tree Valuations," Operations Research, INFORMS, vol. 63(4), pages 751-771, August.
    8. Martin Bichler & Pasha Shabalin & Georg Ziegler, 2013. "Efficiency with Linear Prices? A Game-Theoretical and Computational Analysis of the Combinatorial Clock Auction," Information Systems Research, INFORMS, vol. 24(2), pages 394-417, June.
    9. Mehmet Barlo & Nuh Aygün Dalkıran, 2022. "Computational implementation," Review of Economic Design, Springer;Society for Economic Design, vol. 26(4), pages 605-633, December.
    10. Ozan Candogan & Saša Pekeč, 2018. "Efficient Allocation and Pricing of Multifeatured Items," Management Science, INFORMS, vol. 64(12), pages 5521-5543, December.
    11. Michel Le Breton & Juan Moreno-Ternero & Alexei Savvateev & Shlomo Weber, 2013. "Stability and fairness in models with a multiple membership," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 673-694, August.
    12. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    13. Kenneth R. Mount & Stanley Reiter, 1996. "A lower bound on computational complexity given by revelation mechanisms (*)," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(2), pages 237-266.
    14. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    15. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    16. Goossens, D.R. & Müller, R.J. & Spieksma, F.C.R., 2007. "Matrix bids in combinatorial auctions: expressiveness and micro-economic properties," Research Memorandum 016, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    17. Kovalenkov, Alexander & Wooders, Myrna, 2003. "Approximate cores of games and economies with clubs," Journal of Economic Theory, Elsevier, vol. 110(1), pages 87-120, May.
    18. Saptarshi Mukherjee & Hans Peters, 2022. "Self-implementation of social choice correspondences in Nash equilibrium," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(4), pages 1009-1028, November.
    19. Blumrosen, Liad & Nisan, Noam, 2010. "Informational limitations of ascending combinatorial auctions," Journal of Economic Theory, Elsevier, vol. 145(3), pages 1203-1223, May.
    20. Dries R. Goossens & Rudolf Müller & Frits C. R. Spieksma, 2010. "Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 339-352, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ads:wpaper:0039. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Nancy Cotterman (email available below). General contact details of provider: https://edirc.repec.org/data/ssiasus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.