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.

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

Abstract:

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