Decentralized Convergence to Equilibrium Prices in Trading Networks
Authors: Edwin Lock, Benjamin Patrick Evans, Eleonora Kreacic, Sujay Bhatt, Alec Koppel, Sumitra Ganesh, Paul W. Goldberg
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our main technical contribution is a reduction from markets with arbitrarily many agents to 2-agent markets (Proposition 9). This reduction guarantees that FSMs with m-sparse networks converge (almost surely) to equilibrium iff FSMs with two agents and m trades converge (almost surely).1 As we show that 2-agent FSMs with one or two trades converge (Proposition 5), our reduction thus implies that markets with tree topologies and 2-sparse FSMs reach equilibrium under our market dynamic. We conjecture, based on our experimental evidence, that m-sparse FSMs converge for any m > 2. Surprisingly, we see that full substitutability is not required to guarantee convergence for markets with tree topologies; agents can have arbitrary quasilinear preferences (Theorem 10). By contrast, we give a counterexample of a two-agent market with a non-fully-substitutable agent for which the dynamic does not terminate. Section 4 complements our theoretical results with multi-agent simulations to develop a better quantitative understanding of convergence in our market dynamic.2 Specifically, we demonstrate the convergence, and speed of convergence, in markets with tree topologies, and move beyond the theoretical results to also demonstrate convergence in general (graph-based) markets. We explore numerous market configurations, including various market sizes and agent compositions, to analyze convergence and equilibrium properties. |
| Researcher Affiliation | Collaboration | Edwin Lock1, Benjamin Patrick Evans2, Eleonora Kreacic2, Sujay Bhatt3, Alec Koppel3, Sumitra Ganesh3, Paul W. Goldberg1 1Department of Computer Science University of Oxford Parks Road Oxford, OX1 3QD, UK 2JPMorgan AI Research London, UK 3JPMorgan AI Research New York, USA EMAIL EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Market dynamic. 1: Initialize buying and selling offers σ for all trades. 2: Let U = I be the set of unsatisfied agents. 3: while U = do 4: Sample an agent i U uniformly at random. 5: Let p ZΩi with pω = σ i ω for all ω Ωi be the offers facing agent i. 6: Determine the unique bundle Ψ Di(p) demanded by agent i at prices p [cf. (2)]. 7: Update agent i s offers to σi ω = pω for ω Ψ and σi ω = pω χi ωε for ω Ωi Ψ. 8: Remove agent i from U. 9: Add all agents j = i facing modified offers to U. 10: return final offers σ. |
| Open Source Code | No | For the code and implementation details, we refer to the extended version of this paper, available at https://arxiv.org/abs/2412.13972. |
| Open Datasets | No | We assume one kind of good, and that sellers and buyers have unit supply/demand for this good, i.e., they want to buy/sell at most one item of this good8. Each buyer and seller s value ci C for an item of this good is drawn uniformly at random from a predetermined set of integers, C = {1, . . . , 100}. For the seller, the value can be understood as the production cost, and for a buyer, their perceived fundamental value of the good. The valuation function of a buyer i is given by vi( ) = 0, vi(Ψ) = ci if |Ψ Ωi| = 1 and vi(Ψ) = otherwise. For sellers, we have vi( ) = 0, vi(Ψ) = ci if |Ψ Ωi| = 1 and vi(Ψ) = otherwise. Intermediaries cannot sell more than they buy, and have no value for retaining items, so their valuation is vi(Ψ) = 0 if Ψi contains the same number of buying and selling trades, and vi(Ψ) = otherwise. Environments are configured in Phantom (Ardon et al. 2023). |
| Dataset Splits | No | The paper describes generating synthetic data for simulations (e.g., agent values drawn uniformly at random from a set of integers, network topologies generated) but does not provide information on how these generated datasets were split into training, validation, or test sets in a conventional sense. |
| Hardware Specification | Yes | Each configuration is run 100 times on a standard personal computer9, with the mean standard deviation presented. 9Run with Python 3 on a 2022 Macbook Air M2 with 8GB RAM. |
| Software Dependencies | No | Run with Python 3 on a 2022 Macbook Air M2 with 8GB RAM. Environments are configured in Phantom (Ardon et al. 2023). |
| Experiment Setup | Yes | We assume one kind of good, and that sellers and buyers have unit supply/demand for this good... Each buyer and seller s value ci C for an item of this good is drawn uniformly at random from a predetermined set of integers, C = {1, . . . , 100}... The dynamic then selects one agent i I at a time, uniformly at random, to update her offers by a discrete step size, ε N.6 Without loss of generality, we will assume ε = 1 throughout... For these experiments, we generate Erd os-R enyi networks with connectivity rates r = λ N , where N = 100 and λ = {1, 1.5, 2, 2.5, 3}... Shocks have a specific size s, which controls the variation from the original valuation, i.e., a shock size of 0.1 means the updated ci,t will be in the range [ci,t 1 0.9, ci,t 1 1.1] (clipped to the values in C). |