There has been much recent work on the revenue-raising properties of truthful mechanisms for selling goods to selfish bidders. Typically the revenue of a mechanism is compared against a benchmark (such as, the maximum revenue obtainable by an omniscient seller selling at a fixed price to at least two customers), with a view to understanding how much lower the mechanism's revenue is than the benchmark, in the worst case. We study this issue in the context of lotteries , where the seller may sell a probability of winning an item. We are interested in two general issues. Firstly, we aim at using the true optimum revenue as benchmark for our auctions. Secondly, we study the extent to which the expressive power resulting from lotteries, helps to improve the worst-case ratio. We study this in the well-known context of digital goods , where the production cost is zero. We show that in this scenario, collusion-resistant lotteries (these are lotteries for which no coalition of bidders exchanging side payments has an advantage in lying) are as powerful as truthful ones.
Other benchmarks are defined in the literature to compare the revenue of incentive-compatible auctions, see, e.g., @cite_4 . To the best of our knowledge, our work is the first in which revenue is compared to . However, in certain combinatorial settings, such as the one considered in e.g. @cite_10 , , as social welfare, is used as benchmark for revenue maximization.
@cite_10 @cite_4
203000141 2164143329 2952244728 1495768673
The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. (This does not fall inside the well-studied "single-parameter environment".) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space--based on the bids--and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. We show that Levin's optimal revenue can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is always more efficient. Finally, we show that the optimal revenue can be 6- approximated even if the "reserve pricing" is required to be symmetric across bidders. 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. Our basic model is a single-item auction in which bidders' valuations are drawn independently from unknown and nonidentical distributions. The seller is given m samples from each of these distributions "for free" and chooses an auction to run on a fresh sample. How large does m need to be, as a function of the number k of bidders and e 0, so that a (1 -- e)-approximation of the optimal revenue is achievable? We prove that, under standard tail conditions on the underlying distributions, m = poly(k, 1 e) samples are necessary and sufficient. Our lower bound stands in contrast to many recent results on simple and prior-independent auctions and fundamentally involves the interplay between bidder competition, non-identical distributions, and a very close (but still constant) approximation of the optimal revenue. It effectively shows that the only way to achieve a sufficiently good constant approximation of the optimal revenue is through a detailed understanding of bidders' valuation distributions. Our upper bound is constructive and applies in particular to a variant of the empirical Myerson auction, the natural auction that runs the revenue-maximizing auction with respect to the empirical distributions of the samples. To capture how our sample complexity upper bound depends on the set of allowable distributions, we introduce α-strongly regular distributions, which interpolate between the well-studied classes of regular (α = 0) and MHR (α = 1) distributions. We give evidence that this definition is of independent interest. We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan (2011) to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of (2008) and a special case of the polyhedral clinching auction of (2012). For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from (2002) for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward-closed environments. The profit maximization question is of interest even without budgets and our mechanism is a 7.5-approximation which improving on the 30.4 bound of Ha and Hartline (2012). In this paper, we introduce a novel approach for reducing the k-item n-bidder auction with additive valuation to k-item 1-bidder auctions. This approach, called the Best-Guess reduction, can be applied to address several central questions in optimal revenue auction theory such as the relative strength of simple versus complex mechanisms, the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called Deterministic Best-Guess that yields at least a constant fraction of the optimal revenue by any randomized mechanism. This also gives the first simple mechanism that achieves constant fraction optimal revenue for such multi-buyer multi-item auctions. Second, if all the nk valuation random variables are independent, the optimal revenue achievable in dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in Bayesian incentive compatibility (BIC). Third, when all the nk values are identically distributed according to a common one-dimensional distribution F, the optimal revenue is shown to be expressible in the closed form Θ(k(r + ∫0mr(1 − F(x)n)dx)) where r = supx≥0 x(1 − F(x)n) and m = lk nr; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.