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

Smoke Permits for Three Foundries

tradable permits · marginal abatement cost · cost-effectiveness · piecewise linear · corner solution

A valley's foundries must cut their smoke. Foundry i emits emissions[i] tonnes a year. Cutting x tonnes (0 \le x \le emissions[i]; a foundry cannot cut more than it emits) costs it \frac12 k_i x^2 dollars with k_i = slopes[i] > 0, so the cost of cutting one more tonne after x (its marginal abatement cost) is k_i x.

The regulator wants a total cut of target tonnes. It hands out permits for the remaining sum(emissions) - target tonnes, and the foundries trade permits in a competitive market at a price of p dollars per tonne. At price p each foundry chooses its cut x_i to keep its own bill (cost of cutting, plus permits bought or minus permits sold) as low as possible. The permit price is the p >= 0 at which the foundries' cuts add up to exactly target; when target equals all emissions, report the smallest such p.

Write cheapest_cut(emissions, slopes, target) that returns the tuple (price, cuts, cost, equal_cost):

  1. price: the permit price;
  2. cuts: the list of each foundry's cut at that price (floats);
  3. cost: the total cost of those cuts, \sum_i \frac12 k_i x_i^2;
  4. equal_cost: for comparison, the total cost if instead every foundry had to cut the same share target / sum(emissions) of its own emissions.

Examples

Input:  emissions = [40, 30, 50], slopes = [2, 1, 4], target = 60
Output: (40.0, [20.0, 30.0, 10.0], 1050.0, 1762.5)
Explanation: at a price of 40, foundry 0 cuts 20 and foundry 2 cuts 10 (marginal cost 40
each); foundry 1 would like to cut 40 but emits only 30. 20 + 30 + 10 = 60.
Equal shares mean cutting half of each: 20, 15 and 25 tonnes, at a cost of 1762.5.

Input:  emissions = [10, 10], slopes = [1, 3], target = 20
Output: (30.0, [10.0, 10.0], 200.0, 200.0)
Explanation: everything must go; at any price of 30 or more both foundries cut all of it.

Floats are compared with a tolerance of 1e-6.

Goals

  • Find the permit price at which firms' chosen cuts add up to the target
  • Compute the total cost of those cuts and compare it with an equal-share rule
  • Handle firms that cut everything they emit, and targets of zero or all emissions
Starting Python…