### Abstract

One of the most fundamental problems in mechanism design is that of designing the auction that gives the optimal profit to the auctioneer. For the case that the probability distributions on the valuations of the bidders are known and independent, Myerson [15] reduces the problem to that of maximizing the common welfare by considering the virtual valuations in place of the bidders' actual valuations. The Myerson auction maximizes the seller's profit over the class of all mechanisms that are truthful and individually rational for all the bidders; however, the mechanism does not satisfy ex post individual rationality for the seller. In other words, there are examples in which for certain sets of bidder valuations, the mechanism incurs a loss. We consider the problem of merging the worst case no-deficit (or ex post seller individual rationality) condition with this average case Bayesian expected profit maximization problem. When restricting our attention to ex post incentive compatible mechanisms for this problem, we find that the Myerson mechanism is the optimal no-deficit 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 the computational side of the problem, we note that for supermodular costs the Myerson mechanism is NP-hard to compute. Furthermore, we show that for all-or-nothing costs the optimal thresholding mechanism is NP-hard to compute. Finally, we consider relaxing the ex post incentive compatibility constraint and show that there is a Bayesian incentive compatible mechanism that achieves the same expected profit as Myerson, but never incurs a loss.

Original language | English (US) |
---|---|

Title of host publication | Internet and Network Economics - Second International Workshop, WINE 2006, Proceedings |

Pages | 136-148 |

Number of pages | 13 |

DOIs | |

State | Published - Dec 1 2006 |

Event | 2nd International Workshop on Internet and Network Economics, WINE 2006 - Patras, Greece Duration: Dec 15 2006 → Dec 17 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4286 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 2nd International Workshop on Internet and Network Economics, WINE 2006 |
---|---|

Country | Greece |

City | Patras |

Period | 12/15/06 → 12/17/06 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Bayesian optimal no-deficit mechanism design'. Together they form a unique fingerprint.

## Cite this

*Internet and Network Economics - Second International Workshop, WINE 2006, Proceedings*(pp. 136-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4286 LNCS). https://doi.org/10.1007/11944874_13