IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Log in (now much improved!) to save this paper

Implementation Theory

  • Maskin, Eric

    (Princeton U)

  • Sjostrom, Tomas

    (Pennsylvania State U)

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.

(This abstract was borrowed from another version of this item.)

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://scholar.harvard.edu/maskin/files/implementation_theory_published_version.pdf
Download Restriction: no

Paper provided by Pennsylvania State University, Department of Economics in its series Working Papers with number 5-01-1.

as
in new window

Length:
Date of creation: May 2001
Date of revision:
Handle: RePEc:ecl:peneco:5-01-1
Contact details of provider: Postal:
608 Kern Graduate Building, University Park, PA 16802-3306

Phone: (814)865-1456
Fax: (814)863-4775
Web page: http://econ.la.psu.edu/info/working_papers.html

More information through EDIRC

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. Baliga, S. & Corchon, L.C. & Sjostrom, T., 1995. "The Theory of Implemetation when the Planner is a PLayer," Cambridge Working Papers in Economics 9512, Faculty of Economics, University of Cambridge.
  2. d'Aspremont, Claude & Gerard-Varet, Louis-Andre, 1979. "Incentives and incomplete information," Journal of Public Economics, Elsevier, vol. 11(1), pages 25-45, February.
  3. Postlewaite, Andrew & Schmeidler, David, 1986. "Implementation in differential information economies," Journal of Economic Theory, Elsevier, vol. 39(1), pages 14-33, June.
  4. 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.
  5. Theodore Groves & John Ledyard, 1976. "Optimal Allocation of Public Goods: A Solution to the 'Free Rider Problem'," Discussion Papers 144, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  6. Abreu, Dilip & Matsushima, Hitoshi, 1992. "Virtual Implementation in Iteratively Undominated Strategies: Complete Information," Econometrica, Econometric Society, vol. 60(5), pages 993-1008, September.
  7. Farrell Joseph, 1993. "Meaning and Credibility in Cheap-Talk Games," Games and Economic Behavior, Elsevier, vol. 5(4), pages 514-531, October.
  8. Yamato, Takehiko, 1992. "On nash implementation of social choice correspondences," Games and Economic Behavior, Elsevier, vol. 4(3), pages 484-492, July.
  9. 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.
  10. Pattanaik, Prasanta K & Suzumura, Kotaro, 1994. "Rights, Welfarism, and Social Choice," American Economic Review, American Economic Association, vol. 84(2), pages 435-39, May.
  11. Bhaskar Dutta & Arunava Sen, 1991. "A Necessary and Sufficient Condition for Two-Person Nash Implementation," Review of Economic Studies, Oxford University Press, vol. 58(1), pages 121-128.
  12. Matthew, Jackson O. & Palfrey, Thomas R. & Srivastava, Sanjay., 1990. "Undominated Nash Implementation in Bounded Mechanism," Working Papers 754, California Institute of Technology, Division of the Humanities and Social Sciences.
  13. Hurwicz, Leonid, 1979. "On allocations attainable through Nash equilibria," Journal of Economic Theory, Elsevier, vol. 21(1), pages 140-165, August.
  14. Tomas Sjostrom, 1997. "Undominated Nash Implementaion with Collusion and Renegotiation," Harvard Institute of Economic Research Working Papers 1791, Harvard - Institute of Economic Research.
  15. Vartiainen, Hannu, 2007. "Subgame perfect implementation: A full characterization," Journal of Economic Theory, Elsevier, vol. 133(1), pages 111-126, March.
  16. JoseHerrero, Maria & Srivastava, Sanjay, 1992. "Implementation via backward induction," Journal of Economic Theory, Elsevier, vol. 56(1), pages 70-88, February.
  17. Moulin, H. & Peleg, B., 1982. "Cores of effectivity functions and implementation theory," Journal of Mathematical Economics, Elsevier, vol. 10(1), pages 115-145, June.
  18. Sandeep Baliga & Sandro Brusco, 2000. "Collusion, renegotiation and implementation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 17(1), pages 69-83.
  19. Antonio Cabrales & Giovanni Ponti, . "Implementation, Elimination of Weakly Dominated Strategies and Evolotionary Dynamics," ELSE working papers 057, ESRC Centre on Economics Learning and Social Evolution.
  20. Moulin, Herve, 1979. "Dominance Solvable Voting Schemes," Econometrica, Econometric Society, vol. 47(6), pages 1137-51, November.
  21. Salvador Barbera & Matthew O. Jackson, 1993. "Strategy-Proof Exchange," Discussion Papers 1021, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  22. Jackson, Matthew O. & Palfrey, Thomas R., 2001. "Voluntary Implementation," Journal of Economic Theory, Elsevier, vol. 98(1), pages 1-25, May.
  23. Naoki Yoshihara, 2000. "A Characterization of Natural and Double Implementation in Production Economics," Discussion Paper Series a387, Institute of Economic Research, Hitotsubashi University.
  24. Eric Maskin & Jean Tirole, 1999. "Unforeseen Contingencies and Incomplete Contracts," Review of Economic Studies, Oxford University Press, vol. 66(1), pages 83-114.
  25. Saijo, Tatsuyoshi, 1987. "On constant maskin monotonic social choice functions," Journal of Economic Theory, Elsevier, vol. 42(2), pages 382-386, August.
  26. Schmeidler, David, 1982. "A condition guaranteeing that the Nash allocation is Walrasian," Journal of Economic Theory, Elsevier, vol. 28(2), pages 376-378, December.
  27. Moore, John & Repullo, Rafael, 1990. "Nash Implementation: A Full Characterization," Econometrica, Econometric Society, vol. 58(5), pages 1083-99, September.
  28. Bergin, James & Sen, Arunava, 1998. "Extensive Form Implementation in Incomplete Information Environments," Journal of Economic Theory, Elsevier, vol. 80(2), pages 222-256, June.
  29. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
  30. Eric Maskin & John Moore, 1998. "Implementation and renegotiation," LSE Research Online Documents on Economics 19350, London School of Economics and Political Science, LSE Library.
  31. Danilov, Vladimir, 1992. "Implementation via Nash Equilibria," Econometrica, Econometric Society, vol. 60(1), pages 43-56, January.
  32. 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.
  33. Glazer, Jacob & Rosenthal, Robert W, 1992. "A Note on Abreu-Matsushima Mechanisms," Econometrica, Econometric Society, vol. 60(6), pages 1435-38, November.
  34. William Thomson, 1999. "Monotonic extensions on economic domains," Review of Economic Design, Springer;Society for Economic Design, vol. 4(1), pages 13-33.
  35. Eliaz, K., 1999. "Fault Tolerant Implementation," Papers 21-99, Tel Aviv.
  36. Brusco, Sandro, 1995. "Perfect Bayesian Implementation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 5(3), pages 419-44, May.
  37. Peleg,Bezalel, 2008. "Game Theoretic Analysis of Voting in Committees," Cambridge Books, Cambridge University Press, number 9780521074650, November.
  38. 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.
  39. William Thomson, 1996. "Concepts Of Implementation," The Japanese Economic Review, Japanese Economic Association, vol. 47(2), pages 133-143, 06.
  40. Antonio Cabrales, . "Adaptive Dynamics and the Implementation Problem with Complete Information," ELSE working papers 009, ESRC Centre on Economics Learning and Social Evolution.
  41. 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.
  42. Bezalel Peleg, 1997. "Effectivity functions, game forms, games, and rights," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 15(1), pages 67-80.
  43. Eric Maskin, 1999. "Nash Equilibrium and Welfare Optimality," Review of Economic Studies, Oxford University Press, vol. 66(1), pages 23-38.
  44. Matthew O. Jackson, 1992. "Implementation in Undominated Strategies: A Look at Bounded Mechanisms," Review of Economic Studies, Oxford University Press, vol. 59(4), pages 757-775.
  45. Hong, Lu, 1995. "Nash Implementation in Production Economies," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 5(3), pages 401-17, May.
  46. Baliga, S., 1993. "Implementation in incomplete Information Environments: The Use of Extensive Form Games," Papers 192, Cambridge - Risk, Information & Quantity Signals.
  47. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
  48. L. Hurwicz, 1979. "Outcome Functions Yielding Walrasian and Lindahl Allocations at Nash Equilibrium Points," Review of Economic Studies, Oxford University Press, vol. 46(2), pages 217-225.
  49. Schmeidler, David, 1980. "Walrasian Analysis via Strategic Outcome Functions," Econometrica, Econometric Society, vol. 48(7), pages 1585-93, November.
  50. Baliga, Sandeep & Sjostrom, Tomas, 1999. "Interactive Implementation," Games and Economic Behavior, Elsevier, vol. 27(1), pages 38-63, April.
  51. Grossman, Sanford J. & Perry, Motty, 1986. "Perfect sequential equilibrium," Journal of Economic Theory, Elsevier, vol. 39(1), pages 97-119, June.
  52. 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.
  53. Theodore Groves & Martin Loeb, 1974. "Incentives and Public Inputs," Discussion Papers 29, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  54. Palfrey, Thomas R & Srivastava, Sanjay, 1989. "Implementation with Incomplete Information in Exchange Economies," Econometrica, Econometric Society, vol. 57(1), pages 115-34, January.
  55. Guoqiang Tian, 1989. "Implementation of the Lindahl Correspondence by a Single-Valued, Feasible, and Continuous Mechanism," Review of Economic Studies, Oxford University Press, vol. 56(4), pages 613-621.
  56. Jackson, Matthew O, 1991. "Bayesian Implementation," Econometrica, Econometric Society, vol. 59(2), pages 461-77, March.
  57. Dilip Mookherjee & Stefan Reichelstein, 1990. "Implementation via Augmented Revelation Mechanisms," Review of Economic Studies, Oxford University Press, vol. 57(3), pages 453-475.
  58. Williams, Steven R, 1986. "Realization and Nash Implementation: Two Aspects of Mechanism Design," Econometrica, Econometric Society, vol. 54(1), pages 139-51, January.
  59. Thomas R. Palfrey & Sanjay Srivastava, 1987. "On Bayesian Implementable Allocations," Review of Economic Studies, Oxford University Press, vol. 54(2), pages 193-208.
  60. 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.
  61. 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.
  62. John Duggan, 1997. "Virtual Bayesian Implementation," Econometrica, Econometric Society, vol. 65(5), pages 1175-1200, September.
  63. 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.
  64. Abreu Dilip & Matsushima Hitoshi, 1994. "Exact Implementation," Journal of Economic Theory, Elsevier, vol. 64(1), pages 1-19, October.
  65. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
  66. repec:fth:calaec:6-98 is not listed on IDEAS
  67. Dutta, Bhaskar & Sen, Arunava, 1991. "Implementation under strong equilibrium : A complete characterization," Journal of Mathematical Economics, Elsevier, vol. 20(1), pages 49-67.
  68. 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.
  69. Mark A. Satterthwaite & Hugo Sonnenschein, 1981. "Strategy-Proof Allocation Mechanisms at Differentiable Points," Review of Economic Studies, Oxford University Press, vol. 48(4), pages 587-597.
  70. Bhaskar Dutta & Arunava Sen & Rajiv Vohra, 1994. "Nash implementation through elementary mechanisms in economic environments," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 173-203, December.
  71. 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.
  72. Jordan, J. S., 1986. "Instability in the implementation of Walrasian allocations," Journal of Economic Theory, Elsevier, vol. 39(2), pages 301-328, August.
  73. 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.
  74. 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.
  75. Yamato, Takehiko, 1999. "Nash implementation and double implementation: equivalence theorems1," Journal of Mathematical Economics, Elsevier, vol. 31(2), pages 215-238, March.
  76. Crawford, Vincent P, 1979. "A Procedure for Generating Pareto-Efficient Egalitarian-Equivalent Allocations," Econometrica, Econometric Society, vol. 47(1), pages 49-60, January.
  77. Matsushima Hitoshi, 1993. "Bayesian Monotonicity with Side Payments," Journal of Economic Theory, Elsevier, vol. 59(1), pages 107-121, February.
  78. Reichelstein, Stefan & Reiter, Stanley, 1988. "Game Forms with Minimal Message Spaces," Econometrica, Econometric Society, vol. 56(3), pages 661-92, May.
  79. Matsushima, Hitoshi, 1988. "A new approach to the implementation problem," Journal of Economic Theory, Elsevier, vol. 45(1), pages 128-144, June.
  80. Dutta Bhaskar & Sen Arunava, 1994. "Bayesian Implementation: The Necessity of Infinite Mechanisms," Journal of Economic Theory, Elsevier, vol. 64(1), pages 130-141, October.
  81. Serrano, Roberto & Vohra, Rajiv, 2001. "Some Limitations of Virtual Bayesian Implementation," Econometrica, Econometric Society, vol. 69(3), pages 785-92, May.
  82. De Trenqualye, Pierre, 1988. "Stability of the Groves and Ledyard mechanism," Journal of Economic Theory, Elsevier, vol. 46(1), pages 164-171, October.
  83. 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.
  84. Suh, Sang-Chul, 1996. "Implementation with coalition formation: A complete characterization," Journal of Mathematical Economics, Elsevier, vol. 26(4), pages 409-428.
  85. 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.
  86. Frédéric Gaspart, 2003. "A general concept of procedural fairness for one-stage implementation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(2), pages 311-322, October.
  87. repec:dau:papers:123456789/13220 is not listed on IDEAS
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:ecl:peneco:5-01-1. 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: ()

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.