CS 886 Electronic Market Design Kate Larson School of Computer Science University of Waterloo What is electronic market design? Building the next eBay? Possibly Designing software agents for the stock market? Possibly

Study the economic foundations of market design (game theory and mechanism design) Study computational issues that arise in market design Study the interaction between GT/MD and computation Why now? Fast computers and high bandwidth have changed the cost of dynamic market mechanisms Automated winner determination Automated bidding using software agents Distributed bidders

Standardized ontologies (ie. XML) Ability to exchange structured information Able to construct new markets Historical Perspective* Nash (1950): General definition of equilibrium for large class of games, proof of existence. [Nobel prize 1994] the analytic structure for studying all situations of conflict and cooperation(Myerson99) Vickrey (1961): Birth of auction theory [Nobel prize 1996] FCC Spectrum auction ($100B by 2001)

Many other countries followed More and more practical applications MarketDesign, CombineNet, FreeMarkets, Frictionless Used within CS to design and study networked systems . *Shamelessly borrowed from D. Parkes Two communities Economics Traditional emphasis on game theoretic rationality Describing how agents should

behave Multiple selfinterested agents Computer Science Traditional emphasis on computational and informational constraints Building agents Individual or cooperative agents Resolve conflicts between game-theoretic and computational constraints, develop theories and methodologies

Lots of excitement! Fifth ACM Electronic Commerce Conference, May 2004 Market clearing algorithms, mechanism design, preference elicitation, reputation, economic models for getting rid of spam Workshop on Agent Mediated Electronic Commerce, July 2004 Radcliffe Institute Workshop on Preferences and Computation, May 2004 FCC Combinatorial Bidding Conference, Nov 2003 Dagstuhl Workshop on Electronic Market Design, 2002 (another one soon)

Many papers appearing in AAAI, AAMAS, STOC, FOCS, SODA, This Course Introduced to the state-of-art in electronic market design Game theoretic issues Computational issues The intersection Course structure Introductory lectures [until September 29] Current research papers Combinatorial auctions (WDP, approximation issues, falsename bids, bidding languages, iterative auctions)

Preference elicitation and communication complexity Reputation mechanisms Bidding agents Selling digital goods Applications Prerequisites Students must be comfortable with mathematical proofs Background in algorithms and complexity (for example, CS 466) Ideally an AI course (for example CS 486) must be comfortable with agent rationality concepts I will cover all game theory and

mechanism design required Grading 2-3 assignments on game theory and mechanism design 10% In class presentation(s) 20% Peer-reviewed Class participation 20% Research project 50% Presentations Each student is responsible for presenting a research paper in class Short survey + a critique

Everyone in class will provide feedback on the presentation Marks will be given on coverage of the material + organization + presentation Class Participation Students should participate! Before each class (midnight the day before) student must email me a list of comments on the paper to be presented

What is the main contribution? Is it important? Why? What assumptions are made? What applications might arise from the results? How can it be extended? What was unclear? Projects Goal of the project is to develop a deep understanding of a topic related to electronic market design

Topic is open Theoretical, experimental, in depth literature review, Can be related to your own research If you have troubles coming up with a topic, come talk to me Proposals due October 20th Final project due December 6th Students will present projects in class Other Important Information Office Hours: Wednesday 2:30-3:30

Course webpage http://www.cs.uwaterloo.ca/~klarson/teaching/F04886 Readings and schedule will soon be finalized An Example London Bus System (as of April 2004) 5 million passengers each day 7500 buses 700 routes The system has been privatized since

1997 by using competitive tendering Idea: Run an auction to allocate routes to companies The Generalized Vickrey Auction (VCG mechanism) Let G be set of all routes, I be set of bidders Agent i submits bids vi*(S) for all bundles SG Compute allocation S* to maximize sum of reported bids V*(I)=max(S1,,SI)ivi*(Si) Compute best allocation without each agent i: V*(I\i)=max(S1,,SI)jivi*(Si)

Allocate each agent Si*, each agent pays P(i)=vi*(Si*)-[V*(I)-V*(I\i)] Example cont. Mechanism: Generalized Vickrey auction (GVA) Specifies the rules Describes how outcome will be determined Strategies: Policies which specify what actions an agent should take Agents are free to take any allowable action (ie. Specify any amount for each bid) Assume self-interested rational agents (ie select

strategies which maximize their own utility) GVA is efficient and strategyproof! But. There are some computational issues Winner determination problem: selecting bids to maximize reported value is NP-hard Equivalent to maximum weighted set packing Solve this problem I+1 times (for payments) Agent valuation problem: For each combination of routes, an agent has to compute its value for getting them (exponential number)

Communication complexity: Each agent has to communicate 2700 bids to the auctioneer It might be too difficult to find and execute the optimal strategy (chess) Tractable Winner Determination Restricted bidding languages [Rothfkopf et al 98, Vohra & de Vries 00] Limited bid prices Limited bundle types

Implement approximate solutions to the WDP Care must be taken approximations can change the incentive properties of the mechanism Change the mechanism [Lehmann et al 02] Distribute computation to agents Agent Valuation Problem Explicitly include the valuation problem into the model Use dynamic methods Ask for some information and perform intermediate computation, ask for

more information if required Preference Elicitation and Communication Complexity Sometimes complete information is not necessary! Single item: v1=4, v2=8, v3=12 Only need to know v2=8, v1<8 and v3>8 Combinatorial

auction: Non-overlapping bids 4 2 7 1 We can compute and check the efficient outcome in both cases Overview of Initial Lectures

1. Introduction (today) 2. Introduction to Game Theory normal and extensive form games, dominant strategy, Nash equil, Bayesian-Nash equil 3. Introduction to Social Choice Theory Voting protocols, voting paradoxes, Arrows thm 4. Mechanism Design (I)

Implementation, Revelation principle, Gibbard-Satterthwaite Thm, VCG mechanism 5. Mechanism Design (II) 6. Auctions Auctioning a single item, private and common values, Revenue equivalence thm Other topics Combinatorial auctions

Winner determination problem Approximations Bidding Languages Iterative Auctions Other Topics Preference elicitation False name bidding New form of cheating in Internet auctions Selling digital goods Agents

Trading agents (TAC) Computationally limited agents Other topics Reputation mechanisms eBay and others Automated mechanism design Applications Scheduling Avoiding spam P2P