To Spend or to Gain: Online Learning in Repeated Karma Auctions

Technical Summary: To Spend or to Gain: Online Learning in Repeated Karma Auctions

Problem Formulation
This paper addresses the challenge of learning optimal bidding strategies in repeated auction settings where agents utilize artificial currency, specifically "karma," rather than monetary instruments. Unlike traditional monetary auctions where the currency has an exogenous value, artificial currency in these mechanisms has no value outside the auction context. Furthermore, the paper focuses on a specific class of karma mechanisms where payments are redistributed to all users at each time step. In this setting, agents not only spend karma to win resources but also gain karma when they lose (by yielding the resource). This redistribution creates a closed-loop system where the total amount of karma in the system is preserved over time.

The core difficulty lies in the fact that users must jointly learn the value of the currency and how to spend it optimally. Standard adaptive pacing strategies used in budget-constrained monetary auctions are insufficient here because:

1. Non-Truthfulness: The possibility of gaining karma upon losing creates incentives for agents to bid non-truthfully in second-price auctions to maximize their gains.
2. Budget Dynamics: The conservation of total karma means agents cannot simultaneously deplete their budgets, a condition often assumed in monetary settings to fix the scale of pacing multipliers.
3. Unknown Cost: The cost of spending currency is not known a-priori and must be learned online.

The authors model this as a repeated resource allocation problem (e.g., a morning commute scenario with priority lanes) where $N$ agents bid for $\gamma$ priority slots. Agents have private, time-varying valuations. The mechanism uses a second-price auction rule: the top $\gamma$ bidders win and pay the $(\gamma+1)$-th highest bid. This payment is then redistributed uniformly, granting every agent a gain proportional to the payment.

Methodology
The authors propose an Adaptive Karma Pacing (Strategy $K$) strategy derived from online dual gradient ascent techniques, adapted for the specific constraints of karma mechanisms.

1. Relaxed Primal Problem: The authors first formulate the optimal cost problem for an agent with "hindsight" (knowing future valuations and competing bids). Due to the complexity of the budget constraints involving gains, they derive a relaxed lower bound on the optimal cost. This relaxation allows for temporary negative balances (provided the budget is non-negative at the horizon) and simplifies the gain dependency.
2. Dual Formulation: They construct a Lagrangian dual problem. A key novelty is the replacement of the fixed target expenditure rate (common in monetary auctions) with a time-varying term that accounts for expected gains.
3. Algorithm Design: The proposed strategy $K$ updates a pacing multiplier $\mu_{i,t}$ based on the difference between the agent's expenditure ($z_{i,t}$) and their gain ($g_{i,t}$).
   • Bid: $b_{i,t} = \min(\Delta v_{i,t} / \mu_{i,t}, k_{i,t})$.
   • Update: $\mu_{i,t+1} = \mu_{i,t} + \epsilon(z_{i,t} - g_{i,t})$.
   • Projection: Unlike standard monetary pacing where the multiplier is projected onto a range during the update, here the projection $P_{[\underline{\mu}, \overline{\mu}]}$ is applied to the bid denominator. This modification is crucial to prevent the "vanishing box problem," where a constant initial budget and a decaying step size would prevent the multiplier from converging to a value greater than its initial state.
   • Scale Fixing: To address the non-uniqueness of stationary multipliers (since scaling all multipliers by a constant preserves the equilibrium in a zero-sum gain system), the authors rely on the conservation of the sum of multipliers across agents. By moving the projection to the bid, the update rule preserves the sum of multipliers $\sum \mu_{i,t}$, anchoring the equilibrium to the initial multiplier profile.

Key Contributions
The paper provides a theoretical framework for adaptive learning in karma auctions with redistribution, establishing three main results:

1. Asymptotic Optimality (Single Agent): For a single agent bidding against a stationary distribution of competing bids, the adaptive karma pacing strategy is asymptotically optimal. The average expected regret converges to an $O(\hat{\epsilon})$ neighborhood of the optimal cost with hindsight, where $\hat{\epsilon}$ represents the "residual gain" (the expected difference between the price setter's bid and the next highest bid). This residual gain diminishes as the number of agents increases.
2. Convergence of Learning Dynamics (Multi-Agent): When all agents adopt strategy $K$, the learning dynamics converge asymptotically to a unique stationary multiplier profile. The authors prove that the expected distance between the time-varying multiplier profile and the stationary profile converges to zero.
3. Approximate Nash Equilibrium: In a setting with a large number of parallel auctions (where the probability of any two specific agents interacting decays), the profile of adaptive karma pacing strategies constitutes an approximate Nash equilibrium. No single agent can asymptotically improve their average cost by unilaterally deviating from the strategy.

Results and Analysis
The analysis requires novel technical steps compared to monetary auction literature:

• Regret Bound: The regret bound includes a term for the residual gain $\hat{\epsilon}$, acknowledging that without hindsight, an agent cannot perfectly manipulate the price setter position.
• Hitting Time Control: The authors introduce a stricter notion of "hitting time" (the time until the multiplier hits its bounds or the budget is depleted) to ensure the validity of the gradient ascent approximation. They provide assumptions on valuation and bid distributions to guarantee this hitting time approaches the time horizon $T$.
• Vanishing Box Problem: The paper identifies and solves a convergence issue where fixed initial budgets and decaying step sizes would prevent convergence in standard adaptive pacing. The proposed modification (projecting on the bid rather than the multiplier update) resolves this.

Significance
The paper claims significance in bridging the gap between theoretical equilibrium analysis and practical learning in non-monetary mechanisms. While previous works established the existence of equilibria in karma mechanisms, this work provides a simple, decentralized learning rule that allows agents to reach these equilibria without central coordination or prior knowledge of valuation distributions.

The authors note that their results are particularly relevant for applications where monetary instruments are deemed unfair or inappropriate, such as food donation allocation, course seat assignment, or traffic congestion management. The proposed strategy offers a mechanism for users to express time-varying preferences efficiently and fairly over repeated interactions, ensuring resources are allocated to those with the highest valuations without the need for money. The paper concludes by acknowledging that while the analysis assumes specific redistribution schemes and technical conditions (e.g., absolute continuity of distributions), numerical experiments suggest robustness to discrete distributions and potential extensions to variable step sizes.