Posted Pricing and Competition in Large Markets

José Correa, Vasilis Livanos, Dana Pizarro, Victor Verdugo · 2025

Read Posted Pricing and Competition in Large Markets by José Correa, Vasilis Livanos, Dana Pizarro, Victor Verdugo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18061.txt.

Introduction

Jose Correa, Vasilis Livanos, Dana Pizarro, and Victor Verdugo study posted pricing in large markets. Posted prices are simple and common in online marketplaces. The setting has buyers with independent valuations drawn from one distribution, competing for a single unit, and the market is very large.

In that regime a fixed price guarantee improves well above the classic bound for general markets. For selling many identical units, the optimal fixed price guarantee tends toward one as the unit count grows in a precise form. Auction data test the policies in the large market regime. Competition complexity for the optimal posted price mechanism is constant under the large market assumption. The findings overturn past worst case impossibility results for this setting.

Catalog record

CREATORJosé Correa, Vasilis Livanos, Dana Pizarro, Victor Verdugo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-18061

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Posted Pricing and Competition in Large Markets José Correa, Vasilis Livanos, Dana Pizarro, Victor Verdugo Abstract Posted price mechanisms are prevalent in allocating goods within online marketplaces due to their simplicity and practical efficiency. We explore a fundamental scenario where buyers’ valuations are independent and identically distributed, focusing specifically on the allocation of a single unit. Inspired by the rapid growth and scalability of modern online marketplaces, we investigate optimal performance guarantees under the assumption of a significantly large market. We show a large market benefit when using fixed prices, improving the known guarantee of 1 − 1 / e ≈ 0.632 1-1/e\approx 0.632 to 0.712 0.712 . We then study the case of selling k k identical units, and we prove that the optimal fixed price guarantee approaches 1 − 1 / 2 ​ k ​ π 1-1/\sqrt{2k\pi} , which implies that the large market advantage vanishes as k k grows. We use real-world auction data to test our fixed price policies in the large market regime. Next, under the large market assumption, we show that the competition complexity for the optimal posted price mechanism is constant, and we identify precise scaling factors for the number of bidders that enable it to match benchmark performance. Remarkably, our findings break previously established worst-case impossibility results, underscoring the practical robustness and efficiency of posted pricing in large-scale marketplaces. 1 Introduction Understanding the worst-case welfare obtained by simple pricing mechanisms is a fundamental question in Economics and Computation [ 2 , 3 , 17 , 27 , 37 , 42 , 44 , 18 ] . One of the most fundamental settings corresponds to selling a single item to n buyers with valuations given by independent and identically distributed random variables. In this context, the simplest mechanism is to set a fixed price (a.k.a. anonymous price) for the item. This problem has been extensively studied in the literature, and a result of Ehsani et al. [ 23 ] establishes that the performance of a fixed price policy when facing samples from i.i.d. random variables is at least a fraction 1-1/e of that of the optimal mechanism, and the bound is best possible. Another natural family of mechanisms considered in the literature is the one of posted price mechanisms (PPM) in which the seller offers sequentially a possibly different price to each buyer [ 14 , 15 , 18 , 44 , 56 , 18 , 19 ] . Hill and Kertz studied the i.i.d. setting of this problem [ 40 ] , providing a family of worst possible instances, from which Kertz [ 46 ] proved that no PPM can extract more than a fraction of roughly 0.745 of the optimal mechanism. Later, Correa et al. [ 18 ] proved this value is tight. In this work, we study optimal welfare guarantees of fixed price policies in the i.i.d. setting under an additional large market assumption, relevant to most modern online marketplaces. The essential difference with the classic setting is that, rather than considering the (classic) worst distribution for each possible market size n , we fix the distribution and then take n growing large. Furthermore, we also explore the interplay between the market size and the optimal dynamic pricing policy through the competition complexity measure, exhibiting fundamental differences with respect to the classic setting. 1.1 Our Results and Contribution In what follows, we detail our contribution on tight guarantees for to the design fixed price policies in large markets and the competition complexity of the optimal dynamic pricing policy. At the end of this section, we summarize our work’s main results in Table 1 . Fixed Price Approximation Guarantees. For every positive integer n , consider i.i.d. valuations X_{1},X_{2},\ldots,X_{n} with X_{j} distributed according to F for every j\in\{1,\ldots,n\} , where F is a distribution over the non-negative reals. Given a value T , consider the simple policy given by selling the item to any buyer with valuation exceeding T . Then, for each distribution F , we are interested in understanding the limit ratio between the welfare of this simple policy, which is simply given by the probability of having an X_{i} above T , 1-F^{n}(T) times the expected value of X_{i} conditioned on it being larger than T , and the welfare of the optimal mechanism, which is the expectation of the maximum valuation, and it is denoted as M_{n} . Our quantity of interest is then {\text{apx}}(F)=\liminf_{n\to\infty}\sup_{T\in\mathbb{R}_{+}}\frac{1-F^{n}(T)}{\mathbf{E}(M_{n})}\left(T+\frac{1}{1-F(T)}\int_{T}^{\infty}(1-F(s))\mathrm{d}s\right), (1) and we call this value welfare guarantee . Our first main result shows that 0.712 is a tight lower bound for {\text{apx}}(F) when the distribution satisfies the extreme value condition. This condition is, essentially, the equivalent of a central limit theorem for the maximum of an i.i.d. sample, and it is the cornerstone of the extreme value theory. The 0.712 value is substantially better than the known bound of 1-1/e by Ehsani et al. [ 23 ] and thus represents a significant advantage for the large markets setting. We remark that we are mainly interested in the case of distributions F with unbounded support, since one can show that {\text{apx}}(F)=1 when F is of bounded support. A natural and practically relevant extension of the problem of selling a single item is to consider the setting in which we can sell up to k items. We call this problem k -unit problem and we study whether the large market advantage continues to be significant beyond the single item case. To this end, we provide a lower bound for the approximation factor achievable by the best fixed price policy, again under the extreme value condition. More specifically, for each value of k , the approximation factor is bounded by a (computationally) simple optimization problem. In particular, the bound presented when k=1 follows from obtaining the exact solution of the optimization problem. The performance obtained by our characterization represents an advantage for the k -unit problem. However, we show that the advantage vanishes as k\to\infty . Indeed, we prove that for each integer k , the approximation factor is more than 1-1/\sqrt{2k\pi} , but there exists F such that this lower bound is asymptotically tight in k . This tightness, together with the 1-1/\sqrt{2k\pi} lower bound on the fixed-price approximation ratio of the k -unit problem (see, e.g., [ 21 , 4 ] ) implies that the large market advantage vanishes as k\to\infty ; for an illustration, Figure 1 depicts the bound obtained by our optimization problem and compares it with 1-1/\sqrt{2k\pi} . Figure 1 : Our optimal welfare guarantee over k (continuous line) vs. 1-1/\sqrt{2k\pi} (dashed line). We note that as a direct corollary, when F satisfies the extreme value condition and for large markets, we can derive the adaptivity gap ; the worst case ratio between the value obtained by the optimal fixed price policy and that of the optimal PPM of Kennedy and Kertz. This value is at most 1.105. Finally, we give sufficient conditions under which our main result for the k -unit problem can be translated into a revenue guarantee for a fixed price policy. More specifically, while by standard arguments this works as long as the distribution of the virtual values of F , call it G ,

Read the complete text