|
Competitive Auctions |
|
 CSE Home |
About Us |
Search |
Contact Info |
|
|
Research OverviewMany optimization problems involve a cost or profit model where cost must be minimized or profit maximized. An example is the prize collecting Stiener tree problem. The goal of which is to maximize the prize collected from vertices in a graph while minimizing the cost of tree edges that span these vertices. Such optimization problems are well studied for the case where the the values being optimized over are public values known to the algorithm.When some of the values optimized over are private traditional algorithms fail to give optimal performance. Selfish agents asked to supply values to an algorithm may give incorrect values in attempt to manipulate the solution to their own end. This introduces an Economic and Game Theoretic twist to many standard Computer Science problems. Following a standard approach from the field of mechanism design, we consider mechanisms designed such that each agents best strategy is to reveal their true value. Such mechanisms are truthful (a.k.a., strategy-proof or incentive compatible). Our focus is on truthful mechanism for optimization problems. One of the simplest private value optimization problems is that of basic auctions. Consider the case where identical items are available in unlimited supply (i.e., every bidder can be be sold an item). We are interested in auctions that are truthful and maximize the profit of the seller. We use a competitive analysis, similar to that of online algorithms, to measure the performance of truthful mechanisms for private values against that of the optimal public value mechanisms. A mechanism is competitive if it achieves a constant fraction of the optimal in worst case. This approach, while natural in Computer Science, contrasts significantly from the traditional approach of Economists of looking for an optimal mechanism given the Bayesian priors, the probability distribution from which the private values are chosen. In the papers below, we give solutions to the basic auction problem and show how techniques from basic auctions can be generalized to solve more complicated private value optimization problems. Selected Publications
|
|||||||||||||||||
 |
Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to hartline@cs.washingtion.edu] |
