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.

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

(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?

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 thatIdid not specifythe 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 priceand 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.

Polls

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.

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 →

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 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.

(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…

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)