Maximally-Proportional Allocation

This algorithm tries to divide a set of indivisible items among n agents as “fairly” as possible in the following sense:

  1. Proportional share first. Each agent should, if possible, receive a bundle they value at least 1/n of their total value over all items.
    For example: Given 2 agents and total valuation of 100 each, each agent should get a bundle which he values at least 50.
  2. Maximise how many agents achieve that. Among all allocations, pick one that satisfies the largest number of agents with a proportional bundle.
  3. Then maximise the worst satisfied agent’s happiness. Within that set, choose an allocation that makes the least-happy proportional agent as happy as possible (formally: maximise the minimum rank any satisfied agent assigns to their own bundle).

The result is one Pareto-optimal allocation meeting those three criteria. Pareto-optimal in a sense that there is no other allocation that benfeits at least one agent without harming any other agent.