Profit Maximization in Mechanism Design: Beyond the Bayesian Approach.
详细信息
- 作者：Nguyen ; Cam Thach.
- 学历：Doctor
- 年：2011
- 导师：Karlin, Anna R.,eadvisor
- 毕业院校：University of Washington
- ISBN：9781267234988
- CBH：3501680
- Country：USA
- 语种：English
- FileSize：6283587
- Pages：163
文摘
We study the design of truthful mechanisms for maximizing a sellers profit in a variety of settings that go beyond the traditional Bayesian approach from economics: ·； Prior-free mechanism design. In the first part of this thesis, we study the problem of designing truthful mechanisms to maximize a sellers profit without prior knowledge of buyers valuations, using the competitive framework pioneered in [20] and [19], which involves defining an appropriate profit benchmark and then designing mechanisms that approximate the benchmark on every instance. Working with one of the simplest settings that was not well understood: when a seller can sell to any number of buyers in one of a number of exclusive markets, we show that the profit benchmark proposed by Hartline and Roughgarden [24] is unattainable---that is, no truthful in expectation mechanism can be constant competitive to it. On the other hand, we propose a natural, symmetrized version of this benchmark and show that it is approximable in our setting. ·； Prior-independent mechanism design. In the second part, we consider prior-independent mechanism design for unit-demand combinatorial auctions. In a these auctions, an auctioneer is selling a collection of different items to a set of agents, each has a different private value for each item and is interested in buying at most one item. We consider the problem of designing a truthful auction that maximizes the auctioneers profit. Previously, there has been progress on this problem in the Bayesian setting. Specifically, assuming the distributions of the agents valuations are known, it has been shown how to design auctions tailored to these distributions that achieve high expected profit. In our work, we present the first "prior-independent" unit-demand combinatorial auctions. These auctions are guaranteed to achieve a constant fraction of the optimal expected profit, but are designed without any knowledge of the prior distributions that the agents values come from. ·； Mechanism design in deliberative settings. Deliberative settings are those in which even the agents do not know their values with absolute certainty. Instead, they have some initial beliefs and some deliberations they can perform, at some cost to themselves, to reduce their uncertainty. We investigate a special case of the deliberative model and show that any dominant-strategy mechanism for single-item auctions in this model is equivalent to a sequential posted price mechanism, extending a result of [33]. Moreover, we give a connection between profit maximization mechanisms in deliberative and classical settings, thereby obtaining approximation mechanisms for a variety of special deliberative environments.