Mechanism Design via Machine Learning

We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or /spl beta/-approximation) algorithm for the standard algorithmic problem, we can convert it into a (1 + /spl epsi/)-approximation (or /spl beta/(1 +/spl epsi/)-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, the attribute auction problem, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a 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.

Authors

• Maria-Florina Balcan
• Avrim Blum
• Jason D. Hartline
• Yishay Mansour

Keywords

• Machine learning
• Pricing
• Computer science
• Algorithm design and analysis
• Machine learning algorithms
• Marketing and sales
• Measurement standards
• Cost accounting
• Writing
• Automobiles
• Mechanical Design
• Estimation Algorithm
• Complex Class
• Estimation Problem
• Design Problem
• Bidding
• Algorithm For Problem
• Classical Solution
• Learning Perspective
• Pricing Problem
• Random Sampling
• Cost Function
• Set Of Functions
• Optimal Function
• Functional Class
• Data Privacy
• Interesting Case
• Public Information
• Tree Nodes
• Optimal Price
• Structural Risk Minimization
• Unlimited Supply
• Small Class
• Exact Algorithm
• Multicast
• Optimal Profit
• Subtree
• Simple Algebra
• Prices Of Items