Problem 697805 · medium · Economics · Level 06 Dynamics and General Equilibrium

Random Pairs in the Grain Pit

agent-based model · random matching · gains from trade · allocative efficiency · seeded simulation

In the grain pit of Vessa, each buyer wants one sack and would pay at most her value for it; each seller has one sack and will sell for no less than his cost. Instead of a single market price, traders meet in random pairs. Simulate this market exactly as follows, with one random generator rng = random.Random(seed):

  1. Draw the values [rng.randint(lo, hi) for _ in range(n_buyers)], then the costs [rng.randint(lo, hi) for _ in range(n_sellers)]. Buyer i has values[i], seller j has costs[j].
  2. Keep the numbers of the buyers and the sellers still in the market, each list in increasing order (at the start [0, 1, ..., n_buyers - 1] and [0, 1, ..., n_sellers - 1]).
  3. Each round: rng.shuffle the buyer list, then the seller list. Pair the first buyer with the first seller, the second with the second, and so on (extra traders on the longer list sit the round out). A pair trades when the buyer's value is at least the seller's cost, at the price (value + cost) / 2; both then leave the market. After the round, the traders still in the market go back into increasing order of their numbers.
  4. Run rounds rounds.

A trade creates a surplus of value - cost. The largest possible surplus pairs the highest values with the lowest costs: sort the values from high to low and the costs from low to high, and add up value - cost over the pairs in that order while it is positive. The market's efficiency is the surplus it actually created divided by that largest possible surplus.

Write grain_pit(n_buyers, n_sellers, lo, hi, rounds, seed) that returns a tuple (trades, mean_price, efficiency): the number of trades, the average trade price (None if there were no trades), and the efficiency (None if the largest possible surplus is 0).

Examples

Input:  n_buyers = 4, n_sellers = 4, lo = 1, hi = 10, rounds = 1, seed = 7
Output: (3, 4.33333333, 0.66666667)
Explanation: values [6, 3, 7, 1], costs [2, 9, 2, 6]. The round pairs values and costs
3-2, 1-9, 7-6 and 6-2: three trades at 2.5, 6.5 and 4, surplus 1 + 1 + 4 = 6.
At best 7-2 and 6-2 would have made 9.

Input:  n_buyers = 6, n_sellers = 6, lo = 1, hi = 20, rounds = 3, seed = 9
Output: (5, 10.9, 0.46875)

Input:  n_buyers = 0, n_sellers = 5, lo = 1, hi = 10, rounds = 3, seed = 1
Output: (0, None, None)

Constraints

  • mean_price and efficiency are compared with a tolerance of 1e-6

Goals

  • Simulate a market of individual traders who meet in random pairs, following a stated procedure exactly
  • Measure the largest possible gains from trade by sorting values and costs
  • Compare the realised surplus with that maximum: the market's efficiency
Starting Python…