Source-linked AI summary
Reward-Rate Congestion Games and Replicator--Dinkelbach Dynamics
Hassan Abdelraouf, Vaibhav Srivastava, Vijay Gupta
TL;DR
In cyber-physical and robotic systems, reward per unit execution time can matter more than total reward, yet reward-rate payoffs generally lack the exact-potential structure of standard congestion games. The paper applies a Dinkelbach-based framework to recover potential structure and align it with social reward rate. It establishes finite termination under global inner maximization and stability results for replicator–Dinkelbach dynamics under stated conditions.
Problem
Reward-rate payoffs account for execution time but generally do not preserve the exact-potential structure that supports decentralized learning and equilibrium computation in congestion games.
Source: §I · p. 1Method
A Dinkelbach transformation makes each fixed-parameter game an exact potential game, with marginal externality corrections aligning its potential to the transformed social reward-rate objective.
Source: §I · p. 1, §III · p. 3Results
Takeaways & Limitations
The framework supports optimizing social reward rate through corrected potentials and analyzing continuous task allocation with replicator–Dinkelbach dynamics.
Source: §I · p. 1, §III · p. 3, §VII · p. 6
Abstract
from arXiv · showhide
Reward rate is a key performance criterion in cyber-physical and robotic systems where time, workload, and coordination costs are limiting resources. We introduce reward-rate congestion games, where agents seek to maximize reward per unit execution time. The direct reward-rate game is generally not an exact potential game. We develop a Dinkelbach-based framework in which, for every fixed Dinkelbach parameter, the transformed game is an exact potential game. This yields a potential-level Dinkelbach iteration that terminates finitely at the optimal potential reward rate when the inner potential maximization problem is solved globally. We also provide a sufficient condition under which an equilibrium of the transformed game is an equilibrium of the original reward-rate game. To optimize aggregate performance, we introduce marginal externality corrections that make the corrected potential coincide with the Dinkelbach-transformed social reward-rate objective, thereby enabling optimization of the social reward rate. Finally, we develop a continuous-time replicator--Dinkelbach dynamics for reward-rate population games coupling fast replicator dynamics with a slow reward-rate update. We establish convergence of the fixed-parameter replicator dynamics, global asymptotic and local exponential stability of the reduced Dinkelbach dynamics, and local exponential stability of the coupled system for sufficiently slow Dinkelbach updates. The framework is illustrated on a continuous task-allocation problem.
I. INTRODUCTION
Reward-rate objectives better capture performance when execution time, workload, and coordination costs matter, but ratio payoffs generally disrupt the exact-potential structure used in congestion games. The paper uses a Dinkelbach transformation to recover that structure and develop equilibrium and social-performance methods.
I. INTRODUCTION
- Reward per unit execution time is relevant to cyber-physical and robotic tasks where time, workload, and coordination costs constrain performance.The introduction names search-and-rescue, environmental monitoring, warehouse automation, inspection, and human–robot teams as examples.Source: §I · p. 1
- Reward-rate payoffs do not generally preserve the exact-potential structure of standard congestion games, limiting direct use of potential-game learning and equilibrium methods.The difficulty arises because reward-rate payoffs divide reward by execution time rather than aggregating additive resource payoffs.Source: §I · p. 1
- For each fixed Dinkelbach parameter, transforming the ratio into a reward-minus-time objective yields an exact-potential game and supports potential-level fractional optimization.With appropriate externality corrections, the framework also optimizes the social reward rate.Source: §I · p. 1
- The paper introduces reward-rate congestion games, where agents maximize reward per unit execution time, and establishes a fixed-parameter exact-potential structure.When the inner potential maximization is solved globally, the potential-level Dinkelbach iteration terminates finitely at the optimal potential reward rate.Source: §I · p. 1
- Marginal externality corrections make the corrected transformed-game potential coincide with the Dinkelbach-transformed social reward-rate objective.Optimizing that corrected potential therefore optimizes the social reward rate.Source: §I · p. 1
- For reward-rate population games, the paper establishes convergence and stability results for fixed-parameter replicator dynamics, reduced Dinkelbach dynamics, and the coupled system under sufficiently slow updates.The coupled equilibrium is locally exponentially stable for sufficiently slow Dinkelbach updates.Source: §I · p. 1
II. REWARD-RATE CONGESTION GAMES
Reward-rate congestion games measure each agent’s reward per unit execution time, but these ratio payoffs generally lack an exact-potential structure. A fixed-parameter Dinkelbach transformation recovers that structure and supports a finite potential-level iteration under global inner maximization, while a common-rate condition can transfer transformed-game equilibria to the original game.
II. REWARD-RATE CONGESTION GAMES
- The Dinkelbach transformation replaces the reward-rate ratio with an additive reward-minus-time payoff for each fixed parameter ρ.The transformed payoff is Qρ_i = R_i − ρT_i.Source: §II · p. 2
- For every fixed ρ, the transformed payoffs Qρ_i = R_i − ρT_i form an exact potential game with a Rosenthal-type potential.This contrasts with the generally non-potential direct reward-rate game.Source: §II · p. 2
- The potential-level reward-rate objective is defined with a positive execution-time potential, ΦT(a) > 0 for every feasible profile.This positivity is assumed for the potential-level Dinkelbach iteration.Source: §II · p. 2
- When each inner potential maximization is solved globally, the potential-level Dinkelbach iteration reaches the optimal potential reward rate in finite time.The iteration requires global maximization; a transformed-game pure Nash equilibrium alone may not suffice.Source: §II · p. 2
- An equilibrium of the transformed game is also an equilibrium of the direct reward-rate game when every agent’s reward rate at that profile equals the transformed parameter.Without this common-rate condition, transformed-game equilibria need not be equilibria of the direct game.Source: §II · p. 3
III. SOCIAL-REWARD-RATE ALIGNMENT VIA EXTERNALITY CORRECTIONS
The potential-level reward-rate objective need not match the social reward-rate objective. Marginal externality corrections align the transformed game’s exact potential with the social objective, enabling finite optimization under globally solved inner problems.
III. SOCIAL-REWARD-RATE ALIGNMENT VIA EXTERNALITY CORRECTIONS
- Potential-level reward and execution-time ratios do not generally equal the corresponding social ratios, so optimizing the former need not optimize social reward rate.The section identifies this mismatch as the reason to correct individual incentives.Source: §III · p. 3
- Marginal contributions assign each resource corrected reward and execution time, aligning transformed individual incentives with the social reward-rate objective.For resource e at congestion k, the corrections are k r_e(k) − (k−1)r_e(k−1) and k t_e(k) − (k−1)t_e(k−1).Source: §III · p. 3
- For every fixed ρ, the corrected transformed game is an exact potential game with potential SWR(a) − ρSWT(a).The corrected execution-time potential equals aggregate social execution time.Source: §III · p. 3
- When each inner problem is solved globally, the potential-level Dinkelbach construction reaches the optimal social reward rate in finitely many iterations.Source: §III · p. 3
IV. TASK ALLOCATION AS A SINGLETON CONGESTION GAME
The task-allocation model treats tasks as resources in a singleton congestion game. Each agent’s reward and execution time depend on the number assigned to its task, and Nash stability is equivalent to pure Nash equilibrium.
IV. TASK ALLOCATION AS A SINGLETON CONGESTION GAME
- Each agent selects one task, making the allocation a singleton congestion game with tasks as resources.Source: §IV · p. 3
- For an agent assigned to task j, reward r_j(n_j(a)) and execution time t_j(n_j(a)) depend on the number of agents assigned there.Source: §IV · p. 3
- For a fixed parameter, the transformed task-allocation game is an exact potential game.Source: §IV · p. 3
- Because payoffs depend only on the selected task and coalition size, Nash stability is equivalent to pure Nash equilibrium: no agent can improve by switching tasks.Source: §IV · p. 4
V. CONTINUOUS-TIME REPLICATOR–DINKELBACH DYNAMICS
The paper couples fast replicator dynamics for a fixed Dinkelbach parameter with a slow reward-rate update. Under the stated assumptions, the reduced parameter dynamics converge to the optimum, and the coupled system is locally exponentially stable when the update is sufficiently slow.
V. CONTINUOUS-TIME REPLICATOR–DINKELBACH DYNAMICS
- The fast state x follows the fixed-ρ inner dynamics while the slow parameter ρ updates according to the currently achieved reward rate R(x)/T(x).The update rate ε separates the two time scales.Source: §V · p. 4
- Under Assumptions 1 and 2, the optimizer x⋆(ρ) is unique and varies twice continuously differentiably over I.Source: §V · p. 4
- For fixed ρ, every frozen-parameter replicator trajectory from an interior initial condition converges to x⋆(ρ), which is globally asymptotically attractive relative to the simplex interior.Source: §V · p. 4
- Under Assumption 2, the fixed-parameter optimizer x⋆(ρ) is locally exponentially stable uniformly for ρ in I.Source: §V · p. 4
- The reduced Dinkelbach dynamics make the optimal reward rate ρ⋆ globally asymptotically stable and locally exponentially stable under Assumptions 1 and 2.Source: §V · p. 5
- For sufficiently small ε, the coupled replicator–Dinkelbach system has a locally exponentially stable equilibrium at (x⋆(ρ⋆), ρ⋆).Source: §V · p. 5
- The two-time-scale stability argument also applies to sufficiently smooth fast learning dynamics with the same fixed-parameter optimizer and uniform local exponential stability.Source: §V · p. 6
VI. NUMERICAL EXAMPLE
The continuous task-allocation example shows allocation trajectories and Dinkelbach variables converging to the same optimizer and reward rate from different initial conditions. The static iteration yields a unique global maximizer for each inner problem in the example.
VI. NUMERICAL EXAMPLE
- The example allocates a population across victim search, damage inspection, and communication relay/mapping, with saturating task rewards and congestion-increasing execution-time burdens.The reward and execution-time functions are denoted Bj and Hj, respectively.Source: §VI · p. 6
- The task-allocation objective is to maximize R(x)/T(x) over ∆3.The example uses xj to denote the fraction of the population assigned to task j.Source: §VI · p. 6
- x⋆≈(0.1920, 0.2797, 0.5282)⊤ and ρ⋆≈11.1941; trajectories from different initial conditions converge to both.The optimizer and reward rate are computed by static Dinkelbach iteration and are the limits illustrated in Figure 1.Source: §VI · p. 6, Figure 1 · p. 6
- For every ρk≥0, strict concavity of R−ρkT gives a unique global maximizer over ∆3.The passage attributes this to strictly concave R and strictly convex T.Source: §VI · p. 6
VII. CONCLUSION
The paper develops a Dinkelbach-based framework for reward-rate congestion games, with finite potential-level iteration when inner maximization is global and corrected potentials aligned with the social objective. For continuous task allocation, the coupled dynamics is locally exponentially stable for sufficiently slow Dinkelbach updates.
VII. CONCLUSION
- For fixed Dinkelbach parameters, the transformation recovers an exact potential game, and potential-level iteration terminates finitely at the optimal potential reward rate under global inner maximization.The conclusion states that marginal externality corrections align the potential with the social reward-rate objective.Source: §VII · p. 6
- Marginal externality corrections align the potential with the Dinkelbach-transformed social reward-rate objective.This alignment is the paper's stated route to optimizing the social reward rate.Source: §VII · p. 6
- For continuous task allocation, the fast and reduced subsystems converge, while the coupled equilibrium is locally exponentially stable for sufficiently slow Dinkelbach updates.Source: §VII · p. 6
- Future work will extend the framework to nonconcave transformed potentials and discrete-time learning dynamics with global convergence guarantees.Source: §VII · p. 6