💻 computer science

Learning to Strategically Acquire Resources in Competition

This paper proposes a novel game-theoretic model for multiple agents competing to acquire costly divisible resources over time, establishing the existence and efficient computability of Bayesian Nash equilibria under partial information, proving convergence conditions for learning dynamics without a common prior, and validating these findings through simulations on real financial data.

Original authors: Safwan Hossain, Mirah Shi, Andrew Bennett, Neil Andrew Chriss, Michael Kearns, Anderson Schneider, Yuriy Nevmyvaka

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Safwan Hossain, Mirah Shi, Andrew Bennett, Neil Andrew Chriss, Michael Kearns, Anderson Schneider, Yuriy Nevmyvaka

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling marketplace where everyone is trying to buy or sell the same thing—like shares of a stock or hours of cloud computing power. The catch? The price isn't fixed. It changes every second based on how much everyone else is buying or selling. If too many people try to buy at once, the price spikes. If they all sell, it crashes.

This paper is about figuring out the best way to play this game when you are competing against other smart, strategic players who are also trying to get the best deal.

Here is the breakdown of their ideas using simple analogies:

1. The Problem: The "Traffic Jam" of Trading

Imagine you need to drive a heavy truck across a city to deliver a package. If you drive alone, you can take the fastest route. But if 100 other trucks are trying to do the same thing at the same time, you create a traffic jam. Your driving affects the traffic, and the traffic affects your speed (and fuel cost).

In finance and computing, this is called market impact. If you try to buy a huge amount of an asset quickly, you push the price up, making your own purchase more expensive. The paper looks at how multiple "trucks" (traders) should drive their routes (trading schedules) when they know everyone else is doing the same.

2. The Old Way vs. The New Way

Previous studies tried to solve this, but they had some unrealistic rules:

The "Perfect Knowledge" Assumption: They assumed every trader knew exactly what everyone else was thinking and planning. In real life, you don't know if your competitor is a nervous beginner or a calm expert.
The "Fixed Goal" Assumption: They assumed everyone just wanted to buy a specific number of shares as cheaply as possible. In reality, some traders might want to buy a lot, others a little, and some might care more about when they buy rather than just the total cost.

This paper's new model is more like real life:

Hidden Cards: Traders have "private information" (like their own budget or urgency) that others don't see. They only know the general odds of what others might be doing.
Flexible Goals: Traders can have different goals. Some want to minimize cost, others want to maximize profit based on a specific target, and some have strict rules (like "no short selling").

3. The "Perfect Play" (When Everyone Knows the Rules)

First, the authors asked: "If everyone knows the general rules of the game (the probability of different scenarios), what is the perfect strategy?"

They proved that there is one unique, perfect way for everyone to play. It's like finding the single best route for every driver in a city that avoids traffic jams for everyone simultaneously. They also showed that computers can calculate this "perfect play" relatively quickly.

They also looked at the Price of Anarchy. Imagine a scenario where everyone plays selfishly to get the best deal for themselves. How much worse is the total outcome for the group compared to if they all cooperated?

The Finding: In some tricky situations (where some people are buying and others are selling to each other), the "selfish" outcome can be terrible for the group. However, if everyone is trying to do the same thing (like all trying to buy), the selfish outcome is actually quite efficient.

4. The "Learning" Part (When You Don't Know the Rules)

This is the most practical part of the paper. In the real world, you don't know the "odds" of what others are doing. You have to learn by doing.

The authors created an algorithm (a set of instructions) that allows traders to learn over time.

The Setup: Traders play the game over and over again. After each round, they see the price history and get a rough estimate of how much their trading moved the market.
The Learning: They don't need to know the exact math of the market beforehand. They just adjust their strategy based on what happened last time.
The Result: The paper proves that if everyone uses this learning method, their strategies will eventually settle down and match the "Perfect Play" (the equilibrium) described earlier. Even if their estimates of the market are slightly wrong, they still converge to a very good solution.

5. Real-World Testing

To make sure this wasn't just math on paper, they tested it using real data from the foreign exchange market (trading Canadian Dollars for US Dollars).

They estimated how prices actually move based on real trading volume.
They simulated the game with these real numbers.
The Outcome: The learning algorithm worked incredibly well. The strategies the computers "learned" over 500 rounds were almost identical to the mathematically perfect strategies calculated beforehand.

Summary Analogy

Think of this paper as a guide for a group of drivers trying to navigate a city with no traffic lights, where the road width changes based on how many cars are on it.

The Theory: They figured out the mathematically perfect driving pattern if everyone knew the city's layout.
The Learning: They invented a way for drivers to learn the perfect pattern just by driving the route repeatedly and watching where the traffic jams formed, without needing a map.
The Proof: They tested it in a simulation using real traffic data and showed that the drivers quickly learned to drive in a way that minimized traffic for everyone.

The paper concludes that even in a chaotic, competitive environment where everyone is hiding their true intentions, there is a stable, efficient way to play, and agents can learn to find it through experience.

Technical Summary: Learning to Strategically Acquire Resources in Competition

Problem Definition

This work addresses the problem of multiple strategic agents competing to acquire costly, divisible resources (e.g., financial assets, cloud compute) over a finite time horizon $T$ . Unlike individual optimization problems where agents minimize execution costs in isolation, this setting involves inter-agent strategic behavior where aggregate trading activity endogenously influences market prices and liquidity.

The core challenge lies in the intersection of three factors:

Dynamic Pricing: Prices respond to aggregate demand/supply imbalances, modeled via permanent and temporary market impact.
Heterogeneous Constraints and Objectives: Agents face convex constraints (e.g., no short-selling, inventory limits) and may have diverse objectives, ranging from acquiring a fixed target position to maximizing a general concave utility function of their final position.
Information Asymmetry: Agents often operate with incomplete information regarding market parameters (impact coefficients, exogenous flow) and the types (constraints/valuations) of other participants. Crucially, the paper investigates settings where agents lack a common prior distribution over these unknowns, necessitating learning from repeated interactions.

Methodology

Game-Theoretic Model

The authors formalize a Bayesian game instance characterized by:

Market Dynamics: A price model extending the Almgren & Chriss (2000) framework. The price $p_t$ at time $t$ is determined by a Walrasian dynamic component (permanent impact, coefficient $\alpha$ ) and a temporary impact component (coefficient $\beta$ ) driven by aggregate excess demand $D_t = \sum h_{i,t} + s_t$ .
Agent Types: Each agent $i$ possesses a private type $\theta_i$ determining their feasible strategy set $G_i(\theta_i)$ and value function $f_i$ . Types may be discrete or continuous.
Strategies: A strategy is a mapping from an agent's type to a trading trajectory $h_i: \Theta_i \to \mathbb{R}^T$ . The authors define $(B, L)$ -regular strategy spaces to ensure boundedness and Lipschitz continuity, facilitating learnability.

Analysis with Common Prior (Section 3)

In the setting where all agents share a common prior distribution $P$ over types and market parameters:

Existence and Uniqueness: The authors establish that a unique Bayesian Nash Equilibrium (BNE) exists. This is proven by casting the BNE conditions as a variational inequality in the function space $L_2(P)$ . The operator governing this inequality is shown to be strongly monotone, ensuring a unique, deterministic solution.
Computability: The BNE can be computed efficiently using the extra-gradient algorithm (Korpelevich, 1976), with convergence rates dependent on the strong monotonicity constant and the Lipschitz constant of the operator.
Price of Anarchy (PoA): The paper analyzes the efficiency of the BNE. It demonstrates that PoA can be unbounded in general cases (specifically when agents trade in opposite directions). However, for instances where all agents trade in the same direction (e.g., all buying), the PoA is bounded by $O(n^2 T^2 \gamma^2)$ , where $\gamma$ relates to the ratio of permanent to total market impact.

Learning without Common Prior (Section 4)

The paper extends the framework to a more realistic setting where agents have no knowledge of the prior $P$ and must learn via repeated interaction.

Feedback Model: Agents observe realized price trajectories and estimates of market impact coefficients ( $\hat{\alpha}, \hat{\beta}$ ) at the end of each round. They do not observe the aggregate demand or other agents' actions directly.
Algorithm: The authors propose Algorithm 1, a learning procedure that combines:
1. Type Space Discretization: Continuous type spaces are approximated via a $\delta$ -net to handle infinite-dimensional strategy spaces.
2. Biased Gradient Estimation: Agents reconstruct aggregate demand recursively from price data and estimated parameters. This introduces bias in the gradient estimates.
3. Adaptive Update: The algorithm adapts the update rule of Jordan et al. (2024) to handle these biased gradients and continuous type spaces.
Convergence: The main theoretical result (Theorem 4) proves that if all agents use Algorithm 1, their last-iterate strategies converge to an $\epsilon$ -approximate BNE. The error bound depends on the number of rounds $R$ , the estimation error of market parameters ( $\Delta_\alpha, \Delta_\beta$ ), and the complexity of the type space.

Key Results

Theoretical Guarantees:
- Uniqueness: The BNE is unique and deterministic even under partial information with common priors.
- Convergence: Simultaneous learning dynamics converge to the BNE in the last iterate, even when agents lack a common prior and operate with noisy, biased gradient estimates derived from market feedback.
- Efficiency Bounds: While general PoA is unbounded, specific market conditions (unidirectional trading) yield polynomial bounds on inefficiency.
Empirical Validation:
- Data-Driven Simulation: The authors constructed a Bayesian game instance using real forex data (CAD/USD) from Dukascopy to estimate market impact parameters ( $\alpha, \beta$ ).
- Equilibrium Behavior: Simulations reveal that when temporary impact ( $\beta$ ) is low, agents engage in arbitrage-like behavior (selling initially to dampen price before buying). When $\beta$ is high, strategies converge to a Volume Weighted Average Price (VWAP) execution style, trading proportionally to market volume.
- Learning Performance: In online learning simulations, the strategies generated by Algorithm 1 converged rapidly to the theoretical BNE, with mean-squared error approaching zero significantly faster than theoretical bounds suggested.
Strategic vs. Non-Strategic Interaction:
- In a supplementary analysis (Appendix E), the authors examined markets with a mix of strategic agents and agents following a fixed VWAP rule. They found that while strategic agents could exploit VWAP followers (reducing their own costs), the presence of non-strategic VWAP agents often improved the total system welfare (lowering the sum of all costs) compared to a fully strategic market.

Significance and Claims

The paper claims to provide a general game-theoretic framework for strategic resource acquisition that subsumes and extends prior work in optimal execution and position building (e.g., Chriss, 2024a;b;c; Kearns & Shi, 2025). Its primary contributions are:

Generalization: It accommodates arbitrary convex constraints, concave value functions, and incomplete information without requiring a common prior, addressing limitations in previous models that assumed fixed targets or complete information.
Learning Dynamics: It bridges the gap between equilibrium analysis and practical learning by providing sufficient conditions for last-iterate convergence to BNE in settings where agents learn from realistic, noisy market feedback.
Practical Relevance: By grounding simulations in real financial data and demonstrating convergence, the work offers new insights into how strategic behavior emerges in competitive markets, particularly the transition between arbitrage-driven strategies and VWAP-like execution depending on market impact parameters.

The authors maintain modesty regarding the model's scope, acknowledging that the price dynamics are stylized (linear/quadratic impact) and that real-world microstructures (limit order books) are abstracted. They suggest that future work could explore non-linear impact models and more complex multi-agent reinforcement learning policies that adapt dynamically to history rather than committing to ex-ante trajectories.