6 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-spars…
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…
Policy Space Response Oracles: A Survey
Ariyan Bighashdel, Yongzhao Wang, Stephen McAleer +2
Game theory provides a mathematical way to study the interaction between multiple decision makers. However, classical game-theoretic analysis is limited in scalability due to the l…
Robust Market Making via Adversarial Reinforcement Learning
Thomas Spooner, Rahul Savani
We show that adversarial reinforcement learning (ARL) can be used to produce market marking agents that are robust to adversarial and adaptively-chosen market conditions. To apply…