| paper | d4-conf-ijcai-2021-0181 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Both anchors are computational, but the proposed continuous question is already formulated in the paper’s known-distribution, infinite-committee section. Substituting \(q_x=p(x)\pi^*(x,1)\) yields the same mass constraints and objective, and Proposition 2 connects that model to finite committees. The mirror therefore restates a continuous model already in the paper.
fails bit b-already — the paper is already native to the continuum
The mass formulation is exactly the paper’s known-\(p\) CMDP after setting \(q_x=p(x)\pi^*(x,1)\); Section 4 already gives that LP and Proposition 2 relates it to finite committees.
fatal: True
The mass LP recasts the known-\(p\) CMDP underlying Proposition 2; Theorem 1’s unknown-\(p\) learning model is also already distributional, while Proposition 1 and the experiments are not distinct continuous results.
The strongest positive case is high-multiplicity volunteer recruitment for a citizens’ assembly or a large hiring cohort. Let a type be a volunteer’s complete joint feature profile—for the Brexit example, one of at most \(2\cdot2\cdot3\cdot8\cdot2\cdot2=384\) demographic profiles. In a large recruitment pool, there may be many thousands of volunteers but relatively few distinct profiles. Let \(\mu_x\) be the share of volunteers of type \(x\). If volunteers of the same type face the same selection criteria and screening cost, treating their identities as interchangeable is faithful to the problem. The paper itself conditions on volunteers, so this is the volunteer-pool distribution, not the distribution of the whole electorate.
My lead mirror is Fluid Quota Admission. Its instance is an explicitly listed support \(S\), rational type masses \(\mu_x\) summing to one, and target marginals \(\rho_j^i\). Choose admitted mass \(q_x\) by type, with \(0\le q_x\le\mu_x\), to maximize the admission rate \(g=\sum_{x\in S}q_x\), subject to
\[
\sum_{x:x^i=j}q_x=\rho_j^i g
\quad\text{for every feature }i\text{ and value }j.
\]
A solution is the maximizing mass vector \(q\); where \(\mu_x>0\), it also gives the type’s acceptance probability \(q_x/\mu_x\). If no positive feasible mass exists, the target cannot be met from this pool. This asks the underlying question—how much of the volunteer flow can be admitted while matching the requested representation—not a question about an LP encoding. On explicit support, it is a rational LP with \(|S|\) variables and \(O(\sum_i D_i)\) quota constraints, so I expect Class A. It also gives a direct screening-cost interpretation: the stationary policy needs, in expectation, \(K/g\) candidate arrivals to admit \(K\) people.
The strongest anchor for that question is Proposition 2 (proved here). For known candidate distribution \(p\), take an optimal stationary policy \(\pi^*\) for the paper’s CMDP and use it while recruiting a committee of size \(K\). For every \(\delta>0\), the resulting committee’s representation loss is at most
\[
\sqrt{\frac{\log(2\tilde d/\delta)}{2K}}
\]
with probability at least \(1-\delta\), where \(\tilde d=\sum_i(D_i-1)\). This is the finite-committee guarantee around the fluid quota solution: the continuous policy fixes the selected type proportions in expectation, and sampling produces a finite committee whose proportions concentrate around the targets. Proposition 2 is a probabilistic performance result, not a theorem classifying the problem as polynomial-time solvable.
A second, distinct mirror is Sample-Access Fluid Quota Learning. The instance is the feature domain \(\mathcal X\), target marginals, a fixed but hidden type distribution \(p\), and access to successive independent samples \(x_t\sim p\). After seeing each type, a policy must immediately accept or reject it. The comparator is the best stationary type-based policy satisfying the quota equalities for \(p\); a solution is an online policy with small regret against that comparator and small cumulative quota imbalance. This retains the paper’s immediate-decision constraint while making the unknown population composition the object to learn.
Its anchor is Theorem 1 (proved here). With probability at least \(1-\delta\), the paper’s \(\optalg\) has regret and maximum cumulative constraint violation both \(O(\sqrt{|\mathcal X|T\log(|\mathcal X|T/\delta)})\) through horizon \(T\). It also gives representation loss \(O((1/g^*)\sqrt{|\mathcal X|\log(|\mathcal X|T/\delta)/T})\), where \(g^*\) is the optimal selection rate. I would expect Class A in this sample-access formulation: the paper supplies an algorithm and statistical guarantees. That is a learning result, though, rather than a conventional time-complexity classification. Further questions include whether the guarantees can depend on the observed support size \(\tau\) instead of the full product size \(|\mathcal X|\), and how they change when the target is infeasible on the pool’s support.
These are the paper’s strongest named anchors for a positive case. It has no numbered NP-hardness or standard complexity-class result to anchor; the paper says its setting shifts attention from computational-complexity analysis to probabilistic guarantees. So this is a case for a faithful and tractable continuous formulation, not for showing that discrete hardness dissolves.
The main weakness is also the clearest evidence of plausibility: Section 4 already takes an infinite-committee limit, optimizes selection rate under proportionality constraints, and writes the CMDP as an LP. The proposed mass-admission problem is therefore something these authors would readily recognize, but much of it is already in their paper. The finite online process and the fluid optimization are genuinely distinct, and Proposition 2 links them; still, this is weak evidence for a *new* continuization gap. It is a strong example of a continuous population model already functioning inside computational social choice.
The strongest case against a new mirror is that the paper already makes the volunteer population a distribution over types. A candidate’s complete type for these decisions is their feature vector \(x\); the paper draws \(x_t\) from a fixed distribution \(p\), and its known-\(p\) section explicitly takes the infinite-committee limit. That is already a continuous population model in the proposed citizens’ assembly scenario.
Proposition 2 does not supply a new computational question for that model. Set \(q_x=p(x)\pi^*(x,1)\): the accepted mass of each type. The CMDP’s proportionality constraints become \(\sum_{x:x^i=j}q_x=\rho_j^i\sum_x q_x\), and maximizing the selection rate is maximizing \(\sum_xq_x\). These are exactly the constraints and objective of “Fluid Quota Admission.” Its LP is a sparse-support rewrite of the paper’s own CMDP LP. In the continuum the quotas hold exactly; for a finite committee, Proposition 2 already bounds the sampling error around them. So the stronger version of this mirror is either the LP the paper already gives or the finite-sampling question it already answers.
Theorem 1 also lacks a distinct continuous counterpart: its unknown-\(p\) setting already treats the stream as samples from an aggregate type distribution and learns that distribution online. If the mirror supplies exact type masses, it removes the uncertainty the theorem studies and reduces to the known-\(p\) LP. If it retains sample access, it restates the paper’s learning problem. Changing the story to a hiring cohort does not open a gap: once candidates are grouped by all attributes relevant to selection, the same distribution-over-types formulation applies. Adding further decision-relevant attributes may enlarge the support, but that changes the instance size, not the nature of the mirror.
There is also a mismatch with ChoCo’s central complexity landscape. The paper gives regret, constraint-violation, representation-loss, and sample-complexity guarantees, but no result classifying the computational complexity of its problem or the running time of its algorithms. Those guarantees are valuable, yet mirroring them would extend an existing statistical analysis of an already distributional model, rather than chart the new complexity questions the programme targets.
I cannot honestly make the universal claim airtight: large assemblies with many volunteers and relatively few demographic profiles are a sensible high-multiplicity regime. But that is also the paper’s own motivating regime, and the paper already models it continuously. The negative case is strongest as a claim of no worthwhile new continuization gap here, not as a claim that no related continuous research could be worthwhile.
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.