| paper | d4-conf-ijcai-2018-0751 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→P discrete result → its continuous mirror
Answer: Every instance admits a stable allocation. Existence and construction are in \(\mathrm{P}\), and construction is \(\mathrm{FPT}\) parameterized by \(k=m+\tau\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), activities \(A\), and rational approval intervals \(I_{t,a}\subseteq[0,1]\), find a stable allocation \(x_{t,a}\ge 0\), including a void option \(a_0\), with \(\sum_{a\in A\cup\{a_0\}}x_{t,a}=\mu_t\). Let \(z_a=\sum_t x_{t,a}\); require \(x_{t,a}>0\Rightarrow z_a\in I_{t,a}\), and, whenever type \(t\) has positive mass left in the void, require that \(z_a\) is not a right-accumulation point of \(I_{t,a}\) for every activity \(a\).
A continuum of event participants grouped into finitely many approval types, with rational mass per type, fractional allocation across activities, and approval determined by each activity's population share. Stability means no remaining type mass can enter in an arbitrarily small positive amount and be satisfied.
Standard nonatomic unilateral stability would test whether the current activity share belongs to a type's approval interval; the proposed right-accumulation test instead captures limits of finite one-agent entry tests. The proponent acknowledges this modeling choice but does not establish that the authors would prefer that convention.
fatal: False
The mirror covers the Nash-stability case of Theorem 4 for edgeless association graphs, few approval types, and consecutive size approvals. It leaves aside the paper's results for unrestricted approval sets, treewidth, vertex cover, and nowhere-dense graphs.
My strongest mirror is a narrow one: anonymous, high-multiplicity SIMPLE-CAS, where people differ only in which activity sizes they approve. It keeps the paper’s central question—can everyone be assigned so that participants are willing to attend and nonparticipants have no profitable reason to join—while making the population itself continuous.
The anchor is Theorem 4, proved in this paper. It says that SIMPLE-CAS\(^*\) can be solved in time \(2^{O(q(p+1))}n^4\log n\) when the association graph is edgeless. Here there are at most \(p\) activities, at most \(q\) distinct approval portfolios, and each portfolio approves a consecutive interval of group sizes for each activity; the requested stability conditions are part of the instance. The theorem therefore gives an FPT algorithm parameterized by \(p+q\), for Nash stability, envy-freeness, or both. I use its Nash-stability case.
A plausible regime is a very large recurring online event with a small menu of activities. Millions of people may choose among discussion sessions, games, or workshops; their preferences depend on the activity and its audience size, but not on named friends or enemies. Many people share the same size preferences. If the event scales, those preferences can naturally be expressed as ranges for the fraction of registrants in an activity. The regime has \(N\) people and only \(q\) approval types, with \(N\) much larger than \(q\). This matches the paper’s few-types restriction rather than inventing a new reason to aggregate people.
Call the continuous problem Mass-SIMPLE-CAS. An instance has a finite type set \(T\), with \(|T|=q\); rational masses \(\mu_t>0\) summing to \(1\); a set \(A\) of \(p\) activities; and, for every type \(t\) and activity \(a\), a rational approval interval \(I_{t,a}\subseteq[0,1]\). The interval gives the population shares at which type \(t\) approves of activity \(a\). A solution is an allocation \(x_{t,a}\ge 0\), including a void option \(a_0\), with
\[
\sum_{a\in A\cup\{a_0\}}x_{t,a}=\mu_t.
\]
Write \(z_a=\sum_t x_{t,a}\) for the mass assigned to activity \(a\). Individual rationality requires \(x_{t,a}>0\Rightarrow z_a\in I_{t,a}\).
For stability, use the population-scaled entry condition: a positive mass of type \(t\) left in the void cannot enter any activity in an arbitrarily small positive amount and end up approving its resulting size. Equivalently, \(z_a\) must not be a right-accumulation point of \(I_{t,a}\) for any activity \(a\). This spells out how the finite “one more agent joins” condition is interpreted as group sizes become population shares. The problem is to find such a stable allocation, or report that none exists; it has no optimization objective in the paper, so I would not add one.
I expect this mirror to be tractable, in Class A: specifically, FPT in \(p+q\) and the binary input length \(L\). Theorem 4’s proof branches over finitely many activity-size and type-compatibility cases, then uses a circulation formulation. In the mass version, the units become rational supplies, and the remaining allocation feasibility checks are flow constraints. That is a reason to expect the algorithmic structure to survive, not a claim that Theorem 4 already proves a continuous theorem.
The mirror covers Theorem 4’s edgeless, few-approval-types regime, not the paper’s full CAS landscape. The paper also proves Theorem 2, that CAS\(^*\) is W[1]-hard even on edgeless association graphs. I would not use that as an anchor for this case: it concerns unrestricted approval sets, whereas SIMPLE-CAS\(^*\) imposes consecutive approvals and few portfolios. Its hardness is a useful boundary question for a broader mirror, but it does not negate the narrower mass problem grounded in Theorem 4.
The main weakness is exactly that narrowness. Removing friend and enemy relations rules out socially structured groups, and making activity sizes population shares assumes those preferences remain meaningful as the event scales. The nonatomic stability convention also fixes a boundary behavior that the finite one-person test does not settle automatically. Those limits leave further questions worth asking: does tractability survive for more general approval sets, can sparse interaction patterns be represented without returning to named agents, and how robust is stable existence to small changes in type masses or interval endpoints?
The best objection to the proposed mirror is that its stability condition is not forced by the paper’s definition. In a finite society, an agent outside an activity tests whether its size *after one more agent joins* is approved. In a nonatomic society, one person has zero mass, so a literal individual deviation leaves the activity size unchanged; ordinary Nash stability would test approval at the current mass. The proposed right-accumulation test instead captures whether an arbitrarily small *group* could join. Both are defensible continuous models, but they can disagree at interval endpoints—the very thresholds the paper’s algorithm has to track. Theorem 4 therefore does not, by itself, identify which continuous stability question to ask.
That objection weakens on the stronger version of the mirror. If the authors accept stability as the limit of finite one-agent deviations under replication, right-accumulation is a natural definition. Requiring positive leftover mass of a type before it can deviate fixes another issue in the proposal’s wording. With those choices explicit, the mass problem is well-posed and its rational supplies and interval constraints look amenable to the circulation approach. A missing definition in the paper is a modeling decision to resolve, not a reason the mirror cannot be worthwhile.
The event scenario also requires share-based preferences: people must care about an activity’s share of the population, rather than an absolute attendance range. For fixed-capacity activities, normalizing sizes by a growing population would send their masses toward zero and make this particular limit uninformative. But share-based preferences for large online communities are plausible, so that concern narrows the scenario without eliminating it.
The computational payoff may be modest. Theorem 4 already exploits a small number of approval types, and replacing integer token counts with rational mass constraints may leave much of its algorithm intact. Still, the theorem is a named computational result, and this paper’s setting—few types, no friend or enemy links—is unusually well suited to a high-multiplicity interpretation. Theorem 2’s hardness for unrestricted approval sets does not defeat this narrower mirror.
So the strongest case against is that the mirror needs a carefully chosen stability definition and may yield a routine extension of an existing algorithm. I cannot honestly turn that into the claim that no worthwhile scenario exists. Theorem 4 remains a credible continuous-population mirror; the negative case against this anchor is 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.