Objective: Examine the compatibility of EF1 with Pareto-optimality, introducing the concept of EFX.

Activities: Read and present the paper The Unreasonable Fairness of Maximum Nash Welfare. Ioannis et al. ACM Transactions on Economics and Computation 2019

It’s worth to mention that Iannis received Kalai Prize 2024 for this paper 🎆

Hint from Iannis: Ignore appendix, experiments. Focus on the proof, paraphrase it in my own words, a easy way!

Maximum Nash welfare (abbr. MNW) selects an allocation that maximize the product of utilities.

Not only for divisible goods, MNW is also fair in indivisible setting.

MNW selects allocation that are EF1! It also compatible with other fairness like MMS.

Introduction

MNW exhibits an elusive combination of fairness and efficiency.

Main Results

MNW solution always outputs an allocation that is EF1 as well as Pareto optimal.

EF1 is easy, but EF1 + PO is hard.

MNW solution always guarantees 21+4n3\frac{2}{1+\sqrt{4n-3}}-MMS. (the approximation is tight!)

MNW solution guarantees 512\frac{\sqrt5-1}{2}-PMMS. (the approximation is also tight!)

Computing MNW allocation is NP-hard for unscaled valuations. Solution: scaled valuations.

EF1: Envy-cycle elimination, Round-Robin

Approximate CEEI

Maximizing Nash welfare with divisible goods: Envy-free, Pareto optimal.

MNW is NP-hard. Some approximation MNW in polynomial time. MNW is APX-hard: a constant-factor approximation is the best one can hope to achieve in polynomial time.

Model

N=[n]\mathcal N=[n] players.

M=[m]\mathcal M=[m] indivisible goods.

Each player has a valuation function viv_i for the goods.

  • vi()=0v_i(\empty)=0
  • additive (main results can be generalized to submodular valuations)

Πk(S)\Pi_k(S) denote the set of ordered partitions of SS into kk bundles. SMS\subseteq \mathcal M.

A feasible allocation A=(A1,,An)Πn(M)\mathbf A=(A_1,\cdots,A_n)\in\Pi_n(\mathcal M) is a partition of the goods that assigns a subset AiA_i to player ii. Thus the utility to ii is vi(Ai)v_i(A_i).

Definition of Envy Freeness (EF), EF1, MMS: omitted

Definition of Pareto Optimality (PO): An allocation A\mathbf A is called PO if no alternative allocation AΠn(M)\mathbf A'\in\Pi_n(\mathcal M) can make some players strictly better off without making any player strictly worse off. Formally,

AΠn(M),(iN,vi(Ai)>vi(Ai))(jN,vj(Aj)<vj(Aj)).\forall\mathbf A'\in\Pi_n(\mathcal M),(\exist i\in\mathcal N,v_i(A_i')\gt v_i(A_i))\Rarr(\exist j\in\mathcal N,v_j(A_j')\lt v_j(A_j)).

Maximum Nash Welfare is EF1 and PO

Draft mechanism: Round-robin. It guarantees output is EF1, but not Pareto optimal.

Maximizing the utilitarian welfare (sum of utilities to the players) or the egalitarian welfare (minimum utility for any player) is not EF1.

Maximizing these objectives subject to the constraint that the allocation is EF1 violates PO.

Starting point: By assuming the goods are divisible, compute a CEEI allocation. Then come up with an intelligent rounding scheme to allocate each good to one of the players who received some fraction of it.

CEFI may not exist for indivisible goods, but one can still maximize the Nash welfare over all feasible allocations. This solution is referred to as maximum Nash welfare (MNW) solution, achieves EF1 + PO.

What is CEEI?

All players are given an equal budget. The equilibrium is an allocation coupled with prices for the goods, s.t. each player buys her favorite bundle of goods for the given pieces, and the market clears.

Definition of MNW. The Nash welfare of allocation AΠn(M)\mathbf A\in\Pi_n(\mathcal M) is defined as NW(A)=iNvi(Ai)NW(\mathbf A)=\prod_{i\in\mathcal N}v_i(A_i). Given valuations {vi}iN\{v_i\}_{i\in\mathcal N}, the MNW solution selects an allocation AMNW\mathbf A^{MNW} maximizing the Nash welfare among all feasible allocations, i.e.,

AMNWargmaxAΠn(M)NW(A)\mathbf A^{MNW}\in{\arg\max}_{\mathbf A\in\Pi_n(\mathcal M)}NW(\mathbf A)

Zero Nash welfare is highly unlikely to appear in practice.

Computing MNW consists of 2 stages:

  1. Finding a largest set of players SS to which one can simultaneously provide a positive utility.
  2. Finding an allocation of the goods to players in SS that maximizes their product of utilities.

MNW Pseudo Code

Input: N,M,{vi}iN\mathcal N,\mathcal M,\{v_i\}_{i\in\mathcal N}

Output: AMNW\mathbf A^{MNW}

  1. SargmaxTN:AΠn(M),iT,vi(Ai)>0TS\in\arg\max_{T\subseteq\mathcal N:\exist\mathbf A\in\Pi_n(\mathcal M),\forall i\in T,v_i(A_i)\gt0}|T|; // a largest set of players that can be simultaneously given a positive utility
  2. AargmaxAΠS(M)iSvi(Ai)\mathbf A^*\gets\arg\max_{\mathbf A\in\Pi_{|S|}(\mathcal M)}\prod_{i\in S}v_i(A_i); // The MNW allocation to players in SS
  3. AiMNWAi,iS\mathbf A_i^{MNW}\gets A_i^*,\forall i\in S;
  4. AiMNW,iNS\mathbf A_i^{MNW}\gets\empty,\forall i\in\mathcal N\diagdown S; // Players in NS\mathcal N\diagdown S do not receive any goods

An allocation is a MNW allocation if it can be selected by the MNW solution.

🎯🤔Theorem 1. Every MNW allocation is EF1 and PO for additive valuations over indivisible goods.

Never copy proof from paper again❗Try to capture the main argument of proof.

PO is trivial. Because increase some viv_i without decreasing any vjv_j violates optimality of Nash welfare under A\mathbf A.

EF1 is proved by contradiction.

Assume A\mathbf A is not EF1, there exist i,ji,j, in which ii envies jj after removing removing any single goods from AjA_j.

Let g=argmingAj,vi(g)>0vj(g)vi(g)g^*=\arg\min_{g\in A_j,v_i(g)\gt0}\frac{v_j(g)}{v_i(g)}. Denote A\mathbf A': after moving gg^* from AjA_j to AiA_i.

It suffices to show NW(A)>NW(A)NW(\mathbf A')\gt NW(\mathbf A) (By manipulating two inequalities of gg^* and Non-EF1.), which gives the desired contradiction as Nash welfare is optimal under A\mathbf A.

Additionally, we need to discuss the special case where NW(A)=0NW(\mathbf A)=0.

General Valuations

Is EF1 and PO can be achieved simultaneously for

  1. subadditive;
  2. superadditive;
  3. submodular (special case of subadditive);
  4. supermodular (special case of superadditive) ❓

🎯🤔Theorem 2. For 1. subadditive; 2. supermodular; 3. superadditive valuations over indivisible goods, there exist instances that do not admit allocations that are EF1 + PO.

Proof omitted.

This paper didn’t solve this question for submodular valuations. It only shows MNW is not EF1 + PO for submodular valuations. The paper relaxes the EF1 condition, Marginal Envy Freeness up to One Good (MEF1), showing that every MNW allocation satisfies MEF1 + PO.

subadditive: AB=,v(A)+v(B)v(AB)\forall A\cap B=\empty,v(A)+v(B)\ge v(A\cup B).

submodular: \forall B\subseteq A\and g\notin A,v(A\cup\{g\})-v(A)\le v(B\cup\{g\})-v(B)

superadditive: AB=,v(A)+v(B)v(AB)\forall A\cap B=\empty,v(A)+v(B)\le v(A\cup B).

supermodular: \forall B\subseteq A\and g\notin A,v(A\cup\{g\})-v(A)\ge v(B\cup\{g\})-v(B)

Definition of MEF1. An allocation AΠn(M)A\in\Pi_n(\mathcal M) is MEF1 if

i,jN,gAj,vi(Ai)vi(AiAj{g})vi(Ai)\forall i,j\in\mathcal N,\exist g\in A_j,v_i(A_i)\ge v_i(A_i\cup A_j\diagdown\{g\})-v_i(A_i)

For additive valuations, trivially MEF1 = EF1. For submodular valuations, the marginal value vi(AiAj{g})vi(Ai)vi(Aj{g})v_i(A_i\cup A_j\diagdown\{g\})-v_i(A_i)\le v_i(A_j\diagdown\{g\}).

🎯🤔Theorem 3. Every MNW allocation satisfies MEF1 + PO for submodular valuations over indivisible goods.

Proof omitted.

Maximum Nash Welfare is Approximately MMS

Approximate MMS in Theory

🎯🤔Theorem 4. Every MNW allocation is πn\pi_n-MMS for additive valuations over indivisible goods, where

πn=21+4n3.\pi_n=\frac{2}{1+\sqrt{4n-3}}.

This factor πn\pi_n is tight, i.e., for every nNn\in\mathbb N and ϵ>0\epsilon\gt0, there exists an instance with nn player having additive valuations in which no MNW allocation is (πn+ϵ)(\pi_n+\epsilon)-MMS.

First, prove that an MNW allocation is πn\pi_n-MMS (lower bound), and later prove tightness of the approximation ratio πn\pi_n (upper bound).

Lower bound:

  • Let A\mathbf A be an MNW allocation. Assume NW(A)>0NW(\mathbf A)\gt0, then handle the case of NW(A)=0NW(\mathbf A)=0.

  • Fix a player ii, for a player jN{i}j\in\mathcal N\diagdown\{i\}, let gj=argmaxgAjvi(g)g_j^*=\arg\max_{g\in A_j}v_i(g) denote the most valuable good in AjA_j to ii.

  • Then, prove the lemma:

    vi(Aj{gj})min{vi(Ai),(vi(Ai))2vi(gj)}v_i(A_j\diagdown\{g_j^*\})\le\min\{v_i(A_i),\frac{(v_i(A_i))^2}{v_i(g_j^*)}\}

    vi(Aj{gj})vi(Ai)v_i(A_j\diagdown\{g_j^*\})\le v_i(A_i) since A\mathbf A is MNW.

    To prove vi(Aj{gj})(vi(Ai))2vi(gj)v_i(A_j\diagdown\{g_j^*\})\le\frac{(v_i(A_i))^2}{v_i(g_j^*)}, we need manipulate the MNW properties:

    1. moving gjg_j^* from jj to ii should not increase the Nash welfare.
    2. moving all goods in AjA_j except gjg_j^* from jj to ii should also not increase Nash welfare.

    Do some transforms to 1. and 2. inequalities, then yield the results.

💣💀 💣💀 💣💀Finding upper bound on MMS guarantee.

  • Assume all the goods except goods in T=\{g_j^*|v_i(g_j^*)\gt MMS_i\and j\in\mathcal N\diagdown\{i\}\} become divisible.

    Let each item in TT be a bundle itself, let others divided into nTn-|T| equal-valued (w.r.t ii) bundles.

    Note that all bundles have value MMSi\ge MMS_i. inequality (i)

  • From lemma above, we bound vi(Aj{gj})v_i(A_j\diagdown\{g_j^*\}) in inequality (i). Then do some transforms and substitute variables.

  • 💣💀 💣💀 💣💀 After that, we need do Mathematical analysis.

We will get $\beta=\frac{MMS_i}{v_i(A_i)}\le\frac{1}{\pi_n}$.

For case NW(A)=0NW(\mathbf A)=0, it’s easy to prove MMSi=0MMS_i=0.

  • Proof of the upper bound (no πn+ϵ\pi_n+\epsilon guarantee) and lower bound.

    ☠️☠️☠️OMG I have no patience. This is TERRIBLE!!!

Best approximation of MMS: 23+O(1n)\frac{2}{3}+O(\frac{1}{n}). Whereas MNW approximates Θ(1n)\Theta(\frac{1}{\sqrt n}). When number of nn is small (in real world), the worst-case approximation guarantee is good.

Approximate Pairwise MMS, in Theory

Definition of PMMS and its approximation: omitted.

Neither PMMS nor MMS implies the other.

Definition of EFX: omitted.

🎯🤔Theorem 5. For additive valuation over indivisible goods:

EF(1)PMMS(2)EFX(3)EF1PMMS(4)12MMSEF\stackrel{(1)}\Rarr PMMS\stackrel{(2)}\Rarr EFX\stackrel{(3)}\Rarr EF1\\ PMMS\stackrel{(4)}\Rarr\frac{1}{2}-MMS

(1) (3) is easy.

(2) is proved by contradiction.

(4) is complicated:

A\mathbf A is PMMS. Consider ii and jj. There are only 2 possible cases:

  1. AjA_j has at most one good that player ii values positively.
  2. vi(Aj)2vi(Ai)v_i(A_j)\le2\cdot v_i(A_i).

Assume otherwise (not 1. and not 2.), then consider gg^* that is the least valuable among player ii’s positively valued goods in AjA_j. In that case, player ii could partition AiAjA_i\cup A_j into (Ai{g},Aj{g})(A_i\cup\{g^*\},A_j\diagdown\{g^*\}) and ensure that her pairwise MMS value is strictly more than vi(Ai)v_i(A_i), which contradicts that A\mathbf A is PMMS.

If no player in N{i}\mathcal N\diagdown\{i\} falls into case 2., it’s easy to see the MMS guarantee of player ii is at most vi(Ai)v_i(A_i), if some players fall into 2. (denoted set SN{i}S\subseteq\mathcal N\diagdown\{i\}), we need to bound the MMS guarantee of ii by assuming all the goods allocated to S{i}S\cup\{i\} are divisible. However, this still gives an MMS guarantee of at most 2vi(Ai)2\cdot v_i(A_i), because each player in jS{i}j\in S\cup\{i\} satisfies vi(Aj)2vi(Ai)v_i(A_j)\le2\cdot v_i(A_i). Thus, the MMS guarantee of player ii is at most 2vi(Ai)2\cdot v_i(A_i), which implies A\mathbf A is ½-MMS.

🎯🤔Theorem 6. Every MNW allocation is Φ\Phi-PMMS, where Φ=5120.618\Phi=\frac{\sqrt 5-1}{2}\approx0.618. This factor is tight.

One property of a MNW allocation A\mathbf A: Take the goods allocated to ii and jj, i.e., M=AiAj,N={i,j}\mathcal M'=A_i\cup A_j,\mathcal N'=\{i,j\}. Then the allocation given by AiA_i and AjA_j is also an MNW allocation for the reduced instance of allocating the set of M\mathcal M' to player N\mathcal N'.

Hence, the allocation in π2\pi_2-MMS in the reduced instance.

Therefore, we conclude that MNW allocation is Φ\Phi-PMMS as π2=Φ\pi_2=\Phi.

Tightness? For a given nN,ϵ>0n\in\mathbb N,\epsilon\gt0, we simply use the example of upper bound in theorem 4 after replacing πn\pi_n by π2\pi_2 in the valuations of players.

Approximate MMS and PMMS in Practice

Omitted.

Implementation

Some experiments.

Omitted!!!

Discussion

MNW = EF1 + PO (for additive valuations)

MNW provides Θ(1n)\Theta(\frac{1}{\sqrt n})-MMS, whereas an arbitrary EF1 and PO allocation only provides 1n\frac{1}{n}-MMS.

In paper, assumed the goods are indivisible, but results can be extended to a mix of divisible and indivisible goods.

When all goods are divisible, MNW, CEEI, and proportional Fairness are the same. But not true for indivisible settings: CEEI, PF may not exist.

Open question: is it possible to relate the MNW solution to the CEEI solution when the goods are indivisible?

This paper didn’t solve the strategyproofness on MNW, because

  1. The only strategyproof and PO solutions are dictatorial - UNFAIR.
  2. Users are usually not aware of each other’s preference, don’t know the behavior of allocation algorithm.