| paper | Now We’re Talking: Better Deliberation Groups through Submodular Optimization |
| authors | — |
| venue | AAAI 2023 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.3
statement extracted from the paper’s text layer
Given finitely many complete participant types \(p\) with rational masses \(\mu_p\), \(k\) tables, \(T\) sessions, and mass-normalized representativeness constraints, choose trajectory masses \(x_{p,\sigma} \ge 0\) for \(\sigma \in [k]^T\) with \(\sum_{\sigma} x_{p,\sigma} = \mu_p\) and feasible per-session table masses, so that \(\Phi_f(x) = 1/2 \sum_{p,q} \sum_{\sigma,\sigma'} x_{p,\sigma} x_{q,\sigma'} f(|\{r : \sigma_r = \sigma'_r\}|)\) simultaneously \(\alpha_T\)-approximates \(\max_{x'} \Phi_f(x')\) for every monotone concave saturation function \(f\) with \(f(0) = 0\).
An atomless society with finitely many complete demographic types and masses \(\mu\); decision variables \(x_{p,\sigma}\) assign each type’s mass to table trajectories, and the objective integrates \(f\) of repeated meetings over unordered pairs of agents.
For trajectory masses, the objective is quadratic and the trajectory space is exponential, so Theorem 5.3’s submodular weighted-coverage proof and polynomial-time guarantee do not transfer automatically.
fatal: False
The mirror covers Theorem 5.3’s simultaneous approximation target and its table-allocation objective, while leaving Theorem 5.4’s conjectured table lower bound, the practical ILP implementation, and the empirical results aside.
There is a credible continuous mirror, but it should be anchored narrowly in the paper’s abstract \(f\)-MAXCOVERAGE result rather than claimed for every aspect of table allocation.
My lead anchor is Theorem 5.3, proved by the authors in this paper (with formal details deferred to the full version). The cited Nemhauser–Wolsey–Fisher theorem supplies the ordinary greedy guarantee; Theorem 5.3’s simultaneous-approximation result is the authors’ contribution.
A natural high-multiplicity regime is a large civic-deliberation platform: perhaps \(10^5\)–\(10^6\) participants assigned repeatedly to parallel discussion groups, with only a few dozen complete participant types. A type records every attribute relevant to the scheduling problem—demographic strata, political viewpoint, age band, language or translation requirement, education, clustering restrictions, and so on. Participants sharing a type are interchangeable for the formal objective and constraints. This is not a claim that every small citizens’ assembly is high-multiplicity; the paper’s 40- or 100-person empirical assemblies are not convincing limit objects. The mirror concerns a scaled-up consultation or repeated assembly programme with \(n\gg\tau\).
The continuous problem I would name is Mass Simultaneous Deliberation-\(f\)-MAXCOVERAGE\(_\infty\).
An instance contains a finite type set \(P\), rational masses \(\mu_p\) summing to one, a finite set \(G\) of interaction-opportunity types, rational weights \(w_g\), a number \(T\) of sessions, and a finite collection \(\mathcal Z\) of legal one-session table patterns. Each pattern \(S\in\mathcal Z\) respects the paper’s table-size and representativeness constraints at the type-mass level. The elements \(g\in G\) are pair-opportunity classes: for example, unordered pairs of participant types, refined where necessary by language, role, or other interaction-relevant information. Their weights are population masses rather than individual counts; in the simplest case, \(w_{\{p,q\}}\) is induced by \(\mu_p\mu_q\).
The decision variable is a multiset \(z\) of exactly \(T\) patterns from \(\mathcal Z\), equivalently integers \(z_S\ge0\) with \(\sum_{S\in\mathcal Z}z_S=T\). Define
\[ M_g(z)=\sum_{S\in\mathcal Z:g\in S}z_S \]
and, for every monotone nondecreasing concave saturation function \(f\) with \(f(0)=0\),
\[ \Phi_f(z)=\sum_{g\in G} w_g f(M_g(z)). \]
The task is to output one schedule \(z\) that simultaneously satisfies
\[ \Phi_f(z)\ge \alpha_T\max_{z'}\Phi_f(z') \]
for every such \(f\), where
\[ \alpha_T= \frac{1-1/e}{2} \left(\frac{1}{1+\log_2T}-\frac1T\right) \in\Omega(1/\log T). \]
This is a genuine population continuization: the schedule still has \(T\) discrete sessions and the same table-allocation semantics, but the population and interaction opportunities are represented by rational masses. A discrete instance with \(n\mu_p\) participants of each type recovers the corresponding high-multiplicity case.
I would expect this problem to be Class A in the explicit-pattern regime. The weighted objective has marginal
\[ \Delta_S(z)= \sum_{g\in S}w_g\bigl(f(M_g(z)+1)-f(M_g(z))\bigr), \]
so the same diminishing-returns argument applies. The proof of Theorem 5.3 carries over with weights in the marginal calculations, giving a polynomial-time simultaneous approximation in \(|G|+|\mathcal Z|+T\) and the input bit length. This is not an unrelated weighted-coverage problem: the paper itself explicitly identifies \(f\)-MAXCOVERAGE as the abstraction to which its main theorem applies.
The mirror would therefore cover Theorem 5.3 emphatically, and indirectly Lemmas 5.1 and 5.2 as its technical components. It would not claim that the paper’s implicit table-allocation problem becomes polynomial: the paper expressly relies on ILP because the legal partition family may be exponentially large and even partition feasibility is NP-hard. The next ChoCo question is whether the implicit type-mass family admits a configuration-LP or separation oracle under useful restrictions on the number of types and features.
The weakest point is the identity carried by repeated meetings. In the exact atomless model, agents of one type may be split across tables and sessions. A fully faithful formulation would use variables \(q_{p,\sigma}\), the mass of type \(p\) following table trajectory \(\sigma\in[k]^T\), with objective
\[ \frac12\sum_{p,q}\sum_{\sigma,\sigma'} q_{p,\sigma}q_{q,\sigma'} f\!\left(|\{r:\sigma_r=\sigma'_r\}|\right). \]
That exact formulation has exponentially many trajectory variables and a quadratic objective. If a referee insists on this unrestricted version, the explicit-pattern mirror may look like a controlled abstraction rather than the entire continuum limit. But the objection does not erase the case: Theorem 5.3 is itself stated for the paper’s explicit \(f\)-MAXCOVERAGE abstraction, and the mass version preserves its sessions, table patterns, pair interactions, saturation functions, and approximation question.
I would not add Theorem 5.4 as a second anchor. Its \(f\)-MAXCOVERAGE impossibility result is useful as a boundary question, but the authors only conjecture that the same lower bound can be realized by actual table-allocation instances. The honest follow-up is whether those block constructions survive the transitivity constraints imposed by real tables. That unresolved boundary is precisely the sort of question a continuous mirror should generate, not a reason to reject this one.
The proponent’s stated mirror does not survive scrutiny, although the universal negative is ultimately too strong.
The central defect is that Theorem 5.3 concerns an explicitly represented family of sets, whereas the paper’s table-allocation sets are sets of pairs of named participants. Replacing participants by type masses does not preserve those sets. Repeated meetings are identity-sensitive.
Take four agents of one type, two tables, and two sessions. The schedule \(\{1,2\}\mid\{3,4\}\) repeated twice and the schedule \(\{1,2\}\mid\{3,4\}\), followed by \(\{1,3\}\mid\{2,4\}\), have exactly the same type-mass pattern in every session: one half of the sole type sits at each table. Yet their \(f^1\) values differ: the first has two distinct meetings, the second four. A ground element representing the type pair \((p,p)\) cannot distinguish them. Thus the proposed weights \(w_{\{p,q\}}=\mu_p\mu_q\) do not define the paper’s objective.
There are only two repairs. One can aggregate meetings by type pair, but then the problem is no longer the paper’s repeated-meeting objective: applying \(f\) to an average meeting count loses the distribution of meetings among individual pairs. Or one can retain the necessary information by assigning each agent a table trajectory \(\sigma\in[k]^T\). That is the proponent’s \(q_{p,\sigma}\) formulation. It is a legitimate continuous model, but its objective is quadratic in trajectory masses and the trajectory space is exponential. Theorem 5.3’s submodular set-selection proof no longer applies.
Consequently, the explicit-pattern version is not really a continuization of the population. The schedule remains an integer selection of externally supplied patterns, while \(\mu\) merely supplies weights. With \(\mathcal Z\) explicit, the result is just the paper’s generic weighted \(f\)-MAXCOVERAGE theorem; with \(\mathcal Z\) derived from actual type-mass table assignments, the pair-identity problem reappears and the theorem does not transfer. The proposed formulation therefore has a false choice between a generic weighted coverage problem and a substantially different trajectory-coupling problem.
That defeats Theorem 5.3 as the claimed ChoCo anchor. It does not, however, honestly establish the requested universal conclusion. The trajectory model is a genuine high-multiplicity continuous society: rational trajectory masses can be rounded to finite populations, and atomless assignments preserve exactly the pair-meeting objective. Its nonlinear optimization and possible configuration or relaxation theory could itself be worthwhile. The strongest defensible negative verdict is therefore: reject the proponent’s particular mirror and do not count Theorem 5.3 as a population-continuization result; but claiming that no worthwhile continuous mirror exists in any re-modelling would overreach.
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.