Algorithms and Complexity

Projects Prof. Dr. Susanne Albers

Competitive Mechanism Design and the Price of Anarchy in Networks (G-783-61.6/2003)

Project description

Historically, computer networks and systems have been studied under the assumption that all system components behave properly following some protocol. This is no longer true for large systems such as the Internet where multiple selfish agents operate so as to maximize their own benefit and not necessarily the global good. Research has concentrated on two aspects of this problem. One is to study algorithmic mechanism design where incentives may be provided to the agents so as to obtain a global benefit, while agents still behave selfishly. The other is to compare the Nash equilibrium obtained by selfish agents and the global optimum. We propose to deal within the framework of both these aspects. The Vickrey-Clarke-Groves mechanism, while maximizing social welfare, may effect undesirable behavior from the perspective of the designer who may be interested in other objective functions. E.g., the mechanism designer for an auction would like to maximize the auctioneers benefit and not necessarily the total social welfare. Social welfare and other goals need not be contradictory, and there may be several different mechanisms that simultaneously maximize social welfare and other goals. A mechanism is called competitive if it well approximates the best value of the objective function set by the mechanism designer. We intend to study competitive mechanism design for problems related to combinatorial auctions and to peer to peer networks. Previous competitive studies have been where the seller designs the mechanism and maximizes profit. In particular, we plan to consider competitive auctions where the buyer designs the mechanisms and seeks to maximize the buyer benefit. An example of this type are the results regarding frugality of mechanisms for assigning paths is networks. In peer in peer networks, one of the major problems is that of free riders who contribute nothing; we plan to study mechanisms that address this issue. With regard to the price of anarchy in networks, previous work has considered general networks only when each agents influence is negligible; we intend to study the price of anarchy when agents may have larger impact. Other previous work has considered the case of arbitrary agent influence on very simple networks. We propose to quantify the relationship between how influential agents can be versus the price of anarchy on various types of networks. We plan to consider algorithmic aspects of traffic regulation so as to improve the global performance of the network.

Start/End of project

01.01.2005 until 31.12.2007

Project manager

Prof. Dr. Susanne Albers

Contact person

Prof. Dr. Susanne Albers


Prof. Amos Fiat, Tel Aviv University, School of Computer Science Prof. Yossi Azar, Tel Aviv University, School of Computer Science


German-Israeli Foundation for Scientific Research & Development