Proportional response (PR) dynamics is a decentralized iterative process that, if used by buyers in a Fisher market, converges (under certain assumptions) to a competitive equilibrium. In a Fisher market, each buyer i has a fixed budget Bi and a utility function over bundles of divisible goods; sellers supply fixed quantities of each good. The market equilibrium is a set of prices and allocations where each buyer maximizes utility subject to their budget and all goods clear (supply equals demand). PR dynamics provides a simple, distributed algorithm for reaching such equilibrium without central coordination. PR dynamics were introduced by Wu and Zhang to explain the success of bandwidth sharing in peer-to-peer networks such as BitTorrent. They were later adapted by Zhang to Fisher markets.
Description Each buyer i comes to the market with a fixed budget bi. Each buyer also has a utility function ui.
At each discrete round t, each buyer distributes its entire budget among the available goods, allocating bij(t) to each good j, such that all budget is allocated: B i = ∑ j b i j ( t ) . {\displaystyle B_{i}=\sum _{j}b_{ij}(t).} Each good's price is the sum of bids it receives: p j ( t ) = ∑ i b i j ( t ) . {\displaystyle p_{j}(t)=\sum _{i}b_{ij}(t).} Each buyer then receives a share of the good proportional to their bid:
x i j ( t ) = b i j ( t ) p j ( t ) . {\displaystyle x_{ij}(t)={\frac {b_{ij}(t)}{p_{j}(t)}}.}
Let uij(t) be the utility buyer i derives from good j at round t. The updated bid in the next round is:
b i j ( t + 1 ) = B i ⋅ u i j ( t ) ∑ k u i k ( t ) . {\displaystyle b_{ij}(t+1)=B_{i}\cdot {\frac {u_{ij}(t)}{\sum _{k}u_{ik}(t)}}.}
This ensures buyers spend more on goods that yielded higher utility for them.
Example Consider two buyers (A, B) and two goods (1, 2). Each buyer has budget 1. The buyers have linear utility functions, and their valuations are:
A: vA1 = 2, vA2 = 1 B: vB1 = 1, vB2 = 2
Round 0 Both buyers split bids equally: 0.5 per good. Prices: p1 = 1.0, p2 = 1.0. Allocations:
A: xA1 = 0.5, xA2 = 0.5 B: xB1 = 0.5, xB2 = 0.5 Utilities:
A derives utility 1 from good 1 and utility 0.5 from good 2; B derives utility 1 from good 2 and utility 0.5 from good 1.
Round 1 A bids in ratio 2:1 → bids 2/3 on good 1, 1/3 on good 2. B does the reverse. Prices remain 1.0 for both goods. Allocations:
A gets 2/3 of good 1, 1/3 of good 2. B gets 1/3 of good 1, 2/3 of good 2 Utilities:
A derives utility 4/3 from good 1 and utility 1/3 from good 2. B derives utility 1/3 from good 1 and utility 4/3 from good 2.
Round 2 A bids in ratio 4:1 → bids 4/5 on good 1, 1/5 on good 2. B does the reverse. Prices remain 1.0 for both goods. Allocations:
A gets 4/5 of good 1, 1/5 of good 2. B gets 1/5 of good 1, 4/5 of good 2 We see that the allocation approaches the equilibrium allocation, in which A receives all of good 1 and B receives all of good 2, and their prices are 1.
Main results Zhang proved that PR converges when each agent i has a CES utility function with parameter ρ i ≤ 1 {\displaystyle \rho _{i}\leq 1} . The convergence rates depend on the maximum parameter, ρ M := max i ρ i {\displaystyle \rho _{M}:=\max _{i}\rho _{i}} :
… excerpt ends here. Continue reading the full article.
