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.



Artur Czumaj, New Jersey Institute of Technology
Title: Tight Bounds for Worst-Case Equilibria


The coordination ratio is a game theoretic measure that aims to
reflect the price of selfish routing in a network.
We show that the worst-case coordination ratio on m parallel
links (of possibly different speeds) is

        Theta ( log(m) / logloglog(m) ).

Our bound is asymptotically tight and it entirely resolves an open
question posed recently by Koutsoupias and Papadimitriou [STACS'99].

In the system with m identical links, we obtain a bound that is
tight up to an additive constant and show that the worst-case
coordination ratio is

        Gamma^{(-1)}(m) + Theta(1),

where Gamma^{(-1)} is the inverse of the Euler Gamma function;
it is well known that Gamma^{(-1)}(m) = (1 + o(1)) log(m) / loglog(m).

Joint work with Berthold Voecking (MPI Saarbruecken, Germany)

2. Chris Dellarocas, MIT Sloan School of Management and NYU Stern School of Business A dynamic optimization framework for designing effective online reputation mechanisms Abstract: This talk will present ongoing work in developing a systematic quantitative framework for the design and evaluation of online reputation mechanisms. Reputation mechanisms are an interesting alternative to formal contracts in situations where the latter may be poorly enforceable or prohibitively expensive; a lot of electronic communities fall under these categories. The framework models the function of a reputation mechanism as an infinite horizon optimal control problem where the objective of the seller is to take advantage of existing information asymmetries (e.g. the fact that true product quality is unknown to buyers) in order to maximize the net present value of her profits, while the objective of buyers is to use the power they have in influencing other buyers' future opinions of sellers through ratings in order to maximize the net present value of their surplus. In such a setting, the role of the center is to design the "rules" of the reputation mechanism (data type of rating information being requested, aggregation algorithm, format of aggregate reputation profiles, optimal algorithms for interpreting reputation profiles and optimal rating rules) so as to achieve a "fair" steady state, for example a state where sellers advertise truthfully and buyers assess accurately the true quality of products sold. The talk will outline the basic ideas of the framework and will report the results of applying the framework in order to evaluate the efficiency of eBay-like binary reputation mechanisms (i.e. mechanisms where the only possible ratings can be "positive" and "negative").
3. Daniel Grosu, Univ. of Texas at San Antonio Title: A Cooperative Load Balancing Game in Distributed Systems Abstract: Distributed computing systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper we formulate the static load balancing problem in single class job distributed systems as a cooperative game among computers. It is shown that the Nash Bargaining Solution (NBS) provides a Pareto optimal allocation which is also fair to all jobs. We propose a cooperative load balancing game and present the structure of the NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always 1 using NBS which means that the allocation is fair to all jobs. Finally, the performance of our cooperative load balancing scheme is compared with that of other existing schemes. Joint work with Anthony T. Chronopoulos and Ming-Ying Leung The paper can be downloaded from: http://ringer.cs.utsa.edu/~dgrosu/lbcoop.ps
4. Title: Lower Bounds on Multicast Cost Sharing Speaker: Arvind Krishnamurthy (Yale Univ. Computer Science Dept.) Abstract: We continue the study of algorithmic mechanisms for multicast cost sharing. Following [MS, FPS], we focus on strategyproof mechanisms that satisfy three natural requirements: no positive transfers (NPT), which preculdes paying recipients to receive the multicast; voluntary participation (VP), which ensures that potential recipients are always free to not receive the multicast and not be charged; consumer sovereignty (CS), which ensures that no potential participant who is willing to pay a sufficiently high price can be excluded. We obtain the following two negative results: -- The communication complexity of the Shapley-value mechanism (SH) is \Omega(p\times n) bits, where p is the number of potential recipients and n is the size of the multicast tree. This lower bound applies to both deterministic and randomized distributed algorithms. It is more satisfactory than the lower bound given in [FPS], which applied only to deterministic "linear distributed algorithms." Although SH is a natural budget-balanced mechanism to consider, as shown in [MS], our proof technique can also be used to prove similar lower bounds on the communication complexity of certain other budget-balanced and approximately budget-balanced mechanisms. -- It is a classical result in game theory [GKL, R] that no strategyproof mechanism for multicast cost sharing that satisfies the NPT, VP, and CS requirements can be both budget-balanced and efficient. We extend this result by showing that no such mechanism can be both approximately budget-balanced and approximately efficient. This is joint work with Joan Feigenbaum, Rahul Sami, and Scott Shenker. References: [FPS] J. Feigenbaum, C. Papadimitriou, and S. Shenker, "Sharing the Cost of Multicast Transmissions," Journal of Computer and System Sciences 63 (2001), 21-41. (Special issue on Internet Algorithms.) [GKL] J. Green, E. Kohlberg, and J. J. Laffont, "Partial equilibrium approach to the free-rider problem," Journal of Public Economics 6 (1976), 375-394. [MS] H. Moulin and S. Shenker, "Strategyproof Sharing of Submodular Costs: Budget Balance versus Efficiency," Economic Theory 18 (2001), 511-533. [R] K. Roberts, "The Characterization of Implementable Choice Rules," in Aggregation and Revelation of Preferences, North Holland, Amsterdam, 1979, 321-348.
5. Ron Lavi, Hebrew University Title: Competitive Analysis of Incentive Compatible Online Auctions Abstract: We study auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, online auctions. We first characterize exactly online auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible online auctions. We obtain several results including the identification of an online auction for a large number of identical items that has optimal competitive ratio both in terms of sellers' revenue and in terms of the total social efficiency obtained. Joint work with Noam Nisan. The paper can be downloaded from http://www.cs.huji.ac.il/~tron/online-auctions.ps.gz
6. Ahuva Mu'alem, Hebrew University Title: Truthful Approximation Mechanisms for Restricted Combinatorial Auctions Abstract: When attempting to design an incentive compatible mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics cannot be embedded in any truthful mechanism (e.g. VCG payment rules will not ensure truthfulness). We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann et al, who presented greedy heuristics, and show how to use IF-THEN-ELSE constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios for these cases. Joint work with Noam Nisan. A full presentation can de downloaded from http://www.cs.huji.ac.il/~ahumu/holland.ppt
7. David M. Pennock, NEC Compact securities markets for minimizing risk and maximizing information Abstract Securities markets (everything from stocks, options, futures, and insurance markets to sports betting markets) facilitate both risk sharing and information aggregation. In general, for public markets to optimally allocate risk and maximize collective information, they must include an unimaginably (and infeasibly) large number of securities. I show that, under some conditions, risk can be optimized and information maximized with many fewer securities -- in some cases exponentially fewer. The key "trick" is to structure the market in analogy to a computational data structure called a Bayesian network, originally designed to represent joint probability distributions in a space-efficient manner. http://www.neci.nec.com/homepages/dpennock/papers/compact-markets-uai-00.ps David M. Pennock and Michael P. Wellman. "Compact securities markets for Pareto optimal reallocation of risk", Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI-2000), pp. 481-488, June 2000.
8. Designing and Analyzing Auctions: the Devil is in the Details (and not just on Halloween) and some scary heresies Michael H. Rothkopf Rutgers University Abstract Modeling matters. Answers to questions about auctions can depend heavily on the particular modeling assumptions. Math will not help if you ask the wrong question. I will offer seven scary examples and three frightening heresies in five minutes.
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center

Document last modified on October 25, 2001.