Fractional Allocation

Motivation. Given the Fairness (Economics) properties, we can start allocating things to people. Different allocation methods satisfy different fairness criteria. The most important allocation method is the CEEI Allocation, which is achieved by the Fischer market.

def. Fischer Market. The following describes a Fischer market. There are $m$ items and $n$ agents. There are $q_j$ units of item $j$.

1. All agents given \1$
2. Set prices at a certain point, $\vec{p}$ (ignore how we find this for now)
3. Agents fine their demand set:

$${\vec{x}}_i=\underset{\text{ Utility Maximization }}{\underbrace{arg{\text{max}}_{x_i}{\mu }_i(\overrightarrow{x_i})}}\text{ s.t. }\underset{\text{ Budget Constraint }}{\underbrace{\vec{p}\cdot \vec{x}\le 1}}$$

To clarify the notation:

• $q_1^{(i)}$ is the amount of item $1$ allocated to agent $j$
• $q_1:={\sum }_{\forall i}{q}_1^{(i)}$ which is the total amount of item allocated to

def. Competitive Equilibrium with Equal Incomes (CEEI). In a Fischer market, if we set the prices $\vec{p}$ just right, we will get a solution where:

1. All agents spend all their money $\forall i,\overrightarrow{p_i}\cdot \overrightarrow{x_i}=1$
2. All items are fully allocated (=market clears).

$$\begin{array}{rlr}(q_1^{(i)},\underset{\text{ each item quantity to i}}{\underbrace{\dots .,q_j^{(i)},\dots }},q_m^{(i)})& :=\overrightarrow{x_i}& \text{then}\\ \sum _j{q}_j^{(i)}& =1& \text{equivalently}\end{array}$$

3. The above two properties implies $\vec{p}\cdot {\sum }_i\overrightarrow{x_i}={\sum }_{\forall j}{\sum }_{\forall i}{q}_j^{(i)}=n$ Then, this allocation is a CEEI.

thm. CEEI always exists. (We won’t prove.)

thm. CEEI satisfies Scale Invariance, EF, Prop, and Pareto Efficiency. Let $\overrightarrow{x_1},\vec{\dots }{x}_n$ be the CEEI allocation. Proof of SI. In the Fischer market process agents will find their demand set. Demand set doesn’t change depending on the scale of the utility; only the ordinal preferences. Proof of EF. By contradiction. Assume $i$ envies $j$ s.t. $\overrightarrow{x_j}\succ \overrightarrow{x_i}$. But everybody has the same $1thus$i$couldhavejustdemanded$\vec{x_{j}}$instead.Thusthereisnoenvy.\ast ProofofPR\ast .SinceallmoneyisspentbyCEEIdefinition,$\sum_{j} p_{j}q_{j}=n$where$q_{j}$istheamountofunitsofitem$j$.Thendividebothby$n$toget$\sum_{j}p_{j} \frac{q_{j}}{n}=1$whichmeansthattheproportionalallocation$\left(\frac{q_{1}}{n},\dots \frac{q_{m}}{n} \right)$isfeasible.Butallagentsdemandedsomeotherset$S_{i}$thusi{t}^{\prime }satleastasgoodasproportionalallocationbundle.\ast ProofofParetoOptimality.\ast Bycontradiction.Assumethereisanalternativeallocation$\vec{y_{1}},\dots,\vec{y_{n}}$suchthatitisaParetoimprovementsuchthatwinnersset$W$denotes"winners"agentswhoimproved:$\vec{y_{i}}\succ_{\forall i \in W} \vec{x_{i}}$and"indifferents"set$I$denotesagentswhohassameutility:$\forall i \in I,~ \mu_{i}(\vec{y_{i}})=\mu_{i}(\vec{x_{i}})$.Now,forthewinners,theydid{n}^{\prime }tdemandset$\vec{y_{i}}$inCEEIallocation$\vec{x_{i}}$,sotheyclearlycould{n}^{\prime }taffordit:$\vec{p} \cdot \vec{y_{j}}>1$.NowfortheIndifferents;if$\vec{p} \cdot \vec{y_{i}}<1$thentheycouldhaveinitiallybought$\vec{x_{i}}=\vec{y_{i}}$andafewmorestuffswithleftovermoney.Buttheydid{n}^{\prime }tdemandanythingotherthan$\vec{x_{i}}$,thus$\vec{p} \cdot \vec{y_{i}}\geq 1$ by contradiction. Combining the inequality for winners and losers:

$$\begin{array}{rl}\sum _{i\in W}\vec{p}\cdot \overrightarrow{y_i}+\sum _{i\in I}\vec{p}\cdot \overrightarrow{y_i}& >n\\ \sum _{\forall i}\vec{p}\cdot \overrightarrow{y_i}& >n\\ \vec{p}\cdot \sum _{\forall i}\overrightarrow{y_i}& >\underset{\text{ b/c CEEI clears market}}{\underbrace{n=\vec{p}\underset{=(q_1,\dots ,q_m)}{\underbrace{\sum _{\forall i}\overrightarrow{x_i}}}}}\\ \sum _{\forall i}\overrightarrow{y_i}>\sum _{\forall i}\overrightarrow{x_i}& \end{array}$$

But we also know that CEEI allocation $\overrightarrow{x_1},\dots ,\overrightarrow{x_n}$ guarantees market clearing but $\overrightarrow{y_1},\dots ,\overrightarrow{y_n}$ does not, so:

$$\sum _{\forall i}\overrightarrow{y_i}\le \sum _{\forall i}\overrightarrow{x_i}$$

And this is a contradiction. ■

Now, for the mystical $\vec{p}$, we can find that by using…

def. Eisenberg-Gale (EG) convex program is a Convex Programming for finding CEEI in additive utility. This maximizes:

$$\text{max}\sum _{\forall i}\ln {\mu }_i$$

w.r.t. the following constraints:

1. ${\mu }_i={\sum }_{\forall j}{\mu }_{i,j}\cdot x_{i,j}$ ← utility is summation utility
2. ${\sum }_{\forall i}{x}_{i,j}\le 1$ ← nobody overspends
3. $x_{i,j}\ge 0$ ← no under-allocation

thm. the EG Convex program finds the CEEI. Proof. ■