202312161012

Tags : Algorithms

Allocation Problem

---

Given:

• A set $[n]$ of $n$ agents
• A set $[m]$ of $m$ indivisible goods
• A valuation function $v_i:2^{[m]}\to {\mathbb{R}}^{+}$ where empty set maps to $0$.

Welfare

Maximum Nash Welfare: $\max ({\prod }_i{v}_i(X_i){)}^{\frac{1}{n}}$

• Interesting tradeoff between efficiency and fairness.
• Motivated by Nash bargaining
• Scale free: invariant under
• This is a very hard problem NP-hard.

---

References