You are currently browsing Eilon’s articles.

Yesterday the Israeli Parliament elected the state’s new president. This position is mostly ceremonial, and does not carry any significant duty. Nevertheless, quite a few people, mostly current and past Parliament members, wanted to get this job. The race was fruitful, as a couple of them were forced to withdraw their candidacy after secrets of weird sex stories and bribes were published in the press.

Three main candidates survived until the final stage, Rivlin, Itzik, and Shitrit (in addition to two candidates who did not stand much chance). Election is done by a two-round system: Each of the 120 Parliament members secretly votes for a candidate. If no candidate gets more than 60 votes, then all candidates except the leading two leave the arena, and the Parliament members secretly vote to either one of the two leaders. The candidate who got more than 60 votes is the new proud president of the state.

Politics was ugly. Rivlin, who is a member of the largest party, was the leading candidate, but the Prime Minister, who comes from the very same party, was against him. Many members of the opposition voted for Rivlin. In the first round, Rivlin and Shitrit got the highest number of votes, but none of them had a majority of votes. In the second round, Rivlin won.

What I found interesting in this process is what one of the Parliament members of the second largest party said. He said that in the first round some members of his party voted for Shitrit, but then, in the second round, they voted for Rivlin. Why? “It was a tactical vote.” This way they ensured that the final election will be between Rivlin and Shitrit and not between Rivlin and Itzik. Politics is ugly, but at least as long as the election process does not satisfy Independence of Irrelevant Alternatives, we do not have dictatorship.

 

Abraham Neyman had numerous contributions to game theory. He extended the analysis of the Shapley value in coalitional games with player set which is a measurable space, he proved the existence of the uniform value in stochastic games, and he developed the study of repeated games with boundedly rational players, among others. Abraham Neyman was also one of the founding fathers of the Center for Game Theory at the State University of New York at Stony Brook, which hosts the annual conference of the community for the past 25 years.

The International Journal of Game Theory will honor Abraham Neyman on his 66th birthday, which will take place in 2015, by a special issue, see the announcement here. Everyone is encouraged to submit a paper.

This post is dedicated to a new and important result in game theory – the refutation of Mertens’ conjecture by Bruno Ziliotto. Stochastic games were defined by Shapley (1953). Such a game is given by

  • a set Z of states,
  • a set N = {1,2,…,n} of players,
  • for every state z and every player i a set A_i(z) of actions available to player i at state z. Denote by Λ = { (z,(a_i)_{i ∈ N}) : a_i ∈ A_i(z) for every i} the set of all pairs (state, action profile at that state).
  • for every player i, a stage payoff function u_i : Λ → R, and
  • a transition function q : Λ → Δ(Z), where Δ(Z) is the set of probability distributions over Z.

The game starts at an initial state z^1 ∈ Z and is played as follows. At every stage t, each player i chooses an action a_i^t ∈ A_i(z^t), receives a stage payoff u_i(a_1^t,…,a_n^t), and the play moves to a new state, z^{t+1}, that is chosen according to q(z^t;a_1^t,…,a_n^t).

In this post I assume that all sets are finite. The N-stage game is a finite game, and therefore by backwards induction it has an equilibrium. As I mentioned in my previous post, the discounted game has an equilibrium (even a stationary equilibrium) because of continuity-compactness arguments.

Read the rest of this entry »

When studying dynamic interactions, economists like discounted games. Existence of equilibrium is assured because the payoff is a continuous function of the strategies of the players, and construction of equilibrium strategies often require ingenious tricks, and so are fun to think about and fun to read. Unfortunately in practice the discounted evaluation is often not relevant. In many cases players, like countries, firms, or even humans, do not know their discount factor. Since the discounted equilibrium strategies highly depend on the discount factor, this is a problem. In other cases, the discount factor changes over time in an unknown way. This happens, for example, when the discount factor is derived from the interest rate or the players monetary or familial situation. Are predictions and insights that we get from a model with a fixed and known discount still hold in models with changing and unknown discount factor?

To handle such situations, the concept of a uniform equilibrium was defined. A strategy vector is a uniform ε-equilibrium if it is ε-equilibrium in all discounted games, for all discount factors sufficiently close to 1 (that is, whenever the players are sufficiently patient). Thus, if a uniform ε-equilibrium exists, then the players can play an approximate equilibrium as soon as they are sufficiently patient. In our modern world, in which one can make zillions of actions in each second, the discount factor is sufficiently close to 1 for all practical purposes. A payoff vector x is a uniform equilibrium payoff if for every ε>0 there is a uniform ε-equilibrium that yields payoff that is ε-close to x.

In repeated games, the folk theorem holds for the concept of uniform equilibrium (or for the concept of uniform subgame perfect equilibrium). Indeed, given a feasible and strictly individually rational payoff x, take a sequence of actions such that the average payoff along the sequence is close to x. Let the players play repeatedly this sequence of actions while monitoring the others, and have each deviation punished by the minmax value. When the discount factor is close to 1, the discounted payoff of the sequence of actions is close to the average payoff, and therefore the discounted payoff that this strategy vector yields is close to x. If one insists on subgame perfection, then punishment is achieved by a short period of minmaxing followed by the implementation of an equilibrium payoff that yields the deviator a low payoff.

For two-player zero-sum stochastic games, Mertens and Neyman (1981) proved that the uniform value exists. Vieille (2000) showed that in two-player non-zero-sum stochastic games uniform ε-equilibria exist. Whether or not this result extends to any number of players is still an open problem.

Why do I tell you all that? This is a preparation for the next post, that will present a new and striking result by a young French Ph.D. student.

In the last decade journals adapted e-systems to control the review process of papers. Authors use them to submit papers, associate editors to select referees, referees to download the paper and to upload their reports,  once again authors to view the reports, and editors to know what goes on in their journal.

Unfortunately most e-systems are pain in the XXX. Registering to the e-system requires one to provide, for security reasons, his mother’s maiden name, so that the administrator of the journal can call one’s bank and get through; submitting a paper takes ages instead of simply e-mailing it to the editor as things used to be in the good old days; submitting a referee report requires one to choose between accept/minor revision/major revision/reject, but what if I one’s recommendation is “I do not know what your journal looks for, I would reject from Econometrica and accept to JET”?

For years I used to send my referee reports through e-mails and ignore the e-systems. This was easy, since as a referee the editors need me. But I am also an Associate Editor in some journals, and there I tried to get along with the e-systems.

I survived in the world of e-systems until Elsevier decided to consolidate all the accounts that we, authors, referees, and editors, have on its various journals. I simply could not get through the consolidation process. I did not understand why I need to provide the password of every single account that I have, and it is not enough to provide only one. I did not understand why I need to provide a security question, as if I enter the US and the immigration office at JFK looks at me suspiciously. Frustrated, I informed Felix Kubler, the previous editor-in-chief of JME, where I was an associate editor, that I am out of the game, and that if he wants me to handle a paper, I will gladly receive it through the good old e-mail.

But sometimes I am an author, and then nobody needs my help. Nevertheless, since I cannot use Elsevier’s e-system, I cannot submit papers to any of its journals. One option is to ask one of my dear coauthors to do it. Though this solution is tempting I (and I suspect that they as well) find it a little unfair. Therefore, when I wanted to submit a paper to GEB, I asked Jennifer Byrd, the managing editor of the journal, to upload it for me, and lo and behold, she was glad to do it.

I call all of you who cannot cope with the e-systems to abandon them as well. I do not see why we need to use horrible software that makes our life difficult. If editors will see that enough of us revert to e-mail, they will move back to this simple method.

Yisrael Aumann wrote “‘This is the book for which the world has been waiting for decades.”
Eric Maskin added “There are quite a few good textbooks on game theory now, but for rigor and breadth this one stands out.”
Ehud Kalai thinks that “Without any sacrifice on the depth or the clarity of the exposition, this book is amazing in its breadth of coverage of the important ideas of game theory.”
Peyton Young goes further and writes “This textbook provides an exceptionally clear and comprehensive introduction to both cooperative and noncooperative game theory.”

Jacket

Covering both noncooperative and cooperative games, this comprehensive introduction to game theory also includes some advanced chapters on auctions, games with incomplete information, games with vector payoffs, stable matchings and the bargaining set. Mathematically oriented, the book presents every theorem alongside a proof. The material is presented clearly and every concept is illustrated with concrete examples from a broad range of disciplines. With numerous exercises the book is a thorough and extensive guide to game theory from undergraduate through graduate courses in economics, mathematics, computer science, engineering and life sciences to being an authoritative reference for researchers.

This book is the outcome of 8 years of hard work (and its almost 1000 pages attest for that). It was born in Paris, in February 2004, around Sylvain Sorin’s dinner table, where Shmuel Zamir and your humble servant had a great dinner with Sylvain and his wife. Michael Maschler joined the team several months later, and each month the book grew thicker and thicker. I use the book to teach 4 different courses (two undergrad, two grad), and since it contains so many exercises, there is no reason to spend much time on writing exams.

The book is only one click away. Don’t miss it!

Israel is a parliamentray democracy; our president has but ceremonial role, and the prime minister (and his government) is the one who actually makes all important decisions. After elections, each party recommends to the president a candidate for prime minister, and the person who got most recommendations is asked to form a government. To this end, he/she should form a coalition with at least 61 parliament members out of the total of 120.
In the last elections, taking place on 22-January-2013, results where as follows:
Likkud (secular right), the party of the last prime minister Benyamin Netanyahu, got 31 out of 120 parliament members.
Two ultra orthodox parties, which were part of the last government, got together 18 seats.
An orthodox right party got 12 seats.
Three secular centrist parties got 19 + 7 + 2 = 28 seats.
Five secular left parties got together 32 seats.
The last prime minister, Benyamin Netanyahu, was recommended by most of the parties to be the new prime minister as well, and so was asked to form a coalition. The five left parties cannot be part of a coalition because they share an opposite point of view than that of Netanyahu. Still, Netanyahu has several possible coalitions, and his most preferred coalition was with the two ultra orthodox parties and the secular centrist party. As coalitional game theory (and past experience) tells us, he should retain most of the power. Unfortunately for him, the largest secular centrist party and the orthodox right party realized this, and they formed an alliance: either both are part of the coalition, or both are out of it (and they want to ultra orthodox parties out of the government). Since together they have 31 seats, and the five left parties that will anyway be out of the coalition have 32 seats, this means that they became a veto player. Thus, even though Netanyahu is supposed to be the prime minister, these two parties will determine the shape of the coalition.

The coalition is yet to be formed (it took Netanyahu 28 days to realize that the alliance between the two parties is for real and unbreakable), and of course it is yet to be seen how the next government will function. Yet the power of coalitions in coalitional games, and the motivation of various amalgamation axioms, is demonstrated nicely by the current negotiations.

A mixed strategy is a probability distribution over the set of pure strategies. When a player implements a mixed strategy, she chooses a pure strategy at the outset of the game, and follows that pure strategy all through the game.

A behavior strategy is a function that assigns a mixed action to each of the player’s information sets. When a player implements a behavior strategy, whenever the play reaches an information set the player chooses an action according to the mixed action that corresponds to that information set.

Thus, if the play crosses twice the same information set, a mixed strategy will choose the same action in both visits, while a behavior strategy will choose each time the action to play independently of past play.

The well known Kuhn’s Theorem states that in extensive-form games with perfect recall, the notions of mixed strategies and behavior strategies are the same: it is irrelevant whether the player makes her choices when the play visits the information set, or whether she makes these choices at the outset of the game, because the condition of perfect recall implies in particular that the play can cross each information set only once.

Kuhn’s Theorem holds for finite games: the depth of the game is finite, and there are finitely many actions in each decision nodes. The theorem can be extended to the case of infinite trees (countably many nodes), provided the number of actions in each decision nodes is finite.

In stopping problems the number of nodes is of the cardinality of the continuum, and therefore Kuhn’s Theorem does not apply. Stopping problems are a model that is used in mathematical finance: at every stage an agent receives payoff-relevant information, and she has to choose when to stop (when to sell stocks, or when to exercise options). The payoff is given by some stochastic process. Yuri Kifer asked me a question that boiled down to the following: in the model of stopping problems, are mixed strategies and behavior strategies equivalent? My first response was “sure”. Yuri wanted to see a proof. When I tried to write down the proof, a technical issue emerged. It required some time and the energy of three people to be able to provide a definite answer: “sure”.

Read the rest of this entry »

A quite amusing post I stumbled upon describes pricing algorithms used by book retailers at Amazon.com, and what happens when two retailers use such algorithms. I am pretty sure that economists can say much about the use of these algorithms, optimal pricing algorithms, whether the customer gains or loses when retailers use them, and other similar questions. Alas, I am a mathemtician, so all I can do is read the post and smile.

Symbolab is a new search engine that allows one to search for equations. A great idea for those of us who, for example, forgot how the model of “stochastic game” is called, but remember that in stochastic games one is interested in the discounted sum of payoffs. The search engine presumably searches through articles to look for the equation that you look for.

Excited about the prospect that forgetting words is no longer devastating, I immediately searched for the formula of the discounted sum of payoffs:

$\sum _{t=1}^{\infty }\left(\lambda \left(1-\lambda \right)^{t-1}r\left(s_t,a_t\right)\right)$

Unfortunately 0 results were found. I did not give up and change the payoff function from “r” to “c” and then to “u”. Maybe the engine prefers costs or utilities. When I searched for the equation with costs, I got one result; a sum related to convex sets which is not related whatsoever to discounted sum. When I searched for the equation with utilities the engine gave up. I got 174 results! but they were of various sums, none of them (at least, not the 30 top ones which I looked at) involved discounted sums. There were references to statistics, ergodic theory, and various other topics, but no economics or game theory.

Maybe stochastic games are not that common on the net. Let’s look for something simpler:

$u_i\left(\sigma \right)\ge \:u_i\left(\sigma _{-i},\sigma ‘_i\right)$

which is the condition that defines Nash equilibrium. 0 results again. I gave up.

Unfortunately, it seems that we will have to continue remembering names of concepts, and will have to consult with colleagues when we need results in topics we are not familiar with. Magic has not been found yet.

Kellogg faculty blogroll