Report on the IMA Workshop on “Mathematics and E-Auctions” December 3-5, 2000 : Report on the IMA Workshop on “Mathematics and E-Auctions” December 3-5, 2000 Clyde Monma, Chief Scientist
Mathematical Sciences Research Center
Telcordia Technologies
clyde@monma.com / (973) 829-4428
Institute for Mathematics & Its Applications (IMA) : Institute for Mathematics & Its Applications (IMA) University of Minnesota
NSF Institute (Division of Math Sciences)
Industrial Affiliates (Telcordia)
Special Years / Industrial Programs
2000-2001 Mathematics in Multimedia
2001-2002 Mathematics in Geosciences
2002-2003 Optimization
2003-2004 Probability & Statistics in Complex Systems
Mathematics & E-Auctions : Mathematics & E-Auctions Mathematical research areas
Optimization, Combinatorics & Modeling, Simulation
Game Theory, Partial Differential Equations
Participant research backgrounds
Economic Theory of Markets & Auctions
Applied Math, Operations Research, Optimization
Additional information
IMA proceedings, Fall 2001
Special Issue of Electronic Commerce Research journal on “Dynamic Pricing Issues in E-Commerce” [announcement]
Motivation : Motivation Bidding & auction theory is a very mature area of economics research, BUT …
E-Auctions & new markets offer many new research opportunities
Apply / test existing theories in practice
Extend theory in new directions
Exploit sophisticated optimization models, methods & computational power
Workshop Topics / Speakers : Workshop Topics / Speakers Auction theory & auction practice - Weber
Combinatorial auctions, FCC spectrum - Vohra, Milgrom, Dietrich, Anand
Internet auctions, eBay/Amazon, agents, pricebots – Roth, Kephart, Huang, Ledyard
Electrical power auctions - Birge
Airlines markets - van Ryzin
Modeling issues – Rothkopf (FASS, 3/2)
Auction Theory and Practice [Weber] : Auction Theory and Practice [Weber] Auctions - English, Dutch, first-price-sealed, second-price-sealed, ascending, all-pay, …
What does theory tell us?
Fairness, efficiency, Vickrey pricing, revenue equivalence, Winner’s Curse, …
What does practice show us?
Cites many interesting historical examples
Do bidders act / compete rationally?
Do bidders act independently?
Is the seller reputable / fair?
Combinatorial Auctions : Combinatorial Auctions de Vries & Vohra, “Combinatorial Auctions: A Survey" [PDF] – a good overall survey
Heterogeneous items, package bids
Types of auctions - FCC spectrum, airport time slots, railroad segments, delivery routes
Focuses on the Winner Determination Problem
Set Packing Problem
Theory, algorithms, practice, software, data, results
Exact, approximate, distributed methods
Uses structure of LP to construct auctions / pricing
Combinatorial Auctions : Combinatorial Auctions Dietrich & Kalagnanam, “Complex Markets & Combinatorial Auctions”
Indivisible, double auctions (steel & paper)
Winner Determination solved as Generalized Assignment Problem using column generation with knapsack subproblems& dual pricing
FCC auctions – Winner Determination
12 items, 50 bidders can be easily solved
FCC Spectrum Auctions : FCC Spectrum Auctions FCC spectrum rules, January 2001
FCC survey on spectrum assignment
Milgrom library of papers on FCC spectrum auctions; ascending package bidding
Roth bibliography of papers on FCC spectrum auctions
Internet Auctions : Internet Auctions Roth, “Last Minute Bidding and The Rules for Ending Second-Price Auctions” [pdf]
Interesting empirical comparison of eBay and Amazon auctions and buyer behaviors
Significantly more “sniping” on eBay, especially experienced bidders & for antiques
Fractal, scale-independent, power law bidding
Price vs probability of lost opportunity tradeoff
Internet Auctions : Internet Auctions Kephardt, “Dynamic Pricing by Software Agents”
Empirical tests comparing simple bidding agents, and compared in lab to humans
Agents can usually outbid humans!!
Airline Markets : Airline Markets Van Ryzin, “Airline Revenue Mangement & e-Markets” [PDF]
Product design, pricing, capacity allocation
Saturday night stay, advance purchase, price promotions, dynamic allocations, overbooking
Probabilistic NLP, random LP, combinatorial
New mechanisms / markets - Priceline matching, Hotwire, network auctions
Electrical Power Auctions : Electrical Power Auctions Birge, “Equilibria in Electric Power Exchange Auction Markets” [PDF]
Daily, open, multi-round spot auctions
All bids are public; adjustments allowed
Trades are at market clearing price
Equilibrium bidding strategies
Multi-stage stochastic LP
Modeling Issues : Modeling Issues Rothkopf, “Modeling Opportunities in Auctions” [paper copy]
Interesting insights, scenarios and anecdotes
Open problems / issues
Non-scalar information, budgets, sequential, asymmetry, complex bids, costs, …
FCC spectrum combinatorial auctions
Electric generation & transmission rights (CA, NY)
Demand stochastic, volatile, in-elastic (hourly)
Very complex transmission issues
Additional Resources : Additional Resources Speaker Web Home Pages
Anandalingam, Birge, Dietrich, Huang, Kephart, Ledyard, Milgrom, Roth, Rothkopf, van Ryzin, Vohra, Weber
Bibliographies – Klemperer auction theory/practice, Milgrom market design library, Roth bibliography, Wilson market design course, Friedman Internet auctions