A Resource Allocation Game and its Equilibrium Strategies
2026-05-11 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to fairly divide a limited amount of resources among players who each want a certain amount. They focus on a game where players request resources, but resources are given out starting with the smallest requests fully satisfied first. For two players, the authors find specific equilibrium strategies mathematically. For many players, they use approximation techniques to predict equilibrium behaviors and introduce a method to find these equilibria, including a special "chattering" behavior where strategies fluctuate rapidly. They prove their method always works and show examples to illustrate their findings.
Bayesian gameNash equilibriumresource allocationstrategy functionmean-field approximationGaussian approximationsmallest-request-firstall-or-nothing allocationalternating identity-and-flat (AIF) functionschattering regime
Authors
Duan-Shin Lee
Abstract
In this paper we propose a Bayesian game to allocate resources. In this game, there are $c$ units of resources to be allocated to $n$ players. Agent $i$ has a demand of $V_i$ units of resources and takes action $X_i$ according to a strategy function $s_i$, \ie $X_i=s_i(V_i)$. Payoffs are setup such that player $i$ is contented with no more than $V_i$ units of resources. We assume that resources are granted to the players on a smallest-request-first and all-or-nothing basis. For this game with two players, we analyze the equilibrium strategy functions mathematically within the family of alternating identity-and-flat (AIF) functions. We show that Nash equilibrium profiles consist of two identity functions, two AIF functions with a common switch point, or two AIF functions with one and three switch points, respectively. For an $n$-player game with a large $n$ and a large $c_n$ of order $O(n)$, we present a mean-field first order approximation and a second-order Gaussian approximation for its equilibrium strategy function. The first-order analysis obtains an equilibrium AIF function with one switch point. In Gaussian analysis of large games, we propose a construction algorithm. This construction algorithm begins in searching within the family of AIF functions. If a gradient conflict condition occurs, the game enters a chattering regime, in which players play a continuous, strictly increasing strategy function that is not an identity nor a flat function. Conceptually one can view the chattering regime as if players alternate between a slope-one strategy and a flat strategy infinitely fast in order to sustain a high payoff. We prove that the construction algorithm always obtains a Nash equilibrium and terminates in a finite number of steps. We present several numerical examples for the two player game as well as the Gaussian model.