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