You are currently browsing the monthly archive for August 2010.
One of the assumptions of von-Neumann and Morgenstern’s utility theory is continuity: if the decision maker prefers outcome A to outcome B to outcome C, then there is a number p in the unit interval such that the decision maker is indifferent between obtaining B for sure and a lottery that yields A with probability p and C with probability 1-p.
When I teach von-Neumann and Morgenstern’s utility theory I always provide criticism to their axioms. The criticism to the continuity axiom that I use is when the utility of C is minus infinity: C is death. In that case, one cannot find any p that would make the decision maker indifferent between the above two lotteries.
This morning during breakfast my younger son provided a different type of counter example to the continuity axiom. Every morning my son has a yogurt; a specific type of yogurt, that comes with a side bin full of chocolate balls, that you should pour into the yogurt before eating it. The balls are made of white chocolate, dark chocolate and milk chocolate.
My son prefers the white chocolate, and so he counts the number of white chocolate balls before he eats the yogurt; the higher the number, the happier he is. Today the older son had a bright idea: why don’t we call the producer and ask it to produce yogurts with only white chocolate balls! Brilliant. The younger kid opposed this idea: he prefer the current lottery, where he does not know the outcome, to obtaining the best outcome with probability 1.
So my son does not satisfy von-Neumann’s and Morgenstern’s axioms, and so all the deep theory that I use in raising the kids is useless.
Maybe you’ve been wondering like many whether the advertisement-funded business model for TV can survive the DVR. Well, last night while fast-forwarding the commercials of “Mad Men,” I stopped my DVR after what seemed like a surprising short break. Except the commercials weren’t over — an advertiser had designed a spot with similar costumes (i.e. 60s throwbacks) and scenarios to the show! Since the show is about an ad agency, there are actually 3 layers of tangled levels here, but the first two could be applied to any show. Another technique that evades the DVR is product placement within a show. The industry isn’t dead yet.
At 7:30PM, while the kids were in the middle of building a rock castle, a schoolmate of my 10 year old kid came to our home. She ran away from home, and so she came to the home of her best friend. How logical.
Immediately I thought of the Prisoner’s Dilemma. If your kid runs away from home and drops by at a friend’s home, you would like the friend’s parents to host your kid. But you yourself are better of sending your runaway child’s friend back to his home, or letting him find another friend to host him. So this game is the Prisoner’s Dilemma: sending the friend away is a dominant strategy, but both parents prefer that they both host each other child to having both kids stroll around in the streets looking for a friend with friendly parents.
I did not need to analyze the game to know that what I should do, and I sent an SMS to the friend’s mother telling her that her precious daughter is safe and sound. It is left to see when the runaway kid will decide to return home.
Johannes Horner, Massimo Morelli and Francesco Squintani issued a new discussion paper whose title is similar to the title of this post. Longing for peace in my region, I immediately set out to read the paper. Who knows, maybe the peace will come from that paper. What did I find?
There are two parties who fight over a cake of size 1. Each player has a private type, H or L, which is drawn with probability q (for H) and 1-q (for L). There is incomplete information about the type of the other player. If the players agree on a division (x,1-x) of the cake – that’s great. If not, war ensues, and the cake’s size shrinks to theta. Who wins the war? If the two parties have the same type, each has probability 1/2 to win the war. If they have different types, type H wins with probability p>1/2.
This basic model defines a game with incomplete information, and it is a nice exercise to solve it. The trio go on and analyze variations of this basic model. One variation concerns the case where the players can communicate prior to war declaration: each player can send a costless message to the other (about his type). Another variation, from which the title is derived, concerns the introduction of a mediator, who receives private messages from the players and can propose a division or recommend war. The third variation concerns the introduction of an arbitrator who can enforce his recommendation. In addition to solving the various models, the trio shows that an arbitrator who can enforce his recommendation is as effective as a mediator who can only propose self-enforcing agreements. Cool.
After reading the paper I was left with a little sour taste. The model is interesting, I am sure that the equilibrium calculations are not trivial and perfectly executed. But will this paper bring peace to the worn Middle East? I doubt it. First, there is no incomplete information about the other party’s type: after so many years of struggle, each player knows perfectly well the player he is facing. Second, if mediation breaks down, war does not necessarily ensue. Indeed, in 2000 war followed the breakdown in negotiation. But most probably this will not happen in 2011, after the current round of negotiation fails. And after one round of mediation fails, there is always place for another round. And the relative power of the players changes over time: one day Israel attacks a ship that brings food to Gaza and the Palestinians receive points in the international arena, the other day Israel makes some concession and it gains points. The international arena is not modeled at all. And war itself is not the final outcome; it is just one step towards reaching your goal (is the goal an agreement?). This was exhibited nicely by the 1973 war between Israel and Egypt-Syria, that followed negotiations that led to nothing and was followed by the Egypt-Israel peace treaty. The Palestinian’s Intifadas, uprisings against Israeli rule, were also one way to influence Israel’s attitude towards the Palestinians.
We always have to start somewhere, with a simple model that we can analyze. But I fear that this paper will not help Israeli Prime Minister Netanyahu, Palestinian Chairman Mahmoud Abbas, and the American mediators find the formula of peace.
The web-site of the New York Times tells us a some “neutral” news (midterm elections, US rejects Hen vaccine), some bad news (attacks in Iraq, floods in Pakistan, mine collapse in Chile), and no good news.
The Washington Post also tells us neutral news (more midterm elections), and more bad news (Al Qaeda threat in Yemen, cyberattack, regulatory failure in Mineral Management Service, and again, no good news.
The British Telegraph tells us about an irresponsible pathologist, a murdered British spy, the tube strike, 72 bodies found in Mexico, but here I found one piece of good news: sales of Rover’s twin brother, the Roewe, soar in China.
Another ray of hope is the French Le Monde. It tells us about Romanians and Bulgarians who were deported from France and deaths in Bangla Desh, to remind us of the somber world we live in, but it also tells us one piece of good news, about a couple who finished a 10-year restoration of their 18th century weekend house, which was in ruins when bought.
The largest Newspaper in Israel surprised me. In addition to the usual bad news on the Israeli-Palestinian struggle, it tells us about a man who got a new heart implant, and starts living again.
Bottom line: we read many neutral and bad news on the front page of newspapers, but hardly any good news. The paper version of newspapers is even more somber than their web-site, where space is more pricey. Why is that? Is it that good news do not sell? Don’t we want to know that a new wing was opened in a children hospital, that the chances of survival of some rare species have increased because of a new plan of the international Zoo organization, or that the city of New York decided to invest $5M in hockey teams to increase the chance that the US wins the next Olympic games in hockey? What is the effect that “no good news” have on us? Are we more somber because the news are more somber? Are we less likely to help others because we do not read in the news that this is a possibility? Do we become more aggressive because the news are more aggressive?
I call for an increase in the number of good news: let every newspaper publish (at least) one piece of good news on each page. I am sure that this would make our world a more pleasant place to live in. Or at least, it will make the newspapers more pleasant to read.
Some asked and Patricia L. obliged. My thanks to her.
On the long flight from Shanghai to Chicago, the mind wanders. I chanced upon the observation that a number of prominent young theorists cut their hair close to the skull. Horner (Yale), Shmaya (Northwestern), Sandholm (Wisconsin), Chassang (Princeton), Szentes (LSE), Maccheroni (Bocconi), Sarver (Northwestern)………Clearly, unlike Samson, their locks are not the source of their power. The qualifier `young’ is important because after a certain age it may not be a choice. Non-theorists of the same vintage as far as I can tell (while trapped in coach) favor a less ascetic style. Are the shaved heads a symbol of monkish devotion to truth? Does it stimulate the phagocytes (in which case I’m off to the barber)? Is it a mark of membership in a secret society? Inquiring minds want to know. I’m also fairly certain that I will live to regret this post.
We are in front of a new job-market season, when all old Ph.D. students look for jobs. They will send out their packages, which are bound to be heavy, because there is some belief that long papers are better than short papers. They did not invent this technique, writing long papers. Look at Econometrica or JET, and you will find many papers with an extremely long introduction, that could be summarized in half the space. A paper of 50 pages is the standard. How many bright ideas require 50 pages?
When I was in high school, I had to do a chore on “Crime and Punishment”. To those lucky ones who didn’t have to read it, I will reveal that it is more than 1000 pages long. I simply couldn’t do it. I had a 400-page shorter version. I couldn’t read it either. Eventually I settled for a 50-page summary. And I got the second highest grade in class. So either the other students didn’t even read the 50-page summary, or the 50-page summary is enough to get the essence of “Crime and Punishment”. I am confident that this is not unique to Russian writers, and most 50-page papers can be summarized in 10 pages.
So why do Economists write 50-page papers? Why did we drift to this equilibrium that make us give up reading papers, because they are too long?
Unfortunately (or maybe fortunately) players tend to be boundedly rational. Our computational power is bounded, our memory is bounded, the number of people that an organization can hire is bounded. So it makes sense to study games in which players can use only a restricted set of “simple” strategies. This topic has been extensively studied in the late 80’s and 90’s in the context of repeated games. Eran advocated in previous posts the set of computable strategies. This set of strategies indeed rules out complex strategies, but it still allows unbounded memory.
Two families of strategies in repeated games have been studied in the past to model players with bounded computational power: strategies with bounded recall and strategies implementable by finite automata. A strategy with recall k can recall only the last k action profiles chosen by the players; whatever happened in the far past is forgotten. An automaton is a finite state machine: it has a finite number of states, and in each stage one of the states is designated the “current” state. In every stage, the machine has an output, which is a function of the current state, and it moves to a new state (which is the new “current” state) as a function of its current “current” state and of its input. If the set of inputs is the set of action profiles, and its set of outputs is the set of actions of player i, then an automaton can implements a strategy for player i. Unlike strategies with recall k, an automaton can remember events from the far past, but because the number of its states is bounded, the number of events that it can remember is bounded.
Prominent game theorists, like Abreu, Aumann, Ben Porath, Kalai, Lehrer, Neyman, Papadimitriou, Rubinstein, Sabourian, Sorin, studied repeated games played by finite automata, and repeated games played by players with bounded recall. Here I will restrict myself to finite automata.
In a nut-shell, the theoretical literature is divided into two strands:
1) Two-player zero-sum T-stage repeated games, where each player i is restricted to use strategies that can be implemented by automata with n_i states. Here the question is how the value depends on T, n_1 and n_2. This strand of literature allows one to answer questions like: how does the relative memory size of the two players affect the value of the game? Or, how much a player should invest in increasing his memory so that his payoff significantly increase?
2) Two-player non-zero-sum infinitely repeated games, where the players have lexicographic preferences: each player tries to maximize his long-run average payoff, but, subject to that, he tries to minimize the size of the automaton that he uses. Abreu and Rubinstein proved that the set of equilibrium payoffs significantly shrinks, and one does not obtain a folk theorem. Rather, the set of equilibrium payoffs are only those payoffs that are (a) feasible, (b) individually rational (w.r.t. the min-max value in pure strategies), and (c) can be supported by coordinated play: e.g., whenever player 1 plays T, player 2 plays L, and whenever player 1 plays B, player 2 plays R.
In practice, the memory size of the players is not fixed: players can increase their memory at a given cost, and sometimes they can decrease their memory size thereby reducing their expenses. This raises the following question: suppose that memory is costly, say, each memory cell costs x cents, and the utility is linear: the payoff of a player is the different between, say, his long-run average payoff in the game and the cost of his memory (x times his memory size). Say that a vector y=(y1,y2) is an Bounded Computational Capacity equilibrium payoff if (a) it is the limit of equilibrium payoffs, as the memory cost x goes to 0, and (b) the cost of the corresponding automata (that implement the sequence of equilibria) goes to 0 as x goes to 0. What is now the set of Bounded Computational Capacity equilibrium payoffs?
It is interesting to note that a Bounded Computational Capacity equilibrium payoff need not be a Nash equilibrium payoff, and a Nash equilibrium payoff need not be a Bounded Computational Capacity equilibrium payoff. Do I have an example that this actually happens? Unfortunately not.
It turns out that the set of mixed-strategy Bounded Computational Capacity equilibrium payoffs includes once again the set of feasible and individually rational payoffs (w.r.t. the min-max value in pure strategies). In this context, a mixed-strategy is a probability distribution over pure automata (so a mixed strategy is a mixed automton, and NOT a behavior automaton. The output of a behavior automaton is a mixed output). A mixed automaton is equivalent to having a decision maker randomly choose an agent to play the game, when each agent implements a pure automaton. Mixed automata naturally appear when one player does not know the automaton that the other player is going to use, and therefore he is in fact facing a distribution over automata, which is a mixed automaton.
So, to those of us who know Abreu and Rubinstein (1988), it turns out that their result depends on two assumptions: (a) memory is free, and (b) players are restricted to use pure strategies (that is, pure automata). These two requirements imply that the players must use simple strategies, and they will both use automata of the same size. Once memory is costly, and players can randomly choose their pure automaton, they can restore their ability to choose complex strategies, thereby restoring the folk theorem.
Well, a small step for research, a tiny step for humanity.
MacFreedom is an application that disables network connection for a period of up to eight hours. Actually it doesn’t mean you absolutely can’t restore the connection if you really must check on facebook what your elementary school classmate had for lunch yesterday, but you do have to restart your computer for that. So by using Freedom you force yourself to exert some effort in order to browse around. Therefore you are less likely to actually do it, and you can spend your time more productively on your tenure package research.
Economists sometimes talk about `multiple selves’ model. I never actually managed to get through a behavioral econ paper, but I think it goes something like this: There are two Erans. A sophisticated, long term planning `E1′ and a lazy, self-serving, easily tempted `E2′. As long as they (that is to say, I) are planning to do stuff, E1 is in charge. But when I actually sit down in front of my laptop to read Blograshevski et al. Econometrica 1974 `The multiple selves model in a dynamic multi-valued auction with hyperbolic discounting’, E2 takes control. Since E1 is sophisticated, he uses Freedom to disconnect from the universe for sixty minutes just before E2 arrives, so that E2 will have to pay the cost of rebooting before he can delve into the blogosphere. Presumably, between Blograshevski and rebooting, E2 might actually prefer Blograshevski.
Well, this used worked for me: I have Freedom to thank for some of the few papers that I actually managed to read or write. But here enters another, less abstract, economic idea — if E1 benefits from using Freedom, then he should actually be willing to pay for it ! Indeed, Freedom started as a freeware, then a donationware, and now it costs $10.
The economic reasoning does not work on this particular E1 though. Sorry, but paying for internet and then paying again for not being able to use the internet is just too humiliating, selves or no selves. As somebody mentioned, the next thing you know credit card issuers will ask E1 to pay fee for the service of increasing E2’s over-the-credit-limit fee.