CS Paper Radar

On Deterministic Optimal Mechanisms in a Two-Item Setting for Distributions with Nondecreasing Density

Thirumulanathan D

cs.GT econ.TH ·submitted 2026-08-23 11:31 UTC · v1
published

Abstract

Consider the problem of designing a revenue-optimal auction mechanism when two heterogeneous items are sold to a single buyer having independent valuations over the items. The distributions of the buyer's valuation for the items are assumed to have densities that are positive, nondecreasing, and continuously differentiable on their support sets $[c_i,c_i+b_i]$ in the positive axis. I prove that the optimal mechanism is deterministic if at least one of the minimum valuations (i.e., either $c_1$ or $c_2$) is sufficiently high. I provide a method to calculate the threshold of $(c_1,c_2)$ beyond which the optimal mechanism is deterministic. I also provide a sufficient condition on the distributions of buyer's valuations for which the individual sale mechanism is optimal. I show that when $c_1$ is low and $c_2$ is high, it is optimal for the seller to sell item $2$ at the minimum valuation $c_2$, thus effectively reducing the problem to finding the optimal mechanism in the one-dimensional setting only for item $1$. I conjecture with promising preliminary results that this result can be extended to the three-item setting. Specifically, I conjecture that when $c_1$ and $c_2$ are low but $c_3$ is high, it is optimal for the seller to sell item $3$ at the minimum valuation $c_3$, thus effectively reducing the problem to finding the optimal mechanism in the two-dimensional setting for items $1$ and $2$.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Multi-Item Auctions with I.I.D. Values

cs.GT ·2026-10-08 ·Boyu Liu, Zhengyang Liu, Zihe Wang
similarity 0.67
Abstract · 51 pages, 1 table

We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.

0.21

On the Power of Determinism in Multi-Item Auctions

cs.GT cs.DM ·2026-09-28 ·Yiannis Giannakopoulos, Johannes Hahn
theory similarity 0.66
Abstract · Improved the upper bound on REV/max{SREV,BREV} from 3 to 2.5 for independent items, and added a lower bound of 2.19. For iid items, improved…

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max\{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots,1\}$, for any discretization parameter $K$. Taking $K\to\infty$ yields the tight ratio $1+W(1/e)\approx1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.

0.41

The Exact Approximation Ratio of the Optimal Fixed-Price Mechanism in Bilateral Trade

cs.DS ·2026-08-20 ·Tao Jiang, Minbo Gao, Shaowei Cai
similarity 0.64
Abstract

In bilateral trade, a seller owns an item that a buyer may value more, and their values are drawn independently from known distributions. A fixed-price mechanism posts a single price and trades exactly when both agents accept it. How much of the first-best expected welfare can the optimal fixed price guarantee? A sequence of analytic and computer-assisted results narrowed the worst-case ratio to the interval $[0.7292,0.73805]$, but its exact value remained open. We determine this ratio exactly: it equals $0.7380243357\ldots$, given in closed form through the unique root of an explicit one-dimensional equation. The guarantee holds for every pair of independent nonnegative distributions with finite means, including atomic and unbounded ones, and an explicit family of instances shows that no larger constant is possible. The proof reduces the problem, through put and call transforms of the two distributions and a worst-case choice of seller, to a one-dimensional control problem for the buyer. A logarithmic change of variables makes this problem strictly convex, so its first-order conditions certify a global optimum. The optimizer switches exactly once from an interior arc to the boundary and can be integrated in closed form. Realizing it yields a bounded seller and a bounded buyer together with a vanishing buyer atom at a diverging value. The worst case is approached by this family but attained by no instance.

0.32

Two-Sided Screening in Quality-Differentiated Markets

cs.GT ·2026-11-04 ·Yaohao Liu, Mengfan Ma, Mingyu Xiao
similarity 0.63
Abstract

Motivated by digital marketplaces such as Uber and Airbnb, we study how a two-sided platform designs a menu of qualities, consumer prices, and provider wages. Consumers and providers self-select according to their private values and costs, so the platform must design its menu to attract consumers while inducing enough supply to meet their demand. We study this coordination problem over a continuous quality space, requiring supply to cover demand at every quality threshold. We formulate menu design as an optimization over trading distributions, which specify how much trade occurs at or above each quality. Through convexification of the technological cost function, we characterize the profit- and welfare-optimal trading distributions. This characterization shows how production technology alone can reduce menu size without sacrificing optimal profit or welfare, regardless of the type distributions, and determines when optimal menus can be finite. We then show that profit maximization can be highly efficient: under monotone hazard rate conditions on both sides, a profit-optimal menu achieves at least $1/(e-1)$ of optimal social welfare. We next consider the practical setting in which the menu size is restricted to a prescribed number of offers. We establish how the restricted menu approximates the unrestricted optimum in profit. We develop an algorithm that computes a menu within this size limit in polynomial time. The computed menu simultaneously approximates the unrestricted optimal profit and social welfare with additive error.

0.28

Balanced Posted Prices in Stationary Two-Sided Markets

cs.GT ·2026-10-22 ·Ilan Reuven Cohen
benchmark similarity 0.61
Abstract · 30 pages

We study an intermediary that buys nonperishing items from arriving sellers and sells them to arriving buyers, subject to limited storage. Sellers and buyers arrive according to independent Poisson processes. The intermediary pays and charges the same fixed item prices, aiming to maximize long-run gains from trade: buyer value minus seller cost. Our benchmark may choose allocations directly, has unlimited storage, and must purchase each unit before allocating it. Its optimal long-run gain rate equals the value of a linear program of average purchase and allocation rates, with or without knowledge of future arrivals. For buyers whose bundle values are maxima of nonnegative additive valuations (XOS), we compute static common prices that guarantee half of this benchmark for arbitrary finite item capacities, even one storage slot per item, regardless of how ties are resolved without using future arrivals. The prices are computable in polynomial time using demand and supporting-value queries. The construction equalizes itemwise lower bounds on buyer and seller contributions to gains from trade, accounting for procurement costs. We call this contribution balance. As a single-item foundation, we also equalize the rates of purchases and sales selected by the price, before checking inventory availability. We call this rate balance. For capacity $C$, it yields the tight guarantee $C/(C+1)$. The two principles parallel proofs of the classical prophet inequality based on half the expected benchmark and on a median threshold, adapting these balancing ideas to recurring two-sided markets with limited inventory.

0.13

Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue

cs.DM math.OC ·2026-09-23 ·Weiyuan Li, Paat Rusmevichientong, Huseyin Topaloglu
similarity 0.60
Abstract · 31 pages in main text, 14 pages in appendix, 1 figure

We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to make available and what prices to charge for the available products. The sale probability for a product depends on its price. If we make a sale for a product, then we collect a revenue reflecting the price and consume the capacities of a combination of resources. We work with two types of inter-temporal constraints. In price monotonicity, the prices charged for a product at different time periods have to be monotone. In promotion fatigue, we can discount a product at most once over each time interval of a fixed length. Computing the optimal policy is intractable. We use fluid approximations to construct policies. Traditionally, policies from fluid approximations make randomized decisions at each time period by following an optimal solution to the fluid approximation, but such randomized decisions easily violate price monotonicity or promotion fatigue constraints. We develop policies that sample price paths according to an optimal solution to the fluid approximation, while satisfying the inter-temporal constraints. Letting $c_{\min}$ be the smallest initial capacity of a resource and $L$ be the maximum number of resources used by a product, our policies have a performance guarantee of $\max\Big\{ \frac{1}{8L}, \, \frac{1}{2} - \sqrt{\frac{\log c_{\min}}{2 \,c_{\min}}} - \frac{L}{c_{\min}}\Big\}$. Thus, under large resource capacities, our policies are guaranteed to obtain at least half of the optimal total expected revenue. The latter performance guarantee is tight in the sense that no policy can, in general, obtain more than half of the optimal objective value of the fluid approximation even under large resource capacities. We unify our approach to open the path for extensions to other inter-temporal price constraints.

0.31

Unit-Demand Pricing for Min-Buying Customers

cs.GT econ.TH ·2026-10-12 ·Titing Cui, Michael Hamilton, Jourdain Lamperski, Kasra Tari
similarity 0.59
Abstract

We study the unit-demand pricing problem under \textit{min-buying} behavior, where customers purchase the lowest-priced item that yields non-negative utility. In contrast to the quasi-linear model, we show that uniform pricing becomes substantially more effective under min-buying. First, we study symmetric environments. We show that for min-buying customers with independent and identically distributed valuations, a uniform price across items is optimal. We then extend this optimality result to all valuations drawn from exchangeable and affiliated distributions. However, uniform pricing is not optimal in all symmetric environments: for min-buying customers we construct an exchangeable and non-affiliated valuation distribution for which the gap between uniform pricing and optimal item pricing is logarithmic in the number of items. This gap is tight and matches the worst-case gap in the quasi-linear setting. Next, we consider asymmetric environments in which valuations are independent but not identically distributed. When these valuations are regular and customers are min-buying, we show that a uniform price guarantees approximately 69.86\% of the optimal item-pricing revenue and this is tight. Overall, our results highlight that the value of non-uniform pricing substantially diminishes, and often disappears entirely, under more conservative demand models in which customers engage in satisficing behaviors such as min-buying.

0.16

Sharp Second-Best Welfare in Bilateral and Matching Markets

cs.GT ·2026-09-29 ·Zhengyang Liu, Ying Qin, Zihe Wang
similarity 0.59
Abstract

How much social welfare must a market lose because values are private? We determine the sharp ratio of second-best to first-best welfare under independent nonnegative types, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. The ratio is approximately $0.8882516903$ for arbitrary priors and $0.9113893681$ when buyers have monotone hazard rates and sellers are unrestricted. The arbitrary-prior guarantee holds for every downward-closed family of feasible matchings; the MHR guarantee holds when every matching of a compatibility graph is feasible. Both constants are \revise{attained}{sharp} already in bilateral trade. The proof keeps the sellers' initial endowment inside the budget Lagrangian. For arbitrary priors, a common threshold decomposition reduces the problem to three-parameter power-law distributions. For monotone hazards, common transformations of buyer and seller scores reduce it to shifted capped exponential buyers; a typewise allocation certificate and an explicit worst-case seller satisfy the same boundary equation. The bilateral-to-matching framework, with a welfare endowment charge and an MHR-preserving packing argument, transfers these affine inequalities without loss. We give exact variational characterizations of both constants and reproducible interval certificates for their numerical evaluation. Unrestricted signed transfers also permit pointwise strong budget balance.

0.14