You are currently browsing the monthly archive for May 2012.

We are all descendants of Adam and Eve. But no need to go that way back. The family tree of the great Chinese philosopher Confucius includes more than 80 generations and more than 2 million people, most of them alive. Researchers say that 17 million people are direct descendants of Genghis Khan, the greatest conqueror who ever lived.

Our world inhabits more and more people. We no longer live in villages in which everyone knows everyone else, but in large cities in which we know only few scores of people. We become strangers to each other, we close our eyes and hearts to people in need. We are not family.

But we are. A couple of years ago I prepared a family tree. Many archives from Eastern Europe were lost and my family was somewhat trimmed 70 years ago, and therefore I could climb up the tree only to 1880, in one branch I climbed up to 1830. Overall I have about 1800 people in my tree. Admittedly, many of them are not related by blood but rather through marriage, but nonetheless we are all family.

And then I thought: suppose that one prepares a huge family tree, that includes us all, all the 7 billion souls that roam the earth. We draw a huge graph where each person who ever lived is a node, and each family tie, each marriage and parenthood, is an edge. Every connected component in this graph is one huge family, a group of people who are related by blood and marriage. I guess that we will not end up with one connected component, because of small communities who remained closed for centuries, yet I bet that we will end up with one huge connected component that will include the vast majority of us.

Suppose that you knew that 95% of the people that you see are part of your family. This person who wants to cross the street is the cousin of the cousin of the cousin of aunt Bess. And that driver who drives so slowly is the nephew of the great-grandfather of your neighbor, who is the second niece, twice removed, of the wife of uncle Jim. Will you still honk like crazy?

A family tree may make us all feel like one huge family and help us be better people. On the other hand, it might diminish the significance of the notion of family; if we are all one family, even of those we dislike, then probably one should honk at everyone, family or not. What do you think?

Sergiu Hart organized a small conference on Game Dynamics that took place last week at the Center for Rationality in the Hebrew University of Jerusalem. Luckily for me, Sergiu also likes dynamic games, and therefore talks were on both subjects.

The conference was Sergiu’s style: first talk at 10:30, second at 11:45, then a long lunch break, and then two additional talks, at 15:00 and 16:15. In one of the lunch breaks I asked John Levy to explain to me his construction of a discounted game without a stationary discounted equilibrium. I will try to share with you what I learned. (John’s discussion paper appears here.)

There are m players labeled 1,2,…,m. What is m? It is sufficiently large such that the total discounted payoff from stage m onward has a little effect on a player’s payoff. That is, if the discount factor is β (so that the total discounted payoff is the sum over n of (β to the power n) times (stage payoff at stage n)), then we require that (β to the power m) is a small number.

Read the rest of this entry »

Last night, with about 8 minutes to go in the Indiana-Miami NBA playoff game, Danny Granger for Indiana picked up his 5th foul. Loyal readers will know that I was rooting hard for Granger to be left in (especially since, like so many fans, I would like nothing better than for Miami’s stars to take their talents home for a long offseason.) This time, my hope was actually fulfilled as the coach did not substitute. Just when the evening appeared to be a triumph for rationality, announcer Mike Breen said “Well, you have to leave him in…it’s an elimination game” (meaning a loss would eliminate Indiana.) Now, finding inane comments by sportscasters is like shooting garrulous fish in a barrel, but I think there are some common and important fallacies at work here, so let’s dissect why Breen would have said what he did. As in most fallacious thinking, he was applying reasoning which would apply in closely related situations, but not here.

1. Desperate times call for desperate measures. In some situations, this intuition can be invaluable. If you are down 3 points with time expiring, you had better try a 3. But it only applies to the state of the series if decisions have spillover effects from game to game. Now if we were talking about players becoming injured, or extremely fatigued, there might be spillover effects to the next game, and then you actually should consider the state of the series. But not for fouls (in basketball, unlike soccer.) Unless your decision affects the next game, you play to maximize your chance of winning the current game, whether ahead or behind in the series. The proverbial “one game at a time” really does apply here.

2. Leaving a player in with 5 fouls is a risky move. It’s easy to think this way, but wrong. I won’t rehash my earlier post. Incidentally, the argument I posted here appeared (independently, apparently) in the book Scorecasting, an enjoyable compendium of insights that go against sports conventional wisdom.

Lowest unique bid auctions became popular in recent years. In such an auction, a prize of value $M (a car, an elecronic gudget, etc.) is offered for sale. Each participant can purchase any number of natural numbers at the price of $c per natural number. The winner is the participant who purchased the minimal number among all the numbers that were purchased by a single player. He pays his winning bid (that is, the minimal number that was purchased only by him) and gets the object. If no number was purchased by a single player, no-one wins the object. I explained this game in more details in this post.

This game has a symmetric equilibrium. Indeed, in equilibrium no player will purchase more than M/c numbers, and no player will purchase a number higher than M (actually, no player will purchase M as well). Therefore the set of pure strategies that one should consider for an equilibrium is finite (all subsets of the set {1,2,…,M-1} that contains at most M/c numbers), so that by Nash’s theorem the game has an equilibrium in mixed strategies. Since the game is symmetric, there is in fact a symmetric equilibrium in mixed strategies.

Consider the following variation, in which the winner does not pay his winning bid. Now the set of all pure strategies that can be selected in equilibrium is infinite: it consists of all subsets of the set of natural numbers that include at most M/c numbers. Does this game have an equilibrium? A symmetric equilibrium? When there are two participants the answer is positive. What about more than two participants? I have no idea. Anyone can find the answer?

to service in the lower House of the republic. As evidence, consider the following observation about the census made by a first term congressman (named, ironically enough, Daniel Webster):

We’re spending $70 per person to fill this out. That’s just not cost effective, especially since in the end this is not a survey. Its a random survey.

Can flat earthers and book burners be far behind? On these occasions I think fondly of Heinlein‘s suggestion that citizens be required to demonstrate some mathematical proficiency in order to vote.

The first acronym stands for Massively Open On-line Course. They have been much in the news lately. At least three companies have been formed to commission and deliver them (coursera, udacity and edX). All claim that they will eventually generate revenues via certification. This is where the second acronym in my title, Educational Testing Service comes in.

MOOCS are a boon to the ETS and I’m surprised they have not jumped in to offer testing and certification for MOOCS. The courses on MOOCS are open. Many are at a basic level. Its easy to put together tests for them. The ETS has the infrastructure to deliver and administer those tests. In the short run, the ETS could `free ride’ off the MOOCS on offer. In the long run, the ETS could commission MOOCS offerings on particular topics either directly (or indirectly by announcing a test and the material to be tested for). In doing so, the ETS would cut out the hoped for revenues that coursera and udacity are counting on! Perhaps ETS could use those revenues to support MOOCS for SAT and AP test prep!

In the `longer longer’ run, what is traditionally covered in the first year of college of most US campuses (Econ 101, Psych 101), migrates on-line. Students enroll in the relevant MOOCS and take the tests administered by the ETS. Admission into universities is now pegged to performance on these tests rather than the SATs. The 2-3 years in University are spent in small seminars that emphasize the apprenticeship aspects of education.

On Monday, 7-May-2012, we had a one-day conference at Tel Aviv University, and awarded the 2012 Michael Maschler prize for an outstanding research student. The prize committee, comprised of three professors from different institutions, wrote:

Stochastic games have been introduced and studied by Lloyd Shapley in 1953.  Since then they have proved to be challenging to game theorists as well as useful in a wide range of applications in economics, evolutionary biology, and computer science.

Yehuda Levy has recently succeeded in settling a long-standing open problem concerning the existence of equilibria in stochastic games. This problem has attracted over the last four decades the attention of many scholars and was studied by the most capable researchers in the field. Specifically, the question was whether every discounted stochastic game has a stationary equilibrium.  Levy answers this question in the negative. His work on this problem goes well beyond just solving it. He constructs a discounted stochastic game without a measurable stationary equilibrium, which, moreover, has neither a stationary correlated equilibrium, nor a stationary approximate equilibrium. Levy also proves that a stochastic game with a continuum of states and with transition probabilities absolutely continuous with respect to some fixed measure, need not have a stationary equilibrium. This result contrasts with the known existence of stationary approximate equilibria in this case.

In his work Yehuda Levy has made one of the most important advances in stochastic games, and more broadly in game theory, in the past decade. His work will be a classic in game theory.

The winner, Yehuda (John) Levy, was a little nervous before, while, and after shaking hands, receiving the nice flowers sent by the Center for Rationality, and getting the award. I hope to have enough time this summer to fully understand his construction and report it here.

From left: David Schmeidler, Eilon Solan, Yehuda (John) Levy, Hana Maschler, Yisrael Aumann

At lunch today, I decided to make a foolish claim (on other occasions  they just emerge spontaneously). Specifically, that inflation is not a problem. Why? Consider the budget constraint of the consumer. Inflation scales up the left and right hand side of the budget constraint by the same amount leaving it unchanged. Mark Satterthwaite pointed out that I was assuming that prices an income would adjust all at once. I was, he noted, ignoring the fact that many contracts were denominated in nominal dollars rather than inflation adjusted dollars. Ok, but this raises the question of why we write contracts in this way. Why not contracts based on inflation adjusted dollars? Luciano de Castro piped in that such contracts were normal in Brazil. In fact, salaries were paid the same way. Jonathan Weinstein said that this makes the method by which one computes inflation very important. In particular, it has to be immune to manipulation (he also observed that making a switch to inflated adjusted contracts would be like printing money…..but once). OK, but this means that inflation is not the issue but rather the absence of a reliable index of it. Then, Sasa Pekec and Uri Weiss argued that inflation allowed governments to break promises made earlier, so why would Governments agree to doing away with it? Didn’t get to the bottom of it as we had to break up.

Kellogg faculty blogroll