Maximin Fair Allocation of Indivisible Items under Cost Utilities

We define a sequence $S$ of agents of length $n+2$, and a sequence $T$ of agents where every agent appears exactly once. Let $S=1,2,\dots,n-1,n,n,n$, and $T=n,n-1,...,2,1$. Our picking sequence is $S$, followed by $m$ copies of each element in the sequence $T$. We can think of this as running through $S$, then letting each agent in $T$ choose all the items they want when it is their turn in $T$. We now show that this gives us a strategyproof mechanism.

It is immediately clear that agent $n$ has no incentive to manipulate. They cannot move themselves up in the picking sequence, and once it is their turn, they can essentially grab all the items they want.

For any other agent $i\in N$, let $X_{i}$ be the items remaining immediately before agent $i$ received their first item, and let $x$ be the item with highest cost in $X_{i}\cap A_{i}$. Then, agent $i$ receives $x$. After this, all items in the approval sets of agents $i+1,i+2,...,n$ are allocated before agent $i$ receives all remaining items in $A_{i}$. Thus, agent $i$ receives the bundle $x\cup(A_{i}\cap(X_{i}\setminus(A_{i+1}\cup A_{i+2}\cup...\cup A_{n})))$. Note that the preferences of agent $i$ do not decide the set $X_{i}$. Hence, by misreporting, agent $i$ is unable to gain any additional items that they approve.

Note that the final allocation is Pareto optimal because items are only allocated to agents that want them. As agents have cost utilities, all agents who want an item will value it the same. This concludes the proof.∎

Note that for any $n$-partition of the items in $A_{i}$, there is at most $k$ bundles that are not singletons, meaning at least $(n-k)$ of the bundles have just a single item. Any of these bundles will give agent $i$ their maximin fair share. Of these $(n-k)$ singleton bundles, the highest possible value for the lowest valued bundle is the cost of the $(n-k)$-th most valuable item in the agent’s approval set.

We first show that there is a picking sequence such that Sequential Allocation returns an MMS allocation. If an agent approves fewer than $n$ items, they still receive their maximin fair share even when no items are allocated to them. We therefore focus on agents who approve at least $n$ items. We define the picking sequence based on the cost of the items in $M$.

• $\blacktriangleright$

  If $c(g_{4})>c(g_{2})+c(g_{3})$, our picking sequence is $1,2,\dots,n-1,n,n,n$.

• $\blacktriangleright$

  Otherwise, our picking sequence is $1,2,\dots,n-1,n,n,n-1$.

We now consider what happens when agent $n$ approves $n+k$ items—for $k\in\{1,2\}$), and when agent $(n-1)$ approves $n+2$ items. We look at each potential picking sequence separately.

Case 1: Suppose $c(g_{4})>c(g_{2})+c(g_{3})$. If agent $n$ approves $n+k$ items, they will receive at least $k+1$ items, as they pick last and can pick up to three items if they want, given the picking sequence $1,2,\dots,n-1,n,n,n$. Clearly a bundle of size $k+1$ guarantees them their maximin fair share.

What remains is to check what happens when agent $(n-1)$ approves all items in $M$, so suppose this to be the case. We first show that the maximin fair share of agent $n-1$ is $\min(c(\{g_{1},g_{2},g_{3}\}),c(g_{4}))$. Consider a partition $\boldsymbol{B}$ of $M$ into $n$ bundles, where $c(B_{i})\geq\mathsf{MMS}^{n}_{n-1}(M)$ for each $i\in N$. At least $n-2$ of these bundles must contain a single item, and so we know that either i) $n-2$ bundles contain one item and two bundles contain two items, or ii) $n-1$ bundles contain one item and one bundle contains three items. We know that $c(g_{4})>c(g_{2})+c(g_{3})$ by assumption, and the non-singleton bundles will be made up of the four lowest value items—$g_{1},\dots,g_{4}$. Then the best we can do is one $3$-item bundle $B=\{g_{1},g_{2},g_{3}\}$ and all the remaining items in singleton bundles. It follows that the maximin fair share of agent $n-1$ is $\min(c(B),c(g_{4}))$. When it is agent $n-1$’s turn to pick, in the worst case, the only remaining goods will be $g_{1},\dots,g_{4}$, in which case agent $n-1$ can pick item $g_{4}$ to guarantee their maximin fair share.

Case 2: Suppose instead that $c(g_{4})\leq c(g_{2})+c(g_{3})$. If agent $n$ approves $n+1$ items, they will receive two items, guaranteeing them their maximin fair share. If agent $n$ approves all items in $M$, their maximin fair share in this case is determined by the lowest value bundle between the two bundles of size two, and the cheapest singleton. In particular, agent $n$’s maximin fair share is $\min(c(\{c_{1},c_{4}\}),c(\{c_{2},c_{3}\}),c(\{g_{5}\}))$. With this picking sequence, agent $n$ receives two items and in the worst case, this will be the bundle $B=\{g_{2},g_{3}\}$. Clearly this guarantees agent $n$ their maximin fair share.

Finally, we look at when agent $(n-1)$ approves $n+2$ items. In this case, we know that their maximin fair share is determined by $\min(c(\{g_{1},g_{4}\}),c(\{g_{2},g_{3}\}),c(\{g_{5}\}))$, as was the case for agent $n$. As we did for agent $n$ we know that agent $(n-1)$ will receive two items, and in the worst case this will be the bundle $B=\{g_{4},g_{1}\}$, which gives the agent their maximin fair share.

Strategyproofness and Pareto efficiency for the first case follows directly from Proposition 1. We now prove strategyproofness and Pareto efficiency for the second case, where $c(g_{4})\leq c(g_{2})+c(g_{3})$. In this case, our picking sequence is $1,2,\dots,n-1,n,n,n-1$.

For any agent $i\in N$, if $i<n-1$, it is clear that there is no way for the agent to manipulate as they only get one pick. For agent $n$, because their picks are right after each other, they also have no incentive to manipulate. Thus, we need only consider agent $n-1$. Let $X$ be the items remaining immediately before agent $n-1$ received their first item, and let $x$ be the item with highest cost in $X\cap A_{n-1}$. Agent $n-1$ will pick $x$ by definition of the mechanism. Agent $n$ then receives their two highest valued remaining items if they exist (call these items $y$ and $y^{\prime}$), and then finally agent $n-1$ potentially receives the last item they approve (call this item $z$).

First, consider the case where agent $n-1$ misreports that they approve some item $x^{\prime}$, and they receive $x^{\prime}$ instead of $x$. Then, the bundle of agent $n-1$ will consist of $x^{\prime}$ (which they value at 0), and potentially some other item $z^{\prime}$ with $v_{n-1}(z^{\prime})\leq v_{n-1}(x)$. Thus, agent $n-1$ is not better off in this case. Otherwise, if agent $n-1$ instead misreports that they do not approve item $x$, then they will pick some other item $x^{\prime\prime}$ instead, where $c(x^{\prime\prime})\leq c(x)$. If $x^{\prime\prime}\neq y$ and $x^{\prime\prime}\neq y^{\prime}$, then we must have $v_{n-1}(x^{\prime\prime})\leq v_{n-1}(z)$, and so agent $n-1$ is not better off. Otherwise, if $x^{\prime\prime}=y$ or $x^{\prime\prime}=y^{\prime}$, then agent $n-1$ will have strictly fewer options for their final pick (compared to the case where they do not misreport), and so they are still not any better off.

Therefore, the mechanism is strategyproof. It is clear that no agent is assigned an item they do not want, and all items that are wanted by at least one agent are assigned to someone. Thus the allocation is Pareto efficient. ∎

Let $n=2$, and $M=\{g_{2},g_{3},g_{4},g_{5},g_{6}\}$ such that $c(g_{i})=i$. We will show that no allocation mechanism can satisfy strategyproofness while also guaranteeing a Pareto Efficient MMS allocation. Our aim is to start from an instance $\mathcal{I}_{1}$ and—by repeatedly applying the three axioms—reach a contradiction.

First, consider the instance $\mathcal{I}_{1}$, where both agents approve all items—this corresponds to the top row of Table 1. Then, their maximin fair share is $10$, and the only way to reach an MMS allocation is to give $g_{4}$ and $g_{6}$ to one agent, and $g_{2},g_{3}$ and $g_{5}$ to another. Suppose without loss of generality that $\{g_{2},g_{3},g_{5}\}$ is allocated to agent $1$, and $\{g_{4},g_{6}\}$ is allocated to agent $2$. We will consider $5$ further instances.

$\mathcal{I}_{2}$ differs only on agent $2$’s approval set—they now only approve items $g_{4}$, $g_{5}$, and $g_{6}$. By strategyproofness, agent $2$ must still receive a bundle she values at $10$. If this were a higher value the agent could manipulate from $\mathcal{I}_{1}$, and if it were lower, they could manipulate from $\mathcal{I}_{2}$ to $\mathcal{I}_{1}$.

Instance $\mathcal{I}_{3}$ differs from instance $\mathcal{I}_{2}$ only on agent $1$’s approval set—they now only approve items $g_{3}$, $g_{4}$, $g_{5}$, and $g_{6}$. As agent $1$ is the only one approving item $g_{3}$, they must be allocated this item by Pareto efficiency. The maximin value of agent $1$ in this instance is $9$, so they must receive one of the following bundles: $\{(g_{3},g_{6}\}$, $\{g_{3},g_{4},g_{5}\}$, $\{g_{3},g_{4},g_{6}\}$, $\{g_{3},g_{5},g_{6}\}$, or $\{g_{3},g_{4},g_{5},g_{6}\}$. All but $\{g_{3},g_{6}\}$ break strategyproofness, as agent $1$ would have an incentive to manipulate from $\mathcal{I}_{2}$ to $\mathcal{I}_{3}$.

Instance $\mathcal{I}_{4}$ differs from instance $\mathcal{I}_{3}$ only on agent $1$’s approval set—they now only approve item $g_{6}$. Agent $1$ must be allocated $g_{6}$. If this were not the case, they would have an incentive to manipulate from $\mathcal{I}_{4}$ to $\mathcal{I}_{3}$ as they do receive item $6$ in that instance.

Instance $\mathcal{I}_{5}$ differs from instance $\mathcal{I}_{4}$ only on agent $1$’s approval set—they now approve items $g_{2}$, $g_{3}$ and $g_{6}$. As agent $1$ is the only one approving items $g_{2}$ and $g_{3}$, they must be allocated these items by Pareto efficiency. If agent $1$ is not also given $g_{6}$, they would have an incentive to manipulate from $\mathcal{I}_{4}$ to $\mathcal{I}_{3}$ as their bundle in that instance is valued at $6$ (which is greater than $2+3$, the value of the bundle $\{g_{2},g_{3}\}$). Note that this gives them a bundle valued at $11$.

Finally, instance $\mathcal{I}_{6}$ differs from instance $\mathcal{I}_{5}$ only on agent $1$’s approval set—they now approve all items. If agent $1$ is given a bundle valued lower than $11$, they would have an incentive to manipulate from $\mathcal{I}_{6}$ to $\mathcal{I}_{5}$. Note however that $\mathcal{I}_{6}=\mathcal{I}_{2}$, and our axioms dictated in that instance that agent $1$ must receive utility of $10$. This gives us our contradiction.