A town leases its summer market stalls, named by the letters A to H, in one auction. Traders often want several stalls together (a fishmonger needs two side by side), so they bid on bundles. Each bid is a tuple (trader, bundle, amount): the trader's name, a string of distinct stall letters, and what the whole bundle is worth to them in dollars. A trader may send several bids; they are alternatives (the trader wants at most one of those bundles).
Allocation. The town accepts a set of bids such that no stall is in two accepted bids and no trader has two accepted bids. The welfare of the set is the sum of its amounts. The town picks the set with the largest welfare; if several sets tie, it picks the one whose sorted list of bid indices is smallest in Python's list order (so [0, 3] beats [1, 2]). Accepting no bids at all (welfare 0) is allowed.
Payments (VCG). A trader with no accepted bid pays nothing. A trader t whose bid was accepted pays the harm their presence does to everyone else:
where W is the chosen welfare, v_t is the amount of t's accepted bid, and W_{-t} is the largest welfare the town could reach if all of t's bids were thrown away. With these payments, bidding one's true values is a safe strategy, as in a second-price auction.
Write vcg_auction(bids) that returns the tuple (accepted, welfare, payments): the sorted list of accepted bid indices, the welfare, and a dict mapping each trader with an accepted bid to their payment.
Examples
Input: bids = [("ana", "AB", 10), ("ben", "A", 6), ("cai", "B", 5)]
Output: ([1, 2], 11, {'ben': 5, 'cai': 4})
Explanation: ben and cai together (11) beat ana (10). Without ben the best is ana's 10,
while the others get 5 in the chosen set: ben pays 10 - 5 = 5. Likewise cai pays 10 - 6 = 4.
Input: bids = [("dora", "A", 7), ("dora", "B", 6), ("eli", "AB", 9), ("finn", "B", 4)]
Output: ([0, 3], 11, {'dora': 5, 'finn': 2})
Explanation: dora cannot win both stalls (13), so dora's A with finn's B is best.
Input: bids = [("pia", "A", 3), ("quin", "B", 3), ("rafa", "AB", 6)]
Output: ([0, 1], 6, {'pia': 3, 'quin': 3})
Explanation: [0, 1] and [2] both reach 6; [0, 1] is the smaller list.
Goals
- Choose the set of compatible package bids with the largest total value by exhaustive search
- Break ties between equally valuable allocations by a stated rule
- Charge each winner the harm they do to the others (Vickrey-Clarke-Groves payments)