Learning in Proportional Allocation Auctions Games

Younes Ben Mazziane; Cleque-Marlain Mboulou Moutoubi; Eitan Altman; Francesco De Pellegrini

cs.GTMar 26, 2026

Learning in Proportional Allocation Auctions Games

Authors: Younes Ben Mazziane, Cleque-Marlain Mboulou Moutoubi, Eitan Altman, Francesco De Pellegrini

Organizations: LIA, Avignon university, Avignon, France · INRIA, Sophia Antipolis, France

Abstract

The Kelly or proportional allocation mechanism is a simple and efficient auction-based scheme that distributes an infinitely divisible resource proportionally to the agents bids. When agents are aware of the allocation rule, their interactions form a game extensively studied in the literature. This paper examines the less explored repeated Kelly game, focusing mainly on utilities that are logarithmic in the allocated resource fraction. We first derive this logarithmic form from fairness-throughput trade-offs in wireless network slicing, and then prove that the induced stage game admits a unique Nash equilibrium NE. For the repeated play, we prove convergence to this NE under three behavioral models: (i) all agents use Online Gradient Descent (OGD), (ii) all agents use Dual Averaging with a quadratic regularizer (DAQ) (a variant of the Follow-the-Regularized leader algorithm), and (iii) all agents play myopic best responses (BR). Our convergence results hold even when agents use personalized learning rates in OGD and DAQ (e.g., tuned to optimize individual regret bounds), and they extend to a broader class of utilities that meet a certain sufficient condition. Finally, we complement our theoretical results with extensive simulations of the repeated Kelly game under several behavioral models, comparing them in terms of convergence speed to the NE, and per-agent time-average utility. The results suggest that BR achieves the fastest convergence and the highest time-average utility, and that convergence to the stage-game NE may fail under heterogeneous update rules.

Figures & tables

Fig. 1 : Repeated resource allocation game.

Fig. 2 : Bandwidth Allocation between tenants and users

$\gamma$	$n$	BR	OGD V	OGD F	DAQ F	DAQ V	RRM V
0	2	15	37	122	195	$(r_{T}=3.7{\times}10^{-2})$	1682
	10	7	19	240	311	$(r_{T}=1.05)$	2291
	20	6	20	252	330	$(r_{T}=1.73)$	2361
5	2	15	111	127	184	$(r_{T}=1.0{\times}10^{-1})$	504
	10	7	40	206	274	$(r_{T}=6.8{\times}10^{-1})$	2182
	20	6	1811	221	289	$(r_{T}=7.5{\times}10^{-1})$	2220

TABLE I : Homogeneous dynamics: number of convergence iterations in terms of the fixed-point residual

r_{t}

(threshold

<10^{-5}

) under varying

\gamma

and

n

Panel of Figure 4 — Fig. 3 : Convergence speed under homogeneous dynamics and varying payoff’s heterogeneity levels.

Panel of Figure 5 — Fig. 4 : Agent’s payoff, $\gamma=0$ .

Panel of Figure 6 — Fig. 5 : Heterogeneous dynamics. In each sub-figure: instantaneous payoff (top) and bids (bottom).

Panel of Figure 7 — Fig. 6 : Heterogeneous dynamics: Average payoff

Panel of Figure 8 — Fig. 7 : Heterogeneous dynamics: $\texttt{DAQ}_{\mathrm{F}}$ vs. $\texttt{OGD}_{\mathrm{F}}$ . In each subfigure: bids (top) and instantaneous payoff (bottom).

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 236 papers

Strategyproof Deep Reinforcement Learning for Online Resource Allocation
Oct 27, 2026Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah +1Online Resource Allocation Mechanism Design
University of Southampton
High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
Sep 14, 2026S. Rasoul EtesamiPolicy Gradient Asynchronous RL
Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA
DNQ: Deep Nash Q-Network for Partially Observable n-Player Games
Jun 4, 2026Qintong Xie, Edward Koh, Xavier Cadet +1Nash Equilibrium Reinforcement Learning

Oct 27, 2026J/K move · Enter open · S save

Strategyproof Deep Reinforcement Learning for Online Resource Allocation

Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah, Stephanie Gauthier

University of Southampton

Online Resource Allocation Mechanism Design Game-Theoretic RL Game Theory

Open paper AskPDF arXiv

Online resource allocation faces two coupled challenges: (1) allocating scarce resources efficiently under uncertain future demand, and (2) ensuring that agents report task valuations and requirements truthfully (strategyproofness). Reinforcement Learning (RL) adapts allocation decisions through experience but does not necessarily ensure strategyproofness. Existing strategyproof RL uses a linear allocation rule, which limits the resource interactions it can represent. Neural mechanism design methods offer greater expressiveness, but provide only approximate incentive guarantees. Against this background, we introduce the first strategyproof deep RL mechanism for online resource allocation. It integrates three novel components: (i) a monotonic neural network that learns nonlinear interactions by construction (higher reported value cannot reduce acceptance, while a longer reported duration or larger resource requirement cannot increase it); (ii) a generalised critical payment: the lowest accepted value, with all other inputs fixed; and (iii) training by either RL or imitation of an existing rule. Together, monotonicity and the critical payment ensure strategyproofness and individual rationality, while the neural rule provides flexibility and imitation improves training efficiency. Empirically, on a four-resource stream with two partner pairs that a linear difference cannot represent, the neural rule achieves 97.8% of an offline welfare upper bound, compared with 93.8% for a linear learner and 89.0% for first-come, first-served, closing 65% and 80% of the remaining optimality gap, respectively. Moreover, imitation reaches 97.5% in only 261 seconds, about 89 times faster than RL.

Abstract

Game Theory

Explore similar work

Strategyproof Deep Reinforcement Learning for Online Resource Allocation

High-Probability Nash Regret for Decentralized Learning in Markov ααα-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

DNQ: Deep Nash Q-Network for Partially Observable n-Player Games

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games