A Simple and Approximately Optimal Mechanism for an Additive Buyer

Authors

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg

Type: Article

Publication Date: 2020-06-16

Citations: 33

DOI: https://doi.org/10.1145/3398745

View Ask PDF

Abstract

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a priori better of two simple pricing methods: selling the items separately , each at its optimal price, and bundling together , in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

Topics

Locations

Journal of the ACM
View
arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

A Simple and Approximately Optimal Mechanism for an Additive Buyer

2014-01-01

Moshe Babaioff , Nicole Immorlica , Brendan Lucier +1 more

We consider a monopolist seller with $n$ heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value … We consider a monopolist seller with $n$ heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a-priori better of two simple pricing methods: selling the items separately, each at its optimal price, and bundling together, in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

View PDF Chat

A Simple and Approximately Optimal Mechanism for an Additive Buyer

2014-10-01

Moshe Babaioff , Nicole Immorlica , Brendan Lucier +1 more

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a … We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue.It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting:item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.

View PDF Chat

Revenue Maximization for Selling Multiple Correlated Items

2014-01-01

MohammadHossein Bateni , Sina Dehghani , MohammadTaghi Hajiaghayi +1 more

We study the problem of selling $n$ items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of … We study the problem of selling $n$ items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of the buyer for the items are not drawn independently. Ideally, the goal is to design a mechanism to maximize the revenue. However, it has been shown that a revenue optimal mechanism might be very complicated and as a result inapplicable to real-world auctions. Therefore, our focus is on designing a simple mechanism that achieves a constant fraction of the optimal revenue. Babaioff et al. propose a simple mechanism that achieves a constant fraction of the optimal revenue for independent setting with a single additive buyer. However, they leave the following problem as an open question: "Is there a simple, approximately optimal mechanism for a single additive buyer whose value for $n$ items is sampled from a common base-value distribution?" Babaioff et al. show a constant approximation factor of the optimal revenue can be achieved by either selling the items separately or as a whole bundle in the independent setting. We show a similar result for the correlated setting when the desirabilities of the buyer are drawn from a common base-value distribution. It is worth mentioning that the core decomposition lemma which is mainly the heart of the proofs for efficiency of the mechanisms does not hold for correlated settings. Therefore we propose a modified version of this lemma which is applicable to the correlated settings as well. Although we apply this technique to show the proposed mechanism can guarantee a constant fraction of the optimal revenue in a very weak correlation, this method alone can not directly show the efficiency of the mechanism in stronger correlations.

View PDF Chat

Revenue Maximization for Selling Multiple Correlated Items

2014-12-10

MohammadHossein Bateni , Sina Dehghani , MohammadTaghi Hajiaghayi +1 more

We study the problem of selling $n$ items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of … We study the problem of selling $n$ items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of the buyer for the items are not drawn independently. Ideally, the goal is to design a mechanism to maximize the revenue. However, it has been shown that a revenue optimal mechanism might be very complicated and as a result inapplicable to real-world auctions. Therefore, our focus is on designing a simple mechanism that achieves a constant fraction of the optimal revenue. Babaioff et al. propose a simple mechanism that achieves a constant fraction of the optimal revenue for independent setting with a single additive buyer. However, they leave the following problem as an open question: Is there a simple, approximately optimal mechanism for a single additive buyer whose value for $n$ items is sampled from a common base-value distribution? Babaioff et al. show a constant approximation factor of the optimal revenue can be achieved by either selling the items separately or as a whole bundle in the independent setting. We show a similar result for the correlated setting when the desirabilities of the buyer are drawn from a common base-value distribution. It is worth mentioning that the core decomposition lemma which is mainly the heart of the proofs for efficiency of the mechanisms does not hold for correlated settings. Therefore we propose a modified version of this lemma which is applicable to the correlated settings as well. Although we apply this technique to show the proposed mechanism can guarantee a constant fraction of the optimal revenue in a very weak correlation, this method alone can not directly show the efficiency of the mechanism in stronger correlations.

Selling Multiple Items to a Unit-Demand Buyer via Automated Mechanism Design

2025-02-14

K Hashimoto , Keita Kuwahara , Ryo Nonaka

Finding the optimal (revenue-maximizing) mechanism to sell multiple items has been a prominent and notoriously difficult open problem. Existing work has mainly focused on deriving analytical results tailored to a … Finding the optimal (revenue-maximizing) mechanism to sell multiple items has been a prominent and notoriously difficult open problem. Existing work has mainly focused on deriving analytical results tailored to a particular class of problems (for example, Giannakopoulos (2015) and Yang (2023)). The present paper explores the possibility of a generally applicable methodology of the Automated Mechanism Design (AMD). We first employ the deep learning algorithm developed by D\"utting et al. (2023) to numerically solve small-sized problems, and the results are then generalized by educated guesswork and finally rigorously verified through duality. By focusing on a single buyer who can consume one item, our approach leads to two key contributions: establishing a much simpler way to verify the optimality of a wide range of problems and discovering a completely new result about the optimality of grand bundling. First, we show that selling each item at an identical price (or equivalently, selling the grand bundle of all items) is optimal for any number of items when the value distributions belong to a class that includes the uniform distribution as a special case. Different items are allowed to have different distributions. Second, for each number of items, we established necessary and sufficient conditions that $c$ must satisfy for grand bundling to be optimal when the value distribution is uniform over an interval $[c, c + 1]$. This latter model does not satisfy the previously known sufficient conditions for the optimality of grand bundling Haghpanah and Hartline (2021). Our results are in contrast to the only known results for $n$ items (for any $n$), Giannakopoulos (2015) and Daskalakis et al. (2017), which consider a single buyer with additive preferences, where the values of items are narrowly restricted to i.i.d. according to a uniform or exponential distribution.

View PDF Chat

A simple and approximately optimal mechanism for an additive buyer

2015-01-28

Moshe Babaioff , Nicole Immorlica , Brendan Lucier +1 more

In this letter we briefly survey our main result from [Babaioff el al. 2014]: a simple and approximately revenue-optimal mechanism for a monopolist who wants to sell a variety of … In this letter we briefly survey our main result from [Babaioff el al. 2014]: a simple and approximately revenue-optimal mechanism for a monopolist who wants to sell a variety of items to a single buyer with an additive valuation.

View PDF Chat

A Simple Mechanism for a Budget-Constrained Buyer

2018-01-01

Yu Cheng , Nick Gravin , Kamesh Munagala +1 more

We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting a monopolist seller with $m$ heterogeneous items … We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting a monopolist seller with $m$ heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has a budget and additive valuations drawn independently for each item from (non-identical) distributions. We show that when the buyer's budget is publicly known, the better of selling each item separately and selling the grand bundle extracts a constant fraction of the optimal revenue. When the budget is private, we consider a standard Bayesian setting where buyer's budget $b$ is drawn from a known distribution $B$. We show that if $b$ is independent of the valuations and distribution $B$ satisfies monotone hazard rate condition, then selling items separately or in a grand bundle is still approximately optimal. We give a complementary example showing that no constant approximation simple mechanism is possible if budget $b$ can be interdependent with valuations.

View PDF Chat

A Simple and Approximately Optimal Mechanism for a Buyer with Complements

2017-06-20

Alon Eden , Michal Feldman , Ophir Friedler +2 more

We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation v for the items may exhibit both substitutes (i.e., for some S, T, v(S ∪ … We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation v for the items may exhibit both substitutes (i.e., for some S, T, v(S ∪ T) < v(S) + v(T)) and complements (i.e., for some S, T, v(S ∪ T) > v(S) + v(T)). We show that the mechanism first proposed by Babaioff et al. [2014] -- the better of selling the items separately and bundling them together -- guarantees a Θ(d) fraction of the optimal revenue, where $d$ is a measure on the degree of complementarity. Note that this is the first approximately optimal mechanism for a buyer whose valuation exhibits any kind of complementarity. It extends the work of Rubinstein and Weinberg [2015], which proved that the same simple mechanisms achieve a constant factor approximation when buyer valuations are subadditive, the most general class of complement-free valuations.

View PDF Chat

Buy-many mechanisms are not much better than item pricing

2022-04-19

Shuchi Chawla , Yifeng Teng , Christos Tzamos

Multi-item mechanisms can be very complex offering many different randomized bundles to the buyer. Such complexity is thought to be necessary as the revenue gaps between optimal mechanisms and simple … Multi-item mechanisms can be very complex offering many different randomized bundles to the buyer. Such complexity is thought to be necessary as the revenue gaps between optimal mechanisms and simple mechanisms are unbounded. Our work shows these gaps do not apply to most natural situations: they require that the mechanism overcharges the buyer for a bundle while selling individual items at much lower prices. We study revenue maximization under the buy-many constraint which allows the buyer to purchase any number of (randomized) bundles as he pleases. We show that the revenue of any buy-many mechanism is at most O(log⁡n) times the revenue achievable by item pricing, where n is the number of items. This holds even with an arbitrarily correlated distribution of buyer types and arbitrary valuations. Furthermore, no family of mechanisms of subexponential description complexity can achieve better than a logarithmic approximation even for additive valuations.

View PDF Chat

Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")

2013-04-22

Sergiu Hart , Noam Nisan

We consider the well known, and notoriously difficult, problem of a single revenue-maximizing seller selling two or more heterogeneous goods to a single buyer whose private values for the goods … We consider the well known, and notoriously difficult, problem of a single revenue-maximizing seller selling two or more heterogeneous goods to a single buyer whose private values for the goods are drawn from a (possibly correlated) known distribution, and whose valuation is additive over the goods. We show that when there are two (or more) goods, _simple mechanisms_ -- such as selling the goods separately or as a bundle -- _may yield only a negligible fraction of the optimal revenue_. This resolves the open problem of Briest, Chawla, Kleinberg, and Weinberg (JET 2015) who prove the result for at least three goods in the related setup of a unit-demand buyer. We also introduce the menu size as a simple measure of the complexity of mechanisms, and show that the revenue may increase polynomially with _menu size_ and that no bounded menu size can ensure any positive fraction of the optimal revenue. The menu size also turns out to pin down the revenue properties of deterministic mechanisms.

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

2015-06-12

Aviad Rubinstein , S. Matthew Weinberg

View PDF Chat

Buy-Many Mechanisms are Not Much Better than Item Pricing

2019-06-17

Shuchi Chawla , Yifeng Teng , Christos Tzamos

Multi-item revenue optimal mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue … Multi-item revenue optimal mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for additive valuations. We challenge this conventional belief by showing that these large gaps can only happen in unrealistic situations. These are situations where the mechanism overcharges a buyer for a bundle while selling individual items at much lower prices. Arguably this is impractical as the buyer can break his order into smaller pieces paying a much lower price overall. Our main result is that if the buyer is allowed to purchase as many (randomized) bundles as he pleases, the revenue of any multi-item mechanism is at most O(łog n) times the revenue achievable by item pricing, where n is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations. We also show that this result is tight in a very strong sense. Any family of mechanisms of subexponential description complexity cannot achieve better than logarithmic approximation even against the best deterministic mechanism and even for additive valuations. In contrast, item pricing that has linear description complexity matches this bound against randomized mechanisms.

View PDF Chat

A Simple Mechanism for a Budget-Constrained Buyer

2021-01-04

Yu Cheng , Nick Gravin , Kamesh Munagala +1 more

We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting, a monopolist seller with m heterogeneous items … We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting, a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has a budget and additive valuations drawn independently for each item from (non-identical) distributions. We show that when the buyer’s budget is publicly known, it is better to sell each item separately; selling the grand bundle extracts a constant fraction of the optimal revenue. When the budget is private, we consider a standard Bayesian setting where buyer’s budget b is drawn from a known distribution B . We show that if b is independent of the valuations (which is necessary) and distribution B satisfies monotone hazard rate condition, then selling items separately or in a grand bundle is still approximately optimal.

View PDF Chat

Buy-many mechanisms are not much better than item pricing

2019-01-01

Shuchi Chawla , Yifeng Teng , Christos Tzamos

Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between … Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for additive valuations. We challenge this conventional belief by showing that these large gaps can only happen in restricted situations. These are situations where the mechanism overcharges a buyer for a bundle while selling individual items at much lower prices. Arguably this is impractical in many settings because the buyer can break his order into smaller pieces paying a much lower price overall. Our main result is that if the buyer is allowed to purchase as many (randomized) bundles as he pleases, the revenue of any multi-item mechanism is at most O(logn) times the revenue achievable by item pricing, where n is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations. We also show that this result is tight in a very strong sense. Any family of mechanisms of subexponential description complexity cannot achieve better than logarithmic approximation even against the best deterministic mechanism and even for additive valuations. In contrast, item pricing that has linear description complexity matches this bound against randomized mechanisms.

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

2018-10-01

Aviad Rubinstein , S. Matthew Weinberg

We study the revenue maximization problem of a seller with n heterogeneous items for sale to a single buyer whose valuation function for sets of items is unknown and drawn … We study the revenue maximization problem of a seller with n heterogeneous items for sale to a single buyer whose valuation function for sets of items is unknown and drawn from some distribution D . We show that if D is a distribution over subadditive valuations with independent items, then the better of pricing each item separately or pricing only the grand bundle achieves a constant-factor approximation to the revenue of the optimal mechanism. This includes buyers who are k -demand, additive up to a matroid constraint, or additive up to constraints of any downward-closed set system (and whose values for the individual items are sampled independently), as well as buyers who are fractionally subadditive with item multipliers drawn independently. Our proof makes use of the core-tail decomposition framework developed in prior work showing similar results for the significantly simpler class of additive buyers. In the second part of the article, we develop a connection between approximately optimal simple mechanisms and approximate revenue monotonicity with respect to buyers’ valuations. Revenue non-monotonicity is the phenomenon that sometimes strictly increasing buyers’ values for every set can strictly decrease the revenue of the optimal mechanism. Using our main result, we derive a bound on how bad this degradation can be (and dub such a bound a proof of approximate revenue monotonicity); we further show that better bounds on approximate monotonicity imply a better analysis of our simple mechanisms.

View PDF Chat

Optimal mechanisms with simple menus

2013-01-01

Zihe Wang , Pingzhong Tang

We consider optimal mechanism design for the case with one buyer and two items. The buyer's valuations towards the two items are independent and additive. In this setting, optimal mechanism … We consider optimal mechanism design for the case with one buyer and two items. The buyer's valuations towards the two items are independent and additive. In this setting, optimal mechanism is unknown for general valuation distributions. We obtain two categories of structural results that shed light on the optimal mechanisms. The first category of results state that, under certain mild condition, the optimal mechanism has a monotone menu. In other words, in the menu that represents the optimal mechanism, as payment increases, the allocation probabilities for both items increase simultaneously. Applying this theorem, we derive a version of revenue monotonicity theorem that states stochastically superior distributions yield more revenue. Moreover, our theorem subsumes a previous result regarding sufficient conditions under which bundling is optimal. The second category of results state that, under certain conditions, the optimal mechanisms have few menu items. Our first result in this category says, for certain distributions, the optimal menu contains at most 4 items. The condition admits power (including uniform) density functions. Based on a similar proof of this result, we are able to obtain a wide class of distributions where bundling is optimal. Our second result in this category works for a weaker condition, under which the optimal menu contains at most 6 items. This condition includes exponential density functions. Our last result in this category works for unit-demand setting. It states that, for uniform distributions, the optimal menu contains at most 5 items. All these results are in sharp contrast to Hart and Nisan's recent result that finite-sized menu cannot guarantee any positive fraction of optimal revenue for correlated valuation distributions.

View PDF Chat

Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer

2020-07-09

Moshe Babaioff , Michal Feldman , Yannai A. Gonczarowski +2 more

We consider a robust version of the revenue maximization problem, where a single seller wishes to sell n items to a single unit-demand buyer. In this robust version, the seller … We consider a robust version of the revenue maximization problem, where a single seller wishes to sell n items to a single unit-demand buyer. In this robust version, the seller knows the buyer's marginal value distribution for each item separately, but not the joint distribution, and prices the items to maximize revenue in the worst case over all compatible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case [Carroll, 2017], we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than n1/2-ε. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently.

View PDF Chat

Bundling in Oligopoly: Revenue Maximization with Single-Item Competitors

2024-06-19

Moshe Babaioff , Linda Cai , Brendan Lucier

We consider a principal seller with $m$ heterogeneous products to sell to an additive buyer over independent items. The principal can offer an arbitrary menu of product bundles, but faces … We consider a principal seller with $m$ heterogeneous products to sell to an additive buyer over independent items. The principal can offer an arbitrary menu of product bundles, but faces competition from smaller and more agile single-item sellers. The single-item sellers choose their prices after the principal commits to a menu, potentially under-cutting the principal's offerings. We explore to what extent the principal can leverage the ability to bundle product together to extract revenue. Any choice of menu by the principal induces an oligopoly pricing game between the single-item sellers, which may have multiple equilibria. When there is only a single item this model reduces to Bertrand competition, for which the principal's revenue is $0$ at any equilibrium, so we assume that no single item's value is too dominant. We establish an upper bound on the principal's optimal revenue at every equilibrium: the expected welfare after truncating each item's value to its revenue-maximizing price. Under a technical condition on the value distributions -- that the monopolist's revenue is sufficiently sensitive to price -- we show that the principal seller can simply price the grand-bundle and ensure (in any equilibrium) a constant approximation to this bound (and hence to the optimal revenue). We also show that for some value distributions violating our conditions, grand-bundle pricing does not yield a constant approximation to the optimal revenue in any equilibrium.

View PDF Chat

Approximate revenue maximization with multiple items

2012-06-04

Sergiu Hart , Noam Nisan

Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible … Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for the items, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of them separately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two items even in this simple setting is not understood.

View PDF Chat

Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer

2020-03-12

Moshe Babaioff , Michal Feldman , Yannai A. Gonczarowski +2 more

We consider a robust version of the revenue maximization problem, where a single seller wishes to sell $n$ items to a single unit-demand buyer. In this robust version, the seller … We consider a robust version of the revenue maximization problem, where a single seller wishes to sell $n$ items to a single unit-demand buyer. In this robust version, the seller knows the buyer's marginal value distribution for each item separately, but not the joint distribution, and prices the items to maximize revenue in the worst case over all compatible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case (Carroll, 2017), we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than $n^{1/2-\epsilon}$. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently.

When Is Assortment Optimization Optimal?

2022-06-22

Will Ma

Assortment optimization concerns the problem of selling items with fixed prices to a buyer who will purchase at most one. Typically, retailers select a subset of items, corresponding to an … Assortment optimization concerns the problem of selling items with fixed prices to a buyer who will purchase at most one. Typically, retailers select a subset of items, corresponding to an “assortment” of brands to carry, and make each selected item available for purchase at its brand-recommended price. Despite the tremendous importance in practice, the best method for selling these fixed-price items is not well understood, as retailers have begun experimenting with making certain items available only through a lottery. In this paper, we analyze the maximum possible revenue that can be earned in this setting, given that the buyer’s preference is private, but drawn from a known distribution. In particular, we introduce a Bayesian mechanism-design problem where the buyer has a random ranking over fixed-price items and an outside option, and the seller optimizes a (randomized) allocation of up to one item. We show that allocations corresponding to assortments are suboptimal in general, but under many commonly studied Bayesian priors for buyer rankings, such as the Multinomial Logit and Markov Chain choice models, assortments are, in fact, optimal. Therefore, this large literature on assortment optimization has much greater significance than appreciated before—it is not only computing optimal assortments; it is computing the economic limit of the seller’s revenue for selling these fixed-price substitute items. We derive several further results—a more general sufficient condition for assortments being optimal that captures choice models beyond Markov Chain; a proof that Nested Logit choice models cannot be captured by Markov Chain, but can, to some extent, be captured by our condition; and suboptimality gaps for assortments when our condition does not hold. Finally, we show that our mechanism-design problem provides the tightest-known Linear Programming relaxation for assortment optimization under the ranking distribution model. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2022.4471 .

View PDF Chat

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies

2024-07-08

Vasilis Livanos , Kalen Patton , Sahil Singla

View PDF Chat

Analyzing and Forecasting of COVID-19 Situation Using FbProphet Model Algorithms

2022-05-16

S. Geetha , M. Farida Begam , Ayush Dubey +2 more

SARS-CoV-2 (n-coronavirus) is a global pandemic that has killed millions of people all over the world. In severe situations, it can induce pneumonia and severe acute respiratory syndrome (SARS), which … SARS-CoV-2 (n-coronavirus) is a global pandemic that has killed millions of people all over the world. In severe situations, it can induce pneumonia and severe acute respiratory syndrome (SARS), which can lead to death. It's an asymptomatic sickness that makes life and work more difficult for us. This research focused on the current state of the coronavirus pandemic and forecasted the global situation, as well as its impacts and future status. The authors used the FbProphet model to forecast new covid cases and deaths for the month of August utilizing various information representation and machine learning algorithms. They hope the findings will aid scientists, researchers, and laypeople in predicting and analyzing the effects of the epidemic. Finally, they conclude that the virus's second wave was around four times stronger than the first. They also looked at the trajectory of COVID-19 instances (monthly and weekly) and discovered that the number of cases rises more during the weekdays, which could be due to the weekend lockout.

Selling two identical objects

2021-12-06

Sushil Bikhchandani , Debasis Mishra

View PDF Chat

Simple Mechanisms for Agents with Complements

2016-07-21

Michal Feldman , Ophir Friedler , Jamie Morgenstern +1 more

We study the efficiency of simple auctions in the presence of complements. [DMSW15] introduced the single-bid auction, and showed that it has a price of anarchy (PoA) of $O(\log m)$ … We study the efficiency of simple auctions in the presence of complements. [DMSW15] introduced the single-bid auction, and showed that it has a price of anarchy (PoA) of $O(\log m)$ for complement-free (i.e., subadditive) valuations. Prior to our work, no non-trivial upper bound on the PoA of single bid auctions was known for valuations exhibiting complements. We introduce a hierarchy over valuations, where levels of the hierarchy correspond to the degree of complementarity, and the PoA of the single bid auction degrades gracefully with the level of the hierarchy. This hierarchy is a refinement of the Maximum over Positive Hypergraphs (MPH) hierarchy [FFIILS15], where the degree of complementarity $d$ is captured by the maximum number of neighbors of a node in the positive hypergraph representation. We show that the price of anarchy of the single bid auction for valuations of level $d$ of the hierarchy is $O(d^2 \log(m/d))$, where $m$ is the number of items. We also establish an improved upper bound of $O(d \log m)$ for a subclass where every hyperedge in the positive hypergraph representation is of size at most 2 (but the degree is still $d$). Finally, we show that randomizing between the single bid auction and the grand bundle auction has a price of anarchy of at most $O(\sqrt{m})$ for general valuations. All of our results are derived via the smoothness framework, thus extend to coarse-correlated equilibria and to Bayes Nash equilibria.

View PDF Chat

Settling the Competition Complexity of Additive Buyers over Independent Items

2024-07-08

Mahsa Derakhshan , Emily Ryu , S. Matthew Weinberg +1 more

View PDF Chat

Selling Two Identical Objects.

2020-09-24

Sushil Bikhchandani , Debasis Mishra

It is well-known that optimal (i.e., revenue-maximizing) selling mechanisms in multidimensional type spaces may involve randomization. We obtain conditions under which deterministic mechanisms are optimal for selling two identical, indivisible … It is well-known that optimal (i.e., revenue-maximizing) selling mechanisms in multidimensional type spaces may involve randomization. We obtain conditions under which deterministic mechanisms are optimal for selling two identical, indivisible objects to a single buyer. We analyze two settings: (i) decreasing marginal values (DMV) and (ii) increasing marginal values (IMV). Thus, the values of the buyer for the two units are not independent. We show that under a well-known condition on distributions~(due to McAfee and McMillan (1988)), (a) it is optimal to sell the first unit deterministically in the DMV model and (b) it is optimal to bundle (which is a deterministic mechanism) in the IMV model. Under a stronger sufficient condition on distributions, a deterministic mechanism is optimal in the DMV model. Our results apply to heterogeneous objects when there is a specified sequence in which the two objects must be sold.

Generalized Permutahedra and Optimal Auctions

2022-12-19

Michael Joswig , Max Klimm , Sylvain Spitz

We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias in 2018 to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong … We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias in 2018 to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.

View PDF Chat

Optimal Pricing Schemes for an Impatient Buyer

2021-01-01

Yuan Deng , Jieming Mao , Balasubramanian Sivan +1 more

A patient seller aims to sell a good to an impatient buyer (i.e., one who discounts utility over time). The buyer will remain in the market for a period of … A patient seller aims to sell a good to an impatient buyer (i.e., one who discounts utility over time). The buyer will remain in the market for a period of time $T$, and her private value is drawn from a publicly known distribution. What is the revenue-optimal pricing-curve (sequence of (price, time) pairs) for the seller? Is randomization of help here? Is the revenue-optimal pricing curve computable in polynomial time? We answer these questions in this paper. We give an efficient algorithm for computing the revenue-optimal pricing curve. We show that pricing curves, that post a price at each point of time and let the buyer pick her utility maximizing time to buy, are revenue-optimal among a much broader class of sequential lottery mechanisms. I.e., mechanisms that allow the seller to post a menu of lotteries at each point of time cannot get any higher revenue than pricing curves. We also show that the even broader class of mechanisms that allow the menu of lotteries to be adaptively set, can earn strictly higher revenue than that of pricing curves, and the revenue gap can be as big as the support size of the buyer's value distribution.

View PDF Chat

Bayesian and Randomized Clock Auctions

2022-07-12

Michal Feldman , Vasilis Gkatzelis , Nick Gravin +1 more

In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving … In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving this service, and some feasibility constraint restricts which subsets of buyers can be served simultaneously. Recent work in economics introduced (deferred-acceptance) clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and very strong incentive guarantees. Subsequent work in computer science focused on evaluating these auctions with respect to their social welfare approximation guarantees, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets.

View PDF Chat

The Power of Simple Menus in Robust Selling Mechanisms

2024-09-27

Shixin Wang

We study a robust selling problem where a seller attempts to sell one item to a buyer but is uncertain about the buyer’s valuation distribution. The existing literature shows that … We study a robust selling problem where a seller attempts to sell one item to a buyer but is uncertain about the buyer’s valuation distribution. The existing literature shows that robust screening provides a stronger theoretical guarantee than robust deterministic pricing but at the expense of implementation complexity as it requires a menu of infinite options. Our research aims to find simple mechanisms to hedge against market ambiguity effectively. We develop a general framework for robust selling mechanisms with a finite menu (or randomization across finite prices). We propose a tractable reformulation that addresses various ambiguity sets of the buyer’s valuation distribution, including support, mean, and quantile ambiguity sets. We derive optimal selling mechanisms and corresponding performance ratios for different menu sizes, which show that even a modest menu size can deliver benefits similar to those achieved by the optimal robust mechanism with infinite options, establishing a favorable trade-off between theoretical performance and implementation simplicity. Remarkably, a menu size of merely two can significantly enhance the performance ratio compared with deterministic pricing. This paper was accepted by Chung Piaw Teo, optimization and decision analytics. Funding: This research was supported by the National Natural Science Foundation of China [Grant 72394395]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2023.03738 .

View PDF Chat

Structural Complexities of Matching Mechanisms

2024-06-10

Yannai A. Gonczarowski , Clayton Thomas

We study various novel complexity measures for two-sided matching mechanisms, applied to the two canonical strategyproof matching mechanisms, Deferred Acceptance (DA) and Top Trading Cycles (TTC). Our metrics are designed … We study various novel complexity measures for two-sided matching mechanisms, applied to the two canonical strategyproof matching mechanisms, Deferred Acceptance (DA) and Top Trading Cycles (TTC). Our metrics are designed to capture the complexity of various structural (rather than computational) concerns, in particular ones of recent interest within economics. We consider a unified, flexible approach to formalizing our questions: Define a protocol or data structure performing some task, and bound the number of bits that it requires. Our main results apply this approach to four questions of general interest; for mechanisms matching applicants to institutions, our questions are: (1) How can one applicant affect the outcome matching? (2) How can one applicant affect another applicant's set of options? (3) How can the outcome matching be represented / communicated? (4) How can the outcome matching be verified? Holistically, our results show that TTC is more complex than DA, formalizing previous intuitions that DA has a simpler structure than TTC. For question (2), our result gives a new combinatorial characterization of which institutions are removed from each applicant's set of options when a new applicant is added in DA; this characterization may be of independent interest. For question (3), our result gives new tight lower bounds proving that the relationship between the matching and the priorities is more complex in TTC than in DA. We nonetheless showcase that this higher complexity of TTC is nuanced: By constructing new tight lower-bound instances and new verification protocols, we prove that DA and TTC are comparable in complexity under questions (1) and (4). This more precisely delineates the ways in which TTC is more complex than DA, and emphasizes that diverse considerations must factor into gauging the complexity of matching mechanisms.

View PDF Chat

Deterministic Budget-Feasible Clock Auctions

2021-01-01

Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more

We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the … We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

Tight approximation ratio of anonymous pricing

2018-01-01

Yaonan Jin

How to maximize the revenue of a seller, who intends to sell a single indivisible item to a number of buyers, is a central problem in microeconomics. The Bayesian version … How to maximize the revenue of a seller, who intends to sell a single indivisible item to a number of buyers, is a central problem in microeconomics. The Bayesian version of this problem was settled by Myerson. Although illustrating theoretical beauty, Myerson's auction rarely appears in real-world applications, mainly because of three reasons: (1) it discriminates different buyers with different value priors. This may incur some fairness issues, and is not feasible in some markets; (2) it requires the buyers to report their private values, rather than to make take-it-or-leave-it decisions. This may raise some privacy concerns for the buyers; (3) it is an auction scheme rather than a pricing scheme, and therefore incorporates far more communication between the seller and the buy...[ Read more ]

View PDF Chat

Revenue Maximization for Buyers with Outside Options.

2021-03-05

Yannai A. Gonczarowski , Nicole Immorlica , Yingkai Li +1 more

We study mechanisms for selling a single item when buyers have private values for their outside options, which they forego by participating in the mechanism. This substantially changes the revenue … We study mechanisms for selling a single item when buyers have private values for their outside options, which they forego by participating in the mechanism. This substantially changes the revenue maximization problem. For example, the seller can strictly benefit from selling lotteries already in the single-buyer setting. We bound the menu size and the sample complexity for the optimal single-buyer mechanism. We then show that posting a single price is in fact optimal under the assumption that either (1) the outside option value is independent of the item value, and the item value distribution has decreasing marginal revenue or monotone hazard rate; or (2) the outside option value is a concave function of the item value. Moreover, when there are multiple buyers, we show that sequential posted pricing guarantees a large fraction of the optimal revenue under similar conditions.

Partition and Prosper: Design and Pricing of Single Bundle

2025-02-19

Hailong Sun , Xiaobo Li , Chung‐Piaw Teo

Design and Pricing of a Single Bundle Product bundling is a widely used selling strategy among multiproduct firms, yet designing and pricing bundles optimally remain a complex challenge. In “Partition … Design and Pricing of a Single Bundle Product bundling is a widely used selling strategy among multiproduct firms, yet designing and pricing bundles optimally remain a complex challenge. In “Partition and Prosper: Design and Pricing of a Single Bundle,” Sun, Li, and Teo show that the selection and pricing of a single bundle from a range of products under multivariate normal valuations is polynomial-time solvable, provided that the associated covariance matrix can be decomposed into a positive diagonal matrix minus a positive semidefinite matrix of (small) fixed rank. Interestingly, they also show that if the individual product prices are predetermined, the optimization problem becomes NP hard even if customer valuations are independent. The authors use a Bayesian optimization algorithm combined with a novel conic integer programming reformulation to solve the problem under general valuation distributions and demonstrate the superior numerical performance of the algorithm via extensive simulations.

Efficient and Effective Budget-Feasible Mechanisms for Submodular Valuations

2025-05-01

Kai Han , Haotian Zhang , Shuang Cui

Optimal Pricing Schemes for an Impatient Buyer

2023-01-01

Yuan Deng , Jieming Mao , Balasubramanian Sivan +1 more

A patient seller aims to sell a good to an impatient buyer (i.e., one who discounts utility over time). The buyer will remain in the market for a period of … A patient seller aims to sell a good to an impatient buyer (i.e., one who discounts utility over time). The buyer will remain in the market for a period of time T, and her private value is drawn from a publicly known distribution. What is the revenue-optimal pricing-curve (sequence of (price, time) pairs) for the seller? Is randomization of help here? Is the revenue-optimal pricing-curve computable in polynomial time? We answer these questions in this paper. We give an efficient algorithm for computing the revenue-optimal pricing curve. We show that pricing curves, that post a price at each point of time and let the buyer pick her utility maximizing time to buy, are revenue-optimal among a much broader class of sequential lottery mechanisms: namely, mechanisms that allow the seller to post a menu of lotteries at each point of time cannot get any higher revenue than pricing curves. We also show that the even broader class of mechanisms that allow the menu of lotteries to be adaptively set, can earn strictly higher revenue than that of pricing curves, and the revenue gap can be as big as the support size of the buyer's value distribution.* The full version of the paper can be accessed at https://arxiv.org/abs/2106.02149.

View PDF Chat

Simplicity in Auctions Revisited: The Primitive Complexity

2023-07-07

Moshe Babaioff , Shahar Dobzinski , Ron Kupfer

In this paper we revisit the notion of simplicity in mechanisms. We consider a seller of m heterogeneous items, facing a single buyer with valuation v. We observe that previous … In this paper we revisit the notion of simplicity in mechanisms. We consider a seller of m heterogeneous items, facing a single buyer with valuation v. We observe that previous attempts to define complexity measures often fail to classify mechanisms that are intuitively considered simple (e.g., the "selling separately" mechanism) as such. We suggest to view a menu as simple if a bundle that maximizes the buyer's profit can be found by conducting a few primitive operations that are considered simple. The primitive complexity of a menu is the number of primitive operations needed to (adaptively) find a profit-maximizing entry in the menu. In this paper, the primitive operation that we study is essentially computing the outcome of the "selling separately" mechanism.

View PDF Chat

The power of randomness in Bayesian optimal mechanism design

2012-08-28

Shuchi Chawla , David Malec , Balasubramanian Sivan

View PDF Chat

The power of randomness in bayesian optimal mechanism design

2010-06-07

Shuchi Chawla , David L. Malec , Balasubramanian Sivan

We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem - a single seller aims to maximize expected revenue by allocating multiple kinds … We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem - a single seller aims to maximize expected revenue by allocating multiple kinds of resources to "unit-demand" agents with preferences drawn from a known distribution. When the agents' preferences are single-dimensional Myerson's seminal work [14] shows that randomness offers no benefit - the optimal mechanism is always deterministic. In the multi-dimensional case, where each agent's preferences are given by different values for each of the available services, Briest et al.[6] recently showed that the gap between the expected revenue obtained by an optimal randomized mechanism and an optimal deterministic mechanism can be unbounded even when a single agent is offered only 4 services. However, this large gap is attained through unnatural instances where values of the agent for different services are correlated in a specific way. We show that when the agent's values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor (4 and 8 respectively). Our model of positively correlated values (that we call the common base value model) is a natural model for unit-demand agents and items that are substitutes. Our results extend to multiple agent settings as well.

View PDF Chat

Extreme-Value Theorems for Optimal Multidimensional Pricing

2011-10-01

Yang Cai , Constantinos Daskalakis

We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed.) For all ϵ >; 0, we … We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed.) For all ϵ >; 0, we obtain a (1 + ϵ)-factor approximation to the optimal revenue in time polynomial, when the values are sampled from Monotone Hazard Rate (MHR) distributions, quasi-polynomial, when sampled from regular distributions, and polynomial in n poly(log r) when sampled from general distributions supported on a set [u min ,ru min ]. We also provide an additive PTAS for all bounded distributions. Our algorithms are based on novel extreme value theorems for MHR and regular distributions, and apply probabilistic techniques to understand the statistical properties of revenue distributions, as well as to reduce the size of the search space of the algorithm. As a byproduct of our techniques, we establish structural properties of optimal solutions. We show that, for all ϵ >; 0, g(1/ϵ) distinct prices suffice to obtain a (1 + ϵ)-factor approximation to the optimal revenue for MHR distributions, where g(1/ϵ) is a quasi-linear function of 1/ϵ that does not depend on the number of items. Similarly, for all ϵ >; 0 and n >; 0, g(1/ϵ · log n) distinct prices suffice for regular distributions, where n is the number of items and g(·) is a polynomial function. Finally, in the i.i.d. MHR case, we show that, as long as the number of items is a sufficiently large function of 1/ϵ, a single price suffices to achieve a (1 + ϵ)-factor approximation. Our results represent significant progress to the single-bidder case of the multidimensional optimal mechanism design problem, following Myerson's celebrated work on optimal mechanism design [Myerson 1981].

View PDF Chat

Revenue Maximization for Selling Multiple Correlated Items

2015-01-01

MohammadHossein Bateni , Sina Dehghani , MohammadTaghi Hajiaghayi +1 more

View PDF Chat

The sample complexity of revenue maximization

2014-05-31

Richard Cole , Tim Roughgarden

In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is … In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal of this paper is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue.

View PDF Chat

The sample complexity of auctions with side information

2016-06-10

Nikhil R. Devanur , Zhiyi Huang , Alexandros Psomas

Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter … Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the non-identical but independent value distribution case.

View PDF Chat

Reaping the Benefits of Bundling under High Production Costs

2015-12-08

Will Ma , David Simchi‐Levi

It is well-known that selling different goods in a single bundle can significantly increase revenue, even when the valuations for the goods are independent. However, bundling is no longer profitable … It is well-known that selling different goods in a single bundle can significantly increase revenue, even when the valuations for the goods are independent. However, bundling is no longer profitable if the goods have high production costs. To overcome this challenge, we introduce a new mechanism, Pure Bundling with Disposal for Cost (PBDC), where after buying the bundle, the customer is allowed to return any subset of goods for their production cost. We derive both distribution-dependent and distribution-free guarantees on its profitability, which improve previous techniques. Our distribution-dependent bound suggests that the firm should never price the bundle such that the profit margin is less than 1/3 of the expected welfare, while also showing that PBDC is optimal for a large number of independent goods. Our distribution-free bound suggests that on the distributions where PBDC performs worst, individual sales perform well. Finally, we conduct extensive simulations which confirm that PBDC outperforms other simple pricing schemes overall.

The menu-size complexity of revenue approximation

2017-06-15

Moshe Babaioff , Yannai A. Gonczarowski , Noam Nisan

We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F1,F2,…,Fn that possibly … We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F1,F2,…,Fn that possibly have unbounded support. It is well known that - unlike in the single item case - the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions with a finite bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size remained open.

View PDF Chat

Simple mechanisms for subadditive buyers via duality

2017-06-15

Yang Cai , Mingfei Zhao

We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, … We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, we prove that the better of the following two simple, deterministic and Dominant Strategy Incentive Compatible mechanisms, a sequential posted price mechanism or an anonymous sequential posted price mechanism with entry fee, achieves a constant fraction of the optimal revenue among all randomized, Bayesian Incentive Compatible mechanisms, when buyers' valuations are XOS over independent items. If the buyers' valuations are subadditive over independent items, the approximation factor degrades to O(logm), where m is the number of items. We obtain our results by first extending the Cai-Devanur-Weinberg duality framework to derive an effective benchmark of the optimal revenue for subadditive bidders, and then analyzing this upper bound with new techniques.

View PDF Chat

From Bayesian to Crowdsourced Bayesian Auctions.

2017-02-05

Jing Chen , Bo Li , Yingkai Li

A strong assumption in Bayesian mechanism design is that the distributions of the players' private types are common knowledge to the designer and the players--the common prior assumption. An important … A strong assumption in Bayesian mechanism design is that the distributions of the players' private types are common knowledge to the designer and the players--the common prior assumption. An important problem that has received a lot of attention in both economics and computer science is to repeatedly weaken this assumption in game theory--the Wilson's Doctrine. In this work we consider, for the first time in the literature, multi-item auctions where the knowledge about the players' value distributions is scattered among the players and the seller. Each one of them privately knows some or none of the value distributions, no constraint is imposed on who knows which distributions, and the seller does not know who knows what. In such an unstructured information setting, we design mechanisms for unit-demand and additive auctions, whose expected revenue approximates that of the optimal Bayesian mechanisms by crowdsourcing the players' and the seller's knowledge. Our mechanisms are 2-step dominant-strategy truthful and the revenue increases gracefully with the amount of knowledge the players have. In particular, the revenue starts from a constant fraction of the revenue of the best known dominant-strategy truthful Bayesian mechanisms, and approaches 100 percent of the later when the amount of knowledge increases. Our results greatly improve the literature on the relationship between the amount of knowledge in the system and what mechanism design can achieve. In some sense, our results show that the common prior assumption is without much loss of generality in Bayesian auctions if one is willing to give up a fraction of the revenue.

Strong Duality for a Multiple-Good Monopolist

2017-01-01

Constantinos Daskalakis , Alan Deckelbaum , Christos Tzamos

We characterize optimal mechanisms for the multiple-good monopoly problem and provide a framework to find them.We show that a mechanism is optimal if and only if a measure µ derived … We characterize optimal mechanisms for the multiple-good monopoly problem and provide a framework to find them.We show that a mechanism is optimal if and only if a measure µ derived from the buyer's type distribution satisfies certain stochastic dominance conditions.This measure expresses the marginal change in the seller's revenue under marginal changes in the rent paid to subsets of buyer types.As a corollary, we characterize the optimality of grand-bundling mechanisms, strengthening several results in the literature, where only sufficient optimality conditions have been derived.As an application, we show that the optimal mechanism for n independent uniform items each supported on [c, c + 1] is a grand-bundling mechanism, as long as c is sufficiently large, extending Pavlov's result for 2 items [Pav11].At the same time, our characterization also implies that, for all c and for all sufficiently large n, the optimal mechanism for n independent uniform items supported on [c, c + 1] is not a grand bundling mechanism.

View PDF Chat

Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms

2017-06-20

Johannes Brustle , Yang Cai , Fa Wu +1 more

We design simple mechanisms to approximate the Gains from Trade (GFT) in two-sided markets with multiple unit-supply sellers and multiple unit-demand buyers. A classical impossibility result by Myerson and Satterthwaite … We design simple mechanisms to approximate the Gains from Trade (GFT) in two-sided markets with multiple unit-supply sellers and multiple unit-demand buyers. A classical impossibility result by Myerson and Satterthwaite showed that even with only one seller and one buyer, no Bayesian Incentive Compatible (BIC), Individually Rational (IR), and Budget-Balanced (BB) mechanism can achieve full GFT (trade whenever buyer's value is higher than the seller's cost). The same paper also proposed the ``second-best'' mechanism that maximizes the GFT subject to BIC, IR, and BB constraints, which is unfortunately rather complex for even the single-seller single-buyer case. Our mechanism is simple, BIC, IR, and BB and achieves 1/2 of the optimal GFT among all BIC, IR, and BB mechanisms. The result holds for arbitrary distributions of the buyers' and sellers' values and can accommodate any downward-closed feasibility constraints over the allocations. The analysis of our mechanism is facilitated by extending the Cai-Weinberg-Devanur duality framework to two-sided markets.

View PDF Chat

The Value of Information Concealment

2018-01-01

Hu Fu , Christopher Liaw , Pinyan Lu +1 more

We consider a revenue optimizing seller selling a single item to a buyer, on whose private value the seller has a noisy signal. We show that, when the signal is … We consider a revenue optimizing seller selling a single item to a buyer, on whose private value the seller has a noisy signal. We show that, when the signal is kept private, arbitrarily more revenue could potentially be extracted than if the signal is leaked or revealed. We then show that, if the seller is not allowed to make payments to the buyer and if the value distribution conditioning on each signal is regular, the gap between the two is bounded by a multiplicative factor of 3. We give examples showing that both conditions are necessary for a constant bound on the gap to hold.We connect this scenario to multi-bidder single-item auctions where bidders' values are correlated. Similarly to the setting above, we show that the revenue of a Bayesian incentive compatible, ex post individually rational auction can be arbitrarily larger than that of a dominant strategy incentive compatible auction, whereas the two are no more than a factor of 5 apart if the auctioneer never pays the bidders and if the distribution is jointly regular. The upper bounds in both settings degrade gracefully when the distribution is a mixture of a small number of regular distributions.

View PDF Chat

Third-Party Data Providers Ruin Simple Mechanisms

2018-01-01

Yang Cai , Federico Echenique , Hu Fu +3 more

Motivated by the growing prominence of third-party data providers in online marketplaces, this paper studies the impact of the presence of third-party data providers on mechanism design. When no data … Motivated by the growing prominence of third-party data providers in online marketplaces, this paper studies the impact of the presence of third-party data providers on mechanism design. When no data provider is present, it has been shown that simple mechanisms are "good enough" -- they can achieve a constant fraction of the revenue of optimal mechanisms. The results in this paper demonstrate that this is no longer true in the presence of a third-party data provider who can provide the bidder with a signal that is correlated with the item type. Specifically, even with a single seller, a single bidder, and a single item of uncertain type for sale, the strategies of pricing each item-type separately (the analog of item pricing for multi-item auctions) and bundling all item-types under a single price (the analog of grand bundling) can both simultaneously be a logarithmic factor worse than the optimal revenue. Further, in the presence of a data provider, item-type partitioning mechanisms---a more general class of mechanisms which divide item-types into disjoint groups and offer prices for each group---still cannot achieve within a $\log \log$ factor of the optimal revenue. Thus, our results highlight that the presence of a data-provider forces the use of more complicated mechanisms in order to achieve a constant fraction of the optimal revenue.

View PDF Chat

The Complexity of Optimal Mechanism Design

2013-12-18

Constantinos Daskalakis , Alan Deckelbaum , Christos Tzamos

Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central … Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless zpp ⊇ P#P. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated.We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint.

View PDF Chat

Bounding the menu-size of approximately optimal auctions via optimal-transport duality

2018-06-20

Yannai A. Gonczarowski

The question of the minimum menu-size for approximate (i.e., up-to-ε) Bayesian revenue maximization when selling two goods to an additive risk-neutral quasilinear buyer was introduced by Hart and Nisan [2013], … The question of the minimum menu-size for approximate (i.e., up-to-ε) Bayesian revenue maximization when selling two goods to an additive risk-neutral quasilinear buyer was introduced by Hart and Nisan [2013], who give an upper bound of O(1/ε4) for this problem. Using the optimal-transport duality framework of Daskalakis, Deckelbaum, and Tzamos [2013, 2015], we derive the first lower bound for this problem — of Ω(1/∜ε), even when the values for the two goods are drawn i.i.d. from "nice" distributions, establishing how to reason about approximately optimal mechanisms via this duality framework. This bound implies, for any fixed number of goods, a tight bound of Θ(log1/ε) on the minimum deterministic communication complexity guaranteed to suffice for running some approximately revenue-maximizing mechanism, thereby completely resolving this problem. As a secondary result, we show that under standard economic assumptions on distributions, the above upper bound of Hart and Nisan [2013] can be strengthened to O(1/ε2).

View PDF Chat

Approximate revenue maximization with multiple items

2017-09-20

Sergiu Hart , Noam Nisan

View PDF Chat

On the Competition Complexity of Dynamic Mechanism Design

2018-01-01

Siqi Liu , Alexandros Psomas

The Competition Complexity of an auction measures how much competition is needed for the revenue of a simple auction to surpass the optimal revenue. A classic result from auction theory … The Competition Complexity of an auction measures how much competition is needed for the revenue of a simple auction to surpass the optimal revenue. A classic result from auction theory by Bulow and Klemperer [11], states that the Competition Complexity of VCG, in the case of n i.i.d. buyers and a single item, is 1. In other words, it is better to invest in recruiting one extra buyer and run a second price auction than to invest in learning exactly the buyers' underlying distribution and run the revenue-maximizing auction tailored to this distribution.In this paper we study the Competition Complexity of dynamic auctions. Consider the following problem: a monopolist is auctioning off m items in m consecutive stages to n interested buyers. A buyer realizes her value for item k in the beginning of stage k. How many additional buyers are necessary and sufficient for a second price auction at each stage to extract revenue at least that of the optimal dynamic auction? We prove that the Competition Complexity of dynamic auctions is at most 3n - and at least linear in n - even when the buyers' values are correlated across stages, under a monotone hazard rate assumption on the stage (marginal) distributions. This assumption can be relaxed if one settles for independent stages. We also prove results on the number of additional buyers necessary for VCG at every stage to be an α-approximation of the optimal revenue; we term this number the α-approximate Competition Complexity. For example, under the same mild assumptions on the stage distributions we prove that one extra buyer suffices for a -approximation. As a corollary we provide the first results on prior-independent dynamic auctions. This is, to the best of our knowledge, the first nontrivial positive guarantees for simple ex-post IR dynamic auctions for correlated stages.A key step towards proving bounds on the Competition Complexity is getting a good benchmark/upper bound to the optimal revenue. To this end, we extend the recent duality framework of [14] to dynamic settings. As an aside to our approach we obtain a revenue non-monotonicity lemma for dynamic auctions, which may be of independent interest.

View PDF Chat

Learning Multi-Item Auctions with (or without) Samples

2017-10-01

Yang Cai , Constantinos Daskalakis

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of bidder valuations including unit-demand, additive, constrained additive, XOS, and … We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of bidder valuations including unit-demand, additive, constrained additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly studied setting where sample access to the bidders' distributions over valuations is given, for both regular distributions and arbitrary distributions with bounded support. Here, our algorithms require polynomially many samples in the number of items and bidders. The second is a more general max-min learning setting that we introduce, where we are given "approximate distributions," and we seek to compute a mechanism whose revenue is approximately optimal simultaneously for all "true distributions" that are close to the ones we were given. These results are more general in that they imply the sample-based results, and are also applicable in settings where we have no sample access to the underlying distributions but have estimated them indirectly via market research or by observation of bidder behavior in previously run, potentially non-truthful auctions. All our results hold for valuation distributions satisfying the standard (and necessary) independence-across-items property. They also generalize and improve upon recent works of Goldner and Karlin [25] and Morgenstern and Roughgarden [32], which have provided algorithms that learn approximately optimal multi-item mechanisms in more restricted settings with additive, subadditive and unit-demand valuations using sample access to distributions. We generalize these results to the complete unit-demand, additive, and XOS setting, to i.i.d. subadditive bidders, and to the max-min setting. Our results are enabled by new uniform convergence bounds for hypotheses classes under product measures. Our bounds result in exponential savings in sample complexity compared to bounds derived by bounding the VC dimension and are of independent interest.

View PDF Chat

99% Revenue via Enhanced Competition

2018-06-11

Michal Feldman , Ophir Friedler , Aviad Rubinstein

A sequence of recent studies show that even in the simple setting of a single seller and a single buyer with additive, independent valuations over m items, the revenue-maximizing mechanism … A sequence of recent studies show that even in the simple setting of a single seller and a single buyer with additive, independent valuations over m items, the revenue-maximizing mechanism is prohibitively complex. This problem has been addressed using two main approaches: Approximation: the best of two simple mechanisms (sell each item separately, or sell all the items as one bundle) gives 1/6 of the optimal revenue [1]. Enhanced competition: running the simple VCG mechanism with additional m buyers extracts at least the optimal revenue in the original market [17]. Both approaches, however, suffer from severe drawbacks: On the one hand, losing 83% of the revenue is hardly acceptable in any application. On the other hand, attracting a linear number of new buyers may be prohibitive. We show that by combining the two approaches one can achieve the best of both worlds. Specifically, for any constant ε one can obtain a (1-ε) fraction of the optimal revenue by running simple mechanisms --- either selling each item separately or selling all items as a single bundle --- with substantially fewer additional buyers: logarithmic, constant, or even none in some cases.

View PDF Chat

A Simple Mechanism for a Budget-Constrained Buyer

2018-01-01

Yu Cheng , Nick Gravin , Kamesh Munagala +1 more

View PDF Chat

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer

2018-01-01

Xi Chen , George Matikas , Dimitris Paparas +1 more

We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly, … We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly, even when the optimal solution is guaranteed to be of a very simple kind: the seller picks a price for each individual item and a price for the grand bundle of all the items; the buyer can purchase either the grand bundle at its given price or any subset of items at their total individual prices. The following problems are also #P-hard, as immediate corollaries of the proof:1.determining if individual item pricing is optimal for a given instance,2.determining if grand bundle pricing is optimal, and3.computing the optimal (deterministic) revenue.On the positive side, we show that when the distributions are i.i.d. with support size 2, the optimal revenue obtainable by any mechanism, even a randomized one, can be achieved by a simple solution of the above kind (individual item pricing with a discounted price for the grand bundle) and furthermore, it can be computed in polynomial time. The problem can be solved in polynomial time too when the number of items is constant.

View PDF Chat