Timezone: »

 
Poster
Strategizing against No-regret Learners
Yuan Deng · Jon Schneider · Balasubramanian Sivan

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #222
in Theory -- Game Theory and Computational Economics »

How should a player who repeatedly plays a game against a no-regret learner strategize to maximize his utility? We study this question and show that under some mild assumptions, the player can always guarantee himself a utility of at least what he would get in a Stackelberg equilibrium. When the no-regret learner has only two actions, we show that the player cannot get any higher utility than the Stackelberg equilibrium utility. But when the no-regret learner has more than two actions and plays a mean-based no-regret strategy, we show that the player can get strictly higher than the Stackelberg equilibrium utility. We construct the optimal game-play for the player against a mean-based no-regret learner who has three actions. When the no-regret learner's strategy also guarantees him a no-swap regret, we show that the player cannot get anything higher than a Stackelberg equilibrium utility.

Keywords: Online Learning · Game Theory and Computational Economics · Algorithms · Theory
[ Paper]  [ Poster] 

Author Information

Yuan Deng (Duke University)
Jon Schneider (Google Research)
Balasubramanian Sivan (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors