|
|
 |
Tutorials
Sun, Jun 5, 2005
| 12:00 - 01:30: LUNCH BREAK |
Sun, Jun 5, 2005 - Morning
Optimal Mechanism Design without Priors - Jason Hartline
|
|
Abstract: We consider one of the fundamental economic objectives of profit maximization. For this problem traditional optimal mechanism design (e.g., Myerson, 1983) assumes that the agent types are from a known prior distribution. Unfortunately this only solves half of the problem. Where does this known prior distribution comes from? Maybe it comes from prior experience on the part of the designer. Maybe it comes from market analysis. Assuming a known prior distribution overlooks two important issues in optimal mechanism design. The first is the issue of how the market analysis affects the end performance of the mechanism, and the second is the issue of how the existence of a market analysis phase (or use of pre-existing information) affects the incentive properties of the system as a whole. This motivates explicitly assuming that the mechanism is not based on known externally provided priors, but instead must deduce distributional information on the fly. This approach was independently proposed by Baliga and Vohra, 2003; Goldberg et al., 2001; and Segal, 2003.
The work in this area falls into two major categories. The first is in analyzing the natural mechanisms that are of the form: perform market analysis on a sample of the agents to learn distributional parameters and then use this distributional information to set payments for the remaining agents, assuming they are from the same distribution (Baliga and Vohra, 2003; Goldberg et al., 2001; Segal 2003; Balcan et al., 2005). This raises two natural questions (a) how do existing machine learning techniques perform in learning the distributional information, and (b) given the distributional information, how are optimal payments computed?
The second category of work in this area is in designing mechanisms that bypass the market analysis metaphor and directly looks for ways of doing pricing and price discovery at the same time within an incentive compatible mechanism. This approach has also lead to fruitful discoveries including (a) the notion of a "decision problem" variant of the optimal mechanism design problem (Deshmukh et al., 2003), (b) several techniques for reducing the optimization problem to the decision problem (Fiat et al., 2002; Goldberg and Hartline, 2003), and (c) the observation that many optimal mechanism design problems can be reduced to the "unlimited supply" version of the problem where the auctioneer is assumed not to have supply constraints (Fiat et al., 2002; Aggarwal et al., unpublished).
We discuss the above models and results through a number of example problems. Most of the examples will be for single-round multi-unit auctions for a single item in unlimited supply when the agents are assumed to have unit demand and are a priori indistinguishable. We will also consider combinations of the above in cases with multiple items, combinatorial demand, limited supply, online arrival of agents, and/or when agents are a priori distinguishable.
Instructors: Jason's current research interests lie in the intersection of the fields of Theoretical Computer Science, Game Theory, and Economics. With the Internet developing as the single most important arena for resource sharing among parties with diverse and selfish interests, traditional algorithmic and distributed systems approaches are insufficient. Instead, in protocols for the Internet, game-theoretic and economic issues must be considered. A fundamental research endeavor in this new field is the design and analysis of auction mechanisms and pricing algorithms.
Jason joined Microsoft Research, Silicon Valley in 2004. Prior to that he was a postdoctoral research fellow at the Aladdin Center at Carnegie Mellon University. He received his Ph.D. in Computer Science from the University of Washington in 2003 with advisor Anna Karlin and B.S.s in Computer Science and Electrical Engineering from Cornell University in 1997.
|
| |
Back to top |
Sun, Jun 5, 2005 - Morning
Trading Agent Design and Analysis - Michael P. Wellman
|
|
Abstract: This tutorial will survey the state-of-the-art in developing automated trading strategies for electronic markets. Topics include trading in simple, continuous double, and simultaneous ascending auctions; complex trading scenarios with case studies from the Trading Agent Competition (TAC); methodology for trading agent design and analysis; and trading strategy issues for advanced and novel market designs.
Instructors: Michael P. Wellman received a PhD from MIT in 1988 for his work in qualitative probabilistic reasoning and decision-theoretic planning. >From 1988 to 1992, Wellman conducted research in these areas at the USAF's Wright Laboratory. For the past dozen+ years, his research has focused on computational market mechanisms for distributed decision making and electronic commerce. As Chief Market Technologist for TradingDynamics, Inc. (now part of Ariba), he designed configurable auction technology for dynamic business-to-business commerce. Wellman in Chair of the ACM Special Interest Group on Electronic Commerce (SIGecom), and previously served as Executive Editor of the Journal of Artificial Intelligence Research. He has been elected Councilor and Fellow of the American Association for Artificial Intelligence. In 2000 he initiated an annual series of international Trading Agent Competitions, and recently founded the Association for Trading Agent Research to organize that ongoing activity.
|
| |
Back to top |
Sun, Jun 5, 2005 - Afternoon (two one-hour talks)
Polynomial Time Algorithms for Market Equilibria - Kamal Jain and Vijay Vazirani
|
|
Abstract: Combinatorial Approaches (Vazirani): We will start by defining the market equilibrium problem in two models: Fisher and Arrow-Debreu. We then give the two main combinatorial approaches for linear utility functions: primal-dual schema based and auction based, first for the Fisher model and later approximation algorithms for Arrow-Debreu model. We end with recent work extending these approaches to weak gross substitute utilities and to the production model of equilibria.
Convex Programming Based Approaches (Jain): We start with the classic work of Eisenberg and Gale who gave the first convex program for the Fisher model of equilibria. We then cover the history of this approach within the Economics community. A major portion of this talk will cover two recent results: the first polynomial time (exact) algorithm for the Arrow-Debreu model, and on extending works of Eisenberg-Gale and Eisenberg to homothetic, quasi-concave utility functions. We will end with some applications of market equilibria to wireless networking and ad auctions.
Instructors: Kamal Jain earned his undergraduate degree in Computer Science and Engineering in 1996 from the Indian Institute of Technology, Delhi. After four years he earned his PhD in an interdisciplinary program of Algorithms, Combinatorics and Optimization from Georgia Institute of Technology, Atlanta. Since then he is with Microsoft Research Center in Redmond, Washington. Over the years Kamal's interest diversified in many areas of modern Computer and Information Sciences. He has worked in the areas of Approximation Algorithms, Computational Economics, Game Theory, Network Coding, Wireless Networking, Complexity Theory, Coding Theory, Semantics Theory, Information Theory, Cryptography, and Combinatorics.
Vijay Vazirani got his Bachelor's degree in Computer Science from MIT in 1979, and his Ph.D. from U.C. Berkeley in 1983. He is currently Professor of Computer Science at Georgia Tech.
Vazirani's research career has been centered around the design of algorithms, together with work on complexity theory, cryptography, coding theory, and most recently, game theory. Within the last area, he has worked extensively on polynomial time algorithms for computing market equilibria.
Vazirani is the author of a well-received book on Approximation Algorithms (Springer Verlag, 2001). This book has been translated into Japanese and Polish, and a French translation is forthcoming.
|
| |
Back to top |
Sun, Jun 5, 2005 - Afternoon
Algorithms for Combinatorial Auctions and Exchanges - Tuomas Sandholm
|
|
Abstract: Markets are important mechanisms for allocating goods, services, tasks, and resources among multiple agents, be they human or software. The market clearing problem is that of deciding how to allocate the items among the agents. The last four years have witnessed a leap of improvement in market clearing algorithms both for traditional market designs and entirely new market designs enabled by advanced clearing technology. This tutorial covers the computational implications of different market designs and presents algorithms for clearing markets optimally and approximately. Auctions (one seller, multiple buyers), reverse auctions (one buyer, multiple sellers), and exchanges (multiple buyers and multiple sellers) are covered. Both theoretical and experimental results are presented. Multi-item and multi-unit markets will be a key focus. Computational implications of different classes of side constraints will be presented. Bid types covered include price-quantity bids, different shapes of supply/demand curves, and package bids. Methods for selective incremental preference elicitation for combinatorial markets are presented, with which the market can be cleared optimally using only a small portion of the agents' preferences as input.
A basic understanding of algorithms, search, and NP-completeness is necessary. No background on markets is assumed.
Instructors: Tuomas Sandholm is associate professor in the Computer Science Department at Carnegie Mellon University. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has 15 years of experience building electronic marketplaces, and has fielded over 150 large-scale combinatorial auctions. He has published over 200 papers, and received the inaugural ACM Autonomous Agents Research Award, the NSF Career award, the Sloan Fellowship, and the IJCAI Computers and Thought award.
|
| |
Back to top |
|
