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

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://econ.la.psu.edu/papers/jts%285-01-1%29.pdf
Our checks indicate that this address may not be valid because: 404 Not Found. If this is indeed the case, please notify ()


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. Maskin, Eric & Tirole, Jean, 1999. "Unforeseen Contingencies and Incomplete Contracts," Review of Economic Studies, Wiley Blackwell, vol. 66(1), pages 83-114, January.
  2. Jackson, Matthew O. & Palfrey, Thomas R., 1999. "Voluntary Implementation," Working Papers 1077, California Institute of Technology, Division of the Humanities and Social Sciences.
  3. Moore, John & Repullo, Rafael, 1990. "Nash Implementation: A Full Characterization," Econometrica, Econometric Society, vol. 58(5), pages 1083-99, September.
  4. Yamato, Takehiko, 1999. "Nash implementation and double implementation: equivalence theorems1," Journal of Mathematical Economics, Elsevier, vol. 31(2), pages 215-238, March.
  5. Baliga, Sandeep & Sjostrom, Tomas, 1999. "Interactive Implementation," Games and Economic Behavior, Elsevier, vol. 27(1), pages 38-63, April.
  6. Dutta Bhaskar & Sen Arunava, 1994. "Bayesian Implementation: The Necessity of Infinite Mechanisms," Journal of Economic Theory, Elsevier, vol. 64(1), pages 130-141, October.
  7. Jordan, J. S., 1986. "Instability in the implementation of Walrasian allocations," Journal of Economic Theory, Elsevier, vol. 39(2), pages 301-328, August.
  8. Glazer, Jacob & Rosenthal, Robert W, 1992. "A Note on Abreu-Matsushima Mechanisms," Econometrica, Econometric Society, vol. 60(6), pages 1435-38, November.
  9. Farrell Joseph, 1993. "Meaning and Credibility in Cheap-Talk Games," Games and Economic Behavior, Elsevier, vol. 5(4), pages 514-531, October.
  10. John Duggan, 1997. "Virtual Bayesian Implementation," Econometrica, Econometric Society, vol. 65(5), pages 1175-1200, September.
  11. Danilov, Vladimir, 1992. "Implementation via Nash Equilibria," Econometrica, Econometric Society, vol. 60(1), pages 43-56, January.
  12. Hong, Lu, 1995. "Nash Implementation in Production Economies," Economic Theory, Springer, vol. 5(3), pages 401-17, May.
  13. 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.
  14. Antonio Cabrales, . "Adaptive Dynamics and the Implementation Problem with Complete Information," ELSE working papers 009, ESRC Centre on Economics Learning and Social Evolution.
  15. 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.
  16. Eric Maskin & John Moore, 1999. "Implementation and Renegotiation," Harvard Institute of Economic Research Working Papers 1863, Harvard - Institute of Economic Research.
  17. Palfrey, Thomas R & Srivastava, Sanjay, 1989. "Implementation with Incomplete Information in Exchange Economies," Econometrica, Econometric Society, vol. 57(1), pages 115-34, January.
  18. Abreu, Dilip & Matsushima, Hitoshi, 1992. "Virtual Implementation in Iteratively Undominated Strategies: Complete Information," Econometrica, Econometric Society, vol. 60(5), pages 993-1008, September.
  19. Sjostrom, Tomas, 1999. "Undominated Nash Implementation with Collusion and Renegotiation," Games and Economic Behavior, Elsevier, vol. 26(2), pages 337-352, January.
  20. 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.
  21. 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.
  22. 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).
  23. 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.
  24. Serrano, Roberto & Vohra, Rajiv, 2001. "Some Limitations of Virtual Bayesian Implementation," Econometrica, Econometric Society, vol. 69(3), pages 785-92, May.
  25. Barbera, Salvador & Jackson, Matthew O, 1995. "Strategy-Proof Exchange," Econometrica, Econometric Society, vol. 63(1), pages 51-87, January.
  26. Groves, Theodore & Loeb, Martin, 1975. "Incentives and public inputs," Journal of Public Economics, Elsevier, vol. 4(3), pages 211-226, August.
  27. Matthew O. Jackson, 1990. "Undominated Nash Implementation in Bounded Mechanisms," Discussion Papers 966, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  28. 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).
  29. Moulin, H. & Peleg, B., 1982. "Cores of effectivity functions and implementation theory," Journal of Mathematical Economics, Elsevier, vol. 10(1), pages 115-145, June.
  30. Abreu Dilip & Matsushima Hitoshi, 1994. "Exact Implementation," Journal of Economic Theory, Elsevier, vol. 64(1), pages 1-19, October.
  31. Eliaz, Kfir, 2002. "Fault Tolerant Implementation," Review of Economic Studies, Wiley Blackwell, vol. 69(3), pages 589-610, July.
  32. 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.
  33. 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.
  34. Wulf Gaerther & Prasanta K. Pattanaik & Kotaro Suzumura, 1991. "Individual Rights Revisited," Discussion Paper Series a238, Institute of Economic Research, Hitotsubashi University.
    • 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.
  35. Pattanaik, Prasanta K & Suzumura, Kotaro, 1994. "Rights, Welfarism, and Social Choice," American Economic Review, American Economic Association, vol. 84(2), pages 435-39, May.
  36. 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.
  37. Thomson, W., 1996. "Monotonic Extension on Economic Domains," RCER Working Papers 431, University of Rochester - Center for Economic Research (RCER).
  38. 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.
  39. Moulin, Herve, 1979. "Dominance Solvable Voting Schemes," Econometrica, Econometric Society, vol. 47(6), pages 1137-51, November.
  40. Yamato, Takehiko, 1992. "On nash implementation of social choice correspondences," Games and Economic Behavior, Elsevier, vol. 4(3), pages 484-492, July.
  41. Thomson, W., 1994. "Concepts of Implementation," RCER Working Papers 396, University of Rochester - Center for Economic Research (RCER).
  42. Brusco, Sandro, 1995. "Perfect Bayesian Implementation," Economic Theory, Springer, vol. 5(3), pages 419-44, May.
  43. Williams, Steven R, 1986. "Realization and Nash Implementation: Two Aspects of Mechanism Design," Econometrica, Econometric Society, vol. 54(1), pages 139-51, January.
  44. Maskin, Eric, 1999. "Nash Equilibrium and Welfare Optimality," Review of Economic Studies, Wiley Blackwell, vol. 66(1), pages 23-38, January.
  45. repec:fth:calaec:6-98 is not listed on IDEAS
  46. 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.
  47. 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.
  48. Matthew 0. Jackson, 1989. "Implementation in Undominated Strategies - A Look at Bounded Mechanisms," Discussion Papers 833, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  49. Saijo, Tatsuyoshi, 1987. "On constant maskin monotonic social choice functions," Journal of Economic Theory, Elsevier, vol. 42(2), pages 382-386, August.
  50. Reichelstein, Stefan & Reiter, Stanley, 1988. "Game Forms with Minimal Message Spaces," Econometrica, Econometric Society, vol. 56(3), pages 661-92, May.
  51. Jackson, Matthew O, 1991. "Bayesian Implementation," Econometrica, Econometric Society, vol. 59(2), pages 461-77, March.
  52. Suh, Sang-Chul, 1996. "Implementation with coalition formation: A complete characterization," Journal of Mathematical Economics, Elsevier, vol. 26(4), pages 409-428.
  53. Sandeep Baliga & Sandro Brusco, 2000. "Collusion, renegotiation and implementation," Social Choice and Welfare, Springer, vol. 17(1), pages 69-83.
  54. 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.
  55. 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.
  56. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
  57. 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.
  58. Vartiainen, Hannu, 2007. "Subgame perfect implementation: A full characterization," Journal of Economic Theory, Elsevier, vol. 133(1), pages 111-126, March.
  59. 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.
  60. Bezalel Peleg, 1997. "Effectivity functions, game forms, games, and rights," Social Choice and Welfare, Springer, vol. 15(1), pages 67-80.
  61. Postlewaite, Andrew & Schmeidler, David, 1986. "Implementation in differential information economies," Journal of Economic Theory, Elsevier, vol. 39(1), pages 14-33, June.
  62. 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.
  63. 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.
  64. 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.
  65. Mookherjee, Dilip & Reichelstein, Stefan, 1990. "Implementation via Augmented Revelation Mechanisms," Review of Economic Studies, Wiley Blackwell, vol. 57(3), pages 453-75, July.
  66. Naoki Yoshihara, 2000. "A characterization of natural and double implementation in production economies," Social Choice and Welfare, Springer, vol. 17(4), pages 571-599.
  67. Grossman, Sanford J. & Perry, Motty, 1986. "Perfect sequential equilibrium," Journal of Economic Theory, Elsevier, vol. 39(1), pages 97-119, June.
  68. 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.
  69. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
  70. 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.
  71. Palfrey, Thomas R & Srivastava, Sanjay, 1987. "On Bayesian Implementable Allocations," Review of Economic Studies, Wiley Blackwell, vol. 54(2), pages 193-208, April.
  72. Hurwicz, Leonid, 1979. "On allocations attainable through Nash equilibria," Journal of Economic Theory, Elsevier, vol. 21(1), pages 140-165, August.
  73. 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.
  74. Schmeidler, David, 1982. "A condition guaranteeing that the Nash allocation is Walrasian," Journal of Economic Theory, Elsevier, vol. 28(2), pages 376-378, December.
  75. De Trenqualye, Pierre, 1988. "Stability of the Groves and Ledyard mechanism," Journal of Economic Theory, Elsevier, vol. 46(1), pages 164-171, October.
  76. Bergin, James & Sen, Arunava, 1998. "Extensive Form Implementation in Incomplete Information Environments," Journal of Economic Theory, Elsevier, vol. 80(2), pages 222-256, June.
  77. Crawford, Vincent P, 1979. "A Procedure for Generating Pareto-Efficient Egalitarian-Equivalent Allocations," Econometrica, Econometric Society, vol. 47(1), pages 49-60, January.
  78. Baliga, S., 1993. "Implementation in incomplete Information Environments: The Use of Extensive Form Games," Papers 192, Cambridge - Risk, Information & Quantity Signals.
  79. JoseHerrero, Maria & Srivastava, Sanjay, 1992. "Implementation via backward induction," Journal of Economic Theory, Elsevier, vol. 56(1), pages 70-88, February.
  80. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
  81. 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.
  82. Schmeidler, David, 1980. "Walrasian Analysis via Strategic Outcome Functions," Econometrica, Econometric Society, vol. 48(7), pages 1585-93, November.
  83. Dutta, Bhaskar & Sen, Arunava, 1991. "Implementation under strong equilibrium : A complete characterization," Journal of Mathematical Economics, Elsevier, vol. 20(1), pages 49-67.
  84. Matsushima, Hitoshi, 1988. "A new approach to the implementation problem," Journal of Economic Theory, Elsevier, vol. 45(1), pages 128-144, June.
  85. 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.
  86. Matsushima Hitoshi, 1993. "Bayesian Monotonicity with Side Payments," Journal of Economic Theory, Elsevier, vol. 59(1), pages 107-121, February.
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.