ﻻ يوجد ملخص باللغة العربية
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 independently. 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.
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 s
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
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 str
We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneers revenue in a variety of single-parameter auction environments including
The literature on mechanism design from samples, which has flourished in recent years at the interface of economics and computer science, offers a bridge between the classic computer-science approach of worst-case analysis (corresponding to no sample