Games with Payments between Learning Agents

1. Problem Statement

The paper addresses a critical gap in the analysis of automated economic systems: the behavior of autonomous learning agents (e.g., bidding bots in auctions) that are allowed to make monetary transfers to one another during the course of repeated interactions.

• Context: In modern digital markets (e.g., online ad auctions, blockchain MEV), players use learning agents to optimize long-term payoffs via no-regret algorithms.
• The Gap: Traditional mechanism design and learning theory assume agents act solely based on the rules of the underlying game. However, users may instruct their agents to make side payments to other agents to influence learning dynamics in their favor.
• Core Question: When do players have incentives to enable such payments? How do these endogenous payments alter learning dynamics, equilibria, social welfare, and revenue? Is the "no-payment" state stable?

2. Methodology

The authors propose a Payment-Policy Game (a metagame) to model this interaction.

• Model Structure:
  1. Underlying Game ($\Gamma$): A repeated game (e.g., auction, Prisoner's Dilemma) with $n$ players and utility functions $u_i$.
  2. Agents: Each player $i$ employs a no-regret learning agent ($A_i$) that plays the underlying game for $T$ rounds.
  3. Payment Policies: Before the game dynamics begin, each player $i$ selects a payment policy $p_{ij}(s)$. This policy dictates how much agent $i$ pays agent $j$ as a function of the joint action profile $s$ in the underlying game.
  4. Agent Utility: The utility for agent $i$ at time $t$ is $v_i^t = u_i(s^t) + \sum_{j \neq i} (p_{ji}(s^t) - p_{ij}(s^t))$.
  5. Player Utility: Players care about the long-term average payoff of their agents ($\lim_{T \to \infty} \frac{1}{T} \sum v_i^t$).
• Analysis Framework:
  • The authors analyze the equilibria of the payment-policy game.
  • They assume agents achieve no-regret outcomes (specifically, convergence to Coarse Correlated Equilibria or CCEs) in the underlying game given the payment policies.
  • They define a game as "stable" if zero payments constitute an equilibrium of the payment-policy game. If players can deviate to a payment policy that increases their utility, the game is unstable.

3. Key Contributions

1. Formal Model: Introduction of a metagame framework where users choose payment policies for their learning agents, separating the time scale of policy selection from the learning dynamics.
2. Instability of Zero Payments: Proof that in a broad class of games, abstaining from payments is not a robust equilibrium. Self-interested players generally have incentives to initiate unilateral payments to alter learning dynamics.
3. Auction Analysis: Detailed analysis of First-Price and Second-Price auctions, showing that payment policies lead to highly collusive outcomes that drastically reduce auctioneer revenue.
4. General Game Theory Results:
   • Two-Player Games: Proved that any equilibrium in a two-player payment game is a Pareto improvement over the no-payment outcome.
   • Welfare vs. Revenue: Demonstrated that while payments can improve social welfare in some contexts (e.g., Prisoner's Dilemma), they often lead to revenue extraction by buyers at the expense of the seller (auctioneer).

4. Key Results

A. Second-Price Auctions

• Result: The game is unstable. Players have incentives to use payments.
• Mechanism: The highest-valued player (Player 1) can offer a small payment $\epsilon$ to all other players if they bid zero.
• Outcome:
  • Player 1's agent bids their true value $v_1$.
  • All other agents bid zero (since they receive a payment and avoid the cost of winning).
  • Result: Player 1 wins and pays $v_1$ (the second-highest bid, which is 0).
  • Revenue: The auctioneer's revenue converges to zero as $T \to \infty$.
  • Welfare: Players capture nearly the full social welfare.

B. First-Price Auctions

• Result: The game is unstable. Players prefer payments.
• Mechanism: The high-valued player pays the low-valued player a specific amount $\eta$ when the low-valued player bids zero.
• Outcome:
  • Agents converge to a mixed strategy equilibrium where bids are significantly lower than in the standard no-payment case.
  • Revenue: Revenue is reduced to less than half of the standard outcome.
  • Efficiency: There is a small loss in allocative efficiency (the lower-value player wins occasionally), but the loss is bounded (max ~9% welfare loss).
  • Pareto Improvement: Both players are strictly better off compared to the no-payment equilibrium.

C. General Games (Prisoner's Dilemma & Beyond)

• Prisoner's Dilemma: Without payments, agents defect (Nash Equilibrium). With payments, players can induce cooperation. The paper shows that if the welfare gap is large enough, payments allow agents to reach cooperative outcomes that are Pareto improvements.
• Theorem 5.2 & 5.6: In any finite game where the no-regret dynamics converge to a welfare outcome lower than the optimal (or a better Nash equilibrium), there exists a player who can profitably deviate by using payments to induce the better outcome.
• Theorem 6.1 (Two-Player Games): Every equilibrium of a two-player payment game is a weak Pareto improvement over the no-payment outcome. If one player is worse off, they can simply cancel the payments, reverting to the original game.
• Theorem 6.2: Even in games with dominant strategies (where learning usually converges quickly), players have incentives to use payments to effectively become a Stackelberg leader, forcing the other agent to best-respond to a fixed strategy.

5. Significance and Implications

• Challenge to Mechanism Design: The results suggest that standard auction designs (like Second-Price) are vulnerable to "collusion via side payments" when agents have financial autonomy. The "truthful" nature of Second-Price auctions breaks down when agents can trade outside the mechanism.
• Regulatory Blind Spot: Current antitrust and regulatory frameworks focus on human collusion. This paper highlights a new frontier where algorithmic collusion occurs naturally through learning dynamics and endogenous payments, potentially without explicit human coordination.
• Blockchain and MEV: The findings directly relate to Maximal Extractable Value (MEV) in blockchain, where bots already use payments to manipulate transaction ordering. The paper provides a theoretical basis for why such behaviors are inevitable and profitable for agents.
• Welfare Distribution: While payments can increase total social welfare (by escaping bad equilibria like the Prisoner's Dilemma), they often redistribute wealth from the mechanism designer (seller/auctioneer) to the participants.
• Future Directions: The paper calls for new regulatory tools and mechanism designs that account for the strategic incentives of users to program side payments into their agents.

Conclusion

The paper fundamentally shifts the perspective on learning agents from passive optimizers to strategic actors whose users can manipulate the game structure via payments. It demonstrates that zero-payment strategies are inherently unstable in the presence of learning agents, leading to outcomes that can be highly efficient for participants but devastating for mechanism revenue, posing a significant challenge for the design of future automated markets.