Ordinal Allocation

Motivation. We move on from cardinal allocations where the Utility Function is numerically defined, into a situation where there is only an ordinal ranking by the agents. This is more realistic in real life, since most people are able to identify which item they prefer even if they can’t assign it a numerical utility value. In order for any of this to be remotely fair, we need to allow probabilistic allocation. This means that the allocation solution $P$ is for each item $a$ and agent $i$, gives a probability $P_{i,a}$ that the item is allocated to the agent:

$$P_{i,a}:=\mathbb{P}(\text{a is allocated to i})\text{s.t.}\sum _{\forall a}{P}_i=1$$

For convenience, let’s also define a cumulative distribution function, for each agent.

$$P_i(t)=\sum _{a⪯t}P(a)$$

We might visualize two different allocation $P,Q$ for which for agent $i$ the cumulative allocation function $P_i,Q_i$ is visualized like this:

Now we can define a few properties of baysian allocations.

def Stochastic Dominance (SD). Allocation $P_i$ stoastically dominates distribution $Q_i$ for agent $i$ iff

$$\nexists a\text{ such that }\underset{\text{ probability to get at least a or better }}{\underbrace{\sum _{a^{\prime }>a}{P}_i(a^{\prime })}}<\sum _{a^{\prime }>a}{Q}_i(a^{\prime })$$

Example. Agents $\mathrm{1..4}$ want items $a,b$ with the preferences shown below.

• First allocation $P$ is stochastically dominated by second allocation $Q$ for agents $1,2$ because:

Probability under..	$a$	$a\vee b$	$a\vee b\vee \varnothing$ (=get sth)
$P$	$\frac{5}{12}$	$\frac{6}{12}$	$1$
$Q$	$\frac{1}{2}$	$\frac{1}{2}$	$1$

There is no item where getting $P$ gets clearly better than $Q$. Therefore $Q$ stochastically dominates $P$.

def. (Preferences in Ordinal Allocation) This is how we define preferences in ordinal situations. $P$ stochastically dominates $Q$ for $i$ is equivalent to saying $P{\succ }_{i}Q$.

• ! But note that we cannot say anything about indifference. Stochastic dominance is defined over a partial ordering (we won’t go into more detail) which means there cannot be two different sets $i$ is indifferent about.

We define Fairness (Economics) in the following ways:

def Ordinal Efficiency (OE). Allocation $P$ is pareto-optimal when there does not exist any other allocation $Q$ which is a pareto improvement than $P$:

• Nobody are worse off: $\forall i,Q_i⪰P_i$
• Some are improved: $\exists i^{\ast }{Q}_{i^{\ast }}\succ P_{i^{\ast }}$

def. Ex-Post Pareto Optimality. Allocation $P$ is Ex-post PO when every possible matching in the distribution $P$ is Ordinally Efficient.

There are two definitions of envy-freeness in probabilistic allocations:

• def. Weak Envy-Free (WEF). Allocation $P$ is WEF when there exists no $P_j$ that stochastically dominates for $P_i$.
• def. Strong Envy-Free (SEF). Allocation $P$ is SEF when it stochastically dominates all other agent’s allocation.

Random Dictatorship §

• Proofs of various ordinal allocation schemes#task

thm. RD is DSIC. Trivially. You are best off when you choose your item on the first try. Induction.

thm. RD is Ex-post PO. Trivially. If there are at least as many agents as items, then every agent picks their favorite among that’s left, and nobody can really improve by swapping. Induction.

thm. RD is WEF. (will not prove)

thm. (Not strong envy-free.) Counterexample.

• agent $1$’s allocation’s cumulative allocation is $\left(\frac{1}{2},\frac{4}{6},1\right)$
• agent $3$’s allocation’s cumulative allocation w.r.t. $1$’s preferences is $\left(0,\frac{5}{6},1\right)$

thm. (RD is not ordinally efficient.) Counterexample. (Same example from above)

Proportional Eating §

thm. PE is not truthful. Counterexample.

thm PE is SEF if all agents have different preference orderings (WEF if exists two agents with same ordering). Proof sketch by induction:

• Let $S_1$ be the timepoint $a_1$ is fully eaten, $S_2$ when $a_2$ is fully eaten, and so on.
• Let agent $i$ have preference $a_1\succ a_2\succ \cdots \succ a_m$ of $m$ items of set $T$. Then, agent $i$ eats $a_1$ first. Everybody eats at the same rate, so there is no agent who can eat even more than agent $i$. Agent $i$ eats it from time $0$ to $S_1$:

$$\forall j,S_1=P_{i,a_1}\ge P_{j,a_1}$$

Then, $i$ moves on to eat $a_2$ from time $S_1$ to $S_2$. No other agent can eat more of $a_1$ AND $a_2$ than agent $i$ (unless they both eat identically):

$$\forall j,P_{i,a_1}+P_{i,a_2}>P_{j,a_1}+P_{j,a_2}$$

Induce into all $m$ items:

$$\forall j,\sum _{\forall a}{P}_{i,a}>\sum _{\forall a}{P}_{j,a}$$

(equality when $i,j$ have identical preferences). Considering all of these cases together:

$$\forall a,\forall j\sum _{a^{\prime }>a}{P}_{i,a}>\sum _{a^{\prime }>a}{P}_{j,a}$$

Therefore $i$ does not envy anybody else. ■

thm PE is Ex-Post PO. We will go through a lemma first. def. In allocation $P$, call $a_2\stackrel{\tau }{\to }{a}_1$ (”$a_2$ tau-s $a_1$”) iff there exists an agent $i$ which prefers $a_2$ over $a_2$, but has also eaten some of $a_1$ (and obviously ate $a_2$ beforehand). Allocation-wise, $a_2{\succ }_i{a}_2$ and $P_{i,a_1}>0$. Lemma. If an allocation $P$ is not Ex-Post PO, then there exists a cycle, i.e. $a_1\stackrel{\tau }{\to }{a}_2\stackrel{\tau }{\to }\dots \stackrel{\tau }{\to }{a}_1$ Then Proof by contradiction. Assume $PE$ produces and allocation $P$ that is not EX-post PO; by the lemma this allocation must have a tau-cycle: For the tau’ing $a_{\gamma -1}\stackrel{\tau }{\to }{a}_{\gamma }$ in this cycle, Find the agent $i_{\gamma }$ that tau’ed these items. Let the timepoint when $i$ starts eating $a_{\gamma }$ be $S_{\gamma }$. By this time $a_{\gamma -1}$ must have been fully eaten; thus $S_{\gamma -1}<S_{\gamma }$. We can do this for every tau’ed agent in the cycle. But then $S_1<S_{\gamma }$, but by cycle $S_1>S_{\gamma }$. This is a contradiction. Thus allocation $P$ which is produced by PE must be Ex-Post PO. ■ Proof Sketch of Lemma. Assume allocation $P$ which is not ex-post PO, i.e. there exists another allocation $Q$ where some agent $i$ is better off in $Q$, i.e. $Q_i\succ P_i$ (=$Q_i$ stochastically dominates $P_i$.) Focus on this agent $i$. Then, there must exist for this agent a pair of items (call them $a_2,a_1$) where:

1. $a_2{\succ }_i{a}_1$
2. $Q_{i,a_2}>P_{i,a_2}$ because for $i$ $Q$ is better because it eats more of the better one.
3. $Q_{i,a_1}<P_{i,a_1}$ because probability for each row must both sum to $1$. Thus $P_{i,a_2}>0$ and in alloc. $P$, $a_2\stackrel{\tau }{\to }{a}_1$. Then, find another agent $j$ that $Q_{j,a_2}<P_{j,a_2}$. This $j$ exists because probability of each column sums to $1$ (for each allocation). Now, for this agent $j$, find item $a_3$ that satisfies:
4. $a_3{\succ }_j{a}_2$
5. $P_{j,a_3}<Q_{j,a_3}$ This item $a_3$ must exist because row must sum to one. Then $P_{j,a_2}>0$ and in alloc. $P,$ $a_2\stackrel{\tau }{\to }{a}_1$ We can continue on but we must form a cycle of tau-ing because there are finite number of items. ■