| paper | Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division |
| authors | Jarosław Byrka, F. Malinka, Tomasz Ponitka |
| venue | AAAI 2026 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 6.2
statement extracted from the paper’s text layer
Given complete pair-demand types \(T\), rational type masses \(\mu_t\), item-category supplies \(\rho_g\) with \(\sum_g \rho_g=2\), and weights \(w_{t,g}\), find masses \(\pi_{t,B}\) over integral two-item multisets \(B\) satisfying \(\sum_B \pi_{t,B}=\mu_t\) and \(\sum_{t,B}\pi_{t,B}n_g(B)=\rho_g\), such that every positive-support pair \( (t,B),(u,D) \) satisfies \(v_t(B)\ge \max_{A\uplus A'=B\uplus D}\min\{v_t(A),v_t(A')\}\).
Types \(t\) carry complete pair-demand weight vectors \(w_t\); population mass \(\mu_t\) receives integral two-item bundles, while decision variables \(\pi_{t,B}\) specify bundle-cell masses subject to exact per-capita category supplies \(\rho_g\) and support-wise PMMS.
The paper proves polynomial time only in the expanded numbers of agents and goods; a polynomial algorithm in \(\tau\), \(q\), and the encoding length of the masses is not established, and sequential freezing may not compress directly.
fatal: False
The mirror covers the pair-demand PMMS algorithm and the personalized-bivalued EFX/PMMS algorithms; it leaves the non-existence and separation constructions without a principal continuous anchor.
The strongest positive case is a high-multiplicity fair-division mirror in which agents remain individuals with indivisible bundles; only the population and item supplies are represented by masses. The paper contains no NP-hardness anchor, so I would not manufacture one. Its usable anchors are the constructive polynomial-time results.
My lead is Corollary 6.2, proved in this paper:
“For any instance with pair-demand valuations, a PMMS allocation can be computed in polynomial time.”
Consider a large benefits programme with \(N\) recipients and \(q\) recurring categories of indivisible benefits. Each recipient receives two benefits, so the per-capita supply is \(2\). There are only \(\tau\) recipient types, with \(\tau\ll N\); a type records the recipient’s complete value vector \(w_t(g)\) over benefit categories. Its valuation is
\[ v_t(B)=\max_{\substack{S\subseteq B\\|S|\le 2}}\sum_{g\in S}w_t(g). \]
The type distribution is \(\mu=(\mu_t)_{t\in T}\), and the per-capita supply of category \(g\) is \(\rho_g\), with \(\sum_g\rho_g=2\).
The continuous problem is:
Continuum Pair-Demand-PMMS. Given \(T,\mu,G,\rho\), and the vectors \(w_t\), find a mass allocation \(\pi_{t,B}\), where \(B\) is an integral two-item bundle, satisfying
\[ \sum_B\pi_{t,B}=\mu_t \]
for every type \(t\), and
\[ \sum_{t,B}\pi_{t,B}\,n_g(B)=\rho_g \]
for every item category \(g\). Here \(n_g(B)\) is the number of copies of \(g\) in \(B\). The allocation must satisfy PMMS for every pair of bundle-types occurring with positive mass: for all \(t,u,B,D\) with \(\pi_{t,B},\pi_{u,D}>0\),
\[ v_t(B)\ge \max_{A\uplus A'=B\uplus D}\min\{v_t(A),v_t(A')\}. \]
The output is the mass plan \(\pi\), not a fractional bundle given to an individual. Almost every individual still receives an integral pair; only the fraction of type \(t\) receiving each pair is fractional.
This is recognisably the paper’s PMMS problem. It does not replace PMMS by an average utility constraint, and it does not make the items divisible. It is exactly the high-multiplicity regime: an instance with rational \(\mu\) and \(\rho\) expands to a finite instance with \(N\mu_t\) agents of type \(t\) and \(N\rho_g\) item copies. Conversely, any finite allocation aggregates to a feasible mass plan.
The natural expectation is Class A. The paper’s reversed round-robin construction should have a type-level version as a capacitated matching or flow problem. Since bundles have size two, there are only \(O(q^2)\) bundle patterns, so the continuous instance has a finite configuration representation rather than an arbitrary valuation over exponentially many bundles. The real open question is whether the finite algorithm can be compressed to run polynomially in \(\tau,q\), and the encoding length of \(\mu,\rho,w\), rather than in the enormous denominator \(N\). One can also ask for rounding guarantees back to \(N\)-agent elections.
A second, broader mirror is anchored by Corollary 4.3, also proved in this paper:
“For any instance with personalized bivalued valuations, an EFX allocation can be computed in polynomial time. Furthermore, for any instance with factored personalized bivalued valuations, a PMMS allocation can also be computed in polynomial time.”
Here a type \(t\) has parameters \(a_t>b_t\ge0\) and a high-value set \(H_t\) of item categories. Its valuation is
\[ v_t(B)=a_t\,|B\cap H_t|+b_t\,|B\setminus H_t|. \]
A continuous instance consists of a type distribution \(\mu\), per-capita supplies \(\rho_g\) of recurring indivisible goods, and a mass plan \(\pi_{t,B}\) over integral bundles \(B\). The same supply and type-mass equations apply. For every two positive-mass bundle cells \((t,B)\) and \((u,D)\), require
\[ v_t(B)\ge v_t(D\setminus\{g\}) \]
for every item \(g\in D\); this is continuum EFX. In the factored case, also require
\[ v_t(B)\ge \max_{A\uplus A'=B\uplus D}\min\{v_t(A),v_t(A')\}, \]
which is continuum PMMS.
The regime is a large allocation system with many recipients but few complete valuation profiles: for example, a national programme distributing repeated categories of grants, vouchers, or training places, where each demographic type values every category either at a high or low level. The type must include \(a_t,b_t\) and the full high/low pattern, so this is genuine high multiplicity rather than pretending that agents with different prices are identical.
This mirror also plausibly belongs to Class A. The paper’s Match-and-Freeze proof is based on weighted matching and structural properties of high- and low-value items. With repeated types and scaled supplies, those matchings should become capacitated matchings over type masses. For rational data, finite replication gives a direct existence bridge; the substantive continuous-complexity question is whether one can perform the same reasoning directly over masses using flow, configuration LP, or column generation.
I would not use Proposition 3.1 as a principal anchor. It is a valuable boundary question, but its obstruction assigns essentially unique special partitions \(A_i,B_i\) to different agents. The number of valuation types therefore grows with the population, so it is not naturally a high-multiplicity obstruction. Likewise, the three-agent separation theorem is an existence result rather than a computational-complexity result. The mirrors above cover the paper’s named constructive results most faithfully.
The weakest point is the status of pairwise fairness in a nonatomic population. A bare “almost everywhere” interpretation could permit problematic exceptional agents. I would therefore define the solution support-wise: if two bundle patterns occur with positive mass, every corresponding type pair must satisfy EFX or PMMS. That is stronger than merely requiring the condition for almost every randomly sampled pair and preserves the paper’s original universal quantifier. With that convention, the mirror is a genuine continuous-population problem rather than an averaged or weakened fairness notion.
The strongest negative case is weaker than the proponent suggests, but it does not defeat either anchor.
Corollary 6.2 is a genuine computational result: it gives a polynomial-time algorithm for constructing a PMMS allocation. Corollary 4.3 likewise gives polynomial-time construction of EFX allocations, and PMMS allocations under the factored assumption. Thus the decisive “no named computational result” objection is unavailable.
The best attack on the pair-demand mirror is that it changes the resource model substantially. The paper has \(m\) individually identifiable indivisible goods. The proposed model replaces these by endlessly recurring categories with per-capita supply. If \(m\) is kept fixed while the population grows, almost all agents receive nothing and PMMS becomes degenerate; if supply is scaled with population, one is studying a replicated allocation economy rather than simply continuizing the paper’s society. The same objection applies to the bivalued mirror.
That criticism is not ultimately sufficient under ChoCo’s rules, however. Scaling supplies is explicitly an admissible co-modification when population continuization requires it, and the proposed benefits-programme interpretation is credible. A type consisting of the complete vector \(w_t(g)\), or of \((a_t,b_t,H_t)\), is a legitimate high-multiplicity type. For rational masses, expansion into finitely many repeated agents and item copies preserves the allocation and the pairwise EFX/PMMS conditions exactly.
Nor does the support-wise formulation rescue the negative case. Requiring every positive-mass bundle cell to satisfy the paper’s original pairwise condition is a faithful continuum analogue, not an averaging relaxation. With finitely many item categories, bundles remain integral for each individual, while only their population frequencies are fractional.
The proponent does overstate what has been established: the paper’s algorithms are polynomial in the expanded numbers of agents and goods, not necessarily in the compressed encoding \((\tau,q,L)\). In particular, Match-and-Freeze’s sequential freezing is not automatically a capacitated matching algorithm, and a type-level algorithm still needs to be proved. But that is precisely a worthwhile high-multiplicity question, not a defect in the mirror.
So I cannot honestly defeat these anchors universally. The negative case can show that the proposed continuous algorithms are conjectural and that their supply-scaling interpretation deserves scrutiny; it cannot show that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.