Game Theory

Items are NOT divisible now! Goal: Fair and efficient allocation Model $A$: set of $n$ agents $M$: set of $m$ indivisible goods Each agent $i$ has Valuation function: $V_i: 2^m \to R_+$ over subsets of items. This function is monotone, i.e. the more the happier. Allocation $X = (X_1, \ldots, X_n)$ is the allocation of goods to agents, where they form a partition of $M$. Fairness In the indivisible setting, we envy-free and proportional properties is hard to achieve in the divisible setting. We need new definitions. ...

Divisibles means that the item can be divided to any sizes. A cake is an example. Goal: Fair and efficient allocation Model $A$: set of $n$ agents $M$: set of $m$ divisible goods Each agent $i$ has Valuation function: $V_i: R_+^m \to R_+$ over bundles of items. (doesn’t have to be linear) Concave: Captures decreasing marginal returns (looks like $\sqrt{x}$ curve) Allocation $X = (X_1, \ldots, X_n)$ is the allocation of goods to all agents, $X_{ij}$ is the allocation of good $j$ to agent $i$. Fair (agreeable) Envy-free: no agent envies other’s allocation over her own For each agent $i$, $V_i(X_i) \geq V_i(X_j), \forall j \in [n]$. Proportional: Each agent $i$ gets value at least $V_i(M) / n$ $\equiv$ for each agent $i$, $V_i(X_i) \geq V_i(M)/n$. Efficient(non-wasteful) Pareto-optimal: no other allocation is better for all. There is no allocation $Y$ such taht $V_i(Y_i)\geq V_i(X_i), \forall i \in [n]$. Welfare Maximizing: $\max \sum_{i}V_i$ . Doesn’t makes sense sometimes. If a person has very huge values on one thing, should we just give the item to the person? (Nash) Welfare Maximizing: $ \max \prod_i V_i$. This is the alternative using multipilcations. ...