Description
In this seminar, we will focus on market-based methodologies, both
for distributed resource allocation and Internet-based commerce.
These applications involve self-interested agents, and thus economic and
game theoretic issues play an important role. The problem can be
viewed as a game of incomplete information: consumers' and sellers'
utility of the resource is private information, still as a system
designer we would like to achieve an optimal resource allocation.
In the seminar, we will read papers from the literature on various
market formulations and their realizations in different settings. In
particular, we will study the algorithmic properties of combinatorial
auctions
and commodity markets, and review the results of their application.
Each student will be expected to present one paper.
We include below a non-exhaustive list of papers that should give
you a sense of what topics we want to cover.
In addition, we will cover some chapters from game theory textbooks
to get the basic introduction.
Computational Markets and Resource Allocation
-
Market-based Proportional Resource Sharing for Clusters.
B. Chun and D. E. Culler. To be presented by
Anshul Kothari on
February 4th.
-
Globally Distributed Computation over the Internet--The Popcorn
Project. O. Regev and N. Nisan. To be presented by
Sezgin Sucu on February
11th.
-
Spawn: A Distributed Computational Economy.
C. A. Waldspurger and T. Hogg and B. Huberman and J. O. Kephart
and S. Stornetta.
IEEE Transactions on Software Engineering, pp. 103-117, 1992.
To be presented by Hugh Su on
March 11th.
-
Market-oriented programming: Some early lessons.
M. P. Wellman, in "Market-Based Control: A Paradigm for
Distributed Resource Allocation", World Scientific, 1996.
To be
presented by Todd Bryan on January 28th.
-
The WALRAS algorithm: A convergent distributed implementation of
general equilibrium outcomes.
M. P. Wellman, Computational Economics, pp. 1-24, 1998.
to be presented by Eric Virnig on
February 25th.
-
Analyzing Market-based Resource Allocation Strategies for the
Computational Grid.
Wolski, Plank, Brevik, Bryan.
Complexity of Combinatorial Auctions
-
Combinatorial Auctions: A Survey.
R. Vohra and S. de Vries
-
Complexity of Clearing Auctions of Multiple Indistinguishable Units
Tuomas Sandholm and Subhash Suri. To be presented by
Ye Wen on February 4th.
- Solving Combinatorial Exchanges: Optimality via
a Few Partial Bids.
Kothari, Sandholm and Suri. To be presented by
Jinye Huo on February 11th.
-
Auctions: A Survey.
Wolfstetter
Mechanism Design for Routing
-
How Bad is Selfish Routing?
T. Roughgarden and E. Tardos.
FOCS 2000. To be presented by Lingli
Zhang
on March 4th.
-
Designing Networks for Selfish Users is Hard.
T. Roughgarden.
FOCS 2001.
-
Frugal Path Mechanisms.
Archer and Tardos.
SODA 2002.
Links to Similar Course Elsewhere
-
Algorithmic Aspects of Game Theory C. Papadimitriou
(UC Berkeley)
-
E-commerce foundations J. Feigenbaum (Yale)
-
Topics on the border of CS, Game theory, and Economics
Nisan (Tel Aviv)
-
Topics in Internet agent economics A. Greenwald (Brown)
-
IBM Institute of Advanced Commerce.