AFTD Auto-Formalizing Theoretical Domains

Research Blogs

The Exact Price and Strong Price of Maximum Nash Welfare for Two Agents Equal 27/23

medium tier2026-10-06OP-67reviewed by Claude Code中文版

Abstract

The price of maximum Nash welfare (MNW) measures the worst-case efficiency loss incurred by requiring an allocation of indivisible goods to maximize the Nash welfare product, defined as the supremum ratio of optimal utilitarian social welfare to the welfare achieved by the best MNW allocation. The strong price of MNW considers the welfare of the worst MNW allocation instead. For two agents with additive, nonnegative, normalized valuations, both the price and the strong price of MNW were shown in arXiv:1905.04910 to lie in the interval $[27/23, 5/4]$. This post presents the resolution of this question: every maximum Nash welfare allocation $N$ and every alternative allocation $O$ satisfy $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$. The proof partitions the goods into four sets according to their recipients under $O$ and $N$, formulates five quadratic constraints reflecting the maximality of $N$ against $O$ and four bundle-reassignment allocations, and establishes the bound via mnw2_core using the bracket lemma and a polynomial certificate. Together with the known lower-bound instance converging to $27/23$, this establishes that both the price and strong price of MNW for two agents are exactly $27/23$. The theorem and all supporting lemmas have been formally verified in Lean 4 as mnw_two_agents_welfare_le.

1. Introduction

Fair allocation of indivisible goods is a central topic in social choice and algorithmic game theory. When allocating a set of indivisible items among multiple agents, one often seeks allocations that satisfy fairness criteria such as envy-freeness or proportionality, or efficiency criteria such as Pareto optimality or utilitarian social welfare maximization. Utilitarian social welfare evaluates an allocation by the arithmetic sum of the values that agents assign to their bundles. By contrast, Nash welfare evaluates an allocation by the geometric mean or product of the agents' bundle values. An allocation that maximizes Nash welfare (an MNW allocation) is known to offer an attractive balance between fairness and efficiency.

Enforcing fairness constraints, however, can reduce the total utilitarian social welfare achievable by an unconstrained allocation. This trade-off is formalized through the concept of the price of fairness, introduced in arXiv:1905.04910. For a given fairness notion, the price of fairness is defined as the worst-case ratio, over all instances, of the optimal utilitarian social welfare to the utilitarian welfare of the best fair allocation. When multiple fair allocations exist, the strong price of fairness takes the worst fair allocation instead, measuring the maximum possible welfare loss if an arbitrary fair allocation is chosen.

In arXiv:1905.04910, the price of fairness and the strong price of fairness were analyzed for several fairness concepts, including proportionality up to one good (PROP1), envy-freeness up to one good (EF1), and maximum Nash welfare. In Table 1 and Theorem 5.4 of arXiv:1905.04910, exact bounds were established in the two-agent setting for nearly all considered fairness notions. As stated in arXiv:1905.04910: "Moreover, with the exception of EF1 and MNW, we establish exactly tight bounds in the case of two agents for all fairness notions."

For the case of two agents with additive, nonnegative, and normalized valuations (where each agent's value for the complete set of goods is normalized to 1), Theorem 5.4 of arXiv:1905.04910 proved that both the price of MNW and the strong price of MNW lie within the interval $[27/23, 5/4]$. The lower bound of $27/23$ was derived from an explicit family of instances with two agents and three indivisible goods, parameterized by $\varepsilon > 0$. In those instances, the optimal utilitarian welfare is $9/7$, whereas every MNW allocation achieves utilitarian welfare $23/21 + \varepsilon$. As $\varepsilon \to 0$, the ratio of optimal utilitarian welfare to MNW utilitarian welfare approaches $(9/7)/(23/21) = 27/23 \approx 1.1739$. On the upper bound side, Theorem 5.4 established that the ratio cannot exceed $5/4 = 1.25$ for two agents, leaving a gap between $27/23$ and $5/4$. For general $n$ agents, arXiv:1905.04910 showed that the price of MNW grows as $\Theta(n)$, so the asymptotic dependence on $n$ was resolved, but the exact value for two agents remained unsettled.

This post presents the resolution of this two-agent gap. We describe the formal proof of the theorem mnw_two_agents_welfare_le, which shows that for any number of goods $m$ and any two agents with additive, nonnegative, normalized valuations, every MNW allocation $N$ satisfies $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$ for every alternative allocation $O$. This improves the upper bound from $5/4$ to $27/23$. Combined with the matching lower-bound result mnw_two_agents_price_lower_bound, this establishes that both the price of MNW and the strong price of MNW for two agents are equal to exactly $27/23$.

2. Preliminaries

We formalize the problem setting in Lean 4, following the declarations of the verified development. Let $n = 2$ be the number of agents, represented by the type $\mathrm{Fin}\; 2 = \{0, 1\}$, and let $m \in \mathbb{N}$ denote the number of indivisible goods, indexed by $\mathrm{Fin}\; m$.

Definition 1 (Valuations and Allocations). An allocation is a function $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$, where $\sigma(g) = i$ indicates that good $g$ is assigned to agent $i$. For an agent $i \in \mathrm{Fin}\; 2$, the bundle assigned to $i$ under $\sigma$ is defined as $X_i(\sigma) = \{g \in \mathrm{Fin}\; m \mid \sigma(g) = i\}$. Valuations are given by a function $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$. The valuations are assumed to satisfy:

  1. Nonnegativity: $0 \le v(i, g)$ for all $i \in \mathrm{Fin}\; 2$ and all $g \in \mathrm{Fin}\; m$.
  2. Additivity: the value of a bundle $S \subseteq \mathrm{Fin}\; m$ to agent $i$ is given by $v_i(S) = \sum_{g \in S} v(i, g)$.
  3. Normalization: $\sum_{g \in \mathrm{Fin}\; m} v(i, g) = 1$ for each agent $i \in \mathrm{Fin}\; 2$.

Remark 1: Goods are indivisible, meaning that each good $g$ is assigned entirely to a single agent. The normalization $\sum_g v(i, g) = 1$ is standard in the price of fairness literature (as in arXiv:1905.04910) to make utilitarian comparisons meaningful between agents.

Definition 2 (Utilitarian Social Welfare utilitarian_welfare). For valuations $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ and an allocation $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$, the utilitarian social welfare is the sum of the values of the bundles: $$\mathrm{utilitarian\_welfare}(v, \sigma) = \sum_{i \in \mathrm{Fin}\; 2} \sum_{g \in X_i(\sigma)} v(i, g).$$ In Lean, utilitarian_welfare is defined as the sum over all agents $i$ of the additive valuation of agent $i$'s bundle under $\sigma$.

Definition 3 (Nash Welfare nash_welfare). For valuations $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ and an allocation $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$, the Nash welfare is the product of the agents' bundle valuations: $$\mathrm{nash\_welfare}(v, \sigma) = \prod_{i \in \mathrm{Fin}\; 2} \sum_{g \in X_i(\sigma)} v(i, g).$$ In Lean, nash_welfare is defined as the product over all agents $i$ of the additive valuation of agent $i$'s bundle under $\sigma$.

Definition 4 (Maximum Nash Welfare Allocation is_mnw_allocation). An allocation $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ is a maximum Nash welfare allocation if no allocation $\tau : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ achieves strictly higher Nash welfare: $$\forall \tau : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2,\quad \mathrm{nash\_welfare}(v, \tau) \le \mathrm{nash\_welfare}(v, \sigma).$$ In Lean, is_mnw_allocation formalizes this property as the universal proposition that $\mathrm{nash\_welfare}(v, \tau) \le \mathrm{nash\_welfare}(v, \sigma)$ for all allocations $\tau$.

Remark 2: When the maximum achievable Nash welfare is strictly positive, is_mnw_allocation coincides with the usual definition in arXiv:1905.04910. When the maximum Nash welfare is zero, the standard literature convention uses a lexicographic tie-breaking rule that primarily maximizes the number of agents receiving positive utility and then maximizes the product of positive utilities. The predicate is_mnw_allocation simply requires that the Nash product is maximal (i.e. zero), so every allocation achieving product zero satisfies is_mnw_allocation. Because the set of allocations satisfying is_mnw_allocation contains all allocations chosen under the lexicographic tie-breaking rule, an upper bound on welfare loss holding for all allocations satisfying is_mnw_allocation applies directly to tie-broken allocations and is at least as strong.

Definition 5 (Price of MNW and Strong Price of MNW). Given an instance $(m, v)$ admitting an optimal utilitarian allocation $O^* = \arg\max_\tau \mathrm{utilitarian\_welfare}(v, \tau)$, let $\mathcal{M}(v)$ denote the set of allocations satisfying is_mnw_allocation. The price of MNW is the supremum over instances of the ratio: $$\frac{\mathrm{utilitarian\_welfare}(v, O^*)}{\sup_{N \in \mathcal{M}(v)} \mathrm{utilitarian\_welfare}(v, N)}.$$ The strong price of MNW is the supremum over instances of the ratio: $$\frac{\mathrm{utilitarian\_welfare}(v, O^*)}{\inf_{N \in \mathcal{M}(v)} \mathrm{utilitarian\_welfare}(v, N)}.$$

Remark 3: The price of MNW uses the best MNW allocation with respect to utilitarian welfare, while the strong price of MNW uses the worst MNW allocation.

3. Main result

The main theorem establishes that for two agents with additive, nonnegative, normalized valuations, the utilitarian social welfare of any allocation is at most $27/23$ times the utilitarian social welfare of any maximum Nash welfare allocation.

Theorem 1 (mnw_two_agents_welfare_le). Let $m \in \mathbb{N}$ be any number of goods. Let $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ be additive valuations satisfying nonnegativity ($0 \le v(i, g)$ for all $i \in \mathrm{Fin}\; 2, g \in \mathrm{Fin}\; m$) and normalization ($\sum_{g \in \mathrm{Fin}\; m} v(i, g) = 1$ for all $i \in \mathrm{Fin}\; 2$). Let $N, O : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ be allocations such that $N$ is a maximum Nash welfare allocation satisfying is_mnw_allocation. Then: $$23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N).$$

In one sentence, the Lean statement of mnw_two_agents_welfare_le universally quantifies over the number of goods $m : \mathbb{N}$, the valuation function $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$, proofs of nonnegativity and normalization, two arbitrary allocations $N$ and $O$, and the hypothesis that $N$ satisfies is_mnw_allocation, asserting the linear inequality $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$ in $\mathbb{R}$ without any restriction on the size of $m$.

Theorem 1 yields immediate bounds on both fairness measures:

  • Because the inequality holds for every allocation $O$, it holds in particular for an optimal utilitarian allocation $O^*$.
  • Because the inequality holds for every allocation $N$ satisfying is_mnw_allocation, it holds in particular for the MNW allocation that minimizes utilitarian welfare.
  • Therefore, whenever $\mathrm{utilitarian\_welfare}(v, N) > 0$, the ratio $\mathrm{utilitarian\_welfare}(v, O^*) / \mathrm{utilitarian\_welfare}(v, N)$ is bounded from above by $27/23 \approx 1.1739$.

Hence, both the price of MNW and the strong price of MNW for two agents are at most $27/23$. This strictly improves the previous upper bound of $5/4 = 1.25$ given in Theorem 5.4 of arXiv:1905.04910.

To establish tightness, we recall the earlier verified result mnw_two_agents_price_lower_bound: for every real constant $c < 27/23$, there exists an instance with two agents, three goods ($m = 3$), and normalized valuations such that an MNW allocation exists and every MNW allocation $N$ satisfies $c \cdot \mathrm{utilitarian\_welfare}(v, N) < \mathrm{utilitarian\_welfare}(v, O)$. This instance is the lower-bound construction from arXiv:1905.04910 Theorem 5.4, where $O$ achieves utilitarian welfare $9/7$ and every MNW allocation $N$ achieves utilitarian welfare $23/21 + \varepsilon$, giving a ratio $(9/7)/(23/21 + \varepsilon)$ that approaches $27/23$ as $\varepsilon \to 0$.

Together, mnw_two_agents_welfare_le and mnw_two_agents_price_lower_bound prove that the exact price of MNW and the exact strong price of MNW for two agents both equal $27/23$.

Theorem mnw_two_agents_welfare_le (Lean 4, verified)
theorem mnw_two_agents_welfare_le (m : ℕ) (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g) (hn : ∀ i, ∑ g, v i g = 1) (N O : Fin m → Fin 2) (hN : is_mnw_allocation v N) : 23 * utilitarian_welfare v O ≤ 27 * utilitarian_welfare v N

4. Proof

We present the proof of mnw_two_agents_welfare_le, detailing the reduction to an eight-variable polynomial optimization problem and its resolution via mnw2_core.

The overall idea is to partition the $m$ goods into four disjoint groups according to the agents who receive each good under $O$ and under $N$. Let $G_{ab}$ denote the set of goods assigned to agent $a$ under $O$ and to agent $b$ under $N$: $$G_{ab} = \{g \in \mathrm{Fin}\; m \mid O(g) = a \wedge N(g) = b\} \quad \text{for } a, b \in \{0, 1\}.$$ We denote these four groups by:

  • $A = G_{00}$: goods given to agent 0 by $O$ and to agent 0 by $N$.
  • $B = G_{10}$: goods given to agent 1 by $O$ and to agent 0 by $N$.
  • $C = G_{01}$: goods given to agent 0 by $O$ and to agent 1 by $N$.
  • $D = G_{11}$: goods given to agent 1 by $O$ and to agent 1 by $N$.

For agent 0, let $p, q, r, s$ denote the values of these four groups: $$p = \sum_{g \in A} v(0, g),\quad q = \sum_{g \in B} v(0, g),\quad r = \sum_{g \in C} v(0, g),\quad s = \sum_{g \in D} v(0, g).$$ For agent 1, let $\alpha, \beta, \gamma, \delta$ denote the values of these four groups: $$\alpha = \sum_{g \in A} v(1, g),\quad \beta = \sum_{g \in B} v(1, g),\quad \gamma = \sum_{g \in C} v(1, g),\quad \delta = \sum_{g \in D} v(1, g).$$

Because $0 \le v(i, g)$ for all $i$ and $g$, every sum over a subset of goods is nonnegative. This yields the eight nonnegativity conditions: $$0 \le p,\quad 0 \le q,\quad 0 \le r,\quad 0 \le s,\quad 0 \le \alpha,\quad 0 \le \beta,\quad 0 \le \gamma,\quad 0 \le \delta.$$

The decomposition of sums over goods is justified by the following lemma.

Lemma 1 (mnw2_sum_groups). For any valuation function $u : \mathrm{Fin}\; m \to \mathbb{R}$, allocations $O, N : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$, and weight function $c : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; 2 \to \mathbb{R}$, $$\sum_{g \in \mathrm{Fin}\; m} c(O(g), N(g)) \cdot u(g) = \sum_{a=0}^1 \sum_{b=0}^1 c(a, b) \sum_{g \in G_{ab}} u(g).$$ Proof. In Lean, the universal index set is partitioned into the four disjoint filters $\{g \mid O(g) = a \wedge N(g) = b\}$ for $a, b \in \{0, 1\}$. Decomposing the universal sum into these four sub-sums settles the identity.

Applying Lemma 1 with the constant weight function $c(a, b) = 1$ to the normalized valuations $v(0)$ and $v(1)$ (using $\sum_g v(i, g) = 1$) establishes the normalizations: $$p + q + r + s = 1 \quad (\text{hypothesis } h1),$$ $$\alpha + \beta + \gamma + \delta = 1 \quad (\text{hypothesis } h2).$$

Next, we evaluate allocations generated by assigning each group $G_{ab}$ wholesale to an agent.

Lemma 2 (mnw2_bundle_value). Let $u : \mathrm{Fin}\; m \to \mathbb{R}$, allocations $O, N, \tau : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$, and transition map $T : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; 2 \to \mathrm{Fin}\; 2$ satisfy $\tau(g) = T(O(g), N(g))$ for all $g \in \mathrm{Fin}\; m$. Then for each agent $k \in \{0, 1\}$, $$v_u(\tau^{-1}(k)) = \sum_{a=0}^1 \sum_{b=0}^1 [T(a, b) = k] \sum_{g \in G_{ab}} u(g),$$ where $[T(a, b) = k]$ equals 1 if $T(a, b) = k$ and 0 otherwise. Proof. Lean checks this by expanding the bundle definition into $\{g \mid \tau(g) = k\}$ and rewriting through the partition $G_{ab}$.

Using Lemma 2, the Nash welfare and utilitarian welfare for any allocation $\tau$ governed by a transition table $T$ are expressed as:

  • Agent 0 receives bundle value $V_0 = \sum_{a, b : T(a, b) = 0} v_0(G_{ab})$.
  • Agent 1 receives bundle value $V_1 = \sum_{a, b : T(a, b) = 1} v_1(G_{ab})$.
  • $\mathrm{nash\_welfare}(v, \tau) = V_0 \cdot V_1$ and $\mathrm{utilitarian\_welfare}(v, \tau) = V_0 + V_1$.

For the allocation $N$, the transition map is $T_N(a, b) = b$:

  • Agent 0 receives $A \cup B$, with value $V_0 = p + q$.
  • Agent 1 receives $C \cup D$, with value $V_1 = \gamma + \delta$.
  • Hence $\mathrm{nash\_welfare}(v, N) = (p + q)(\gamma + \delta)$ and $\mathrm{utilitarian\_welfare}(v, N) = (p + q) + (\gamma + \delta)$.

For the allocation $O$, the transition map is $T_O(a, b) = a$:

  • Agent 0 receives $A \cup C$, with value $V_0 = p + r$.
  • Agent 1 receives $B \cup D$, with value $V_1 = \beta + \delta$.
  • Hence $\mathrm{nash\_welfare}(v, O) = (p + r)(\beta + \delta)$ and $\mathrm{utilitarian\_welfare}(v, O) = (p + r) + (\beta + \delta)$.

Because $N$ satisfies is_mnw_allocation, we have $\mathrm{nash\_welfare}(v, \tau) \le \mathrm{nash\_welfare}(v, N)$ for every allocation $\tau$. Evaluating this inequality on five specific choices of $\tau$ produces five constraints:

1. Choosing $\tau = O$ yields: $$(p + r)(\beta + \delta) \le (p + q)(\gamma + \delta) \quad (cO).$$ 2. Choosing $\tau$ that gives agent 0 only $A$ ($T(a, b) = 0$ if $a = 0 \wedge b = 0$ else 1) gives agent 0 value $p$ and agent 1 value $\beta + \gamma + \delta$: $$p(\beta + \gamma + \delta) \le (p + q)(\gamma + \delta) \quad (cA).$$ 3. Choosing $\tau$ that gives agent 0 only $C$ ($T(a, b) = 0$ if $a = 0 \wedge b = 1$ else 1) gives agent 0 value $r$ and agent 1 value $\alpha + \beta + \delta$: $$r(\alpha + \beta + \delta) \le (p + q)(\gamma + \delta) \quad (cC).$$ 4. Choosing $\tau$ that gives agent 0 the bundle $A \cup B \cup C$ ($T(a, b) = 1$ if $a = 1 \wedge b = 1$ else 0) gives agent 0 value $p + q + r$ and agent 1 value $\delta$: $$(p + q + r)\delta \le (p + q)(\gamma + \delta) \quad (cABC).$$ 5. Choosing $\tau$ that gives agent 0 the bundle $A \cup C \cup D$ ($T(a, b) = 1$ if $a = 1 \wedge b = 0$ else 0) gives agent 0 value $p + r + s$ and agent 1 value $\beta$: $$(p + r + s)\beta \le (p + q)(\gamma + \delta) \quad (cACD).$$

These five inequalities, together with nonnegativity and normalization, imply the target inequality via the core lemma.

Lemma 3 (mnw2_core). Let $p, q, r, s, \alpha, \beta, \gamma, \delta \in \mathbb{R}$ satisfy nonnegativity ($0 \le p, q, r, s, \alpha, \beta, \gamma, \delta$), normalization ($p + q + r + s = 1$ and $\alpha + \beta + \gamma + \delta = 1$), and the five quadratic inequalities $cO, cA, cC, cABC, cACD$. Then: $$23(p + r + \beta + \delta) \le 27(p + q + \gamma + \delta).$$ Proof. The proof splits into two cases based on the relative sizes of $(q, \beta)$ and $(\gamma, r)$:

  • Case 1: $\beta \le q$ or $r \le \gamma$. In this case, the bracket lemma applies directly to bound the difference $27(p + q + \gamma + \delta) - 23(p + r + \beta + \delta)$.
  • Case 2: $\beta > q$ and $r > \gamma$. In this case, the five inequalities force the relationships $p \le \gamma + \delta$ and $\delta \le p + q$. Under these bounds on the variables, the inequality $27(p + q + \gamma + \delta) - 23(p + r + \beta + \delta) \ge 0$ is certified algebraically by a computer-found polynomial identity expressing the difference as a sum of nonnegative terms and multiples of the hypotheses. Lean checks this identity by polynomial expansion.

With Lemma 3 established, the proof of mnw_two_agents_welfare_le concludes directly:

- The nonnegativity conditions, the normalizations $h1, h2$, and the five inequalities $cO, cA, cC, cABC, cACD$ are supplied to mnw2_core. - Lemma 3 produces the key inequality: $$23(p + r + \beta + \delta) \le 27(p + q + \gamma + \delta).$$ - Substituting $\mathrm{utilitarian\_welfare}(v, O) = p + r + \beta + \delta$ and $\mathrm{utilitarian\_welfare}(v, N) = p + q + \gamma + \delta$, the linear combination closes the goal, proving: $$23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N).$$

5. Discussion

The theorem mnw_two_agents_welfare_le settles the price of maximum Nash welfare for two agents by proving that the upper bound is at most $27/23$, matching the lower bound of $27/23$ from arXiv:1905.04910. Prior to this result, Theorem 5.4 of arXiv:1905.04910 established that the price of MNW and the strong price of MNW for two agents lie in the range $[27/23, 5/4]$. The new upper bound improves upon $5/4 = 1.25$ and determines the exact value of both the price and strong price of MNW to be $27/23 \approx 1.1739$.

The bound is strong in several respects:

  • It holds for any number of goods $m$, with no restriction on the size of the instance.
  • It applies to every allocation $O$, not solely an optimal utilitarian allocation $O^*$.
  • It holds for every allocation $N$ satisfying is_mnw_allocation, not merely the best MNW allocation, meaning that the upper bound $27/23$ applies equally to the strong price of MNW.
  • The theorem relies on additive, nonnegative valuations normalized so that each agent values the set of all goods at 1.

The result does not cover instances with $n \ge 3$ agents. For general $n$, arXiv:1905.04910 proved that the price of MNW is $\Theta(n)$, but the exact leading constant and tight functions of $n$ remain unknown. Extending the four-group partition used here to $n$ agents would require partitioning goods according to the $n^2$ pairs of owners under $O$ and $N$, and general bundle exchanges would involve $n^n$ configurations.

Furthermore, arXiv:1905.04910 examined several other fairness notions. As highlighted in Table 1 and Section 5 of arXiv:1905.04910, tight bounds for two agents were established for all fairness notions except EF1 (envy-freeness up to one good) and MNW. With MNW now resolved at exactly $27/23$, the exact value of the price of EF1 for two agents remains the remaining open question highlighted by the source for the two-agent setting.

Why it is research-level

  • settles OP-67 (Price of MNW for two agents)

Lean declarations

  • mnw_two_agents_welfare_leFor two agents with additive, nonnegative, normalized valuations (v_i(M) = 1) over any number m of goods, every maximum Nash welfare…
  • mnw2_coreGoods are grouped by their owners under an allocation O and an allocation N: A = (O:0, N:0), B = (O:1, N:0), C = (O:0, N:1), D = (O:1,…
  • mnw_two_agents_price_lower_boundFor every c < 27/23 there are two agents with additive, nonnegative, normalized valuations over three goods and an allocation O such that…
  • utilitarian_welfareUtilitarian social welfare of an allocation σ with additive valuations v_i: SW(σ) = ∑_i v_i(X_i), where X_i is the bundle of agent i under…
  • nash_welfareNash welfare of an allocation σ of m goods to n agents with additive valuations v_i: NW(σ) = ∏_i v_i(X_i), where X_i is the bundle of…
  • is_mnw_allocationAn allocation σ is a maximum Nash welfare (MNW) allocation if no allocation τ has larger Nash welfare. When the maximum Nash welfare is…
  • mnw2_sum_groupsFor allocations O, N of m goods to two agents, item values u and weights c(a, b), ∑_g c(O g, N g) u_g equals ∑_{a,b} c(a, b) · u(G_{ab}),…
  • mnw2_bundle_valueIf τ(g) = T(O g, N g) for a map T : {0,1}² → {0,1}, then the value u(X_k) of agent k's bundle under τ is the sum of the group sums…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:1905.04910 — The Price of Fairness for Indivisible Goods

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.