|
Call
for Participation:
The Fifth Israeli Seminar on Computational Game Theory follows the first , second, third and fourth seminars, which were held in Tel-Aviv
university (1st and 2nd), in Google Tel-Aviv (3rd)
and in Microsoft Israel (4th).
Recent years have seen a flurry of research
activity on problems on the border of computer science and game-theory /
economics. Research in this area includes (but is not limited to):
algorithmic mechanism design, computational issues in games, and incentives
in computer networks and the Internet. This field has been of particular
interest to quite a few Israeli research groups, encompassing several
universities throughout the country. This seminar seeks to bring together
active researchers in this developing field, to promote the exchange of ideas
between local researchers, to encourage further collaboration between the
different groups, and to familiarize researchers from computer science,
economics, mathematics, and management programs with this intriguing,
interdisciplinary area.
The seminar will take place on Thursday, December 10, in Microsoft
Israel R&D Center, located in 13 Shenkar St. Herzliya, Gav Yam building No. 5, floor L2.
Important
notes:
1. Registration is required. Please register by sending an
email to ac-ildc@microsoft.com with subject ISRAELI CGT 2009,
which includes your name and affiliation (university and department /
company) until November 29.
2. Parking will be freely available at the building. Please
enter the Gav Yam 5 parking, take a ticket from the
machine and park at level -2. Make sure to take the parking ticket with you
as you enter the building and take the elevator to floor L2. In floor L2 you
will get stickers to validate the parking tickets.
Seminar
Schedule:
10:00 - 10:30: Coffee
10:30 - 10:35: Welcoming
10:35 - 11:20: Dov Samet (Tel-Aviv University), The sure thing principle and independence of irrelevant
knowledge.
11:25 - 12:10: Seffi Naor (Technion), Bounding Price of Anarchy of Best Response
Dynamics in Network Design Games.
12:10 - 13:40: Lunch break
13:40 - 14:25: Noga Alon (Tel-Aviv
University and Microsoft Israel R&D Center), Zero-sum games with
adversarial leakage.
14:25 - 14:50: Coffee break
14:50 - 15:35: Svetlana Olonetsky (Tel-Aviv University & Google Tel-Aviv),
Envy-Free and Incentive-Compatible Mechanisms.
15:40 - 16:30: Joe Halpern (Cornell University), Beyond Nash Equilibrium:
Solution Concepts for the 21st Century.
Abstracts:
The sure thing principle and independence of irrelevant
knowledge. Dov Samet.
Savage (1954) introduced the sure thing principle in terms of the dependence
of decisions on knowledge, but gave up on formalizing it in epistemic terms
for lack of a formal definition of knowledge. Using simple models of
knowledge, we examine the sure thing principle, presenting two ways to
capture it. One is in terms of theunion of
future events, for which we reserve the original name — the sure thing
principle; the other is in terms of the intersection of kens —
bodies of agents' knowledge — which we call independence of irrelevant
knowledge. We show that the two principles are equivalent and that the only
property of knowledge required for this equivalence is the axiom of
truth--the requirement that whatever is known is true. We present a symmetric
version of the independence of irrelevant knowledge which is equivalent to
the impossibility of agreeing to disagree on the decision made by agents,
namely the impossibility of agents making different decisions being common
knowledge.
Bounding
Price of Anarchy of Best Response Dynamics in Network Design Games.
Seffi Naor
When do (natural) best resposne dynamics converge
to a good equilibrium? This question is considered in network design games
with selfish non-cooperative players. The simplest version is the Steiner
tree game in which there is a special source node and each player is
interested in connecting to the source by making a routing decision
minimizing its payment. The mutual influence of the players is determined by
a fair cost sharing mechanism. We focus on the price of anarchy of a Nash
equilibrium resulting from the best-response dynamics of a game course, where
the players join the game sequentially and play till equilibrium is reached.
Upper and lower bounds on the price of anarchy of this game are presented.
A more general setting happens when there is a set of facilities, and
each facility provides services to a subset of the users. Each user is
interested in purchasing a service, and will buy it from the facility
offering it at the lowest cost. A central authority can encourage the
purchase of services by offering subsidies that reduce their price, in order
to improve the system performance. The subsidies are financed by taxes
collected from the users. A tradeoff between the price of anarchy and the
taxation ratio, defined as the fraction of payments collected as taxes from
the users, is shown.
Zero-sum
games with adversarial leakage. Noga
Alon
We introduce the study of adversarial leakage of information in
games, and study its effect on general zero-sum games with binary payoffs.
Joint work with Yuval Emek, Michal Feldman and
Moshe Tennenholtz.
Envy Free and Incentive Compatible
Mechanisms. Svetlana Olonetsky
We study mechanisms, where agents have no incentive to lie about their true
values (incentive compatible) and for which no agent will seek to exchange
outcomes with another (envy-freeness). Mechanisms satisfying each requirement
separately have been studied extensively, but there are few results on
mechanisms achieving both. We are interested in those problems for which
there exist payments such that the resulting mechanism is simultaneously
incentive compatible and envy-free. Examples of such problems are auctions
with additive valuations and with capacity constraints (motivated by the
problem of paper assignment to program committee members), mechanism for
scheduling tasks on unrelated machines that approximately minimize the makespan, and others.
Joint work with Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan
Beyond Nash Equilibrium: Solution Concepts
for the 21st Century. Joe Halpern
Nash equilibrium is the most commonly-used notion of equilibrium in
game
theory. However, it suffers from numerous problems. Some are well
known
in the game theory community; for example, the Nash equilibrium of repeated
prisoner's dilemma is neither normatively nor descriptively reasonable.
However, new problems arise when considering Nash equilibrium from a
computer science perspective: for example, Nash equilibrium is not tobust
(it does not tolerate "faulty" or "unexpected" behavior),
it does not
deal with coalitions, it does not take computation cost into account, and
it does not deal with cases where players are not aware of all aspects of
the game. In this talk, I discuss solution concepts that try to address
these shortcomings of Nash equilibrium. This talk represents joint work
with various collaborators, including Ittai
Abraham, Danny Dolev, Rica Gonen,
Rafael Pass, and Leandro Rego. No background
in game theory will be
presumed.
Seminar Organizers:
Michal Feldman. Hebrew
University of Jerusalem and Microsoft Israel R&D Center. email: mfeldman at
huji.ac.il
Noam Nisan. Hebrew University of
Jerusalem and Google Tel-Aviv. email: noam at cs.huji.ac.il
Moshe Tennenholtz. Microsoft Israel R&D Center and Technion--Israel Institute of Technology. email: moshet at ie.technion.ac.il
|
