| paper | To Give or Not to Give: Fair Division for Single Minded Valuations |
| authors | Simina Brânzei, Yuezhou Lv, R. Mehta |
| venue | IJCAI 2016 |
| filed under | fairalloc · markets |
| 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: \(\mathrm{NP\text{-}hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given rational divisible-good supplies \(q_j\), finitely many demand types \(T\) with masses \(\mu_t\), demand vectors \(v_t\), and unit budgets, choose common prices \(p\) and a probability measure \(\lambda_t\) over bundles for each type such that every supported bundle is utility-maximizing under the explicitly fixed CEEI convention, each supported bundle exhausts its budget, \(\sum_t \mu_t\int z_j\,d\lambda_t(z)=q_j\) for every good, and the mass-weighted welfare \(\sum_t\mu_t\int u_t(z)\,d\lambda_t(z)\) is maximized; decide whether it reaches a given threshold.
A mass-one CEEI market with finite single-minded demand types: \(\mu_t\) is agent mass, \(q_j\) is per-capita supply, \(p\) is the common price vector, and \(\lambda_t\) distributes bundles among type-\(t\) agents.
The literal formulation with one bundle \(z_t\) per type can misrepresent welfare because unhappy agents of the same type may receive heterogeneous bundles under discontinuous utility.
fatal: False
The mirrors cover the divisible-goods welfare results in Theorems 2 and 3, including hardness and fixed-\(\tau\) tractability; they leave the existence results, cake-cutting and discrete-goods variants, and fairness comparisons untreated.
The strongest positive case is a high-multiplicity version of the paper’s divisible-goods problem. My lead anchor is Theorem 2.
The natural regime is a large population of users submitting recurring computational jobs. A type is a complete demand vector \(v_t\), together with the unit budget and single-minded utility rule. Thus agents of type \(t\) are indistinguishable: they all require the same quantities of CPU, memory, bandwidth, and so on. The population is represented by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\), and typically \(N\gg\tau\), where \(N\) is the actual number of users and \(\tau\) is the number of demand templates. Resource supplies are expressed per capita: a finite realization with \(N\mu_t\) agents has \(Nq_j\) units of good \(j\).
My lead problem is:
Continuous Welfare-Maximizing CEEI for Single-Minded Demand Types. An instance consists of divisible goods \(j\in[m]\), rational per-capita supplies \(q_j\), a finite type set \(T\), rational masses \(\mu_t\), and demand vectors \(v_t\). Every type-\(t\) agent has utility
\[ u_t(z)= \begin{cases} 1 & \text{if } z_j\ge v_{tj}\text{ for every }j,\\ 0 & \text{otherwise.} \end{cases} \]
A solution consists of nonnegative prices \(p\) and an allocation \(z_t\) for each type, satisfying
\[ \sum_{t\in T}\mu_t z_{tj}=q_j \]
for every good \(j\), and
\[ p\cdot z_t=1 \]
for every type \(t\). Each \(z_t\) must maximize \(u_t(z)\) among bundles with \(p\cdot z\le1\). The objective is to maximize
\[ \sum_{t\in T}\mu_tu_t(z_t). \]
Equivalently, a type is happy precisely when its demand is affordable, \(p\cdot v_t\le1\), and then all of its mass must receive its demand. If \(p\cdot v_t>1\), that type cannot be happy.
The anchor is Theorem 2, proved in this paper: “Computing a CEEI solution that maximizes social welfare for single minded valuations with divisible goods is NP-hard.” The proof reduces SET PACKING. For a collection \(C_1,\ldots,C_n\), it creates one agent whose demand is the set \(C_i\) together with a private good. At least \(K\) agents can be made happy exactly when \(K\) of the sets are mutually disjoint.
That reduction has a credible high-multiplicity form. Replace each original agent by \(r\) identical agents of the same type, set \(\mu_i=1/n\), and scale every good supply by \(r\). Equivalently, use per-capita supply \(q_j=1/n\). A type that is made happy consumes the entire mass \(1/n\) of every good in its demand, so two selected types cannot overlap on a shared element. The private goods preserve the original pricing gadget. The number of named agents can therefore be made arbitrarily larger than the number of types without removing the set-packing obstruction.
I would expect this mirror to be Class B: hardness transfers because the combinatorics lives in the incidence pattern between demand types and goods, not in the identities of individual agents. The main follow-up questions are whether the problem is fixed-parameter tractable in \(\tau\), what approximation guarantees are possible, and whether allowing type-specific budgets or partial type participation creates a genuinely continuum-specific variant.
The paper’s terminology needs one caveat: Theorem 2 is stated for CEEI, but its proof repeatedly refers to CAEI. A formal continuation should resolve that discrepancy rather than silently treating the two concepts as identical.
As supporting evidence, I would also anchor Theorem 3, proved here: “Given a fair division problem with single minded agents and divisible goods, a welfare maximizing CAEI solution can be found in polynomial time for a constant number of agent types.” The paper’s algorithm enumerates the subsets \(S\subseteq T\) of types that are happy and solves a linear program for each subset.
Its continuous counterpart is:
Continuous Welfare-Maximizing CAEI with Fixed Demand Types. The instance is the same as above, except that the allocation must satisfy
\[ p\cdot z_t\le1 \]
rather than equality. All goods are allocated, every \(z_t\) is utility-maximizing at prices \(p\), and the objective remains \(\sum_t\mu_tu_t(z_t)\). The question is to compute a welfare-maximizing CAEI.
For fixed \(\tau\), this should be in Class A. The paper’s enumeration becomes an enumeration of happy type subsets, with mass-weighted resource and budget constraints; the resulting running time is \(2^\tau\operatorname{poly}(m,\tau,L)\), hence polynomial for constant \(\tau\). This is particularly convincing as a mirror because the original proof already aggregates agents by identical type. The continuum is not replacing the paper’s divisible goods with a fractional outcome: the goods were already divisible. It makes the population itself a distribution over repeated demand templates.
The scope is deliberately narrow: these two mirrors cover the paper’s welfare-maximization results for divisible goods. They do not claim to continuize the paper’s cake-cutting results, discrete-goods existence theorem, or envy-freeness comparisons.
The weakest point is that Theorem 2’s reduction has \(\tau=n\), so it does not establish hardness when the number of types is fixed. But that is not fatal: the proposed mirror still describes a legitimate high-multiplicity regime with many repeated users, and Theorem 3 covers the fixed-type tractable boundary. A referee should recognise both questions as faithful continuous-population versions of the paper’s underlying CAEI/CEEI welfare problems.
The strongest negative case is that the proponent’s two anchors add very little beyond renaming multiplicities.
Theorem 2’s construction does not genuinely use a population continuum. Replacing each agent by \(r\) identical copies and scaling every supply by \(r\) is an exact blow-up: after dividing by \(r\), one recovers the original instance. The private good attached to each set also means that every computationally relevant object remains a distinct type. Thus the proposed hardness mirror is really weighted Set Packing over explicitly distinct demand types, not a phenomenon created by a continuous society. The CEEI/CAEI slippage in the paper makes the stated anchor additionally unstable, since the theorem says CEEI while the proof repeatedly establishes CAEI.
Theorem 3 is weaker as a research anchor. Its proof already aggregates agents by type and enumerates the happy type subsets \(S\subseteq T\). Replacing the integer number of agents of type \(t\) by a rational mass \(\mu_t\) merely replaces repeated sums by weighted sums in the same LP. For the CAEI version, this is essentially an immediate compressed implementation of the paper’s own algorithm, rather than a new continuous-population problem.
There is also a modelling defect in the proposed formulation. A single vector \(z_t\) cannot generally represent the allocation of a continuum of identical agents: unhappy agents may receive different worthless bundles, and \(u_t\) evaluated on their average bundle need not equal their average utility because single-minded utility is discontinuous. A faithful model would need a distribution of bundles for each type. But once that correction is made, common prices make every type all-or-nothing: if \(p\cdot v_t\le 1\), every type-\(t\) agent must be happy; if \(p\cdot v_t>1\), none can be. The population continuum therefore disappears from the welfare decision except as a weight in \(\sum_{t\in S}\mu_t\).
That is the best negative case: the proposed mirrors are either exact replications of finite instances, or direct weighted restatements of an algorithm already organized by types; the literal type-level allocation is not even faithful without an additional measure-valued allocation model.
It is not, however, enough to support the requested universal verdict. A corrected high-multiplicity version with per-capita supplies and distributions over individual bundles is perfectly coherent, and the Set Packing reduction survives it. The fact that its hardness is carried by demand-type incidence rather than by the replication factor is not a valid objection under the programme’s rules. Likewise, the weighted fixed-type CAEI problem is a sensible bit-complexity question even if the paper’s LP nearly answers it already. The honest conclusion is therefore that the negative case can downgrade the proponent’s novelty and formulation, but cannot defeat the existence of a worthwhile continuous 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.