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

Implementation, Elimination of Weakly Dominated Strategies and Evolotionary Dynamics

Contents:

Author Info

  • Antonio Cabrales
  • Giovanni Ponti

Abstract

This paper is concerned with the realism of mechanisms that implement social choice functions in the traditional sense. Will agents actually play the equilibrium assumed by the analysis? As an example, we study convergence and stability prop-erties of Sjostrom's (1994) mechanism, on the assumption that boundedly rational players find their way to equilibrium using monotonic learning dynamics. This mechanism implements most social choice functions in economic environments using as a solution concept the iterated elimination of weakly dominated strategies (only one round of deletion of weakly dominated strategies is needed). There are, how-ever, many sets of Nash equilibria whose payoffs may be very different from those desired by the social choice function. We show that many equilibria in all the sets of equilibria we have described are the limit points of trajectories that have completely mixed initial conditions. The initial conditions that lead to these equilibria need not be very close to the limiting point. Furthermore, even if the dynamics converge to the "right" set of equilibria, it still can converge to quite a poor outcome in welfare terms.

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: ftp://ftp.repec.org/RePEc/els/esrcls/weak.pdf
Download Restriction: no

Bibliographic Info

Paper provided by ESRC Centre on Economics Learning and Social Evolution in its series ELSE working papers with number 057.

as in new window
Length:
Date of creation:
Date of revision:
Handle: RePEc:els:esrcls:057

Contact details of provider:
Postal: Gower Street, London WC1E 6BT
Email:
Web page: http://else.econ.ucl.ac.uk/
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. repec:att:wimass:9325 is not listed on IDEAS
  2. Cressman, R. & Schlag, K. H., 1998. "The Dynamic (In)Stability of Backwards Induction," Journal of Economic Theory, Elsevier, vol. 83(2), pages 260-285, December.
  3. Mookherjee, Dilip & Sopher, Barry, 1997. "Learning and Decision Costs in Experimental Constant Sum Games," Games and Economic Behavior, Elsevier, vol. 19(1), pages 97-132, April.
  4. Chen, Hsiao-Chi & Friedman, James W. & Thisse, Jacques-Francois, 1997. "Boundedly Rational Nash Equilibrium: A Probabilistic Choice Approach," Games and Economic Behavior, Elsevier, vol. 18(1), pages 32-54, January.
  5. Karl H. Schlag, . "Why Imitate, and if so, How? A Bounded Rational Approach to Multi- Armed Bandits," ELSE working papers 028, ESRC Centre on Economics Learning and Social Evolution.
  6. Leslie McFarland-Marx & Jeroen M. Swinkels, 1993. "Order Independence for Iterated Weak Dominance," Discussion Papers 1040, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  7. Cooper, R. & DeJong, D.W. & Ross, T.W., 1992. "Cooperation without Reputation: Experimental Evidence from Prisoner's Dilemma Games," Papers 36, Boston University - Industry Studies Programme.
  8. Giovanni Ponti, 1996. "Cycles of Learning in the Centipede Game," Discussion Papers 96-22 ISSN 1350-6722, University College London, Department of Economics.
  9. Matthew O. Jackson, 1990. "Undominated Nash Implementation in Bounded Mechanisms," Discussion Papers 966, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  10. Jordan, J. S., 1986. "Instability in the implementation of Walrasian allocations," Journal of Economic Theory, Elsevier, vol. 39(2), pages 301-328, August.
  11. 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.
  12. Drew Fudenberg & Eddie Dekel, 1987. "Rational Behavior with Payoff Uncertainty," Working papers 471, Massachusetts Institute of Technology (MIT), Department of Economics.
  13. Abreu Dilip & Matsushima Hitoshi, 1994. "Exact Implementation," Journal of Economic Theory, Elsevier, vol. 64(1), pages 1-19, October.
  14. A. Roth & I. Er’ev, 2010. "Learning in Extensive Form Games: Experimental Data and Simple Dynamic Models in the Intermediate Run," Levine's Working Paper Archive 387, David K. Levine.
  15. Antonio Cabrales, . "Adaptive Dynamics and the Implementation Problem with Complete Information," ELSE working papers 009, ESRC Centre on Economics Learning and Social Evolution.
  16. Dunia López-Pintado & Giovanni Ponti, 2003. "Solomon'S Dilemma: An Experimental Study On Dynamic Implementation," Working Papers. Serie AD 2003-11, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
  17. Jorgen W. Weibull, 1997. "Evolutionary Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262731215, December.
  18. Borgers Tilman, 1994. "Weak Dominance and Approximate Common Knowledge," Journal of Economic Theory, Elsevier, vol. 64(1), pages 265-276, October.
  19. Hofbauer, Josef & Weibull, Jîrgen W., 1995. "Evolutionary selection against dominated strategies," CEPREMAP Working Papers (Couverture Orange) 9506, CEPREMAP.
  20. repec:fth:louvco:9644 is not listed on IDEAS
  21. Charness, Gary B & Cabrales, Antonio & Corchon, Luis C, 2001. "An Experiment on Nash Implementation," University of California at Santa Barbara, Economics Working Paper Series qt8275577k, Department of Economics, UC Santa Barbara.
  22. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
  23. Walker, Mark, 1984. "A simple auctioneerless mechanism with Walrasian properties," Journal of Economic Theory, Elsevier, vol. 32(1), pages 111-127, February.
  24. T. Borgers & R. Sarin, 2010. "Learning Through Reinforcement and Replicator Dynamics," Levine's Working Paper Archive 380, David K. Levine.
  25. Schlag, Karl H., 1994. "Why Imitate, and if so, How? Exploring a Model of Social Evolution," Discussion Paper Serie B 296, University of Bonn, Germany.
  26. Samuelson, L. & Zhang, J., 1990. "Evolutionary Stability In Symmetric Games," Working papers 90-24, Wisconsin Madison - Social Systems.
  27. Fudenberg Drew & Kreps David M., 1993. "Learning Mixed Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 320-367, July.
  28. 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.
  29. Guth, Werner & Schmittberger, Rolf & Schwarze, Bernd, 1982. "An experimental analysis of ultimatum bargaining," Journal of Economic Behavior & Organization, Elsevier, vol. 3(4), pages 367-388, December.
  30. I. Gilboa & A. Matsui, 2010. "Social Stability and Equilibrium," Levine's Working Paper Archive 534, David K. Levine.
  31. De Trenqualye, Pierre, 1988. "Stability of the Groves and Ledyard mechanism," Journal of Economic Theory, Elsevier, vol. 46(1), pages 164-171, October.
  32. Tang, Fang-Fang, 1996. "Anticipatory Learning in Two-Person Games: An Experimental Study, Part II. Learning," Discussion Paper Serie B 363, University of Bonn, Germany.
  33. Sjostrom Tomas, 1994. "Implementation in Undominated Nash Equilibria without Integer Games," Games and Economic Behavior, Elsevier, vol. 6(3), pages 502-511, May.
  34. Samuelson, Larry & Zhang, Jianbo, 1992. "Evolutionary stability in asymmetric games," Journal of Economic Theory, Elsevier, vol. 57(2), pages 363-391, August.
  35. Matsui, Akihiko, 1992. "Best response dynamics and socially stable strategies," Journal of Economic Theory, Elsevier, vol. 57(2), pages 343-362, August.
  36. Vega-Redondo, Fernando, 1989. "Implementation of Lindahl equilibrium: an integration of the static and dynamic approaches," Mathematical Social Sciences, Elsevier, vol. 18(3), pages 211-228, December.
  37. Nachbar, J H, 1990. ""Evolutionary" Selection Dynamics in Games: Convergence and Limit Properties," International Journal of Game Theory, Springer, vol. 19(1), pages 59-89.
  38. Binmore, K. & Samuelson, L., 1997. "Evolutionary Drift and Equilibrium Selection," Working papers 9729r, Wisconsin Madison - Social Systems.
  39. Walker, Mark, 1981. "A Simple Incentive Compatible Scheme for Attaining Lindahl Allocations," Econometrica, Econometric Society, vol. 49(1), pages 65-71, January.
  40. de Trenqualye, Pierre, 1989. "Stable implementation of Lindahl allocations," Economics Letters, Elsevier, vol. 29(4), pages 291-294.
  41. Cressman, R., 1996. "Evolutionary Stability in the Finitely Repeated Prisoner 's Dilemma Game," Journal of Economic Theory, Elsevier, vol. 68(1), pages 234-248, January.
  42. repec:fth:calaec:16-97 is not listed on IDEAS
  43. Gale, John & Binmore, Kenneth G. & Samuelson, Larry, 1995. "Learning to be imperfect: The ultimatum game," Games and Economic Behavior, Elsevier, vol. 8(1), pages 56-90.
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:
  1. Maskin, Eric & Sjostrom, Tomas, 2001. "Implementation Theory," Working Papers 5-01-1, Pennsylvania State University, Department of Economics.
  2. David K Levine & Aldo Rustichini, 2000. "Introduction: The Dynamic Games Special Issue," Levine's Working Paper Archive 2127, David K. Levine.
  3. Roberto Serrano, 2003. "The Theory of Implementation of Social Choice Rules," Economics Working Papers 0033, Institute for Advanced Study, School of Social Science.
  4. Cason, Timothy N. & Saijo, Tatsuyoshi & Sjostrom, Tomas & Yamato, Takehiho, 2003. "Secure Implementation Experiments: Do Strategy-Proof Mechanisms Really Work?," Working Papers 1165, California Institute of Technology, Division of the Humanities and Social Sciences.
  5. Galbiati, Marco, 2008. "Fair divisions as attracting Nash equilibria of simple games," Economics Letters, Elsevier, vol. 100(1), pages 72-75, July.
  6. Giovanni Ponti & Anita Gantner & Dunia López-Pintado & Robert Montgomery, 2003. "Solomon's Dilemma: An experimental study on dynamic implementation," Review of Economic Design, Springer, vol. 8(2), pages 217-239, October.
  7. David K. Levine & Aldo Rustichini, 2000. "Introduction," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 3(2), pages 213-215, April.
  8. Antonio Cabrales & Roberto Serrano, 2007. "Implementation in Adaptive Better-Response Dynamics," Economics Working Papers we075731, Universidad Carlos III, Departamento de Economía.
  9. Norovsambuu Tumennasan, 2011. "To Err is Human: Implementation in Quantal Response Equilibria," Economics Working Papers 2011-11, School of Economics and Management, University of Aarhus.
  10. Jordi Brandts & Antonio Cabrales & Gary Charness, 2007. "Forward induction and entry deterrence: an experiment," Economic Theory, Springer, vol. 33(1), pages 183-209, October.
  11. Sandholm,W.H., 2001. "Negative externalities and evolutionary implementation," Working papers 15, Wisconsin Madison - Social Systems.
  12. Sandholm,W.H., 1999. "Evolutionary implementation and congestion pricing," Working papers 38, Wisconsin Madison - Social Systems.

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:els:esrcls:057. 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: (s. malkani) The email address of this maintainer does not seem to be valid anymore. Please ask s. malkani to update the entry or send us the correct address.

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.