CS / ORIE
Tuesday, April 8th, 2003
B17 Upson Hall
University of Washington
"Optimization in the Private Value Model"
One feature of the classical treatment of optimization problems is that the space over which the optimization is being performed, i.e., the input description of the problem, is assumed to be publicly known to the optimizer. This assumption does not always accurately represent reality, for example, in applications involving resource sharing and electronic commerce on the Internet where transactions must occur among parties with diverse and selfish interests. In such settings, the inputs to many optimizations being performed are not publicly known in advance. Instead they must be solicited from companies, computerized agents, individuals, etc. that may act selfishly to promote their own self-interests. In particular, they may lie about their values or may not adhere to specified protocols if it benefits them.
In this talk, I will review the private value model solution concept of truthful mechanism design. Then I will discuss the fundamental private value optimization problem of designing truthful auctions that maximize the profit of the auctioneer in worst case. I will give several solutions to this problem including one that is based on a general reduction from private value optimization problems to private value decision problems.