Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Empirical Revenue Maximization in Single-Parameter Auction Environments
93
0
0.0
(
0
)
Added by
Yannai A. Gonczarowski
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.
rate research
Read More
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 by 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.
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.
What fraction of the potential social surplus in an environment can be extracted by a revenue-maximizing monopolist? We investigate this problem in Bayesian single-parameter environments with independent private values. The precise answer to the question obviously depends on the particulars of the environment: the feasibility constraint and the distributions from which the bidders private values are sampled. Rather than solving the problem in particular special cases, our work aims to provide universal lower bounds on the revenue-to-welfare ratio that hold under the most general hypotheses that allow for non-trivial such bounds. Our results can be summarized as follows. For general feasibility constraints, the revenue-to-welfare ratio is at least a constant times the inverse-square-root of the number of agents, and this is tight up to constant factors. For downward-closed feasibility constraints, the revenue-to-welfare ratio is bounded below by a constant. Both results require the bidders distributions to satisfy hypotheses somewhat stronger than regularity; we show that the latter result cannot avoid this requirement.
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 samples) and the classic economic approach of average-case analysis for a given Bayesian prior (conceptually corresponding to the number of samples tending to infinity). Nonetheless, the two directions studied so far are two extreme and almost diametrically opposed directions: that of asymptotic results where the number of samples grows large, and that where only a single sample is available. In this paper, we take a first step toward understanding the middle ground that bridges these two approaches: that of a fixed number of samples greater than one. In a variety of contexts, we ask what is possibly the most fundamental question in this direction: are two samples really better than one sample?. We present a few surprising negative results, and complement them with our main result: showing that the worst-case, over all regular distributions, expected-revenue guarantee of the Empirical Revenue Maximization algorithm given two samples is greater than that of this algorithm given one sample. The proof is technically challenging, and provides the first result that shows that some deterministic mechanism constructed using two samples can guarantee more than one half of the optimal revenue.
The design of revenue-maximizing auctions with strong incentive guarantees is a core concern of economic theory. Computational auctions enable online advertising, sourcing, spectrum allocation, and myriad financial markets. Analytic progress in this space is notoriously difficult; since Myersons 1981 work characterizing single-item optimal auctions, there has been limited progress outside of restricted settings. A recent paper by Dutting et al. circumvents analytic difficulties by applying deep learning techniques to, instead, approximate optimal auctions. In parallel, new research from Ilvento et al. and other groups has developed notions of fairness in the context of auction design. Inspired by these advances, in this paper, we extend techniques for approximating auctions using deep learning to address concerns of fairness while maintaining high revenue and strong incentive guarantees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
