You are currently browsing Eilon’s articles.
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?
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
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.
Like this:
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.
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?
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.
I live in a suburb of Tel Aviv. Every morning during rush hour the two streets leading to the highways to Tel Aviv are packed. I try to evade going to the university during rush hour. Unfortunately, the kids start school at 8:30, and therefore quite often I have to trail to Tel Aviv with many other sleepy parents.
In some countries drivers keep their lane while driving in a multi-lane packed street. This is not the case in Israel. People believe that by changing lanes they can get to their destination faster, even when all lanes in the roadway are equally packed. Plainly one can rationalize this behavior, as one lane may be momentarily faster than the other, and therefore by changing lanes one can progress a little faster.
The streets leading from my home town to the highways consist of four lanes, two lanes leading from the town center to the highway, and two lanes leading from the highway to the town center.
The other day I was going to the University, and the two lanes leading to the highway were packed as usual. I noticed that the car in front of me tries to change lanes. Then I noticed that the car in the other lane also tries to change lanes. Thus, each driver believed that the other lane is faster than his own lane. As they were driving one next to the other, their intentions were common knowledge among them. But then, as Aumann tells us, it should be common knowledge among the two drivers that both lanes are equally slow. Nonetheless the two drivers switched lanes.
Anyone has a good explanation?
Try to remember the last conference that you attended. How many talks did you want to follow? How many talks could you follow? In how many talks did the speaker made any effort to help you follow?
The answers that I give to the last two questions convinced me early in my career that the meager amount of time that I spend away of my family should be spent with co-authors rather than in conferences. But sometimes there are conferences in which the answer to the first question convinces me that I should join my colleagues in an attempt to follow speakers.
I was sitting in the conference hall in Toulouse, looking around, observing the people in the audience yawn, surf the web, read papers, talk to each other, sometimes even take a nap. True, there were clear and interesting talks, but many speakers lost their audience within a minute. And these speakers were sitting in the audience before their talk and could not follow the talks of others (I noticed them surfing the web…).
When preparing a presentation, my rule is to spend 5 minutes on each slide, to use a large font and to refrain from having equations on the slide as much as possible. Thus, a 30-minute talk translates to 6 slides. Knowing that 5 minutes per slide may be a little too much, to my talk at Toulouse I prepared 8 slides (lo and behold, I did not reach the last one!) In contrast, some speakers had 30 slides with small fonts and many equations for a 30-minute talk. Did they really think that people can follow one slide per minute? Can they do it? And some people simply jump over slides saying they are not important. If they are not, why are they there? Why didn’t they prepare the talk in advance? Some people provide the formal definition of the model, with all measurability conditions and exact sets of strategies. Is it important for the talk? Wouldn’t a verbal description suffice, something like “players choose strategies in continuous time that ensure that the play path is well defined”, and mention the term that people use for this type of strategies? People who are not in the field do not care anyway about measurability conditions and the formal definition of strategies in continuous time. Some speakers provide the full list of notations; can they remember notations that were defined two slides ago and were hardly shown on the screen?
So why do people give bad presentations? Why do they not invest more time and energy at home? I thought that people talk at conferences to spread their work: after all, who reads papers these days? But then to give a bad presentation is a waste of time: you lose your audience and nobody will remember what you did. I would understand if the conference were at Paris, Rome or Beijing. Then there are other reasons to attend it. But even though Toulouse has a rich history I think that it is not sufficiently interesting to attract the average tourist.
Anyone can help in figuring out this puzzle: What is the utility of the average game theorist that explains why he/she gives a bad presentation in a non-touristic city?
Eran
rvohra
Eilon
Jonathan Weinstein
Aviad Heifetz
Recent Comments