Problem 505629 · medium · Economics · Level 05 Mechanisms and Policy

The Village Fireworks Fund

public good · free riding · Samuelson condition · Nash equilibrium · piecewise linear

A village pays for its midsummer fireworks by voluntary contributions. The show lasts G minutes, and every minute costs c dollars, paid by whoever contributes. Everyone in the village sees the whole show, whoever paid for it: the show is a public good.

Resident i enjoys the show with a marginal benefit (the value in dollars of one more minute when the show already lasts G minutes) of

MB_i(G) = \max(0,\ a_i - b_i G),

so the benefit of a show of length G is B_i(G) = \int_0^G MB_i(x)\,dx. Here a[i] > 0 and b[i] > 0.

  1. Voluntary level. Each resident chooses a contribution g_i \ge 0 (in minutes paid for), and G = \sum_i g_i. Resident i gets B_i(G) - c\,g_i. A Nash equilibrium is a list of contributions where no resident can raise their own payoff by changing only their own contribution. Every equilibrium of this game has the same total G: report it.
  2. Efficient level. The length G^* \ge 0 that maximises the village's total \sum_i B_i(G) - cG. (For a public good this is where the sum of the marginal benefits equals the marginal cost, or 0 if even the first minute is worth less than c to the village as a whole.)
  3. Free riders. The residents who contribute 0 in every equilibrium although the voluntary total is positive, in increasing order (an empty list when the voluntary total is 0).

Write fireworks(a, b, c) that returns the tuple (voluntary, efficient, free_riders), with the two levels as floats.

Examples

Input:  a = [10, 8, 6], b = [1, 1, 2], c = 9
Output: (1.0, 4.5, [1, 2])
Explanation: only resident 0 values a first minute at more than 9 dollars, and only
until 10 - G = 9. Together, (10 - G) + (8 - G) + 0 = 9 at G = 4.5, where resident 2's
benefit has already run out (6 - 2G reaches 0 at G = 3).

Input:  a = [5, 5, 5, 5], b = [1, 1, 1, 1], c = 8
Output: (0.0, 3.0, [])
Explanation: nobody alone pays 8 for a minute worth 5 to them, yet four residents
together value the first minutes at 20.

Floats are compared with a tolerance of 1e-6. To see the kinks of \sum_i MB_i(G), plot it: gs = [k / 10 for k in range(100)], then plot(gs, [sum(max(0, a[i] - b[i] * g) for i in range(len(a))) for g in gs]).

Goals

  • Find the total a group provides when each member chooses their own contribution
  • Find the efficient level where the sum of marginal benefits equals marginal cost
  • Identify the members who free-ride in every equilibrium
Starting Python…