Distributed Computation of Optimal Allocations Through Bilateral Exchange

Robert Axtell and Joshua Epstein
Brookings Institution, Washington
RAxtell@brook.edu

Abstract

The character of allocations arrived at through bilateral trade in a population of truthfully-revealing, neoclassical agents is investigated. Repeated bilateral trade (pure exchange) between randomly-selected pairs of agents, either sequentially or in parallel, approaches an equilibrium allocation. Allocations produced in this way are locally Pareto optimal whenever preferences are convex; globally Pareto optmial when strictly convex. Bilateral trade processes are meaningfully viewed as a kind of distributed computation of near-Pareto optimal allocations. It is argued that such distributed trade processes provide more faithful interpretations of the `invisible hand' than does the first welfare theorem of Walrasian general equilibrium. In contrast to Walrasian equilibria, allocations produced via bilateral trade do not have the `equal treatment' property-agents having identical preferences and endowments will not generally end up with equal welfare. Bilateral trade processes modify the distribution of wealth-while all agents gain utility from trade, some agents gain wealth while others lose it. The exact nature of the equilibria produced via bilateral trade is shown to depend on the fine structure of agent-agent interaction. The variance in the distribution of final agent internal valuations (MRS) is inversely proportional to the number of agents participating in the bilateral trade ``market". In the limit of an infinite number of agents, the distribution of feasible final valuatons has Dirac measure; this may correspond to the Walrasian price. However, the Walrasian allocation has measure zero in the set of bilateral allocations which are consistent with this price. Finally, the computational complexity of bilateral trade is investigated. It is shown that the number of bilateral interactions required to reach Pareto optimality is linear in the number of agents and the number of commodities. It is argued that the non-polynomial complexity of algorithms for the computation of Walrasian equilibria make them unrealistic as metaphors for real markets.