Balanced Posted Prices in Stationary Two-Sided Markets

1 Introduction

• The target is long-run buyer value minus acquisition costs under finite storage, compared with a flow benchmark that optimizes average purchases and allocations without inventory limits.The benchmark must purchase each unit before allocating it; the flow relaxation has the same optimal value as unlimited-storage online and clairvoyant policies.Source: §1 · p. 2

1.1 Our contributions

• 1/2 of the unlimited-inventory offline benchmark is guaranteed by polynomial-time static common prices for XOS buyers, arbitrary finite capacities, and any nonanticipatory tie-breaking.With direct allocation, sampling an optimal flow guarantees Cmin/(Cmin + 1) of the benchmark, compared with 1/2 for common prices.Source: §1.1 · p. 4
• Contribution balance sets buyer-utility and seller-surplus lower bounds equal at half the item's flow contribution, accounting for acquisition costs.The bounds are Wj − xjpj and xjpj − Aj; because each item is either in stock or has free capacity, at least one applies in every inventory state.Source: §1 · p. 3, §1.1 · p. 4
• C/(C + 1) is the tight guarantee for a single item under a rate-balanced posted price.The result holds for every capacity C ≥1, with prescribed randomization for indifferent sellers or buyers.Source: §1.1 · p. 4
• A multi-item rate-balanced construction exists for XOS buyers, using a fixed point to align prices with inventory probabilities despite coupled bundle choices.It gives each used item empty-stock and full-capacity probabilities of at least one half, but establishes existence rather than an efficient construction.Source: §1.1 · p. 5

1.2 Related work

• The supporting-clause XOS pricing approach [21] is extended to recurring procurement with a seller-surplus certificate, while stationary-prophet work [26] shares the C/(C + 1) capacity barrier.The paper also distinguishes its nonperishing two-sided welfare setting from prior trading models and strategic markets.Source: §1.2 · pp. 5–6

1.3 Organization

• The paper proceeds from single-item rate balance to both principles for XOS markets, then compares them and discusses limitations.Flow relaxations, the allocation baseline, and technical details appear in appendices.Source: §1.3 · p. 6

2.1 Model and unlimited-inventory offline benchmark

• The model has one item, finite capacity C, and independent Poisson seller and buyer arrivals; purchases require free capacity and sales require available stock.Source: §2.1 · p. 6
• The flow relaxation maximizes average gains from feasible seller-buyer trade rates subject to type supply and demand, and its value upper-bounds the unlimited-inventory offline benchmark.The benchmark may choose allocations with full arrival-sequence knowledge and unlimited storage, but must acquire each unit before allocating it.Source: §2.1 · pp. 6–7

2.2 A rate-balanced posted price

• A posted price accepts strict types on the appropriate side and uses prescribed randomization for indifferent sellers or buyers to realize the common rate.The potential intensities count price-eligible arrivals before checking whether inventory is full or empty.Source: §2.2 · pp. 7–8
• Rate balance sets potential purchase and sale intensities equal before inventory checks, making all C + 1 inventory levels equally likely in steady state.Consequently, buyers find stock and sellers find free capacity with probability C/(C + 1).Source: §2.2 · p. 8
• For every capacity C, a rate-balanced posted price guarantees C/(C+1) of the unlimited-inventory offline benchmark, and no online policy can guarantee a larger ratio.The factor is tight for each C.Source: §2.2 · pp. 8–9

3.1 Model, policy, and flow benchmark

• The unlimited-inventory offline benchmark equals the average-flow LP value, which upper-bounds every finite-capacity offline policy.An unrestricted online allocation policy can approach the LP value by imposing increasingly large finite capacities.Source: §3.1 · p. 11

3.2 The utility-surplus decomposition

• The utility-surplus decomposition expresses long-run gain as buyer utility plus seller surplus, without requiring independent item inventories.The decomposition applies to every nonnegative price vector in steady state.Source: §3.2 · p. 12

3.3 Two routes to a one-half guarantee

• A multi-item rate-balanced price vector and fixed randomized tie-breaking rule yield a stationary inventory process with half the flow benchmark as a gain guarantee.The theorem establishes existence for XOS buyers and arbitrary finite capacities; a polynomial-time construction remains open in this subsection.Source: §3.3 · p. 14
• Contribution-balanced prices guarantee at least half of the unlimited-storage offline benchmark for arbitrary finite capacities, under any admissible nonanticipatory tie-breaking rule.The proof balances certified buyer and seller contributions itemwise and does not require a stationary inventory distribution.Source: §3.3 · p. 14

3.4 Allocation baseline and benchmark equality

• With minimum capacity B, an unrestricted online allocation policy achieves at least B/(B + 1) of the LP value, implying equality between the unlimited-inventory online and offline benchmarks and the LP.This baseline directly chooses allocated bundles and does not establish an implementation using common posted prices.Source: §3.4 · pp. 15–16

3.5 Polynomial-time computation

• With rational rates and seller costs and polynomial-time exact demand and XOS oracles, an optimal flow and prices are computable in polynomial time, with at most d positive y and z variables.Here d = |K| + m + P_j |R_j|; each arriving buyer’s choice under the prices uses a demand query.Source: §3.5 · p. 16
• Establishing the required conditions from numerical approximations or samples, or replacing the exact oracles, requires a separate argument.Source: §3.5 · p. 17

4 Balancing principles: comparison and open directions

• For one item with unit capacity, contribution balance weakly dominates rate balance, but neither rule dominates across capacities.The gains in the comparison examples need not be optimal for their instances.Source: §4 · p. 17
• The multi-item one-half guarantees transfer similarly to the clairvoyant benchmark with the same capacity.The unlimited-storage online and clairvoyant values both equal LPm.Source: §4 · pp. 17–18
• The tightness result does not prove that every online policy is limited against the same-capacity offline benchmark.In the stated free-seller, unit-value-buyer example, accepting every feasible trade raises both gains toward one, while rate balance remains at C/(C + 1).Source: §4 · p. 18
• A polynomial-time construction of multi-item rate-balanced prices and their fixed randomized tie-breaking rule remains open.Source: §4 · p. 18
• A capacity-sensitive guarantee for static common prices with XOS buyers choosing utility-maximizing available bundles remains open.Contribution balance applies to arbitrary finite capacities but remains at one-half; the unrestricted LP-sampling baseline guarantees Cmin/(Cmin+1) of LPm.Source: §4 · p. 18
• Strategic reporting, profit objectives, and maximizing gain under a capital budget require further study; profit may require different purchase and sale prices.The paper states that working capital of Σj pjCj funds transfers under its nonnegative common prices and empty initial inventory.Source: §4 · p. 18

Declaration of AI Assistance

• OpenAI tools assisted with literature searches, related-work drafting, exposition, and developing, formalizing, and checking mathematical arguments.The author reviewed and verified the AI-assisted material and cited sources and takes responsibility for the final manuscript.Source: Declaration of AI Assistance · p. 18

A Finite-horizon arguments

• The finite-horizon appendix proves flow upper bounds without assuming componentwise long-run benchmark flows and gives a formal Poisson sampling identity.It also removes the steady-state assumption used to present the main multi-item proof.Source: A Finite-horizon arguments · p. 22

A.1 Single-item type-pair flows

• Pairing each sale with a distinct earlier purchase yields type-pair counts that satisfy arrival constraints and bound expected gain by the flow LP.Deleting costs of unsold purchases and replacing completed-pair gains by their positive parts can only increase gain.Source: §A.1 · p. 22

A.2 Multi-item bundle and acquisition flows

• Matching each allocated item to an earlier purchase yields feasible bundle and acquisition flows, so expected gain per unit time is at most LPm.Removing costs of unmatched purchases can only increase gain.Source: §A.2 · p. 22

A.3 Poisson sampling and arbitrary tie-breaking

• Arbitrary nonanticipatory tie-breaking may prevent a limiting inventory distribution, so the proof uses finite-horizon identities instead.The tie-breaking rule may depend on time or history, but not on future arrivals.Source: §A.3 · p. 23
• For any bounded predictable process, expected Poisson arrivals weighted by that process equal the arrival rate times its expected integrated value.Using stock availability or free capacity as the process gives expected trade opportunities without assuming inventory is independent of past arrivals.Source: §A.3 · p. 23
• The finite-horizon proof bounds buyer utility and seller surplus using expected occupation times, then uses inventory accounting to relate purchases and allocations.The argument does not require the occupation-time fractions to converge.Source: §A.3 · pp. 23–24
• Dividing the combined inequality by the horizon and taking a liminf proves Theorem 3.5.The resulting proof covers admissible nonanticipatory tie-breaking without relying on a stationary distribution.Source: §A.3 · pp. 23–24

Restricting an optimal flow

• Removing items with vj ≤ aj from an optimal flow does not reduce its value, allowing the proof to focus on active items.For items outside the active set, the policy sets price zero and rejects sellers at equality, leaving those inventories empty.Source: B Proof of multi-item rate-balance… · p. 25

A continuous auxiliary inventory process

• Fictitious feasible inventory moves at rate ε make the auxiliary chain irreducible and its stationary distribution continuous in prices.The extra moves vanish in the limit.Source: B Proof of multi-item rate-balance… · p. 25

The fixed point and its limit

• A fixed point makes every active item’s continuous purchase-consumption imbalance zero, and a convergent subsequence yields a stationary randomized policy supported on price-accepted sellers and utility-maximizing buyer choices.Brouwer’s theorem supplies the fixed point; strict utility gaps vanish from the limiting choice probabilities.Source: B Proof of multi-item rate-balance… · p. 26

Convergence from empty inventory

• The limiting stationary distribution is reached from empty inventory because the finite chain has a unique closed recurrent class containing the full active inventory state.The proof first rules out recurrent classes retaining an item with no potential purchase intensity, then establishes positive purchase intensity for every active item.Source: B Proof of multi-item rate-balance… · p. 27

The welfare guarantee

• The policy earns at least half the flow benchmark, with the proof bounding the probabilities of empty and full inventory by one half.The limiting policy’s long-run gain is at least LPm/2.Source: B Proof of multi-item rate-balance… · p. 27

Exact oracle model

• With rational rates and costs, exact demand and XOS queries run in polynomial time in the instance and query encoding lengths.The XOS oracle returns supporting clauses with rational weights of polynomial encoding length.Source: C Exact oracle model and primal recovery · p. 27

Primal recovery

• The dual admits an exact strong separation oracle, enabling polynomial-time optimization and recovery of optimal multipliers using Grötschel, Lovász, and Schrijver’s results [25].Demand and XOS queries either return a violated buyer inequality or certify the buyer inequalities for a type.Source: C Exact oracle model and primal recovery · pp. 27–28
• Reducing recovered z-values itemwise preserves feasibility and objective value, while basic-solution sparsity limits the positive variables needed to compute prices.XOS queries on positive y-variables supply the clauses needed to compute item contributions; prices follow by polynomially many exact arithmetic operations.Source: C Exact oracle model and primal recovery · p. 28

Classical prophet inequalities and posted prices

• The two proof templates draw on the classical prophet inequality, Samuel-Cahn’s median rule, and the balanced-price argument of Kleinberg and Weinberg [27].Related one-sided XOS auction pricing includes Feldman, Gravin, and Lucier [21]; this paper adds recurring procurement from cost-bearing sellers.Source: D Extended related work · p. 28

Stationary prophets, uncertain supply, and dynamic matching

• Unlike stationary-prophet models with exogenous copies, this model requires each nonperishing unit to be purchased from a seller, whose cost enters welfare.The contribution-balanced proof avoids independence assumptions and does not need prescribed stationary availabilities; rate balance jointly controls inventory probabilities.Source: D Extended related work · p. 29

Trading prophets

• Trading-prophet models use finite observed sequences and maximize trader profit, whereas this model has recurring stationary arrivals and maximizes long-run social gain without terminal liquidation.The paper states that these distinctions allow balanced long-run flows to overcome the initial transient.Source: D Extended related work · p. 29

Strategic two-sided combinatorial markets

• Unlike one-shot strategic two-sided mechanisms, agents here take prices as given and sellers create recurring procurement opportunities.The benchmark is a clairvoyant unlimited-inventory benchmark, and each sold unit must have been purchased earlier.Source: D Extended related work · p. 29

Online intermediation

• The guarantees omit strategic reporting, intermediary profit, and operating costs; bounded working capital is addressed separately.Optimizing gains under a given capital budget and strategic recurring two-sided mechanisms remain for further analysis.Source: D Extended related work · pp. 29–30

• The price τ is an actual payment.Source: E Single-item implementation details · p. 30
• For the rate-balanced guarantee, prescribed randomization at indifference is needed to ensure u = v.With a different rule for indifferent sellers and buyers, u = v need not hold.Source: E Single-item implementation details · p. 30
• The contribution-balanced multi-item guarantee holds under any nonanticipatory tie-breaking rule, including rules resolving seller indifference and buyer demand ties.Source: E Single-item implementation details · p. 30

F Single-item rule comparisons

• For one item, matching and bundle-flow relaxations have the same LP value.A feasible matching can be converted to a flow with the same objective, and a feasible flow can be coupled into a matching with at least its objective.Source: F Single-item rule comparisons · p. 30
• At capacity 1, rate balance achieves gain LP1/2 exactly, while contribution balance achieves at least LP1/2 from an optimal flow.Source: F Single-item rule comparisons · p. 30
• The fixed rules induce irreducible finite birth-death chains that converge from empty inventory, so PASTA justifies the long-run stock calculations.For positive potential purchase and sale rates u and v, neighboring inventory probabilities satisfy πn+1/πn = u/v.Source: F Single-item rule comparisons · p. 30
• With capacity 1, seller rate 2, and value-1 buyer rate 1, contribution balance yields gain 2/3 versus 1/2 for rate balance.The LP value is 1; the contribution-balanced example has stationary probabilities (π0, π1) = (1, 2)/3.Source: F Single-item rule comparisons · p. 30
• With capacity 2, seller rate 1, and buyer values 8 and 15 arriving at rate 1 each, rate balance yields gain 10 by accepting only value-15 buyers.The LP value is 15, and the rate-balanced inventory is uniform on {0, 1, 2}.Source: F Single-item rule comparisons · p. 30