Offline congestion games: How feedback type affects data coverage requirement
This paper investigates when one can efficiently recover an approximate Nash Equilibrium (NE) in offline congestion games. The existing dataset coverage assumption in offline general-sum games inevitably incurs a dependency on the number of actions, which can be exponentially large in congestion games. We consider three different types of feedback with decreasing revealed information. Starting from the facility-level (a.k.a., semi-bandit) feedback, we propose a novel one-unit deviation coverage condition and give a pessimism-type algorithm that can recover an approximate NE. For the agent-level (a.k.a., bandit) feedback setting, interestingly, we show the one-unit deviation coverage condition is not sufficient. On the other hand, we convert the game to multi-agent linear bandits and show that with a generalized data coverage assumption in offline linear bandits, we can efficiently recover the approximate NE. Lastly, we consider a novel type of feedback, the game-level feedback where only the total reward from all agents is revealed. Again, we show the coverage assumption for the agent-level feedback setting is insufficient in the game-level feedback setting, and with a stronger version of the data coverage assumption for linear bandits, we can recover an approximate NE. Together, our results constitute the first study of offline congestion games and imply formal separations between different types of feedback.
Code (0)
등록된 구현이 없습니다.
Tasks
Vocal Bursts Type PredictionSimilar Papers 제목 키워드 기반
Learning in Congestion Games with Bandit Feedback
In this paper, we investigate Nash-regret minimization in congestion games, a class of games with benign theoretical structure and broad real-world applications. We first propose a centralized algorithm based on the opti…
Learning Optimal Tax Design in Nonatomic Congestion Games
In multiplayer games, self-interested behavior among the players can harm the social welfare. Tax mechanisms are a common method to alleviate this issue and induce socially optimal behavior. In this work, we take the ini…
Robust perfect equilibrium in large games
This paper proposes a new equilibrium concept "robust perfect equilibrium" for non-cooperative games with a continuum of players, incorporating three types of perturbations. Such an equilibrium is shown to exist (in symm…
Individual Altruism Cannot Overcome Congestion Effects in a Global Pandemic Game
A key challenge in responding to public health crises such as COVID-19 is the difficulty of predicting the results of feedback interconnections between the disease and society. As a step towards understanding these inter…
Generalized Mirror Descents in Congestion Games
Different types of dynamics have been studied in repeated game play, and one of them which has received much attention recently consists of those based on "no-regret" algorithms from the area of machine learning. It is k…