| paper | d4-conf-wine-2023-0022 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), binary utilities \(p:T\times T\to\{0,1\}\), and rational masses \(\mu_t\ge 0\) summing to one, decide whether there is a nonnegative mass distribution \(\rho_{abcd}\) over four consecutive types in a large cycle. Require total mass one, stationarity \(\sum_d\rho_{abcd}=\sum_x\rho_{xabc}\), and type marginals \(\mu_t=\sum_{a,c}Q_{atc}\), where \(Q_{abc}=\sum_d\rho_{abcd}\). For every pair of positive-mass triples \((a,t,c)\) and \((d,u,e)\), require \(p(t,a)+p(t,c)\ge p(t,d)+p(t,e)\); for every positive-mass adjacent window \((a,t,u,e)\), require \(p(t,a)\ge p(t,e)\) and \(p(u,e)\ge p(u,a)\). This asks whether a large-cycle mass society can be envy-free except on a set of vanishing population mass.
A stationary mass distribution over local type windows in large cycles, with type marginals \(\mu\) and envy ruled out between positive-mass contexts. It represents an almost-everywhere population limit, not a geometric circle with immediate neighbors.
Finite arrangements require every guest to be envy-free, while the mass model ignores blocking contexts of vanishing mass; the paper’s reduction also does not show hardness after replicating types.
fatal: False
Covers cycle envy-freeness from Theorems 1 and 5; leaves path envy-freeness, stability, swap dynamics, and the random-preference analysis untouched.
The strongest positive case is for a large-cycle, high-multiplicity version of envy-free seating. The types are complete preference classes: \(p(t,u)\) is the utility a type-\(t\) person gets from a type-\(u\) neighbor, and people of the same type are indistinguishable in every way the seating problem uses. The population is a rational mass vector \(\mu\), with \(\sum_t\mu_t=1\).
A continuous cycle still needs to preserve the paper’s two-neighbor utility and seat swaps. I would encode its arrangement by \(\rho_{abcd}\), the mass of locations whose four consecutive types are \(a,b,c,d\). Require \(\rho\ge0\), total mass one, and the stationarity conditions \(\sum_d\rho_{abcd}=\sum_x\rho_{xabc}\) for every triple \(a,b,c\). These ensure that the local pattern masses fit together around a large cycle. Write \(Q_{abc}=\sum_d\rho_{abcd}\); then the type masses must satisfy \(\mu_t=\sum_{a,c}Q_{atc}\).
Call this problem Mass-Cycle Envy-Freeness. Its input is \(T,p,\mu\); its decision variable is \(\rho\). It asks whether there is such a local-mass arrangement in which no positive-mass type-context envies another occupied seat. For any occupied triples \((a,t,c)\) and \((d,u,e)\), require \(p(t,a)+p(t,c)\ge p(t,d)+p(t,e)\). For adjacent occupants in any positive-mass window \((a,t,u,e)\), also require \(p(t,a)\ge p(t,e)\) and \(p(u,e)\ge p(u,a)\), which checks each person’s utility after the adjacent swap. The objective is feasibility; a solution is the mass vector \(\rho\), not a winner or a divisible bundle. Here \(\rho\) describes frequencies of local seat patterns in the population, not a lottery over seating outcomes. This preserves the paper’s central question while taking the cycle to its large-population limit.
My lead hardness anchor is Theorem 1, proved in this paper: with binary preferences, deciding whether an envy-free arrangement exists on a cycle is NP-hard. The proof reduces from directed Hamiltonian Cycle; the paper also notes that [10] had already proved a stronger hardness result for symmetric binary preferences. Mass-Cycle Envy-Freeness with binary \(p\) and unrestricted \(|T|\) is the direct population-mass question I would hand to a prover. I expect hardness to survive when the type interaction graph grows, because the reduction’s combinatorics sit in that graph. That is a prediction, not a consequence of Theorem 1.
The high-multiplicity anchor is Theorem 5, also proved here: for any fixed \(k\), \(k\)-class preferences admit polynomial-time algorithms that find an envy-free or stable arrangement on a cycle, or report that none exists, with arbitrary preference values. The paper also proves the corresponding result for paths. The continuous question I take from it is Mass-Cycle Envy-Freeness restricted to \(|T|\le k\), with rational masses and rational preferences. I expect this version to be tractable: for fixed \(k\), there are only constantly many local patterns and support choices for \(\rho\), after which feasibility is a finite system of linear constraints. This anchor is the clearest evidence that authors could recognize a genuine regime with many people per type: for example, a large conference or assembly where attendees’ neighbor preferences depend on a fixed set of roles or delegations.
The theorem’s hard instances have an important limitation for this programme. Theorem 1’s reduction uses \(3n\) agents and effectively \(3n\) distinct types, so it does not establish hardness when the population is large relative to the number of types. It is a meaningful mirror of the paper’s unrestricted-type problem, but not evidence that hardness survives in the most compelling high-multiplicity regime.
That caveat is also my weakest point. The continuous local-mass model permits the mass of a type to be represented at a scale that need not match the original number of agents. The paper’s finite-instance question may therefore differ from asking whether *some replication* of the type counts admits an envy-free cycle. Theorem 1 does not show that a no-instance stays a no-instance under replication; proving or refuting that homogeneity property is a central follow-up. If replication can make a no-instance feasible, the hard mirror could become easier in the continuum. I would limit the proposed case to cycle envy-freeness: the same population-continuity argument does not automatically settle paths with endpoint effects, stability, or the paper’s dynamics results.
The strongest objection is that a cycle has no ordinary continuous seating limit. If its length is normalized to one, the distance between neighbors tends to zero, and the limiting circle has no immediate left and right neighbors. Keeping those neighbors as a primitive relation leads to a shift system over type sequences. The proposed \(\rho_{abcd}\) records frequencies in that system; it does not describe an arrangement on a continuous circle.
That matters for Theorem 1. Envy-freeness quantifies over every guest and every possible seat swap. A limit of local frequencies can discard a blocking configuration confined to a vanishing fraction of seats. Requiring envy-freeness only among positive-mass contexts changes the criterion to an almost-everywhere one. Keeping track of exceptional guests would require finite marked agents alongside the mass distribution. The theorem’s Hamiltonian-cycle reduction also relies on preference types that encode individual graph vertices. Cloning those types to create high multiplicity need not preserve the reduction: repeated visits to a type can break the correspondence with a Hamiltonian cycle. So Theorem 1 supports a continuous mirror only if a new model and a suitable high-multiplicity reduction are supplied.
Theorem 5 is harder to dismiss. Bounded preference classes are a plausible large-population regime, and a mass version could ask which type frequencies admit a stable or envy-free arrangement. The paper’s finite-state algorithm suggests a route through local-pattern frequencies, perhaps as a weighted circulation or LP. The negative case is that, for fixed support, this looks like a compact extension of a problem the paper already solves for every finite class count, rather than a new complexity frontier. That is a reason to expect a modest result, though it does not show the question lacks value.
So I can make a substantial case against treating Theorem 1’s hardness as evidence for a high-multiplicity mirror: the natural limit changes the seating object, and the reduction does not survive cloning as stated. I cannot honestly defeat the Theorem 5 anchor. Its bounded-class setting is a sensible population regime, and its mass extension remains a well-posed question. The universal negative case is therefore weak.
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.