2026-07-23T22:31:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11150 2024-03-06T10:47:34Z ddc:004 open_access

Non-Cooperative Rational Interactive Proofs Chen, Jing McCauley, Samuel Singh, Shikha non-cooperative game theory extensive-form games with imperfect information refined sequential equilibrium rational proofs interactive proofs Interactive-proof games model the scenario where an honest party interacts with powerful but strategic provers, to elicit from them the correct answer to a computational question. Interactive proofs are increasingly used as a framework to design protocols for computation outsourcing. Existing interactive-proof games largely fall into two categories: either as games of cooperation such as multi-prover interactive proofs and cooperative rational proofs, where the provers work together as a team; or as games of conflict such as refereed games, where the provers directly compete with each other in a zero-sum game. Neither of these extremes truly capture the strategic nature of service providers in outsourcing applications. How to design and analyze non-cooperative interactive proofs is an important open problem. In this paper, we introduce a mechanism-design approach to define a multi-prover interactive-proof model in which the provers are rational and non-cooperative - they act to maximize their expected utility given others' strategies. We define a strong notion of backwards induction as our solution concept to analyze the resulting extensive-form game with imperfect information. We fully characterize the complexity of our proof system under different utility gap guarantees. (At a high level, a utility gap of u means that the protocol is robust against provers that may not care about a utility loss of 1/u.) We show, for example, that the power of non-cooperative rational interactive proofs with a polynomial utility gap is exactly equal to the complexity class P^{NEXP}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jing Chen and Samuel McCauley and Shikha Singh 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.29 urn:nbn:de:0030-drops-111508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode