Integer Allocation

Motivation. As opposed to Fractional Allocation where an item can be infinitely divided (and thus much fairness criteria are satisfied), in a situation where you cannot divide the items it is much harder to find a “fair” allocation. We will try nevertheless; here are a few attempts:

1. Converting fraction allocation to integer allocation
2. Serial Dictatorship
3. Nash Welfare Objective

\mu_{i} is an additive utility function.

Fractional to Integer §

First use fractional, then convert to integer allocation.

Serial Dictatorship §

def. Serial Dictatorship. (Round Robin). The following process of allocation is a SD allocation:

1. Round $i$: Each agent picks favorite item
2. Repeat until all items allocated Properties.

• SD is EF1 (defined and proved below)
• SD is not PO
• Comparable to MMS (bounded; see below) def. Envy-Free without one item (EF1). An allocation is envy-free without one item if:

$$\forall i,j\exists \text{item }g\text{ s.t. }\underset{\text{ i’s alloc.}}{\underbrace{{\mu }_i(S_i)}}\ge {\mu }_i(\underset{\text{ some other’s alloc without g }}{\underbrace{S_j-\{g\}}})$$

Intuition. If $i$ envies $j$’s basket $S_j$ (=traditional Envy) then take out one item $g$, and then $i$ no longer envies $S_j-\{g\}$.

thm. SD is EF1. Proof. For all agent $i$, let’s say $i$ envies $j$.

1. Due to SD game order, $i$’s pick in the $k$-th round will always be preferred to $j$’s pick in the $k+1$-st round. Therefore, $i$ will: $\text{i’s picks from round 1 to finish}{\succ }_i\text{j’s picks from round 2 to finish}$
2. The issue arises because $j$ may pick before $i$ in round $1$. If we simply remove that item, $i$ will not envy $j$ anymore.
3. Therefore, in any pair of agents $i$ envying $j$, removing one item that was picked by $j$ before $i$ in the first round is enough to make $i$ no longer envy $j$. ■ Example.

• $2$ may envy $1$ because $2$ prefers $a$ to $d$, its first pick.
• But $2$ does not envy any other of $1$’s pick, because it picked it.
• Removing $a$ from $1$’s set makes $2$ no longer envy $1$.

Comparison to MMS §

def. Maximin Share (MMS). Imagine first an allocation process where

1. $i$ splits the items first
2. All other agents chooses which item to have
3. $i$ gets the remaining item. In this case, it is in $i$’s best interest to maximize the minimum utility bundle (for itself)‘s utility. Thus we have the definition of MMS as the utility of this maximin bundle:

$${\mu }_i({\text{MMS}}_i):=\underset{\text{ maximize the... }}{\underbrace{{\text{max}}_S}}\underset{\text{ minimum utility bundle }}{\underbrace{\text{min}\{{\mu }_i(S_i)\}}}$$

Example. The blue groups are what each agent splits the items into to maximize their minimum utility. The red circles are an example allocation that give more utility than MMS for every agent. lem. (MMS utility worse than proportional utility). If we allow a fractional allocation on items $T$, a proportional allocation will give utility $\frac{{\mu }_i(T)}{n}$ for agent $i$. On the other hand, if you use (integer) MMS allocation:

$$\begin{array}{rlr}{\mu }_i({\text{MMS}}_i)& =\underset{\text{allocation }S}{\max }\underset{S_i\in S}{\min }{\mu }_i(S_i)& \\ & \le \underset{S}{\max }\underset{\text{ avg. utility of each good }}{\underbrace{\frac{{\sum }_{S_i\in S}{\mu }_i(S_i)}{n}}}& \text{min. < avg.}\\ & =\underset{S}{\max }\frac{{\mu }_i(T)}{n}& \text{max doesn’t apply}\\ & =\frac{{\mu }_i(T)}{n}& \end{array}$$

Therefore we ${\mu }_i({\text{MMS}}_i)\le \frac{{\mu }_i(T)}{n}$ ■

thm. (Serial Dictatorship vs. Proportional vs. MMS) Let $S_i$ be a serial dictatorship allocation. For agent $i$, let ${\mu }_i^{\max }$ be a single item that $i$ values the most. Then:

$$\underset{\text{ SD }}{\underbrace{{\mu }_i(S_i)}}+{\mu }_i^{\text{max}}\ge \underset{\text{ prop }}{\underbrace{\frac{{\mu }_i(T)}{n}}}\ge {\mu }_i({\text{MMS}}_i)$$

Proof. Model the round robin with $n$ agents and items from set $T$, s.t. we call round 1 starting with agent $i$. All items allocated before $i$ in round 1, let $T_0$. These are ignored for now. Let the items allocated to agents in round $k$ be $T_k$. Let ${\mu }_i^{(k)}$ be the utility to agent $i$ by the single item allocated to $i$ on round $k$. For agent $i$ in every round:

$$\begin{array}{rlr}{\mu }_i^{(k)}& \ge \underset{t\in T_k}{\max }{\mu }_i(t)& \\ & \ge \frac{{\mu }_i(T_k)}{n}& \text{max}\ge \text{avg.}\\ \sum _{{\forall }_k}{\mu }_k^{(k)}& \ge \sum _{\forall k}\frac{{\mu }_i(T_k)}{n}& \end{array}$$

Now, consider the ignored items $T_0$. We can easily establish that:

$$\begin{array}{rlr}{\mu }_i(T_0)& =|T_0|\underset{\text{ avg. }}{\underbrace{\frac{{\mu }_i(T_0)}{|T_0|}}}& \\ & \le |T_0|\underset{t\in T_0}{\max }{\mu }_i(t)& \text{avg.}\le \max \\ & \le n\cdot \underset{t\in T_0}{\max }{\mu }_i(t)& \\ & \le n\cdot \underset{t\in T}{\max }{\mu }_i(t)& \end{array}$$

Continuing on from above:

$$\begin{array}{rl}\sum _{{\forall }_k}{\mu }_k^{(k)}& \ge \frac{{\sum }_{\forall k}{\mu }_i(T_k)}{n}\\ {\mu }_k(\underset{\text{ SD alloc }}{\underbrace{S_i}})& \ge \frac{{\mu }_i(T\setminus T_0)}{n}=\frac{{\mu }_i(T)-{\mu }_i(T_0)}{n}\\ & \\ & \ge \frac{\mu (T)-n{\max }_{t\in T}{\mu }_i(t)}{n}=\frac{{\mu }_i(T)}{n}-\underset{t\in T}{\max }{\mu }_i(t)\end{array}$$

Thus we have the final inequality w.r.t proportional allocation and thus MMS (due to theorem before).

$${\mu }_i(S_i)+\underset{t\in T}{\max }{\mu }_i(t)\ge \frac{{\mu }_i(T)}{n}\ge {\mu }_i({\text{MMS}}_i)$$

■

thm. (Alternative SD vs MMS) Serial Dictatorship allocation $S_i$ satisfies for each agent that:

$${\mu }_i(S_i)\ge \frac{1}{2}{\text{MMS}}_i$$

Proof.

■

Integer Nash Welfare §

def. Integer Nash Welfare. For integer allocation $x$, Nash welfare is:

$$\text{Nash Welfare}:=\underset{\text{ product of everybody }}{\underbrace{\prod _i}}\underset{\text{ Sum a person’s utility }}{\underbrace{\sum _j{\mu }_{ij}{x}_{ij}}}$$

• NP hard to compute
• …but satisfies EF1

thm. (Integer Nash Welfare objective satisfies EF1). Proof. Suppose in the allocation $S$, $i$ envies $j$ even remove one item. Now, choose $g^{\ast }$ as the most bang-for-buck item to move from $S_j$ to $S_i$:

$$g^{\ast }:={\text{argmin}}_{g\in S_j}\frac{{\mu }_j(g)}{{\mu }_i(g)}$$

And we also note the inequality (1):

$$\frac{{\mu }_j(g^{\ast })}{{\mu }_i(g^{\ast })}\le \frac{{\mu }_j(S_j)}{{\mu }_i(S_j)}$$

Now per our assumption, $i$ still envies $S_j\setminus \{g^{\ast }\}$:

$$\begin{array}{rlr}{\mu }_i(S_i)& <{\mu }_i(S_j)-{\mu }_i(g^{\ast })& \\ {\mu }_i(S_i)+{\mu }_i(g^{\ast })& <{\mu }_i(S_j)& \text{multiply by }\frac{{\mu }_j(g^{\ast })}{{\mu }_i(g^{\ast })}\\ \frac{{\mu }_j(g^{\ast })}{{\mu }_i(g^{\ast })}({\mu }_i(S_i)+{\mu }_i(g^{\ast }))& <\underset{\text{ by inequality (1) }}{\underbrace{\frac{{\mu }_j(g^{\ast })}{{\mu }_i(g^{\ast })}{\mu }_i(S_j)\le \frac{{\mu }_j(S_j)}{{\mu }_i(S_j)}{\mu }_i(S_j)}}& \\ & ={\mu }_j(S_j)& \\ \frac{{\mu }_j(g^{\ast })}{{\mu }_i(g^{\ast })}{\mu }_i(S_j)& \le {\mu }_i(S_j)& \text{inequality (2)}\end{array}$$

Now, on the other hand, since $S_i,S_j,\dots$ are NW allocations, it is the maximum product:

$$\begin{array}{rlr}{\mu }_i(S_i){\mu }_j(S_j)& \ge \underset{\text{ give to i }}{\underbrace{({\mu }_i(S_i)+{\mu }_i(g^{\ast }))}}\underset{\text{ remove from j }}{\underbrace{({\mu }_j(S_j)-{\mu }_j(g^{\ast }))}}& \\ {\mu }_j(g^{\ast })({\mu }_i(S_i+{\mu }_i(g^{\ast })))& \ge {\mu }_j(S_j){\mu }_i(g^{\ast })& \text{expand and simplify}\\ \frac{{\mu }_j(g^{\ast })}{{\mu }_i(g^{\ast })}(\underset{\le {\mu }_i(S_j)\text{since I }}{\underbrace{{\mu }_i(S_i)+{\mu }_i(g^{\ast })}})& \ge {\mu }_j(S_j)& \end{array}$$

■