| paper | d4-conf-aaai-2014-0190 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 3 and Theorem 4 are genuine computational results, but each instance has a fixed pair of claimants and one set of goods. Treating settlement cases as population types only averages independent instances, while a society of claimants would require a different envy-free allocation model. The goods are outcomes, so increasing their number does not supply the population continuity this programme studies.
fails bit b-none — no population with multiplicity to relax
The proposed batch formulation covers Theorems 3 and 4, while Theorems 1 and 2 give welfare-ratio bounds rather than computational anchors; no result has a surviving population mirror.
The strongest honest mirror I see is a population of two-party asset-division cases. Imagine a large mediation service handling \(N\) independent settlements over the same catalog of \(m\) goods. In a regime with standardized valuation assessments, many cases have exactly the same pair of valuation functions. Let \(t\) denote a complete case type, including both claimants’ normalized additive valuations \(v_A^t,v_B^t\), and let \(\mu_t\) be the fraction of cases of that type. Here \(N\) can be much larger than the support size \(\tau\). Each case has its own copy of the goods; its claimants receive an envy-free allocation with selling under the paper’s rules.
This is a population of cases rather than a population of individual claimants, which makes the mirror somewhat indirect. But the local decision remains the paper’s exact decision: goods are allocated integrally or sold, and each case must be envy-free. Mass is the share of cases receiving a given allocation, not a fractional share of an item.
Call the resulting problem Population-MAX-EFS(\(c\)). Its input is the rational distribution \(\mu\) over \(\tau\) case types, the goods catalog, the selling fraction \(c\), and a threshold \(K\). For type \(t\), let \(\mathcal E_t\) be the paper’s envy-free allocations with selling. An allocation \(X\in\mathcal E_t\) partitions the goods into \(X_A,X_B\), and a sold set \(S_X\); its cash shares satisfy
\[
C_A+C_B=c\sum_{j\in S_X}\min\{v_A^t(j),v_B^t(j)\}.
\]
It must satisfy both claimants’ envy constraints, and has welfare
\[
\operatorname{SW}_t(X)=v_A^t(X_A)+C_A+v_B^t(X_B)+C_B.
\]
A solution gives rational masses \(x_{t,X}\geq 0\), with \(\sum_{X\in\mathcal E_t}x_{t,X}=\mu_t\), and the corresponding per-case allocations. The question is whether
\[
\sum_t\sum_{X\in\mathcal E_t}x_{t,X}\operatorname{SW}_t(X)\geq K.
\]
Thus every case gets a valid local allocation, while the objective measures average welfare across the continuous population.
My lead anchor is Theorem 3, proved in this paper: for every \(c\in(0,1]\), MAX-EFS(\(c\)) is NP-complete. The paper defines MAX-EFS(\(c\)) as taking the goods, the two valuation functions, and a threshold \(k\), and asking whether there is an envy-free allocation with selling whose welfare is at least \(k\). Population-MAX-EFS(\(c\)) asks the same welfare-threshold question over a distribution of such cases. Its hardness follows already when \(\tau=1\) and \(\mu_1=1\), which recovers the paper’s problem exactly. A certificate can specify one allocation per type: mixing allocations cannot improve on choosing a highest-welfare feasible allocation for each type. I expect hardness transfers. The hard combinatorics concern assigning the goods, so taking the case population to a continuum does not remove them.
A second, closely related anchor is Theorem 4, also proved here: MAX-EFS(1) admits an FPTAS. For every \(\epsilon>0\), it returns an envy-free allocation with selling \(X\), possibly including cash, satisfying \(\operatorname{SW}(X)\geq(1-\epsilon)\operatorname{OPT}_{\mathrm{EFS}}\), in time polynomial in the problem parameters and \(1/\epsilon\). The continuous question is whether Population-MAX-EFS(1) admits an FPTAS returning a type-to-allocation policy with exact envy-freeness within each case and average welfare at least \((1-\epsilon)\) times the population optimum. I expect tractability here: run the paper’s FPTAS on each supported type and assign that type’s mass to its returned allocation. The weighted guarantee follows by summing the per-type guarantees, and the running time is polynomial in \(\tau\) and the total input size. This is a modest lift of the theorem, but it is a precise one.
The mirror covers these two computational results only. Theorem 1 and Theorem 2 give welfare-ratio bounds; they are not computational-complexity anchors for this case. The paper’s divisible cash is also not the continuity I am relying on: the continuous object here is the distribution of cases.
Further questions include whether an FPTAS extends to \(c<1\), and whether useful parameterized algorithms exist in \(m\) or \(\tau\). Theorem 3’s exact hardness does not settle approximation. One would also want to establish when exact repeated valuation profiles are a realistic regime; standardized valuation menus make the premise more plausible than unconstrained, arbitrary profiles.
The weakest point is that this construction aggregates independent two-claimant problems. A referee could see it as batching instances, rather than as a new social-choice problem whose population changes the computation. The case for accepting it is that the type is complete, the regime can have \(N\gg\tau\), and neither the item integrality nor the paper’s envy-free requirement is relaxed. Its honest conclusion is narrow: it gives a continuous high-multiplicity wrapper around the paper’s computational problem, while predicting that the NP-hardness survives.
The objection is not that the paper lacks computational results: Theorems 3 and 4 are clear anchors. It is that their subject has no population of decision-makers to continuize. Each input has two fixed claimants and one set of goods. The goods are the objects being allocated; increasing their number would continuize the outcome side, which is outside ChoCo’s scope.
For Theorem 3, the proposed population of settlement cases preserves the paper’s problem by running it independently many times. If \(\mathcal E_t\) is the set of feasible allocations for case type \(t\), then the population optimum is
\[ \sum_t \mu_t \max_{X\in\mathcal E_t}\operatorname{SW}_t(X). \]
There are no cross-type constraints. Mixing allocations within a type cannot improve the linear welfare objective, so the population problem reduces to solving one instance for each supported type. A mediation service handling many standardized cases could make this batching useful in practice, but its types are cases, not agents in one society. At support size one, the proposed mirror is exactly the original problem; at larger support, it is a collection of independent instances. The hardness transfer is not itself a reason to reject it; the issue is that the continuous population contributes no structure to the decision being studied.
Theorem 4 lifts just as directly: run the paper’s FPTAS on each supported case type and sum the weighted guarantees. That is a valid guarantee for a batch of cases, but it does not produce a population version of the allocation problem. Introducing a shared budget or other cross-case constraint could create a coupled optimization problem, but then the resulting question would no longer be the paper’s MAX-EFS problem.
The strongest alternative is a common goods economy with many claimants, described by a distribution over valuation types. One could scale per-capita supplies and keep each person’s bundle integral, while imposing envy-freeness across types. That is a plausible research direction. But it replaces the paper’s two-person envy constraints with all-to-all envy, and requires extending the sale and cash rules to a many-claimant setting. It may be worthwhile as a new fair-division problem; it does not mirror Theorems 3 or 4 as stated.
So the negative case is strong against both proposed anchors: the case-population construction is batch optimization, while the natural agent-population construction changes the underlying problem. The universal claim is less certain: a many-claimant extension could be valuable if the authors would recognize it as their problem. I would treat that as the sole serious opening, but not as a continuous mirror established by this paper’s results.
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.