| paper | On Pareto-Optimal and Fair Allocations with Personalized Bi-Valued Utilities |
| authors | Jiarong Jin, Biaoshuai Tao |
| venue | WINE 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm P\), with bit complexity \((L+\tau m+sm^2)^{O(1)}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite good classes \(G\), agent types \(T\), rational masses \(\mu_t\), ratios \(r_t>1\), high-value sets \(H_t\subseteq G\), per-capita supplies \(q_g\), and an explicit current allocation \(\lambda_{t,B}\) over integral bundles \(B\in\{0,1\}^{G}\), decide whether there exists a reassignment flow \(y_{t,B,B'}\) preserving source masses and every \(q_g\), with \(u_t(B')\ge u_t(B)\) for every used transition and \(\sum y_{t,B,B'}(u_t(B')-u_t(B))>0\), where \(u_t(B)=r_t|B\cap H_t|+|B\setminus H_t|\).
A high-multiplicity fair-division model with finitely many valuation types, mass \(\mu\), replicated indivisible good classes with per-capita supplies \(q\), integral bundles per agent, current-allocation masses \(\lambda\), and reassignment flows maximizing aggregate utility gain.
The mirror covers the Pareto-optimality verification hardness of Theorem 2. It leaves Theorem 1, Corollary 1, Theorem 3, and the open EFX-plus-Pareto-optimality problem untreated.
The strongest mirror is anchored in Theorem 2, and I would make it the lead.
Theorem 2, proved in this paper, states: given an allocation \(X\) under normalized personalized bi-valued utilities \(\{(r_i,1)\}_{i\in[n]}\), deciding whether \(X\) is Pareto-optimal is coNP-complete, even when every ratio satisfies \(r_i\in\{r_a,r_b\}\). The proof reduces from the \(k\)-Regular Bipartite Subgraph Problem, for fixed \(k\ge3\), using \(r_a=1+1/k\) and \(r_b=1+(1+\epsilon)/k\), with sufficiently small \(\epsilon>0\). Thus the hardness is not caused by three or more values per agent: two personalized values suffice.
My continuous problem would be Continuous Personalized-Bi-Valued Pareto Verification, \(\mathrm{CPO\text{-}PBV}_\infty\).
There are finitely many indivisible good classes \(G\) and finitely many agent types \(T\). A type \(t\) specifies its ratio \(r_t>1\) and the subset \(H_t\subseteq G\) of goods it values highly. Its value for an integral bundle \(B\in\{0,1\}^{G}\) is \(u_t(B)=r_t|B\cap H_t|+|B\setminus H_t|\). The population is a distribution \(\mu=(\mu_t)_{t\in T}\), and each good class \(g\) has per-capita supply \(q_g\). Thus \(q_g\) is the fraction of the population that can receive one copy of \(g\). Goods remain indivisible: an individual receives an integral bundle \(B\), never a fraction of a good.
An allocation is represented by masses \(\lambda_{t,B}\), where \(\lambda_{t,B}\) is the mass of type-\(t\) agents receiving bundle \(B\). It satisfies \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B}\lambda_{t,B}B_g=q_g\). The input includes such a current allocation, with rational masses and explicit support.
The question is whether there is a Pareto improvement. The decision variable is a reassignment flow \(y_{t,B,B'}\): the mass currently in state \((t,B)\) moved to the integral bundle \(B'\). It must preserve each source mass and every good supply. It may use only \(B'\) with \(u_t(B')\ge u_t(B)\), and must produce strictly positive total utility gain, \(\sum y_{t,B,B'}(u_t(B')-u_t(B))>0\). Equivalently, maximize that expression and ask whether the optimum is positive. A positive flow is a certificate of non-Pareto-optimality; an optimum of zero certifies Pareto-optimality.
This is a natural high-multiplicity version of the paper’s problem. The scenario could be a large course-allocation or public-benefits system: hundreds of thousands of students or households, a few dozen recurring preference/urgency classes, and many copies of standardized course seats, appointment slots, or benefit units. The type records everything relevant to utility, including the personalized ratio and high-value classes. The regime is \(N\gg |T|\), with repeated agents of each type. Per-capita good supplies are necessary: retaining only finitely many one-off goods while making the population continuous would leave almost everyone empty and would not represent the paper’s allocation problem.
I expect \(\mathrm{CPO\text{-}PBV}_\infty\) to be tractable, probably Class A. The aggregate improvement problem is a configuration LP with exponentially many possible integral target bundles. Its pricing problem has the form of choosing \(B'\) with \(u_t(B')\ge u_t(B)\) while optimizing a linear expression in item prices. Because each type has only two item values, one can enumerate the number of selected high-valued and low-valued goods and choose the best goods within each class. That gives a polynomial pricing oracle, after which the ellipsoid or column-generation machinery should solve the LP in time polynomial in \(|G|\), \(|T|\), the allocation support, and the encoding length.
This also explains why Theorem 2 need not transfer. Its reduction forces an integral choice of a regular bipartite subgraph. In the continuum, a positive mass of agents can participate fractionally, so the regular-subgraph condition becomes a capacitated fractional-flow condition. The individuals still receive integral bundles, but the population-level participation is divisible—the precise relaxation ChoCo is meant to study. The paper’s discrete coNP-hardness may therefore dissolve into a polynomial continuous optimization problem.
The finite-to-continuous bridge is exact for rational data: clearing denominators expands \(\mu_t\) and \(q_g\) into a finite replicated instance, while repeated identical agents and goods compress back to the continuous representation. The mirror is therefore not an unrelated fractional-allocation problem; it is the high-multiplicity form of the same Pareto-improvement question.
The main further questions are whether the proposed pricing argument yields a fully formal polynomial-time theorem, how to round a continuous improvement back to a finite population with bounded utility loss, and where tractability fails if utilities have three values, agents have budgets, or goods cannot be replicated. The paper’s EFX result and its open EFX-plus-Pareto-optimality problem are outside this mirror’s scope.
The weakest point is that the tractability claim is a proposed result, not something proved by Jin and Tao. Moreover, the continuous model deliberately relaxes the integral choice of which named agents participate—the very feature exploited by their reduction. An opponent can therefore argue that the mirror has removed the paper’s hard core. My answer is that this is exactly the population continuization being tested, while the indivisibility of each individual bundle and the personalized bi-valued utility structure remain intact.
The best case against rests on the inventory, not on the agents. Theorem 2’s reduction couples named agents and named goods into an incidence graph: each edge-good is large for precisely its endpoints and initially belongs to one endpoint. With those \(m\) indivisible goods held fixed while the population becomes atomless, the limit degenerates: every good is assigned to a measure-zero set, and Pareto verification becomes an almost-everywhere statement that ignores the finite allocation.
The proponent avoids this only by replacing each good with a positive per-capita supply of identical copies. That is a substantial change. The graph-coded object in Theorem 2 becomes a replicated resource-class transport problem, and the current bundle must be part of the state—so the relevant “types” are really \((\text{valuation type},\text{bundle})\), not merely repeated agents. One could therefore argue that the proposed problem is not the paper’s fair-division problem continued, but a new anonymous market model whose central discrete obstruction has been removed by construction.
That objection is ultimately insufficient under ChoCo’s rules. Per-capita supplies are precisely the sort of co-modification the programme permits when population continuization otherwise degenerates, and a plausible scenario exists: a large population of repeated household or student types receiving integral bundles of standardized goods. In that model, the aggregate allocation is genuinely a distribution over integral bundles, not fractional goods.
Indeed, the proponent’s LP idea appears coherent. For a source state \((t,B)\), pricing a target bundle amounts to optimizing a linear item score subject to
\[ r_t |B'\cap H_t|+|B'\setminus H_t| \ge r_t |B\cap H_t|+|B\setminus H_t|. \]
Enumerating the numbers of selected high- and low-valued goods gives a polynomial pricing oracle. The discrete regular-subgraph choice can become fractional participation across a nonatomic population, exactly as a high-multiplicity relaxation is supposed to do.
Thus the negative case is weak. The literal fixed-inventory limit degenerates, and the meaningful version requires replicated goods and bundle-state types, but both repairs are natural and permitted. Saying that the repair destroys the paper’s hardness is only an answer-based objection, not a reason the mirror is unworthwhile. Theorem 2 therefore survives as a credible continuous-population anchor, and I cannot honestly support the universal claim that this paper has no worthwhile mirror.
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.