Borel Games: Part I

Anne and Bill play the following sequential game: at odd stages Anne chooses either 0 or 1, and at even stages Bill chooses either 0 or 1. This way they generate an infinite sequence of bits, which is the binary expansion of a real number x in the interval [0,1]. Who wins the game? Well, there is a subset W of [0,1], the winning set of Anne, which is known to the players in advance. If the real number x that they generated is in W, Anne wins. If it is outside W, Bill wins.
Suppose for example that W=[0,1/2]. Then, by choosing 0 at the first stage of the game, Anne guarantees a win. If, on the other hand, W is the union of the two intervals [0,1/4) and (1/2,3/4), then by choosing 0 at the second stage, Bill guarantees a win.
Zermelo’s Theorem guarantees that every finite two-player game with two outcomes: “player I wins” or “player II wins”, is determined: one of the players has a winning strategy. The game between Anne and Bill is not a finite game, and therefore Zermelo’s Theorem does not apply.
Gale and Stewart (1953) proved that if the set W is closed, then the game is determined. This result was significantly extended by Martin (1975), who proved that if W is Borel measurable then the game is determined.
Borel games are similar to the game described above between Anne and Bill, but instead of choosing a bit at every stage, Anne and Bill have some set of actions A available to them; at odd stages Anne chooses an action from A, and at even stages Bill chooses an action from A. The set A may be finite or infinite. When the set of actions A is not {0,1}, Anne’s winning set is a subset of A^∞.
In fact, it does not matter whether Anne and Bill have the same set of actions, or different sets of actions. Actually, the set of actions available to each of them may be history dependent. Also, the players need not alternate in choosing actions: the identity of the player who currently chooses the action may be history dependent as well. The result of Martin (1975) was proved to this general setup.
Up to now, the outcome of the game was either 1 (Anne wins) or -1 (Bill wins). However, we could think of general two-player zero-sum Borel games. Here the data of the game includes a payoff function u that assigns a real number u(p) to each play p (=infinite sequence of actions).
One game that falls into this class of games is the following: we are given a directed graph. The vertices of the graph are divided into four types: some vertices are “win vertices of Anne”, others are “win vertices of Bill”, yet others are “vertices controlled by Anne”, and the rest are “vertices controlled by Bill”. The game starts at one of the vertices, and moves between the vertices as follows: if the current vertex s is controlled by Anne, Anne chooses an outgoing edge from s, and the vertex at the end of the edge is the new vertex. If s is controlled by Bill, it is he who chooses an outgoing edge. If s is a winning vertex of one of the players, then that player is the winner, and the game ends. If the play never reaches a winning vertex, the game ends with a draw.
Martin’s (1975) result implies that if the payoff function u is measurable and bounded, then the game has a value. The argument is as follows: for every real number x denote by W(x) the set of all plays p where u(p) ≥ x. Because u is Borel measurable, the set W(x) is a Borel set. By Martin, the game G(x) with winning set W(x) is determined for every x. If Anne can guarantee a win in G(x), it means that she can guarantee a payoff of at least x in the original game; if Bill can guarantee a win in G(x), it means that he can guarantee a payoff smaller than x in the original game. Because u is bounded, for x=∞ Bill can guarantee a win in the game G(x), and for x=-∞ Anne can guarantee a win in the game G(x). Let then x* be the maximal x for which the game G(x) is determined for Anne. Then x* is the value of the original game.
So, every two-player zero-sum Borel game has a value? What about equilibria in multi-player Borel games? This will be discussed in a subsequent post.

Local Action Groups

A couple of years ago I wrote an article for a popular journal on game theory. The standard content: John Nash and the Beautiful Mind, strategic analysis, auctions, the value of information and the winner’s curse. A social worker, who works with local action groups, read the article, and realized that it may be interesting and useful for his community to model the interaction between local action groups, and municipalities and large firms, using game theory. I found this idea worthwhile pursuing, and after some time, two years, to be precise, we ended up analyzing the construction of the new central bus station at Tel Aviv, the second largest city in Israel, and the struggle of the local neighborhood to receive fair compensation for the damages caused by this project.
The modeling is routine and not difficult. One player is the municipality; the other player(s) is the locals. The municipality can be fair or unfair; the locals can fight together, separately or do nothing. Determine payoffs, find equilibria. Lo and behold, in equilibrium the municipality if unfair, it plays divide-and-conquer, it plays a war of attrition.
The mathematical analysis is just a tool to obtain insights: what do we learn from this interaction? This struggle made me think of the tyranny of the municipalities and government. In the back of our minds we all know of this tyranny, we read of it in the news and we see it around us. This interaction is nevetheless a nice example where a municipality mistreats its people: instead of providing fair compensation, it dragged the people for years in court, and did its best to kill their fight.
Unions where established to fight the tyranny of employers. But what can one do to fight the tyranny of municipalities against the weaker sections of the populations? A popular union won’t do. It is fun to strike and to remain at home for others, but it is less fun to demonstrate 100 kilometers away from home for a cause you may not even agree to.
But then, what can be done? Can one establish a non-for-profit organization that helps action groups, backed by first-rate lawyers and experts in public relations, and supported by thousands of people who value justice and fairness and are willing to support struggles against the tyranny of the rich, the strong, and the various institutions of state? Who can be the driving force behind such an organization? Who will finance it? Who ensures us that it, too, will not become part of the rich and strong? Other ideas? Other solutions that exist someplace?

Bounded Memory

In most theoretical models in game theory, the strategies that players may follow can be extremely complex. Because humans, computer programs that implement strategies, and animals, all have bounded computational capacity, many strategies that we, theoreticians, use in our constructions are too complex for the real-life agents that are supposed to play in our games. A strand of the literature that tries to take care of this issue studies repeated games where the players have bounded rationality: they have bounded memory, bounded recall (that is, they remember only the actions taken by the players in the last k stages of the game), or bounded computational capacity, so that they can use, for example, encryption to send private communicate among themselves.
One of the messages of this theory is that if one player is much stronger than the other, that is, his memory space or computational capacity is much larger than that of the other player, then, even if the weaker player chooses his strategy randomly, along the play the stronger player can learn the pure strategy that the weaker player follows, and best respond to it, thereby reducing the payoff of the weaker player to his min-max level in pure strategies. For example, in the game Matching Pennies, if one player’s memory is much larger than the other’s (in fact, exponentially larger), than the stronger player can increase his average payoff to 1, where 0 is the value of the one-shot game.
The theory also tells us that if one player is stronger than the other, but not much stronger, then the larger memory/computational capacity that he has does not translate to higher payoffs: to increase the long-run (or discounted) average payoff the stronger player needs a significantly larger memory than that of the weaker player.
Other papers study one-player decision problems where the decision maker has bounded memory, and they characterize the optimal simple strategy of the decision maker; that is, the optimal strategy among the set of strategies that use a specific memory size.
The proofs of the results on repeated games with boundedly rational players are far from trivial, and usually involve deep mathematical arguments. However, after reading (and writing) papers in this area, I wondered what practical insights this literature tells us.

Consider for example repeated games played by players with bounded memory, as studied, among others, by Elchanan Ben Porath, Ehud Kalai, Abraham Neyman, Daijiro Okada, and Ariel Rubinstein. Let G be a one-shot game. Let G(n1,n2,T) be the T-stage repetition of the game G, where player 1 is restricted to strategies with memory n1 (e.g., he can only follow strategies that can be implemented by a computer program with n1 command lines), and player 2 is restricted to strategies with memory n2. Then the game G(n1,n2,T) has a value v(n1,n2,T) in mixed strategies, this value v(n1,n2,T) is approximately the value of the one shot game if n1 and n2 are close, and the value v(n1,n2,T) is close to the min-max value of the one-shot game G if n1 is much larger than n2, yet both are much smaller than T.

The insights gained from these papers were mentioned above: the relation between the relative computational capacity of the players and the value of the game. The catch, in my view, is the usual one concerning optimal strategies and equilibria in game theory: how do players get to know their optimal strategy? That is, how do boundedly rational players find their optimal mixed strategy in the game G(n1,n2,T)? The computation of such a strategy is a very difficult task, which requires memory much larger than n1 (or n2). The usual answer is evolution or learning. A third answer, which I find more convincing, is that the agents who play the game are indeed boundedly rational, but they are agents of much more sophisticated players, who design the optimal strategies of the agents. This story is convincing when, e.g., the agents undergo a training period before playing the game. For example, salespersons undergo a training period, where they learn how to interact with potential buyers. This training of salespersons in effect dictates the strategy that they will use in the repeated game.
When two players face a new situation, each must use his memory/computational capacity to find his optimal strategy. The meta-program he uses for that purpose, which he inherited by evolution and improved through learning, serves for the same purpose.
Therefore I believe that results from the game theoretic literature on boundedly rational players give us some insights on real life situations.

What are the insights that we gain from results on one-player decision problems with a boundedly rational decision maker? As can be expected, in some models an agent with bounded memory can approximate the behavior of a rational agent, whereas in other, more complex models this cannot be achieved. An interesting paper in this venue is “Bounded Memory and Biases in Information Processing” by Andrea Wilson, which I will now discuss. Wilson studies a problem where there are two states of nature, H and L, and the decision maker should make a decision at an unknown period which is geometrically distributed. There are two possible actions, H and L; each action yields a payoff 1 if it matches the unknown state and 0 otherwise. The decision maker receives a signal at every period, either h or l; the probability to observe the signal h is high when the true state is H, and a similar property holds for the signal l and the state L. A rational decision maker can calculate after the arrival of each new piece of information the posterior belief about the state of nature, and then, when called upon to play, choose the action that corresponds to the more likely state. An agent with bounded memory must forget some of the information that he has, and therefore it is not clear what his optimal strategy looks like. Wilson provides a very neat and sophisticated proof that the optimal strategy has a special structure: the decision maker remembers one integer, k, which reflects the “likelihood” that the state is H. The value of k can be between 1 and the maximal number allowed by the memory size of the decision maker. When called upon to play, the decision maker chooses H if k is above some cutoff, and L if k is below the cutoff. Whenever the signal h is received, k increases by 1; whenever the signal l is observed, k decreases by 1. When k is one of the extreme points, say k=1, and the decision maker observes the signal h, with positive probability the value of k increases by 1, so that the decision maker will not be stuck with the incorrect decision when a lot of evidence in favor of the opposite decision arrives.
Wilson relates the structure of the optimal strategies to two psychological phenomena: confirmatory bias, that is, the tendency to interpret information as supporting the current belief, and overconfidence/underconfidence bias. The reason for the confirmatory bias is that if Alice is in state k=1 (so she is confident that the true state is L), and she observes the sequence of signals hhl, she will most probably remain at k=1, whereas if Bob is the maximal state k (so he is confident that the true state is H) and he observed the same sequence of signals hhl, he will most probably remain at the maximal state. Thus, the same sequence of signals is interpreted differently by the players, according to their initial belief.
Do I find this relation convincing? I must say that I do not. I agree that the optimal strategy resembles confirmatory bias, but do humans actually play using such a strategy? Don’t we sometimes ignore/forget signals? Don’t we sometimes exaggerate? Moreover, this strategy has properties that I believe that humans fail to have. For example, if one follows the optimal strategy, and if the true state is, say, H, then nevertheless there will be periods (infinitely many, in fact) in which the decision maker will be confident that the true state is L. This will happen by shear luck (or bad-luck) – there will be long periods in which the signal will happen to be l, and then the decision maker will shift from one extreme state to the other. True, these periods will be rare, but they will happen. I cannot imagine a hardcore Republican voting for Obama after reading tons of articles in favor of Obama’s candidacy.
The bottom line: I believe that theoretical results on games played by boundedly rational players are mathematically interesting. Sometimes they provide interesting and surprising insights (in addition to the discussion above, see, for example, the recent paper by Bavly and Neyman). Sometimes, as often happens in economic theory, we stretch the relevance of our theoretical results too far. Yet I believe that many insights still wait for us in this area, and I hope that we will not see the end of this exciting topic.

Peer review can be made less torturous

Peer review is a painful process both to authors and to referees, and I gather from Eilon’s post that editors are not thrilled with it either. This, I believe, is in part because we game theorists expect the referee not only to judge the paper, but also to discuss the paper more than is necessary to justify the judgment, and, even worse, to suggest ways to improve the paper.

This is why we produce long reports, sometimes of low quality because we force ourselves to write something even when we have nothing valuable to say. Sure, the referee’s feedback can be useful — As Eilon says, some authors believe that it is actually worth the delay in publication even when the paper is bound to be rejected. But even in these cases I think the effort to write the report is not worth the small audience that the report will receive. If the referee has some interesting observation or criticism about the paper, why hide it from the rest of community ?

This is why I suggest that the profession adopt the guidlines of The Annals of Statistics, which to my knowledge are common in math and physics journals

you are not expected to rewrite the paper or to suggest major revisions or avenues for further research. Your role is simply to recommend whether or not the paper should be published.

My beef with quantum games

I am getting too many requests to referee `quantum games’ papers, and while I am very enthusiastic about the interface of game theory and quantum physics, there is a certain strand of this literature which in my view misses the point of game theory. Since I find myself copy-pasting from previous reports I wrote, I thought I should make my stance public. This post is a generic referee report. If you think my criticism shows that I am too narrow minded to understand your paper then I recommend that you ask the editor not to send it to me. If you have already read this post in a rejection letter then I hope we can still be friends. I am mostly going to rely on EWL’s paper which is a seminal paper in this literature (350 citations in google scholar) and the most mathematically coherent that I know.

Back to Anonymity

For five years I served as the Area Editor for Game Theory at “Mathematics of Operations Research”. I guess that most of you know the journal. As the top journal in mathematical game theory, at least this is the way the journal views itself, only about 15% of the submitted papers in this area are accepted. Quick calculation suggests that around 85% of the papers are rejected. As I was the only one standing at the forefront, I was the one who sent (and signed on) the rejection letters, and attached the referee reports that looked as if the referees did not invest enough time in reading the paper. I guess that other editors face the same situation.

This post is written for those of us who do not (yet) serve on the editorial boards of journals. And to those who do or did, but forget how the system works when it comes to their papers.

Some of us submit their papers to top journals because we believe that there is some probability that the paper will be accepted, and so, why not to try. Some of us believe that the paper will be rejected, but the input from the reviewers of a top journal, the associate editor and the editor is worth the delay in publication caused by a submission that is rejected. Yet many of us are confident that our papers are great, that we solve interesting problems, and that the insights we offer are enlightening and important.

As an editor, I got many papers that simply were not the type of papers that the journal looks for. Other papers did not explain why the result they present is interesting, and what the readers gains from the paper. And the contribution of others was simply not significant enough to grant publication at a top journal. After all, 50% of the papers are below the median. If only 15% of the papers are accepted, the paper should be really outstanding to be published at the journal.

A common complaint that I heard is that the review process is too long, and that eventually the referees did not understand the paper. I completely agree with the first complaint, not with the second. With regard to the first complaint, one should keep in mind, though, that sometimes people complain when they are authors, but delay reports when they are referees. Concerning the second complaint, sometimes indeed referees miss the point of the paper, but this usually means that the authors did a bad job in explaining their results. After all, the referees are more often then not experts in their fields, and they could easily understand a well-written paper. 

The work of an editor is demanding: you are in charge of many papers in different topics, in most of these topics you have never written anything. And you must rely on the associate editors and referees to know the literature and provide reliable assessments. But you are responsible for the decision regarding the paper: accept or reject. And the anger of the disappointed authors is directed at the only person whose identity is public – you. Once, one author caught me at a conference after lunch and told me in detail what he thinks of my virtues as an editor and of the way I choose referees. You can imagine the feeling. The job is time-consuming, and sometimes frustrating, and getting such reactions is disappointing, especially because you do the job as a service to the community.

So, what do I want to say except of complaining about busy referees and angry authors?

 First, I ask everyone to take seriously the referee jobs. If you invest more time in others’ papers, and if you complete the reports quickly, then others will do the same. When I was a junior, I used to complete a report within a week of receiving the paper. Why postpone the job, as it will wait for me anyway? These days, with the additional chores that fall on us with age, I need more time, but usually one month is enough. I do not see why some people take ages to complete a report. And I ask you not to turn down requests to review papers. Even if you are busy, there is always time to read one additional paper. When you take the kid to a Tennis class, when you try to put your baby to sleep, when you take a flight; there is plenty of free time that pleads to be used for noble causes. One month before I moved to Evanston for my first position at Kellogg I got a request to review a paper for “Mathematics of Operations Research”. I told the editor that I have infinitely many chores to complete in this month. He said that infinity plus one is infinity, so I would not feel the difference. The report was in his mailbox before I crossed the Atlantic.

Second, I ask authors to accept rejections. Having a paper rejected does not cheer you up or make you feel good, but all it says is that either you did a bad job in selling the paper, or that you did not properly estimate the contribution of your work. Usually a rejection says nothing about the referees, only about the authors. And this is said by someone who had quite a few papers rejected in recent years. It is easy to blame the unknown referees. But whatever you say on the referees, the authors of the papers that you review say about you. Are they correct?

Now, after five years of service, I am back to anonymity. Again I will be a mere associate editor, who has to chase referees but does not need to face disappointed authors and to deliver bad news. So that I am not forgotten, I upgraded myself and joined the Leisure blog; I can now write whatever comes to my mind, without making anyone specific angry or disappointed. And if anyone is angry by what I write, it will be because of me, and not because of the phantoms that used to hide behind my back.

A Question About WalMart

WalMart does not issue `loyalty’ cards. Why not? Other retailers, like Safeway, do. They are not literally loyalty cards since they do not induce holders to concentrate their purchases with a particular retailer. They do allow the retailer to track purchases by household. Why would WalMart choose to forgo that information?

A Profiling Tax

Racial and ethnic profiling of airline passengers is back in the news again. The argument in favor  is that it would be costly to mount a careful examination of all airline passengers. Assuming that such profiling is effective, it means that the costs of the acquired safety benefits are borne by a subset of the population. There is a way to redress this inequity. A profiling tax charged to all passengers. Proceeds from such a tax are paid to those who are profiled. Clearly, there are implementation issues but………..

We, the undersigned

I take it as self-evident and undisputed that when a group of eminent economists sign a letter endorsing the health care bill, the subtext of their message is that the issue is part of their scientific expertise and that they have studied the details sufficiently to deliver their professional opinion: This is the only way to interpret the fact that the undersigned are all economists, and that their academic position is mentioned in the letter. This is why their advice should carry more weight than the advice of an unknown blogger. If this advice is followed and the bill passes, then some of their professional reputation is tied with its success.

What is perhaps more disputable, but still true in my view, is that even this group of most distinguished economists don’t have individual reputations, and that they are drawing from and contributing to a collective reputation pool of the entire profession. The people of this (or any other) country, who are the audience of this letter, don’t distinguish between different scholars of the same discipline. Public trust in the entire profession is determined by the success of the predictions and policy advices of its members.

Samuelson’s price fluctuations paper

Following the death of Paul Samuelson, I looked at his seminal paper `Proof that properly anticipated prices fluctuate randomly’. I found it intriguingly related to my beloved puzzlement about the meaning of probability, and I have something to say about it. Since I didn’t look at the forty-five years of literature that followed this paper I am probably going to flaunt my ignorance in public, but this is just a blog so what harm can it do.

The purpose of Samuelson’s paper is to formalize the intuition that competitive prices must, in some sense, look like random walk: Let be a stochastic process that represents the spot price of some product, say wheat: is the price in which you can buy wheat at day . Fix a day and let , for , be the price at day of a contract that requires the delivery of wheat at day . Samuelson proves the following theorem: