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

Apprentices Knock, Workshops Hold

matching · deferred acceptance · Gale-Shapley · stable matching · capacities

A guild places m apprentices in k workshops. Workshop s has seats[s] places, and there are enough seats for everybody. Preferences are strict and complete:

  • app_prefs[a] lists all workshops from apprentice a's favourite to least favourite;
  • shop_prefs[s] lists all apprentices from workshop s's favourite to least favourite.

The guild's clearing house runs in rounds. Apprentices propose; workshops answer.

  1. At the start no apprentice is held anywhere and nobody has been turned down.
  2. In each round, every apprentice who is not currently held by a workshop applies to their favourite workshop among those that have not yet turned them down.
  3. Each workshop then looks at everyone it holds plus its new applicants, keeps the seats[s] it likes best (or all of them, if there are no more than that), and turns down the rest. Being kept is only tentative: a workshop may turn down an apprentice it held earlier when it gets someone it likes more.
  4. When a round ends with every apprentice held, the held apprentices are placed for good.

Write place_apprentices(app_prefs, shop_prefs, seats) that returns the list match where match[a] is the workshop apprentice a is placed in. (The order in which applications within a round are handled does not change the result.)

Examples

Input:  app_prefs  = [[0, 1, 2], [0, 2, 1], [0, 1, 2], [1, 0, 2], [2, 0, 1]]
        shop_prefs = [[3, 1, 0, 2, 4], [0, 2, 4, 1, 3], [4, 3, 2, 1, 0]]
        seats = [2, 1, 2]
Output: [1, 0, 2, 0, 2]
Explanation: in round 1 apprentices 0, 1, 2 apply to workshop 0, which keeps 1 and 0
and turns down 2. Later apprentice 3 is turned down by workshop 1 and bumps
apprentice 0 out of workshop 0, who then bumps apprentice 2 out of workshop 1.

Input:  app_prefs  = [[1, 0], [0, 1], [0, 1]]
        shop_prefs = [[1, 0, 2], [2, 0, 1]]
        seats = [1, 2]
Output: [1, 0, 1]

Goals

  • Run a clearing house's rounds of proposals and tentative acceptances exactly as stated
  • Let a workshop with several seats keep its best proposals so far and release the rest
  • Produce a placement in which no apprentice and workshop would both rather be together
Starting Python…