| paper | Fair Division with Allocator's Preference |
| authors | Xiao-Lin Bu, Zihao Li, Shengxin Liu, Jia-Xin Song, Biaoshuai Tao |
| venue | WINE 2023 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: For every fixed \(0<\epsilon<1/2\), attaining either factor \(m^{1-\epsilon}\) or \(\tau^{1/2-\epsilon}\) is \(\mathrm{NP}\)-hard, even with binary agent and allocator values and dyadic masses and supplies. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.5
statement extracted from the paper’s text layer
Given finite types \(T\) with rational population masses \(\mu_t\), indivisible item categories \(G\) with rational per-capita supplies \(0\leq\rho_g\leq1\), binary additive agent valuations \(v_t\), and additive allocator valuations \(u_t\), choose masses \(\lambda_{t,S}\) of type-\(t\) agents receiving integral bundles \(S\subseteq G\), subject to \(\sum_S\lambda_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}\lambda_{t,S}\leq\rho_g\). Require that every pair of supported bundles satisfies support-wise EF-\(1\): for \(\lambda_{t,S},\lambda_{t',D}>0\), some \(R\subseteq D\) with \(|R|\leq1\) has \(v_t(S)\geq v_t(D\setminus R)\). Decide whether \(W(\lambda)=\sum_{t,S}\lambda_{t,S}u_t(S)\geq Q\), or maximize \(W(\lambda)\).
A high-multiplicity indivisible-goods allocation with complete types \(t\) carrying \(v_t\) and \(u_t\), population mass \(\mu\), per-capita item supply \(\rho\), configuration variables \(\lambda_{t,S}\), support-wise EF-\(1\), and allocator objective \(W(\lambda)=\sum_{t,S}\lambda_{t,S}u_t(S)\).
Support-wise mass splitting may destroy the Maximum Independent Set gap, so Theorem 5.5 does not establish hardness for the continuous problem without a new argument.
fatal: False
The mirror covers Theorems 5.5 and 5.8: EF-\(1\) allocator-efficiency hardness as an open continuous question and PROP-\(c\) allocator-efficiency as an exact LP problem. It leaves the double-fairness existence results, other approximation theorems, and the divisible-resource appendix aside.
The best positive case is a high-multiplicity version of the paper’s allocator-efficiency problem, with goods still indivisible for each individual.
Take a finite set \(T\) of complete agent types. A type \(t\) specifies both the agent valuation \(v_t\) and the allocator valuation \(u_t\); two agents of the same type are identical for everything the problem uses. The population is a rational distribution \(\mu\) over \(T\). Goods are indivisible categories \(G\), with per-capita supply \(\rho_g\) for each \(g\in G\). An allocation is a mass distribution \(\lambda_{t,S}\), where \(\lambda_{t,S}\) is the mass of type-\(t\) agents receiving the integral bundle \(S\subseteq G\):
\[ \sum_S\lambda_{t,S}=\mu_t,\qquad \sum_{t,S:g\in S}\lambda_{t,S}\le \rho_g. \]
Thus aggregate allocations are fractional, but every unit of population mass receives an integral bundle. If a finite instance has \(N_0\) agents and one creates \(K\) identical copies of every agent and every good, then \(\mu_t=n_t/N_0\) and \(\rho_g=1/N_0\), independently of \(K\). This is exactly the high-multiplicity regime: \(K N_0\) agents, but only \(|T|\) distinct types.
The allocator’s objective is the normalized welfare
\[ W(\lambda)=\sum_{t,S}\lambda_{t,S}u_t(S). \]
For fairness, I would use the support-wise interpretation, preserving the paper’s individual quantifiers. A plan is support-wise EF-\(1\) if whenever \(\lambda_{t,S}>0\) and \(\lambda_{t',D}>0\),
\[ \exists R\subseteq D,\quad |R|\le 1,\quad v_t(S)\ge v_t(D\setminus R). \]
Similarly, it is support-wise PROP-\(c\) if every supported bundle \(S\) satisfies
\[ \exists R\subseteq G\setminus S,\quad |R|\le c,\quad v_t(S\cup R)\ge \sum_{g\in G}\rho_gv_t(g). \]
The right-hand side is the per-capita value of the entire resource supply, which is the correct normalization obtained by cloning both agents and goods.
My lead anchor is Theorem 5.5, proved in this paper. It states that, for every \(\epsilon>0\), maximizing the allocator’s social welfare subject to agents’ EF-\(c\) constraint is NP-hard to approximate within factor \(m^{1-\epsilon}\) or \(n^{1/2-\epsilon}\), even when both the agents’ and allocator’s additive utilities are binary and \(c=1\). The proof is by reduction from Maximum Independent Set.
The corresponding continuous problem is:
Continuous Binary Allocator-Efficiency under EF-\(1\). Given \(G,T,\mu,\rho\), binary additive valuations \(v_t,u_t\), and a rational threshold \(Q\), decide whether there is a feasible mass allocation \(\lambda\) that is support-wise EF-\(1\) and satisfies \(W(\lambda)\ge Q\); or, in optimization form, maximize \(W(\lambda)\).
This is recognisably the authors’ problem: the agents’ fairness constraint is unchanged, the allocator still evaluates who receives which goods, and only the population representation has changed. The paper’s graph reduction also suggests why the problem should not become automatically easy. Its combinatorics live in the goods and their valuation graph, not merely in the number of named agents. One can repeat every edge-agent type \(K\) times, making the population arbitrarily large while retaining the same finite type description.
I expect this problem to be hard for continuum-specific reasons, or to retain hardness in unrestricted type regimes. I would not claim that Theorem 5.5 transfers verbatim: mass splitting can let agents of one type receive different integral bundles, potentially weakening the original independent-set gap. That is precisely the interesting continuous question. Does support-wise EF-\(1\) still force an independent-set-like structure, or does population splitting reduce the problem to a tractable configuration LP? The answer should depend on \(m\), \(|T|\), and the supply encoding, rather than on the expanded population size.
A second, cleaner anchor is Theorem 5.8, also proved here. It states that when the agents’ additive valuations are binary, maximizing the allocator’s efficiency subject to PROP-\(c\) can be solved exactly in polynomial time by linear programming, even when the allocator’s valuations are arbitrary.
Its continuous counterpart is:
Continuous Binary Allocator-Efficiency under PROP-\(c\). Given \(G,T,\mu,\rho\), binary agent valuations \(v_t\), arbitrary additive allocator valuations \(u_t\), and integer \(c\), find a feasible mass allocation maximizing \(W(\lambda)\) subject to support-wise PROP-\(c\).
For a type \(t\), let \(V_t=\{g:v_t(g)=1\}\) and
\[ q_t=\max\left\{0,\left\lceil\sum_{g\in G}\rho_gv_t(g)\right\rceil-c\right\}. \]
Because valuations are binary, every type-\(t\) agent must receive at least \(q_t\) valued goods. Let \(x_{t,g}\) be the mass of type \(t\) receiving good \(g\). The continuous problem reduces to
\[ \max \sum_{t,g}u_t(g)x_{t,g} \]
subject to
\[ 0\le x_{t,g}\le \mu_t,\qquad \sum_t x_{t,g}\le \rho_g,\qquad \sum_{g\in V_t}x_{t,g}\ge \mu_tq_t. \]
This is a polynomial-size transportation-style LP. Its solution can be decomposed into integral bundles for each type while preserving the required valued-good count, so the LP is not silently replacing indivisible individual bundles by divisible ones. I therefore expect this mirror to be Class A: exact polynomial optimization in \(|T|\), \(|G|\), and the input bit-length, independent of the clone factor \(K\).
The scope is deliberately narrow: these two allocator-efficiency results, not the paper’s double-fairness existence theorems or its divisible-goods appendix. The weakest point is the lead hardness mirror: the paper’s reduction uses individually identified agents, and continuous mass splitting may destroy its gap. But that weakness does not undermine the mirror itself; it identifies the central ChoCo question for this paper—whether EF-\(1\) configuration structure remains computationally difficult once the society, rather than the goods or outcomes, becomes continuous.
The strongest negative case is against the proponent’s reading of Theorem 5.5. In the Maximum Independent Set reduction, every edge-agent has a different valuation vector, so after making the type description complete, the “high-multiplicity” population still contains one distinct type per edge. Repeating each agent \(K\) times is only cloning the instance. If goods are not also cloned, per-agent proportional shares collapse; if they are cloned, the model has become a repeated-resource-category problem.
More importantly, the continuous allocation may split one type across several integral bundles. The reduction’s independent-set argument concerns one named super-agent receiving a particular bundle, and does not automatically survive such splitting. The support-wise EF-\(1\) condition prevents some bad supports, but the proponent has not shown that it restores the original gap. One could force every type to use one bundle, but that is an additional discrete restriction rather than the natural mass-allocation model. Thus Theorem 5.5 supplies no established hardness transfer.
That objection does not, however, defeat the underlying continuous question: whether support-wise EF-\(1\) over integral bundles yields a configuration problem whose difficulty survives aggregation. It merely defeats the claimed reduction.
The negative case fails completely against Theorem 5.8. For binary \(v_t\), let
\[ q_t=\max\left\{0,\left\lceil\sum_g \rho_g v_t(g)\right\rceil-c\right\}. \]
A type-\(t\) agent satisfies PROP-\(c\) exactly when she receives at least \(q_t\) valued goods. Hence the aggregate problem is the transportation LP
\[ \max \sum_{t,g}u_t(g)x_{t,g} \]
subject to
\[ 0\le x_{t,g}\le\mu_t,\qquad \sum_t x_{t,g}\le\rho_g,\qquad \sum_{g:v_t(g)=1}x_{t,g}\ge \mu_tq_t. \]
This is not silently divisible-goods allocation: the relevant marginal polytope is the convex hull of integral bundles containing at least \(q_t\) valued goods, so the solution decomposes into integral bundles for each unit of mass. It is a genuine Class A high-multiplicity result.
Calling this LP “too easy,” or confusing it with the paper’s divisible-resource appendix, would be invalid objections. An exact polynomial answer is still a worthwhile mirror, and continuity of the population is distinct from continuity of the goods.
So the honest conclusion is that the universal negative case is weak. Theorem 5.5’s particular hardness argument does not establish a transfer, but Theorem 5.8 gives a clean, natural continuous-population mirror. I cannot responsibly defeat every anchor; this paper should remain green.
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.