Which Coalition?

The problem.

OK, we had an election and have a new parliament with 120 members. The president has asked the leader of one party to form a coalition. (This has not happened yet in the Israeli election but it will happen soon.) Such a coalition should include parties that together have more than 60 seats in the parliament.

Can game theory make some prediction as to which coalition will be formed or give some normative suggestions on which coalition to form?

Robert Aumann and Roger Myerson made  (in 1977) the following concrete suggestion.  (Update: A link to the full 1988 paper is now in place.)  The party forming the coalition would (or should) prefer to form the coalition in which its own power (according to the Shapley-Shubik power index) is maximal. Of course Continue reading

The Retaliation Game


We have two players playing in turns. Each player can decide to stop in which case the game is stopped and the two players can go on with their lives, or to act.

The player that acts gains and the other player loose twice as much. 

So in the first round: player I can stop the game, if he acts he gets 1 and the other player II gets -2.
If the games continues in the second turn player II can stop the game, if he acts he gets 1 and player I gets -2.
If the games continues in the third turn player I can stop the game, if he acts he gets +1 and player II gets -2.

How to play this game?

The Prisoner’s Dilemma, Sympathy, and Yaari’s Challenge

Correlation and Cooperation

In our spring school devoted to Arrow’s economics, Menahem Yaari gave a talk  entitled “correlation and cooperation.” It was about games as a model of people’s behavior, and Yaari made the following points:

It is an empirical fact that people (players in a game)  act in a correlated way,

It is unscientific not to take this into account (although this is not taken into account in game theory and economics).


The prisoner’s dilemma

A basic example in game theory (which also played a central part in Yaari’s lecture) is the Prisoner’s dilemma. Let’s talk about this example a little, before getting to Yaari’s claims. Continue reading

Amir Ban on Deep Junior

Kasparov and Junior

Ladies and Gentelmen: Amir Ban (right, in the picture above) the guest blogger, was an Israeli Olympiad math champion in the early 70s, with Shay Bushinsky he wrote Deep Junior, and he is also one of the inventors of the “disc on key”. This post is about computer chess. 

Let me introduce myself: I’m Amir Ban, and I wrote the computer chess program Junior, also known as Deep Junior. When Gil invited me to guest-blog for him on the subject of computer chess, I was honored and pleased, but what can I write to introduce the subject to the uninitiated? Well, as luck has it, I participated last week in a unique event in Barcelona, Spain: a man with machine vs. machine match! The “man” was veteran grandmaster and Spanish champion Miguel Illescas. The “machine” he assisted himself by was my own Junior 10 (a commercially available product) on his Toshiba notebook. On the other side of the board was my latest Deep Junior 11, due to be released later this summer, running on an ordinary core-duo Dell desktop.

Susan Polgar, a former women’s world chess champion, and the eldest of the three Hungarian-Jewish Polgar sisters, describes the event on her popular blog. The comments to the blog entry show some difference of opinion:

Comment 1: “That’s not fair to the computer at all.”

Comment 2: “Big deal, Junior 10 vs. Junior 11 with a grandmaster moving the mouse….”

Visualization of Deep Junior Bxh2 sacrifice in the 5th game, New York, 2003.
Hmm… We need some perspective here. For that, let us take a few quick flashbacks, starting ca. 60 years ago with the pioneering efforts of Alan Turing, and especially Claude Shannon, who in 1950 wrote “Programming a Computer For Playing Chess“. In the article, Shannon lays out the foundations of computer chess, still practiced to this day: Given the current position where the computer must play a move, it will generate the tree of all hypothetical continuations: All moves playable at the position, then all possible replies to each of these moves, then all possible replies to the replies, and so on. Theoretically this process may continue indefinitely until a terminal position is reached, i.e. a checkmate, or a draw by the rules of chess. Unfortunately (or rather, fortunately) this possibility is merely theoretical, as the typical number of legal moves per position is around 40, and a chess game may last a hundred or so moves, the exponential explosion of possibilities forces a limit to the practical depth of the moves tree.

The Shannon trophy

Shannon proposed stopping the tree generation at some practical depth, and attaching an evaluation to the position at the leaf.

Continue reading