IDEAS home Printed from https://ideas.repec.org/p/els/esrcls/057.html
   My bibliography  Save this paper

Implementation, Elimination of Weakly Dominated Strategies and Evolotionary Dynamics

Author

Listed:
  • 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.

Suggested Citation

  • Antonio Cabrales & Giovanni Ponti, "undated". "Implementation, Elimination of Weakly Dominated Strategies and Evolotionary Dynamics," ELSE working papers 057, ESRC Centre on Economics Learning and Social Evolution.
  • Handle: RePEc:els:esrcls:057
    as

    Download full text from publisher

    File URL: ftp://ftp.repec.org/RePEc/els/esrcls/weak.pdf
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. Ponti, Giovanni, 2000. "Cycles of Learning in the Centipede Game," Games and Economic Behavior, Elsevier, vol. 30(1), pages 115-141, January.
    2. 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.
    3. 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.
    4. Samuelson, L., 1989. "Evolutionnary Stability In Asymmetric Games," Papers 11-8-2, Pennsylvania State - Department of Economics.
    5. Fudenberg Drew & Kreps David M., 1993. "Learning Mixed Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 320-367, July.
    6. Borgers Tilman, 1994. "Weak Dominance and Approximate Common Knowledge," Journal of Economic Theory, Elsevier, vol. 64(1), pages 265-276, October.
    7. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
    8. Cooper, Russell & DeJong, Douglas V. & Forsythe, Robert & Ross, Thomas W., 1996. "Cooperation without Reputation: Experimental Evidence from Prisoner's Dilemma Games," Games and Economic Behavior, Elsevier, vol. 12(2), pages 187-218, February.
    9. Cabrales, Antonio & Charness, Gary & Corchon, Luis C., 2003. "An experiment on Nash implementation," Journal of Economic Behavior & Organization, Elsevier, vol. 51(2), pages 161-193, June.
    10. Walker, Mark, 1981. "A Simple Incentive Compatible Scheme for Attaining Lindahl Allocations," Econometrica, Econometric Society, vol. 49(1), pages 65-71, January.
    11. Hofbauer, Josef & Weibull, Jorgen W., 1996. "Evolutionary Selection against Dominated Strategies," Journal of Economic Theory, Elsevier, vol. 71(2), pages 558-573, November.
    12. 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.
    13. Schlag, Karl H., 1998. "Why Imitate, and If So, How?, : A Boundedly Rational Approach to Multi-armed Bandits," Journal of Economic Theory, Elsevier, vol. 78(1), pages 130-156, January.
    14. 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.
    15. 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;Society for Economic Design, vol. 8(2), pages 217-239, October.
    16. 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.
    17. repec:cdl:ucsbec:16-97 is not listed on IDEAS
    18. de Trenqualye, Pierre, 1989. "Stable implementation of Lindahl allocations," Economics Letters, Elsevier, vol. 29(4), pages 291-294.
    19. Marx, Leslie M. & Swinkels, Jeroen M., 2000. "Order Independence for Iterated Weak Dominance," Games and Economic Behavior, Elsevier, vol. 31(2), pages 324-329, May.
    20. Binmore, K. & Samuelson, L., 1995. "Evolutionary Drift and Equilibrium Selection," Working papers 9529, Wisconsin Madison - Social Systems.
    21. 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.
    22. K. Schlag, 2010. "Why Imitate, and if so, How? Exploring a Model of Social Evolution," Levine's Working Paper Archive 454, David K. Levine.
    23. Walker, Mark, 1984. "A simple auctioneerless mechanism with Walrasian properties," Journal of Economic Theory, Elsevier, vol. 32(1), pages 111-127, February.
    24. Dekel, Eddie & Fudenberg, Drew, 1990. "Rational behavior with payoff uncertainty," Journal of Economic Theory, Elsevier, vol. 52(2), pages 243-267, December.
    25. Jorgen W. Weibull, 1997. "Evolutionary Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262731215, January.
    26. Jackson Matthew O. & Palfrey Thomas R. & Srivastava Sanjay, 1994. "Undominated Nash Implementation in Bounded Mechanisms," Games and Economic Behavior, Elsevier, vol. 6(3), pages 474-501, May.
    27. 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.
    28. 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.
    29. Schlag, Karl H., 1998. "Why Imitate, and If So, How?, : A Boundedly Rational Approach to Multi-armed Bandits," Journal of Economic Theory, Elsevier, vol. 78(1), pages 130-156, January.
    30. Borgers, Tilman & Sarin, Rajiv, 1997. "Learning Through Reinforcement and Replicator Dynamics," Journal of Economic Theory, Elsevier, vol. 77(1), pages 1-14, November.
    31. Gilboa, Itzhak & Matsui, Akihiko, 1991. "Social Stability and Equilibrium," Econometrica, Econometric Society, vol. 59(3), pages 859-867, May.
    32. Sjostrom Tomas, 1994. "Implementation in Undominated Nash Equilibria without Integer Games," Games and Economic Behavior, Elsevier, vol. 6(3), pages 502-511, May.
    33. Abreu Dilip & Matsushima Hitoshi, 1994. "Exact Implementation," Journal of Economic Theory, Elsevier, vol. 64(1), pages 1-19, October.
    34. De Trenqualye, Pierre, 1988. "Stability of the Groves and Ledyard mechanism," Journal of Economic Theory, Elsevier, vol. 46(1), pages 164-171, October.
    35. Jordan, J. S., 1986. "Instability in the implementation of Walrasian allocations," Journal of Economic Theory, Elsevier, vol. 39(2), pages 301-328, August.
    36. Samuelson, Larry & Zhang, Jianbo, 1992. "Evolutionary stability in asymmetric games," Journal of Economic Theory, Elsevier, vol. 57(2), pages 363-391, August.
    37. Cabrales, Antonio, 1999. "Adaptive Dynamics and the Implementation Problem with Complete Information," Journal of Economic Theory, Elsevier, vol. 86(2), pages 159-184, June.
    38. 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.
    39. Yan Chen & Fang-Fang Tang, 1998. "Learning and Incentive-Compatible Mechanisms for Public Goods Provision: An Experimental Study," Journal of Political Economy, University of Chicago Press, vol. 106(3), pages 633-662, June.
    40. 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.
    41. Nachbar, J H, 1990. ""Evolutionary" Selection Dynamics in Games: Convergence and Limit Properties," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(1), pages 59-89.
    42. Matsui, Akihiko, 1992. "Best response dynamics and socially stable strategies," Journal of Economic Theory, Elsevier, vol. 57(2), pages 343-362, August.
    43. Binmore, K. & Samuelson, L. & Gale, J., 1993. "Learning to be Imperfect: The Ultimatum Game," Working papers 9325, Wisconsin Madison - Social Systems.
    44. 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.
    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


    Cited by:

    1. William H. Sandholm, 2002. "Evolutionary Implementation and Congestion Pricing," Review of Economic Studies, Oxford University Press, vol. 69(3), pages 667-689.
    2. Jordi Brandts & Antonio Cabrales & Gary Charness, 2007. "Forward induction and entry deterrence: an experiment," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(1), pages 183-209, October.
    3. William H. Sandholm, 2005. "Negative Externalities and Evolutionary Implementation," Review of Economic Studies, Oxford University Press, vol. 72(3), pages 885-915.
    4. Cason, Timothy N. & Saijo, Tatsuyoshi & Sjostrom, Tomas & Yamato, Takehiko, 2006. "Secure implementation experiments: Do strategy-proof mechanisms really work?," Games and Economic Behavior, Elsevier, vol. 57(2), pages 206-235, November.
    5. Roberto Serrano, 2003. "The Theory of Implementation of Social Choice Rules," Working Papers 2003-19, Brown University, Department of Economics.
    6. Cabrales, Antonio & Serrano, Roberto, 2011. "Implementation in adaptive better-response dynamics: Towards a general theory of bounded rationality in mechanisms," Games and Economic Behavior, Elsevier, vol. 73(2), pages 360-374.
    7. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications, Elsevier.
    8. Roberto Serrano & Antonio Cabrales, 2007. "Implementation in Adaptive Better-Response Dynamics," Working Papers 2007-10, Brown University, Department of Economics.
    9. Maskin, Eric & Sjostrom, Tomas, 2002. "Implementation theory," 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 5, pages 237-288 Elsevier.
    10. Galbiati, Marco, 2008. "Fair divisions as attracting Nash equilibria of simple games," Economics Letters, Elsevier, vol. 100(1), pages 72-75, July.
    11. 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.
    12. David K Levine & Aldo Rustichini, 2000. "Introduction: The Dynamic Games Special Issue," Levine's Working Paper Archive 2127, David K. Levine.
    13. Tumennasan, Norovsambuu, 2013. "To err is human: Implementation in quantal response equilibria," Games and Economic Behavior, Elsevier, vol. 77(1), pages 138-152.
    14. 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;Society for Economic Design, vol. 8(2), pages 217-239, October.

    More about this item

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D70 - Microeconomics - - Analysis of Collective Decision-Making - - - General
    • D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy Formulation and Implementation

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. 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). General contact details of provider: http://edirc.repec.org/data/elucluk.html .

    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 CitEc recognized a reference but did not link an item in RePEc 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 RePEc Author Service 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.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.