DIMACS Workshop on Computational Issues in Game Theory and Mechanism Design

October 31 - November 2, 2001
DIMACS Center, Rutgers University, Piscataway

Organizers:

Vijay Vazirani, Georgia Tech, vazirani@cc.gatech.edu

Noam Nisan, Hebrew University, Jerusalem, Israel, noam@cs.huji.ac.il

Abstracts:

1.

Title: Pricing, behavioral economics, and mechanism design
Andrew Odlyzko, University of Minnesota

Abstract: There are striking analogies between pricing on
19th century railroads and on the Internet.  They suggest
that electronic commerce will be shaped to a great extent
by the conflict between the incentives to price discriminate 
and numerous hard to quantify factors from behavioral
economics, especially concerns about fairness.  As a result,
some promising technologies are likely to see little
application, while others will fourish.


2.

Mechanism Design under Incomplete Information:
Uses, Limitations, and the Necessity of Computational Approaches

Mark A. Satterthwaite
Northwestern University

Mechanism design through its exploitation of the revelation principle is a
powerful means for determining the constraints that private information
strategically exploited places on the efficiency of solutions to resource
allocation problems. In this presentation I review how its techniques
enable elegant analytical results to be obtained in one-shot allocation
problems (e.g., bargaining between a buyer and a seller) when the
independent private values model describes agents' information about each
other's preferences. I then apply these techniques to a model of repeated
bargaining  in which new agents enter the market each period, active agents
become matched in pairs to arrange a bilateral trade, and older agents leave
when they either become discouraged or succeed in arranging a trade with the
agent with whom they are currently matched. The additional complexity this
model introduces into the analysis prevents derivation of neat formulas for
the optimal mechanism. Numerical computation, however, allows explicit
characterization of the optimal mechanism and its performance for specific
parameter values.

This optimal mechanism is not, I argue, the end of the analysis because the
optimal mechanism depends critically on the agents and  mechanism designer
sharing a common knowledge prior of the ex ante distribution of each other's
preferences. Common knowledge among the agents who participate in the
mechanism is a strong assumption; for this common knowledge to extend to the
mechanism designer is arguably untenable. Consequently the analysis should
not stop with derivation of the optimal mechanism. A simple
mechanism---one such as the double auction whose rules do not vary with the
common knowledge prior---that can be used to solve the allocation problem
should be posited and, for a variety of prior distributions, the efficiency
of their equilibria should be computed. Almost certainly, computing these
equilibria and their performance is a numerical problem. If, for a
reasonable sample of prior distributions, the performance of the simple
mechanism's equilibria compare well with the performance of the optimal
mechanism, then the simple mechanism may fairly be categorized as a good
mechanism. I illustrate this approach in the repeated bargaining model by
positing that agents use the bilateral double auction to arrange their
trades, computing equilibria of the resulting simple mechanism, and
evaluating its performance against the performance of the optimal mechanism.


3.

Mechanism Design and the Internet
Scott Shenker, University of California, Berkeley

The Internet is an example of a large distributed system whose
resources are shared among many users.  As we move from a mostly
cooperative environment to one where user selfishness may prevail, the
ideas of game theory and mechanism design will be useful in guiding
future Internet designs.  I will discuss various challenges in
applying the mechanism design paradigm to such distributed systems.
While some past results will be reviewed, the emphasis will be on
identifying open problems.


4.

Combinatorial Auctions
Rakesh Vohra, Northwestern University

Abstract:

Game Theory and Computer Science are about the same age (born in the 
late 40's and early 50's) and even share a common ancestor (von 
Neumann). In their roughly half century of existence they have even 
shared some common interests. I know of at least four:

1) stable matchings

2) modeling uncertainty and bounded rationality

3) computational learning theory and learning in games

4) mechanism design

Of these, the last is the most recent and the subject of my talk. I 
will use the subject of combinatorial auctions as a vehicle to survey 
work on mechanism design at the intersection of computer science and 
game theory.

The research to date has been of two kinds. The first, is to study 
optimization problems that arise in the context of auction design. 
While useful, by itself it yields no new insights about auction 
design.

The second, takes the view that computational constraints are as 
important to auction design as informational ones and seeks to study 
how the two kinds of constraints interact with each other. In my talk 
I intend to concentrate on work  of this kind.


5.

Trading Agents

Michael Wellman
University of Michigan

The proliferation of electronic marketplaces opens new opportunities 
for deploying automated trading strategies.  Much of the extant 
literature on trading agents concerns isolated markets employing 
continuous double auction mechanisms.  Alternative market mechanisms 
(including combinatorial), as well as complexes of interrelated 
markets, present distinct strategic issues.  Lessons for trading 
agents can be gleaned from studies of a variety of market games, 
including studies of scenarios in scheduling, supply chain formation, 
and travel shopping.  The latter has served as the basis for an 
international Trading Agent Competition (http://tac.eecs.umich.edu), 
providing a forum to compare approaches from a diverse collection of 
agent developers.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage