You are currently browsing the monthly archive for September 2010.
Among game theoretic concepts, mixed strategy is arguably the most difficult to digest. We don’t see people tossing coins all the time, and it’s difficult to justify rational decision as based on Lady Fortuna’s unpredictable caprices. The case of Nash Equilibrium is especially disturbing — if you are indifferent between a couple of strategies then why bother randomizing between them according to the mixture prescribed by the equilibrium. Just pick one of these strategies arbitrary and get it over with.
I know of two types of answers that game theory gives for this conundrum. One, which may be called `interpretation of mixed strategies’ is arguing that the mixed strategies in Nash equilibrium do not reflect an actual randomization performed by the players: Epistemic game theory interprets mixed strategies as opponent’s beliefs about a player’s (non-randomized) strategy; Harsanyi’s Purification approach embeds a normal form game in a larger game with incomplete information and pure equilibrium. The other type of answers is identifying classes of games which admit pure equilibrium, such as games with strategic complementarity and potential games.
In my new paper with Yaron(pdf) we suggest another class of games which admit pure 
Math and open problems below the fold…
The Nile river, which is the longest river in the world, flows from Lake Victoria deep in Africa, which is itself fed by various rivers, through Uganda, Sudan and Egypt until it reaches the Mediterranean sea. On its way it meets the Blue Nile that comes from Ethiopia. The rivers that feed Lake Victoria pass through Zair, Kenya, Tanzania, Rwanda and Burundi. Many countries, they all need water, the needs of the growing populations increase, and one can see that problems are bound to appear. Egypt, the strongest among the countries that use the water of the river is also the most populated one, but it is located downstream: it is the last country to receive its water. Fortunately for the Egyptians, the British who occupied the east of Africa at the beginning of the 20th century wanted to assure the flow of water to Egypt. By an agreement from 1929, 55 billion cubic meter of water out of the 84 billion that flow anually in the river go to Egypt. This agreement was re-affirmed in 1959. Plainly Egypt is happy with this agreement, while the countries that lie upstream are less happy. In fact, these days they try to change the water distribution. This of course maddens Egypt, who unfortunately cannot do much: it lies downstream, so it does not control the flow of the river, and it is far away from the origin of the river: Sudan, whose length from north to south is roughly 2,000 kilometers, separates Egypt from the upstream countries, so Egypt cannot credibly threaten these countries if they decide to use water more than their share according to the 1929 accord. What should be done?
Not surprisingly, game theory does have something to say on this issue. Ambec and Sprumont identify the efficient allocation – the allocation that maximizes the sum of utilities of the various countries; they then present the situation as a cooperative game, find that it is a convex game and therefore has a non-empty core, and further study some properties of this game and its core. There are additional follow-up papers. I did not work out the details to say what Ambec and Sprumont will give to Egypt, but I suspect that it is not applicable. For example, the river flows through Sudan before entering Egypt. Egypt is militarily stronger than Sudan. Egypt may be able to force Sudan into not using the Nile water be credible threats. Egypt, who lies on the mediterranean sea, can desalinate water; this option is not available to Ethiopia, Rwanda and Burundi, who do not have sea-shores, and it will be much more costly to Sudan, whose capital lies far from the red sea. So the game is not a simple game as described by Ambec and Sprumont, but as usual in life it has specific features.
I guess that the nine Nile-river countries will have no choice but to sit together and find a solution that will ensure that all of them have water. Will they? At present Egypt is not ready for that. “Violating Egypt’s quota of Nile water is a genocidal war against 80 million people,” an Egyptian commentator, Hazem el-Beblawi, wrote this year in Al Masry Al Youm, an Egyptian daily <quotation taken from New York Times>. It surprised me to read that Egypt uses this type of rhetoric, the same type of rhetoric that is sometimes used by other strong nations who do not want to cooperate and give up something they unfairly have. But Egypt will have no choice but to cooperate, otherwise it will lose its water.
Back to game theory: can we come up with a model that resembles the Nile river problem more accurately, and takes into account other factors that affect the outcome, and not only the river?
The GDP is an index for ranking countries by their overall economic output. As we all know, economics is important, but it is not all that counts. In particular, the GDP does not take into account the population utility, which is much more important than the GDP. The HPI, Happy Planet Index, is an index that “is based on general utilitarian principles — that most people want to live long and fulfilling lives, and the country which is doing the best is the one that allows its citizens to do so, whilst avoiding infringing on the opportunity of future people and people in other countries to do the same.” So the HPI is one possible index that measures some aspects of our life which are not material. One can object to how it does it or to the principles that underlies it, but certainly it is a good step towards better life.
To find the HPI of a country, a random sample of its population is interviewed, the answers are then analyzed, and the index of the country is found. In 2009, various countries in Latin America were ranked on top, European countries were ranked in places 50-60, Japan was ranked 75 and the US was ranked 114. Zimbabwe closed the list of 143 countries.
In fact, one can calculate his or her own HPI at the site http://survey.happyplanetindex.org/. I did it, and found that my HPI is 59.9; if I were a country, I would have ranked 13 in the world, between Egypt and Saudi Arabia. Apparently one cannot run away from one’s neighbors. If I did not forget my hour and a half taiji class, I may even come before Egypt, who knows.
As usual with surveys, this survey draws conclusions from scant data. For example, my life expectancy is 92.2 years. Not 92.1 and not 92.3. Given the unstable political situation in the middle east I would be far more conservative, but apparently the HPI knows more than I do. My “ecological footprint is 5.23 global hectares, or 2.91 planets. [I am] using between two and three times [my] share of the planet’s resources.” Very nice given that I was only asked about my spending on electronic equipment in the last 12 months (more than 500 pounds), about my home (apartment), my car (less than 20 miles to work) and my diet (mixed diet of fruit, veg & pulses, with meat no more than twice a week).
Yet the thing that surprised me most is a short sentence in the feedback that I got after completing the survey: “research shows that when people are commuting they are less happy than any other time of the day, including when they are at work.” Is that true? I like my commuting moments: between 20 and 30 minutes from home to the university and back. When I was young I used to think of research problems while traveling to/from university; then I used to listen to audio stories; then I used to talk with my grandmother, until she passed away; and now I talk with my mother and think again on mathematical problems. I guess that if we want to increase the HPI of the population, we need to develop a program that would teach commuters how to use their time during rush hour; quite easily the US can climb higher in the HPI ranking, maybe even pass the Palestinian Authority (56) or Haiti (42).
I have two kids, ages 14 and 11; you may have met them at Stony Brook. We have three PC’s at home so that we can work at the same time and play together using our home network. The PC’s stand one next to the other in the same room. This way we are together even when each one works on his own things, and I have control over the sites they visit on the net. In general, I do not allow telephones/TV/PC in bedroom: all devices that can cause a family member to be locked in his room must be located in public areas.
A couple of days ago my older son asked whether he can purchase his own laptop from his own money. Why do you need a laptop? I would like to write stories, and it is difficult to concentrate in the room-with-computers. Correct answer, for which I have no counterarguments. Yet so far he did not write so many stories, and he does not have much time to write stories anyway. Anything else? I may also read my e-mail. Wrong answer; this is exactly what your father is afraid of. You can use my laptop. Your laptop is not always available, and I cannot use it when I am at mom’s house. That’s correct. I am afraid that you will use the laptop for other activities, be locked in your room and we will never see you again. I can delete Internet Explorer.
So here is where we stand. The kid wants a laptop, I know that writing stories on the laptop is just the first step, and that even if now he will use it only for that goal, in some years he will use it for games, surfing, chatting, and all the things that kids in his age will do, and we will see him only for meals. I may fight windmills, like Don Quixote, and in few years anyway he will be locked in his room, but I have hopes that I can keep some social activity even when the kids are 17-year old. I also do not exclude the possibility that writing stories is nothing but an excuse: a reason he came up with so that I allow him to purchase a laptop, but in fact he wants the laptop for other reasons.
What should I do? Any suggestions?
And, Eran, this is one example for the use of strategic thinking in raising kids. Once you think of the consequences of your decisions, and try to figure out the reasons for you kids’ requests, you enter the zone of game theory. Others may use different terms, but, after all, each one uses the terms that he knows.
On Sunday we had an excursion to Palermo, the capital of Sicily that houses more than 150 churches, according to our guide. After visiting few of the churches and the impressing cathedral, which is build in many different architectural styles, our bus continued to the cathedral in Monreale, 8 kilometers from Palermo. On our way to Monreale, we stopped to have lunch at the restaurant that is located on the top floor of Hotel Guglielmo. I will not dwell on the food, which was standard. I will dwell on another aspect of the restaurant: its floor rotates. The walls of the restaurant are nothing but glass, to allow the visitors to appreciate the landscape. To add to the eating experience the architect added a rotating floor, so that one will be able to see all the land that surrounds the hotel, and not only one portion of it. Brilliant, is it not.
Unfortunately, the correct answer is Not. I do not know whether you have ever had the experience of eating while rotating. This is worse than eating while on an airplane. You feel dizzy, and food is not the first thing that comes to your mind. A rotating restaurant seems a great idea: something that will attract tourists, who will be willing to pay extra for the once-in-a-lifetime meal. In fact, the tourists were dizzy, paid extra for the dubious pleasure, and the engine that rotates the floor made a lot of noise, so that the music had to be turned full-volume to cover the horrible noise.
I am sure that this carousel cost a lot for the proprietor. Either not enough thought has been put in the matter before it was installed, or maybe this is the first place ever it was tried, and so architects did not know the effect of rotation on diners. But now that the construction cost is sunk, why do they keep on operating this carousel, instead of letting people enjoy the view without moving around? We were all relieved when, after one full round, the floor stopped moving and we could finish our meal peacefully.
<Edited on September 24, following comments of Jason Hartline>
A gambler has to choose at every stage t whether to take the current prize A_t that is offered to him and go home, or whether to forgo the prize in the hope that he will get an even higher prize in the next stage. The prize A_t is chosen according to a known distribution F_t, and the process continues for T stages.
Clearly, at stage T the gambler will take the prize that is offered to him. One can then calculate by backward induction the optimal strategy of the gambler. This strategy will be a threshold strategy: for every t there exists a threshold q_t; if the prize offered at stage t is higher than q_t, the gambler will take the prize and go home, otherwise he will wait and hope for a higher prize in the future.
To calculate this strategy one needs to find the T thresholds. Apparently there is a simple strategy that is not optimal yet it is 1/2-optimal: it ensures an expected payoff which is at least 1/2 of the optimal payoff. This strategy is a threshold strategy: there is a threshold q_* such that the gambler accepts the prize if and only it is higher than q_* (regardless of the stage). In particular, it may well happen that the gambler will not accept the prize at stage T, if the game reaches that stage. The proof uses the Prophet Inequality, and was shown to us by Jason Hartline in a remarkably interesting presentation.
Jason went on and generalized this basic observation to a mechanism design setup. A single item is offered for sale on an auction. The private values of the n bidders are independent. By Myerson (1981) we know the structure of the optimal mechanism: for each player there is a function that transforms his bid into a virtual price. Then one runs a second price auction with reserve prices on the virtual prices, where the reserve price is bidder dependent. In practice the assumptions of Myerson’s theorem do not hold: private values need not be independent and their distributions need not be common knowledge. Moreover, setting bidder-dependent reserve prices will never work. It turns out that a second price auction with bidder-dependent reserve prices is a 1/2-optimal mechanism for the seller in a wide range of applications. If one insists on a common reserve price, then a second price auction is a 1/4-optimal mechanism for the seller, provided one carefully chooses the common reserve price.
Jason and co. have more results on simple mechanisms that approximate the optimal mechanism in various setups, but I am afraid that my description of these results will not be accurate, and that I will get tons of complaints on my sloppiness. So please do read his and his co-authors’ work. The original is always better than copies.
Wherever you find tourists, you find tourist shops, those shops that sell things specifically for tourists. Erice is no exception: the two castles and the few churches attract tourists, and attract vendors for tourists. What type of marchandise do you find in those shops? T-shirts with a large “Sicily” spread over the front; well, if you have kids and you have to bring presents back home, then such shirts are what you need. T-shirts with Homer Simpson and “Godfather” below it; I guess that young people who still find this funny may enjoy this T-shirt. Hats; if you forgot to bring a hat (or lost it) you do need one. Bags. Cheap Jewellery. T-shirts which say “I love you”. These you can find in your home town, and for less price. If the shops offer these items for sale, it means that they have a market. So the question is: what makes tourists buy those items that bear no relation to the place they visit, and that they can purchase at home for less money?
When and where was the first share issued? Babylon? Rome? Italy during Renaissance? Reuters reports that a dutch student of history, who is an assistant to the mayors of the town of Enkhuizen, found the first share that was issued by the dutch sea trading firm East-India Company in 1606. The company was supposed to pay dividends to the shareholders until 1650, but it started to pay them only in 1610, due to financial difficulties. Payment was in money and spices. The share is going to be displayed at the Westfries Museum in the Netherlands. This is a piece of history.
Every game in strategic form (a matrix game) has an equilibrium in mixed strategies. But finding an equilibrium in a specific game is a difficult problem. Gilboa and Zemel proved that this is a computationally difficult task: it is NP-hard to determine whether a specific game has a Nash equilibrium where both players gets non-negative payoffs. Computer scientists, who adore giving names to classes of problems, call the class of problems that are computationally equivalent to this problem PPAD.
The Folk Theorem tells us that the set of Nash equilibria of a repeated game is the set of feasible and individually rational payoffs. It therefore seems that this problem is simple. Indeed, the set of feasible payoffs can be easily determined from the payoff matrix, and the individually rational level of a player in a two-player game can be found using a linear program. The catch is that this is true only for two-player games. Apparently the determination of the min-max value of a player in a three-player game is difficult. In fact, a recent paper by Christian Borges, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni and Christos Papadimitriou shows that this problem is PPAD: it is as hard to calculate the individually rational level of a player in a three-player game as it is to find an equilibrium in a two-player game. So finding equilibria in repeated games is neither easier nor harder than finding equilibria in one-shot game. The six authors ruined our belief that repeated games are easy to play. Thanks guys.
And thanks to Jason Hartline who brought this paper to my attention.
This is one of the best workshops I have been to. No parallel sessions, long breaks, focused scope so speakers can assume some background, and 45 minutes talks, so we are spared the race over slides that usually occurs in 25 min conference talks. The only minus so far is no blackboard, which is why I stayed in Erice today to prepare the slides for my talk tomorrow instead of going to the tour to Trapani. No complains though. it’s fun walking around in the cobbled streets, there is an awesome view from Venus Castle, and I can’t have enough latte di mondorla.
So, automatic chairing: The clock is ticking, the amount of time left in a talk is visible to both the speaker and the audience on a large screen, and the bell rings a `three min left’ warning, and rings again at the end. All without human intervention. Nobody has to suffer the misfortune of the last speaker in a session, who is usually also the chair. If you have ever been in this position you know what I mean: You are always busy trying to make the first speakers notice that you are holding a piece of paper with the number 5 on it. When they finally can’t pretend not to see it, it’s actually already two minutes after their time, and in addition they give you that shocked and offended look `So your watch is more interesting than my model ?’ You end up feeling bad and not having even the 25 minutes for your own talk.
Oh, and Kudos to Eilon for a general audience presentation in a joint session with the other workshops that take place here, and especially for brave correspondence with a dude from the engineering workshop, who I think was asking about applications of Blackwell & Fergurson to combinatorial optimization and aerodynamics.
The Leisure of the Theory Class 
Recent Comments