| paper | d4-journals-ai-2024-0035 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
For each round \(t\), let a large cohort of matched seller–buyer opportunities have a finite-support rational distribution \(\mu_t\) over valuation types \((s,b)\in[0,1]^2\), fixed adversarially in advance. A learner posts a common single price \(p_t\) and receives the two acceptance bits from a uniformly sampled opportunity. For fixed \(\alpha>1\), does the minimax \(\alpha\)-regret against the best fixed price, with per-capita reward \(g_t(p)=\sum_{(s,b)}\mu_t(s,b)(b-s)\mathbf{1}\{s\le p\le b\}\), necessarily grow linearly in \(T\)?
Types are matched opportunities \(\theta=(s,b)\), with cohort mass \(\mu_t(\theta)\). The learner chooses a common price \(p_t\); the sampled opportunity supplies the two-bit feedback, and the per-capita reward is \(g_t(p_t)=\sum_\theta\mu_t(\theta)(b-s)\mathbf{1}\{s\le p_t\le b\}\). Compare the learner’s expected cumulative reward with the fixed-price benchmark \(\max_{p\in[0,1]}\sum_t g_t(p)\) using \(\alpha\)-regret.
The proposed mirrors cover Theorems 1, 4, and 5: the full-feedback lower bound, the single-price two-bit lower bound, and the two-price one-bit upper bound. They do not claim to cover the paper’s other regret bounds or its broader market variants.
I see a credible mirror if the population is a sequence of large market cohorts. The time steps stay discrete; what becomes continuous is the number of bilateral opportunities served at each step. That preserves the paper’s central question—how a learner’s posted prices perform against the best fixed price under adversarial change—while making each round’s society a distribution over types.
Let a type be a pre-matched seller–buyer opportunity \(\theta=(s,b)\), including any context that affects the transaction. At round \(t\), the cohort is a finite-support distribution \(\mu_t\) over these types, with rational masses summing to one. A mass \(\mu_t(\theta)\) means that fraction of the cohort has type \(\theta\); in a finite realization, it can represent \(n_{t,\theta}\) of \(N_t\) pairs. The support size \(\tau\) counts distinct opportunity types, not the number of pairs.
The learner posts \(p_t\le q_t\) to the whole cohort. Each pair either trades or does not, while the cohort’s per-capita gain is \(g_t(p,q)=\sum_{(s,b)}\mu_t(s,b)(b-s)\mathbf 1\{s\le p\le q\le b\}\). Thus the aggregate gain can be fractional even though each pair’s trade is integral. Nature fixes the sequence \(\mu_1,\ldots,\mu_T\) in advance. In the partial-feedback versions, the learner receives the one- or two-bit report of a randomly sampled pair from the cohort; full feedback reveals \(\mu_t\). The question is whether a policy mapping past feedback to prices can guarantee sublinear worst-case \(\alpha\)-regret against \(\max_{p\le q}\sum_t g_t(p,q)\).
A plausible regime is a platform that prices large batches of standardized ride, delivery, or shift opportunities. In a given market cell, many matched opportunities may share the same reservation value, willingness to pay, and relevant context—for example, because offers and acceptance values fall into a bounded set of price tiers. There could be millions of pairs and only a modest number of distinct types. This is a scenario claim, not a claim about every bilateral market. The type includes the full information relevant to the transaction; idiosyncratic valuations create different types.
My lead is Theorem 5, proved in this paper. It states that with one-bit feedback and permission to post two prices, Block-Decomposition achieves \(R^2_T\le 5T^{3/4}\sqrt{\log T}\) for suitable choices of the expert algorithm, grid, and number of blocks. The continuous question is: for the cohort model above, with two prices and one-bit feedback from a sampled pair, is there a policy with sublinear 2-regret against the best fixed posted price? The answer should be yes, with the same bound. The paper’s estimator is unbiased for a single pair’s gain at a fixed price; sampling a pair from \(\mu_t\) makes it unbiased for \(g_t(p)\). Likewise, the discretization inequality can be applied to each type and then integrated over the cohort. So the key parts of the proof appear to lift to mass rewards. This is the strongest anchor because it gives a concrete algorithmic result for the population model, not just a reason to ask the question.
Theorem 4, also proved here, supplies a distinct negative anchor. With two-bit feedback but only a single price, it proves that for every constant \(\alpha>1\), the minimax \(\alpha\)-regret is at least \(T/(128\alpha^3)\). The continuous question is whether single-price policies can achieve sublinear \(\alpha\)-regret in the cohort model with two-bit sampled feedback. They cannot: restrict the adversary to cohorts with \(\mu_t\) concentrated on one type. Then all pairs in a cohort give the same feedback, and its per-capita reward is exactly the reward of the single pair in the paper. The lower-bound construction draws these cohort types from finite sets whose size depends on \(\alpha\), not \(T\), so this is compatible with very large cohorts and a small type support. The expected direction is an inherited linear lower bound. This is a useful boundary to the positive result: the mirror retains the paper’s separation between single-price and two-price learning.
Theorem 1, proved here, is a further full-feedback anchor. It establishes that for every \(\varepsilon\in(0,1]\), even with full feedback, the minimax \((2-\varepsilon)\)-regret is at least \(\varepsilon T/8\). The continuous question is whether revealing the full cohort type distribution allows sublinear \((2-\varepsilon)\)-regret. It does not: point-mass cohorts again reproduce the theorem’s hard sequences, and for those cohorts revealing \(\mu_t\) is exactly revealing the seller and buyer values. The lower bound applies even though the learner may post two prices; as in the paper, a fixed comparator gains nothing by using unequal prices. This gives a second, independent no-go boundary, now under the richest feedback model.
I think the authors would recognize these as mirrors of their problem: the same bilateral transaction, budget-balanced price actions, gain-from-trade objective, feedback distinctions, and fixed-price hindsight comparator remain. The change is a large cohort per time step, represented by type masses. That is a natural high-multiplicity extension of their sequential setting. The scope here is specifically its online regret results; the paper does not provide NP-hardness, membership in P, or other classical complexity-class results, and I would not present these regret bounds as such.
The follow-up questions include whether exact aggregate feedback—such as the fraction of a mixed cohort that trades—changes the single-price lower bound; how the guarantees depend on \(\tau\) when the type dictionary is explicit; and whether the partial-feedback gap between an \(\Omega(T^{2/3})\) lower bound and the \(O(T^{3/4}\sqrt{\log T})\) upper bound closes in the cohort model.
The weakest point is the feedback interpretation. A one-bit report from a sampled member preserves the paper’s information constraint and lets Theorem 5’s estimator extend, but a platform that observes the exact response fractions of a continuum cohort gets richer feedback. The paper does not study batches, and its results do not establish that the same bounds hold under that richer observation. The mirror is strongest when the market truly gives sampled or severely aggregated feedback; changing that convention could change the negative results.
The strongest case against is a scope objection, and it does not defeat the mirrors. This paper’s named results concern online regret and feedback: they do not analyze a computation on a society given as an input. In the cohort version, the key difficulty remains learning against an adversarial sequence over time. The population measure supplies the reward and feedback distributions, but the paper’s algorithm still uses a price grid and an expert method. That makes the mirror a natural online-learning extension, but a weak fit for ChoCo’s focus on the complexity of computational social choice problems over populations.
That objection does not make Theorem 5 go away. With a cohort distribution \(\mu_t\) over seller–buyer types, the per-capita reward is
\[
g_t(p,q)=\sum_{(s,b)}\mu_t(s,b)(b-s)\mathbf{1}\{s\le p\le q\le b\}.
\]
If the learner gets a one-bit report from a sampled pair, the paper’s estimator remains unbiased after averaging over that sample: its expected value is \(g_t(p)\). The block algorithm’s guarantee therefore has a credible route to the cohort model. Calling this merely a restatement would not be a sound objection; it is a well-posed extension, even if the proof lifts cleanly.
The lower-bound anchors are harder to dislodge. For Theorem 4, use cohorts concentrated on one type at each time step. Every member then gives the same two-bit feedback, so the paper’s hard instances and linear lower bound carry over. Theorem 1 transfers the same way under full feedback: revealing the point-mass distribution is equivalent to revealing the pair’s valuations. Even exact cohort response fractions would not help on these instances, since every fraction is \(0\) or \(1\). These are valid mirrors, though they show that the bounds can arise without mixed cohorts.
So the adverse case is that the population continuum contributes little to the paper’s central technical story: the positive result extends by averaging, while the negative results already hold in a one-type regime. That is a reason to rank this mirror below work where mass structure changes the algorithmic problem. It is not a reason to reject it. The cohort scenario is plausible, the type model is coherent, and at least one anchor survives in a stronger version. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists; the negative case is weak at precisely the point the proponent’s case is strongest: this is a sensible high-multiplicity online market problem.
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.