Learning in Proportional Allocation Auctions Games

1. Problem Statement

The paper investigates the repeated Kelly mechanism (also known as the proportional allocation mechanism), a decentralized auction scheme where a divisible resource is allocated to agents proportionally to their bids.

• Context: In standard settings, agents are assumed to know the allocation rule and the utilities of others, forming a static game with a known Nash Equilibrium (NE). However, in realistic scenarios (e.g., wireless network slicing, cloud computing), agents often lack knowledge of others' utilities and budgets.
• Challenge: Agents must adapt their bidding strategies over repeated rounds based only on feedback (e.g., aggregate bids) to maximize their time-average utility.
• Specific Focus: The paper focuses on agents with logarithmic utility functions ($V_i(x) = a_i \ln(x) + d_i$), which arise naturally in bandwidth allocation problems aiming to balance throughput and fairness (Proportional Fairness). The authors analyze whether repeated play under various learning dynamics converges to the unique Nash Equilibrium of the stage game.

2. Methodology

The authors employ a combination of Game Theory, Online Convex Optimization (OCO), and Fixed-Point Analysis.

A. Problem Formulation

• Mechanism: Agents submit bids $b_{i,t}$. The resource owner allocates a share $x_{i,t} = \frac{w_i(b_{i,t})}{\sum w_j(b_{j,t}) + \delta}$. For the classic Kelly mechanism, $w_i$ is the identity function.
• Utility: Agent $i$'s utility is $\phi_i = V_i(x_{i,t}) - b_{i,t}$.
• Transformation: The problem is reformulated using a change of variable $z_{i,t} = w_i(b_{i,t})$ to simplify the allocation rule and utility function, treating $z$ as the effective bid.
• Assumptions: Valuation functions $V_i$ are strictly increasing, concave, and twice differentiable. Payment functions are convex and increasing.

B. Theoretical Framework

1. Uniqueness of NE: The authors establish conditions for the existence of a unique Nash Equilibrium. They utilize Rosen's Diagonal Strict Concavity (DSC) (specifically $r$-DSC). They derive a tractable sufficient condition (Theorem 2) that reduces the verification of DSC from an $O(n^3)$ matrix check to an $O(n)$ scalar function check.
2. Learning Algorithms: Four bidding strategies are analyzed:
   • Online Gradient Descent (OGD): A standard no-regret algorithm using gradient updates.
   • Dual Averaging with Quadratic Regularizer (DAQ): A variant of Follow-the-Regularized-Leader (FTRL).
   • Regularized-Robbins-Monro (RRM): A distributed procedure for computing the NE.
   • Myopic Best Response (BR): Agents play the best response to the previous round's aggregate bid.
3. Convergence Analysis:
   • For OGD and DAQ, convergence is proven using the $r$-monotonicity property derived from the DSC condition. The authors extend these results to allow for personalized (heterogeneous) learning rates.
   • For BR, the system is modeled as a fixed-point iteration. The authors prove the Best Response operator is a contraction mapping under specific conditions on the minimum bid, guaranteeing linear convergence.

C. Numerical Simulations

Extensive simulations were conducted to validate theoretical results and explore heterogeneous dynamics (where different agents use different learning algorithms simultaneously). Metrics included convergence speed (fixed-point residual) and time-average utility.

3. Key Contributions

1. Derivation of Logarithmic Utilities: The paper formally derives the logarithmic utility form from a practical wireless network slicing scenario, linking the Kelly mechanism to Proportional Fairness optimization.
2. Tractable Uniqueness Condition: They provide a novel, computationally efficient condition (Theorem 2) to verify the uniqueness of the NE for Kelly games with logarithmic utilities and budget constraints. This condition holds for arbitrary convex action sets.
3. Convergence with Personalized Rates: Unlike prior work requiring common learning rates, the authors prove that OGD and DAQ converge to the unique NE even when agents use personalized, regret-optimal learning rates, provided the utilities differ only by multiplicative factors (affine heterogeneity).
4. Best Response Convergence: They prove that myopic Best Response dynamics converge linearly to the NE, provided the minimum bid is sufficiently large relative to the number of agents and utility parameters.
5. Heterogeneous Dynamics Analysis: Through simulations, they demonstrate that while homogeneous dynamics converge to the NE, heterogeneous dynamics (mixing BR, OGD, and DAQ) may fail to converge to the NE point, though they often settle into a stable regime with utilities close to the NE.

4. Key Results

• Uniqueness: The stage game with logarithmic utilities admits a unique Nash Equilibrium.
• Convergence Speed (Homogeneous):
  • Best Response (BR): Achieves the fastest convergence and the highest time-average utility.
  • OGD: Converges slower than BR but faster than DAQ.
  • DAQ/RRM: Converge significantly slower.
  • Note: BR convergence speed increases with the number of agents ($n$), whereas OGD/DAQ speed decreases.
• Convergence with Heterogeneous Rates: Theoretical proofs confirm that OGD and DAQ converge to the NE even with different learning rates per agent.
• Heterogeneous Algorithms: When agents mix strategies (e.g., some use BR, others DAQ):
  • The system often fails to converge to the exact NE point (oscillations occur).
  • However, the time-average utilities remain close to the NE utility.
  • BR agents consistently achieve payoffs slightly above the NE level, while OGD/DAQ agents may fall slightly below, especially when they are the minority.
• Regret: While BR lacks formal "no-regret" guarantees, it empirically outperforms no-regret algorithms (OGD/DAQ) in terms of convergence speed and average payoff in this specific game setting.

5. Significance

• Practical Relevance: The work bridges the gap between theoretical game theory and practical resource allocation in 5G/6G networks (network slicing), where agents (tenants) must learn to bid without full information.
• Algorithmic Insight: It challenges the assumption that "no-regret" algorithms are always superior. In this specific class of games, myopic best-response is computationally simpler and empirically superior in convergence speed and utility.
• Robustness: The results show that the system is robust to heterogeneity; even if agents use different learning rules, the collective outcome remains efficient (close to NE), preventing catastrophic failure in decentralized systems.
• Theoretical Advancement: The derivation of a scalar condition for DSC in Kelly games simplifies the analysis of uniqueness and convergence for a broad class of allocation mechanisms, extending previous results that were limited to linear utilities or specific constraints.

In conclusion, the paper establishes that the repeated Kelly game with logarithmic utilities is a well-behaved system with a unique equilibrium. It demonstrates that while no-regret learning guarantees convergence, simple best-response dynamics are often more efficient in practice, and the system remains stable even when agents employ diverse learning strategies.