Abstract
Interactiveproof 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 interactiveproof games largely fall into two categories: either as games of cooperation such as multiprover 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 zerosum game. Neither of these extremes truly capture the strategic nature of service providers in outsourcing applications. How to design and analyze noncooperative interactive proofs is an important open problem.
In this paper, we introduce a mechanismdesign approach to define a multiprover interactiveproof model in which the provers are rational and noncooperative  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 extensiveform 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 noncooperative rational interactive proofs with a polynomial utility gap is exactly equal to the complexity class P^{NEXP}.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2019:11150,
author = {Jing Chen and Samuel McCauley and Shikha Singh},
title = {{NonCooperative Rational Interactive Proofs}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {29:129:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11150},
URN = {urn:nbn:de:0030drops111508},
doi = {10.4230/LIPIcs.ESA.2019.29},
annote = {Keywords: noncooperative game theory, extensiveform games with imperfect information, refined sequential equilibrium, rational proofs, interactive proofs}
}
Keywords: 

noncooperative game theory, extensiveform games with imperfect information, refined sequential equilibrium, rational proofs, interactive proofs 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 