| paper | d4-conf-ecai-2024-0284 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even with \(\tau=1\), a connected block graph, and strictly positive supplies. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given finitely many block types \(b\), each a graph \(H_b=(P_b,E_b)\) with strict rankings over \(K\) item classes at its positions, rational block masses \(\lambda_b\) with \(\sum_b |P_b|\lambda_b=1\), and rational per-capita item supplies \(s_k\) with \(\sum_k s_k=1\), decide whether there are nonnegative rational masses \(z_{b,a}\) such that \(\sum_{a\in\mathcal A_b} z_{b,a}=\lambda_b\) for each \(b\), and \(\sum_b\sum_{a\in\mathcal A_b} z_{b,a}|\{p\in P_b:a(p)=k\}|=s_k\) for each \(k\). Here \(\mathcal A_b\) contains the assignments giving each position one indivisible item and satisfying local envy-freeness on every edge of \(H_b\); item-class copies are interchangeable, and distinct blocks have no edges between them.
A distribution over repeated finite social-network motifs, with mass on each motif and its locally envy-free integral assignment patterns; the assignment-pattern masses must meet the per-capita supplies of interchangeable item classes.
The mirror covers LEF allocation existence from Proposition 1 in repeated-motif societies; it does not cover the activation characterization, MUS-selection bounds, or the paper's explanation metrics and experiments.
My strongest honest case is a narrow mirror of the paper’s feasibility backbone: Motif-LEF Mass Feasibility. The paper’s numbered results do not give a conventional complexity classification such as NP-hardness or membership in P. The relevant named result is Proposition 1, proved in this paper: a locally envy-free allocation exists if and only if the formula \(\phi=\phi_{\mathrm{alloc}}\land\phi_{\mathrm{lef}}\) is satisfiable. Here, \(\phi_{\mathrm{alloc}}\) enforces a one-to-one assignment of items to agents, and \(\phi_{\mathrm{lef}}\) enforces that each agent prefers their own item to every neighbor’s. In particular, its clauses encode that if \(i\) gets \(o\), then each neighbor \(j\) must get an item \(o'\) with \(o'\succ_j o\) and \(o\succ_i o'\). The paper uses this encoding to extract MUSes. The paper mentions that the general discrete existence problem is NP-complete, citing [3], but that is not a numbered complexity result of this paper, so I would not use it as an anchor.
Here is the mirror I would put to a prover. The input is a finite list of block types \(b\). A block type is a fixed finite social-network motif \(H_b=(P_b,E_b)\); each position \(p\in P_b\) has a strict ranking \(\succ_{b,p}\) over \(K\) item classes. It occurs with rational block mass \(\lambda_b\), where \(\sum_b |P_b|\lambda_b=1\). Item class \(k\) has rational supply \(s_k\), with \(\sum_k s_k=1\). A type is a position in a block motif together with its preference ranking and neighborhood role. Thus every agent of that type has the same preferences and the same local social structure. Copies of a motif have no edges between them.
Let \(\mathcal A_b\) be the set of assignments \(a:P_b\to[K]\) that give every position one item and are locally envy-free on the block’s edges: for every edge \(\{p,q\}\in E_b\), \(a(p)\succ_{b,p}a(q)\) and \(a(q)\succ_{b,q}a(p)\). The decision variable \(z_{b,a}\) is the mass of blocks of type \(b\) using assignment pattern \(a\). The question is whether there are nonnegative rational \(z_{b,a}\) satisfying
\[ \sum_{a\in\mathcal A_b}z_{b,a}=\lambda_b\quad\text{for every }b, \qquad \sum_{b}\sum_{a\in\mathcal A_b}z_{b,a}\, \bigl|\{p\in P_b:a(p)=k\}\bigr|=s_k\quad\text{for every }k. \]
A solution is such a collection of masses. Each individual still gets one indivisible item: \(z_{b,a}\) describes a mass of whole blocks receiving a locally envy-free assignment, not agents receiving fractional bundles. Item classes represent repeated, interchangeable copies; their supplies scale with the population.
This is a plausible high-multiplicity regime for repeated small teams, housing clusters, or cohorts that allocate one slot per person and compare allocations within a local group. As the number \(N\) of agents grows, the number of distinct position-and-preference types \(\tau\) can stay small: many agents share each type, and item supply is stated per capita. The co-modification of item supplies is part of the mirror. It keeps the paper’s one-item-per-agent allocation question intact while giving it a meaningful population limit.
I expect this version to be tractable (Class A) when motif size is bounded. It is an LP over locally envy-free block configurations. For maximum block size \(h\), one can enumerate at most \(K^h\) patterns per block type, so feasibility is polynomial in the support size, \(K\), and the input bit length for fixed \(h\). The hard part for larger motifs is pricing or generating the locally envy-free configurations; I would not claim tractability there. This is a real computational question about the same allocation and fairness condition, not a continuous outcome-space or probability question.
The scope is deliberately just Proposition 1’s existence problem. I would not claim that this LP mirrors the paper’s MUS-selection criteria, dynamic activation graph, or explanation-length results. The natural next questions are whether infeasibility has useful mass-level certificates, whether those certificates can be rendered as explanations of the kind the paper studies, and how continuous feasible solutions relate to finite populations with indivisible block counts.
The soft spot is the restriction to repeated, disconnected motifs and interchangeable item classes. The paper handles arbitrary social graphs and distinct items; this mirror does not cover those general instances. But within the repeated-motif regime, agents still have complete, identical types, local envy is checked on actual social edges, and every realized block allocation remains integral. That is why I think the restriction is narrow but recognizable as their problem, rather than a tractable reformulation that has lost it.
The strongest objection is that Proposition 1 is an encoding equivalence, not a complexity result: it shows that LEF existence is equivalent to satisfiability of \(\phi\). The paper’s NP-completeness statement cites earlier work, and its own numbered results concern the activation characterization and bounds on explanation metrics. So the proposed LP asks a new computational question about the underlying feasibility problem; it does not continue a complexity result established by this paper.
The proposed block model is coherent, but its contribution may be thin. With bounded blocks, it mixes a finite menu of integral LEF assignments and checks aggregate item supplies. That is a standard configuration LP; the population itself adds little structure. With larger blocks, pricing must handle the LEF assignment problem inside each block, so the original combinatorics sit in the pricing problem while continuous mass merely mixes block outcomes. The paper’s distinctive work—MUS selection and step-by-step explanations—also has no evident counterpart in this model, though one missing mirror alone would not disqualify it.
This objection has a clear limit. Repeated teams or housing clusters with interchangeable item classes are plausible, and the block assignments preserve integral items and local envy on actual edges. The permitted co-modifications cover the scaled supplies. A stronger version using repeated connected cohort templates could be worth studying too. I therefore cannot honestly defend the universal claim that no worthwhile mirror exists. The case against is that this is a weak mirror of the paper’s *results*, not that its continuous LEF problem is ill-posed; the proponent’s anchor remains the strongest part of their case.
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.