| paper | d4-conf-ecai-2025-0232 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Pointwise \(R_T=o(T)\) is polynomial-time achievable. Static selection is \(\mathrm{NP}\)-hard with a constant gap; uniformly polynomial-horizon learning would imply \(\mathrm{NP}=\mathrm{RP}\). An \(\varepsilon\)-accurate implementation in time \(f(\tau,\alpha)\operatorname{poly}(m,L,T,1/\varepsilon,W,\sigma)\) exists. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
Given rational type masses \(\mu_a\), a coalition-size bound \(\alpha\), a per-capita coalition-count bound \(\kappa\), and unknown symmetric type-pair utilities \(w_{ab}\), does there exist a learner with expected regret \(o(T)\) against the minimum achievable maximum pairwise envy? In each round it chooses masses \(x_q\) over nonempty integer group compositions \(q\in\mathbb{Z}_{\ge 0}^{\tau}\) with \(\sum_a q_a\le\alpha\), subject to \(\sum_q q_a x_q=\mu_a\) and \(\sum_q x_q\le\kappa\), then receives one independent sub-Gaussian report for each type pair that co-occurs in positive mass (including \((a,a)\) when a group contains at least two type-\(a\) members). For a type-\(a\) person in composition \(q\), own utility is \(\sum_c(q_c-\mathbf{1}[c=a])w_{ac}\); replacing a type-\(b\) member of composition \(r\) gives utility \(\sum_c(r_c-\mathbf{1}[c=b])w_{ac}\). The envy objective is the maximum positive difference between these utilities over types and positive-mass compositions. Can the learner achieve this regret with an \(f(\tau,\alpha)\operatorname{poly}(L,T,1/\varepsilon)\)-time \(\varepsilon\)-accurate implementation, where \(L\) is the input bit length?
A population distribution over \(\tau\) complete interaction types, with mass \(\mu_a\) per type and shared symmetric pair utilities \(w_{ab}\). Decision variables \(x_q\) give mass per person assigned to each integral group composition, subject to the type-mass and per-capita group-count constraints. The objective and regret benchmark are the maximum replacement envy over compositions with positive mass; each round’s fixed audit supplies noisy reports for co-occurring type pairs.
With the paper’s all-within-coalition feedback rule, repeated types yield many reports per type pair and noise washes out as population size grows; the fixed audit preserves learning but changes the observation rule.
fatal: False
The mirror covers Theorem 4’s instance-independent regret guarantee for online minimax-envy learning; it leaves the instance-dependent bound and the paper’s finite-agent initialization analysis aside.
The strongest anchor is Theorem 4, proved by Cohen and Agmon, with detailed proof in their supplementary material [25]. Under Assumption 1, for any input and with \(\gamma=2\), LCB-EM-CF’s instance-independent envy regret satisfies, for \(\beta>2\),
\[
R_T\le
1.5T^{2/3}
\left(16\Delta_{\max}n^4(\sqrt{2\beta}+2)^2\sigma^2\log T\right)^{1/3}
+4n^2\Delta_{\max}
+\frac{2n^2(n-1)\Delta_{\max}}{\beta-2},
\]
where \(\Delta_{\max}\) is the largest envy gap between a non-minimax-envy partition and a minimax-envy partition. In particular, for fixed instance parameters, the bound is sublinear in \(T\), of order \(T^{2/3}(\log T)^{1/3}\), and does not depend on the minimum suboptimality gap. This is a guarantee about learning to minimize the maximum envy from partial, noisy feedback; it is not a polynomial-time guarantee for choosing each partition.
Here is a continuous problem I would put to a prover: Continuous-Type Online Minimax-Envy Learning. Consider a large population of \(N\) people in a repeated project-grouping system—for example, a large training programme whose participants share a small set of role or collaboration profiles. Let \(\tau\) be the number of profiles, with \(N\) in the thousands or more and \(\tau\) in the tens or low hundreds. A type \(a\) is a complete interaction profile: every person of type \(a\) has the same symmetric utility \(w_{ab}=w_{ba}\) toward every type \(b\), and the same feedback-noise law. This retains the paper’s pairwise preferences and envy criterion while making high multiplicity an actual feature of the instance.
Let \(\mu_a>0\) be the known fraction of the population of type \(a\). Coalition size is capped at \(\alpha\), while the number of groups is capped at \(\kappa N\), for a per-capita group limit \(\kappa\) with \(\alpha\kappa\ge1\). A feasible group composition is an integer vector \(q\in\mathbb Z_{\ge0}^{\tau}\) with \(1\le\sum_a q_a\le\alpha\). The action is a nonnegative mass \(x_q\) of groups of each composition, measured per person in the population, satisfying
\[
\sum_q q_a x_q=\mu_a\quad\text{for every }a,
\qquad
\sum_q x_q\le\kappa.
\]
Thus people remain in integral-sized groups; it is the population split across group compositions that is fractional.
For a type-\(a\) person in a group of composition \(q\), utility is
\[
U_a(q)=\sum_c(q_c-\mathbf 1[c=a])w_{ac}.
\]
If that person considers replacing a type-\(b\) person in a group of composition \(r\), their envy is
\[
\left[U_a(r-e_b)-U_a(q-e_a)\right]_+.
\]
Define \(E(x,w)\) as the maximum of this quantity over types \(a,b\) and compositions \(q,r\) with \(x_q,x_r>0\), \(q_a>0\), and \(r_b>0\). The benchmark \(E^*(\mu,w)\) is the minimum of \(E(x,w)\) over feasible mass allocations. This is the paper’s minimax pairwise envy objective, with coalition counts scaled to the population.
Each round, the learner chooses a feasible \(x^t\), then receives noisy feedback only for type pairs that actually co-occur in positive mass. To keep the paper’s partial, noisy feedback meaningful at continuum scale, I would use a fixed per-round audit: one independent \(\sigma^2\)-subgaussian report around \(w_{ab}\) for each co-occurring type pair. The question is whether there is a learner that uses those reports to output feasible allocations with
\[
\mathbb E\!\left[\sum_{t=1}^T\big(E(x^t,w)-E^*(\mu,w)\big)\right]=o(T),
\]
and runs in \(f(\tau,\alpha)\operatorname{poly}(L,T,1/\varepsilon)\) time for an \(\varepsilon\)-accurate implementation, where \(L\) is the input bit length. That is the continuous analogue of the underlying learning problem, rather than a question about an encoding.
I expect this bounded-type version to be tractable in the parameterized sense, hence a Class A candidate. There are finitely many integral group compositions, and envy depends on an allocation through which compositions have positive mass. For any proposed support of compositions, feasibility is a linear mass-allocation question; enumerating supports may cost a large function of \(\tau\) and \(\alpha\), but that leaves room for an FPT algorithm. The feedback still has to be used to learn the type-pair utilities, so this does not make the learning problem disappear. I would not claim polynomial time in unrestricted \(\tau\): the composition-support search may retain substantial combinatorial difficulty.
The authors should recognize the mirror: it keeps repeated group formation, bounded group sizes and counts, pairwise replacement envy, noisy feedback from interactions, and regret against a minimax-envy benchmark. The changes—type-level utilities, fractional masses of group compositions, and a per-capita group cap—are consequences of making the population the continuous object. This covers Theorem 4’s online minimax-envy learning result, not the paper’s entire model or all hedonic games.
The weak point is material: the paper permits an essentially arbitrary utility for each pair of named individuals, whereas this mirror assumes many people share a complete type profile. Also, the paper’s regret theorem assumes an oracle for choosing a partition that minimizes estimated envy; it does not establish the computational cost of that step. The continuous question therefore asks whether a parameterized allocation method can supply the missing computation. And the audit model is a deliberate co-modification: if one literally observes every interaction in an infinite population, averaging can erase the paper’s noise. Those limits narrow the claim, but leave a recognizable and concrete continuous version of the paper’s central problem.
Theorem 4 is a real anchor: it proves a sublinear-regret guarantee for an online algorithm, so the objection cannot be that the paper has no computational result. The harder question is whether that guarantee survives as a meaningful *learning* problem for a continuous population.
With bounded coalition size and a fixed number \(\tau\) of repeated types, it may not. If a positive mass of each type is placed in groups together, a finite population of size \(N\) produces \(\Theta(N)\) noisy reports for that type pair in a round. Their average has variance \(O(1/N)\), so in the continuous limit the learner learns the pair’s utility essentially exactly on its first co-occurrence. Covering the \(\binom{\tau}{2}\) type pairs then takes a finite number of rounds. The \(n^2\)-scale uncertainty that motivates the paper’s initialization and regret analysis disappears.
A fixed audit budget, as proposed, preserves uncertainty, but it changes the feedback process: reports no longer arrive for every realized within-coalition pair. That is a plausible model for a teacher with limited observation capacity, and the authors might recognize it. Still, the result would concern learning under a new sampling budget, rather than the population limit of the paper’s observation rule. Under the paper’s rule, noise washes out; under the audit rule, the audit design becomes part of the problem.
There is a second mismatch. Theorem 4 assumes an oracle for choosing the partition that minimizes estimated envy. It proves a statistical guarantee, not a running-time bound for that choice. In the proposed type model, there are finitely many group compositions \(q\). One can enumerate their supports, determine each support’s envy, and test feasibility with a linear program. This gives an \(f(\tau,\alpha)\operatorname{poly}(L)\) algorithm directly. That may be too large to use, and a polynomial-time result in \(\tau\) could still be interesting, but the advertised parameterized target follows from finite support enumeration rather than a new continuous-optimization technique. The mirror therefore either makes the learning theorem largely vacuous in the limit or redirects attention to a finite composition-selection problem.
This is not an airtight negative case. Large cohorts with a small set of shared interaction profiles are sensible, and a fixed reporting budget could make the online question worthwhile. The strongest case against is narrower: the natural limit erases the theorem’s noisy-learning challenge, while the co-modification that restores it also changes the learning model and leaves a finite, parameterized allocation problem. That makes this a weak candidate for a *continuous* mirror of Theorem 4, rather than a convincing claim that no worthwhile mirror exists in any scenario.
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.