Mechanism design via machine learning

摘要: We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design standard algorithmic questions, for a wide variety revenue-maximizing pricing problems. Our reductions imply that these problems, given an optimal (or /spl beta/-approximation) algorithm the problem, we can convert it into (1 + epsi/)-approximation beta/(1 +/spl epsi/)-approximation) so long as number bidders is sufficiently large function appropriate measure complexity comparison class solutions. apply results problem auctioning digital good, attribute auction and item-pricing unlimited-supply combinatorial auctions. From perspective, settings present several challenges: particular loss discontinuous asymmetric, range bidders' valuations may be large.