Thumbnail
Access Restriction
Open

Author Balcan, Maria-Florina ♦ Blum, Avrim ♦ Hartline, Jason D. ♦ Mansour, Yishay
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Attribute Auction Problem ♦ Unlimited-supply Combinatorial Auction ♦ Incentive-compatible Mechanism Design Problem ♦ Standard Algorithmic Problem ♦ Revenue-maximizing Pricing Problem ♦ Comparison Class ♦ Loss Function ♦ Wide Variety ♦ Machine Learning ♦ Discriminatory Pricing Problem ♦ Broad Class ♦ Appropriate Measure ♦ Digital Good ♦ Algorithmic Question ♦ Mechanism Design ♦ Several Challenge ♦ Incentive-compatible Mechanism Design
Description We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or #-approximation) algorithm for the standard algorithmic problem, we can convert it into a (1 + #)-approximation (or #(1 + #)-approximation) for the incentive-compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the comparison class of solutions. We apply these results to the problem of auctioning a digital good, to the attribute auction problem which includes a wide variety of discriminatory pricing problems, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a machine learning perspective, these settings present several challenges: in particular, the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2005-01-01
Publisher Institution IN PROC. OF THE 46TH IEEE SYMP. ON FOUNDATIONS OF COMPUTER SCIENCE