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
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
Globally Distributed Computation over the Internet--The Popcorn
Project. O. Regev and N. Nisan. To be presented by
Sezgin Sucu on February
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
Market-oriented programming: Some early lessons.
M. P. Wellman, in "Market-Based Control: A Paradigm for
Distributed Resource Allocation", World Scientific, 1996.
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
Analyzing Market-based Resource Allocation Strategies for the
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.
Mechanism Design for Routing
How Bad is Selfish Routing?
T. Roughgarden and E. Tardos.
FOCS 2000. To be presented by Lingli
on March 4th.
Designing Networks for Selfish Users is Hard.
Frugal Path Mechanisms.
Archer and Tardos.
Links to Similar Course Elsewhere
Algorithmic Aspects of Game Theory C. Papadimitriou
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.