You are currently browsing the monthly archive for April 2012.

Israel’s minister of defense, Ehud Barak, heard what Benny Gantz, Israel’s Chief of General Staff, had to say on the rationality of Iran’s leadership, and contributed his two cents on this subject:

“The fact that we talk about sophisticated and calculated people, who want to stay in power, and try to achieve their goals cunningly and by continuously estimating the moves and intentions of their rivals, does not make them into rational people in the western sense of the world; that is, people who look for a status quo and peaceful solutions to the problems at hand. The Iranian leadership does not behave this way.

So, according to Ehud Barak, the word “rationality” has a western sense, which is “the wish to keep the status quo and to solve disagreements peacefully”, and, I guess, by contrast, an eastern sense, which is the opposite. I wish Israel joins the western world soon.

Today Israel honors the memory of its soldiers killed during its wars; tomorrow we will celebrate the 64’th year since our independence in 1948. On this occasion Benny Gantz, Israel’s chief of general staff, that is, the head of the Israeli Defence Force, was interviewed. Concerning the nuclear threat of Iran Gantz said (in Hebrew; the following is my translation):

“Iran advances step by step to the point where it can decide if it wants to build a nuclear bomb. They have not decided yet whether to advance the extra mile. In their mind , as long as their nuclear facilities cannot withstand bombing, the nuclear program is too vulnerable. If the supreme leader Ali Khamenei wants, he will proceed to obtain a nuclear bomb, but a decision on this issue is still to be made. It will be made if Khamenei believes that he can withstand the response. I think he will do a grave mistake if he does so, and I do not think he wants to do the extra mile. I think the Iranian leadership consists of rational people. But I agree that such an ability in the hands of Islamic fundamentalists, who at some moments might make different calculations [and reach different conclusions], is dangerous.”

Leaving aside the issue of whether or not Iran should have nuclear weapon, I wonder what Gantz means when he says that Iranian leadership cosists of rational people. If he means that their decisions maximize their utility, then howcome at some future time they might make different calculations and reach different conclusions? Are they rational now yet they might stop being rational in the future? Why are rational religious fundamentalists more prone to irrational decisions than secular liberals? Or maybe the utility function of a religious fundamentalist is so different than that of a secular liberal, that the secular thinks that that some choices of the religious person cannot maximize his utility, though from the religious person point of view they do maximize his utility function? I wish decision makers had to take courses in decision theory and game theory, so that they would understand strategic interactions a little better.

A few weeks ago I wrote here that the Israeli chapter of the game theory society decided to award an annual prize, the Michael B. Maschler prize, to an outstanding research student in game theory in Israel. Yesterday the judge panel has reached its decision, to award this year’s prize to John Levy, a Ph.D. student of Professor Abraham Neyman at the Hebrew University of Jerusalem (Center for Rationality).

John’s main contribution so far is a counterexample: he provided an example of a discounted stochastic game with contiuum of states without a stationary equilibrium. This result is striking because quite a few people worked hard on proving that a discounted stationary equilibrium does exist, and one paper proving it has been published…

A stochastic game is a sequential game that is given by a collection of matrix games. Each entry in each matrix contains a vector of payoffs, one for each player, and, in addition, a probability distribution over the set of matrices (also called transition function). At every stage of the game the players play one of the matrices; each player chooses an action, thereby an entry in the matrix is chosen. Each player receives the payoff prescribed for him by the chosen entry, and the matrix that the players will play in the following stage is chosen by the probability distribution over matrices indicated by the chosen entry. Thus, in a stochastic game the players play a sequence of matrix games, and their actions at every stage determine both their stage payoff, and influence the matrix games they will play in the future.

In a stochastic game each player receives a stream of payoffs, one per stage. It is assumed that each player tries to maximize the discounted sum of his stage payoffs.

Each matrix game is called a state. When the number of states is finite (or countable), the existence of a stationary equilibrium follows from a standard fixed-point argument. When the number of states is countable, the existence of an equilibrium is a difficult problem. Mertens and Parthasarathy proved the existence of a (not necessarily stationary) equilibrium under continuity assumptions on payoffs and transitions (see also this paper).

Yehuda Levy has constructed an example of a game that does not possess a measurable stationary discounted equilibrium. This is a remarkable achievement that puts an end to the chase for a proof of existence. Levy’s example is robust: any stochastic game which is “close” in a suitable manner to his example does not possess a measurable stationary equilibrium either. In a subsequent work, Levy proves that a stochastic game with a continuum of states that obeys an absolute continuity property (that is, all transition probabilities are absolutely continuous w.r.t. a fi xed measure) need not have a stationary equilibrium. This result contrasts with a result of Nowak that proves the existence of stationary epsilon-equilibria under the absolute continuity assumption.

Yehuda brought new ideas to the area of stochastic games, an area that I feared exhausted itself in the last years. I am happy that he won the Maschler prize.

At dinner recently I was asked by a young chap who had just joined the faculty of an elite B-school whether  he had signed onto a sinking ship (not in those words of course). I did not hesitate to bore him into somnolence on the subject.

I think there are two challenges. One specific to B-schools and the other  to Universities in general. The specific one is driven by demography and (apparent) changes in preferences. Specifically, the decline in appetite among US students for an MBA and the corresponding growth in demand by students outside the US. For B-schools at the top of the charts, this will necessitate some changes in their offerings but it is a challenge that can be feasibly met. Schools that are neither regionally or internationally dominant will be up against the wall.

The second is the possible disintermediation of higher education as we know it by  the MOOC’s (massively open online courses). It was said that Universities would be killed by Gutenberg. They were not. Then, it was Marconi that would would bury them. They survived. They survived John Logie Baird as well. Why not the internet? Ok, I’m sure the same argument was made about the newspaper business. Perhaps, like them, we will  make our money in advertising. Opportunities abound. The surface of desks in classrooms, floors in the hallway, bathroom stalls (the Goldman Lavatory of Finance?), quizzes, exams, the school web site. A crawler at the bottom of screens in classrooms as well as the TV monitors in the hallways. Product placement on instructor power point presentations. Double the time spent in courses and use the extra time for employer presentations (make attendance mandatory!).

Returning to the  MOOC’s, they are  not, shock and horror, novel. Think Open University in the UK or the School of the Air in Australia. Both seek to circumvent the bonds of time and place to deliver instruction. The first attempts to do this at scale.

OK, so what is the challenge MOOC’s pose? They allow students to customize the timing and pace of the class to their needs without having to scale up the size of the faculty. How might B-schools (and Universities) respond to this? We have to systematically exploit the fact that we bring students and faculty together in one location at the same time. That synchronicity allows us to do things that none of the MOOC’s I have sampled can do: sustained and deep discussion. In contrast, the famous Thrun AI course, for example, was a well delivered compilation of lists, facts and recipes.  It is possible the kind of Socratic experience I have in mind can be replicated by discussion among students on the discussion board (which are then filtered up the pyramid to the professor). I don’t think so. If I’m wrong, I’m a dodo  and  it does not matter.

One of my nephews plays tennis. Because the cost of tennis equipment in Israel is twice as much as elsewhere, and because I am the English speaker of the family, I take care of all high-end Tennis needs of the kid. Four months ago I brought with me from Paris a Wilson Six One Lite BLX racket, and last week I ordered a Wilson BLX tour Federer super six pack bag from Tennis Warehouse, USA, paying $33 for shipping this great bag with UPS. The delivery man brought, together with the bag, an invoice on NIS 264 (roughly$70), which included Israeli taxes and handling fee. I asked the delivery man why I need to pay handling fee, because I already paid for the delivery. He referred me to UPS-Israel customer service.

After 2:40 minutes waiting on the line, while the delivery man waits  beside me, a nice lady answered. I explained to her the issue and she said that I must pay this amount, since someone at UPS handled customs for me.

• But I already paid for the delivery, I said.
• The seller should have told you that you would have to pay additional amount, she answered. You should contact the seller.
• If I talk with the seller about it, they will tell me that UPS overcharged me, and that I should contact you, I objected.
• There is nothing I can do. You have to pay handling fee.
• Can I speak with your manager?
• He will tell you the same thing.
• Can I speak with your manager?
• He won’t be able…
• Can I speak with your manager? I asked for the third time, irritated.
• Wait a moment.

After two minutes she went back on the line, saying that they decided not to charge handling fee this time.

After the delivery man left I started wondering: did I have to pay the extra handling fee? If I did, then why did UPS decide not to charge it? Suppose they sincerely believe that the vendor did not tell me that I would have to pay it; then why not tell me that they decided not to charge me this time, without arguing? They can think of it as a one-time education bonus that the customer receives from UPS. If I did not have to pay this extra fee, then why did they claim that I had to pay it? The risk of being caught and the consequences that will follow are not worth the extra revenue. The way it turned out was the worst possible for UPS: they did not charge the extra handling fee, and they have an unhappy customer.

Can someone rationalize UPS-Israel behavior?

One reason I like thinking about probability and statistics is that my raw intuition does not fit well with the theory, so again and again I find myself falling into the same pits and enjoying the same revelations. As an impetus to start blogging again, I thought I should share some of these pits and revelations. So, for your amusement and instruction, here are three statistics questions with wrong answers which I came across during the last quarter. The mistakes are well known, and in fact I am sure I was at some level aware of them, but I still managed to believe the wrong answers for time spans ranging from a couple of seconds to a couple of weeks, and I still get confused when I try to explain what’s wrong. I will give it a shot some other post.

— Evaluating independent evidence —

The graduate students in a fictional department of economics are thrown to the sharks if it can be proved at significance level ${\alpha=0.001}$ that they are guilty of spending less than eighty minutes a day on reading von Mises `Behavioral econometrics’. Before the penalty is delivered, every student is evaluated by three judges, who each monitors the student in a random sample of days and then conducts a statistical hypothesis testing about the true mean of daily minutes the student spend on von Mises:

$\displaystyle \begin{array}{rcl} &H_0: \mu \ge 80\\&H_A: \mu<80\end{array}$

The three samples are independent. In the case of Adam Smith, a promising grad student, the three judges came up with p-values ${0.09, 0.1, 0.08}$. Does the department chair have sufficient evidence against Smith ?

Wrong answer: Yup. The p-value in every test is the probability of failing the test under the null. These are independent samples so the probability to end up the three tests with such p-values is ${0.09\cdot 0.1\cdot 0.08<0.001}$. Therefore, the chair can dispose of the student. Of course it is possible that the student is actually not guilty and was just extremely unlucky to get monitored exactly on the days in which he slacked, but hey, that’s life or more accurately that’s statistics, and the chair can rest assured that by following this procedure he only loses a fraction of ${0.001}$ of the innocent students.

— The X vs. the Y —

Suppose that in a linear regression of ${Y}$ over ${X}$ we get that

$\displaystyle Y=4 + X + \epsilon$

where ${\epsilon}$ is the idiosyncratic error. What would be the slope in a regression of ${X}$ over ${Y}$ ?
Wrong answer: If ${Y= 4 + X + \epsilon}$ then ${X = -4 + Y + \epsilon'}$, where ${\epsilon'=-\epsilon}$. Therefore the slope will be ${1}$ with ${\epsilon'}$ being the new idiosyncratic error.

— Omitted variable bias in probit regression —

Consider a probit regression of a binary response variable ${Y}$ over two explanatory variables ${X_1,X_2}$:

$\displaystyle \text{Pr}(Y=1)=\Phi\left(\beta_0 + \beta_1X_1 + \beta_2X_2\right)$

where ${\Phi}$ is the commulative distribution of a standard normal variable. Suppose that ${\beta_2>0}$ and that ${X_1}$ and ${X_2}$ are positively correlated, i.e. ${\rho(X_1,X_2)>0}$. What can one say about the coefficient ${\beta_1'}$ of ${X_1}$ in a probit regression

$\displaystyle \text{Pr}(Y=1)=\Phi\left(\beta_0'+ \beta_1'X_1\right)$

of ${Y}$ over ${X_1}$ ?
Wrong answer: This is a well known issue of omitted variable bias. ${\beta_1'}$ will be larger than ${\beta_1}$. One way to understand this is to consider the different meaning of the coefficients: ${\beta_1}$ reflects the the impact on ${Y}$ when ${X_1}$ increases and ${X_2}$ stays fixed, while ${\beta_1'}$ reflects the impact on ${Y}$ when ${X_1}$ increases without controlling on ${X_2}$. Since ${X_1}$ and ${X_2}$ are positively correlated, and since ${X_2}$ has positive impact on ${Y}$ (as ${\beta_2>0}$), it follows that ${\beta_1'>\beta_1}$.

In Harsanyi games with incomplete information, also known as Bayesian games, each player has a type. The type of the player describes all that he knows and believes about the situation he faces: who are the players, what are his and their available actions, what are his and their utility functions, and what are the beliefs of the other players about the situation.

Since the player’s type describes his knowledge and beliefs, a player always knows his own type. But a player need not know the other players’ types. Indeed, a chess player knows his own abilities, but he may not the level of his opponent: he may ascribe probability 1/3 to the event that his opponent is familiar with the Benko gambit, and probability 2/3 to the event that the opponent is not familiar with this opening.

In a Bayesian game,  a chance move selects a vector of types, one type for each player, according to a known probability distribution p at the outset of the game. Each player learns his own type, but he does not know the types chosen for the other players. He does have a belief about the other players’ types, which is the conditional distribution of p given his own type.

The Bayesian game is an auxiliary construction. In reality there is no chance move that selects the player’s types: the knowledge and beliefs each player is equipped with determine his or her type. Bayesian games are  merely a way to model the incomplete information each player has on the other players’ types. Thus, the true situation the players face is the situation after the vector of types was selected, which is called the interim stage. The situation before the vector of types is chosen, which is called ex ante stage, is the mathematical way that Harsanyi found to model the game.

Consider now the following Bayesian game, that depends on a real number a (which is in the unit interval; below, all additions and subtractions are modulo 1). There are two players; the type space of each player is the unit interval [0,1]. The types of the players are correlated: if  player 1 has type x, then he believes that player 2’s type is either x of x+a (each with probability 1/2); if  player 2 has type x, then he believes that player 1’s type is either x of x-a (each with probability 1/2). This belief structure can be described by a common prior distribution: the types of the two players are chosen according to the uniform distribution over the following set T (this is a variation of an example of Ehud Lehrer and Dov Samet):

If player 1’s type is x, then he believes that player 2 may be of type x or x+a. It follows that player 2 may believes that player 1’s type is x-a, x, or x+a. So player 2 may believe that player 1 believes that player 2’s type is x-a, x, x+a or x+2a. When the situation is a game, to decide how to play, player 1 needs to take all types of player 2 (and of himself) of the form {x+na, n is an integer}. This set of finite if a is a rational number, and countable if a is an irrational number. Denote by Zx the set of all pairs of type {(x+na,x+na), n is an integer} union with {(x+na,x+(n+1)a), n is an integer}. The set Zx is called the minimal belief subspace of player 1. In the interim stage, after his type was selected and told to him, player 1 knows that the type vector is in Zx, that only type vectors in Zx appear in the belief hierarchy of player 2, and therefore he can think about the situation as if the Bayesian game is restricted to Zx: a type vector in Zx was chosen according to the conditional distribution over Zx. To determine how to play, player 1 should find an equilibrium in the game restricted to Z.

The uniform distribution of the set T that appears in the figure above induces a probability distribution over Zx. When Zx is finite (= a is a rational number), this is the uniform distribution over a finite set. Alas, when Zx is countable (a is irrational) there is no uniform distribution over Zx. In particular, the interim stage is not well defined! Thus, even though the interim stage is the actual situation the players face, and even though they can describe their beliefs using a Harsanyi game with a larger type space, the situation they face cannot be described as a Harsanyi game if they take into account only the types that are possible according to their information.

It is interesting to note that one can find a Bayesian equilibrium in the game restricted to Zx, for every x. However, when one tries to “glue” these equilibria together, one might find out that the resulting pair of strategies over [0,1] is not measurable, and in particular an equilibrium in the Harsanyi game (over T) need not exist. This finding was first noted by Bob Simon.

Since indeed the true situation the players face is the interim stage, and the ex ante stage is merely an auxiliary construction, how come the ex ante stage does not define a proper game in the interim stage? If this is the case, is the auxiliary construction of Harsanyi game over T the correct one?

Michael Maschler, 1927-2008, was a prominent game theorist, who influenced both cooperative and noncooperative games. His contributions include the bargaining set and the kernel, the Maschler-Perles solution to bargaining games, bankruptcy problems and the Talmud, the study of two-player zero-sum repeated games with incomplete information on one side, the application of cooperative games to network games and to voting systems.
Michael was also keen on mathematical education: he wrote many books at middle-school and high-school level in mathematics, and several textbooks in game theory.
To commemorate Michael Maschler, the Israeli chapter of the Game Theory Society decided to award each year a prize to an outstanding research student in Game Theory in Israel. In addition to the money that comes with the prize, the Michael Maschler prize will demonstrate the recognition of the abilities of the winner as viewed by the Israeli community. This year the deadline for nomination is 10-April, and the prize will be given in a one-day conference that we organize at Tel Aviv University on 7-May. I will write on the work of the winner when he/she is chosen.