| paper | d4-conf-aaai-2018-0767 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time achievable under both feedback models: full feedback \(O(\min\{H,\sqrt{H\ln\tau}\})\), partial feedback \(O(\min\{H,\sqrt{H\min\{m,\tau\}\ln\tau}\})\). Regret is zero when \(\tau=1\) or \(m=1\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.3
statement extracted from the paper’s text layer
Given a society with finite support \(\Theta\), binary-rational masses \(\mu_\theta>0\), and each type \(\theta\) specified by a ballot trajectory \((\sigma_r^\theta)_{r=1}^H\), let round \(r\) use a voting rule \(f_r\) that is a distribution over unilaterals and loss vector \(\ell_r\). A deterministic online policy chooses weight shares \(q_r\in\Delta(\Theta)\), inducing profile \(\pi^r_\sigma=\sum_{\theta:\sigma_r^\theta=\sigma}q_r(\theta)\). Does there exist a policy whose expected regret against the best fixed type, \(\mathbb{E}[\sum_{r=1}^H f_r(\pi^r)\cdot\ell_r-\min_{\theta\in\Theta}\sum_{r=1}^H f_r(e_{\sigma_r^\theta})\cdot\ell_r]\), is sublinear in \(H\) under full and partial feedback, and what are the achievable rates as functions of \(H\) and \(\tau=|\Theta|\)?
A repeated organization has a distribution \(\mu\) over exact adviser-protocol types, each type carrying a fixed ballot trajectory across \(H\) discrete rounds. The policy assigns each type a share \(q_r(\theta)\) of total voting weight each round; the voting rule selects an alternative, and regret is measured against the best single type. The population is continuous over types while time and outcomes remain discrete.
Because weights are unrestricted, cohort masses cancel and the \(\tau\)-type guarantee is ordinary online-expert compression; this limits the mirror's contribution to ChoCo's complexity landscape.
fatal: False
The type-level formulation mirrors Theorem 5.3's full- and partial-information guarantees for distributions over unilaterals and Theorem 5.2's deterministic-rule boundary. It leaves the stronger best-weight-vector benchmark and runtime bounds under explicit rule representations open.
The strongest honest mirror is a high-multiplicity online no-regret problem for repeated decisions. The paper does not prove a standard complexity classification such as membership in P or NP-hardness. Its nearest computational anchors are named theorems about regret guarantees and impossibility; if “anchor” strictly requires a P/NP-style result, this paper has none.
Take a population with \(\tau\) positive-mass cohorts, described by a distribution \(\mu\) with binary-rational masses. A type \(\theta\) is a cohort’s complete ballot-generating behavior across the \(H\) rounds: in round \(r\), it submits ranking \(\sigma_r^\theta\). A concrete regime is a large platform or organization whose many automated advisers use a small number of shared evaluation protocols. The individual count can be very large while the number of distinct protocols, \(\tau\), stays small. The small venture-capital group in the paper is not the regime I would rely on.
A weighting action is \(q_r\in\Delta(\Theta)\), the fraction of total voting weight assigned to each type. For \(\mu_\theta>0\), this corresponds to per-person weight \(q_r(\theta)/\mu_\theta\). The resulting weighted profile is
\[
\pi^r_\sigma=\sum_{\theta:\,\sigma_r^\theta=\sigma}q_r(\theta).
\]
With rule \(f_r\) and loss vector \(\ell_r\), the round’s expected loss is \(f_r(\pi^r)\cdot\ell_r\). The benchmark is the best single type:
\[
\min_{\theta\in\Theta}\sum_{r=1}^{H} f_r(e_{\sigma_r^\theta})\cdot\ell_r.
\]
The policy chooses weights from the history; time and outcomes remain discrete. Only the population is represented by mass.
My lead mirror, anchored in Theorem 5.3, is the following problem: given \(\mu\), the type ballots revealed round by round, and a voting rule that is a distribution over unilaterals, does there exist a deterministic online reweighting policy with sublinear worst-case regret against the best type? Here “deterministic” describes the choice of weights; the voting rule itself may randomize. A solution is such a policy. In the paper, Theorem 5.3 is proved there: for any rule that is a distribution over unilaterals, deterministic weighting schemes achieve regret \(O(\sqrt{H\ln n})\) with full information and \(O(\sqrt{Hn\ln n})\) with partial information. This includes randomized positional scoring rules. The theorem is not a running-time classification. For the finite-support mirror, the natural type-level analogue replaces \(n\) by \(\tau\), giving \(O(\sqrt{H\ln\tau})\) and \(O(\sqrt{H\tau\ln\tau})\); this follows by running the corresponding online update over types. I expect this mirror to be regret-tractable when \(\tau\) is moderate.
A useful boundary anchor is Theorem 5.2, also proved in the paper. It states that for a deterministic voting rule \(f\), a deterministic weighting scheme with \(o(H)\) regret exists if and only if \(f\) is constant on unanimous profiles, in both feedback settings. Its continuous question is: for a fixed society with at least two positive-mass types, can a deterministic reweighting policy guarantee sublinear worst-case regret against the best type under deterministic \(f\)? The solution would be a policy with that guarantee. The expected answer is the same sharp boundary: if \(f\) is constant on unanimous profiles, putting all weight on one type gives zero regret; otherwise no such policy exists. For the lower bound, choose rankings \(\tau,\tau'\) with distinct unanimous outcomes. After the policy chooses weights, assign one cohort \(\tau\), the other \(\tau'\), and set loss \(1\) on the selected outcome and \(0\) elsewhere. At least one of the two types gets zero loss that round, while the policy loses \(1\). This can be fixed as a ballot sequence for the deterministic policy and yields linear regret against a fixed type. It is a no-regret impossibility, not an NP-hardness result.
Together these anchors make the mirror more than a relabeling: it asks whether the paper’s rule-dependent boundary survives when voter multiplicities become masses. It covers the paper’s repeated weighted aggregation and regret results, not its whole discussion of voting. For a conventional complexity study, a further question is the running time in \(H,\tau,m\), and the input bit length, assuming efficient evaluation of the rule. Other natural follow-ups are whether the bounds hold for richer benchmarks such as the best weight vector, and what happens when types are only approximately alike.
The soft spot is the type regime. Treating a type as a complete ballot trajectory makes identical types meaningful, but \(\tau\) may grow rapidly with the horizon. The argument also relies on finitely many positive-mass types: for a nonatomic population, an individual type can have zero mass, and competing with the best individual no longer has the finite-support guarantee above. This is a credible mirror for replicated decision protocols with a small number of exact cohorts; it is a much weaker case for a population of heterogeneous people whose ballot histories rarely coincide.
The strongest negative is that the proposed mirror does not create a new continuous-optimization problem. In the paper, voters may receive arbitrary nonnegative weights. For any positive-mass type distribution \(\mu\), an aggregate weight share \(q_t\) can be implemented by giving each member of type \(t\) per-person weight proportional to \(q_t/\mu_t\). Thus every \(q\in\Delta(\Theta)\) is feasible, whatever the cohort masses. The input \(\mu\) drops out: one representative per type gives the same profiles, actions, and benchmark. The continuous question is therefore a quotient of the finite-expert online-learning problem, not a problem whose tractability turns on population mass or continuous optimization.
That makes this a weak fit for ChoCo’s complexity programme. The paper’s theorems establish regret bounds and impossibility results, but specify no running-time model or representation for the voting rule; indeed, Theorem 5.3 covers arbitrary anonymous rules. A runtime question would need extra assumptions about how rules are represented and evaluated. The natural mirror—whether the regret guarantee transfers from \(n\) voters to \(\tau\) types—then follows by running the same online update over those types. That may be useful as a compression result, but it offers little of the programme’s intended complexity landscape.
I cannot honestly say Theorem 5.3’s mirror is invalid. A large organization with many advisers following a small set of shared protocols is a credible high-multiplicity regime. The theorem’s update over \(\tau\) types gives the proposed regret bounds, and the fact that the answer is direct is not, under the stated rules, a reason to reject the question.
Theorem 5.2’s boundary mirror also survives. With two positive-mass cohorts and a deterministic rule that is not constant on unanimous profiles, assign the cohorts rankings whose unanimous outcomes differ. Each round, let \(z\) be the rule’s outcome on the policy’s weighted profile, and set loss \(1\) on \(z\) and \(0\) elsewhere. At least one cohort’s unanimous outcome differs from \(z\), so that type has zero loss while the policy loses \(1\). For a deterministic policy, this adversarial sequence can be fixed in advance by simulating the policy. Conversely, if the rule is constant on unanimous profiles, putting all weight on one type matches every type’s outcome. The same dichotomy therefore holds for the continuous cohorts.
So the negative case is limited: the mass representation adds no operative constraint, and the resulting work looks more like a standard online-learning compression than a ChoCo optimization problem. But both anchors remain sensible continuous questions. I do not see an honest way to defend the universal 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.