Category Archives: Games

Second third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Dear all, here is the draft of the second third of my paper for ICM 2018. Corrections and comments are very welcome! This part is around voting games and election rules, Boolean functions and their Fourier representation, noise stability and sensitivity … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games | Tagged , , , , , | 3 Comments

First third of my ICM2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

I have a very strict December 20 deadline (self-imposed, I missed the official one)  for my ICM2018 paper. I plan to talk about three puzzles on mathematics, computation and games, and here is a draft of the first third. Corrections … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games, Updates | Tagged | 12 Comments

Sergiu Hart: Two-Vote or not to Vote

  Sergiu Hart raises a very interesting idea regarding elections. Consider the Brexit referendum. Sergiu  proposes to have two rounds two weeks apart.  Every voter can vote in each, and the votes of both rounds add up! The outcomes of … Continue reading

Posted in Economics, Games | Tagged , | 13 Comments

Layish

This story is implicitly referred to in the 2008 opening post of this blog. ———– It was high time to raise the level of the discussion, I thought. Princeton, Fall 1995. We were a group of mathematicians at the IAS … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games, Mathematics to the rescue, Philosophy, Rationality, Sport, Taxi-and-other-stories | Tagged , , | 6 Comments

Is Heads-Up Poker in P?

Five years ago I wrote a post entitled Is Backgammon in P? It was based on conversations with Peter Bro Miltersen and Uri Zwick (shown together in the above picture) about the computational complexity of computing the values (and equilibrium … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games | Tagged , , , , | 3 Comments

The Median Game

Update: Apparently this game was invented already by Douglas Hofstadter who called it  “Mediocrity” and it is published in Hofstadter’s book Metamagical Themas: Questing for the Essence of Mind and Pattern. It is also called “Hruska.” (See here and here.) Ehud Friedgut … Continue reading

Posted in Games | Tagged | 4 Comments

A Historical Picture Taken by Nimrod Megiddo

Last week I took a bus from Tel Aviv to Jerusalem and I saw (from behind) a person that I immediately recognized. It was Nimrod Megiddo, from IBM Almaden, one of the very first  to relate game theory with complexity … Continue reading

Posted in Conferences, Economics, Games | Tagged , | Leave a comment

Auction-based Tic Tac Toe: Solution

Reshef, Moshe and Sam The question: (based on discussions with Reshef Meir, Moshe Tennenholtz, and Sam Payne) Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking … Continue reading

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

Test Your Intuition (21): Auctions

You run a single-item sealed bid auction where you sell an old camera. There are three bidders and the value of the camera for each of them is described by a certain (known) random variable: With probability 0.9 the value … Continue reading

Posted in Economics, Games, Test your intuition | Tagged , , | 4 Comments

Itai Ashlagi, Yashodhan Kanoria, and Jacob Leshno: What a Difference an Additional Man makes?

We are considering the stable marriage theorem. Suppose that there are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average … Continue reading

Posted in Economics, Games, Probability, Test your intuition | Tagged , , , , | Leave a comment