IDEAS home Printed from https://ideas.repec.org/p/ebg/heccah/0926.html
   My bibliography  Save this paper

Mechanism design and communication networks

Author

Listed:
  • Tomala, Tristan
  • Renou, Ludovic

Abstract

This paper studies a mechanism design model where the players and the designer are nodes in a communication network. The authors characterize the communication networks (directed graphs) for which, in any environment (utilities and beliefs), every incentive compatible social choice function is implementable. They show that any incentive compatible social choice function is implementable on a given communication network, in all environments with either common independent beliefs and private values or a worst outcome, if and only if the network is strongly connected and weakly 2-connected. A network is strongly connected if for each player, there exists a directed path to the designer. It is weakly 2-connected if each player is either directly connected to the designer or indirectly connected to the designer through two disjoint paths, not necessarily directed. They couple encryption techniques together with appropriate incentives to secure the transmission of each player’s private information to the designer.

Suggested Citation

  • Tomala, Tristan & Renou, Ludovic, 2010. "Mechanism design and communication networks," HEC Research Papers Series 926, HEC Paris.
  • Handle: RePEc:ebg:heccah:0926
    as

    Download full text from publisher

    File URL: http://www.hec.fr/var/fre/storage/original/application/1bc9ede1c35ec59d923620ea35f90d79.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Dirk Bergemann & Stephen Morris, 2012. "Robust Implementation in Direct Mechanisms," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 4, pages 153-194, World Scientific Publishing Co. Pte. Ltd..
    2. Patrick Bolton & Mathias Dewatripont, 1994. "The Firm as a Communication Network," The Quarterly Journal of Economics, Oxford University Press, vol. 109(4), pages 809-839.
    3. Dirk Bergemann & Stephen Morris, 2012. "Robust Mechanism Design," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 2, pages 49-96, World Scientific Publishing Co. Pte. Ltd..
    4. Myerson, Roger B, 1979. "Incentive Compatibility and the Bargaining Problem," Econometrica, Econometric Society, vol. 47(1), pages 61-73, January.
    5. Forges, Francoise, 1990. "Universal Mechanisms," Econometrica, Econometric Society, vol. 58(6), pages 1341-1364, November.
    6. Guido Friebel & Michael Raith, 2004. "Abuse of Authority and Hierarchical Communication," RAND Journal of Economics, The RAND Corporation, vol. 35(2), pages 224-244, Summer.
    7. Krishna, Vijay, 2009. "Auction Theory," Elsevier Monographs, Elsevier, edition 2, number 9780123745071, December.
    8. Jackson, Matthew O, 1991. "Bayesian Implementation," Econometrica, Econometric Society, vol. 59(2), pages 461-477, March.
    9. Salanié, Bernard, 2011. "The Economics of Taxation," MIT Press Books, The MIT Press, edition 2, volume 1, number 0262016346.
    10. Serrano, Roberto & Vohra, Rajiv, 2010. "Multiplicity of mixed equilibria in mechanisms: A unified approach to exact and approximate implementation," Journal of Mathematical Economics, Elsevier, vol. 46(5), pages 775-785, September.
    11. Harris Milton & Townsend, Robert M, 1981. "Resource Allocation under Asymmetric Information," Econometrica, Econometric Society, vol. 49(1), pages 33-64, January.
    12. Ben-Porath, Elchanan, 2003. "Cheap talk in games with incomplete information," Journal of Economic Theory, Elsevier, vol. 108(1), pages 45-71, January.
    13. Tristan Tomala, 2008. "Probabilistic Reliability and Privacy of Communication Using Multicast in General Neighbor Networks," Post-Print hal-00464542, HAL.
    14. Gerardi, Dino, 2004. "Unmediated communication in games with complete and incomplete information," Journal of Economic Theory, Elsevier, vol. 114(1), pages 104-131, January.
    15. Partha Dasgupta & Peter Hammond & Eric Maskin, 1979. "The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility," Review of Economic Studies, Oxford University Press, vol. 46(2), pages 185-216.
    16. 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.
    17. 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.
    18. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    19. Timothy Van Zandt, 2007. "Communication Complexity and Mechanism Design," Journal of the European Economic Association, MIT Press, vol. 5(2-3), pages 543-553, 04-05.
    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. Peters, Michael & Troncoso-Valverde, Cristián, 2013. "A folk theorem for competing mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 953-973.
    2. Renault, Jérôme & Renou, Ludovic & Tomala, Tristan, 2014. "Secure message transmission on directed networks," Games and Economic Behavior, Elsevier, vol. 85(C), pages 1-18.
    3. Mohamed Belhaj & Sebastian Bervoets & Frédéric Deroïan, 2013. "Network Design under Local Complementarities," Working Papers halshs-00796487, HAL.
    4. Rene Saran & Norovsambuu Tumennasan, 2015. "Implementation by Sortition in Nonexclusive Information Economies," Economics Working Papers 2015-13, Department of Economics and Business Economics, Aarhus University.
    5. Marie Laclau & Ludovic Renou & Xavier Venel, 2020. "Robust communication on networks," Papers 2007.00457, arXiv.org, revised Oct 2020.
    6. Rivera, Thomas J., 2018. "Incentives and the structure of communication," Journal of Economic Theory, Elsevier, vol. 175(C), pages 201-247.
    7. Pinghan Liang, 2010. "Transfer of Authority within Hierarchy," Levine's Working Paper Archive 661465000000000139, David K. Levine.

    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. Corchón, Luis C., 2008. "The theory of implementation : what did we learn?," UC3M Working papers. Economics we081207, Universidad Carlos III de Madrid. Departamento de Economía.
    2. Shimoji, Makoto & Schweinzer, Paul, 2015. "Implementation without incentive compatibility: Two stories with partially informed planners," Games and Economic Behavior, Elsevier, vol. 91(C), pages 258-267.
    3. Izmalkov, Sergei & Lepinski, Matt & Micali, Silvio, 2011. "Perfect implementation," Games and Economic Behavior, Elsevier, vol. 71(1), pages 121-140, January.
    4. Roberto Serrano, 2003. "The Theory of Implementation of Social Choice Rules," Working Papers 2003-19, Brown University, Department of Economics.
    5. Blume, Lawrence & Easley, David & Kleinberg, Jon & Kleinberg, Robert & Tardos, Éva, 2015. "Introduction to computer science and economic theory," Journal of Economic Theory, Elsevier, vol. 156(C), pages 1-13.
    6. Bergemann, Dirk & Morris, Stephen & Takahashi, Satoru, 2017. "Interdependent preferences and strategic distinguishability," Journal of Economic Theory, Elsevier, vol. 168(C), pages 329-371.
    7. Serrano, Roberto & Ray, Indrajit & Kar, Anirban, 2005. "Multiple equilibria as a difficulty in understanding correlated distributions," UC3M Working papers. Economics we057238, Universidad Carlos III de Madrid. Departamento de Economía.
    8. Dirk Bergemann & Stephen Morris & Olivier Tercieux, 2012. "Rationalizable Implementation," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 11, pages 375-404, World Scientific Publishing Co. Pte. Ltd..
    9. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2020. "Arrow on domain conditions: a fruitful road to travel," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 237-258, March.
    10. Moritz Meyer-ter-Vehn & Stephen Morris, 2012. "The Robustness of Robust Implementation," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 10, pages 357-373, World Scientific Publishing Co. Pte. Ltd..
    11. Claude d'Aspremont & Jacques Crémer & Louis-André Gérard-Varet, 2003. "Correlation, independence, and Bayesian incentives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(2), pages 281-310, October.
    12. de Castro, Luciano I. & Liu, Zhiwei & Yannelis, Nicholas C., 2017. "Implementation under ambiguity," Games and Economic Behavior, Elsevier, vol. 101(C), pages 20-33.
    13. Dirk Bergemann & Stephen Morris, 2012. "Ex Post Implementation," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 3, pages 97-152, World Scientific Publishing Co. Pte. Ltd..
    14. Renault, Jérôme & Renou, Ludovic & Tomala, Tristan, 2014. "Secure message transmission on directed networks," Games and Economic Behavior, Elsevier, vol. 85(C), pages 1-18.
    15. Victor V. Claar, 1998. "An Incentive-Compatibility Approach To the Problem of Monitoring a Bureau," Public Finance Review, , vol. 26(6), pages 599-610, November.
    16. Sumit K. Majumdar, 2010. "Incentive Compatible Mechanism Design And Firm Growth: Experiences From Telecommunications Sector Regulation," Annals of Public and Cooperative Economics, Wiley Blackwell, vol. 81(3), pages 357-387, September.
    17. Matsushima, Hitoshi, 2008. "Detail-free mechanism design in twice iterative dominance: Large economies," Journal of Economic Theory, Elsevier, vol. 141(1), pages 134-151, July.
    18. Roger B. Myerson, 1988. "Mechanism Design," Discussion Papers 796, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    19. Kar, Anirban & Ray, Indrajit & Serrano, Roberto, 2010. "A difficulty in implementing correlated equilibrium distributions," Games and Economic Behavior, Elsevier, vol. 69(1), pages 189-193, May.
    20. Mezzetti, Claudio & Renou, Ludovic, 2012. "Implementation in mixed Nash equilibrium," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2357-2375.

    More about this item

    Keywords

    Mechanism design; incentives; Bayesian equilibrium; communication networks; encryption; secure transmission;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:ebg:heccah:0926. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: https://edirc.repec.org/data/hecpafr.html .

    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: Antoine Haldemann (email available below). General contact details of provider: https://edirc.repec.org/data/hecpafr.html .

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.