Welfare Maximization in the Airplane Problem

Given a set of passengers and a set of airplane seats, the goal of the airplane problem is to sit passengers in seats in a way that maximizes the sum of their total welfare, that is, the total happiness of the passengers in the plane. We aim to maximize their welfare subject to three constraints and how much they care about each constraint being satisfied: a group constraint (where passengers may want to sit together), a constraint on where in a row passengers want to sit (ie a window seat, a middle seat, or an aisle seat), and finally a constraint on where in the plane (closer to the front or to the back of the plane) passengers would like to be seated. In this paper, we argue that valuations of passengers on seats are both superadditive and, more strongly, supermodular, and we are therefore able to employ a greedy framework that maximizes the sum of social welfare for passengers with supermodular valuations on seats.

Recommended citation: Chadwick, A. (2024). "Welfare Maximization in the Airplane Problem." Dartmouth Digital Commons.
Download Paper