Problem 441877 · medium · Economics · Level 04 Strategy and Growth

Undercut by a Cent

Bertrand competition · Nash equilibrium · best response · price competition · discrete prices

Each autumn a town council buys units bags of road salt. Several suppliers, all selling the same salt, each submit a price per bag in whole cents, at the same time: supplier i bids prices[i] and has a constant cost of costs[i] cents per bag. Any bid from 0 to 5000 cents is allowed. The rules of the tender:

  • The council pays at most ceiling cents a bag; bids above ceiling are rejected.
  • Among the bids at or below ceiling, the lowest bid wins all units bags. If k suppliers tie at that lowest bid, each sells units / k bags (units is a multiple of 60, so every share is a whole number). If no bid is at or below ceiling, nobody sells.
  • Supplier i earns the profit (prices[i] - costs[i]) * bags_sold, which is negative if it sells below cost, and 0 if it sells nothing.

Supplier i's best deviation profit is the highest profit it could get by changing its own bid to any whole number of cents from 0 to 5000 (keeping its current bid is allowed), while the other bids stay as they are. The bids form a (Bertrand) Nash equilibrium when no supplier's best deviation profit is strictly higher than its current profit.

Write salt_tender(costs, prices, ceiling, units) that returns a tuple (profits, best, equilibrium): the list of current profits, the list of best deviation profits, and True or False.

Examples

Input:  costs = [30, 45], prices = [44, 45], ceiling = 100, units = 60
Output: ([840, 0], [840, 0], True)
Explanation: supplier 0 wins at 44 and earns 14 * 60. Matching 45 would earn only
15 * 30 = 450. Supplier 1 cannot win without selling below its cost of 45.

Input:  costs = [30, 45], prices = [45, 45], ceiling = 100, units = 60
Output: ([450, 0], [840, 0], False)
Explanation: supplier 0 shares the order at 45 but would earn 840 by bidding 44.

Input:  costs = [30, 30], prices = [31, 31], ceiling = 100, units = 60
Output: ([30, 30], [30, 30], True)
Explanation: undercutting to 30 earns nothing; bidding 32 loses the order. One cent
above cost is an equilibrium when prices move in whole cents.

Goals

  • Compute each firm's sales and profit when the lowest price takes the whole market
  • Find a firm's best unilateral deviation over a grid of prices
  • Decide whether a price profile is a Bertrand equilibrium, and see that the low-cost firm prices just under its rival's cost
Starting Python…