Research map / Multi-agent systems and games / Games and equilibria
Decentralized Convergence to Equilibrium Prices in Trading Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a decentralized best-response market dynamic where agents negotiate bilateral trade offers, proves almost-sure convergence to equilibrium for 1-sparse markets and 2-sparse fully-substitutable markets, and shows experimentally fast convergence in more general networks.
Problem
Whether competitive equilibrium prices can emerge from uncoordinated bilateral negotiations between agents in general trading networks with fully-substitutable preferences, rather than from a central price-computing algorithm.
Approach
Each agent maintains buying and selling offers for each trade; agents are selected at random and best-respond by matching counterpart offers for demanded trades and offering one step off for others. A reduction from many-agent markets to two-agent markets, via valuation merging and restriction, yields convergence proofs for sparse topologies.
Key results
- Proves 1-sparse markets (even non-FS) and 2-sparse FSMs converge almost surely to equilibrium under the random best-response dynamic.
- Single-trade markets converge after O(V) best responses; two-agent FSMs with two trades after O(V^2).
- Experiments on BS, BIS and general Erdos-Renyi networks (N=100) show convergence in every configuration, with reconvergence after shocks faster than original convergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed best-response dynamic in tree-topology markets, without requiring fully substitutable preferences | Decentralized market dynamic · Tree-topology markets | convergence to equilibrium | Helped |
| Use the proposed best-response dynamic in general networks with cycles | Decentralized market dynamic · General trading networks | convergence to equilibrium | Helped |
| Increase the number of agents | BS networks · BS networks | time to convergence | Hurt |
| Increase the number of intermediaries | BIS networks · BIS networks | time to convergence | Hurt |
| Increase the proportion of buyers | BS networks · BS networks | buyer average utility | Hurt |
| Increase the proportion of buyers | BS networks · BS networks | seller average utility | Helped |
| Increase the number of intermediaries | BIS networks · BIS networks | intermediary utility | Hurt |
| Increase the number of intermediaries | BIS networks · BIS networks | buyer and seller utility | Helped |
| Increase network connectivity rate λ | General trading networks · General trading networks | convergence rate | Hurt |
| Increase the shock magnitude | BS networks after convergence · Shock propagation | proportion of additional non-shocked agents affected | Hurt |
| Shock 25% of agents | BS networks after convergence · Shock propagation | proportion of agents impacted: 25%; approximately 50%+ | Hurt |
| Increase the proportion of shocked agents or shock magnitude | BS networks after convergence · Reconvergence after shocks | additional time to converge | Hurt |
Surprising findings
- Full substitutability is not needed for convergence on tree topologies; 1-sparse markets converge even with arbitrary quasilinear preferences.
- A two-agent market with a complementary seller cycles forever under the dynamic, showing FS is necessary in the maximal-domain sense.
Limitations
- Convergence for general (cyclic) networks and two-agent markets with more than two trades is only conjectured and supported experimentally.
- Experiments use a single good with unit demand and supply and a simple valuation structure.
Experimental setup
Metrics: proportion of satisfied agents over iterations convergence time mean agent utility (welfare) reconvergence speed after shocks proportion of unsatisfied agents after shocks
Baselines: centralized ascending-price algorithm (Hatfield et al. 2013)
Builds on: Hatfield et al. 2013 trading networks substitutes preferences M-natural concavity
Closest papers by meaning
- First-Order Methods for Large-Scale Market Equilibrium Computation (NeurIPS 2020 · similarity 0.87)
- Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets (NeurIPS 2022 · similarity 0.87)
- Walrasian Dynamics in Multi-Unit Markets (AAAI 2019 · similarity 0.86)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.85)
- Fair Online Bilateral Trade (NeurIPS 2024 · similarity 0.84)
- Network Intervention by Polling Strategic Agents (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.