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 theory, one of the pioneers of computational geometry, and one of the leaders in optimization and linear programming, the guy who (with Ehud Kalai) was the first to  invited me to an international conference, and a fresh Laureate of the John von Neumann theory Prize.  I did not see Nimrod more than a year after our last coincidental  meeting at the Berkeley Simons Institute, I called over to him and he was happy to see me as I was happy to see him, and we found a place together at the back of the bus and caught up on things.

Nimrod showed me on the bus a picture he found in his house, taken by him at the  1974  game theory workshop in Bad Salzuflen, Germany. With Nimrod’s kind permission I present the picture here: (The copyright © belongs to Nimrod Megiddo who took the picture).


Here are some of the people left to right, (on some I already told you in other posts):

David Schmeidler (only beard visible)
Guillermo Owen
Lloyd Shapley
Sergiu Hart
Yair Tauman (only back shown)
Robert Aumann
Werner Güth (behind Aumann)
Reinhard Selten
Ehud Kalai (just to the right of Selten looking at the camera)
Gerhard Schwedihauer
Elon Kohlberg (only back shown, looking to the left)
William Lucas (in the back, looking at the wall)
Robert Weber (only hair and jacket visible)
Bezalel Peleg (looking to the right)
Joel Moulen (looking to the left)
Thomas Marschak (sunglasses and beard)
Michael Maschler
Joachim Rosenmüller (with glasses behind Maschler)
Kenjiro Nakamura

Happy new 2015!

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 the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw. Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

What would you expect the minimal value of Y is so the X player has a winning strategy?

We asked this question in our test your intuition series (#17)  in this post. Here is a recent new nice version of tic-tac-toe.

The poll:


The answer:


Continue reading

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 is 100+x where x is taken uniformly at random from the interval [-1,1]. With probability 0.1 the value is 300+x where x is as before. The 300 value represents the case that the item has a special nostalgic value for the buyer.

The values of the camera to the three bidders are thus i.i.d random variables. (The reason for adding this small random x is to avoid ties, and you can replace the interval [-1,1] with [-ε, ε] for a small ε, if you wish.) If you don’t want to worry about ties you can simply think about the value being 100 with probability 0.9 and 300 wit probability 0.1.

The basic question

The basic questions for you the seller is:

What is the highest expected revenue you, the seller, can guarantee and what is your optimal allocation policy.

I’d like to see the answer for this question. But let me challenge your intuition with two simpler questions.

1) Can the seller guarantee an expected revenue of 120  or more?

2) What (roughly) is the optimal allocation policy

a) Highest bidder wins.

b) Highest bidder wins if his bid passes some reserve price.

c) The item is allocated at random to the bidders with probabilities depending on their bids.

Background: Myerson’s paper and his revenue equivalence theorem

The most relevant paper to this post is a well-known paper Optimal auction design by Roger Myerson. Myerson considered the case of a single-item sealed-bid auction where the bidders’ values for the item are independent identical random variable.

Note that I did not specify the price that the winning bidder is going to pay for the camera. The reason is that according to a famous theorem by Myerson (referred to as the revenue equivalence theorem), when the bidders are strategic, the expected revenues for the seller are determined by the allocation rule and are independent from the pricing policy! (Well, you need to assume a reasonable pricing policy…)

For example, if the item is allocated to the highest bidder then the expected price will be the second highest price. If the price is determined by the second highest bid (Vickery’s auction) then each bidder has no incentive to give a bid which is different from its value. But even if the item will be allocated to the first bidder for the highest price, the expected revenues will still be the same! When you analyze an auction mechanism like ours you can assume that the payments are set in a way that the bidders have no incentive not to bid the true value the camera has. This is sometimes referred to as the revelation principle.

Myerson considered a mechanism which sometimes lead to higher revenues compared to allocating the item to the highest bidder: The seller set a reserve price and the item is allocated to the highest bidder if the bid passes this reserve price, and is not allocated at all otherwise. In the paper Myerson also considered more complicated allocation rules which are important in the analysis where the item is allocated to bidders according to some probabilities based on their bids.


This time we have two questions and two polls:

Once again this is a game-theory question. I hope it will lead to interesting discussion like the earlier one on tic-tac-toe.

A little more Background: Auctions and Vickery’s second price auction.

(From Wikipedia) An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder. In economic theory, an auction may refer to any mechanism or set of trading rules for exchange.

In our case, we consider an auction of a single item (the camera) and each bidder is giving a sealed bid.

(Again from Wikipedea) A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction, and in which the highest bidder wins, but the price paid is the second-highest bid. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893.[2] This type of auction is strategically similar to an English auction, and gives bidders an incentive to bid their true value.

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 men’s rank of their wives?

Boris Pittel proved that on average a man will be matched to the woman in place log n on his list. (Place one is his most preferred woman.) A woman will be matched on average to a man ranked n/log n on her list.

We asked in the post “Test your intuition (19)”  what is the situation if there is one additional man, and men are still proposing. This question is based on a conversation with Jacob Leshno who told me about a remarkable paper Unbalanced random matching markets by Itai Ashlagi, Yash Kanoria, and Jacob Leshno. Continue reading

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 there is a stable marriage, namely a perfect matching between the men and the women so that there are no men and women which are not matched so that both of them prefer the other on their spouces.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. On the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the previous day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most n^2+n days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Sababa!
It turns out that the above algorithm where the men are proposing and being rejected is optimal for the men! If a man M is matched to a woman W then there is not a single stable marriage where M can be matched to a woman higher on his list. Similarly this algorithm is worst for the women. But by how much?

Random independent preferences

Question 1:  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 men’s rank of their wives.

You can test your intuition, or look at the answer and for a follow up question after the fold.

Continue reading

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 in a 3 by 3 board – each player has a strategy that can guarantee a draw.

Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.

What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?

(Thanks to Reshef Meir and Moshe Tennenholtz)

Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…

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, algebraic geometry, and economics. It is certainly an object I would like to think more and  tell you more about. Here is a sculpture made by artist Ann Lehman based on such a body generated by a certain 4 by 3 matrix.


Ann Lehman: A sculpture based on a maximal lattice free convex body (photograph taken by the sculptress).

The body described in this sculpture is topologically a (two dimensional) disk, triangulated in a specific way. The boundary is a polygon embedded in 3-space consist of 21  “blue” edges. The “black” edges are internal edges of the triangulation. The triangles of the triangulation are not part of the sculpture but it is easy to figure out what they are and the shape has a remarkable zigzag nature. All vertices are integral. The only interior integral point is in “red”. (The “green” point is the origin, it is not in the body.)


Herb Scarf, me , and the sculpture (picture taken by Kareen Rozen)

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 come up with a post most relevant to your blog theme. The content would be fully yours.” Lenore only asked for a link back to her site . She sent me also a few of her articles like this one about finding jobs after graduation and this one about video games for training.

I asked Lenore to explore the following issue and she agreed:

Is the game Angry Bird becoming gradually easier with new versions so people get the false illusion of progress and satisfaction of breaking new records?

Stay tuned!

The Privacy Paradox of Rann Smorodinsky

rann  privacy

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 the sandwich of your preference (say, the avocado sandwich) adds one to your utility, but having your private preference known to the seller,  reduces by one your utility. The prior people have on your preferences is fifty-fifty.

If you choose the avocado sandwich your utility is zero, hence you can improve on this by picking each type of sandwich at random with probability 1/2. In this case your private preference remains unknown and you gain in expectation 1/2 for having the sandwich you prefer with probability 1/2.

But given this strategy, you can still improve on it by choosing the avocado sandwich.

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 for new areas where their models and concepts can make a difference. Physics, Economics, CS, Biology are just some examples, surely not exhausting a longer list of such areas. Although the origins of accounting emanate from mathematicians (for example: L. Pacioli, and even  A. Cayley found interest in it), it is a fact,  though not unexplained,  that these days  (almost) no mathematicians are interested in accounting and there is no field of “mathematical accounting”.  In the following few paragraphs I would like to thus draw attention to accounting as a possible field for mathematicians. Surprisingly, a possibly “profitable field”. I believe that accounting can be subject, inter-alia, to use of theories of Formal Systems, Information Theory, Voting  theory, Fuzzy Logic, Graph theory and even Catastrophe theory. In brief, accounting (Financial Reporting) deals with the measurement and reporting of economic events .  As such, it is a measurement system interlaced with an information system. (Results such as Blackwell theorem on the comparison of information systems are of relevance).

Financial reporting of firms, the lifeline of the Capital Markets, is dictated by “reporting standards”. Those reporting standards are determined by “standard boards” (according to voting rules and procedures, which are very interesting for analysis)  and interpreted and evolve over time (as is the case with other languages).   The reports are audited by accounting firms.  Auditing theory became more sophisticated  but even fairly standard tools like Benford Law are not yet routine.

Moreover, a huge debate centers on whether to adopt a rule-based system where “every” possible scenario is prescribed in advance or whether to adopt a principle based system which gives” freedom” to every reporting entity in reflecting the economic substance of an event.

It is well known that a rule-based systems provide greater comparability (between firms), but at the same time, as they are more rigid and make use of “bright lines”,  can be more easily forced to reflect form over substance . Indeed, Bright line Accounting rules are not continuous functions and hence small changes in the description or design of an event can lead to enormous differences in the reported values. For example, given that the definition of “CONTROL” was based on a “50% legal test” ,until recently it was the case that  if company A was holding 50.01% of the shares of company B (other holders being each  much smaller)  and sold only  1.02% it could recognize a profit, due to “loss of control”,  as though it sold the whole holding and bought back 49.01%. Needless to say that although holding “only” 49.01% , A CONTROLs B (Danny Ben Shahar, Desmond Tsang and Myself are in the process of demonstrating that “accounting theory of control” is inconsistent with Shapley Value).

Principle based systems, on the other hand, must make sure that its principles are common knowledge. For example, if a provision for loss regarding a claim against a firm depends on the chances of loss being “Probable” or  “remote” or “reasonably possible” a question arises what the preparers and users of the financial statements think about those terms. Many years ago, me and my colleague Yossi Aharoni found out-through questionnaires- that different types of agents have different probabilistic interpretations to those terms and we explained the mis-communication it can cause. I attach two simple papers (one co-authored with Danny Ben Shahar, the other one in hebrew),  that can shed some more light on the above point of view and I dare state a wish that a new field of “mathematical accounting” will be created .