Category Archives: Games

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 , , | 3 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

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 , , | Leave a 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 | 4 Comments