Answer: Yes. Universal constants exist, and \(k=1\) suffices.
Theorem 1 — class: algorithmic
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 society is specified by its support: \(\tau\) role–valuation types with positive binary-rational masses \(\mu_i\) and nonnegative binary-rational valuations \(v_i\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total encoding length. State running times in \(\tau,L,n\); there is no candidate parameter \(m\).
For \(n\geq1\), let \(\delta=1/(2n)\). Buyer and seller masses each total \(1/2\), and each \(\mu_i\) is an integer multiple of \(\delta\). Replace each type by \(\mu_i/\delta\) packets and present these packets in a uniformly random permutation.
Each seller packet initially owns item mass \(\delta\); buyers initially own none, and the intermediary starts with zero inventory. Each packet can trade its entire mass once, at its arrival, or leave without trading.
The policy knows \(n\), but not the support or masses. It observes the arriving role, then declines or posts a nonnegative price using only previous observations and private randomness; the current valuation is revealed after this decision, whether or not trade occurs.
A seller accepts price \(p\) when \(v_i\leq p\); a buyer accepts when \(v_i\geq p\). Accepted offers execute, except that sales require inventory at least \(\delta\). Inventory can be stored indefinitely; there is no monetary budget or budget-balance constraint. Equal valuations are allowed.
Realized welfare \(W_A\) is the sum of valuation times final item mass held by sellers and buyers; leftover intermediary inventory contributes zero. Let \(\mathrm{OPT}(\mu)=\max\{\sum_i v_i x_i:0\leq x_i\leq\mu_i,\ \sum_i x_i=1/2\}\), without arrival-order restrictions.
Does there exist a family of policies \(A_\delta\), independent of \(\mu\), and universal constants \(C>0\), \(k\geq0\), and \(\delta_0>0\), such that every admissible society with \(\delta\leq\delta_0\) satisfies \(\mathbb E[W_{A_\delta}(\mu)]\geq[1-C\delta^{1/3}(\log(1/\delta))^k]\mathrm{OPT}(\mu)\), with expectation over arrival order and policy randomness?
For discrete societies with equally many buyers and sellers, a posted-price welfare guarantee of \(1-\widetilde O(n^{-1/3})\) is established; the formal model assumes distinct valuations for convenience. [Verified source](https://arxiv.org/pdf/1812.11149v2).
No separate theorem for the stated mass-support model was verified.
Yes. There is a family of policies independent of the support and masses satisfying the requested guarantee with \(k=1\).
The proof below treats repeated and zero valuations explicitly. The cited [discrete-market paper](https://arxiv.org/html/1812.11149v2) establishes the corresponding asymptotic guarantee under distinct valuations; the argument here proves the guarantee directly for the stated model.
Label the \(2n\) packets individually, even when several packets have the same type. Write their valuations as \(v_a\). There are exactly \(n\) seller packets and \(n\) buyer packets.
For the proof, measure item quantities in packets. Let \(P\) be the sum of the \(n\) largest packet valuations. Then
\(P=\mathrm{OPT}(\mu)/\delta.\)
Indeed, the mass allocation problem is equivalent to choosing numbers \(y_a\) satisfying \(0\leq y_a\leq1\) and \(\sum_a y_a=n\), maximizing \(\delta\sum_a v_a y_a\). Sorting valuations decreasingly, the maximum is attained by allocating to the first \(n\) packets. To verify optimality, use the \(n\)-th largest valuation \(c\):
\(\sum_a v_a y_a=nc+\sum_a(v_a-c)y_a\leq nc+\sum_{a:\,v_a>c}(v_a-c)=P.\)
The proposed allocation attains this bound, including when there are ties.
Likewise, if \(Z\) denotes a policy’s realized welfare in packet units, then \(W_A=\delta Z\). Thus it suffices to prove an approximation to \(P\).
All parameters below depend only on \(n\). Set
\(r=\lceil n^{2/3}\rceil,\qquad h=\lceil\log_2(2n)\rceil,\qquad K=1024rh,\qquad D=2^{8h}.\)
We analyze sufficiently large \(n\), so that \(K\leq n/2\). For smaller \(n\), define the policy arbitrarily, for example by declining every trade.
At each arrival, independently draw an integer \(U\), uniformly from \(\{1,\ldots,D\}\), before posting a price. After the valuation \(v\) is revealed, associate the virtual valuation
\(w=v\left(1+\frac{U}{nD}\right).\)
Consequently,
\(v\leq w\leq(1+1/n)v.\)
The policy has two phases.
At each subsequent arrival, offer the price
\(p=\dfrac{q}{1+U/(nD)}.\)
Execute accepted trades subject to the inventory requirement.
This is an admissible policy. Every price is nonnegative and rational, and uses only previous observations, the current role, and private randomness. In the trading phase, acceptance is exactly equivalent to
\(w\leq q\quad\text{for sellers},\qquad w\geq q\quad\text{for buyers}.\)
In particular, the policy never needs to observe the current valuation before choosing its price.
We establish the probability estimates used in the proof.
Suppose \(j\) entries are sampled without replacement from a fixed population whose entries lie in an interval of length \(b\). If \(X\) is their sum, then
\(\Pr[X-\mathbb EX\leq-u]\leq\exp\!\left(-\dfrac{u^2}{2jb^2}\right),\)
and the same bound holds for the upper tail.
To justify this, expose the sampled entries sequentially and use the Doob martingale for their eventual sum. After the \(i\)-th exposure, its increment is
\(\dfrac{N-j}{N-i}\left(X_i-\overline X_{i-1}\right),\)
where \(N\) is the population size and \(\overline X_{i-1}\) is the mean of the remaining population before that exposure. Its absolute value is at most \(b\). Azuma’s inequality gives the stated bounds. If \(j=N\), the sum is deterministic.
We may equivalently assign all packets their independent marks \(U_a\) before drawing the arrival permutation.
For two packets with positive valuations, condition on the mark of one. The equation equating their virtual valuations has at most one possible mark for the other. Hence its probability is at most \(1/D\).
By a union bound, the probability of any positive virtual tie is at most
\(\binom{2n}{2}/D\leq2n^{-6}.\)
Conditional on the marks, order the packets by increasing virtual valuation, breaking zero ties by fixed packet labels. These labels are used only in the analysis.
Let
\(t=4\sqrt{K\log n}.\)
For each prefix of \(H\) packets in the fixed rank order, let \(h_H\) be its number of sampled packets. The sampling bound and a union bound over all \(2n\) prefixes give
\(\Pr\!\left[\exists H:\left|h_H-\frac{KH}{2n}\right|>t\right]\leq4n^{-7}.\)
Call its complement the rank event.
Let \(S_0,B_0\) be the sampled seller and buyer counts. Their expectations are \(K/2\), so
\(\Pr[S_0<K/3\text{ or }B_0<K/3]\leq2e^{-K/72}.\)
Let \(e\) be the number of sampled sellers from whom the policy does not buy. Each such seller is a strict record in the sequence of observed seller valuations. For the \(j\)-th seller, the probability of being a strict record is at most \(1/j\): among the first \(j\) sellers, a unique maximum is equally likely to occupy any position. This argument allows repeated valuations.
Therefore, writing \(H_n=\sum_{j=1}^n1/j\),
\(\mathbb Ee\leq H_n,\qquad \Pr[e>r]\leq H_n/r.\)
The inventory at the end of sampling is exactly \(R=S_0-e\).
First suppose \(q>0\). Work on the rank event, with \(S_0,B_0\geq K/3\), \(e\leq r\), and no positive virtual ties.
Let
\(H=\#\{a:w_a<q\},\qquad h_q=\#\{\text{sampled }a:w_a<q\}.\)
We claim that \(H\geq n-r\).
If \(q=q_{\mathrm{med}}>0\), distinctness gives \(h_q=K/2-1\). The rank event implies
\(H\geq n-\frac{2n(t+1)}K\geq n-r.\)
If \(q=M/(2n^2)>0\), the sample median is zero, so at least \(K/2\) sampled packets have zero valuation. Applying the rank event to the prefix consisting of all zero packets shows that their total number is at least
\(n-\frac{2nt}K\geq n-r.\)
All these packets lie strictly below \(q\), proving the claim.
The inequalities used here hold for sufficiently large \(n\), because
\(\frac{2nt}K=8n\sqrt{\frac{\log n}{K}}\leq\frac{n^{2/3}}4.\)
Now let \(S,B\) be the numbers of eligible sellers and buyers in the remaining sequence. If every eligible buyer were served, the final inventory would be \(F=R+S-B\).
Let \(E_S\) count remaining sellers whose virtual valuation equals \(q\). Counting packets strictly below \(q\) gives
\(S-B=H-h_q-n+B_0+E_S.\)
Consequently,
\(F=H-n+K-h_q-e+E_S\geq H-n+K-h_q-e.\)
Using the rank event and \(H\geq n-r\),
\(F\geq(H-n)\left(1-\frac K{2n}\right)+\frac K2-t-e\geq\frac K2-t-2r.\)
For sufficiently large \(n\), this is at least \(K/4\). Also,
\(R=S_0-e\geq K/3-r\geq K/4.\)
Thus both endpoints of the inventory path that would result from executing every eligible trade are at least \(K/4\).
If \(M=0\), all sampled packets have zero valuation. The rank event implies that the number of positive packets is at most
\(\frac{2nt}K\leq r.\)
The threshold is \(q=0\). All remaining buyers are eligible, while exactly the zero-valued remaining sellers are eligible. Every sampled seller was purchased, so \(R=S_0\). If \(P_S\) is the total number of positive sellers, the hypothetical final inventory is
\(F=B_0-P_S\geq K/3-r\geq K/4.\)
The initial inventory is also at least \(K/4\).
Condition on all marks and the ordered sample. The remaining packets are uniformly permuted.
Give each remaining packet increment \(+1\) if it is an eligible seller, \(-1\) if it is an eligible buyer, and zero otherwise. The expected hypothetical inventory after any number of remaining arrivals is the linear interpolation between \(R\) and \(F\), hence is at least \(K/4\).
The increments lie in an interval of length two. The sampling bound, followed by a union bound over at most \(2n\) remaining positions, shows that the probability the hypothetical inventory ever becomes negative is at most
\(2n\exp\!\left(-\frac{K^2}{256n}\right).\)
If this path never becomes negative, every eligible buyer is served. Indeed, at a buyer step the hypothetical inventory decreases by one; its nonnegativity implies that the preceding inventory was at least one. Induction therefore identifies the hypothetical path with the actual inventory path.
Combining the preceding estimates, all these conclusions hold outside an event of probability at most
\(\beta_n=2n^{-6}+4n^{-7}+2e^{-K/72}+\frac{H_n}{r}+2n\exp\!\left(-\frac{K^2}{256n}\right).\)
In particular,
\(\beta_n=O(n^{-2/3}\log n).\)
Let \(\widetilde P\) be the sum of the \(n\) largest virtual valuations. Let \(T\) be a fixed set attaining this sum, with deterministic tie-breaking, and define
\(Q=\sum_{a\in T:\,a\text{ sampled}}w_a.\)
Let \(\widetilde Z\) be realized welfare in virtual packet units. Pointwise,
\(P\leq\widetilde P\leq(1+1/n)P,\qquad Z\geq\widetilde Z/(1+1/n).\)
We now bound \(\widetilde Z\) on the successful event.
Here \(h_q=K/2-1\). The rank event gives
\(H+1\leq n+\frac{2nt}K+1\leq n+r.\)
Therefore every one of the top \(n-r\) virtual-valued packets outside the sample lies strictly above \(q\). Sellers among them retain their items, and buyers among them receive items by the inventory result.
For nonnegative numbers, the sum of the largest \(n-r\) is at least \((1-r/n)\) times the sum of the largest \(n\). Thus
\(\widetilde Z\geq(1-r/n)\widetilde P-Q.\)
Here \(q=M/(2n^2)\). Every packet outside the sample with virtual valuation above \(q\) ends with an item if it belongs to \(T\): sellers retain theirs and buyers are served.
The total virtual value of packets in \(T\) with valuation at most \(q\) is at most
\(nq=M/(2n)\leq P/(2n),\)
because every actual packet valuation, including \(M\), is at most \(P\). Hence
\(\widetilde Z\geq\widetilde P-Q-P/(2n).\)
There are at most \(r<n\) positive packets. All positive sellers retain their items, and all positive buyers receive items. Therefore
\(\widetilde Z=\widetilde P.\)
All three cases imply the common bound
\(\widetilde Z\geq(1-r/n)\widetilde P-Q-P/n.\)
Conditional on all marks, \(T\) is fixed and the sample is a uniformly random \(K\)-element subset. Therefore,
\(\mathbb E[Q\mid(U_a)_a]=\frac K{2n}\widetilde P.\)
On failure, welfare remains nonnegative. Since \(\widetilde P\leq(1+1/n)P\), the preceding successful-event bound yields
\(\mathbb E\widetilde Z\geq\left(1-\frac rn-\frac K{2n}\right)\mathbb E\widetilde P-\frac Pn-(1+1/n)P\beta_n.\)
For sufficiently large \(n\), the coefficient of \(\mathbb E\widetilde P\) is positive. Using \(\mathbb E\widetilde P\geq P\) and dividing by \(1+1/n\), we obtain
\(\mathbb EZ\geq\left(1-\frac rn-\frac K{2n}-\frac2n-\beta_n\right)P.\)
Now \(r/n=O(n^{-1/3})\), \(K/n=O(n^{-1/3}\log n)\), and \(\beta_n=O(n^{-2/3}\log n)\). Thus, for a universal constant \(C_1\),
\(\mathbb EZ\geq[1-C_1n^{-1/3}\log n]P.\)
Multiplying by \(\delta\) and using \(n=1/(2\delta)\) proves that universal constants \(C,\delta_0>0\) exist such that
\(\mathbb E[W_{A_\delta}(\mu)]\geq[1-C\delta^{1/3}\log(1/\delta)]\mathrm{OPT}(\mu)\)
for every admissible society with \(\delta\leq\delta_0\). When the optimum is zero, the inequality follows directly from nonnegative welfare.
The policy uses \(8h=O(\log n)\) random bits per packet. Virtual valuations and posted prices have encoding length \(O(L+\log n)\).
Using elementary exact rational arithmetic and comparison sorting, processing the stream takes
\(O\!\left(n\log n\,(L+\log n)^2\right)\)
bit operations and stores
\(O\!\left(K(L+\log n)\right)\)
bits. It does not need the support as input.
If a supplied support representation is used to generate the packet stream, forming its multiplicities costs \(O(\tau(L+\log n)^2)\), and explicit packet generation costs \(O(n(L+\log n))\). The dependence on \(n\) is unavoidable for explicitly processing \(2n\) arrivals; it need not be polynomial in the compressed support encoding length alone.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes the requested guarantee with \(k=1\). I found no major or minor mathematical issues requiring repair. The construction handles repeated valuations, zero valuations, inclusive acceptance, and the inventory constraint.
The mass assumptions give exactly \(n\) seller packets and \(n\) buyer packets. Labeling identical packets individually is valid for analyzing their uniformly random permutation.
The fractional packet allocation formulation is equivalent to the original allocation problem: allocation within each type can be distributed among its packets, and packet allocations can be aggregated by type.
The displayed inequality using the \(n\)-th largest valuation \(c\) correctly proves
\(P=\mathrm{OPT}(\mu)/\delta\). Terms with \(v_a<c\) are nonpositive, and terms with \(v_a>c\) are bounded using \(y_a\leq1\). Ties at \(c\) cause no difficulty. The scaling \(W_A=\delta Z\) is also correct.
All parameters depend only on \(n\). The eventual restriction \(K\leq n/2\) is legitimate because \(K=O(n^{2/3}\log n)\). Arbitrary policies for the finitely many excluded values of \(n\) do not affect the requested existence of \(\delta_0\).
During sampling, seller prices use only previously revealed seller valuations. During trading, \(q\) is determined by the sample, and the current mark \(U\) is private randomness drawn before the decision. No price uses the current valuation.
Because \(1+U/(nD)>0\), the acceptance equivalences
\(v\leq p\iff w\leq q\) and \(v\geq p\iff w\geq q\) hold, including equality. All prices are nonnegative rational numbers.
Preassigning independent marks to labeled packets is distributionally equivalent to generating independent marks at their arrivals. The policy does not need access to the analytical labels.
The sampling-without-replacement bound is justified by the stated Doob martingale. For \(j<N\), its increment coefficient satisfies
\(0\leq(N-j)/(N-i)\leq1\), so the increment magnitude is at most \(b\). Azuma’s inequality gives the displayed tails. The deterministic case \(j=N\) is explicitly covered.
Each positive virtual collision has probability at most \(1/D\): after fixing one mark, the equality equation has at most one solution for the other mark. Since \(D\geq(2n)^8\), the stated bound \(2n^{-6}\) is valid.
For sampled ranks, each fixed prefix has a binary indicator population. With \(t=4\sqrt{K\log n}\), its two-sided failure probability is at most \(2n^{-8}\). The union bound over \(2n\) prefixes therefore gives \(4n^{-7}\).
For sampled roles, deviation below \(K/3\) is a deviation of \(K/6\) from the mean. Substitution into the sampling bound gives \(e^{-K/72}\) for each role, as claimed.
An unpurchased sampled seller must have valuation strictly exceeding all previously observed seller valuations. For the \(j\)-th seller, this requires a unique maximum among the first \(j\) sellers to occupy position \(j\), with probability at most \(1/j\). Repeated maxima cannot produce a strict record. Thus the expectation and Markov bound for \(e\) are valid, and \(R=S_0-e\) is exact.
Here \(K\) is even. If the sample median is positive and positive virtual ties are absent, exactly \(K/2-1\) sample packets lie strictly below it. Zero ties do not affect this count.
Both arguments establishing \(H\geq n-r\) are valid. In the fallback-threshold case, all zero packets lie strictly below the positive threshold, so the zero-prefix concentration bound applies directly.
The numerical estimate
\(2nt/K=8n\sqrt{\log n/K}\leq n^{2/3}/4\)
holds for the stated parameters for sufficiently large \(n\), under the conventional natural-log interpretation of \(\log\). The additional \(2n/K\) term in the median case is also absorbed by \(r\).
The identity
\(S-B=H-h_q-n+B_0+E_S\)
correctly counts remaining sellers below or equal to the threshold and remaining buyers at or above it. In particular, the \(E_S\) term correctly handles inclusive seller acceptance.
The ensuing lower bounds \(F\geq K/4\) and \(R\geq K/4\) follow for sufficiently large \(n\), because \(t=o(K)\) and \(r=o(K)\).
The zero-prefix rank bound correctly implies at most \(r\) positive packets. Every sampled seller is purchased at price zero.
At threshold zero, all remaining buyers accept, while exactly the remaining zero-valued sellers accept. Therefore \(F=B_0-P_S\), and both endpoint reserves are at least \(K/4\).
Conditioning on all marks and the ordered sample leaves the remaining labeled packets uniformly permuted. The eligibility increments are then fixed population entries in \(\{-1,0,1\}\).
Their expected partial sums interpolate between the initial and final reserves. Applying the sampling bound with interval length two and deviation \(K/4\), followed by the position union bound, gives the stated probability
\(2n\exp(-K^2/(256n))\).
Nonnegativity of the hypothetical inventory path is sufficient: at an eligible buyer step, the preceding inventory must be at least one. The stated induction consequently establishes that every eligible remaining buyer is served.
The combined failure bound \(\beta_n\) is valid, and its asserted asymptotic order is correct.
The comparisons
\(P\leq\widetilde P\leq(1+1/n)P\) and
\(Z\geq\widetilde Z/(1+1/n)\)
follow directly from the pointwise valuation bounds and nonnegative holdings.
In the positive-median case, \(H+1\leq n+r\) implies that the largest \(n-r\) virtual valuations lie strictly above \(q\). Outside the sample, their sellers retain their items and their buyers are served. The largest-\(n-r\) sum bound is valid for nonnegative valuations. Subtracting \(Q\) accounts for sampled members of this set.
In the positive fallback-threshold case, members of \(T\) whose virtual valuations are at most \(q\) contribute at most \(nq=M/(2n)\). The inequality \(M\leq P\) holds because valuations are nonnegative and \(n\geq1\).
In the all-zero-sample case, all positive packets are outside the sample and number fewer than \(n\). Every positive seller retains its item and every positive buyer is served, giving \(\widetilde Z=\widetilde P\).
The common successful-event inequality follows from these three cases.
Conditional on the marks, \(T\) is fixed and each packet has sampling probability \(K/(2n)\). Thus the formula for \(\mathbb E[Q\mid(U_a)_a]\) is correct.
The failure-event deduction does not assume independence between success and \(Q\) or \(\widetilde P\). Nonnegative welfare permits discarding failure outcomes; \(Q\geq0\) permits subtracting its unconditional expectation; and \(\widetilde P\leq(1+1/n)P\) bounds the lost successful-event term.
The subsequent division by \(1+1/n\) and relaxation to the displayed bound for \(\mathbb EZ\) are valid. The asymptotic substitutions yield the claimed universal constant. Using \(n=1/(2\delta)\) gives the requested guarantee uniformly over admissible societies. The zero-optimum case is correctly covered separately.
The arithmetic and storage bounds are consistent with the construction. Exact rational comparisons and operations have the stated quadratic bit-cost upper bound, and median computation is covered by comparison sorting.
The running times are expressed in \(n,L,\tau\), with no candidate parameter. The distinction between explicit stream processing and computation polynomial in compressed support length is correctly stated.
The background claim about the discrete result and its distinct-valuation convention agrees with the [cited paper](https://arxiv.org/html/1812.11149v2). The submitted proof establishes its guarantee directly and does not require transferring that theorem to repeated valuations.
No additional clarification or repair is necessary. The established result is an approximation guarantee, so the requested metadata category is “other.”
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.