Thumbnail
Access Restriction
Open

Author Chawla, Shuchi ♦ Hartline, Jason ♦ Rajan, Uday ♦ Ravi, R.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Bayesian Optimal No-decit Mechanism Design ♦ Myerson Mechanism ♦ All-or-nothing Cost ♦ Supermodular Cost ♦ Single Parameter Agent Problem ♦ Probability Distribution ♦ Cient Allocation ♦ Optimal Prot ♦ Mechanism Design ♦ Average Case Bayesian ♦ Optimal No-decit Mechanism ♦ Prot Maximization Problem ♦ Ex Post Incentive Compatibility Constraint ♦ Virtual Valuation ♦ Simple Thresholding Mechanism ♦ Submodular Cost ♦ Bayesian Incentive Compatible Mechanism ♦ Arbitrary Cost Function ♦ Case No-de Cit Condition ♦ General Submodular Cost ♦ Post Incentive Compatible Mechanism ♦ Optimal Thresholding Mechanism ♦ Fundamental Problem ♦ Computational Side
Abstract One of the most fundamental problems in mechanism design is that of designing the auction that gives the optimal prot to the auctioneer. For the case that the probability distribution on the valuations of the bidders is known and independent, Myerson [13] reduces the problem to that of computing the eÆcient allocation on the bidders ' virtual valuations. We review this technique for any single parameter agent problem, i.e., where there is an arbitrary cost function on the outcome that the mechanism produces. Further, we consider the problem of merging the worst case no-de cit condition with this average case Bayesian expected prot maximization problem. When restricting our attention to ex post incentive compatible mechanisms for this problem, we nd that the Myerson mechanism is the optimal no-decit mechanism for supermodular costs, that Myerson merged with a simple thresholding mechanism is optimal for all-or-nothing costs, and that neither mechanism is optimal for general submodular costs. Addressing computational side of the problem, for supermodular costs the Myerson mechanism is hard to compute. For all-or-nothing costs we show that the optimal thresholding mechanism is NP-hard to compute. Finally, for submodular costs if we relax the ex post incentive compatibility constraint, we can specify a Bayesian incentive compatible mechanism that achieves the same expected prot as Myerson, but never has a loss. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2004-01-01