DIMACS Workshop on Computational Issues in Auction Design

October 7 - 8, 2004
DIMACS Center, CoRE Building, Rutgers University

Organizers:: Jayant Kalagnanam, IBM Watson Lab, jayant@us.ibm.com; Eric Maskin, School of Social Science, Institute for Advanced Study, maskin@ias.edu; David Parkes, Harvard University, parkes@eecs.harvard.edu; Aleksandar Pekec, Fuqua School of Business, Duke University, pekec@duke.edu; Michael Rothkopf, Rutgers University, rothkopf@rutcor.rutgers.edu

Presented under the auspices of the Special Focus on Computation and the Socio-Economic Sciences.

Workshop Program:

Thursday, October 7, 2004 

 8:00 -  8:30  Registration and Breakfast - CoRE Building, 4th Floor

 8:30 -  8:45  Welcome and Opening Remarks
               Fred Roberts, DIMACS Director

 8:45 -  9:30  Characterizing Dominant Strategy Mechanisms with Multi-dimensional types
               Rakesh Vohra, Northwestern

 9:30 - 10:10  Multi-Item Auctions with Credit Limits
               Shmuel Oren and Shehzad Wadalawala, UC Berkeley

10:10 - 10:30  Break

10:30 - 11:15  Approximation Algorithms for Truthful Mechanisms
               Eva Tardos, Cornell
             
11:15 - 11:55  Tolls for heterogeneous selfish users in multicommodity
               generalized congestion games
               Lisa Fleischer, IBM Watson Research, Kamal Jain, MSR and 
               Mohammad Mahdian, MIT

11:55 - 12:35  VCG Overpayment in Random Graphs
               Evdokia Nikolova and  David Karger, MIT

12:35 -  2:00  Lunch

 2:00 -  2:45  The communication requirements of social
               choice rules and supporting budget sets
               Ilya Segal, Stanford University

 2:45 -  3:25  The communication complexity of the private
               value single item bisection auction
               Elena Grigorieva,  P Jean-Jacques Herings, Rudolf Muller, and
	       Dries Vermeulen, University Maastricht, the Netherlands

 3:25 -  3:45  Break

 3:45 -  4:30  Market Mechanisms for Redeveloping Spectrum
               Evan Kwerel, FCC

 4:30 -  5:15  Issues in Electricity Market Auction Design
               Richard O'Neill, FERC

 5:15 -  6:15  Panel

 6:30          Dinner

Friday, October 8, 2004

 8:00 -  8:30  Breakfast and Registration

 8:30 -  9:15  The Limits of Ex Post Implementation Revisted
               Sushil Bikhchandani, UCLA
             
 9:15 - 10:00  The Over-Concentrating Nature of Simultaneous Ascending Auctions
               Charles Zheng, Northwestern University

10:00 - 10:20  Break

10:20 - 11:00  Designing Auction Protocols under Asymmetric Information on
               Nature's Selection
               Takayuki Ito, Nagoya Inst.,  Makoto Yokoo, Kyushu and
               Shigeo Matsubara, NTT

11:00 - 11:40  Elicitation in combinatorial auctions with restricted 
               preferences and bounded interdependency between items
               Vincent Conitzer and Tuomas Sandholm, Carnegie Mellon University, and
               Paolo Santi, Pisa University
               
11:40 - 12:20  Applying learning algorithms to preference elicitation
               in combinatorial auctions
               Sebastien Lahaie and David C. Parkes, Harvard

12:20 -  1:30  Lunch


 1:30 -  2:15  To auction or not? Historical perspectives on the development
               of ecommerce
               Andrew Odlyzko, University of Minnesota

 2:15 -  2:55  Non-computational Approaches to Mitigating Computational Problems
               in Combinatorial Auctions
               Sasa Pekec, Duke University and Michael Rothkopf, Rutgers University

 2:55 -  3:15  Break

 3:15 -  3:55  The Clock-Proxy Auction: A Practical Combinatorial Auction Design
               Peter Cramton and Lawrence M.Ausubel, University of Maryland and
	       Paul Milgrom, Stanford University

 3:55 -  4:35  Generation and Selection of Core Outcomes in Sealed Bid
               Combinatorial Auctions
               Bob Day and S Raghavan, University of Maryland

 4:35 -  5:15  Eliciting Bid Taker Non-price Preferences
               in (Combinatorial) Auctions
               Craig Boutilier, University of Toronto, Tuomas Sandholm, Carnegie Mellon University 
               and Rob Shields, CombineNet

Poster Presentations:

Methods for boosting revenue in Combinatorial Auctions
Anton Likhodedov and Tuomas Sandholm, Carnegie Mellon University

Arbitrage in Combinatorial Exchanges
Andrew Gilpin and Tuomas Sandholm, Carnegie Mellon University

Optimal Auctions with Finite Support
Edith Elkind, Princeton University

Optimal Distributed Protocols for Generalized Job Shop
Scheduling Problems via Ascending Combinatorial Auctions
Judy Geng and Roy Kwon, University of Toronto

Negotiation-Range Mechanisms: Coalition-Resistant Markets
Rica Gonen, Hebrew University

A Bidder Aid Tool for Dynamic Package Creation in the FCC Spectrum Auctions
Karla Hoffman, GMU, Dinesh Menon and Susara A. van den Heever, Decision Analytics

An Exact Algorithm for Procurement Problems under a Total Quantity Discount Structure
D.Goossens, A.Maas, F.C.R. Spieksma, and J.J van de Klundert, Maastricht U. and Katholieke U. Leuven

Approximation Algorithms for CAs with Complement-Free Bidders
Shahar Dobzinski, Noam Nisan, Michael Schapira, The Hebrew University, University of Jerusalum