Fair Item Allocation
Have you ever had to divide candy among your picky friends? Perhaps you want to divide an estate among possible heirs. These problems fall into the category of item allocation. Our goal in this problem is to find an allocation that is as fair as possible.
How do we decide what is fair?
At the end of the day, fairness is subjective – each agent has their own priorities. When we wish to model our item allocation problem, we assume that agents have additive utility functions. Simply put, the value of a toy train and a toy truck together is equal to the sum of the values separately. (This assumption doesn’t always hold in the real world: e.g. too much of a good thing decreases its marginal value and some items are worth more in combination, like a pair of shoes.)
One way to define fairness is to ask that each agent prefers what they received to what anyone else receives. This envy-free notion works well when we can divide items arbitrarily, but it fails when items are indivisible. Another popular notion for divisible items is proportionality where each agent requires as 1/n of their total valuation (where n is the number of agents). However, again proportionality is not guaranteed to exist for indivisible items. Think of one laptop and two agents. I can’t give the laptop to both agents, and I can’t cut it in half.
Enter the Maximin Share
For indivisible goods, we turn to the maximin share (MMS) notion of fairness. Here, each agent requests as muc value as they can guarantee for themself if they were to divide items into bundles and then select their least favorite bundle. Intuitively, if there is some skew in the item valuations, MMS accounts for this by focusing on the bundles with the least value. If we have a laptop and two markers to allocate, each agent will request that they receive at least two markers in value. Surprisingly, the MMS notion cannot be guaranteed for all fair division instances.
Approximating MMS
While MMS cannot be guaranteed on its own, multiple approximations of it can be. In my thesis, I studied ordinal approximations of MMS. Essentially, I asked the question of how many agents can be guaranteed their MMS value simultaneously. In this work, I designed new techniques to prove that at least 2/3 of the agents can be guaranteed their MMS value. This marks the first non-trivial guarantee in the setting of ordinal MMS approximations.