I recently faced a dilemma with a group of friends in which auction theory provided a nice solution to ensure everyone's satisfaction. Due to its elegance and potential application to similar coordination problems, I detail the solution below as well as some intuition for why it works.

Scenario

You and $n - 1$ friends are traveling to Spain next week. Due to unforeseen circumstances, the hotel is booked for only $n - 1$ people, hence one person must find other housing. However, because of the short-term notice as well as money constraints, the only option is a hostel where that person must live with others they do not know. No one in the group is eager to live in the hostel as the hotel is particularly nice. How can we fairly pick the hostel-goer?

Intuition

If asked to perform something unpleasant, every person has a minimum amount of compensation they would want in order to perform said task. Thus, we can think to solve the dilemma by providing money to the hostel-goer as consolation. Under this framework, we must decide who is picked to be the hostel-goer and how much compensation they should receive while respecting everyone's interests. A flawed system would allow the hostel-goer to demand compensation exceeding what hotel-stayers are willing to pay.

Interestingly, auction theory provides a solution that guarantees satisfaction for all. In particular, we can think of the scenario as a reverse auction. In a reverse auction, the typical roles are reversed: there is one buyer and several sellers. The sellers compete to sell their good to the buyer. The scenario can be framed as a reverse auction by thinking of everyone in the group as a seller, selling away their right to stay in the hotel. The buyer is the collective group, buying away someone's right to stay in the hotel.

The high-level idea is to pick the hostel-goer through some reverse auction system, providing them with compensation. The remaining hotel-stayers evenly split the payout of the hostel-goer's compensation.

First-Price Sealed-Bid Reverse Auction

The reverse auction can be executed via a first-price sealed-bid reverse auction. Essentially, every person in the group writes the minimum compensation they need to stay in the hostel on a paper slip. This slip is their bid to sell their right to the hotel. Every person submits their slip to a box, while keeping their bid hidden. After everyon...

Posts

Wikitag Contributions

Comments