Weihrauch degrees of finding equilibria in sequential games

2014/07/21 by Roux, Stephane Le, Pauly, Arno
#03D30 #03E15 #03E60 #91A18 #91A44 #Computer Science and Game Theory (cs.GT) #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1407.5587

Abstract

We consider the degrees of non-computability (Weihrauch degrees) of finding winning strategies (or more generally, Nash equilibria) in infinite sequential games with certain winning sets (or more generally, outcome sets). In particular, we show that as the complexity of the winning sets increases in the difference hierarchy, the complexity of constructing winning strategies increases in the effective Borel hierarchy.

Related

• The Weihrauch degree of finding Nash equilibria in multiplayer games
• From winning strategy to Nash equilibrium
• Computation of Stackelberg Equilibria of Finite Sequential Games
• Concurrent games and semi-random determinacy
• Sequential discontinuity and first-order problems