Category Archives: Games

Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

Stable mariage The Gale-Shapley stable matching theorem and the algorithm. GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then … Continue reading

Posted in Combinatorics, Games, Probability, Test your intuition | Tagged , , , , , , | 7 Comments

Test Your Intuition (17): What does it Take to Win Tic-Tac-Toe

(A few more quantum posts are coming. But let’s have a quick break for games.) Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares … Continue reading

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

Ann Lehman’s Sculpture Based on Herb Scarf’s Maximal Lattice Free Convex Bodies

Maximal lattice-free convex bodies introduced by Herb Scarf and the related complex of maximal lattice free simplices (also known as the Scarf complex) are remarkable geometric constructions with deep connections to combinatorics, convex geometry, integer programming, game theory, fixed point computations, … Continue reading

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

Angry Bird Skepticism

Lenore Holditch is a freelance writer. Here is what she wrote to me: “I love learning about new topics, so I am confident that I can provide valuable content for your blog on any topic you wish, else I can … Continue reading

Posted in Games, Rationality | Tagged , , | 1 Comment

The Privacy Paradox of Rann Smorodinsky

   The following paradox was raised by Rann Smorodinsky: Rann Smorodinsky’s Privacy Paradox Suppose that you have the following one-time scenario. You want to buy a sandwich where the options are a roast beef sandwich or an avocado sandwich. Choosing … Continue reading

Posted in Games, Philosophy, Rationality | Tagged , , | 17 Comments

Eyal Sulganik: Towards a Theory of “Mathematical Accounting”

The following post was kindly contributed by Eyal Sulganik  from IDC (Interdiciplinary Center)  Herzliya. Eyal was motivated by our poll on certainty “beyond a reasonable doubt,” which is related to several issues in accounting. Mathematicians, I believe, are always looking … Continue reading

Posted in Economics, Games, Guest blogger, Law | Tagged , | 3 Comments

Galvin’s Proof of Dinitz’s Conjecture

Dinitz’ conjecture The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994: Theorem: Consider an n by n square table such that in each cell (i,j) you have a set with n or more elements. … Continue reading

Posted in Combinatorics, Games | 6 Comments

Another way to Revolutionize Football

The angle of Victoria Beckham’s hat (here in a picture from a recent wedding) is closely related to our previous post on football One of the highlights of the recent Newton Institute  conference on discrete harmonic analysis was a football … Continue reading

Posted in Games, Mathematics to the rescue, Sport | Tagged , | 8 Comments

Is Backgammon in P?

  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 | 10 Comments

Subexponential Lower Bound for Randomized Pivot Rules!

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