arxiv: 2605.09988 · v1 · submitted 2026-05-11 · 💻 cs.GT

Recognition: no theorem link

A Resource Allocation Game and its Equilibrium Strategies

Duan-Shin Lee

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:43 UTC · model grok-4.3

classification 💻 cs.GT

keywords resource allocationBayesian gameNash equilibriumalternating identity-flat functionsmean-field approximationGaussian approximationchattering regimeconstruction algorithm

0 comments

The pith

In a resource allocation game with smallest-first all-or-nothing grants, Nash equilibria for two players are specific pairs of identity or alternating identity-flat functions, and a finite algorithm constructs them for large numbers of玩家.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets up a Bayesian game in which a fixed pool of c resource units is awarded to n players according to their private demands, with each player choosing a request via a strategy function and receiving payoff only if granted exactly up to their demand. It restricts attention to the family of alternating identity-and-flat strategy functions to derive all two-player Nash equilibria and shows they fall into three explicit profile types. For large n with c of order n it supplies a mean-field first-order AIF equilibrium and a Gaussian second-order construction procedure that begins in the AIF family, switches to a chattering regime on gradient conflict, and is proved to reach a true Nash equilibrium after finitely many steps. A reader would care because the model captures competitive resource requests in networks or computing systems and supplies concrete functional forms rather than abstract existence results.

Core claim

For the two-player game the Nash equilibrium profiles inside the AIF family are either two identity functions, two AIF functions sharing one switch point, or a pair consisting of a one-switch AIF and a three-switch AIF. For large n the first-order mean-field limit produces a single-switch AIF equilibrium; the Gaussian approximation yields a construction algorithm that searches the AIF family and, when a gradient conflict appears, enters a chattering regime in which players effectively alternate between slope-one and flat segments at infinite speed. The algorithm is proved always to terminate after finitely many steps at a Nash equilibrium.

What carries the argument

Alternating identity-and-flat (AIF) functions, which are piecewise strategies that alternate between segments of slope one (identity) and flat (constant) segments, used both to enumerate two-player equilibria and as the starting family for the large-n construction algorithm.

If this is right

Two-player games admit only three equilibrium types inside the AIF family.
The mean-field limit supplies an explicit one-switch AIF equilibrium for large player counts.
The construction algorithm reaches a Nash equilibrium in finite steps even after entering the chattering regime.
Numerical examples confirm that the Gaussian approximation matches simulated equilibria for moderate n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The chattering regime offers a deterministic way to realize what would otherwise require mixed strategies in a continuous-action game.
Explicit switch-point formulas could be derived for particular demand distributions such as exponential or uniform, enabling closed-form predictions.
The model suggests that mechanism designers could enforce the smallest-first rule to make equilibrium strategies more predictable than in proportional allocation.

Load-bearing premise

Equilibrium strategies can be found or approximated inside the restricted family of alternating identity-and-flat functions without missing other equilibria or requiring different functional forms.

What would settle it

A counter-example in which a continuous strictly increasing non-AIF strategy yields strictly higher expected payoff against every AIF equilibrium strategy for some two-player demand distribution, or a large-n instance in which the construction algorithm cycles indefinitely or stabilizes at a non-equilibrium point.

Figures

Figures reproduced from arXiv: 2605.09988 by Duan-Shin Lee.

**Figure 1.** Figure 1: Payoff function of player one is drawn in a dot-dashed line and payoff function of player two is drawn in a thick solid line. In this case, c = 2, λ1 = 1 and λ2 = 2. In this case, s1 and s2 are AIF functions with a common switch point at v ∗ 2 = 1.17062. This switch point is marked by a red vertical dashed line. Function values p1,I (v ∗ 2 ) and p2,I (v ∗ 2 ) are marked by horizontal blue dotted lines. The… view at source ↗

**Figure 2.** Figure 2: Payoff function of player one is drawn in a dot-dashed line and payoff function of player two is drawn in a thick solid line. In this case, c = 2, λ1 = 1 and λ2 = 3. The switch points of s1 are marked by three vertical red dashed lines. Function values p1,I (v ∗ 2 ), p2,I (v ∗ 2 ) and p1,F(t1,3) are marked by horizontal blue dotted lines. v 999.8966 1150 1250 1500 1700 1800 2000 η(v) 999.8966 1000.27 1000.… view at source ↗

**Figure 3.** Figure 3: Chattering strategy η(v). The identity strategy function is shown in red dotted line. Gaussian approximation model. Appendix A Proof of Proposition 3, Lemma 5 and Theorem 6 Proof of Proposition 3. Since we assume that strategy function s is non-decreasing, its right-continuous generalized inverse function s← is also non-decreasing. Cumulative distribution functions are non-decreasing. Composite functions F… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper introduces a Bayesian resource allocation game with all-or-nothing smallest-first allocation, characterizes AIF equilibria for two players, and gives a construction algorithm for large n that switches to a chattering regime, but the chattering part is only conceptual.

read the letter

The core contribution is a game where n players have private demands V_i drawn from some distribution, choose requests via strategy functions s_i, and receive resources only if their request is among the smallest, with all-or-nothing grants up to c units total. Payoffs make a player content once they get at least V_i. For two players the authors stay inside the alternating identity-and-flat (AIF) family and list the possible Nash profiles: both identity, both AIF with one shared switch point, or one AIF with one switch and the other with three. That case analysis is explicit and comes with numerical checks. For large n with c_n linear in n they first derive a mean-field AIF equilibrium with a single switch point, then move to a Gaussian second-order approximation and build an iterative algorithm that searches inside AIF functions. When a gradient conflict appears the algorithm enters the chattering regime, described as players alternating slope-1 and flat segments at infinite speed to produce a continuous strictly increasing strategy. The claim is that this algorithm always returns a Nash equilibrium and stops after finitely many steps. Numerical examples are shown for both the two-player and the Gaussian cases. What is actually new is the specific pairing of the allocation rule with the AIF family plus the chattering device for handling the large-game approximation; these pieces do not collapse to earlier results cited in the abstract. The two-player work is the strongest part because the cases are finite and checkable. The large-n construction is concrete as an algorithm, which is better than a pure existence argument. The soft spot is exactly the chattering regime. It is introduced only conceptually, without an explicit limiting construction or a direct verification that the resulting function remains a best response under the approximated payoffs. The termination proof is stated for the overall algorithm, yet it is unclear whether the argument still holds once the regime is active. The mean-field and Gaussian steps are also taken as valid without reported error bounds or simulation checks against the original finite-n game. This paper is aimed at game theorists who study mechanism design for resource sharing under incomplete information, especially those comfortable with mean-field approximations. A reader looking for new equilibrium constructions in allocation games will find usable material in the two-player section and the algorithm outline. It deserves a serious referee because the model is cleanly defined, the small-case results are specific, and the large-n procedure raises concrete questions that can be answered by revision. I would send it to peer review but would ask the referees to focus on whether the chattering object can be made rigorous as a strategy and equilibrium in the limit.

Referee Report

1 major / 2 minor

Summary. The paper proposes a Bayesian resource allocation game in which n players with private demands V_i select actions X_i = s_i(V_i) and resources are allocated on a smallest-request-first, all-or-nothing basis. For the two-player case the authors characterize Nash equilibrium profiles within the family of alternating identity-and-flat (AIF) strategy functions, showing that they consist of two identity functions, two AIF functions sharing a common switch point, or AIF functions with one and three switch points. For large n with c_n of order O(n) they derive a mean-field first-order AIF equilibrium with one switch point and then a second-order Gaussian construction algorithm that searches within AIF functions; when a gradient conflict arises the algorithm enters a chattering regime whose strategy is described as the infinite-speed alternation of slope-1 and flat segments, yielding a continuous strictly increasing function. The paper asserts that this algorithm always produces a Nash equilibrium and terminates after finitely many steps, and supplies numerical illustrations for both the two-player and Gaussian cases.

Significance. If the chattering regime can be placed on a rigorous footing, the work would supply a concrete algorithmic method for approximating equilibria in large Bayesian resource-allocation games that combines mean-field and Gaussian corrections with a finite-termination guarantee. The explicit two-player characterization inside the AIF family is a clear technical contribution, and the finite-step claim for the construction procedure would be attractive for computational applications in mechanism design or distributed resource systems.

major comments (1)

[Gaussian analysis and construction algorithm] In the Gaussian-analysis and construction-algorithm section the chattering regime is introduced only conceptually (infinite alternation of slope-1 and flat segments) without a formal definition as a measurable strategy, a limit construction, or a verification that the resulting function remains a best response in the Gaussian-approximated payoff. Consequently the claim that the algorithm 'always obtains a Nash equilibrium' once this regime is entered, together with the finite-termination argument, rests on an incomplete foundation and constitutes the principal load-bearing gap for the large-n result.

minor comments (2)

[Abstract and two-player analysis] The abstract and early sections would benefit from an explicit statement that the two-player analysis is exhaustive only inside the AIF family rather than claiming all possible equilibria.
[Notation and definitions] Notation for the AIF switch points and the precise definition of the gradient-conflict condition should be introduced with displayed equations before the algorithm is described.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough reading and for highlighting the need for a more rigorous treatment of the chattering regime. We agree that the current manuscript presents this regime primarily at a conceptual level and will revise the Gaussian-analysis section to supply the missing formal foundations.

read point-by-point responses

Referee: In the Gaussian-analysis and construction-algorithm section the chattering regime is introduced only conceptually (infinite alternation of slope-1 and flat segments) without a formal definition as a measurable strategy, a limit construction, or a verification that the resulting function remains a best response in the Gaussian-approximated payoff. Consequently the claim that the algorithm 'always obtains a Nash equilibrium' once this regime is entered, together with the finite-termination argument, rests on an incomplete foundation and constitutes the principal load-bearing gap for the large-n result.

Authors: We acknowledge that the chattering regime is described conceptually in the present version. In the revision we will define the chattering strategy formally as the pointwise limit of a sequence of AIF functions whose number of switches tends to infinity while the switch points become dense in an interval; this limit is a continuous, strictly increasing, measurable function. We will then verify that the limiting payoff under the Gaussian approximation is continuous in the strategy and that the chattering function satisfies the first-order optimality condition (no profitable deviation) within the approximated game. With these additions the existing finite-termination argument for the construction algorithm carries through, because each step before chattering remains within the AIF family and the chattering regime, once entered, is shown to be an equilibrium. We believe this closes the identified gap while preserving the algorithmic character of the large-n result. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations start from game definition and proceed via explicit best-response analysis

full rationale

The paper begins with an explicit definition of the Bayesian resource allocation game, payoffs, and strategy functions s_i(V_i) on measurable functions with all-or-nothing allocation. Two-player equilibria are derived mathematically by restricting to the AIF family and solving the resulting best-response conditions, yielding the stated profiles of identity functions or AIF functions with one or three switch points. For large n the mean-field first-order AIF equilibrium is obtained directly from the limiting payoff, after which the second-order Gaussian construction algorithm is defined to search within AIF functions and switch to a chattering regime only upon gradient conflict; the termination and Nash property are proved from the algorithm's finite-step rules and the approximation structure. No parameters are fitted to target equilibria and then relabeled as predictions, no load-bearing self-citations appear, and no ansatz is imported via prior work. The chattering regime is introduced conceptually within the construction rather than presupposed, so the central claims do not reduce to their inputs by definition or construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on standard Bayesian game assumptions plus the restriction to the AIF function family and the validity of the mean-field limit; no new physical entities are postulated.

axioms (2)

domain assumption Players have private demands V_i drawn from a known distribution and choose actions X_i = s_i(V_i) to maximize expected payoff under the smallest-request-first all-or-nothing rule.
Stated in the model setup; required for the Bayesian game formulation.
ad hoc to paper Equilibrium analysis is confined to the family of alternating identity-and-flat functions.
Explicitly chosen for the two-player mathematical analysis.

invented entities (2)

Alternating identity-and-flat (AIF) strategy functions no independent evidence
purpose: Restricted class in which equilibria are sought for the two-player game
Introduced to make the equilibrium characterization tractable
Chattering regime no independent evidence
purpose: Continuous strictly increasing strategy that alternates slope-one and flat infinitely fast when gradient conflict occurs
Constructed to sustain high payoff in the Gaussian approximation

pith-pipeline@v0.9.0 · 5672 in / 1539 out tokens · 39965 ms · 2026-05-12T03:43:15.712743+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

[1]

Challenges and issues of resource allocation techniques in cloud computing,

A. Abid, M. F. Manzoor, M. S. Farooq, U. Farooq, and M. Hussain, “Challenges and issues of resource allocation techniques in cloud computing,”KSII Transactions on Internet & Information Systems, vol. 14, no. 7, 2020

work page 2020
[2]

A review of internet of things — resource allocation,

X. Li and L. D. Xu, “A review of internet of things — resource allocation,”IEEE Internet of Things Journal, vol. 8, no. 11, pp. 8657–8666, 2021

work page 2021
[3]

A survey on resource allocation for 5G heterogeneous networks: Current research, future trends, and challenges,

Y. Xu, G. Gui, H. Gacanin, and F. Adachi, “A survey on resource allocation for 5G heterogeneous networks: Current research, future trends, and challenges,”IEEE Communications Surveys & Tutorials, vol. 23, no. 2, pp. 668–695, 2021

work page 2021
[4]

Fair resource allocation in systems with complete information sharing,

F. Fossati, S. Hoteit, S. Moretti, and S. Secci, “Fair resource allocation in systems with complete information sharing,” IEEE/ACM Transactions on Networking, vol. 26, no. 6, pp. 2801–2814, 2018

work page 2018
[5]

Rate control for communication networks: Shadow prices, proportional fairness and stability,

F. P . Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability,”J. Oper. Res. Soc., vol. 49, no. 3, p. 237–252, March 1998

work page 1998
[6]

Fair optimization and networks: A survey,

W. Ogryczak, H. Luss, M. Pi ´oro, D. Nace, and A. Tomaszewski, “Fair optimization and networks: A survey,”Journal of Applied Mathematics, vol. 2014, no. 612018, pp. 1–25, 2014

work page 2014
[7]

Fair end-to-end window-based congestion control,

J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,”IEEE/ACM Trans. on Networking, vol. 8, no. 5, p. 556–567, October 2000. 23

work page 2000
[8]

A quantitative measure of fairness and discrimination for resource allocation in shared computer system,

R. Jain, D. M. Chiu, , and W. R. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer system,” Hudson, MA, USA, Eastern Research Laboratory, Digital Equipment Corporation, 1984

work page 1984
[9]

Resource allocation for URLLC and eMBB traffic in uplink wireless networks,

D.-S. Lee, C.-S. Chang, R. Zhang, and M.-P . Lee, “Resource allocation for URLLC and eMBB traffic in uplink wireless networks,”Performance Evaluation, vol. 161, September 2023

work page 2023
[10]

Distributed algorithm design for resource allocation problems of high-order multiagent systems,

Z. Deng, “Distributed algorithm design for resource allocation problems of high-order multiagent systems,”IEEE Transactions on Control of Network Systems, vol. 8, no. 1, pp. 177–186, 2021

work page 2021
[11]

Distributed resource allocation algorithm for general linear multiagent systems,

B. Shao, M. Li, and X. Shi, “Distributed resource allocation algorithm for general linear multiagent systems,”IEEE Access, vol. 10, pp. 74 691–74 701, 2022

work page 2022
[12]

Distributed resource allocation algorithms,

J. Bar-Ilan and D. Peleg, “Distributed resource allocation algorithms,” inInternational Workshop on Distributed Algorithms. Springer, 1992, pp. 277–291

work page 1992
[13]

Game-theoretic resource allocation for fog-based industrial internet of things environment,

Y. Jie, C. Guo, K.-K. R. Choo, C. Z. Liu, and M. Li, “Game-theoretic resource allocation for fog-based industrial internet of things environment,”IEEE Internet of Things Journal, vol. 7, no. 4, pp. 3041–3052, 2020

work page 2020
[14]

Bankruptcy games,

I. Curiel, M. Maschler, and S. Tijs, “Bankruptcy games,”Zeitschrift f ¨ur Operations Research, vol. 31, p. A143–A159, 1987

work page 1987
[15]

Game theoretic resource allocation for multicell D2D communications with incomplete information,

J. Huang, Y. Yin, Y. Sun, Y. Zhao, C.-c. Xing, and Q. Duan, “Game theoretic resource allocation for multicell D2D communications with incomplete information,” in2015 IEEE International Conference on Communications (ICC). IEEE, 2015, pp. 3039–3044

work page 2015
[16]

A new game theoretical resource allocation algorithm for cloud computing,

F. Teng and F. Magoul `es, “A new game theoretical resource allocation algorithm for cloud computing,” inAdvances in Grid and Pervasive Computing: 5th International Conference, GPC 2010, Hualien, Taiwan, May 10-13, 2010. Proceedings 5. Springer, 2010, pp. 321–330

work page 2010
[17]

A. S. Tanenbaum,Modern Operating Systems, 3rd ed. Pearson Education, Inc., 2008

work page 2008
[18]

Stationary analysis of the shortest queue first service policy,

F. Guillemin and A. Simonian, “Stationary analysis of the shortest queue first service policy,”Queueing System, vol. 77, p. 393–426, 2014

work page 2014
[19]

The queue M/G/1 with the shortest remaining processing time discipline,

L. E. Schrage and L. W. Miller, “The queue M/G/1 with the shortest remaining processing time discipline,”Operations Research, vol. 14, no. 4, pp. 670 – 684, 1966

work page 1966
[20]

Performance of the smallest-variance-first rule in appointment sequencing,

M. A. de Kemp, M. Mandjes, and N. Olver, “Performance of the smallest-variance-first rule in appointment sequencing,” Operations Research, vol. 69, no. 6, pp. 1909 – 1935, November-December 2021

work page 1909
[21]

Winning the battle but losing the war: The psychology of debt management,

M. Amar, D. Ariely, S. Ayal, C. E. Cryder, and S. I. Rick, “Winning the battle but losing the war: The psychology of debt management,”Journal of Marketing Research, vol. XLVIII (Special Issue 2011), p. S38 – S50, 2011

work page 2011
[22]

M. J. Osborne,An introduction to game theory. New York: Oxford University Press, 2004

work page 2004
[23]

Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle,

M. Huang, R. P . Malham ´e, and P . E. Caines, “Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle,”Communications in Information & Systems, vol. 6, no. 3, pp. 221– 252, 2006

work page 2006
[24]

Mean field games,

J.-M. Lasry and P .-L. Lions, “Mean field games,”Japanese Journal of Mathematics, vol. 2, no. 1, pp. 229–260, 2007

work page 2007
[25]

Anonymous sequential games,

B. Jovanovic and R. W. Rosenthal, “Anonymous sequential games,”Journal of Mathematical Economics, vol. 17, no. 1, pp. 77–87, 1988

work page 1988
[26]

From the master equation to mean field game limit theory: a central limit theorem,

F. Delarue, D. Lacker, and K. Ramanan, “From the master equation to mean field game limit theory: a central limit theorem,” Electronic Journal of Probability, vol. 24, pp. 1–54, 2019

work page 2019
[27]

Cardaliaguet, F

P . Cardaliaguet, F. Delarue, J.-M. Lasry, and P .-L. Lions,The master equation and the convergence problem in mean field games, ser. Annals of Mathematics Studies. Princeton University Press, 2019, vol. 201

work page 2019
[28]

The Fokker-Planck equation of N-particles systems and its mean field limit,

C. Bertucci, J.-M. Lasry, and P .-L. Lions, “The Fokker-Planck equation of N-particles systems and its mean field limit,” Communications in Mathematical Physics, vol. 370, no. 3, pp. 991–1025, 2019

work page 2019
[29]

Whitt,Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues, ser

W. Whitt,Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues, ser. Springer Series in Operations Research and Financial Engineering. New York: Springer, 2002

work page 2002
[30]

Y. S. Chow and H. Teicher,Probability Theory: Independence, Interchangeability, Martingales, 2nd ed., ser. Springer Texts in Statistics. Springer-Verlag, 1988

work page 1988
[31]

M. I. Zelikin and V. Borisov,Theory of Chattering Control with Applications to Astronautics, Robotics, Economics, and Engineering. Boston, MA: Birkh ¨auser, 1994

work page 1994
[32]

Rudin,Principles of Mathematical Analysis, 3rd ed

W. Rudin,Principles of Mathematical Analysis, 3rd ed. New York: McGraw-Hill, 1976

work page 1976
[33]

U. M. Ascher and L. R. Petzold,Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 1998. 24

work page 1998