Advanced Search
MyIDEAS: Login to save this paper or follow this series

Implementation Theory

Contents:

Author Info

  • Maskin, Eric

    (Princeton U)

  • Sjostrom, Tomas

    (Pennsylvania State U)

Abstract

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.)

Download Info

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

Bibliographic Info

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

Related research

Keywords:

Other versions of this item:

Find related papers by JEL classification:

References

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

Cited by:
This item has more than 25 citations. To prevent cluttering this page, these citations are listed on a separate page.

Lists

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

Statistics

Access and download statistics

Corrections

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.