Paper deep dive
Learning in Proportional Allocation Auctions Games
Younes Ben Mazziane, Cleque-Marlain Mboulou Moutoubi, Eitan Altman, Francesco De Pellegrini
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/27/2026, 1:13:08 AM
Summary
This paper analyzes the repeated Kelly (proportional allocation) game, specifically focusing on logarithmic utility functions derived from fairness-throughput trade-offs in wireless network slicing. The authors prove the existence of a unique Nash equilibrium (NE) using Rosen's Diagonal Strict Concavity (DSC) condition. They establish convergence to this NE under three behavioral models: Online Gradient Descent (OGD), Dual Averaging with a quadratic regularizer (DAQ), and myopic best-response (BR) dynamics, even with heterogeneous learning rates. Numerical simulations confirm that BR dynamics achieve the fastest convergence and highest time-average utility.
Entities (6)
Relation Signals (3)
Best Response → achievesfastestconvergencein → Repeated Kelly game
confidence 95% · The results suggest that BR achieves the fastest convergence and the highest time-average utility
Kelly mechanism → induces → Repeated Kelly game
confidence 95% · 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
Online Gradient Descent → guaranteesconvergenceto → Nash Equilibrium
confidence 92% · For the repeated play, we prove convergence to this NE under three behavioral models: (i) all agents use Online Gradient Descent (OGD)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.25303v1
- Canonical: https://arxiv.org/abs/2603.25303v1
Trouble viewing inline? Open PDF directly →
Full Text
80,943 characters extracted from source content.
Expand or collapse full text
Learning in Proportional Allocation Auctions Games Younes Ben Mazziane1, Cleque-Marlain Mboulou Moutoubi1, Eitan Altman1,2 and Francesco De Pellegrini1 1LIA, Avignon university, Avignon, France; 2INRIA, 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), (i) all agents use Dual Averaging with a quadratic regularizer (DAQ) (a variant of the Follow-the-Regularized leader algorithm), and (i) 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. I Introduction Decentralized resource allocation in large-scale systems is a fundamental problem extensively studied in network economics [14]. In this context, a resource owner seeks to distribute resources among multiple agents to optimize an objective, such as maximizing social welfare, namely, the aggregate net benefit of the agents, or their own revenue. It is standard to assume that the resource owner may have partial or lack information about the agents’ utilities or preferences. Instead, they depend on signals [17] provided by the agents, such as declared valuations, willingness to pay, or other indirect indicators of agents’ preferences. Moreover, agents often act selfishly and strategically in order to maximize their benefits. This problem is prevalent in various technological domains, including bandwidth allocation in communication networks [18], task scheduling in cloud computing [29], energy distribution in smart grids [27], and pricing mechanisms in shared transportation systems [32]. Figure 1: Repeated resource allocation game. The Kelly or proportional allocation mechanism stands out among decentralized resource allocation mechanisms for its simplicity and efficiency [15, 14]. In its basic form, agents submit bids to secure shares of a finite, infinitely divisible resource, with allocations distributed proportionally to their bids. In a generalized formulation [17], each user’s allocation is determined by a weighting function of their bid, enabling diverse allocation strategies. In particular, the classic Kelly mechanism arises when this weighting function is simply the identity for all agents. Many works have shown that the Kelly mechanism enjoys strong social-welfare optimality guarantees across several settings: (i) agents with unlimited budgets who are either price takers (unaware of the allocation rule) [15] or price anticipator (aware of it) [13, 17, 30], and (i) environments in which price anticipator agents have budget constraints [28, 2, 3]. More specifically, price anticipator agents induce a competitive game with continuous action sets, and the guarantees in terms of social welfare hold exclusively at a Nash Equilibrium (NE) of this game, that we refer to as the Kelly game in the sequel. In practice, however, agents are not necessarily aware of the utilities of other agents. A more realistic setting is when agents know only their own utilities but adapt their bids over repeated synchronous rounds based on feedback from previous rounds, e.g., the aggregate bid. This motivates the study of the repeated Kelly game. Figure 1 illustrates this setting, where at each round, agents compete over a new resource by submitting bids based on outcomes from previous rounds. They then receive a fraction of the resource according to the Kelly mechanism. In this setting, rational agents aim to maximize their time-average utility. To our knowledge, only a few works have examined the repeated Kelly game [9, 5, 8], and they focus on the case where agents’ utilities are linear in the fraction of the allocated resource. This case coincides with Tullock (rent-seeking) contests [26], also known as lottery contests [8]. In particular, [9] shows that if every player uses any no-regret bidding algorithm, then each player’s average utility converges to their stage-game NE utility. [12] proves that under a specific bidding rule used by all agents, the sequence of actions converges to a NE of the stage game. [8] establishes convergence to this equilibrium when all agents employ fictitious-play updates. On the other hand, we study the repeated Kelly game with a general class of utilities that include logarithmic ones. I-A Contributions Our contributions are summarized as follows: 1. We show that a practical scenario of interest induces a repeated Kelly game with logarithmic utilities. 2. We derive a tractable sufficient condition ensuring that the stage game satisfies Rosen’s Diagonal Strict Concavity (DSC) with some vector ≻ r 0 ( r-DSC) [1], equivalently, r-monotonicity, and thus admits a unique Nash equilibrium. The condition reduces to verifying negativity of a scalar function, and we show it holds for logarithmic utilities. 3. For repeated Kelly games satisfying our sufficient r-DSC condition, and with utilities that differ only by multiplicative factors, we prove convergence when all agents use either Online Gradient Descent (OGD) or Dual Averaging with a quadratic regularizer (DAQ). 4. We establish convergence of best-response dynamics in the repeated Kelly game under logarithmic utilities. 5. We conduct extensive numerical simulations to validate our theoretical results, and complement them with additional scenarios in which agents run heterogeneous learning dynamics. We provide more details about our contributions. Rosen’s r r-DSC and uniqueness of the Nash equilibrium. A standard way to establish DSC is to show that a certain n×n× n matrix (with n the number of agents) is negative definite over the action set. In general, checking negative definiteness requires (n2)O(n^2) memory and (n3)O(n^3) time. In contrast, Theorem 2 exploits the structure of the repeated Kelly game to reduce this verification to (n)O(n) time and (1)O(1) memory. This tractable condition also enables proving that there exists a vector r for which r-DSC holds under logarithmic utilities. Moreover, proving DSC extends prior uniqueness guarantees of the NE to arbitrary convex action sets, which accommodates budget constraints and Kelly mechanisms with general weighting functions. Convergence of no-regret learning to the NE. Previous results show that convergence of OGD is guaranteed when the stage game satisfies r-DSC for some > r> 0 [33], whereas convergence of DAQ requires the stronger condition 1-DSC [23]. Under our r-DSC sufficient condition—which holds for logarithmic utilities—convergence of OGD follows immediately. However, these previous results impose a common learning rate across agents, and our 1-DSC sufficient condition holds only for homogeneous logarithmic utilities. We show in Theorem 3 that, under affine heterogeneity in utilities (e.g., utilities share the same logarithmic form but differ by agent-specific multiplicative factors), OGD still converges to the stage-game NE when agents use regret-optimal learning rates. Under the same heterogeneity model, Theorem 4 further establishes that, assuming our r-DSC sufficient condition (for some > r> 0), DAQ also converges under personalized regret-optimal learning rates. Convergence of best response dynamics. When agents use best response dynamics, we model the iterates of agents as fixed point iterations. We then derive closed form expressions of the Jacobian of the fixed point operator, and we prove that it is a contraction. Leveraging this, Theorem 5 proves convergence of the system to the NE of the stage game and shows that the convergence speed is linear. Numerical simulations. We simulate the bidding algorithms under both homogeneous dynamics, where agents use the same update rule, and heterogeneous dynamics, where two update rules coexist in the population. Under homogeneous dynamics, the simulations confirm our theoretical convergence results to the stage game NE, and indicate that, in terms of both convergence speed and time-average utility, BR performs best, followed by OGD, and then DAQ. Under heterogeneous dynamics, the results suggest that convergence to the stage game NE may fail. However, the resulting time-average utilities remain similar across algorithms and close to the NE ones, with BR consistently better in the considered settings. I-B Paper outline The rest of the paper is organized as follows. Section I formally introduces the Kelly mechanism and the induced game. Section I derives the repeated Kelly game with α-fair utilities for bandwidth allocation in wireless networks, presents the proposed bidding algorithms, and establishes their convergence guarantees. Section IV complements the theoretical results with numerical simulations. Section V concludes the paper. I Problem Formulation We consider a repeated allocation of a unit-sized divisible resource among n agents over T rounds according to the general allocation mechanism proposed in [17], which extends the Kelly mechanism introduced in [15]. Bidding. At each step t, each agent i submits a bid bi,tb_i,t that must be at least a fixed positive constant ϵ~i ε_i, i.e., bi,t≥ϵ~i>0b_i,t≥ ε_i>0. It must also respect the budget constraint, i.e., bi,t≤c~ib_i,t≤ c_i, where c~i c_i is the budget of agent i at each round t. This bid is based on previously submitted bids 1,…,t−1 b_1,…, b_t-1, where s=(bi,s)i∈ℐ b_s=(b_i,s)_i and ℐI is the set of agents. Allocation: Based on the bids of each round t, the resource owner allocates fractions xi,t(t)x_i,t( b_t) of the resource according to xi,t(t)=wi(bi,t)∑j=1nwj(bj,t)+δ,if wi(bi,t)>0,0,otherwise, x_i,t( b_t)= cases w_i(b_i,t) _j=1^nw_j(b_j,t)+δ,&if w_i(b_i,t)>0,\\ 0,&otherwise, cases (1) where wi:R+→R+w_i:R^+ ^+ are continuous, increasing functions governing how resources are distributed, and δ≥0δ≥ 0 is a reservation parameter [17]. If wiw_i is the identity function, this mechanism reduces to the classic Kelly mechanism. Each agent i has a valuation function Vi:[0,1]→R≥0nV_i:[0,1] _≥ 0^n, where Vi(xi)V_i(x_i) quantifies monetary benefit of acquiring a fraction xix_i of the resource. The utility of agent i at each step t is determined by the function φi _i, defined as the value the agent derives from the allocated fraction minus the payment, i.e., φi(t)=Vi(xi,t(t))−bi,t _i( b_t)=V_i(x_i,t( b_t))-b_i,t. The objective of each agent is devise an online bidding strategy bi,1,…,bi,Tb_i,1,…,b_i,T to maximize their aggregate utility, i.e., ∑t=1Tφi(t) _t=1^T _i( b_t). Following [17], define the change of variable zi,t=wi(bi,t)z_i,t=w_i(b_i,t), and the function pi:R+→R+p_i:R^+ ^+ as the inverse of wiw_i, i.e., pi(zi)wi−1(zi)p_i(z_i) w_i^-1(z_i). We refer to pip_i as the payment function for agent i. Under this change of variable, the allocation rule and the utility function become, xi,t(t)=zi,t∑j=1nzj,t+δif zi,t>0,0otherwise. x_i,t( z_t)= cases z_i,t _j=1^nz_j,t+δ&if z_i,t>0,\\ 0&otherwise. cases (2) φi()Vi(xi())−pi(zi). _i( z) V_i(x_i( z))-p_i(z_i). (3) Note that both formulations are equivalent in the sense that the allocated fraction corresponding to a given payment is the same in each setting. In this paper, we will focus on the second formulation using z. When agents are aware that the Kelly mechanism governs resource allocation, the interaction between them forms a competitive repeated game. We define G as the stage game arising from this competition, where the set of players is ℐI with utility functions =(φi)i∈ℐ =( _i)_i and action space constrained by budgets, denoted ℛR, and given by the cartesian product of ℛiR_i for i∈ℐi , where ℛi[ϵi,ci]R_i [ _i,c_i], where ϵi=pi−1(ϵ~i) _i=p_i^-1( ε_i) and ci=pi−1(c~i)c_i=p_i^-1( c_i). We make the following assumptions about the functions ViV_i and pip_i. Assumption 1. Over the domain [0,1][0,1], ViV_i is strictly increasing, concave, and twice continuously differentiable (Vi∈2([0,1])V_i ^2([0,1])). Over the domain R≥0nR^n_≥ 0, pip_i is convex, increasing with respect to ziz_i for any i, and twice continuously differentiable, i.e., ∈2(R≥0n) p ^2(R^n_≥ 0). Note that the above assumption is standard [17, 14]. Moreover, it is natural for ViV_i and pip_i to be increasing. Agents gain larger utility from receiving a larger share of the resource. Under Assumption 1, the utility function φi _i is concave with respect to the i-th component and thus the best response operator is a function, that we denote as BR:Rn↦RnBR:~R^n ^n. Note that G is an aggregative game because the utility function of each agent in (3) depends only on their own bid and on the sum of the bids of others. Thus, by abuse of notation, we can write φi(zi,z−i)=φi(zi,si()) _i(z_i,z_-i)= _i(z_i,s_i( z)) such that si()∑jizj+δs_i( z) _j≠ iz_j+δ and (zi,−i)(z_i, z_-i) denotes the vector where agent i submits a bid ziz_i, while the other agents submit bids −i z_-i. The best response of a player i, denoted BRi:R+↦R+BR_i:R_+ _+, is defined as, BRi(s)=argmaxzi∈ℛiφi(zi,s), _i(s)= _z_i _i _i(z_i,s), (4) and it holds that BR()=(BRi(si()))i∈[n]BR( z)=(BR_i(s_i( z)))_i∈[n]. Definition 1 (Nash Equilibrium). A strategy profile ∗=(z1∗,z2∗,…,zn∗)∈ℛ z^*=(z_1^*,z_2^*,…,z_n^*) is a Nash Equilibrium (NE) of G if and only if, for every player i∈ℐi , φi(zi∗,−i∗)≥φi(zi,−i∗)∀zi∈ℛi _i(z_i^*, z_-i^*)≥ _i(z_i, z_-i^*) ∀ z_i _i (5) As a consequence of Assumption 1, the function φi _i is concave in its i-th component and twice continuously differentiable on R≥0nR_≥ 0^n, and the actions set ℛR is non empty, closed, bounded, and convex. Existence of a Nash Equilibrium (NE) of the game G follows by [1, Thm. 1]. Theorem 1. The set of Nash equillibria of G, denoted NE()NE(G) is non-empty, i.e., NE()∅NE(G)≠ . Notation. We use V˙i(⋅) V_i(·) and V¨i(⋅) V_i(·) to denote the first and second derivatives of ViV_i, respectively. We use a similar notation for pip_i. We use ∂jφi _j _i to designate the partial derivative of φi _i with respect to the bid of agent j, and ∂j,k2φi _j,k^2 _i to designate the second order mixed derivatives of ϕφ with respect to the bid of agents j and k. I Repeated Kelly Game I-A Motivation: Bandwidth allocation in wireless networks Figure 2: Bandwidth Allocation between tenants and users In this section, we show how a repeated Kelly game with logarithmic valuations ViV_i arises in bandwidth allocation among multiple tenants (e.g., virtual operators or service providers), each serving its own set of users. Over rounds t∈1,…,Tt∈\1,…,T\, an infrastructure provider allocates a total bandwidth B according to the Kelly mechanism; given bids zj(t)z_j(t), tenant j receives bandwidth: Bj(t)=zj(t)∑k∈ℐzk(t)+δ, B_j(t)= z_j(t) _k z_k(t)+δ, (6) where ℐI denotes the set of tenants and δ≥0δ≥ 0. Within round t, time is divided into slots. At each slot, tenant j schedules exactly one user from its set ℐjI_j. Let Sjτ(t)∈ℐjS_j^τ(t) _j denote the scheduled user at slot τ. When a user i is scheduled, its transmission rate, denoted rj,iτ(t)r_j,i^τ(t), is proportional to the allocated bandwidth, rj,iτ(t)=γj,iτ(t)Bj(t)(Sjτ(t)=i), r_j,i^τ(t)= _j,i^τ(t)B_j(t) 1 (S_j^τ(t)=i ), (7) where γj,iτ(t)>0 _j,i^τ(t)>0. For instance in [6], γj,iτ(t)=ln(1+pj,ihj,iτ(t)N0) _j,i^τ(t)= (1+ p_j,ih_j,i^τ(t)N_0 ), where pj,ip_j,i is the transmission power, hj,iτ(t)h_j,i^τ(t) is the channel state, and N0N_0 is the noise power111For the sake of simplicity, we consider a basic AWGN channel model and a single user scheduler; with due modifications, same game extends to more advanced channels and multi-user scheduling.. A standard objective in this setting is the Proportional-fair metric [16]. Optimizing this objective enables balancing the overall throughput and fairness across users. We use PropFairj(t)PropFair_j(t) to denote the proportional fair metric of tenant j at round t, and it is expressed as, PropFairj(t) _j(t) ∑i∈ℐjln(∑τrj,iτ(t)) _i _j ( _τr_j,i^τ(t) ) (8) =Njln(Bj(t))+∑i∈ℐjln(∑τγj,iτ(t)(Sjτ(t)=i)), =N_j (B_j(t))+ _i _j ( _τ _j,i^τ(t) 1 (S_j^τ(t)=i ) ), (9) where NjN_j is the number of users served by tenant j, i.e., Nj=|ℐj|N_j=|I_j|. This decomposition makes the roles of bidding and scheduling transparent: the term Njln(Bj(t))N_j (B_j(t)) depends only on the bidding process, while the second term is controlled by the scheduling policy and channel states, and is independent of the bids. Using the quasi-linear utility model [14], the utility of tenant j at round t writes φj(zj(t),z−j(t))= _j(z_j(t),z_-j(t))= Njln(zj(t)B∑k∈ℐjzk(t)) N_j ( z_j(t)B _k _jz_k(t) ) +∑i∈ℐjln(∑τγj,iτ(t)(Sjτ(t)=i))−zj. + _i _j ( _τ _j,i^τ(t) 1 (S_j^τ(t)=i ) )-z_j. (10) Therefore, the bidding interaction induced by the scheme just described is a repeated Kelly game with logarithmic ViV_i’s. I-B Single-Agent Formulation of the Online Bidding Problem At round t of the repeated Kelly game, agent i faces uncertainty about others’ aggregate bid si((t))=δ+∑jizj(t)s_i( z(t))=δ+ _j≠ iz_j(t). Before bidding, agent i only knows the history (si((1)),…,s−i((t−1)))(s_i( z(1)),…,s_-i( z(t-1))). A bidding algorithm iA_i maps this history to a bid zii(t)∈ℛiz_i^A_i(t) _i, and earns the payoff φi(zii(t),si((t))) _i(z_i^A_i(t),s_i( z(t))). Under Assumption1, this yields an Online Convex Optimization (OCO) [11] problem: in each of the T rounds, the agent chooses zii(t)∈ℛiz_i^A_i(t) _i, then a concave reward function uit:ℛi↦Ru_i^t:R_i , defined as uit(zi)ϕi(zi,si((t)))u_i^t(z_i) _i(z_i,s_i( z(t))) is revealed, and the agent receives uit(zii(t))u_i^t (z_i^A_i(t) ). The objective is then to maximize the aggregate reward over rounds. In this framework, the main performance metric of an algorithm iA_i is the regret, denoted as RegT(i)(i)Reg_T^(i)(A_i), and defined as the gap between the cumulative reward of the best fixed bid in hindsight and the agent’s cumulative reward, i.e., RegT(i)(i)maxzi∈ℛi∑t=1Tuit(zi)−∑t=1Tuit(zii(t)). _T^(i)(A_i) _z_i _i _t=1^Tu_i^t(z_i)- _t=1^Tu_i^t (z_i^A_i(t) ). (11) Define the constants DiD_i and GiG_i as upper bounds on the diameter of the decision set ℛiR_i, and the derivatives of uitu_i^t’s for any t, i.e., Di≥ci−ϵi,Gi≥sup∈ℛ|∂iφi(zi,si())|. D_i≥ c_i- _i, G_i≥ _ z | _i _i(z_i,s_i( z)) |. (12) Because φi _i is continuous over the closed set ℛR, the constants DiD_i and GiG_i exists. Thus, standard OCO methods achieve sublinear regret, RegT(i)=o(T)Reg_T^(i)=o(T). Consequently, for any sequence of opponent aggregates si((t))s_i( z(t)), the agent’s time-average reward approaches that of the best fixed bid appearing in (11). I-C Bidding algorithms We consider four bidding algorithms. Two of them are adaptations of classical no-regret methods to the repeated Kelly game, namely Online Gradient Descent (OGD) [35] and Dual Averaging (DA) [21], an instance of the Follow-The-Regularized-Leader (FTRL) family of algorithms. The third algorithm is an instance of Regularized-Robbins–Monro (RRM) family of algorithms, recently studied in the context of repeated games [23, 22], and encompassing DA as a special case. The fourth algorithm is a myopic best-response scheme. OGD, DA, and RRM are first-order methods: they only require the derivative of the stage utility with respect to the agent’s bid. Specifically, at each step t, algorithm i∈OGD,DA,RRMA_i∈\ OGD, DA, RRM\ for agent i uses the gradient of the utility function evaluated at its current bid zii(t)z_i^A_i(t), namely, gt(i),i∂iuit(zii(t))=φi(zii(t),si((t))). g_t^(i),A_i _iu_i^t(z_i^A_i(t))= _i(z_i^A_i(t),s_i( z(t))). (13) The algorithm also employs a learning rate (or step-size) ηt(i)>0 _t^(i)>0 that is tuned at each step t. Online Gradient Descent OGD. When i=OGDA_i= OGD, agent i updates their bid by moving along the gradient/derivative of the reward function uitu_i^t at the current bid, then projects back to the feasible set ℛiR_i (minimum bid and budget constraints). Formally, the update at step t+1t+1 is given by, ziOGD(t+1)=(ziOGD(t)+ηt+1(i)gt(i),OGD)ℛi, z_i OGD(t+1)=_R_i (z_i OGD(t)+ _t+1^(i)g_t^(i), OGD ), (14) where ℛi_R_i is the euclidean projection over ℛiR_i, which reduces to clipping, (z)ℛi=max(min(z,ci),ϵi)_R_i(z)=~ ( (z,c_i), _i). Taking ηt(i)=Di/(Git) _t^(i)=D_i/(G_i t), yields, RegT(i)(OGD)≤32GiDiTReg_T^(i)( OGD)≤~ 32G_iD_i T [11][Thm. 3.1]. Similar regret guarantees hold when ηt(i) _t^(i) is constant over time; taking ηt(i)≡η(i)=Di/(GiT) _t^(i)≡η^(i)=D_i/(G_i T) leads to, RegT(i)(OGD)≤GiDiTReg_T^(i)( OGD)≤ G_iD_i T [25]. If uitu_i^t’s are γi _i–strongly convex on ℛiR_i, then choosing a more aggressive learning rate ηt(i)=1/(γit) _t^(i)=1/( _it) yields, RegT(i)(OGD)≤Gi2γi(1+logT)Reg_T^(i)( OGD)≤ G_i^2 _i (1+ T ). Dual Averaging (DA). This algorithm employs a regularizer, i.e., a continuous strongly convex function, hi:ℛi↦Rh_i:R_i . Let g1:t(i),DAg_1:t^(i), DA designates the sum of the gradients up to time t, i.e., g1:t(i),DA=∑s=1tgs(i),DAg_1:t^(i), DA= _s=1^tg_s^(i), DA. DA’s update selects the bid z that maximizes (z∗g1:t(i),DA−1ηt(i)hi(z)) (z*g_1:t^(i), DA- 1 _t^(i)h_i(z) ). In particular, if hi(z)=z2/2h_i(z)=z^2/2, then the update, denoted DAQ, is given by, ziDAQ(t+1) z_i DAQ(t+1) =(ηt+1(i)g1:t(i),DAQ)ℛi. =_R_i ( _t+1^(i)g_1:t^(i), DAQ ). (15) This update is also known as the lazy version of OGD, while (14) is known as the agile one. Taking an adaptive learning rate ηt(i)=Di/(2Git) _t^(i)=D_i/(2G_i t) yields, RegT(i)(DAQ)≤2GiDiTReg_T^(i)( DAQ)≤~ 2G_iD_i T [21][Sec. 3.1]. If the number of rounds T is apriori known, then taking ηt(i)=Di/(GiT) _t^(i)=D_i/(G_i T) yields, RegT(i)(DAQ)≤GiDiTReg_T^(i)( DAQ)≤ G_iD_i T [21][Sec. 3.2]. Remark 1. In general, OGD and DAQ require an upper bound GiG_i on the gradient of the agent’s utility (see (12)), for tuning ηt(i) _t^(i). The constant GiG_i depends on the budgets of the other players and may therefore be unknown in practice. In the case of logarithmic utilities, i.e., Vi(⋅)=ailn(⋅)+diV_i(·)=a_i (·)+d_i, and pip_i is the identity function, we can write, |∂iφi()|=|ai(1zi−1∑jzj+δ)−1|≤aizi+1≤aiϵi+1. | _i _i( z) |= |a_i ( 1z_i- 1 _jz_j+δ )-1 |≤ a_iz_i+1≤ a_i _i+1. (16) for every ∈ℛ z . Thus taking Gi=aiϵi+1G_i= a_i _i+1 provides a bound that is independent of the other agents’ budgets, which simplifies the use of these bidding algorithms in practice. Indeed, the learning rate for each agent i, using either OGD or DAQ, can be tuned as ηt(i)=(ciϵiaiT) _t^(i)=O ( c_i _ia_i T ), leading to a regret (ciaiϵiT)O ( c_i\,a_i _i T ). Regularized-Robbins Monro (RRM). In the context of the repeated Kelly, an agent i using RRM maintains a cumulative weighted sum of gradients at each step t, denoted yiRRM(t)y_i RRM(t), which is then converted to the bid for that iteration, denoted as ziRRM(t)z_i RRM(t). Initially, yiRRM(0)=0y_i RRM(0)=0. At any step t≥1t≥ 1, yiRRM(t)=yiRRM(t−1)+ηt(i)gt(i),RRM,ziRRM(t)=Qi(yiRRM(t−1)):Qi(y)argmaxzi∈ℛi(ziy−hi(zi)), cases&y_i RRM(t)=y_i RRM(t-1)+ _t^(i)g_t^(i), RRM,\\ &z_i RRM(t)=Q_i(y_i RRM(t-1)):\\ &Q_i(y) *arg\,max_z_i _i (z_iy-h_i(z_i) ), cases (17) where hi:ℛi↦Rh_i:R_i is a continuous and KiK_i-strongly convex function for some Ki>0K_i>0. In particular, if hi(z)=z22λih_i(z)= z^22 _i, then the update, denoted RMQ, is given by, ziRMQ(t)=(λiyiRMQ(t))ℛi, z_i RMQ(t)=_R_i ( _iy_i RMQ(t) ), (18) In particular, if ηt(i)η^(i)_t is constant over time and λi=1 _i=1 for all agents, then RMQ and DAQ yield the same update. Thus RMQ in this case has sublinear regret guarantees. Best-response (BR). When i=BRA_i= BR, at each round t, agent i selects the bid that maximizes their payoff function φi _i, when the aggregate bid of the other agents is equal to its value in the previous round, si((t−1))∑jizjs_i( z(t-1)) _j≠ iz_j. Formally, ziBR(t)=BRi(si(BR(t−1))). z_i^BR(t)=BR_i (s_i ( z BR(t-1) ) ). (19) While BR lacks in general the no-regret guarantees of DAQ and OGD, it is simpler to implement: it uses the observed aggregate si(BR(t−1))s_i ( z BR(t-1) ) and the agent’s own constraints, and requires no knowledge or estimation of other agents’ budgets. Remark 2. When the ViV_i’s are logarithmic, i.e., Vi(⋅)=ailn(⋅)+diV_i(·)=a_i (·)+d_i with ai>0a_i>0, and pi(z)=zp_i(z)=z, straightforward calculations yield a closed-form expression for the best response operator, BRi(s)=(−s+s2+4ais2)ℛi.BR_i(s)=_R_i ( -s+ s^2+4a_i\,s2 ). (20) More generally, [20] derives closed form expressions for the best-response operator for ViV_i’s of the α-fair type with α∈0,1,2α∈~\0,1,2\. I-D Convergence guarantees In this section, we focus utilities of the form, namely Vi(⋅)=aiV(⋅)+diV_i(·)=a_iV(·)+d_i with ai>0a_i>0. Our results hold in particular when V(⋅)=ln(⋅)V(·)= (·). This model is motivated by the network-slicing setting described in Section I-A. We first provide a sufficient condition for the stage game G to satisfy Strong Diagonal Strict Concavity (SDSC), which implies Rosen’s Diagonal Strict Concavity [1], or equivalently monotonicity [34]. As a consequence, the Nash equilibrium is unique. This property also serves as a key ingredient to establish convergence to the equilibrium under OGD and DAQ dynamics. Finally, we prove convergence of BR via a contraction argument. For a vector ∈R>0n r _>0^n, SDSC is defined in terms of the n×n× n matrix () H_ r( z), whose (i,j)(i,j)-entry is given by, (())i,jri∂i,j2φi()+rj∂j,i2φj(), ( H_ r( z))_i,j r_i\,∂^2_i,j _i( z)+r_j\,∂^2_j,i _j( z), (21) where the partial derivative is taken with respect to the actions of agent i and j, i.e., ziz_i and zjz_j, respectively. Definition 2 (Strong Diagonal Strict Concavity). The game G satisfies Strong Diagonal Strict Concavity in r if and only if the matrix () H_ r( z) is negative definite for all ∈ℛ z , max:‖=1()<0. _ v:\| v\|=1 \ v H_ r( z) v \<0. (22) In this case, we write that G satisfies () SDSC( r). SDSC appears in Rosen’s paper [1] as a sufficient condition for diagonal strict concavity, or equivalently for the game to be monotone [34]. This assumption is particularly useful for analyzing more general Kelly-type games with coupled action sets and for proving convergence of continuous-time dynamics. SDSC is also one of the main conditions for the convergence of RRM updates in a multi-agent setting to a NE [23, 22]. We prove in Theorem 2 that the Kelly game satisfies SDSC when utilities scale logarithmically with the allocated resource. First, we introduce the necessary notation. Define the functions fif_i, gig_i, and ψ, _ r, V as fi(x)=(1−x)2V¨i(x)−2(1−x)V˙i(x), f_i(x)=(1-x)^2 V_i(x)-2(1-x) V_i(x), (23) gi(x)=−x(1−x)V¨i(x)+(2x−1)V˙i(x), g_i(x)=-x(1-x) V_i(x)+(2x-1) V_i(x), (24) ψ,()(∑i∈ℐrigi(xi)2ki(xi))(∑i∈ℐ1riki(xi)), _ r, V( x) ( _i r_ig_i(x_i)^2k_i(x_i) ) ( _i 1r_ik_i(x_i) ), (25) where ki(x)=gi(x)−fi(x)+δ2Lik_i(x)=g_i(x)-f_i(x)+δ^2L_i and Li=minzi∈ℛip¨i(zi)L_i= _z_i _i p_i(z_i). Further define the set =>:∑i∈ℐxi≤∑k∈ℐck∑k∈ℐck+δ =\ x> 0:\; _i x_i≤ _k c_k _k c_k+δ\. Theorem 2. The following holds, 1. If there exists a vector > r> 0 such that ψ,() _ r, V( x) is strictly smaller than 11, then G is () SDSC( r). Formally, ∃>:sup∈ψ,()<1⟹ is (). ∃ r> 0:\; _ x∈ _ r, V( x)<1 is SDSC( r). (26) 2. If Vi(⋅)=ailn(⋅)+diV_i(·)=a_i (·)+d_i, then the condition (26) is satisfied for ri=1/air_i=1/a_i. The proof of Theorem 2 is presented in the supplementary material. In general, a negative definiteness numerical test for an n×n× n matrix requires (n3)O(n^3) time and (n2)O(n^2) memory. Theorem 2 exploits the structure of the matrix () H_ r( z) in the Kelly game to significantly reduce the verification, for a fixed z, to (n)O(n) time and (1)O(1) memory via the condition (26). Moreover, this reduction turns SDSC test into bounding the maximum of a closed-form function, which is easier to deal with analytically; in particular, it enables the proof of SDSC when the ViV_i’s are logarithmic. Corollary 1. The condition (26) is sufficient for the uniqueness of the Nash equilibrium of G. We denote this unique equilibrium as ∗ z^*. Corollary 1 follows directly from Theorem 2 using [1]. Uniqueness of the Nash equilibrium has been established under various conditions: when the ViV_i’s satisfy Assumption 1 with identity payment function and no budget constraints [14, Thm. 2.2], or more generally when the pip_i’s satisfy Assumption 1 but are identical across agents [17, Prop. 2]. These results do not account for constraints. Under budget constraints, uniqueness was shown in [7, Thm. 1] for a common linear weighting function, while [31] allows heterogeneous linear coefficients but no budget constraints. By contrast, Theorem 1 and Corollary 1 establish uniqueness for logarithmic ViV_i, admits any pip_i satisfying Assumption 1 (possibly heterogeneous), and incorporates budget constraints, thereby unifying and extending the above results for logarithmic ViV_i. Leveraging the SDSC property of the game G, Theorem 3 establishes the convergence of OGD to the unique NE when the utilities scale logarithmically in the allocated resource. Theorem 3 (Convergence of OGD). Assume that the condition (26) holds and that the ViV_i’s are of the form Vi(⋅)=aiV(⋅)+diV_i(·)=a_iV(·)+d_i, with ai>0a_i>0 and V satisfying Assumption 1. If each agent updates their bid using OGD, i.e., i=OGDA_i= OGD, ∀i∈ℐ∀ i , with ηt(i)=αiηt(0) _t^(i)= _i _t^(0), αi>0 _i>0, ∑t=1∞ηt(0)=∞ _t=1^∞ _t^(0)=∞, and ∑t=1∞(ηt(0))2<∞ _t=1^∞ ( _t^(0) )^2<∞, then the sequence of play OGD(t)=(ziOGD(t))i∈ℐ z OGD(t)=(z_i OGD(t))_i converges to the unique NE of the stage game, i.e., limt→∞OGD(t)=∗ _t→∞ z OGD(t)= z^*. Proof: Let ∗ r^* be the vector for which the condition (26) is satisfied. If ηt(i)=ηt(0) _t^(i)=η^(0)_t, then by Theorem 2 the game G is ∗ r^*-monotone, so the convergence of OGD follows directly from [34][Thm. 4]. To extend this result to heterogeneous learning rates ηt(i)=αiηt(0) _t^(i)= _i _t^(0), consider the auxiliary game ~ G with modified utilities ϕ~i=αiϕi φ_i= _i _i. The following holds, • The OGD updates in the game ~ G with η~t(i)=ηt(0) η_t^(i)= _t^(0) coincide with the OGD updates in the game G with ηt(i)=αiηt(0) _t^(i)= _i _t^(0). • The games ~ G and G share the same set of Nash equilibria. • If G is ∗ r^*-monotone, then the game ~ G is r-monotone with ri=ri∗/αir_i=r_i^*/ _i. Combining the above statements with Theorem 2, we deduce that ~ G is r-monotone with ri=ri∗/αir_i=r_i^*/ _i. Thus, applying [34][Thm. 4] to ~ G yields the desired convergence result, which completes the proof. ∎ The step-size condition in Theorem 3 is satisfied whenever ηt∝t−β _t t^-β with β∈(1/2,1]β∈(1/2,1]. For logarithmic utilities, the induced optimization problem is convex, and the standard choice is ηt∝t−1/2 _t t^-1/2, which yields the usual O(T)O( T) regret but does not satisfy this condition. A simple workaround in the merely convex case is to take β close to 1/21/2, which preserves sublinear regret while complying with β>1/2β>1/2. Moreover, since each agent’s action set is a compact interval [ϵi,ci][ _i,c_i] with ϵi>0 _i>0, the logarithmic utilities are in fact strongly concave on this domain, with parameter γi>0 _i>0 that goes to 0 when ϵi→0 _i→ 0. In this strongly concave setting, one may take ηt∝1/t _t 1/t (corresponding to β=1β=1), which both satisfies the corollary’s condition and yields the standard logarithmic regret guarantees. Now we turn our attention to the analysis of DAQ and RMQ. Theorem 4 shows that RMQ converges to the NE of the stage game. Moreover, when the utilities scale logarithmically in the allocated resource, the theorem quantifies the convergence gap of DAQ to the NE, via the metric Gap¯T() Gap_T(A), used in [23], and defined as, Gap¯T()=1T∑t=1TGap((t)): Gap_T(A)= 1T _t=1^TGap ( z^A(t) ): (27) Gap()=∑i∈ℐ∂iφi()ai(zi∗−zi). ( z)= _i _i _i( z)a_i (z^*_i-z_i ). (28) Indeed, when the ViV_i’s are logarithmic, the game G is (∗) SDSC( r^*) with ri∗=1/air_i^*=1/a_i, as shown in Theorem 2. Thus, Gap()>0Gap( z)>0 for all ∗ z≠ z^*, with equality if and only if =∗ z= z^* [23]. Theorem 4 (Convergence of RMQ and DAQ). Assume that the condition (26) holds and that the ViV_i’s are of the form Vi(⋅)=aiV(⋅)+diV_i(·)=a_iV(·)+d_i, with ai>0a_i>0 and V is function that satisfies Assumption 1. Further assume that ϵi=ϵ _i=ε for all agents. The following holds, 1. If all agents update their bids according to RMQ, i.e., ∀i∀ i, i=RMQA_i= RMQ, ηt(i)=αiηt(0) _t^(i)= _i _t^(0), αi>0 _i>0, and ∑t=1∞(ηt(0))2/∑t=1∞ηt(0)→0 _t=1^∞( _t^(0))^2/ _t=1^∞ _t^(0)→ 0, then the vector of bids RMQ(t) z RMQ(t) converges to the unique NE of the stage game, i.e., limt→∞RMQ(t)=∗ _t→∞ z RMQ(t)= z^*. 2. If all agents update their bids according to DAQ and V(⋅)=ln(⋅)V(·)= (·), with ηt(i)=ϵciaiT _t^(i)= ε c_ia_i T, pip_i is the identity function, and ai≥ϵa_i≥ε, then Gap¯T(DAQ)≤12ϵT(∑i∈ℐci+4|ℐ|maxi∈ℐci). Gap_T( DAQ)≤ 12ε T ( _i c_i+4|I|\, _i c_i ). (29) Proof: Let ∗ r^* be the vector for which the condition (26). We first prove the convergence of RMQ in (18). When for all agents, ηt(i)=ηt(0) _t^(i)= _t^(0), and ∑t=1∞(ηt(0))2/∑t=1∞ηt(0)→0 _t=1^∞( _t^(0))^2/ _t=1^∞ _t^(0)→ 0, convergence of the bids vector, when all agents use RRM—with RMQ as particular case—is guaranteed by [23][Thm. 4.6] under two conditions: 1) The game G is () SDSC( 1), and 2) For any player i and for any sequence yn⊂R\y_n\ such that Qi(yn)→ℓQ_i(y_n)→ , Fi(ℓ,yn)→0F_i( ,y_n)→ 0, where FiF_i is what is called the Fenchel conjugate in [23], and defined as, Fi(ℓ,y)=hi∗(y)−h~i(y,ℓ)F_i( ,y)=h^*_i(y)- h_i(y, ), where hi∗(y)=maxz∈ℛih~i(y,z)h^*_i(y)= _z _i \ h_i(y,z) \, and hi∗h_i^* is the convex conjugate of hih_i. It is easy to prove that the second condition holds for quadratic regularizers, i.e., any h such that h(z)=z22λh(z)= z^22λ, and λ>0λ>0 [19]. Thus, when ∗= r^*= 1 convergence follows directly from [23][Thm. 4.6]. To extend this result to arbitrary ∗> r^*> 0 and when ηt(i)=αiηt(0) _t^(i)= _i _t^(0), we define the payoff functions ϕ~i=ri∗ϕi φ_i=r_i^* _i, and the corresponding stage game ~ G. The following holds, • The games ~ G and G share the same set of Nash equilibria. • If the game G is (∗) SDSC( r^*), then the game ~ G is () SDSC( 1). • RMQ updates with η~t(i)=ηt(0) η_t^(i)= _t^(0) and regularizer h~i(z)=z22λ~i h_i(z)= z^22 λ_i, with λ~i=λiαiri∗ λ_i= _i _ir_i^* in the repeated ~ G, coincides with RMQ updates in the repeated G with ηt(i)=αiηt(0) _t^(i)= _i _t^(0), and hi(z)=z22λih_i(z)= z^22 _i. The statements above combined with Theorem 2 yields the convergence of the RMQ updates with homogeneous η~t(i) η_t^(i) regularizers h~i h_i in the repeated ~ G. This implies the convergence of RMQ updates in G with heterogeneous ηt(i) _t^(i)’s. We now prove the gap bound for DAQ when V(⋅)=ln(⋅)V(·)= (·), when ηt(i)=ϵciaiT _t^(i)= ε c_ia_i T. By Theorem 2, ri∗r_i^* is equal to 1/ai1/a_i for logarithmic V. Moreover, because ηt(i) _t^(i) is constant over time, RMQ, with λi=1 _i=1, and DAQ updates coincide. Similarly to the convergence proof of RMQ, we consider the proxy RMQ updates in ~ G with η~t(i)=ηt(0)=1T η_t^(i)= _t^(0)= 1 T, for any agent i, h~i(z)=z22λ~i h_i(z)= z^22 λ_i, λ~i=αiai λ_i= _ia_i, and αi=ϵciai _i= ε\,c_ia_i. Applying [23, Thm. 6.2] and [23, Cor. 6.3] to these RMQ updates in ~ G yields, Gap¯T(DAQ)≤1T(~+G~22K~), Gap_T( DAQ)≤ 1 T ( + G^22 K ), (30) where ~max∈ℛ∑ih~i(zi)−min∈ℛ∑ih~i(zi), _ z _i h_i(z_i)- _ z _i h_i(z_i), (31) K~mini∈ℐ1λ~i,G~sup∈ℛ‖(∂iφ~i())i∈ℐ‖22. K _i 1 λ_i, G _ z \| ( _i _i( z) )_i \|_2^2. (32) We bound these quantities as follows, G~2≤∑i∈ℐ1ai2Gi2≤∑i∈ℐ4ai2ai2ϵ2=4|ℐ|ϵ2, G^2≤ _i 1a_i^2G_i^2≤ _i 4a_i^2a_i^2ε^2= 4|I|ε^2, (33) 1K~=maxiλ~i=ϵmaxici,and ~≤12ϵ∑i∈ℐci2. 1 K= _i λ_i=ε _ic_i, ≤ 12ε _i c_i^2. (34) Plugging these bounds in (30) yields the target result, which finishes the proof.∎ While DAQ comes with standard no-regret guarantees and can therefore be viewed as a plausible behavioral model for repeated bidding, RMQ with adaptive step-sizes (ηt(i))t( _t^(i))_t does not generally enjoy regret guarantees. Nevertheless, RMQ acts as proxy to analyze the multi-agent behavior of DAQ when the step-sizes ηt(i) _t^(i) are time-invariant; in addition, RMQ can be interpreted as a distributed procedure for computing the unique Nash equilibrium of the stage game, as shown in Theorem 4. The choice of ηt(i) _t^(i) optimizes the asymptotic dependency of the regret in the parameters problem when the budgets of other agents is unknown (see Remark 1). Under this choice of ηt(i) _t^(i), Theorem 4 provides an explicit finite-horizon bound of the deviation from equilibrium through the averaged gap Gap¯T(DAQ) Gap_T( DAQ). The established bound highlights that convergence may deteriorate when the minimum admissible bid ϵε is small, since logarithmic utilities induce large gradients near 0. Finally, budget constraints introduce additional variability in the updates, which also contributes to slower convergence. Now we study the case where all agents employ a myopic best response. This is a simultaneous best-response update: all agents revise in parallel from the last observed profile. Such parallel BR does not necessarily converge to a Nash equilibrium in general [10]. By contrast, in unilateral best-response updates, agents revise one at a time (cyclically or at random); in finite potential games, these dynamics converge to a pure Nash equilibrium [24]. Theorem 5. If Vi(⋅)=ailn(⋅)+diV_i(·)=a_i (·)+d_i, pi(z)=zp_i(z)=z, i=BRA_i= BR for all agents, and ϵi=ϵ _i=ε such that, ϵ>1n−1((n−1)2nmaxi∈ℐai−δ). ε> 1n-1 ( ( n-1)^2 n\, _i a_i-δ ). (35) then (BR(t))t( z BR(t))_t converges to the unique Nash equilibrium ∗ z^* linearly fast, i.e., ∃ρ∈(0,1)∃ρ∈(0,1): ‖BR(t)−∗‖≤ρt‖BR(0)−∗‖\| z BR(t)- z^*\|≤ρ^t\| z BR(0)- z^*\|. Proof: The best-response updates are fixed point iterations with the best-response operator BR. We prove that this operator is a contraction, which yields convergence to the unique fixed point—which is also the NE of the stage game—at linear speed. To prove that BR is a contraction, define BR~i(s)=(−s+s2+4ais)/2 BR_i(s)= (-s+ s^2+4a_is )/2 and ~()(BR~i(si()))i∈ℐ BR( z) ( BR_i(s_i( z)) )_i , so that ()=(~())ℛBR( z)=_R ( BR( z) ) (see (20)). Given that the projection map R is 11-Lipschitz, BR~i BR_i is smooth, and using the generalized mean-value theorem [4, Cor. 3.2], a sufficient condition for the best-response operator BR to be a contraction, is given by, sup∈ℛ‖BR~()‖∞<1. _ z \|J_ BR( z) \|_∞<1. (36) Direct calculations yield, (~())i,j=ζi(si()),ji,0,j=i. (J_ BR( z) )_i,j= cases _i(s_i( z)),&j≠ i,\\ 0,&j=i. cases (37) where ζi(s)=−12+s+2ai2s2+4ais _i(s)=- 12+ s+2a_i2 s^2+4a_is, and si()=∑jizj+δs_i( z)= _j≠ iz_j+δ. The function ζi _i is decreasing over R+R^+, and thus, ‖~()‖∞ \|J_ BR( z) \|_∞ =maxi∈ℐ∑jiζi(si())=maxi∈ℐ(n−1)ζi(smin). = _i _j≠ i _i\! (s_i( z) )= _i (n-1) _i (s_ ). (38) where smin(n−1)ϵ+δs_ (n-1)ε+δ. Combining this with the fact that (n−1)ζi(s)<1(n-1) _i(s)<1 is satisfied whenever, s>(n−1)2nais> ( n-1)^2 n\,a_i (see [20]), proves that (35) is indeed a sufficient condition for BR to be a contraction. This finishes the proof. ∎ Note that the lower bound on the minimum bid in (35) scales inversely with the number of agents, i.e., ϵ=(1/n)ε=O(1/n), and thus the convergence of best response dynamics is guaranteed with arbitrarily small minimum bid ϵε for large number of agents. Moreover, only (ln(1/p))O( (1/p)) iterations are needed to converge to a point whose distance from the NE is smaller than p. IV Numerical Simulations TABLE I: Homogeneous dynamics: number of convergence iterations in terms of the fixed-point residual rtr_t (threshold <10−5<10^-5) under varying γ and n. γ n BR OGDV OGDF DAQF DAQV RRMV 0 2 15 37 122 195 (rT=3.7×10−2)(r_T=3.7×10^-2) 1682 10 7 19 240 311 (rT=1.05)(r_T=1.05) 2291 20 6 20 252 330 (rT=1.73)(r_T=1.73) 2361 5 2 15 111 127 184 (rT=1.0×10−1)(r_T=1.0×10^-1) 504 10 7 40 206 274 (rT=6.8×10−1)(r_T=6.8×10^-1) 2182 20 6 1811 221 289 (rT=7.5×10−1)(r_T=7.5×10^-1) 2220 10 2 15 116 117 184 (rT=9.7×10−2)(r_T=9.7×10^-2) 498 10 8 533 185 253 (rT=4.5×10−1)(r_T=4.5×10^-1) 1604 20 8 533 194 259 (rT=4.5×10−1)(r_T=4.5×10^-1) 2062 (a) γ=0γ=0 (b) γ=5γ=5 (c) γ=10γ=10 Figure 3: Convergence speed under homogeneous dynamics and varying payoff’s heterogeneity levels. (a) Time-average payoff. (b) Instantaneous payoff. Figure 4: Agent’s payoff, γ=0γ=0. (a) BR vs. DAQF DAQ_F (αBR=10% _ BR=10\%) (b) BR vs. DAQF DAQ_F (αBR=80% _ BR=80\%) (c) BR vs. DAQF DAQ_F (αBR=90% _ BR=90\%) (d) BR vs. OGDF OGD_F (αBR=10% _ BR=10\%) (e) BR vs. OGDF OGD_F (αBR=80% _ BR=80\%) (f) BR vs. OGDF OGD_F (αBR=90% _ BR=90\%) Figure 5: Heterogeneous dynamics. In each sub-figure: instantaneous payoff (top) and bids (bottom). (a) DAQF DAQ_F vs. BR (b) OGDF OGD_F vs. BR (c) DAQF DAQ_F vs. OGDF OGD_F Figure 6: Heterogeneous dynamics: Average payoff We consider a set of agents ℐI. Each agent i’s valuation function is Vi(x)=ailnxV_i(x)=a_i x, where ai>0a_i>0 is an agent-specific parameter, and payment function pi(z)=zp_i(z)=z. Utilities heterogeneity is determined by γ by setting ai=max(a−iγ,1)a_i= (a-iγ,1), with γ∈0,5,10γ∈\0,5,10\, a=100a=100, and a budget constraint ci=c=400c_i=c=400 and ϵi=ϵ=1 _i=ε=1. We set δ=0.1δ=0.1. The number of rounds in the repeated Kelly game is T=3000T=3000, and results are averaged over 1010 independent runs with random initial bids. Agents follow one of the bidding algorithms described in Section I-C. Namely, OGD, DAQ, RRM, and BR. For OGD, DAQ, and RRM, we consider both fixed and time-varying learning rates: the fixed learning rate is η(i)=DiGiTη^(i)= D_iG_i T and the time-varying one is ηt(i)=DiGit _t^(i)= D_iG_i t. We distinguish these variants by either adding the subscripts F for fixed or V for time-varying. Our simulations include both homogeneous dynamics settings, where all agents follow the same update rule, and heterogeneous dynamics settings, where a fraction α1 _A_1 of agents use algorithm 1A_1 while the remaining agents use a different algorithm 2A_2. The objective is twofold: (1) to verify whether repeated play converges to the Nash equilibrium (NE) of the stage game, while measuring the convergence speed of the bidding algorithms, and (2) to compare their time-average payoff. To measure convergence to the NE, we use the metric rtr_t, defined as, rt‖BR((t))−(t)‖2. r_t \|BR( z(t))- z(t)\|_2. (39) Indeed, the unique NE of the stage game is the fixed point of the best-response operator, i.e., BR(∗)=∗BR( z^*)= z^*. Accordingly, when the bid profile (t) z(t) is near the NE, one expects BR((t))≈(t)BR( z(t))≈ z(t). To make payoffs comparable across agents, we normalize them to lie in [0,1][0,1]. Specifically, we define φi¯()=φi()−φminφmax−φmin _i( z)= _i( z)- _ _ - _ where φmin _ and φmax _ are the smallest and largest values of the payoff functions among all players and across all actions. We then compare the bidding algorithms using the time-average normalized payoff, i.e., 1T∑t=1Tφi¯((t)) 1T _t=1^T _i( z(t)), which matches each player’s objective of maximizing long-run payoff. The rest of this section is organized as follows; Section IV-A addresses these questions under homogeneous dynamics, whereas Section IV-B addresses them under heterogeneous dynamics. IV-A Homogeneous dynamics Table I reports, for n=|ℐ|∈2,10,20n=|I|∈\2,10,20\, the minimum number of iterations required to reach the threshold rt≤10−5r_t≤ 10^-5. The results show that repeated play with OGD, DAQF DAQ_F, RRM, and BR converges to the Nash equilibrium, in agreement with our theoretical results. In contrast, DAQV DAQ_V may fail to converge with comparable precision. In terms of convergence speed, BR is the fastest, followed by OGD and DAQF DAQ_F, while RRM converges significantly more slowly. Moreover, the convergence of BR becomes faster as the number of players increases, whereas the other bidding algorithms exhibit the opposite trend. This behavior is consistent with the (n)O(n) convergence bound established in Theorem 4. Finally, varying the heterogeneity level through γ has only a limited overall effect on convergence rates, although it slightly accelerates OGDF OGD_F, DAQF DAQ_F, and RRM. In the following experiments, we focus on a population of n=10n=10 agents. Figure 3 illustrates the evolution of the fixed-point residual rtr_t under homogeneous dynamics (OGD, DAQ, and BR) for the same values of γ. Figure 4 reports, for a representative player, both the instantaneous payoff and the time-average payoff. Since γ=0γ=0, all agents share the same payoff function, so the plotted curves are representative of any player. The figure shows that the ranking in payoff performance mirrors the ranking in convergence speed: best-response dynamics achieves faster the limit payoffs, followed by OGD, then DAQ, and finally RRM. It is interesting to observe that that, even though DAQV DAQ_V does not yet converge within the tested horizon (see Table I), it still achieves time-average payoffs comparable to its fixed-learning rate counterpart DAQF DAQ_F. By comparing Figure 3 and Figure 4(b) we note that, for both DAQV DAQ_V and RRM, reaching a moderately small rtr_t (e.g., rt<1r_t<1) is sufficient to render the instantaneous payoff close to one attained at the Nash-equilibrium. Actually, further reductions in rtr_t bring only marginal payoff improvements. This explains why DAQV DAQ_V performs well in terms of payoff despite not converging to very high precision. Finally, the poor payoff of RRM indicates that it is not an attractive update rule from a selfish perspective. IV-B Heterogeneous dynamics We consider now heterogeneous dynamics where a fraction α1 _A_1 of agents uses algorithm 1A_1 while the remaining agents use 2A_2 with γ=0γ=0. Figure 5 shows the evolution over time of the instantaneous bid and payoff of two representative agents—one using 1A_1 and the other using 2A_2—for (1,2)∈(BR,OGD),(BR,DAQ)(A_1,A_2)∈\( BR, OGD),( BR, DAQ)\ and for αBR∈10%,80%,90% _ BR∈\10\%,80\%,90\%\. Similar results for the couple (OGD,DAQ)( OGD, DAQ) are available in the supplementary material. Overall, heterogeneous dynamics do not appear to converge to the stage-game NE. For αBR∈10%,80% _ BR∈\10\%,80\%\, the trajectories nevertheless appear to settle to a steady regime. In the (BR,DAQ)( BR, DAQ) regime, DAQ at first saturates its budget constraint and then exhibits a slow transient regime before stabilizing, whereas OGD adapts relatively faster. This is consistent with DAQ aggregating gradients over time and OGD responding more strongly to recent feedback. Finally, for αBR=90% _ BR=90\%, both OGD and DAQ show persistent bid oscillations, while BR bids remain comparatively stable. Since BR agents form the large majority, the aggregate bid changes little so best responses vary only little because of the concavity of the payoff function. In terms of instantaneous payoff, for αBR∈10%,80% _ BR∈\10\%,80\%\ the (BR,DAQ)( BR, DAQ) configuration displays periods of low payoff for BR, but even lower for DAQ, due to the DAQ agents budget saturation. In contrast, with (BR,OGD)( BR, OGD) the system stabilizes more quickly. In both cases, the BR agent’s payoff converges to a value close (and sometimes slightly above) the stage-game NE value, whereas the DAQ and OGD agents can fall below the NE payoff at αBR=80% _ BR=80\%. Finally, for αBR=90% _ BR=90\%, the oscillatory bids of OGD and DAQ player translate into large payoff fluctuations, with a payoff repeatedly dropping to significantly lower values than their NE payoff. Finally, Figure 6 reports the average payoff of two representative agents—one using 1A_1 and the other using 2A_2—for (1,2)∈(BR,OGD),(BR,DAQ),(OGD,DAQ)(A_1,A_2)∈\( BR, OGD),( BR, DAQ),( OGD, DAQ)\ and multiple values of α1 _A_1. Overall, heterogeneous play can yield time-average payoffs that are slightly above or below the stage-game NE payoff, sometimes benefiting one group more than the other. However, these deviations remain small: across all mixtures, observed payoffs lie in [0.64,0.67][0.64,0.67], while the NE payoff is roughly 0.6550.655. Both OGD and DAQ exhibit similar trends: when they represent less than 30%30\% of the population, their time-average payoff falls below the NE payoff, whereas for larger fractions it can exceed it. In contrast, BR achieves payoffs consistently above the NE, with peak values for large αBR _ BR. Overall, while payoff differences across policies remain small in these experiments, the BR dynamics appear slightly preferable, despite lacking no-regret guarantees. V Conclusion In this paper, we study the game induced by the competition among agents in a proportional allocation auction. We derive a sufficient condition under which the game satisfies Rosen’s diagonal strict concavity (DSC). The condition holds in particular when agents have logarithmic utilities in their allocated share. We further relate these utilities to bandwidth allocation problems in which the objective is to balance fairness and throughput. We then consider the repeated version of the game, where all agents update their bids using either best-response dynamics or classical no-regret learning algorithms, namely Online Gradient Descent and Dual Averaging. Under DSC, these homogeneous dynamics are proved to converge to the stage-game Nash equilibrium. Several extensions of this work can be considered. First, it would be desirable to develop a theoretical framework to capture the impact of heterogeneous update rules on system dynamics. Another direction is to extend the analysis to more general utility functions, such as α-fair utilities, or to settings in which players bid for multiple heterogeneous resources. References [1] J. B. Rosen (1965-07) Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33 (3). Cited by: item 2, §I, §I-D, §I-D, §I-D. [2] I. Caragiannis and A. A. Voudouris (2016) Welfare guarantees for proportional allocations. Theory Comput. Syst. 59. Cited by: §I. [3] I. Caragiannis and A. A. Voudouris (2018) The efficiency of resource allocation mechanisms for budget-constrained users. In EC, p. 681–698. Cited by: §I. [4] R. Coleman (2012) Calculus on normed vector spaces. Springer. Cited by: §I-D. [5] S. D’Oro et al. (2017) Auction-based resource allocation in openflow multi-tenant networks. Comput. Networks. External Links: Document Cited by: §I. [6] M. Datar, E. Altman, F. D. Pellegrini, R. E. Azouzi, and C. Touati (2020) A mechanism for price differentiation and slicing in wireless networks. In WiOPT, p. 121–128. Cited by: §I-A. [7] F. De Pellegrini, A. Massaro, L. Goratti, and R. El-Azouzi (2017) Bounded generalized Kelly mechanism for multi-tenant caching in mobile edge clouds. In NetGCoop, Cited by: §I-D. [8] E. Elkind, A. Ghosh, and P. W. Goldberg (2024) Continuous-time best-response and related dynamics in tullock contests with convex costs. arXiv preprint arXiv:2402.08541. Cited by: §I. [9] E. Even-Dar, Y. Mansour, and U. Nadav (2009) On the convergence of regret minimization dynamics in concave games. In STOC, p. 523–532. Cited by: §I. [10] S. Hart and A. Mas-Colell (2003) Uncoupled dynamics do not lead to nash equilibrium. American Economic Review. Cited by: §I-D. [11] E. Hazan (2016) Introduction to online convex optimization. Foundations and Trends® in Optimization. Cited by: §I-B, §I-C. [12] A. Héliou, J. Cohen, and P. Mertikopoulos (2017) Learning with bandit feedback in potential games. In NIPS, p. 6369–6378. Cited by: §I. [13] R. Johari and J. N. Tsitsiklis (2004) Efficiency loss in a network resource allocation game. Math. Oper. Res.. External Links: Document Cited by: §I. [14] R. Johari (2004) Efficiency loss in market mechanisms for resource allocation. Ph.D. Thesis, Department of Electrical Engineering and Computer Science. Cited by: §I, §I, §I, §I-A, §I-D. [15] F. Kelly (1997) Charging and rate control for elastic traffic. Eur. Trans. Telecommun. 8 (1), p. 33–37. External Links: Document Cited by: §I, §I, §I. [16] H. Kim and Y. Han (2005) A proportional fair scheduling for multicarrier transmission systems. IEEE Commun. Lett.. External Links: Link, Document Cited by: §I-A. [17] R. T. Maheswaran and T. Basar (2006) Efficient signal proportional allocation (ESPA) mechanisms: decentralized social welfare maximization for divisible resources. IEEE JSAC. 24 (5). Cited by: §I, §I, §I, §I, §I, §I, §I, §I-D. [18] P. Maillé and B. Tuffin (2004) Multi-bid auctions for bandwidth allocation in communication networks. In IEEE INFOCOM, Cited by: §I. [19] Y. B. Mazziane, C. Mboulou-Moutoubi, F. De Pellegrini, and E. Altman (2025) Learning to bid in proportional allocation auctions with budget constraints. In 2025 23rd WiOpt, p. 1–8. Cited by: §I-D. [20] C. M. Mboulou-Moutoubi, Y. Ben Mazziane, F. De Pellegrini, and E. Altman (2025) Best-response learning in budgeted α-fair kelly mechanisms. In NETGCOOP, p. 90–99. Cited by: §I-D, Remark 2. [21] H. B. McMahan (2017) A survey of algorithms and analysis for adaptive online learning. J. Mach. Learn. Res. 18. Cited by: §I-C, §I-C. [22] P. Mertikopoulos et al. (2024) A unified stochastic approximation framework for learning in games. Math. Program. (). Cited by: §I-C, §I-D. [23] P. Mertikopoulos and Z. Zhou (2019) Learning in games with continuous action sets and unknown payoff functions. Math. Program. 173 (1-2), p. 465–507. External Links: Document Cited by: §I-A, §I-C, §I-D, §I-D, §I-D, §I-D, §I-D. [24] D. Monderer and L. S. Shapley (1996) Potential games. Games and economic behavior 14 (1), p. 124–143. Cited by: §I-D. [25] L. Orseau (2025-06) A regret bound for online gradient descent with momentum. Technical report Personal Technical Report. Note: Available at: https://laurent-orseau.com/docs/OGDM_regret.pdf Cited by: §I-C. [26] J. D. Pérez-Castrillo and T. Verdier (1992) A general analysis of rent-seeking games. Public choice 73 (3), p. 335–350. Cited by: §I. [27] W. Saad et al. (2011) A noncooperative game for double auction-based energy trading between phevs and distribution grids. In IEEE SmartGridComm, Vol. . Cited by: §I. [28] V. Syrgkanis and É. Tardos (2013) Composable and efficient mechanisms. In STOC, p. 211–220. External Links: Document Cited by: §I. [29] X. Wang et al. (2021) A distributed truthful auction mechanism for task allocation in mobile cloud computing. IEEE Trans. Serv. Comput. (3). Cited by: §I. [30] S. Yang and B. E. Hajek (2007) VCG-kelly mechanisms for allocation of divisible goods: adapting VCG mechanisms to one-dimensional signals. IEEE J. Sel. Areas Commun.. External Links: Link, Document Cited by: §I. [31] Y. Yang, R. T. B. Ma, and J. C. S. Lui (2013) Price differentiation and control in the kelly mechanism. Perform. Evaluation. External Links: Document Cited by: §I-D. [32] L. Zheng et al. (2019) Auction-based order dispatch and pricing in ridesharing. In 35th IEEE ICDE, External Links: Document Cited by: §I. [33] Z. Zhou, P. Mertikopoulos, A. L. Moustakas, N. Bambos, and P. W. Glynn (2021) Robust power management via learning and game design. Operations Research 69 (1), p. 331–345. External Links: Document Cited by: §I-A. [34] Z. Zhou, P. Mertikopoulos, et al. (2021) Robust power management via learning and game design. Oper. Res. 69 (1). Cited by: §I-D, §I-D, §I-D, §I-D. [35] M. Zinkevich (2003) Online convex programming and generalized infinitesimal gradient ascent. In ICML, p. 928–936. Cited by: §I-C. VI Supplementary Material VI-A Proof of Theorem 2 Define the functions fif_i, gig_i, and ψ, _ r, V as fi(x)=(1−x)2V¨i(x)−2(1−x)V˙i(x), f_i(x)=(1-x)^2 V_i(x)-2(1-x) V_i(x), (40) gi(x)=−x(1−x)V¨i(x)+(2x−1)V˙i(x), g_i(x)=-x(1-x) V_i(x)+(2x-1) V_i(x), (41) ψ,()(∑i∈ℐrigi(xi)2ki(xi))(∑i∈ℐ1riki(xi)), _ r, V( x) ( _i r_ig_i(x_i)^2k_i(x_i) ) ( _i 1r_ik_i(x_i) ), (42) where ki(x)=gi(x)−fi(x)+δ2Lik_i(x)=g_i(x)-f_i(x)+δ^2L_i and Li=minzi∈ℛip¨i(zi)L_i= _z_i _i p_i(z_i). Further define the set =>:∑i∈ℐxi≤∑k∈ℐck∑k∈ℐck+δ =\ x> 0:\; _i x_i≤ _k c_k _k c_k+δ\. We prove that, ∃>:sup∈ψ,()<1⟹ is (), ∃ r> 0:\; _ x∈ _ r, V( x)<1 is SDSC( r), (43) or equivalently we prove that the matrix () H_ r( z) is negative definite whenever sup∈ψ,()<1 _ x∈ _ r, V( x)<1. The second-order partial derivatives of the payoff functions ∂i,j2φi _i,j^2 _i can be written as ∂i,j2φi()=∂i,j2Ui()−p¨i(zi), _i,j^2 _i( z)= _i,j^2U_i( z)- p_i(z_i), (44) where Ui()=Vi(xi())U_i( z)=V_i(x_i( z)), and p¨i p_i is the second derivative of pip_i. Note that pip_i is convex, which implies it contributes to the matrix () H_ r( z) as a diagonal matrix whose entries are −2rip¨i(zi)≤0-2r_i p_i(z_i)≤ 0 and thus is negative semi-definite. Consequently, any failure of () H_ r( z) to be negative definite would stem from the matrix formed by ∂i,j2Ui() _i,j^2U_i( z). Lemma 1 shows that this matrix has a particular structure. Lemma 1. The partial derivatives of UiU_i verify, m(z)∂i,j2Ui()=fi(xi()),if i=j,gi(xi()),otherwise. m(z) _i,j^2U_i( z)= casesf_i(x_i( z)),&if i=j,\\ g_i(x_i( z)),&otherwise. cases (45) Proof: The calculation of the derivative of UiU_i with respect to ziz_i writes ∂iUi(zi)=∑jiNzj+δ(∑l=1Nzl+δ)2V˙i(zi∑l=1Nzl+δ). _iU_i(z_i)= _j≠ i^Nz_j+δ ( _l=1^Nz_l+δ )^2 V_i ( z_i _l=1^Nz_l+δ ). (46) The elements on the diagonal can be written as ∂i,i2Ui() ∂^2_i,iU_i( z) =−2∑liNzi+δ(∑l=1Nzl+δ)3V˙i(zi∑l=1Nzl+δ) = -2 _l≠ i^Nz_i+δ( _l=1^Nz_l+δ)^3 V_i ( z_i _l=1^Nz_l+δ ) +(∑liNzl+δ(∑l=1Nzl+δ)2)2V¨i(zi∑l=1Nzl+δ) + ( _l≠ i^Nz_l+δ( _l=1^Nz_l+δ)^2 )^2 V_i ( z_i _l=1^Nz_l+δ ) =[(1−xi())2V¨i(xi())−2(1−xi())V˙i(xi())](∑i=1Nzj+δ)2 = [(1-x_i( z))^2 V_i(x_i( z))-2(1-x_i( z)) V_i(x_i( z)) ] ( _i=1^Nz_j+δ )^2 =fi(xi())m(z)2. = f_i(x_i( z))m(z)^2. (47) In a similar fashion we obtain the off-diagonal entries ∂i,j2Ui() ∂^2_i,jU_i( z) =∑l=1Nzl+δ−2(∑liNzl+δ)(∑l=1Nzl+δ)3V˙i(zi∑l=1Nzl+δ) = _l=1^Nz_l+δ-2 ( _l≠ i^Nz_l+δ ) ( _l=1^Nz_l+δ )^3 V_i ( z_i _l=1^Nz_l+δ ) −∑liNzl+δ(∑l=1Nzl+δ)4⋅zi⋅V¨i(zi∑l=1Nzl+δ) - _l≠ i^Nz_l+δ ( _l=1^Nz_l+δ )^4· z_i· V_i ( z_i _l=1^Nz_l+δ ) =[−V¨i(xi())xi()(1−xi())+V˙i(xi())(2xi()−1)](∑i=1Nzj+δ)2 = [- V_i(x_i( z))x_i( z)(1-x_i( z))+ V_i(x_i( z))(2x_i( z)-1) ] ( _i=1^Nz_j+δ )^2 =gi(xi())m(z)2 = g_i(x_i( z))m(z)^2 (48) which concludes the calculation. ∎ Lemma 1 shows that the matrix of second partial derivatives of the functions UiU_i can be rewritten using a change of variable from ∈ℛ z to () x( z). Moreover, this reformulated matrix can be decomposed into the sum of a diagonal matrix, with entries fi(xi)−gi(xi)f_i(x_i)-g_i(x_i), and a rank-one matrix, whose entries are given by gi(xi)g_i(x_i). Lemma 2 leverages this particular structure to prove (43). Lemma 2. sup∈ψ,()<1⟹() is negative definite for any . _ x∈ _ r, V( x)<1 H_ r( z) is negative definite for any $ z$. Proof: Let > r> 0. We assume that sup∈ψ,()<1 _ x∈ _ r, V( x)<1 and prove that the matrix () H_ r( z) is negative definite for every ∈ℛ z . To this end, we introduce the following notation. We define the vectors =(gi(xi()))i=1n g=(g_i(x_i( z)))_i=1^n and =(fi(xi()))i=1n f=(f_i(x_i( z)))_i=1^n, and set k~i()=gi(xi())−fi(xi())+m()p¨i(zi) k_i( z)=g_i(x_i( z))-f_i(x_i( z))+m( z) p_i(z_i), so that ~=(k~i())i=1n k=( k_i( z))_i=1^n. Here, ⊙ denotes the Hadamard (elementwise) product, 1 is the vector of ones, and () ( a) represents the diagonal matrix whose diagonal entries are the components of a. Thanks to Lemma 1, the matrix can be expressed as m()⋅(r())i,j=2ri(fi(xi())−m()p¨i(zi)),if i=j,rigi(xi())+rjgj(xj()),if ij. m( z)·( H_r( z))_i,j= cases2r_i (f_i(x_i( z))-m( z)\, p_i(z_i) ),&if i=j,\\ r_i\,g_i(x_i( z))+r_j\,g_j(x_j( z)),&if i≠ j. cases (49) Thus, the matrix r() H_r( z) can be written compactly as ()=−2(~⊙)+(⊙)+(⊙). H_ r( z)=-2\, ( k r )+ ( g r )1+1 ( g r ). (50) Notice that k~i()≥ki(xi()) k_i( z)≥ k_i(x_i( z)). Moreover, replacing by the expressions of gig_i and fif_i in (24) and (23), we obtain, ki(xi)=(xi−1)V¨i(xi)+V˙i(xi)+δ2minzi∈ℛip¨i(zi). k_i(x_i)=(x_i-1)\, V_i(x_i)+ V_i(x_i)+δ^2\, _z_i _i p_i(z_i). (51) By Assumption 1, we have V˙i>0 V_i>0, V¨i<0 V_i<0, and p¨i>0 p_i>0. Moreover, since xi()<1x_i( z)<1 (as ∈ x∈ ), it follows that ki(xi())>0k_i(x_i( z))>0. Define also the vector =(ki(xi()))i=1N k= (k_i(x_i( z)) )_i=1^N. Let ∈RN v ^N. Using the expression of r() H_r( z), we have T() v^T H_ r( z) v =−2(∑i=1nvi2rik~i()−⟨,⊙⟩⟨, 1⟩) =-2 ( _i=1^nv_i^2\,r_i\, k_i( z)- v,\, g r \, v,\,1 ) ≤−2(∑i=1nvi2riki(xi())−⟨,⊙⟩⟨, 1⟩), ≤-2 ( _i=1^nv_i^2\,r_i\,k_i(x_i( z))- v,\, g r \, v,\,1 ), (52) where ⟨⋅,⋅⟩ ·,· denotes the inner product. We now rewrite the inner products in (52) by noting that, for any vector a, the notation a represents the vector obtained by taking the square root of each component of a, and the ratio of two vectors is computed elementwise. In particular, ⟨,⊙⟩ v,\, g r =⟨⊙,⊙⟩, = v k r,\, r g k , (53) ⟨, 1⟩ v,\,1 =⟨⊙,⊙⟩. = v k r,\, 1 k r . (54) Applying the Cauchy-Schwarz inequality to these expressions and substituting into (52) yields T()≤−2∑i=1nvi2riki(xi()) v^T H_ r( z) v≤-2 _i=1^nv_i^2\,r_i\,k_i(x_i( z)) +2(∑i=1nvi2riki(xi()))∑i=1nrigi(xi())2ki(xi())∑i=1n1riki(xi()) +2 ( _i=1^nv_i^2r_ik_i(x_i( z)) ) _i=1^n r_i\,g_i(x_i( z))^2k_i(x_i( z)) _i=1^n 1r_ik_i(x_i( z)) =2∑i=1nvi2riki(xi())⏟>0(−1+∑i=1nrigi(xi())2ki(xi())∑i=1n1riki(xi())), =2 _i=1^nv_i^2r_ik_i(x_i( z))_>0 (-1+ _i=1^n r_ig_i(x_i( z))^2k_i(x_i( z)) _i=1^n 1r_ik_i(x_i( z)) ), which concludes the proof. ∎ Assume that Vi(x)=ailog(x)+diV_i(x)=a_i (x)+d_i, δ>0δ>0, and ri=ai−1r_i=a_i^-1. Straightforward calculations show that gi(x)=aig_i(x)=a_i and ki(x)=ai/x2+δ2Lik_i(x)= a_ix^2+δ^2L_i. Thus ψ,() _ r, V( x) verifies, ψ,() _ r, V( x) =(∑i=1naiai/xi2+δ2Li))(∑i=1n11/xi2+δ2ai−1Li) = ( _i=1^n a_i a_ix_i^2+δ^2L_i) ) ( _i=1^n 1 1x_i^2+δ^2a_i^-1L_i ) (55) ≤(∑i=1nxi2)2≤(∑i=1nxi)4≤(C+δ)4<1. ≤ ( _i=1^nx_i^2 )^2≤ ( _i=1^nx_i )^4≤ ( CC+δ )^4<1. (56) Thus the condition sup∈ψ,()<1 _ x∈ _ r, V( x)<1 is satisfied for logarithmic utilities. This finishes the proof. VI-B Additional experiments (a) αDAQF=20% _ DAQ_F=20\% (b) αDAQF=50% _ DAQ_F=50\% (c) αDAQF=80% _ DAQ_F=80\% (d) αDAQF=10% _ DAQ_F=10\% (e) αDAQF=90% _ DAQ_F=90\% Figure 7: Heterogeneous dynamics: DAQF DAQ_F vs. OGDF OGD_F. In each subfigure: bids (top) and instantaneous payoff (bottom). We consider now heterogeneous dynamics where a fraction αDAQ _ DAQ of agents uses DAQ while the remaining agents use OGD with γ=0γ=0. Figures 7 shows the evolution over time of the instantaneous bid and payoff of two representative agents—one using OGD and the other using DAQ—for αDAQ∈10%,20%,50%,80%,90% _ DAQ∈\10\%,20\%,50\%,80\%,90\%\. Convergence is observed only for αDAQ∈[20%,80%] _ DAQ∈[20\%,80\%]. In this regime, the algorithm used by the majority of agents achieves a utility above the NE-utility, while the minority attains a lower payoff. The dynamics are nearly symmetric for αDAQ=50% _ DAQ=50\%. On the other hand, for extreme splits α1∈10%,90% _A_1∈\10\%,90\%\, we observe oscillations.