Playing against no-regret players

DOI10.1016/J.ORL.2023.01.005zbMATH Open1525.91038arXiv2202.09364MaRDI QIDQ6161902FDOQ6161902

Authors: Maurizio D'Andrea 

Publication date: 28 June 2023

Published in: Operations Research Letters (Search for Journal in Brave)

Abstract: In increasingly different contexts, it happens that a human player has to interact with artificial players who make decisions following decision-making algorithms. How should the human player play against these algorithms to maximize his utility? Does anything change if he faces one or more artificial players? The main goal of the paper is to answer these two questions. Consider n-player games in normal form repeated over time, where we call the human player optimizer, and the (n -- 1) artificial players, learners. We assume that learners play no-regret algorithms, a class of algorithms widely used in online learning and decision-making. In these games, we consider the concept of Stackelberg equilibrium. In a recent paper, Deng, Schneider, and Sivan have shown that in a 2-player game the optimizer can always guarantee an expected cumulative utility of at least the Stackelberg value per round. In our first result, we show, with counterexamples, that this result is no longer true if the optimizer has to face more than one player. Therefore, we generalize the definition of Stackelberg equilibrium introducing the concept of correlated Stackelberg equilibrium. Finally, in the main result, we prove that the optimizer can guarantee at least the correlated Stackelberg value per round. Moreover, using a version of the strong law of large numbers, we show that our result is also true almost surely for the optimizer utility instead of the optimizer's expected utility.

Full work available at URL: https://arxiv.org/abs/2202.09364

Recommendations

• No-regret dynamics and fictitious play
• scientific article; zbMATH DE number 1164581
• scientific article; zbMATH DE number 1149740
• Gambling in contests with regret
• No regrets about no-regret
• Cheap play with no regret
• When the players are not expectation maximizers
• Playing to retain the advantage
• Playing to retain the advantage

zbMATH Keywords

repeated gamesStackelberg equilibriano-regret algorithms

Mathematics Subject Classification ID

Decision theory for games (91A35) Multistage and repeated games (91A20)

Cites Work

• Subjectivity and correlation in randomized strategies
• Title not available (Why is that?)
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• A general class of adaptive strategies
• Asymptotic calibration
• How to use expert advice
• Approachability, regret and calibration: implications and equivalences
• Potential-based algorithms in on-line prediction and game theory
• A Randomization Rule for Selecting Forecasts

This page was built for publication: Playing against no-regret players

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161902)