DIMACS Workshop on Computational Issues in Game Theory and Mechanism Design

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

Vijay Vazirani, Georgia Tech, vazirani@cc.gatech.edu
Noam Nisan, Hebrew University, Jerusalem, Israel, noam@cs.huji.ac.il
Presented under the auspices of Next Generation Networks Technologies and Applications and Social Science Methods and Information Technology.



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
Contacting the Center

Document last modified on September 13, 2001.