BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-99-88
       ENTRY:: July 12, 1999
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Truth Revelation in Rapid, Approximately Efficient
               Combinatorial Auctions
        TYPE:: Technical Note
      AUTHOR:: Lehmann, Daniel
      AUTHOR:: O'Callaghan, Liadan Ita
      AUTHOR:: Shoham, Yoav
        DATE:: July 1999
       PAGES:: 33
    ABSTRACT:: Some important classical mechanisms considered in
               Microeconomics and Game Theory require the solution of a
               difficult optimization problem. This is true of mechanisms
               for combinatorial auctions, which have in recent years
               assumed practical importance, and in particular of the gold
               standard for combinatorial auctions, the Generalized Vickrey
               Auction (GVA). Traditional analysis of these mechanisms - in
               particular, their truth revelation properties - assumes that
               the optimization problems are solved precisely. In reality,
               these optimization problems can usually be solved only in an
               approximate fashion. We investigate the impact on such
               mechanisms of replacing exact solutions by approximate ones.
               Specifically, we look at a particular greedy optimization
               method, which has empirically been shown to perform well. We
               show that the GVA payment scheme does not provide for a truth
               revealing mechanism. We introduce another scheme that does
               guarantee truthfulness for a restricted class of players. We
               demonstrate the latter property by identifying sufficient
               conditions for a combinatorial auction to be truth-revealing,
               conditions which have applicability beyond the specific
               auction studied here.
       NOTES:: [Adminitrivia V1/Prg/19990712]
         END:: STAN//CS-TN-99-88