| paper | d4-conf-aaai-2014-0411 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 1
statement extracted from the paper’s text layer
For \(m\) candidates, an instance is a piecewise-constant schedule \(\nu:[0,1]\to A\) with rational interval lengths summing to \(1\), fixed before the policy’s random choices. A randomized policy observes each arriving type \(\nu(s)\) but not the future, and may irrevocably add one candidate to an initially empty singleton slate. Let \(\mu_a=|\{s:\nu(s)=a\}|\), and let \(W_{\mathcal A}(\nu)\) be the mass whose top choice is on the slate when it arrives. Determine the asymptotic order in \(m\) of \(\rho_m=\sup_{\mathcal A}\inf_{\nu}\mathbb E[W_{\mathcal A}(\nu)]/\max_a\mu_a\); in particular, does Proposition 1’s \(O(\log\log m/\log m)\) upper bound hold for these ordered mass schedules?
The society is an ordered unit-mass flow with types \(a\in A\), where \(a\) records an agent’s top choice under STNV. The schedule \(\nu\) specifies the type at each population position \(s\in[0,1]\); its total type masses are \(\mu_a\). A nonanticipating policy may select one candidate irrevocably as the flow arrives, earns the mass whose top choice is selected, and is compared with the offline benchmark \(\max_a\mu_a\).
The result is an information-theoretic competitive lower bound rather than a running-time lower bound, so the mirror does not test whether continuous optimization changes computational tractability; the proponent acknowledges this, and it limits the mirror’s reach without defeating the online question.
fatal: False
The mirror covers Proposition 1 for \(k=1\) under STNV and adversarial arrivals. It leaves the random-order guarantees, Mallows results, utility results, and buyback results outside this mirror.
My strongest mirror is an online singleton-slate problem on an ordered mass flow. It keeps the paper’s online choice and its single non-transferable-vote scoring rule, while making the population mass the object being modeled.
Take \(m\) candidates. A type is a complete ranking with a specified top choice; since the scoring rule gives score \(1\) only to the top-ranked candidate and \(0\) to every other candidate, rankings with the same top choice are indistinguishable here. Represent the population by a unit mass of agents arriving in order along \(s\in[0,1]\). An instance is a finite piecewise-constant schedule: each interval has a binary-rational length and a type, and the lengths sum to \(1\). The schedule is fixed before the policy’s random choices, but the policy sees only the type currently arriving, not the future schedule or total type masses.
The policy may add one candidate to an initially empty slate and cannot later replace it. Its welfare is the mass whose top choice is on the slate when that mass arrives. If \(\mu_a\) is the total mass of type \(a\), the offline benchmark is \(\max_a\mu_a\). The question is to determine the best worst-case expected competitive ratio
\[
\rho_m=\sup_{\mathcal A}\inf_{\nu}
\frac{\mathbb E[W_{\mathcal A}(\nu)]}{\max_a\mu_a},
\]
where \(\nu\) ranges over these ordered mass schedules. A solution is an online policy with a guarantee, or an adversarial schedule proving an upper bound on \(\rho_m\).
The anchor is Proposition 1, proved in this paper. It states that against a non-adaptive adversary, every randomized online algorithm has competitive ratio \(O(\log\log m/\log m)\), even when \(k=1\) and the scoring rule is STNV—the positional score vector has \(1\) in the first position and \(0\) elsewhere. Thus the guarantee tends to zero as the number of candidates grows. This is an online inapproximability result, not a conventional NP-hardness classification.
The proposition’s construction carries over to mass schedules: its successive blocks become rational masses \(X^j/m\), with the remaining mass distributed among the candidates. The indistinguishability argument still applies because the future block lengths and types are hidden. There are at most \(m\) relevant types, and the total population can be arbitrarily large relative to that support: scaling the rational masses gives a finite electorate with many agents per type. The lower bound’s combinatorics depend on \(m\) and the order of demand, not on keeping voters individually distinct. I expect this mirror to be Class B-style: the discrete lower-bound construction embeds in the continuous-flow model, so the population continuum does not remove it.
A plausible regime is a high-volume product service whose customers arrive in waves: many customers share a top-choice product, and the provider must commit to one product without knowing future demand. Their top choice is a sufficient type description for this scoring rule; the waves supply the order that makes the decision online. This is close to the paper’s own manufacturer scenario, with mass replacing headcounts. The authors would likely recognize it as their problem’s fluid-population form: preferences, scoring, irrevocability, and the information constraint are all retained. The temporal coordinate records arrival order; population mass is still what is being continuized.
The main open question generated by this mirror is whether the \(O(\log\log m/\log m)\) upper bound is tight. Another is how much structure on the ordered mass flow—such as a bound on type changes—would permit a constant guarantee.
My weakest point is that a static distribution \(\mu\) alone cannot express the hidden-future constraint; the mirror needs the population’s order as well as its type masses. The proposed object is therefore an ordered mass flow, not just a profile simplex point. Also, the paper’s result is an information-theoretic online lower bound, not a running-time hardness result. These limit what the mirror says, but the ordered flow still makes the population continuous while preserving the paper’s central computational question: what can an online decision-maker guarantee as demand arrives?
The strongest objection is about what Proposition 1 would ask ChoCo to study. Its lower bound is information theoretic: it applies to every online policy, regardless of computation time. A continuous mass version therefore asks for the best guarantee under hidden arrival order, not for the complexity of a mass-transfer problem or for an algorithm enabled by continuous optimization. The paper’s construction can be translated from voter counts to rational block masses, but that translation does not make the computational question more tractable or expose a new optimization structure.
A static society \(\mu\) cannot preserve the anchor: two arrival schedules with the same type masses can give an online policy different information at each step. The proposed ordered flow \(\nu(s)\) repairs this, but makes arrival position essential to the instance. That puts the mirror closer to continuous-time online algorithms than to ChoCo’s core model of a distribution over types. If that is outside the programme’s intended scope, it is the best reason to set this anchor aside.
It is not, however, a decisive objection. The flow still represents positive masses of indistinguishable customers, and the lower-bound construction can use a small number of rational-mass waves. So this is not an identity objection, and the proposed mirror is coherent. I cannot honestly claim the anchor fails altogether: if ChoCo includes online competitive guarantees, Proposition 1 survives as a plausible mirror. The negative case is strongest only if the programme reserves its effort for computational questions where continuization changes the algorithmic or complexity landscape.
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.