IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Login to save this book chapter or follow this series

Implementation theory

In: Handbook of Social Choice and Welfare

  • Maskin, Eric
  • Sjostrom, Tomas

The implementation problem is the problem of designing a mechanism (game form) such that the equilibrium outcomes satisfy a criterion of social optimality embodied in a social choice rule. If a mechanism has the property that, in each possible state of the world, the set of equilibrium outcomes equals the set of optimal outcomes identified by the social choice rule, then the social choice rule is said to be implemented by this mechanism. Whether or not a social choice rule is implementable may depend on which game-theoretic solution concept is used. The most demanding requirement is that each agent should always have a dominant strategy, but mainly negative results are obtained in this case. More positive results are obtained using less demanding solution concepts such as Nash equilibrium. Any Nash-implementable social choice rule must satisfy a condition of "monotonicity". Conversely, any social choice rule which satisfies monotonicity and "no veto power" can be Nash-implemented. Even non-monotonic social choice rules can be implemented using Nash equilibrium refinements. The implementation problem can be made more challenging by imposing additional requirements on the mechanisms, such as robustness to renegotiation and collusion. If the agents are incompletely informed about the state of the world, then the concept of Nash equilibrium is replaced by Bayesian Nash equilibrium. Incentive compatibility is a necessary condition for Bayesian Nash implementation, but in other respects the results closely mimic those that obtain with complete information.

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://www.sciencedirect.com/science/article/B7P65-4FFPH86-9/2/bfcccd08faf9ab044aac4b356552009e
Download Restriction: Full text for ScienceDirect subscribers only

As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.

as
in new window

This chapter was published in:
  • K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
  • This item is provided by Elsevier in its series Handbook of Social Choice and Welfare with number 1-05.
    Handle: RePEc:eee:socchp:1-05
    Contact details of provider: Web page: http://www.elsevier.com/wps/find/bookseriesdescription.cws_home/BS_HE/description

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

    as in new window
    1. Farrell Joseph, 1993. "Meaning and Credibility in Cheap-Talk Games," Games and Economic Behavior, Elsevier, vol. 5(4), pages 514-531, October.
    2. Serrano, Roberto & Vohra, Rajiv, 2001. "Some Limitations of Virtual Bayesian Implementation," Econometrica, Econometric Society, vol. 69(3), pages 785-92, May.
    3. Hurwicz, L, 1979. "Outcome Functions Yielding Walrasian and Lindahl Allocations at Nash Equilibrium Points," Review of Economic Studies, Wiley Blackwell, vol. 46(2), pages 217-25, April.
    4. Kenneth Mount & Stanley Reiter, 1973. "The Informational Size of Message Spaces," Discussion Papers 3, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    5. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
    6. Hurwicz, Leonid & Walker, Mark, 1990. "On the Generic Nonoptimality of Dominant-Strategy Allocation Mechanisms: A General Theorem That Includes Pure Exchange Economies," Econometrica, Econometric Society, vol. 58(3), pages 683-704, May.
    7. Crawford, Vincent P, 1979. "A Procedure for Generating Pareto-Efficient Egalitarian-Equivalent Allocations," Econometrica, Econometric Society, vol. 47(1), pages 49-60, January.
    8. Baliga, Sandeep & Sjostrom, Tomas, 1999. "Interactive Implementation," Games and Economic Behavior, Elsevier, vol. 27(1), pages 38-63, April.
    9. Mookherjee, Dilip & Reichelstein, Stefan, 1990. "Implementation via Augmented Revelation Mechanisms," Review of Economic Studies, Wiley Blackwell, vol. 57(3), pages 453-75, July.
    10. Groves, Theodore & Loeb, Martin, 1975. "Incentives and public inputs," Journal of Public Economics, Elsevier, vol. 4(3), pages 211-226, August.
    11. Saijo, Tatsuyoshi, 1987. "On constant maskin monotonic social choice functions," Journal of Economic Theory, Elsevier, vol. 42(2), pages 382-386, August.
    12. Sandeep Baliga & Sandro Brusco, 2000. "Collusion, renegotiation and implementation," Social Choice and Welfare, Springer, vol. 17(1), pages 69-83.
    13. Naoki Yoshihara, 2000. "A characterization of natural and double implementation in production economies," Social Choice and Welfare, Springer, vol. 17(4), pages 571-599.
    14. Satterthwaite, Mark A & Sonnenschein, Hugo, 1981. "Strategy-Proof Allocation Mechanisms at Differentiable Points," Review of Economic Studies, Wiley Blackwell, vol. 48(4), pages 587-97, October.
    15. Deb, Rajat & Pattanaik, Prasanta K. & Razzolini, Laura, 1997. "Game Forms, Rights, and the Efficiency of Social Outcomes," Journal of Economic Theory, Elsevier, vol. 72(1), pages 74-95, January.
    16. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
    17. Saijo, T. & Tatamitani, Y. & Yamato, T., 1994. "Toward Natural Implementation," ISER Discussion Paper 0340, Institute of Social and Economic Research, Osaka University.
      • Saijo, Tatsuyoshi & Tatamitani, Yoshikatsu & Yamato, Takehiko, 1996. "Toward Natural Implementation," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 37(4), pages 949-80, November.
    18. Maskin, Eric & Tirole, Jean, 1999. "Unforeseen Contingencies and Incomplete Contracts," Review of Economic Studies, Wiley Blackwell, vol. 66(1), pages 83-114, January.
    19. Palfrey, Thomas R & Srivastava, Sanjay, 1989. "Mechanism Design with Incomplete Information: A Solution to the Implementation Problem," Journal of Political Economy, University of Chicago Press, vol. 97(3), pages 668-91, June.
    20. De Trenqualye, Pierre, 1988. "Stability of the Groves and Ledyard mechanism," Journal of Economic Theory, Elsevier, vol. 46(1), pages 164-171, October.
    21. Schmeidler, David, 1980. "Walrasian Analysis via Strategic Outcome Functions," Econometrica, Econometric Society, vol. 48(7), pages 1585-93, November.
    22. Dasgupta, Partha S & Hammond, Peter J & Maskin, Eric S, 1979. "The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility," Review of Economic Studies, Wiley Blackwell, vol. 46(2), pages 185-216, April.
    23. Moore, John & Repullo, Rafael, 1990. "Nash Implementation: A Full Characterization," Econometrica, Econometric Society, vol. 58(5), pages 1083-99, September.
    24. repec:fth:calaec:6-98 is not listed on IDEAS
    25. Bezalel Peleg, 1997. "Effectivity functions, game forms, games, and rights," Social Choice and Welfare, Springer, vol. 15(1), pages 67-80.
    26. d'ASPREMONT, Claude & GERARD-VARET, Louis-André, . "Incentives and incomplete information," CORE Discussion Papers RP -354, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    27. Brusco, Sandro, 1995. "Perfect Bayesian Implementation," Economic Theory, Springer, vol. 5(3), pages 419-44, May.
    28. Jackson, Matthew O, 1992. "Implementation in Undominated.Strategies: A Look at Bounded Mechanisms," Review of Economic Studies, Wiley Blackwell, vol. 59(4), pages 757-75, October.
    29. Glazer, Jacob & Rosenthal, Robert W, 1992. "A Note on Abreu-Matsushima Mechanisms," Econometrica, Econometric Society, vol. 60(6), pages 1435-38, November.
    30. Jackson, Matthew O. & Palfrey, Thomas R., 2001. "Voluntary Implementation," Journal of Economic Theory, Elsevier, vol. 98(1), pages 1-25, May.
    31. Hurwicz, Leonid & Schmeidler, David, 1978. "Construction of Outcome Functions Guaranteeing Existence and Pareto Optimality of Nash Equilibria," Econometrica, Econometric Society, vol. 46(6), pages 1447-74, November.
    32. Tomas Sjostrom, 1997. "Undominated Nash Implementaion with Collusion and Renegotiation," Harvard Institute of Economic Research Working Papers 1791, Harvard - Institute of Economic Research.
    33. Hurwicz, Leonid, 1979. "On allocations attainable through Nash equilibria," Journal of Economic Theory, Elsevier, vol. 21(1), pages 140-165, August.
    34. Barbera, Salvador & Jackson, Matthew O, 1995. "Strategy-Proof Exchange," Econometrica, Econometric Society, vol. 63(1), pages 51-87, January.
    35. Postlewaite, Andrew & Schmeidler, David, 1986. "Implementation in differential information economies," Journal of Economic Theory, Elsevier, vol. 39(1), pages 14-33, June.
    36. Antonio Cabrales, 1996. "Adaptive dynamics and the implementation problem with complete information," Economics Working Papers 179, Department of Economics and Business, Universitat Pompeu Fabra.
    37. Thomson, W., 1994. "Concepts of Implementation," RCER Working Papers 396, University of Rochester - Center for Economic Research (RCER).
    38. Frédéric Gaspart, 2003. "A general concept of procedural fairness for one-stage implementation," Social Choice and Welfare, Springer, vol. 21(2), pages 311-322, October.
    39. Matsushima, Hitoshi, 1988. "A new approach to the implementation problem," Journal of Economic Theory, Elsevier, vol. 45(1), pages 128-144, June.
    40. Peleg, Bezalel, 2002. "Game-theoretic analysis of voting in committees," 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 8, pages 395-423 Elsevier.
    41. Moulin, H. & Peleg, B., 1982. "Cores of effectivity functions and implementation theory," Journal of Mathematical Economics, Elsevier, vol. 10(1), pages 115-145, June.
    42. Grossman, Sanford J. & Perry, Motty, 1986. "Perfect sequential equilibrium," Journal of Economic Theory, Elsevier, vol. 39(1), pages 97-119, June.
    43. Hong, Lu, 1995. "Nash Implementation in Production Economies," Economic Theory, Springer, vol. 5(3), pages 401-17, May.
    44. Abreu Dilip & Matsushima Hitoshi, 1994. "Exact Implementation," Journal of Economic Theory, Elsevier, vol. 64(1), pages 1-19, October.
    45. Eric Maskin & John Moore, 1999. "Implementation and Renegotiation," Harvard Institute of Economic Research Working Papers 1863, Harvard - Institute of Economic Research.
    46. Groves, Theodore & Ledyard, John O, 1977. "Optimal Allocation of Public Goods: A Solution to the "Free Rider" Problem," Econometrica, Econometric Society, vol. 45(4), pages 783-809, May.
    47. Antonio Cabrales & Giovanni Ponti, 2000. "Implementation, Elimination of Weakly Dominated Strategies and Evolutionary Dynamics," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 3(2), pages 247-282, April.
    48. Vartiainen, Hannu, 2007. "Subgame perfect implementation: A full characterization," Journal of Economic Theory, Elsevier, vol. 133(1), pages 111-126, March.
    49. John Duggan, 1997. "Virtual Bayesian Implementation," Econometrica, Econometric Society, vol. 65(5), pages 1175-1200, September.
    50. Schmeidler, David, 1982. "A condition guaranteeing that the Nash allocation is Walrasian," Journal of Economic Theory, Elsevier, vol. 28(2), pages 376-378, December.
    51. Thomson, W., 1996. "Monotonic Extension on Economic Domains," RCER Working Papers 431, University of Rochester - Center for Economic Research (RCER).
    52. Yamato, Takehiko, 1992. "On nash implementation of social choice correspondences," Games and Economic Behavior, Elsevier, vol. 4(3), pages 484-492, July.
    53. Dutta, Bhaskar & Sen, Arunava, 1991. "Implementation under strong equilibrium : A complete characterization," Journal of Mathematical Economics, Elsevier, vol. 20(1), pages 49-67.
    54. Muller, Eitan & Satterthwaite, Mark A., 1977. "The equivalence of strong positive association and strategy-proofness," Journal of Economic Theory, Elsevier, vol. 14(2), pages 412-418, April.
    55. Moulin, Herve, 1994. "Social choice," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 31, pages 1091-1125 Elsevier.
    56. Tian, Guoqiang, 1989. "Implementation of the Lindahl Correspondence by a Single-Valued, Feasible, and Continuous Mechanism," Review of Economic Studies, Wiley Blackwell, vol. 56(4), pages 613-21, October.
    57. Baliga, S., 1993. "Implementation in incomplete Information Environments: The Use of Extensive Form Games," Papers 192, Cambridge - Risk, Information & Quantity Signals.
    58. Deb, Rajat, 1994. "Waiver, Effectivity and Rights as Game Forms," Economica, London School of Economics and Political Science, vol. 61(242), pages 167-78, May.
    59. Jackson Matthew O. & Palfrey Thomas R. & Srivastava Sanjay, 1994. "Undominated Nash Implementation in Bounded Mechanisms," Games and Economic Behavior, Elsevier, vol. 6(3), pages 474-501, May.
    60. Abreu, Dilip & Matsushima, Hitoshi, 1992. "Virtual Implementation in Iteratively Undominated Strategies: Complete Information," Econometrica, Econometric Society, vol. 60(5), pages 993-1008, September.
    61. Abreu, Dilip & Sen, Arunava, 1990. "Subgame perfect implementation: A necessary and almost sufficient condition," Journal of Economic Theory, Elsevier, vol. 50(2), pages 285-299, April.
    62. Dutta, Bhaskar & Sen, Arunava, 1991. "A Necessary and Sufficient Condition for Two-Person Nash Implementation," Review of Economic Studies, Wiley Blackwell, vol. 58(1), pages 121-28, January.
    63. Palfrey, Thomas R & Srivastava, Sanjay, 1987. "On Bayesian Implementable Allocations," Review of Economic Studies, Wiley Blackwell, vol. 54(2), pages 193-208, April.
    64. Eliaz, Kfir, 2002. "Fault Tolerant Implementation," Review of Economic Studies, Wiley Blackwell, vol. 69(3), pages 589-610, July.
    65. Abreu, Dilip & Matsushima, Hitoshi, 1992. "A Response [Virtual Implementation in Iteratively Undominated Strategies I: Complete Information]," Econometrica, Econometric Society, vol. 60(6), pages 1439-42, November.
    66. Matsushima Hitoshi, 1993. "Bayesian Monotonicity with Side Payments," Journal of Economic Theory, Elsevier, vol. 59(1), pages 107-121, February.
    67. Luis Corchón & Sandeep Baliga & Tomas Sjöström, 1995. "The Theory Of Implementation When The Planner Is A Player," Working Papers. Serie AD 1995-14, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    68. Williams, Steven R, 1986. "Realization and Nash Implementation: Two Aspects of Mechanism Design," Econometrica, Econometric Society, vol. 54(1), pages 139-51, January.
    69. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    70. Yamato, Takehiko, 1999. "Nash implementation and double implementation: equivalence theorems1," Journal of Mathematical Economics, Elsevier, vol. 31(2), pages 215-238, March.
    71. Moulin, Herve, 1979. "Dominance Solvable Voting Schemes," Econometrica, Econometric Society, vol. 47(6), pages 1137-51, November.
    72. Maskin, Eric, 1999. "Nash Equilibrium and Welfare Optimality," Review of Economic Studies, Wiley Blackwell, vol. 66(1), pages 23-38, January.
    73. Danilov, Vladimir, 1992. "Implementation via Nash Equilibria," Econometrica, Econometric Society, vol. 60(1), pages 43-56, January.
    74. 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.
    75. Gaertner, Wulf & Pattanaik, Prasanta K & Suzumura, Kotaro, 1992. "Individual Rights Revisited," Economica, London School of Economics and Political Science, vol. 59(234), pages 161-77, May.
    76. Palfrey, Thomas R & Srivastava, Sanjay, 1989. "Implementation with Incomplete Information in Exchange Economies," Econometrica, Econometric Society, vol. 57(1), pages 115-34, January.
    77. Jackson, Matthew O, 1991. "Bayesian Implementation," Econometrica, Econometric Society, vol. 59(2), pages 461-77, March.
    78. JoseHerrero, Maria & Srivastava, Sanjay, 1992. "Implementation via backward induction," Journal of Economic Theory, Elsevier, vol. 56(1), pages 70-88, February.
    79. Bergin, James & Sen, Arunava, 1998. "Extensive Form Implementation in Incomplete Information Environments," Journal of Economic Theory, Elsevier, vol. 80(2), pages 222-256, June.
    80. Bhaskar Dutta & Arunava Sen & Rajiv Vohra, 1994. "Nash implementation through elementary mechanisms in economic environments," Review of Economic Design, Springer, vol. 1(1), pages 173-203, December.
    81. Suh, Sang-Chul, 1996. "Implementation with coalition formation: A complete characterization," Journal of Mathematical Economics, Elsevier, vol. 26(4), pages 409-428.
    82. Jordan, J. S., 1986. "Instability in the implementation of Walrasian allocations," Journal of Economic Theory, Elsevier, vol. 39(2), pages 301-328, August.
    83. Reichelstein, Stefan & Reiter, Stanley, 1988. "Game Forms with Minimal Message Spaces," Econometrica, Econometric Society, vol. 56(3), pages 661-92, May.
    84. Dutta Bhaskar & Sen Arunava, 1994. "Bayesian Implementation: The Necessity of Infinite Mechanisms," Journal of Economic Theory, Elsevier, vol. 64(1), pages 130-141, October.
    85. Pattanaik, Prasanta K & Suzumura, Kotaro, 1994. "Rights, Welfarism, and Social Choice," American Economic Review, American Economic Association, vol. 84(2), pages 435-39, May.
    86. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    Full references (including those not matched with items on IDEAS)

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    When requesting a correction, please mention this item's handle: RePEc:eee:socchp:1-05. 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: (Zhang, Lei)

    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 references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link 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 profile, as there may be some citations waiting for confirmation.

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

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.