The Complexity of Exact MMS Allocations

Public text index for scholarly discovery. It mirrors theorem, lemma, proposition and related statements from this immutable version and does not imply human verification.

1. Definition 3.1
   PF:2026.000014/v1/DEF-3.1

   An \emph{NP metric machine} is a nondeterministic machine that runs in polynomial time and on every branch halts and writes a natural number in binary. A function $f$ is in $\OptP$ if $f(x)$ is, for every $x$, the largest number written on a branch of some NP metric machine on input $x$, and it is in $\OptPlog$ if in addition $f(x)$ has $O(\log|x|)$ bits.

2. Definition 3.2
   PF:2026.000014/v1/DEF-3.2

   A search problem $\Pi$ \emph{reduces} to a search problem $\Pi'$ if there are polynomial-time functions $T_1,T_2$ such that $T_2(x,\bot)=\bot$ and $T_2(x,y)\in\Sol_\Pi(x)$ for every $x$ and \emph{every} $y\in\Sol_{\Pi'}(T_1(x))$.

3. Theorem 3.3:
   PF:2026.000014/v1/THM-3.3

   A function that is complete for $\OptP$ under metric reductions is $\FPNP$-complete, and a function that is complete for $\OptPlog$ under metric reductions is $\FPNPlog$-complete.

4. Definition 3.4:
   PF:2026.000014/v1/DEF-3.4

   The class $\FNPOptP$ consists of the partial multi-valued functions $F$ for which there are a polynomial-time nondeterministic transducer $T$ and a function $g\in\OptPlog$ such that, for every $x$, $F(x)$ is the set of strings that $T$ outputs on its accepting branches on input $\langle x,\mathrm{bin}(g(x))\rangle$. We view $F$ as the search problem $\{(x,y):y\in F(x)\}$, so that $\Sol_F(x)=F(x)$ if $F(x)\neq\emptyset$, and $\Sol_F(x)=\{\bot\}$ otherwise. A search problem $\Pi$ is \emph{in} this class if some such $F$ solves it: for every $x$, $F(x)=\emptyset$ if $x$ has no solution in $\Pi$, and $\emptyset\neq F(x)\subseteq\Sol_\Pi(x)$ otherwise.

5. Proposition 3.5
   PF:2026.000014/v1/PROP-3.5

   For arbitrary $n$ and arbitrary additive valuations: \item[(i)] \MMSV{} is in $\OptP$, and in $\OptPlog$ with values in unary, \item[(ii)] \MMSA{} is in $\FPNP$, and with values in unary it is in $\FNPOptP$, \item[(iii)] \MMSE{} is in $\PNP$, and with values in unary it is in $\PNPlog$.

6. Proposition 3.7
   PF:2026.000014/v1/PROP-3.7

   For every fixed $n$, with values in unary, \MMSV, \MMSA{} and \MMSE{} are solvable in polynomial time.

7. Lemma 3.8:
   PF:2026.000014/v1/LEM-3.8

   \OMS{} is $\PNP$-complete.

8. Lemma 3.9
   PF:2026.000014/v1/LEM-3.9

   Let $\varphi$ be a satisfiable CNF formula over $z_1,\dots,z_k$, and let $\beta=\varphi$ and $\alpha=\varphi\wedge z_k$. Then $\varphi\in\OMS$ if and only if $\alpha$ is satisfiable and $\lex(\alpha)\geq\lex(\beta)$.

9. Lemma 3.10:
   PF:2026.000014/v1/LEM-3.10

   Let $\mathcal{M}$ be an NP metric machine that writes exactly $p=p(|x|)$ bits on every branch on input $x$. There is a polynomial-time map from $x$ to a $3$-CNF formula $\varphi$ over variables $z_1,\dots,z_k$ with $k\geq p$, the \emph{output bits} $z_1,\dots,z_p$ being the first, such that the output bits of every model of $\varphi$, read with $z_1$ most significant, are the number written on some branch of $\mathcal{M}$ on input $x$, and every number written on a branch arises in this way. Moreover, for every polynomial-time relation $R$ with polynomially bounded third argument, there is a polynomial-time map from $x$ to a $3$-CNF formula $\eta_b$ over $z_1,\dots,z_p$, variables $y_1,\dots,y_{p'}$, a varia…

10. Lemma 3.11: cf.~
    PF:2026.000014/v1/LEM-3.11

    There is a polynomial-time map from a $3$-CNF formula $\varphi$ over $z_1,\dots,z_k$ to a \POS{} instance $\psi$ whose variables include $z_1,\dots,z_k$, such that (a) every variable of $\psi$ occurs in some clause of $\psi$, (b) the restriction to $z_1,\dots,z_k$ of every exactly-$1$ model of $\psi$ is a model of $\varphi$, and (c) every model of $\varphi$ arises as such a restriction.

11. Lemma 3.12:
    PF:2026.000014/v1/LEM-3.12

    Let $A$ be an $\NP$-complete language, $B$ a language, and $f$ a polynomial-time function such that for every $k\geq1$ and all $x_1,\dots,x_{2k}$ with $x_{j+1}\in A\Rightarrow x_j\in A$ for each $j<2k$, the number $|\{j:x_j\in A\}|$ is odd if and only if $f(x_1,\dots,x_{2k})\in B$. Then $B$ is $\PNPlog$-hard.

12. Lemma 4.1
    PF:2026.000014/v1/LEM-4.1

    Let $c_1,\dots,c_r$ be digit blocks on $\goods$ whose totals $T_1,\dots,T_r$ are divisible by $n$. Let $\rho_j=T_j+1$, $W_r=1$ and $W_j=\rho_{j+1}W_{j+1}$ for $j<r$, and let $w(g)=\sum_jW_jc_j(g)$ and $\tau=\sum_jW_jT_j/n$. Then $w(\goods)=n\tau$, and $w(S)=\tau$ if and only if $S$ meets every block.

13. Lemma 4.2
    PF:2026.000014/v1/LEM-4.2

    Let $F_1,\dots,F_h$ be a partition of the digit blocks of Lemma 4.1, with unions of supports $\goods_1,\dots,\goods_h$ covering $\goods$. A partition $\allocation$ of $\goods$ is balanced if and only if its restriction to each $\goods_l$ is a configuration of $F_l$. Conversely, given a configuration $\allocation_l$ of each $F_l$ and bijections $f_l$ from the bundles of $\allocation_l$ to $\{1,\dots,n\}$, the sets $\allocation(j)=\bigcup_l f_l^{-1}(j)$ form a balanced partition if and only if, for every good $g\in\goods_l\cap\goods_{l'}$, the bundles of $\allocation_l$ and $\allocation_{l'}$ containing $g$ are mapped to the same index. In particular, if $\goods_l$ and $\goods_{l'}$ are disjoint, the two confi…

14. Definition 4.3
    PF:2026.000014/v1/DEF-4.3

    Let $\goods$ be a set of goods with positive integer weights $w$ and $w(\goods)=n\tau$, and let $\delta_1,\dots,\delta_n\colon\goods\to\ints$ be charges with $\delta_i(\goods)=0$ and $|\delta_i(S)|\leq M$ for all $i$ and all $S\subseteq\goods$. Let $I(\delta_1,\dots,\delta_n)$ be the instance with agents $\{1,\dots,n\}$ and goods $\goods$ in which agent $i$ has the valuation $\utility_i(g)=K\cdot w(g)+\delta_i(g)$, for $K=2M+1$.

15. Lemma 4.4
    PF:2026.000014/v1/LEM-4.4

    Let $\allocation$ be a partition of the goods of $I(\delta_1,\dots,\delta_n)$ (Definition 4.3). \item[(i)] If $\utility_i(\allocation(j))\geq K\tau-M$ for some agent $i$ and all $j$, or if $\utility_i(\allocation(i))\geq K\tau-M$ for all $i$, then $\allocation$ is balanced. \item[(ii)] If balanced partitions exist and $d_i\leq M$, then $\mmsshare_i=K\tau-d_i$.

16. Lemma 4.5
    PF:2026.000014/v1/LEM-4.5

    There is a polynomial-time computable function mapping a CNF formula $\varphi$ as in Section 3.4 to a set of goods $X_\varphi=\{P_i,N_i : i\leq k\}\cup\{s^c_j : c\leq q,\ j<\ell_c\}\cup\{a\}$ with positive integer weights $w$ such that $w(X_\varphi)=2\tau_\varphi$ for an integer $\tau_\varphi$, and: \item[(a)] every ledger $S$ contains exactly one of $P_i,N_i$ for each $i$, and $\sigma_S$ is a model of $\varphi$, \item[(b)] every model of $\varphi$ equals $\sigma_S$ for some ledger $S$. Clauses of width $1$ are allowed, and such a clause has no slack goods.

17. Lemma 4.6
    PF:2026.000014/v1/LEM-4.6

    Let $\psi_1,\dots,\psi_\Gamma$ be gadgets with $\nv$ variables and $\no$ occurrences in all, let $n=2\no+\nv+1$, and let $a$ be a good. There are a set of goods $G_\gear$ as in the vocabulary above, of size $3(n-1)+\nv+1$, and seven digit blocks with digit $0$ on all goods outside $G_\gear$ and with totals polynomial in $n$, all computable in polynomial time, with the following properties. Let $\allocation$ be a configuration of the seven blocks, with $n$ bundles, and $\Lambda$ its ledger. \item[(i)] \emph{Locality:} every bundle other than $\Lambda$ consists of exactly one tooth, one gap and one edge, and all three belong to the same gadget. \item[(ii)] \emph{Ledger:} $\Lambda$ consists of $a$ and exactly o…

18. Lemma 4.8
    PF:2026.000014/v1/LEM-4.8

    Let $I=I(\chi,\dots,\chi)$ (Definition 4.3) have $n$ agents with identical valuations, let $\zeta$ be a grading with $\Delta_\zeta\leq M$, and let $\Sigma$ be a nonempty set of assignments. Let $\allocation\mapsto\sigma_\allocation$ be a polynomial-time map from the balanced partitions to $\Sigma$ such that \item[\textup{(GL1)}] $\chi(\allocation)=-\Delta_\zeta+\val_\zeta(\sigma_\allocation)$ for every balanced partition $\allocation$, and \item[\textup{(GL2)}] every $\sigma\in\Sigma$ equals $\sigma_\allocation$ for some balanced partition $\allocation$. Then $\mmsshare=K\tau-\Delta_\zeta+\max_{\sigma\in\Sigma}\val_\zeta(\sigma)$, MMS-fair allocations exist and are balanced, and $\val_\zeta(\sigma_\allocatio…

19. Corollary 4.9
    PF:2026.000014/v1/COR-4.9

    Let $x\mapsto I_x$ be a polynomial-time map to instances as in Lemma 4.8, such that $K$, $\tau$ and $\Delta_\zeta$ are computable from $x$ in polynomial time, and let $V(x)=\max_{\sigma\in\Sigma}\val_\zeta(\sigma)$. Then $T_1(x)=(I_x,1)$ and $T_2(x,y)=y-K\tau+\Delta_\zeta$ form a metric reduction from $V$ to \MMSV. Moreover, the correct outputs of \MMSA{} on $I_x$ do not include $\bot$, and every correct output $\allocation$ is balanced and has $\val_\zeta(\sigma_\allocation)=V(x)$.

20. Definition 5.1: the instance $I_x$
    PF:2026.000014/v1/DEF-5.1

    Let $X_\varphi$ be the halving gadget of Lemma 4.5 for $\varphi$, with weights $w$ and $w(X_\varphi)=2\tau$, and let $\chi=\chinegz$ be its negative form for the grading $\zeta$. Let $M=\Delta_\zeta=2^p-1$ and $K=2\Delta_\zeta+1$. Then $I_x=I(\chi,\chi)$ is the instance with two agents and goods $X_\varphi$ in which both agents have the valuation $\utility=K\cdot w+\chi$.

21. Lemma 5.2
    PF:2026.000014/v1/LEM-5.2

    The balanced partitions of $I_x$ (Definition 5.1) are exactly the pairs of a ledger $S$ of $X_\varphi$ and its anchor side, and $I_x$ satisfies (GL1) and (GL2) of Lemma 4.8 with $\Sigma$ the set of models of $\varphi$ and $\sigma_\allocation=\sigma_S$ for the ledger $S$ of $\allocation$. Hence $\mmsshare(I_x)=K\tau-\Delta_\zeta+f(x)$. Moreover, $I_x$ is computable from $x$ in polynomial time, and every value has $O(p+k+q)$ bits.

22. Theorem 5.3
    PF:2026.000014/v1/THM-5.3

    \MMSV{} is $\OptP$-complete under metric reductions, and hence $\FPNP$-complete. \MMSA{} is $\FPNP$-complete. Hardness holds already for $n=2$ agents with identical valuations, on instances that always admit an MMS-fair allocation.

23. Definition 6.1: the core $ _2$
    PF:2026.000014/v1/DEF-6.1

    The \emph{core goods} are the four \emph{vertices} $A_1,A_2,B_1,B_2$ and the four \emph{edges} $V_1,V_2,U_1,U_2$ of the cycle, and a \emph{shadow} $\bar A_i,\bar B_i$ of each vertex. The goods $A_i,\bar A_i$ are the \emph{$A$-side} goods, and $B_i,\bar B_i$ the \emph{$B$-side} goods, as each edge of the cycle has one endpoint of each kind. They carry six digit blocks $\sideA,\sideB,\edg,\rol,L_1,L_2$, whose roles we explain below. Their digits are in Table 9 in the appendix. Their totals are $4$ for the first four blocks and $12$ for the link blocks $L_1$ and $L_2$, so that, with $n=4$ bundles, a bundle meets them if its digit sums are $(1,1,1,1,3,3)$.

24. Lemma 6.2
    PF:2026.000014/v1/LEM-6.2

    The partitions of the core goods into four bundles that meet all six blocks of Definition 6.1 are exactly $\PV$ and $\PU$.

25. Lemma 6.3
    PF:2026.000014/v1/LEM-6.3

    Both $\dV$ and $\dU$ sum to $0$. The perturbation $\dV$ has offset $0$ on every bundle of $\PV$, and on $\PU$ it has offset $-s$ on the bundles of $B_1$, $B_2$ and $\bar B_1$, and $3s$ on the bundle of $\bar B_2$. Symmetrically, $\dU$ has offset $0$ on every bundle of $\PU$, and on $\PV$ the same offsets as $\dV$ on $\PU$.

26. Lemma 6.4
    PF:2026.000014/v1/LEM-6.4

    (a) If the bundles of $\PU$ are handed to the four agents, one each, some type-$V$ agent receives a bundle of $\Bad_V$. The same holds for $\PV$, type $U$ and $\Bad_U$. (b) For each type-$V$ agent $i$ and every $S\in\Bad_V$, the bundles of $\PU$ can be handed out so that $i$ receives $S$ and every other agent receives a bundle of offset at least $0$ for her perturbation.

27. Proposition 6.5
    PF:2026.000014/v1/PROP-6.5

    Let $w$ be given by Lemma 4.1 for the six blocks of $\Sigma_2$ (Definition 6.1), and let $I_0=I(\dV,\dV,\dU,\dU)$ (Definition 4.3) be the instance with four agents on the twelve core goods, with $M=4s$. Then $\mmsshare_i=K\tau$ for every agent $i$, and $I_0$ admits no MMS-fair allocation.

28. Definition 6.6
    PF:2026.000014/v1/DEF-6.6

    Let $s\geq1$. A \emph{gated instance} is an instance $I(\dV+\chi,\dV,\dU,\dU)$ of Definition 4.3, with agents $\dial,\blkV$, $\blkUa,\blkUb$, in which \item[(G1)] the goods are the core goods of Definition 6.1 and further goods, \item[(G2)] the weights are given by Lemma 4.1 for the six core blocks, which have digit $0$ on all goods outside the core, and further \emph{gate blocks}, which have digit $0$ on all core goods other than the $B$-side goods $B_1,B_2,\bar B_1,\bar B_2$, \item[(G3)] the dial's charge $\chi$ sums to $0$ and is $0$ on all core goods other than $\bar B_2$, and \item[(G4)] $M\geq s$. The goods outside the core, together with the $B$-side goods that the gate blocks see, are the \emph{gate …

29. Lemma 6.7
    PF:2026.000014/v1/LEM-6.7

    A partition $\allocation$ of the goods of a gated instance is balanced if and only if (i) its restriction to the core goods is $\PV$ or $\PU$, its \emph{phase}, (ii) its restriction to the gate goods is a configuration of the gate blocks, and (iii) for each $B$-side good seen by a gate block, the bundle of the configuration containing it lies in the bundle of the phase named after it. Conversely, if the $B$-side goods seen by the gate blocks lie in distinct bundles of a configuration of the gate blocks, then every phase and this configuration combine to a balanced partition by every bijection between their bundles that satisfies (iii).

30. Lemma 6.8
    PF:2026.000014/v1/LEM-6.8

    Let $I$ be a gated instance, and let $\dr$ and $\rl$ be integers with $0\leq\dr\leq M$ such that the following two conditions hold. \item[\textup{(drop)}] Balanced partitions of phase $\PV$ exist, and some balanced partition of phase $\PV$ has $\chi\geq-\dr$ on every bundle. Every balanced partition, of either phase, has $\chi\leq-\dr$ on some bundle other than the host bundle. \item[\textup{(relief)}] Every balanced partition of phase $\PU$ has $\chi\leq\rl$ on every bundle in $\Bad_V$, and some balanced partition of phase $\PU$ has $\chi(S)=\rl$ for some $S\in\Bad_V$. Then every blocker has maximin share $K\tau$, the dial has maximin share $K\tau-\dr$, and $I$ admits an MMS-fair allocation if and only if $…

31. Lemma 6.9
    PF:2026.000014/v1/LEM-6.9

    In every partition into four bundles that all meet the drop block: the bundles of $B_1$ and of $\bar B_1$ hold no other good of the block, the bundle of $B_2$ holds, besides $B_2$, exactly a ledger $S$ of $X_\beta$, the bundle of $\bar B_2$ holds exactly the anchor side $X_\beta\setminus S$, and $B_2$ and $\bar B_2$ lie in different bundles. Every ledger $S$ gives such a partition.

32. Lemma 6.10
    PF:2026.000014/v1/LEM-6.10

    In every partition into four bundles that all meet the relief block: the bundles of $B_2$ and of $\bar B_2$ hold no other good of the block, and the other two bundles hold, as goods of the block, either \item[(S)] $\{\gamma_l\}\cup T$ and $\{\gamma_{7-l}\}\cup(X_\alpha\setminus T)$, for a half $T$ and some $l\in\{3,4\}$, or \item[(U)] $\{\gamma_3,\gamma_4\}$ and $X_\alpha$. Every half $T$ gives an instance of (S), and (U) always meets the block.

33. Lemma 6.11
    PF:2026.000014/v1/LEM-6.11

    Let $\beta$ be satisfiable. In every configuration of the drop block, the classes of $B_1$ and $\bar B_1$ are $\{B_1\}$ and $\{\bar B_1\}$, and carry charge $0$. The class of $B_2$, the \emph{drop ledger class}, is $\{B_2\}\cup S$ for a ledger $S$, and carries $-(\Delta-\val(\sigma))\leq-(\Delta-\lex(\beta))$, where $\sigma=\sigma_S$ is the model of $\beta$ encoded by $S$. The class of $\bar B_2$, the \emph{drop anchor class}, is $X_\beta\setminus S$, and carries $\Delta-\val(\sigma)\geq0$. Some configuration has a drop ledger class of charge exactly $-(\Delta-\lex(\beta))$.

34. Lemma 6.12
    PF:2026.000014/v1/LEM-6.12

    Let $\rl=\lex(\alpha)$ if $\alpha$ is satisfiable and $\rl=0$ otherwise. In every configuration of the relief block, the classes of $B_2$ and $\bar B_2$ are $\{B_2\}$ and $\{\bar B_2\}$, and carry charge $0$, and the two classes not containing $B_2$ or $\bar B_2$ are the \emph{relief classes}. In case (S), they are $\{\gamma_l\}\cup T$ and $\{\gamma_{7-l}\}\cup(X_\alpha\setminus T)$ for a half $T$ and some $l\in\{3,4\}$, and carry $\chilex(T)$ and $-\chilex(T)$. In case (U), they are $\{\gamma_3,\gamma_4\}$ and $X_\alpha$, and both carry $0$. Every relief class carries at most $\rl$. Case (U) gives a configuration, and some configuration has a relief class of charge exactly $\rl$.

35. Definition 6.13: the instance $I_ , $
    PF:2026.000014/v1/DEF-6.13

    Let $\alpha$ and $\beta$ be CNF formulas over $z_1,\dots,z_k$ as in Section 3.4, and let $s=\Delta$ (this choice is explained in Section 6.5). The goods of $I_{\alpha,\beta}$ are \item the twelve goods of the core $\Sigma_2$, \item the goods $X_\beta$ of Lemma 4.5 for $\beta$, with weights $w_\beta$ and $w_\beta(X_\beta)=2\tau_\beta$, where the anchor of $X_\beta$ is the core good $\bar B_2$ and all other goods are fresh (the conclusions of Lemma 4.5 concern weights and do not depend on names), \item the goods $X_\alpha$ of Lemma 4.5 for $\alpha$, with weights $w_\alpha$ and $w_\alpha(X_\alpha)=2\tau_\alpha$, all of them fresh, with anchor $a_\alpha$, \item fresh goods $\gamma_3,\gamma_4$. The two halving ga…

36. Lemma 6.14
    PF:2026.000014/v1/LEM-6.14

    Let $\beta$ be satisfiable, and let $\rl$ be as in Lemma 6.12 for $\alpha$. \item[(a)] The balanced partitions of $I_{\alpha,\beta}$ (Definition 6.13) are exactly the combinations, in the sense of Lemma 4.2, of a phase of the core, a configuration of the drop block and a configuration of the relief block, glued at the $B$-side goods: each class that contains a $B$-side good lies in the bundle named after it, and the two relief classes lie in the bundles of $B_1$ and $\bar B_1$, in either order. Every such combination is balanced. \item[(b)] Consequently, in every balanced partition, the host bundle holds the drop anchor class, with $\chi\geq0$. The bundle of $B_2$ holds the drop ledger class, with $\chi\leq-…

37. Lemma 6.15
    PF:2026.000014/v1/LEM-6.15

    Let $\beta$ be satisfiable with $\lex(\beta)\geq1$. Then $I_{\alpha,\beta}$ (Definition 6.13) satisfies the hypotheses of Lemma 6.8 with $\dr=\Delta-\lex(\beta)$ and with $\rl$ as in Lemma 6.12 for $\alpha$. Hence $\mmsshare_{\blkV}=\mmsshare_{\blkUa}=\mmsshare_{\blkUb}=K\tau$, $\mmsshare_{\dial}=K\tau-\Delta+\lex(\beta)$, and $I_{\alpha,\beta}$ admits an MMS-fair allocation if and only if $\alpha$ is satisfiable and $\lex(\alpha)\geq\lex(\beta)$.

38. Theorem 6.16
    PF:2026.000014/v1/THM-6.16

    \MMSE{} is $\PNP$-complete. Hardness holds already for $n=4$ agents with additive valuations, of which exactly three are distinct: agent $\blkV$ has $\utility_{\blkV}=K\cdot w+\dV$, agents $\blkUa$ and $\blkUb$ have $\utility_{\blkUa}=\utility_{\blkUb}=K\cdot w+\dU$, and agent $\dial$ has $\utility_{\dial}=\utility_{\blkV}+\chi$.

39. Definition 7.1: the instance $J_ , $
    PF:2026.000014/v1/DEF-7.1

    Let $\varphi$ be a satisfiable $3$-CNF formula and $\zeta$ a grading of its variables. Let $\psi$ be the \POS{} instance of Lemma 3.11 for $\varphi$, with $\nv$ variables, $\nc$ clauses and $\no=3\nc$ occurrences. Apply Lemma 4.6 to the single gadget $\psi$, a fresh anchor $a$, and $n=2\no+\nv+1$, and let $w$ be given by Lemma 4.1 for its seven blocks, with $n$ bundles. The charge $\chi$ is $\chi(a)=-\Delta_\zeta$, $\chi(P^{z})=\zeta_z$ for each variable $z$ of $\varphi$, and $0$ on all other goods. Let $M=\Delta_\zeta$ and $K=2\Delta_\zeta+1$. Then $J_{\varphi,\zeta}=I(\chi,\dots,\chi)$ is the instance with $n$ agents and goods $G_\gear$ in which all agents have the valuation $\utility=K\cdot w+\chi$.

40. Lemma 7.2
    PF:2026.000014/v1/LEM-7.2

    The instance $J_{\varphi,\zeta}$ of Definition 7.1 satisfies (GL1) and (GL2) of Lemma 4.8 with $\Sigma$ the set of exactly-$1$ models of $\psi$. Hence $\mmsshare(J_{\varphi,\zeta})=K\tau-\Delta_\zeta+\lex_\zeta(\varphi)$, and $\sigma_\allocation|_\varphi$ is a model of $\varphi$ of graded value $\lex_\zeta(\varphi)$ for every MMS-fair allocation $\allocation$. Moreover, $J_{\varphi,\zeta}$ is computable in polynomial time, and all its values are polynomial in $|\varphi|+\Delta_\zeta$.

41. Theorem 7.3
    PF:2026.000014/v1/THM-7.3

    With values in unary and the number of agents free, \MMSV{} is $\OptPlog$-complete under metric reductions, and hence $\FPNPlog$-complete, already for identical valuations.

42. Lemma 7.4
    PF:2026.000014/v1/LEM-7.4

    $\lex_{\zeta'}(\varphi')=2g(x)+[F(x)\neq\emptyset]$. Every model $\sigma$ of $\varphi'$ of this graded value has $\sigma(b)=[F(x)\neq\emptyset]$, and if $\sigma(b)=1$, then the witness variables of $\sigma$ form a pair $t=(y,\omega)$ with $R(x,g(x),t)$, and $y\in F(x)$.

43. Theorem 7.5
    PF:2026.000014/v1/THM-7.5

    With values in unary and the number of agents free, \MMSA{} is $\FNPOptP$-complete, already for identical valuations.

44. Definition 8.1: the core $ _m$
    PF:2026.000014/v1/DEF-8.1

    The \emph{core goods} are the $2m$ \emph{vertices} $A_i,B_i$ and the $2m$ \emph{edges} $V_i,U_i$ of the cycle, for $i\leq m$, and a \emph{shadow} $\bar A_i,\bar B_i$ of each vertex, $6m$ goods in all. They carry six digit blocks, with digit $0$ on all goods not listed: $\sideA$ is $1$ on the $A$-side goods $A_i,\bar A_i$, $\sideB$ is $1$ on the $B$-side goods $B_i,\bar B_i$, $\edg$ is $1$ on the edges, and $\rol$ is $1$ on $A_i$ and $\bar B_i$, and the link blocks are L_1&:\ A_i,\bar A_i\mapsto i,\quad V_i\mapsto m+1-i,\quad U_i\mapsto m+1-i^+,\\ L_2&:\ B_i,\bar B_i\mapsto i,\quad V_i,U_i\mapsto m+1-i. Their totals are $2m$ for the first four blocks and $2m(m+1)$ for the link blocks, so that, with $n=2m$ bun…

45. Lemma 8.2
    PF:2026.000014/v1/LEM-8.2

    Let $m\geq2$. \item[(a)] The partitions of the core goods of $\Sigma_m$ (Definition 8.1) into $2m$ bundles that meet all six blocks are exactly $\PV$ and $\PU$. \item[(b)] Both $\dV$ and $\dU$ sum to $0$. The perturbation $\dV$ has offset $0$ on every bundle of $\PV$, and on $\PU$ it has offset $-s$ on every deficit bundle, $3s$ on the host bundle, and $s$ on the other safe bundles. Symmetrically, $\dU$ has offset $0$ on every bundle of $\PU$, and on $\PV$ the same offsets as $\dV$ on $\PU$. In particular, the bundles of $\bar B_2,\dots,\bar B_m$ are safe. \item[(c)] Let there be $m$ agents of each type. If the bundles of $\PU$ are handed to the $2m$ agents, one each, some type-$V$ agent receives a bundle of…

46. Lemma 8.3
    PF:2026.000014/v1/LEM-8.3

    Let $I$ be a gated instance over $\Sigma_m$ (Definition 6.6 and Definition 8.1) with dials $D_1,\dots,D_r$, where $r\geq1$. For each dial $D_e$, let $\dr_e$ and $\rl_e$ be integers with $0\leq\dr_e\leq M$ such that the following two conditions hold. \item[\textup{(drop)}] Balanced partitions of phase $\PV$ exist, and some balanced partition of phase $\PV$ has $\chi_e\geq-\dr_e$ on every bundle. Every balanced partition of phase $\PV$ has $\chi_e\leq-\dr_e$ on some bundle, and every balanced partition of phase $\PU$ has $\chi_e\leq s-\dr_e$ on some bundle in $\Bad_V$. \item[\textup{(relief)}] As in Lemma 6.8 for $\chi_e$ and $\rl_e$, where the balanced partition $\allocation$ with $\chi_e(S)=\rl_e$ has in add…

47. Definition 8.4
    PF:2026.000014/v1/DEF-8.4

    For a positive exactly-$1$ instance $\psi$ and a fresh variable $w$, let $\psi^w=\{C\cup\{w\}:C\text{ a clause of }\psi\}$. We call $w$ the \emph{wildcard} of $\psi^w$.

48. Lemma 8.5
    PF:2026.000014/v1/LEM-8.5

    Let $\psi^w$ be as in Definition 8.4. (a) $\psi^w$ is satisfiable. (b) $\psi^w$ has an exactly-$1$ model with $w$ false if and only if $\psi$ is satisfiable.

49. Definition 8.6: the instance $J$
    PF:2026.000014/v1/DEF-8.6

    Let $(\alpha_1,\beta_1),\dots,(\alpha_r,\beta_r)$ be normalised \POS{} instances. For each $e$, let the \emph{$\beta_e$-gadget} be $\psi^w_{\beta_e}=\beta_e^w$ (Definition 8.4) and the \emph{$\alpha_e$-gadget} be $\psi^w_{\alpha_e}=\alpha_e^w$, each with its own fresh wildcard $w$, and write $P^\beta_e,N^\beta_e$ and $H^\beta_e$ for the terminals and the hub of the wildcard's gear in the $\beta_e$-gadget, and $P^\alpha_e,N^\alpha_e$ and $H^\alpha_e$ likewise for $\alpha_e$. Let $N=2\no+\nv+1$, where $\nv$ and $\no$ are the total numbers of variables and occurrences of the $2r$ gadgets. A gadget with $v$ variables and $o$ occurrences contributes $2o+v$ to $N$, so $N$ has the parity of $\nv+1$. If $N$ is odd, …

50. Lemma 8.7
    PF:2026.000014/v1/LEM-8.7

    The instance $J$ of Definition 8.6 is a gated instance over $\Sigma_m$: in particular, $|\delta_i(S)|\leq M$ for every agent $i$ and every bundle $S$. Its values are polynomial in the total size of the instances $\alpha_e,\beta_e$, so $J$ is computable in polynomial time with values in unary.

51. Lemma 8.8
    PF:2026.000014/v1/LEM-8.8

    Let $\psi^w$ be a gadget of $J$ (Definition 8.6) with wildcard $w$, hub $H^w$ and terminals $P^w,N^w$, for a normalised \POS{} instance $\psi$. In every balanced partition of $J$, exactly one of $P^w,N^w$ lies in $\Lambda$, and the other lies in the bundle of $H^w$, which is not $\Lambda$ and holds no other terminal. The gadget can be in wildcard mode $w=1$ (with $P^w\in\Lambda$) in some balanced partition always, and in wildcard mode $w=0$ (with $N^w\in\Lambda$) in some balanced partition if and only if $\psi\in\POS$. The wildcard modes of all gadgets, the phase, and the matching of the bundles of the gear block other than $\Lambda$ to the bundles of the phase other than the host bundle can be chosen indepe…

52. Lemma 8.9
    PF:2026.000014/v1/LEM-8.9

    The instance $J$ of Definition 8.6 satisfies the hypotheses of Lemma 8.3 with $s=4$, $\dr_e=2\cdot[\beta_e\notin\POS]$ and $\rl_e=2\cdot[\alpha_e\in\POS]$. Hence every blocker has maximin share $K\tau$, every dial $D_e$ has maximin share $K\tau-\dr_e$, and $J$ admits an MMS-fair allocation if and only if $\alpha_e\in\POS$ and $\beta_e\notin\POS$ for some $e$.

53. Theorem 8.10
    PF:2026.000014/v1/THM-8.10

    With values in unary and the number of agents free, \MMSE{} is $\PNPlog$-complete. Hardness holds for instances with $2m$ agents holding $r+2$ distinct valuations, for $r\leq m-1$: $m$ agents of type $U$ share one valuation, $m-r$ blockers of type $V$ share another, and each of the $r$ dials has her own. For every fixed number of agents, the problems are in $\P$.

54. Definition 10.1: the gear block
    PF:2026.000014/v1/DEF-10.1

    \emph{Input:} gadgets $\psi_1,\dots,\psi_\Gamma$, a number of bundles $n=2\no+\nv+1$, and an anchor $a$. \emph{Occurrences.} An \emph{occurrence} is a triple $o=(g,z,j)$, the $j$-th occurrence of the variable $z$ in gadget $g$, and $C(o)$ is its clause. We write $k_{g,z}$ for the number of occurrences of $z$ in $\psi_g$ and $r_C=|C|$, so that $\sum_{g,z}k_{g,z}=\sum_Cr_C=\no$. \emph{Units.} A \emph{unit} is a gear $(g,z)$, a \emph{$U$-absorber} $(g,C)$, or a \emph{$V$-absorber} $(g,C)$ for a clause $C$ of $\psi_g$. We number the units $1,\dots,L$ and write $\lambda_v$ for the number of unit $v$, we number the gears $1,\dots,\nv$ and write $\gidx_{g,z}$ for the number of gear $(g,z)$, and we number the clause…

55. Lemma 10.2
    PF:2026.000014/v1/LEM-10.2

    Let $\allocation$ be a configuration of the seven blocks with $n=2\no+\nv+1$ bundles, and $\Lambda$ the bundle of $a$. Then $\Lambda$ consists of $a$ and exactly $\nv$ edges, and every other bundle is a triple of a tooth, a gap and an edge of one of the following six forms, for a gear $(g,z)$ with $k=k_{g,z}$ occurrences and $C_j=C(g,z,j)$, or for a clause $C$ of a gadget $\psi_g$ with $r_C$ variables: \[ {llll} \text{form} & \text{tooth} & \text{gap} & \text{edge}\\\hline \text{T1} & A^{g,z}_1 & H^{g,z} & P^{g,z}\\ \text{T2} & A^{g,z}_{k+1} & H^{g,z} & N^{g,z}\\ \text{T3}\ (1\leq j\leq k) & A^{g,z}_j & B^{g,z}_j & \text{a $V$-copy of }C_j\\ \text{T4}\ (1\leq j\leq k) & A^{g,z}_{j+1} & B^{g,z}_j & \text{a $U…