اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Menu-Size Complexity of Revenue Approximation
66
0
0.0
(
0
)
نشر من قبل
Yannai A. Gonczarowski
تاريخ النشر
2016
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Consider a monopolist selling $n$ items to an additive buyer whose item values are drawn from independent distributions $F_1,F_2,ldots,F_n$ possibly having unbounded support. Unlike in the single-item case, it is well known that the revenue-optimal selling mechanism (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. Also known is that simple mechanisms with a bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, whether an arbitrarily high fraction of the optimal revenue can be extracted via a bounded menu size remained open. We give an affirmative answer: for every $n$ and $varepsilon>0$, there exists $C=C(n,varepsilon)$ s.t. mechanisms of menu size at most $C$ suffice for obtaining $(1-varepsilon)$ of the optimal revenue from any $F_1,ldots,F_n$. We prove upper and lower bounds on the revenue-approximation complexity $C(n,varepsilon)$ and on the deterministic communication complexity required to run a mechanism achieving such an approximation.
قيم البحث
اقرأ أيضاً
The question of the minimum menu-size for approximate (i.e., up-to-$varepsilon$) 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
(frac{1}{varepsilon^4})$ for this problem. Using the optimal-transport duality framework of Daskalakis et al. (2013, 2015), we derive the first lower bound for this problem - of $Omega(frac{1}{sqrt[4]{varepsilon}})$, 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 $Theta(logfrac{1}{varepsilon})$ 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(frac{1}{varepsilon^2})$.
We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of $n$ additive bidders whose values for $m$ heterogeneous items are drawn independen
tly. For any such instance and any $varepsilon>0$, we show that it is possible to learn an $varepsilon$-Bayesian Incentive Compatible auction whose expected revenue is within $varepsilon$ of the optimal $varepsilon$-BIC auction from only polynomially many samples. Our fully nonparametric approach is based on ideas that hold quite generally, and completely sidestep the difficulty of characterizing optimal (or near-optimal) auctions for these settings. Therefore, our results easily extend to general multi-dimensional settings, including valuations that are not necessarily even subadditive, and arbitrary allocation constraints. For the cases of a single bidder and many goods, or a single parameter (good) and many bidders, our analysis yields exact incentive compatibility (and for the latter also computational efficiency). Although the single-parameter case is already well-understood, our corollary for this case extends slightly the state-of-the-art.
We analyze the revenue loss due to market shrinkage. Specifically, consider a simple market with one item for sale and $n$ bidders whose values are drawn from some joint distribution. Suppose that the market shrinks as a single bidder retires from th
e market. Suppose furthermore that the value of this retiring bidder is fixed and always strictly smaller than the values of the other players. We show that even this slight decrease in competition might cause a significant fall of a multiplicative factor of $frac{1}{e+1}approx0.268$ in the revenue that can be obtained by a dominant strategy ex-post individually rational mechanism. In particular, our results imply a solution to an open question that was posed by Dobzinski, Fu, and Kleinberg [STOC11].
We investigate revenue guarantees for auction mechanisms in a model where a distribution is specified for each bidder, but only some of the distributions are correct. The subset of bidders whose distribution is correctly specified (henceforth, the gr
een bidders) is unknown to the auctioneer. The question we address is whether the auctioneer can run a mechanism that is guaranteed to obtain at least as much revenue, in expectation, as would be obtained by running an optimal mechanism on the green bidders only. For single-parameter feasibility environments, we find that the answer depends on the feasibility constraint. For matroid environments, running the optimal mechanism using all the specified distributions (including the incorrect ones) guarantees at least as much revenue in expectation as running the optimal mechanism on the green bidders. For any feasibility constraint that is not a matroid, there exists a way of setting the specified distributions and the true distributions such that the opposite conclusion holds.
Most work in mechanism design assumes that buyers are risk neutral; some considers risk aversion arising due to a non-linear utility for money. Yet behavioral studies have established that real agents exhibit risk attitudes which cannot be captured b
y any expected utility model. We initiate the study of revenue-optimal mechanisms under buyer behavioral models beyond expected utility theory. We adopt a model from prospect theory which arose to explain these discrepancies and incorporates agents under-weighting uncertain outcomes. In our model, an event occurring with probability $x < 1$ is worth strictly less to the agent than $x$ times the value of the event when it occurs with certainty. In contrast to the risk-neutral setting, the optimal mechanism may be randomized and appears challenging to find, even for a single buyer and a single item for sale. Nevertheless, we give a characterization of the optimal mechanism which enables positive approximation results. In particular, we show that under a reasonable bounded-risk-aversion assumption, posted pricing obtains a constant approximation. Notably, this result is risk-robust in that it does not depend on the details of the buyers risk attitude. Finally, we examine a dynamic setting in which the buyer is uncertain about his future value. In contrast to positive results for a risk-neutral buyer, we show that the buyers risk aversion may prevent the seller from approximating the optimal revenue in a risk-robust manner.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
