This content will become publicly available on October 1, 2024
This paper considers a twoplayer game where each player chooses a resource from a finite collection of options. Each resource brings a random reward. Both players have statistical information regarding the rewards of each resource. Additionally, there exists an information asymmetry where each player has knowledge of the reward realizations of different subsets of the resources. If both players choose the same resource, the reward is divided equally between them, whereas if they choose different resources, each player gains the full reward of the resource. We first implement the iterative best response algorithm to find an ϵapproximate Nash equilibrium for this game. This method of finding a Nash equilibrium may not be desirable when players do not trust each other and place no assumptions on the incentives of the opponent. To handle this case, we solve the problem of maximizing the worstcase expected utility of the first player. The solution leads to counterintuitive insights in certain special cases. To solve the general version of the problem, we develop an efficient algorithmic solution that combines online convex optimization and the driftplus penalty technique.
more » « less Award ID(s):
 1824418
 NSFPAR ID:
 10494715
 Editor(s):
 Yllka Velaj and Ulrich Berger
 Publisher / Repository:
 Games
 Date Published:
 Journal Name:
 Games
 Volume:
 14
 Issue:
 5
 ISSN:
 20734336
 Page Range / eLocation ID:
 61
 Subject(s) / Keyword(s):
 ["resourcesharing games","congestion games","potential games","worstcase utilitymaximization","driftplus penalty method"]
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

arXiv:2402.05300v2 (Ed.)This paper considers a multiplayer resourcesharing game with a fair reward allocation model. Multiple players choose from a collection of resources. Each resource brings a random reward equally divided among the players who choose it. We consider two settings. The first setting is a oneslot game where the mean rewards of the resources are known to all the players, and the objective of player 1 is to maximize their worstcase expected utility. Certain special cases of this setting have explicit solutions. These cases provide interesting yet nonintuitive insights into the problem. The second setting is an online setting, where the game is played over a finite time horizon, where the mean rewards are unknown to the first player. Instead, the first player receives, as feedback, the rewards of the resources they chose after the action. We develop a novel Upper Confidence Bound (UCB) algorithm that minimizes the worstcase regret of the first player using the feedback received.more » « less

We formulate a mean field game where each player stops a privately observed Brownian motion with absorption. Players are ranked according to their level of stopping and rewarded as a function of their relative rank. There is a unique mean field equilibrium, and it is shown to be the limit of associated nplayer games. Conversely, the mean field strategy induces nplayer εNash equilibria for any continuous reward function—but not for discontinuous ones. In a second part, we study the problem of a principal who can choose how to distribute a reward budget over the ranks and aims to maximize the performance of the median player. The optimal reward design (contract) is found in closed form, complementing the merely partial results available in the nplayer case. We then analyze the quality of the mean field design when used as a proxy for the optimizer in the nplayer game. Surprisingly, the quality deteriorates dramatically as n grows. We explain this with an asymptotic singularity in the induced nplayer equilibrium distributions. Funding: M. Nutz is supported by an Alfred P. Sloan Fellowship and the Division of Mathematical Sciences of the National Science Foundation [Grants DMS1812661 and DMS2106056]. Y. Zhang is supported in part by the Natural Sciences and Engineering Research Council of Canada [NSERC Discovery Grant RGPIN202006290].more » « less

The aim of this paper is to find the distributed solution of the generalized Nash equilibrium problem (GNEP) for a group of players that can communicate with each other over a connected communication network. Each player tries to minimize a local objective function of its own that may depend on the other players’ decisions, and collectively all the players’ decisions are subject to some globally shared resource constraints. After reformulating the local optimization problems, we introduce the notion of network Lagrangian and recast the GNEP as the zero finding problem of a properly defined operator. Utilizing the DouglasRachford operator splitting method, a distributed algorithm is proposed that requires only local information exchanges between neighboring players in each iteration. The convergence of the proposed algorithm to an exact variational generalized Nash equilibrium is established under two different sets of assumptions. The effectiveness of the proposed algorithm is demonstrated using the example of a NashCournot production game.more » « less

Francisco Ruiz, Jennifer Dy (Ed.)We study the sample complexity of identifying an approximate equilibrium for twoplayer zerosum n × 2 matrix games. That is, in a sequence of repeated game plays, how many rounds must the two players play before reaching an approximate equilibrium (e.g., Nash)? We derive instancedependent bounds that define an ordering over game matrices that captures the intuition that the dynamics of some games converge faster than others. Specifically, we consider a stochastic observation model such that when the two players choose actions i and j, respectively, they both observe each other’s played actions and a stochastic observation Xij such that E [Xij ] = Aij . To our knowledge, our work is the first case of instancedependent lower bounds on the number of rounds the players must play before reaching an approximate equilibrium in the sense that the number of rounds depends on the specific properties of the game matrix A as well as the desired accuracy. We also prove a converse statement: there exist player strategies that achieve this lower bound.more » « less

null (Ed.)A twoplayer finite game is represented by two payoff matrices (A, B), one for each player. Imitation games are a subclass of twoplayer games in which B is the identity matrix, implying that the second player gets a positive payoff only if she "imitates" the first. Given that the problem of computing a Nash equilibrium (NE) is known to be provably hard, even to approximate, we ask if it is any easier for imitation games. We show that much like the general case, for any c > 0, computing a 1 over n^c approximate NE of imitation games remains PPADhard, where n is the number of moves available to the players. On the other hand, we design a polynomialtime algorithm to find εapproximate NE for any given constant ε > 0 (PTAS). The former result also rules out the smooth complexity being in P, unless PPAD ⊂ RP.more » « less