AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Every Minimum EFX Share Allocation Is PROP1 for Monotone Submodular Valuations and Equal Entitlements

medium tier2026-10-03OP-47reviewed by Claude Code中文版

Abstract

Open Problem 3 in Section 6 of arXiv:2502.02815 asks whether every allocation of indivisible goods that is MXS-fair (minimum EFX share) to an agent is necessarily PROP1-fair (proportional up to one good) to that agent, under monotone submodular valuations and equal entitlements. This post presents a positive resolution of the problem. If an agent's assigned bundle were not PROP1-fair, the agent would suffer a strictly positive deficit $\delta > 0$ relative to their proportional share, and every individual good outside their bundle would provide marginal gain at most $\delta$. Examining a certificate allocation witnessing the minimum EFX share property allows the identification of at most one good from each other agent's bundle that has positive marginal value over the recipient's certificate bundle. Eliminating these goods reduces the value of each other bundle below the certificate bundle by the EFX guarantee. The proof then branches on whether every other agent's bundle contains such an item or at least one agent does not: in the former case, submodular monotonicity bounds the grand bundle valuation strictly below its true value; in the latter case, all items from agents without positive marginal goods contribute zero marginal value on top of the certificate bundle and collapse, again yielding a strict contradiction. The theorem has been formalized and mechanically checked in Lean 4 as mxs_fair_imp_prop1_fair_of_submodular.

1. Introduction

The allocation of indivisible goods among multiple agents is studied in discrete fair division. When $m$ indivisible items are distributed among $n$ agents with equal entitlements, classical criteria such as proportionality—which requires that each agent $i$ receive a bundle valued at least $v_i(M)/n$, where $M$ is the grand bundle of all goods—cannot always be satisfied. For example, when a single good is allocated between two agents, one agent receives nothing, which does not achieve exact proportionality.

This motivates the study of relaxations of fairness. One relaxation is proportionality up to one good (PROP1), which stipulates that an agent's bundle either achieves their proportional share directly, or can be brought strictly above the proportional share by the addition of a single good outside their bundle (or by the removal of a good). Another direction investigates share-based criteria derived from envy-freeness up to any good (EFX). An allocation is EFX if no agent envies the bundle of any other agent after the removal of any item from that other agent's bundle. While the existence of EFX allocations in all instances is an open question, arXiv:2502.02815 studies the minimum EFX share (MXS), defined in Definition 10 of that paper. Under MXS, an allocation is fair to an agent if the agent values their assigned bundle at least as much as the bundle they would receive under some hypothetical allocation that is EFX-fair to them. Such a hypothetical allocation serves as an EFX certificate witnessing the fairness of the assignment.

Understanding the relations among these fairness notions is the focus of arXiv:2502.02815. In Section 6 of that paper, Open Problem 3 poses the following question:

"For submodular goods (equal entitlements), does MXS imply PROP1?"

According to the material in arXiv:2502.02815, this implication was previously established for a special case: Lemma 68 in Appendix D of arXiv:2502.02815 proves that MXS implies PROP1 when the valuations are submodular with binary marginals, meaning that every good has a marginal contribution of either 0 or 1 to any bundle. Whether this implication holds for general submodular valuations remained an open question.

This post presents an affirmative answer to Open Problem 3 of arXiv:2502.02815: for any number of agents and goods, every allocation that is MXS-fair to an agent under monotone submodular valuations and equal entitlements is also PROP1-fair to that agent.

The argument proceeds by contradiction. Assuming an allocation fails PROP1-fairness for an agent, the agent falls short of the proportional share by a positive deficit $\delta > 0$, which simultaneously imposes an upper bound of $\delta$ on the marginal gain of any single item outside their bundle. By taking an EFX certificate allocation, we isolate for each other agent at most one item outside the bundle that yields a positive marginal gain over the certificate bundle. Removing these items reduces the value of each other bundle below that of the certificate bundle. We then partition the analysis into two cases based on the number of agents whose bundles contain such positive-marginal items:

  • If every other agent possesses such an item, the total number of removed items is $n - 1$. The remaining items together with the certificate bundle cover all goods outside this set, and submodularity forces the total value of the grand bundle to be bounded by $n \cdot v_i(A) + (n - 1)\delta$, strictly less than $n(v_i(A) + \delta) = v_i(M)$.
  • If at least one other agent has no such item, the items belonging to those agents contribute zero marginal value on top of the certificate bundle. Submodularity allows us to absorb these zero-marginal items without increasing valuation, and the total value is bounded by $n \cdot v_i(A) + (n - 2)\delta < v_i(M)$, once again reaching a contradiction.

This theorem has been formalized and verified in Lean 4 as mxs_fair_imp_prop1_fair_of_submodular. Below, we present the definitions, supporting lemmas, and full proof.

2. Preliminaries

We work in the standard model of discrete fair division of indivisible goods among agents with equal entitlements. We formalize this setting using the definitions matching the Lean development.

Definition 1 (Allocations and Bundles, bundle_of). Let $m, n \in \mathbb{N}$. Let $M = \{0, 1, \dots, m-1\}$ denote the set of indivisible goods, and let $N = \{0, 1, \dots, n-1\}$ denote the set of agents. An allocation is a function $\sigma : M \to N$ specifying for each good $x \in M$ the agent $\sigma(x) \in N$ who receives it. For any agent $i \in N$, the bundle of agent $i$ under $\sigma$, denoted $\text{bundle\_of } \sigma\ i$, is defined by $$\text{bundle\_of } \sigma\ i = \{x \in M \mid \sigma(x) = i\}.$$ Under this definition, the bundles partition $M$ into $n$ pairwise disjoint subsets, some of which may be empty.

Definition 2 (Submodular Valuation Functions, is_submodular). A set function $v : 2^M \to \mathbb{R}$ is normalized if $v(\emptyset) = 0$. It is monotone if for all subsets $S \subseteq T \subseteq M$, $v(S) \le v(T)$. A set function $v : 2^M \to \mathbb{R}$ is submodular (is_submodular) if marginal values diminish as the bundle expands: for all subsets $S \subseteq T \subseteq M$ and every good $j \in M \setminus T$, $$v(T \cup \{j\}) - v(T) \le v(S \cup \{j\}) - v(S).$$

Definition 3 (EFX Fairness). Let $v : 2^M \to \mathbb{R}$ be a valuation function. An allocation $\tau : M \to N$ is EFX-fair to agent $i \in N$ if for every other agent $j \in N \setminus \{i\}$, setting $X = \text{bundle\_of } \tau\ i$ and $B_j = \text{bundle\_of } \tau\ j$, agent $i$ values their own bundle at least as much as $B_j$ after eliminating any subset that agent $i$ strictly values: either $v(B_j) \le v(X)$, or for every subset $S \subseteq B_j$ such that $v(X) < v(X \cup S)$, we have $$v(B_j \setminus S) \le v(X).$$ In particular, when specialized to singleton subsets $S = \{g\}$ with $g \in B_j$ such that $v(X) < v(X \cup \{g\})$, this condition requires that $v(B_j \setminus \{g\}) \le v(X)$.

Definition 4 (Minimum EFX Share, is_mxs_fair). Given a profile of valuation functions $v = (v_i)_{i \in N}$ and an allocation $\sigma : M \to N$, the allocation $\sigma$ is MXS-fair to agent $i \in N$ (is_mxs_fair) if there exists an allocation $\tau : M \to N$ such that $\tau$ is EFX-fair to agent $i$ and $$v_i(\text{bundle\_of } \tau\ i) \le v_i(\text{bundle\_of } \sigma\ i).$$ The allocation $\tau$ is called an EFX certificate for agent $i$ under $\sigma$.

Definition 5 (Proportionality Up to One Good, is_prop1_fair). Given a valuation function $v : 2^M \to \mathbb{R}$, an entitlement weight $w \in \mathbb{R}$, and a bundle $A \subseteq M$, the bundle $A$ is PROP1-fair (is_prop1_fair) if at least one of the following three conditions holds:

  1. $w \cdot v(M) \le v(A)$,
  2. there exists a good $g \in M \setminus A$ such that $w \cdot v(M) < v(A \cup \{g\})$,
  3. there exists a good $c \in A$ such that $w \cdot v(M) < v(A \setminus \{c\})$.

For equal entitlements among $n$ agents, the entitlement weight is $w = 1/n$.

We highlight several aspects of the Lean formalization:

  • Strict versus weak inequalities: In Definition 5, condition 1 uses a weak inequality ($w \cdot v(M) \le v(A)$), while conditions 2 and 3 require strict inequalities ($w \cdot v(M) < v(A \cup \{g\})$ and $w \cdot v(M) < v(A \setminus \{c\})$). This corresponds to the strict form of PROP1 from Definition 5 of arXiv:2502.02815.
  • Deletion branch: Condition 3 allows reaching the proportional share by giving away an item $c \in A$. In the context of goods with monotone valuations, $v(A \setminus \{c\}) \le v(A)$, so condition 3 can never hold unless condition 1 already holds. While the deletion branch is retained in is_prop1_fair for full generality, it plays no positive role in the goods case.
  • Normalization: The valuations are explicitly assumed to satisfy $v_i(\emptyset) = 0$ for all agents $i$.
  • Empty universe convention: When $m = 0$, the universe $M = \emptyset$ is empty, so $A = \emptyset$ and $v_i(M) = 0$; condition 1 is trivially satisfied since $(1/n) \cdot 0 \le 0$.

3. Main result

The main result settles Open Problem 3 of arXiv:2502.02815:

Theorem (mxs_fair_imp_prop1_fair_of_submodular). Let $n, m \in \mathbb{N}$, and let $v = (v_i)_{i \in N}$ be a profile of valuation functions on $2^M$, where $N = \{0, 1, \dots, n-1\}$ and $M = \{0, 1, \dots, m-1\}$. Suppose that for each agent $i \in N$, $v_i(\emptyset) = 0$, $v_i$ is monotone, and $v_i$ is submodular (is_submodular). Let $\sigma : M \to N$ be an allocation and let $i \in N$. If $\sigma$ is MXS-fair to agent $i$ (is_mxs_fair), then the bundle $\text{bundle\_of } \sigma\ i$ is PROP1-fair to agent $i$ (is_prop1_fair) with entitlement weight $w = 1/n$.

The Lean statement formalizes the English theorem by universally quantifying over the number of agents $n$ and goods $m$ as natural numbers, taking valuations $v$ as functions from Fin $n$ to set functions from Finset (Fin $m$) to the real numbers, requiring normalization, monotonicity, and is_submodular for each agent, and asserting that for every allocation $\sigma$ and agent $i$, is_mxs_fair implies is_prop1_fair with entitlement $1/n$ for the bundle bundle_of $\sigma\ i$.

This result settles the open problem in full generality for all monotone submodular valuations. Prior to this theorem, the only known case was established in Lemma 68 in Appendix D of arXiv:2502.02815, which showed the implication under the restriction that all marginal values are binary ($v_i(S \cup \{g\}) - v_i(S) \in \{0, 1\}$). Theorem mxs_fair_imp_prop1_fair_of_submodular removes that restriction completely, demonstrating that the implication holds without any constraint on the magnitudes of the marginal values.

Theorem mxs_fair_imp_prop1_fair_of_submodular (Lean 4, verified)
theorem mxs_fair_imp_prop1_fair_of_submodular :
    ∀ (n m : ℕ) (v : Fin n → Finset (Fin m) → ℝ),
      (∀ i, v i ∅ = 0 ∧ Monotone (v i) ∧ is_submodular (v i)) →
      ∀ (σ : Fin m → Fin n) (i : Fin n), is_mxs_fair v σ i →
        is_prop1_fair (v i) (1 / n) (bundle_of σ i)

4. Proof

We outline the proof idea, then present the four supporting lemmas with their proofs, and finally give the step-by-step argument combining them.

The proof proceeds by contradiction. Assume that $\sigma$ is MXS-fair to agent $i$, but the assigned bundle $A = \text{bundle\_of } \sigma\ i$ fails PROP1-fairness with entitlement $1/n$. Let $u = v_i$ and $V = u(M)$. Failure of PROP1-fairness implies that $u(A) < V/n$, giving a positive deficit $\delta = V/n - u(A) > 0$, and that for every good $g \notin A$, $u(A \cup \{g\}) \le u(A) + \delta$.

By MXS-fairness, there is an EFX certificate allocation $\tau$ with $u(X) \le u(A)$, where $X = \text{bundle\_of } \tau\ i$. For each other agent $j \neq i$, we check if their bundle $B_j = \text{bundle\_of } \tau\ j$ contains an item outside $A$ with positive marginal gain over $X$. If so, we select one such item $g(j)$; by EFX, removing $g(j)$ leaves $B_j$ valued at most $u(X)$. Let $K$ be the set of such agents, and $G = \{g(j) \mid j \in K\}$.

We define $W = X \cup \bigcup_{j \in K} (B_j \setminus \{g(j)\})$. Subadditivity and diminishing returns give $u(W) \le (|K| + 1) u(A)$. We then branch on whether $|K| = n - 1$:

  • If $|K| = n - 1$, the items outside $G$ are contained in $W$, so $A \subseteq W$ and $M \subseteq W \cup G$. Adding $G$ incurs at most $(n - 1)\delta$, giving $V \le n \cdot u(A) + (n - 1)\delta < n(u(A) + \delta) = V$.
  • If $|K| \le n - 2$, items outside $A$ of agents not in $K$ have zero marginal gain over $X$ and collapse into $W \cup A$ without increasing value. Adding $G$ incurs at most $|K|\delta \le (n - 2)\delta$, while the base is at most $(|K| + 2) u(A) \le n \cdot u(A)$, giving $V \le n \cdot u(A) + (n - 2)\delta < V$.

Both cases produce a contradiction. We now establish the four lemmas.

Lemma 1 (submod_union_marginal_le). Let $v : 2^M \to \mathbb{R}$ be a monotone submodular set function. For all subsets $S \subseteq T \subseteq M$ and $U \subseteq M$, $$v(T \cup U) - v(T) \le v(S \cup U) - v(S).$$ Proof. Settled in Lean by induction on the finite set $U$. The base case $U = \emptyset$ gives $0 \le 0$. For the step, adding $u \notin U$, submodularity (is_submodular) on $S \cup U \subseteq T \cup U$ gives $v(T \cup U \cup \{u\}) - v(T \cup U) \le v(S \cup U \cup \{u\}) - v(S \cup U)$. Adding this to the induction hypothesis telescopes the intermediate terms.

Lemma 2 (submod_biUnion_le_sum). Let $v : 2^M \to \mathbb{R}$ be a monotone submodular set function with $v(\emptyset) = 0$. For any finite index set $K$ and collection of subsets $(B_j)_{j \in K}$, $$v\left(\bigcup_{j \in K} B_j\right) \le \sum_{j \in K} v(B_j).$$ Proof. Settled in Lean by induction on $K$. For $K = \emptyset$, $v(\emptyset) = 0 \le 0$. For $K = K' \cup \{k\}$ with $k \notin K'$, let $U = \bigcup_{j \in K'} B_j$. Lemma 1 with $S = \emptyset \subseteq U$ yields $v(U \cup B_k) - v(U) \le v(B_k) - v(\emptyset) = v(B_k)$. Adding the induction hypothesis $v(U) \le \sum_{j \in K'} v(B_j)$ completes the step.

Lemma 3 (submod_add_items_le). Let $v : 2^M \to \mathbb{R}$ be a submodular set function. Let $A \subseteq W \subseteq M$, $\delta \ge 0$, and let $G \subseteq M$ be a finite set such that for every $g \in G$, $g \notin A$ and $v(A \cup \{g\}) \le v(A) + \delta$. Then $$v(W \cup G) \le v(W) + |G| \cdot \delta.$$ Proof. Settled in Lean by induction on $G$. For $G = \emptyset$, $|G| = 0$ and $v(W) \le v(W)$. For $G = G' \cup \{g\}$ with $g \notin G'$, since $A \subseteq W \subseteq W \cup G'$, submodularity implies $v(W \cup G' \cup \{g\}) - v(W \cup G') \le v(A \cup \{g\}) - v(A) \le \delta$. Adding this to the inductive bound $v(W \cup G') \le v(W) + |G'|\delta$ yields $v(W \cup G) \le v(W) + |G|\delta$.

Lemma 4 (submod_zero_marginals). Let $v : 2^M \to \mathbb{R}$ be a monotone submodular set function. Let $X \subseteq W \subseteq M$, and let $R \subseteq M$ be a finite set such that for every $z \in R$, $v(X \cup \{z\}) \le v(X)$. Then $$v(W \cup R) = v(W).$$ Proof. Settled in Lean by induction on $R$. The case $R = \emptyset$ is trivial. For $R = R' \cup \{z\}$ with $z \notin R'$, the hypothesis gives $v(W \cup R') = v(W)$. Since $X \subseteq W \subseteq W \cup R'$, submodularity gives $v(W \cup R' \cup \{z\}) - v(W \cup R') \le v(X \cup \{z\}) - v(X) \le 0$. Monotonicity provides the matching lower bound $v(W \cup R') \le v(W \cup R' \cup \{z\})$, so equality holds.

We now combine these lemmas to prove the theorem.

Fix agent $i \in N$. Write $u = v_i$, $A = \text{bundle\_of } \sigma\ i$, and $V = u(M)$. Since $\sigma$ is MXS-fair to $i$ (is_mxs_fair), there is an allocation $\tau$ that is EFX-fair to $i$ such that $u(X) \le u(A)$, where $X = \text{bundle\_of } \tau\ i$. Note that $u(A) \ge 0$ since $u(\emptyset) = 0$ and $u$ is monotone.

Assume for contradiction that $A$ is not PROP1-fair with entitlement $1/n$. By the negation of Definition 5 (is_prop1_fair), we have:

  1. $u(A) < \frac{1}{n} V$,
  2. for all $g \notin A$, $u(A \cup \{g\}) \le \frac{1}{n} V$,
  3. for all $c \in A$, $u(A \setminus \{c\}) \le \frac{1}{n} V$.

Set $\delta = \frac{1}{n} V - u(A)$. From condition 1, $\delta > 0$, so $V = n(u(A) + \delta)$. Condition 2 gives $u(A \cup \{g\}) \le u(A) + \delta$ for all $g \notin A$. If $M = \emptyset$, then $A = \emptyset$ and $V = 0$, giving $0 < 0$, a contradiction. Thus $M$ is non-empty and $n \ge 1$.

For each $j \in N$, write $B_j = \text{bundle\_of } \tau\ j$. Define the property $P(j, x) \iff x \in B_j \land x \notin A \land u(X) < u(X \cup \{x\})$. Let $$K = \{j \in N \setminus \{i\} \mid \exists x \in M, P(j, x)\}.$$ For each $j \in K$, pick a witness $g(j) \in M$ satisfying $P(j, g(j))$ by choice (Classical.epsilon). By EFX fairness (Definition 3), since $j \neq i$ and $u(X) < u(X \cup \{g(j)\})$, the singleton $\{g(j)\}$ yields $$u(B_j \setminus \{g(j)\}) \le u(X) \quad \text{for all } j \in K.$$

Let $G = \{g(j) \mid j \in K\}$. Then $|G| \le |K|$. Every $x \in G$ satisfies $x \notin A$ and $u(A \cup \{x\}) \le u(A) + \delta$. Define $$W = X \cup \bigcup_{j \in K} (B_j \setminus \{g(j)\}).$$ Applying Lemma 1 with $S = \emptyset \subseteq X$ and $U = \bigcup_{j \in K} (B_j \setminus \{g(j)\})$ gives $u(W) - u(X) \le u(U) - u(\emptyset) = u(U)$. Applying Lemma 2 to $U$ gives $u(U) \le \sum_{j \in K} u(B_j \setminus \{g(j)\}) \le |K| \cdot u(X)$. Since $u(X) \le u(A)$, $$u(W) \le (|K| + 1) u(X) \le (|K| + 1) u(A).$$

Since $K \subseteq N \setminus \{i\}$, we have $|K| \le n - 1$. We branch on whether $|K| = n - 1$.

Case 1: $K = N \setminus \{i\}$, so $|K| = n - 1$.

For any $x \in M \setminus G$, if $\tau(x) = i$ then $x \in X \subseteq W$. If $\tau(x) = j \neq i$, then $j \in K$ and $x \neq g(j)$, so $x \in B_j \setminus \{g(j)\} \subseteq W$. Hence $M \setminus G \subseteq W$. Since $G \cap A = \emptyset$, this gives $A \subseteq W$, and also $M \subseteq W \cup G$.

By monotonicity, $V \le u(W \cup G)$. Applying Lemma 3 with $A \subseteq W$ and $G$ gives $u(W \cup G) \le u(W) + |G| \cdot \delta \le n \cdot u(A) + (n - 1) \delta$. Since $\delta > 0$, $$V \le n \cdot u(A) + (n - 1) \delta < n \cdot u(A) + n \delta = V,$$ a contradiction. Concretely, for $n = 3$ agents and $|K| = 2$, this upper bound gives $V \le 3 u(A) + 2\delta$, which falls short of $V = 3 u(A) + 3\delta$ by $\delta > 0$.

Case 2: $K \subsetneq N \setminus \{i\}$, so $|K| \le n - 2$ and $(|K| : \mathbb{R}) + 2 \le n$.

Define $R = \{x \in M \mid x \notin A \land \tau(x) \neq i \land \tau(x) \notin K\}$. For each $z \in R$, agent $\tau(z) \notin K$ has no items outside $A$ with positive marginal gain over $X$, so $u(X \cup \{z\}) \le u(X)$.

Set $W' = W \cup A$. Every $x \in M$ belongs to $(W' \cup R) \cup G$:

  • If $\tau(x) = i$, then $x \in X \subseteq W \subseteq W'$.
  • If $x \in A$, then $x \in A \subseteq W'$.
  • If $x \notin A$ and $\tau(x) \in K$ with $x = g(\tau(x))$, then $x \in G$.
  • If $x \notin A$ and $\tau(x) \in K$ with $x \neq g(\tau(x))$, then $x \in B_{\tau(x)} \setminus \{g(\tau(x))\} \subseteq W \subseteq W'$.
  • If $x \notin A$ and $\tau(x) \notin K \cup \{i\}$, then $x \in R$.

Thus $M \subseteq (W' \cup R) \cup G$, so $V \le u((W' \cup R) \cup G)$. Since $X \subseteq W'$, Lemma 4 gives $u(W' \cup R) = u(W')$. Lemma 1 with $\emptyset \subseteq W$ and $A$ gives $u(W') = u(W \cup A) \le u(W) + u(A) \le (|K| + 2) u(A)$.

Applying Lemma 3 with $A \subseteq W' \subseteq W' \cup R$ and $G$ gives $$V \le u(W' \cup R) + |G| \cdot \delta \le (|K| + 2) u(A) + |K| \delta.$$ Since $|K| + 2 \le n$, $u(A) \ge 0$, $|K| \le n - 2$, and $\delta > 0$, $$V \le n \cdot u(A) + (n - 2) \delta < n(u(A) + \delta) = V,$$ a contradiction. Concretely, for $n = 3$: if $|K| = 1$, the bound gives $V \le 3 u(A) + \delta < 3 u(A) + 3\delta = V$ (shortfall $2\delta$); if $|K| = 0$, it gives $V \le 2 u(A) \le 3 u(A) < 3 u(A) + 3\delta = V$ (shortfall at least $u(A) + 3\delta$).

Both cases contradict $V = V$, establishing Theorem mxs_fair_imp_prop1_fair_of_submodular.

5. Discussion

Theorem mxs_fair_imp_prop1_fair_of_submodular provides an affirmative resolution to Open Problem 3 of Section 6 in arXiv:2502.02815, showing that for monotone submodular valuations and equal entitlements, every allocation that is MXS-fair to an agent is also PROP1-fair to that agent.

This result broadens what was established in arXiv:2502.02815. In that paper, the implication was established under the restriction of binary marginals (Lemma 68, Appendix D), where the marginal contribution of any good to any bundle is either 0 or 1. Theorem mxs_fair_imp_prop1_fair_of_submodular shows that the implication holds for all monotone submodular valuations without restricting marginal values.

The argument highlights the structural role of submodularity and indicates what the theorem does not cover:

  • Valuations beyond submodularity: The proof uses submodularity at three distinct steps. One step is bounding the value of the union of reduced bundles $W$ using subadditivity, which follows from submodularity and normalization $v(\emptyset) = 0$ (Lemma 2, submod_biUnion_le_sum). Another step is bounding the marginal contribution of the chosen items $G$ on top of supersets of $A$ using diminishing marginal returns (Lemma 3, submod_add_items_le). A further step is absorbing the goods $R$ belonging to agents outside $K$, which depends on the property that goods with non-positive marginal gain over $X$ contribute zero marginal gain over any superset of $X$ (Lemma 4, submod_zero_marginals). For broader classes of valuations—such as subadditive, fractionally subadditive, or general monotone valuations—the third property does not hold in general, and whether MXS implies PROP1 in those settings is not settled by this result.
  • Unequal entitlements: The theorem is formulated for equal entitlements, where each agent's entitlement weight is $w = 1/n$. Under unequal entitlements $(w_i)_{i \in N}$, both proportionality and share-based notions incorporate agent weights. Whether an allocation satisfying a weighted minimum EFX share guarantee must satisfy weighted PROP1 is not addressed by the result.
  • Chores and mixed items: The result applies to goods, where valuations are monotone non-decreasing and $v_i(S) \ge 0$. In fair division of indivisible chores, the definitions of EFX, MXS, and PROP1 involve different item removals and additions, and those relations remain separate.

With Open Problem 3 settled, the relationship between MXS and PROP1 is resolved for submodular valuations under equal entitlements.

Why it is research-level

  • settles OP-47 (Does MXS imply PROP1 for submodular goods?)

Lean declarations

  • mxs_fair_imp_prop1_fair_of_submodularOpen problem 3 of arXiv:2502.02815 has a positive answer: for submodular goods (monotone, v(empty) = 0) and equal entitlements, every…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
  • is_mxs_fairAn allocation is MXS-fair to agent i (minimum EFX share, arXiv:2502.02815, Def. 10) if i's bundle is worth to her at least her bundle in…
  • is_prop1_fairAn allocation is PROP1-fair to an agent with valuation v and entitlement w if her bundle A has v(A) >= w v(M), or v(A + g) > w v(M) for…
  • submod_union_marginal_leFor a monotone submodular set function and S inside T, adding a set U gains at most as much on top of T as on top of S.
  • submod_biUnion_le_sumA monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.
  • submod_add_items_leFor a submodular set function, if every item of G lies outside A and adds at most delta >= 0 to A, then adding G to any superset W of A…
  • submod_zero_marginalsFor a monotone submodular set function, items whose marginal value over X is zero add nothing on top of any superset of X.

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

References

  1. arXiv:2502.02815 — Exploring Relations among Fairness Notions in Discrete Fair Division

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.