Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders
84
0
0.0
(
0
)
Added by
Ophir Friedler
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A seminal result of Bulow and Klemperer [1989] demonstrates the power of competition for extracting revenue: when selling a single item to $n$ bidders whose values are drawn i.i.d. from a regular distribution, the simple welfare-maximizing VCG mechanism (in this case, a second price-auction) with one additional bidder extracts at least as much revenue in expectation as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a {em prior-independent} mechanism, where the seller possesses no information about the distribution, and yet, by recruiting one additional bidder it performs better than any prior-dependent mechanism tailored exactly to the distribution at hand (without the additional bidder). In this work, we establish the first {em full Bulow-Klemperer} results in {em multi-dimensional} environments, proving that by recruiting additional bidders, the revenue of the VCG mechanism surpasses that of the optimal (possibly randomized, Bayesian incentive compatible) mechanism. For a given environment with i.i.d. bidders, we term the number of additional bidders needed to achieve this guarantee the environments {em competition complexity}. Using the recent duality-based framework of Cai et al. [2016] for reasoning about optimal revenue, we show that the competition complexity of $n$ bidders with additive valuations over $m$ independent, regular items is at most $n+2m-2$ and at least $log(m)$. We extend our results to bidders with additive valuations subject to downward-closed constraints, showing that these significantly more general valuations increase the competition complexity by at most an additive $m-1$ factor. We further improve this bound for the special case of matroid constraints, and provide additional extensions as well.
rate research
Read More
We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non-trivial approximation ratio of $O(log^2 m)$ [STOC06], where $m$ is the number of items. This was subsequently improved to $O(log mlog log m)$ [Dobzinski, APPROX07] and then to $O(log m)$ [Krysta and Vocking, ICALP12]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of $O(sqrt {log m})$. Similarly to previous constructions, our mechanism uses polynomially many value and demand queries, and in fact provides the same approximation ratio for the larger class of XOS (a.k.a. fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although in general computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive.
We consider the problem of welfare maximization in two-sided markets using simple mechanisms that are prior-independent. The Myerson-Satterthwaite impossibility theorem shows that even for bilateral trade, there is no feasible (IR, truthful, budget balanced) mechanism that has welfare as high as the optimal-yet-infeasible VCG mechanism, which attains maximal welfare but runs a deficit. On the other hand, the optimal feasible mechanism needs to be carefully tailored to the Bayesian prior, and is extremely complex, eluding a precise description. We present Bulow-Klemperer-style results to circumvent these hurdles in double-auction markets. We suggest using the Buyer Trade Reduction (BTR) mechanism, a variant of McAfees mechanism, which is feasible and simple (in particular, deterministic, truthful, prior-independent, anonymous). First, in the setting where buyers and sellers values are sampled i.i.d. from the same distribution, we show that for any such market of any size, BTR with one additional buyer whose value is sampled from the same distribution has expected welfare at least as high as the optimal in the original market. We then move to a more general setting where buyers values are sampled from one distribution and sellers from another, focusing on the case where the buyers distribution first-order stochastically dominates the sellers. We present bounds on the number of buyers that, when added, guarantees that BTR in the augmented market have welfare at least as high as the optimal in the original market. Our lower bounds extend to a large class of mechanisms, and all of our results extend to adding sellers instead of buyers. In addition, we present positive results about the usefulness of pricing at a sample for welfare maximization in two-sided markets under the above two settings, which to the best of our knowledge are the first sampling results in this context.
We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the government) can choose a number of licenses to put up for auction, and wishes to maximize the societal welfare: the total economic value of the buyers minus the social cost. Motivated by emission license markets deployed in practice, we focus on uniform price auctions with a price floor and/or price ceiling. The seller has distributional information about the market, and their goal is to tune the auction parameters to maximize expected welfare. The target benchmark is the maximum expected welfare achievable by any such auction under truth-telling behavior. Unfortunately, the uniform price auction is not truthful, and strategic behavior can significantly reduce (even below zero) the welfare of a given auction configuration. We describe a subclass of safe-price auctions for which the welfare at any Bayes-Nash equilibrium will approximate the welfare under truth-telling behavior. We then show that the better of a safe-price auction, or a truthful auction that allocates licenses to only a single buyer, will approximate the target benchmark. In particular, we show how to choose a number of licenses and a price floor so that the worst-case welfare, at any equilibrium, is a constant approximation to the best achievable welfare under truth-telling after excluding the welfare contribution of a single buyer.
We study the problem of selling a good to a group of bidders with interdependent values in a prior-free setting. Each bidder has a signal that can take one of $k$ different values, and her value for the good is a weakly increasing function of all the bidders signals. The bidders are partitioned into $ell$ expertise-groups, based on how their signal can impact the values for the good, and we prove upper and lower bounds regarding the approximability of social welfare and revenue for a variety of settings, parameterized by $k$ and $ell$. Our lower bounds apply to all ex-post incentive compatible mechanisms and our upper bounds are all within a small constant of the lower bounds. Our main results take the appealing form of ascending clock auctions and provide strong incentives by admitting the desired outcomes as obvious ex-post equilibria.
We study the problem of finding personalized reserve prices for unit-demand buyers in multi-unit eager VCG auctions with correlated buyers. The input to this problem is a dataset of submitted bids of $n$ buyers in a set of auctions. The goal is to find a vector of reserve prices, one for each buyer, that maximizes the total revenue across all auctions. Roughgarden and Wang (2016) showed that this problem is APX-hard but admits a greedy $frac{1}{2}$-approximation algorithm. Later, Derakhshan, Golrezai, and Paes Leme (2019) gave an LP-based algorithm achieving a $0.68$-approximation for the (important) special case of the problem with a single-item, thereby beating greedy. We show in this paper that the algorithm of Derakhshan et al. in fact does not beat greedy for the general multi-item problem. This raises the question of whether or not the general problem admits a better-than-$frac{1}{2}$ approximation. In this paper, we answer this question in the affirmative and provide a polynomial-time algorithm with a significantly better approximation-factor of $0.63$. Our solution is based on a novel linear programming formulation, for which we propose two different rounding schemes. We prove that the best of these two and the no-reserve case (all-zero vector) is a $0.63$-approximation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
