| paper | d4-conf-aaai-2018-0770 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 12 proves a separation between fairness notions, not a computational result under the stated criterion. Mass-\(G\)-EEF feasibility is a precise possible follow-up, but it adds a search task that this paper does not establish as a named result; the unnumbered remark about checking \(G\)-EEF cannot serve as the anchor.
fails bit a — no named computational result to mirror
Theorem 12 is the sole proposed anchor. Its fairness separation and the paper's other fairness hierarchies are not computational results; the proposed feasibility problem goes beyond them.
There is a plausible continuous population model here, but the paper has no named computational result to anchor it. The closest result is Theorem 12, proved in this paper: for \(n\ge3\) and an \(n\)-node social graph \(G\) with a node of out-degree at most \(n-3\), there is a resource-allocation instance with a \(G\)-PEF allocation but no \(G\)-EEF allocation. That is a separation between fairness notions, not a complexity classification. The paper also says, outside a numbered result, that checking whether a given allocation is \(G\)-EEF is computationally hard; that remark does not classify the allocation-feasibility problem.
A reasonable follow-up would be Mass-\(G\)-EEF Feasibility. Imagine a large organization assigning recurring indivisible benefits or work items to employees. There are many employees but relatively few complete types: each type has the same additive valuation and the same pattern of who can observe whose allocation. Let \(T\) be the finite set of types, \(\mu_t\) their rational population masses, and \(K_{t,r}\) indicate whether members of type \(t\) observe members of type \(r\). For each item \(g\), give the instance a rational per-capita supply \(q_g\). An allocation is a table \(x_{t,S}\), for \(S\subseteq M\), where \(x_{t,S}\) is the mass of type \(t\) receiving the integral bundle \(S\). It must satisfy
\[
\sum_{S\subseteq M}x_{t,S}=\mu_t,\qquad
\sum_{t,S:g\in S}x_{t,S}=q_g.
\]
The question is whether such an allocation exists that is \(G\)-EEF; a solution is the table \(x\), with witnesses for the required reallocations.
Precisely, for every \(t,S\) with \(x_{t,S}>0\), the value \(v_t(S)\) must be at least the value of every bundle allocated to a type \(r\) with \(K_{t,r}=1\). The remaining item supply must also be reallocatable among non-neighbor types, preserving each type’s mass, so that every resulting bundle has value at most \(v_t(S)\). This keeps each individual’s bundle integral while allowing a fraction of a type to receive each bundle. Scaling rational masses gives a high-multiplicity interpretation. The block-structured social graph is a substantive modelling choice: it fits cohorts with shared access or observation patterns, but it does not cover arbitrary individual social networks.
This candidate covers only the \(G\)-EEF/\(G\)-PEF comparison around Theorem 12, not the paper’s whole hierarchy or its general framework. It has a credible chance of being recognized by the authors as their allocation-fairness problem with a continuous population. For the associated search problem, I would provisionally expect hardness to persist when the combinatorics come from choosing bundles of items: aggregating agents does not remove those choices. That is an inference, not a result established by this paper. The central follow-up is whether Mass-\(G\)-EEF Feasibility has an efficient algorithm in \(m,\tau,L\), or whether hardness persists even with few types; one could also ask whether a mass-level \(G\)-PEF allocation can exist when no mass-level \(G\)-EEF allocation does.
The weak point is the social-graph restriction, followed closely by the missing computational anchor. Theorem 12 motivates the fairness phenomenon, but it does not establish a complexity claim whose continuous fate this paper lets us test.
I would reject Theorem 12 as a computational anchor. It proves a strict separation between \(G\)-PEF and \(G\)-EEF: some allocation satisfies the former, while no allocation satisfies the latter. It gives no algorithmic problem, complexity bound, or optimization task to continuize. A faithful mass analogue would ask whether that separation persists for a continuous population. That is an axiomatic question, outside ChoCo’s stated computational scope.
The proposed Mass-\(G\)-EEF feasibility problem is the strongest repair. With per-capita supplies, integral bundles, and a block-structured observation graph, it can be made mathematically coherent. But it adds a search task that Theorem 12 does not pose. Mirroring the theorem leads to a question about whether the fairness hierarchy separates; asking for an algorithm to find a fair allocation leads to a new computational project. The paper’s informal remark that checking \(G\)-EEF is hard offers a closer algorithmic foothold, but it is not the named result the proponent anchored on.
There is a real modelling cost, too. In the paper, an agent knows the bundles of particular neighbors. Grouping agents by valuation and a type-level observation pattern preserves that information only for special graphs, such as complete blocks. For general social graphs, exact neighborhoods can distinguish individuals, leaving no small set of types. The block model may fit some institutional settings, but it narrows the paper’s central social-network model. That is a reason to doubt the mirror’s reach, not proof that no credible regime exists.
So the negative case is strong only if “mirror” means a continuous computational counterpart of a problem the paper actually studies computationally: Theorem 12 supplies no such problem. I cannot honestly claim the stronger universal conclusion. A reader who accepts a new algorithmic allocation problem inspired by the paper may find the block-model version worth studying; that possibility is the weakest point in the case against.
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.