Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with games:
TR13-136 | 27th September 2013
Paul Goldberg, Aaron Roth

Bounds for the Query Complexity of Approximate Equilibria

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>>

TR14-016 | 16th January 2014
Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

The Complexity of Debate Checking

We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

ISSN 1433-8092 | Imprint