Proportional response dynamics

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 B_i 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 b_i. Each buyer also has a utility function u_i.

At each discrete round t, each buyer distributes its entire budget among the available goods, allocating b_ij(t) to each good j, such that all budget is allocated:

$B_{i}=\sum _{j}b_{ij}(t).$

Each good's price is the sum of bids it receives:

$p_{j}(t)=\sum _{i}b_{ij}(t).$

Each buyer then receives a share of the good proportional to their bid:

$x_{ij}(t)={\frac {b_{ij}(t)}{p_{j}(t)}}.$

Let u_ij(t) be the utility buyer i derives from good j at round t. The updated bid in the next round is:

$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: v_A1 = 2, v_A2 = 1
• B: v_B1 = 1, v_B2 = 2

Round 0

Both buyers split bids equally: 0.5 per good. Prices: p₁ = 1.0, p₂ = 1.0. Allocations:

• A: x_A1 = 0.5, x_A2 = 0.5
• B: x_B1 = 0.5, x_B2 = 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 whe each agent i has a CES utility function with parameter $\rho _{i}\leq 1$. The convergence rates depend on the maximum parameter, $\rho _{M}:=\max _{i}\rho _{i}$:

• When $\rho _{M}<1$ (corresponding to strictly concave utility functions), a strong ε-approximate market equilibrium is attained after $O\left({\frac {\log(W/\varepsilon )}{(1-\rho _{M})^{2}}}\right)$ steps, where W is a parameter related to the maximum size of the coefficients in the agents' utility functions.
• When $\rho _{M}=1$ (corresponding to linear utility functions), an ε-approximate market equilibrium is attained after $O\left(W^{3}/\varepsilon ^{2}\right)$ steps.

Birnbaum et al showed that PR is equivalent to mirror descent on a convex program due to Shmyrev. They also generalized the convergence results to agents with linear utilities with spending constraints.

Cheung, Cole and Tao studied two generalizations of PR. One of them a damped generalized PR. They prove that it has a linear rate of convergence for agents with "strict" CES utilities (excluding the linear and Leontief utilities). When linear and Leontief are included, the empirical convergence rate is O(1/T).

Cheung, Hoefer and Nakhe adapted the convergence results of PR to dynamic markets, in which the parameters of agents and goods may change over time.

Yang, Li, Chen and Lin introduce the online PR auction for periodic Fisher markets, in which the properties of goods change over time. They show an upper bound on the buyers' regret.

Kolumbus, Levy and Nisan studied asynchronous PR, where agents update their bids asynchronously with adversarial scheduling (each time, an adversary chooses a subset of the agents and they update their bids). They show convergence when the utilities are linear.

Li and Tang extended PR to a setting in which several goods may belong to the same seller. They show that it still converges. However, the sellers may have an incentive to manipulate the rule.

Brânzei, Mehta and Nisan study PR in a production economy. They proved that PR converges to an unbounded growth process, with users learning the production cycles in a distributed way; but it also leads to high inequality.

Cheung, Cole and Tao showed convergence of PR when agents have gross substitute valuations.

See also

• Dynamic pricing: PR adapts to utility/supply changes.
• Market equilibrium computation
• Tatonnement: PR is large-step and discrete; contrast with price adjustment
• Walrasian equilibrium