| paper | d4-conf-sagt-2018-0026 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Yes. Universal constants exist, and \(k=1\) suffices. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
For each δ = 1/(2n), let a society be a finite set of buyer and seller valuation types with rational mass distribution μ, total buyer mass and seller mass each 1/2, and every positive type mass a multiple of δ. The society arrives as a uniformly random permutation of packets of mass δ; a packet's role and valuation are revealed on arrival, and an online posted-price policy may trade only when the packet accepts and inventory permits. Does there exist a policy A_δ, independent of μ, such that for every such society, E[W_Aδ(μ)] ≥ (1 - \widetilde{O}(δ^{1/3})) OPT(μ), where OPT assigns the item mass to the highest-valued population mass 1/2?
A high-multiplicity online trading market whose types specify role and valuation and carry mass μ_t. Each arrival packet has mass δ and brings or demands δ units of inventory; a policy observes packets in uniformly random order, sets prices from the history and δ, and seeks to maximize mass-weighted terminal welfare against the offline top-half benchmark.
The mirror covers Theorem 1's welfare guarantee only; it leaves the gain-from-trade results, including Theorems 2 and 3, outside the mirror.
My strongest case is a narrow mirror of the paper’s welfare result. The paper has no named NP-hardness or complexity-class result to anchor; its strongest fit here is an online algorithmic guarantee.
The anchor is Theorem 1, proved in this paper. It states that, with \(n\) buyers and \(n\) sellers whose adversarially chosen valuations arrive in a uniformly random order, the paper’s posted-price algorithm is \(\left(1-\widetilde O(n^{-1/3})\right)\)-competitive for welfare against the offline optimum. The algorithm samples the first \(8n^{2/3}\log n\) arrivals, buys from sellers during that phase, sets a price to the sample median, and then buys from sellers below that price and sells to eligible buyers above it whenever it has stock. The theorem covers the welfare objective, not the paper’s separate gain-from-trade result.
Here is the mirror I would put to a prover: the \(\delta\)-resolved continuous welfare secretary problem. An instance is a finite set of types \(T\), where each type is a buyer or seller with a rational valuation, and a rational mass distribution \(\mu\) over \(T\). Total buyer mass and seller mass are each \(1/2\), and every positive type mass is a multiple of \(\delta=1/(2n)\). Thus the society has total mass \(1\), arriving as \(2n\) equal packets of mass \(\delta\). Each seller packet brings \(\delta\) units of the item; each buyer packet demands \(\delta\). The packets arrive in a uniformly random order. A posted-price policy sees each packet’s role and value on arrival, bases its offer on the history and \(n\), and can trade only when the packet accepts and inventory permits. Its welfare is the mass-weighted value of the agents holding the items at the end. The offline benchmark assigns the item mass to the highest-valued population mass \(1/2\).
The policy is not told \(\mu\), just as the paper’s algorithm is not told the traders’ valuations. The distribution describes the adversarial instance against which the policy is evaluated. The question is: does there exist one online policy \(A_\delta\), independent of \(\mu\), such that for every such society
\[
\mathbb E[\mathcal W_{A_\delta}(\mu)]
\;\ge\;
\left(1-\widetilde O(\delta^{1/3})\right)\mathrm{OPT}(\mu)
\]
as \(\delta\) tends to zero? A solution is a policy and a proof of the guarantee. Since \(n=1/(2\delta)\), Theorem 1 supplies this result directly after normalizing welfare by population size. I expect this mirror to be tractable; in this case the paper’s result already answers the central guarantee question.
The regime is a large, randomly interleaved market with many traders but relatively few exact buyer and seller valuation types—for example, recurring cohorts with standardized reservation values. Here the type is exactly role plus valuation, and mass is the fraction of traders in that cohort. The number of agents grows as \(1/\delta\), while the support size \(\tau\) can remain small. This preserves the unit-demand trade, inventory constraint, random-order information, and offline benchmark, so it is recognizably the paper’s problem rather than an easier allocation problem.
My weakest point is also the boundary of this case: the guarantee is for a society with arrival resolution \(\delta\). At resolution zero, a random permutation of a nonatomic population has no automatic secretary-process interpretation, and its limiting fluctuations may disappear. So I would not claim Theorem 1 establishes a nontrivial, resolution-free online continuum model. The question it does support is the high-multiplicity family and its welfare guarantee, with the rate of convergence—and whether an adaptive policy can improve the exponent, as the paper itself suggests—as natural follow-up questions.
Theorem 1 is a real algorithmic anchor, so I can’t argue that the paper has no computational result to mirror. My best case against it is that the proposed mirror either retains the paper’s finite random process almost exactly, or loses the feature that makes the theorem interesting.
At resolution \(\delta=1/(2n)\), each mass packet is an individual trader, and the society is still a uniformly random permutation of \(2n\) packets. Setting \(n=1/(2\delta)\) transfers the theorem’s guarantee directly: \(1-\widetilde O(\delta^{1/3})\). That is a sensible high-multiplicity formulation, but it adds no continuous optimization question. Improving the rate would be worthwhile online-algorithm work; it is also the adaptive-scheme question the paper itself already raises.
A genuinely nonatomic version has a different problem. A uniform random permutation of a continuum of agents has no canonical meaning. In the natural fluid limit of the finite process, the mass of every type observed by time \(t\) is exactly \(t\mu_t\). The random fluctuations that drive the finite-\(n\) analysis vanish after normalization, and any positive-length sample reveals the type proportions exactly. The limit therefore discards the sampling uncertainty behind the theorem; its \(1-\widetilde O(\delta^{1/3})\) rate is a finite-resolution effect. Preserving nonvanishing randomness would require an additional stochastic arrival model or fluctuation scaling. That may yield a worthwhile control problem, but it would no longer be the continuum limit of the paper’s fixed society in random order, and it does not bring the continuous optimization tools ChoCo is targeting into play.
That is a case against the *incremental value* of this mirror, not against its plausibility. A large market with repeated buyer and seller reservation values is a convincing high-multiplicity regime; role and valuation give a sensible type, and the objective does not depend on personal identity. Under ChoCo’s stated standard, I cannot honestly conclude that no worthwhile mirror exists. The negative case is weak precisely where the proponent’s is strongest: the \(\delta\)-resolved family is a well-posed mirror, even if its direct guarantee is already implicit in Theorem 1.
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.