|
Call
for Participation:
The Fourth Israeli Seminar on Computational Game Theory follows the first , second and third seminars,
which were held in Tel-Aviv university (1st and 2nd) and in Google Tel-Aviv
(3rd).
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 Wednesday, December 31, 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 AGT SEMINAR, which
includes your name and affiliation (university and department / company)
until December 15.
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: Yuval
Peres, Microsoft Research Redmond. Random-Turn Hex and Other Selection
Games..
11:25 - 12:10: Sarit Kraus, Bar-Ilan
University. Intelligent Randomization for Physical Security.
12:10 - 13:40: Lunch break
13:40 - 14:25: Ariel Procaccia, Microsoft Israel R&D Center. Approximating
Lewis Carroll's Voting Rule.
14:25 - 14:50: Coffee break
14:50 - 15:35: Shahar Dobzinski, Hebrew
University. Multi-unit Auctions with Budget Limits.
15:40 - 16:30: Sergiu Hart, Hebrew University. Dynamics and
Equilibrium.
Abstracts:
Random-Turn Hex and Other Selection Games.
Yuval Peres
Any function f of n variables yields a game, where players alternate turns
setting variables of f, with player 1 trying to maximize the value of f and
player 2 trying to minimize it. A nice example is provided by the game of
Hex, where two players take turns placing stones of their colors on the
hexagons of a rhombus-shaped hexagonal grid (so the variables are the colors
assigned to the hexagons). White (=Player I) wins by completing a crossing
between two opposite vertical edges (If he succeeds then f=1), while Black
(=Player II) wins by completing a crossing between the two horizontal edges
(In this case f=0). Exactly one of them can succeed. Although ordinary Hex is
famously difficult to analyze, random-turn Hex---in which players toss a fair
coin before each move to decide who gets to place the next stone---has a
simple optimal strategy. I will describe the optimal strategy and estimate
the expected length of the game under optimal play for several random-turn
games; I will also discuss connections with decision-tree complexity of
Boolean functions and Percolation theory.
Talk based on joint work with Oded Schramm, Scott
Sheffield and David Wilson.
Intelligent Randomization for Physical
Security. Sarit Kraus
Security at major locations with economic or political significance is a key
concern throughout the world, particularly given the threat of terrorism.
Limited security resources prevent full security coverage at all times, which
allow adversaries to observe and exploit patterns in selective patrolling or
monitoring. Hence, randomized patrolling or monitoring is important. In this
talk we will consider two problems: (i) scheduling
checkpoints for the protection of important locations against adversaries;
(ii) strategies for multi-robot patrols around a closed area which an
adversary is attempting to penetrate. The first problem we model as a
Bayesian Stackelberg Game and the second as a
Markov chain. For both problems we will present efficient algorithms which
find optimal strategies for the agents, given the adversary is fully rational
and has full knowledge on the defending agents. We will also present the
deployment of the Bayesian Stackelberg Game
approach for scheduling checkpoints in the Los-Angeles airport. We will
discuss the impact of the adversary's knowledge and bounded rationality on
the performance of the agents. We will present alternative algorithms showing
both theoretically and through extensive experiments with human subjects that
in many situations the resulting strategies yield better results than
strategies assuming the worst case of fully knowledgeable adversaries.
The first part of the talk concerns joint work with Milind
Tambe, Fernando Ordez and
their TEAMCORE research group while the second part relates to joint work
with Noa Agmon and Gal Kaminka.
Approximating Lewis Carroll's Voting Rule.
Ariel Procaccia
Charles Dodgson (better known by his pen name, Lewis Carroll) suggested an
appealing voting system in 1876. Unfortunately, at the time Dodgson did not
take into account such futuristic considerations as computational complexity,
and, as it turned out more than a century later, computing the Dodgson score
of a candidate is NP-hard. I will present two very different approximation
algorithms, as well as inapproximability results,
for the Dodgson score. I will also try to position this work in the context
of a wider agenda: studying the desirability of approximation algorithms as
voting rules.
This talk is based on joint work with Ioannis Caragiannis, Jason Covey, Michal Feldman, Chris Homan, Christos
Kaklamanis, Nikos Karanikolas,
and Jeff Rosenschein.
Multi-unit Auctions with Budget Limits.
Shahar Dobzinski
We study multi-unit auctions where the bidders have a budget constraint, a situation
very common in practice that has received very little attention in the
auction theory literature. Our main result is an
impossibility: there are no incentive-compatible auctions that always
produce a Pareto-optimal allocation. We also obtain some surprising positive
results for certain special cases, including an auction that simultaneously
maximizes efficiency and revenue.
Joint work with Ron Lavi and Noam Nisan.
Dynamics and Equilibrium. Sergiu Hart
It is a fact that in the existing literature there are no general natural dynamics
leading to Nash equilibria. The talk will provide an overview of research
that sheds light on this and related issues. (GAMES2008 Presidential
Address; presentation at http://www.ma.huji.ac.il/hart/abs/dyn-p.html
)
Seminar Organizers:
Michal Feldman. Hebrew
University of Jerusalem. email: mfeldman at huji.ac.il
Noam Nisan. Google Tel-Aviv and
Hebrew University of Jerusalem. 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
|
