4 papers
Tracking the Best Strategy in an Extensive-Form Game
Stephen Pasteris, Rahul Savani, Theodore Turocy
We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regre…
Differential Privacy in the Extensive-Form Bandit Problem
Stephen Pasteris, Rahul Savani, Theodore Turocy
We consider the extensive-form bandit problem, where on each trial the learner (a user coordinated by a server) plays an extensive-form game against an oblivious adversary, observi…
The Complexity of Sparse Win-Lose Bimatrix Games
Eleni Batziou, John Fearnley, Abheek Ghosh +1
We prove that computing an -approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial . Our result holds for 3-spa…
From Natural Language to Extensive-Form Game Representations
Shilong Deng, Yongzhao Wang, Rahul Savani
We introduce a framework for translating game descriptions in natural language into extensive-form representations in game theory, leveraging Large Language Models (LLMs) and in-co…