IDEAS home Printed from
   My bibliography  Save this paper

Further results on verification problems in extensive-form games


  • Nicola, Gatti
  • Mario, Gilli
  • Fabio, Panozzo


The computational study of games is receiving increasing attention both in game theory and computer science. The challenge is distinguishing computationally tractable problems (also said easy), admitting polynomial{time algorithms, from the intractable ones (also said hard). In this paper, we focus on extensive form games, as the computational problems defined on such games are largely unexplored. We study the problem (aka verification problem) of certifying that a solution given in input is an equilibrium according to different refinements for extensive form games as the input change. We show that, when the input is a realization plan strategy profile (i.e., strategies for the sequence form representation), deciding whether the input is a Subgame Perfect Equilibrium or is a part of a Sequential Equilibrium is NP-hard even in two-player games (we conjecture the same holds also for Quasi Perfect Equilibrium). This means that there is no polynomial-time algorithm unless P = NP, but it is commonly believed that P x NP. Subsequently, we show that in two{player games, when the input is a behavioral strategy profile, there is a polynomial-time algorithm deciding whether the input is a Quasi-Perfect Equilib- rium, and a simple variation of the algorithm decides whether the input is part of some Sequential Equilibrium (in games with three or more players, the problem is known to be NP{hard for both Quasi-Perfect Equilibrium and Sequential Equilibrium). Finally, we show that, when the input is an assessment, there is a polynomial{time algorithm deciding whether the input is a Sequential Equilibrium regardless the number of players.

Suggested Citation

  • Nicola, Gatti & Mario, Gilli & Fabio, Panozzo, 2016. "Further results on verification problems in extensive-form games," Working Papers 347, University of Milano-Bicocca, Department of Economics, revised 15 Jul 2016.
  • Handle: RePEc:mib:wpaper:347

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Catherine C. Eckel & Philip J. Grossman, 2002. "Sex Differences and Statistical Stereotyping in Attitudes Toward Financial Risk," Monash Economics Working Papers archive-03, Monash University, Department of Economics.
    2. Luca Corazzini & Marco Faravelli & Luca Stanca, 2010. "A Prize To Give For: An Experiment on Public Good Funding Mechanisms," Economic Journal, Royal Economic Society, vol. 120(547), pages 944-967, September.
    3. Marco Faravelli & Luca Stanca, 2007. "Single versus Multiple Prize Contests to Finance Public Goods: Theory and Experimental Evidence," Working Papers 127, University of Milano-Bicocca, Department of Economics, revised Nov 2007.
    4. Konrad, Kai A., 2009. "Strategy and Dynamics in Contests," OUP Catalogue, Oxford University Press, number 9780199549603, June.
    5. A. Mitchell Polinsky & Steven Shavell, 2009. "Public Enforcement of Law," Chapters,in: Criminal Law and Economics, chapter 1 Edward Elgar Publishing.
    6. Lugovskyy, Volodymyr & Puzzello, Daniela & Tucker, Steven, 2010. "An experimental investigation of overdissipation in the all pay auction," European Economic Review, Elsevier, vol. 54(8), pages 974-997, November.
    7. Olivier Armantier & Amadou Boly, 2015. "Framing Of Incentives And Effort Provision," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 56, pages 917-938, August.
    8. Tanjim Hossain & John A. List, 2012. "The Behavioralist Visits the Factory: Increasing Productivity Using Simple Framing Manipulations," Management Science, INFORMS, vol. 58(12), pages 2151-2167, December.
    9. Roland Fryer & Steven Levitt & John List & Sally Sadoff, 2012. "Enhancing the Efficacy of Teacher Incentives through Loss Aversion: A Field Experiment," Framed Field Experiments 00591, The Field Experiments Website.
    10. Dan Kovenock & Michael R. Baye & Casper G. de Vries, 1996. "The all-pay auction with complete information (*)," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(2), pages 291-305.
    11. Steven D. Levitt & John A. List & Susanne Neckermann & Sally Sadoff, 2016. "The Behavioralist Goes to School: Leveraging Behavioral Economics to Improve Educational Performance," American Economic Journal: Economic Policy, American Economic Association, vol. 8(4), pages 183-219, November.
    12. Subhasish M. Chowdhury & Joo Young Jeon & Abhijit Ramalingam, 2016. "Property rights and loss aversion in contests," Working Paper series, University of East Anglia, Centre for Behavioural and Experimental Social Science (CBESS) 16-14, School of Economics, University of East Anglia, Norwich, UK..
    13. Douglas Davis & Robert Reilly, 1998. "Do too many cooks always spoil the stew? An experimental analysis of rent-seeking and the role of a strategic buyer," Public Choice, Springer, vol. 95(1), pages 89-115, April.
    14. Matteo Rizzolli & Luca Stanca, 2012. "Judicial Errors and Crime Deterrence: Theory and Experimental Evidence," Journal of Law and Economics, University of Chicago Press, vol. 55(2), pages 311-338.
    15. Hong, Fuhai & Hossain, Tanjim & List, John A., 2015. "Framing manipulations in contests: A natural field experiment," Journal of Economic Behavior & Organization, Elsevier, vol. 118(C), pages 372-382.
    16. Arye L. Hillman & John G. Riley, 1989. "Politically Contestable Rents And Transfers," Economics and Politics, Wiley Blackwell, vol. 1(1), pages 17-39, March.
    17. Kaplow, Louis & Shavell, Steven, 1994. "Accuracy in the Determination of Liability," Journal of Law and Economics, University of Chicago Press, vol. 37(1), pages 1-15, April.
    18. Roman M. Sheremeta, 2013. "Overbidding And Heterogeneous Behavior In Contest Experiments," Journal of Economic Surveys, Wiley Blackwell, vol. 27(3), pages 491-514, July.
    19. Richard R. W. Brooks & Alexander Stremitzer & Stephan Tontrup, 2012. "Framing Contracts: Why Loss Framing Increases Effort," Journal of Institutional and Theoretical Economics (JITE), Mohr Siebeck, Tübingen, vol. 168(1), pages 62-82, March.
    20. Roman Sheremeta & Jingjing Zhang, 2010. "Can groups solve the problem of over-bidding in contests?," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 35(2), pages 175-197, July.
    21. Edward Millner & Michael Pratt, 1989. "An experimental investigation of efficient rent-seeking," Public Choice, Springer, vol. 62(2), pages 139-151, August.
    22. Urs Fischbacher, 2007. "z-Tree: Zurich toolbox for ready-made economic experiments," Experimental Economics, Springer;Economic Science Association, vol. 10(2), pages 171-178, June.
    23. David Dickinson, 2001. "The Carrot vs. the Stick in Work Team Motivation," Experimental Economics, Springer;Economic Science Association, vol. 4(1), pages 107-124, June.
    24. Png, I. P. L., 1986. "Optimal subsidies and damages in the presence of judicial error," International Review of Law and Economics, Elsevier, vol. 6(1), pages 101-105, June.
    25. Ben Greiner, 2004. "The Online Recruitment System ORSEE 2.0 - A Guide for the Organization of Experiments in Economics," Working Paper Series in Economics 10, University of Cologne, Department of Economics.
    26. Kahneman, Daniel & Tversky, Amos, 1979. "Prospect Theory: An Analysis of Decision under Risk," Econometrica, Econometric Society, vol. 47(2), pages 263-291, March.
    27. Ben Greiner, 2004. "The Online Recruitment System ORSEE - A Guide for the Organization of Experiments in Economics," Papers on Strategic Interaction 2003-10, Max Planck Institute of Economics, Strategic Interaction Group.
    28. Gneezy, Uri & Smorodinsky, Rann, 2006. "All-pay auctions--an experimental study," Journal of Economic Behavior & Organization, Elsevier, vol. 61(2), pages 255-275, October.
    29. Christiane Ernst & Christian Thöni, 2013. "Bimodal Bidding in Experimental All-Pay Auctions," Games, MDPI, Open Access Journal, vol. 4(4), pages 1-16, October.
    Full references (including those not matched with items on IDEAS)

    More about this item


    Ecient algorithms; extensive{form re nements;

    JEL classification:

    • C7 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    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:mib:wpaper:347. 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: (Matteo Pelagatti). General contact details of provider: .

    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.

    We have no references for this item. You can help adding them by using 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.