Abstract:

   Computational problems that arise in game theoretical environments 
   are very different from "usual" algorithmic problems. We study a 
   fundamental problem in economics called optimal auction design: 
   A seller wishes to sell an item to a group of self-interested agents. 
   Each agent $i$ has a {\em privately} known valuation $v^i$ for the object. 
   Given a distribution on these valuations, our goal is to design an auction 
   (i.e. a protocol) that maximizes the seller's expected revenue. 
   
   We investigate this problem using tools from theoretical computer science 
   and provide the following main results: 
   
   We present a simple generic protocol that {\bf guarantees} at least 
   half of the optimal revenue.
   
   We conjecture that no deterministic polynomial auction can do much better
   and prove this for ascending auctions.
   
   We show that if the dependency between the agents is bounded, the problem
   can be approximated with a factor close to 1.
   
   We show tight bounds for the case where the designer can only sample the 
   underlying distribution or must commit to the protocol in advance.
   
   The talk is based on the following papers:
   "On approximating optimal auctions" By A. Ronen (EC 2001)
   "Optimal Auctions are Hard" By A. Ronen & A. Saberi (FOCS 2002)

   Both are available at http://iew3.technion.ac.il/~amirr/