Category Archives: Games

Is Backgammon in P?

Posted on January 14, 2011 by

  The Complexity of Zero-Sum Stochastic Games with Perfect Information Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is … Continue reading →

Posted in Computer Science and Optimization, Games, Open problems, Probability | 9 Comments

Subexponential Lower Bound for Randomized Pivot Rules!

Posted on November 9, 2010 by

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading →

Posted in Computer Science and Optimization, Convex polytopes, Games | Tagged , | 11 Comments

Test Your Intuition (13): How to Play a Biased “Matching Pennies” Game

Posted on October 14, 2010 by

Recall the game “matching pennies“. Player I has to chose between ’0′ or ’1′, player II has to chose between ’0′ and ’1′.No player knows what is the choice of the other player before making his choice. Player II pays … Continue reading →

Posted in Games, Test your intuition | Tagged | 5 Comments

Futures Trading as a Game of Luck

Posted on January 5, 2010 by

A recent interesting article by Ariel Rubinstein entitled “Digital Sodom” (in Hebrew) argues that certain forms of  futures trading (and Internet sites where these forms of trading take place) are essentially gambling activities.  The issue of “what is gambling” is very intereting. In an earlier … Continue reading →

Posted in Economics, Games, Law | 9 Comments

Chess can be a Game of Luck

Posted on July 5, 2009 by

Can chess be a game of luck? Let us consider the following two scenarios: A) We have a chess tournament where each of forty chess players pay 50 dollars entrance fee and the winner takes the prize which is 80% … Continue reading →

Posted in Controversies and debates, Economics, Games, Law, Probability, Rationality | Tagged , , , , , | 37 Comments

Social Choice Talk

Posted on June 2, 2009 by

I took part in a workshop celebrating the publication of a new book on Social Choice by Shmuel Nitzan which took place at the Open University. (The book is in Hebrew, and an English version is forthcoming from Cambridge University Press.) … Continue reading →

Posted in Economics, Games, Rationality | Tagged , , , | 2 Comments

Do Politicians Act Rationally?

Posted on March 9, 2009 by

Well, I wrote an article (in Hebrew) about it in the Newspaper Haaretz. An English translation appeared in the English edition. Here is an appetizer: During World War II, many fighter planes returned from bombing missions in Japan full of bullet holes. The … Continue reading →

Posted in Games, Rationality | Tagged , , , , | 4 Comments

Which Coalition to Form (2)?

Posted on February 17, 2009 by

Yair Tauman (This post is a continuation of this previous post.) Aumann and Myerson proposed that if political and ideological matters are put aside, the party forming the coalition would (or should) prefer to form the coalition in which its own power (according … Continue reading →

Posted in Games, Rationality | Tagged | 3 Comments

Which Coalition?

Posted on February 16, 2009 by

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 … Continue reading →

Posted in Games, Rationality | Tagged | 2 Comments

The Hex-Voting-Rule (Not Recommended)

Posted on February 3, 2009 by

Blue wins – if there is a right to left continuous path of blue regions Red wins – if there is north to south continuous path of red regions (A region is red or blue according to the majority of … Continue reading →

Posted in Economics, Games | 12 Comments