You are currently browsing the category archive for the ‘Uncategorized’ category.
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.”
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!
There is a debate underway about how effective Israel’s iron dome system is in protecting populated areas from missile attacks. On the pro side it is argued that somewhere between 85% to 90% of incoming missiles are destroyed. The con side argues that the proportion is much smaller, 40% or less. A large part of the difference comes from how one defines `destroy’. Perhaps a better term would be intercept. It is possible that about 90% of incoming missiles are intercepted. However, a missile once intercepted may not have its warhead disabled, making at least one of the fragments that falls to ground (in a populated area) dangerous.
While nailing down the actual numbers may be interesting, it strikes me as irrelevant. Suppose that any incoming missile has a 90% chance of being intercepted and destroyed (which is the claim of the builder of the iron dome technology). If the attacker launches N missiles and iron dome is deployed, the probability (assuming independence) not a single one making it through is (0.9)^N. Thus, the probability of at least one missile making it through the `dome’ is 1 – (0.9)^N. If N is large, this is large. For example, for N = 10, the probability that at least one missile makes its way through is at least 60% (thanks to anonymous below for correction). Thus, as long as the attacker has access to large quantities of missiles, it can be sure to get missiles through the dome.
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.
In the course of a pleasant dinner, conversation turned to dictatorship and the organization of markets. At this point, Roger Myerson, remarked upon the absence of inter-species trade. He was not, of course, referring to trade with alien beings from another planet (who would have discovered correlated equilibrium before Nash equilibrium). Rather, the absence of trade with, say, monkeys. Adam Smith, went further and denied the possibility of trade between animals.
Nobody ever saw a dog make a fair and deliberate exchange of one bone for another with another dog. Nobody ever saw one animal by its gestures and natural cries signify to another, this is mine, that yours………
There is a long history of interactions between men and monkeys of various kinds. Monkeys have been marauders of crops, domestic companions, religious symbols and commodities (meat). The interactions between the species seems to fall into one of three categories: pure conflict (keeping out marauders), long run relationships (pets) or exploitation (used in labs and as entertainment). However, no examples of what one might call trade in the sense of voluntary arms length transactions involving barter. For example, why don’t villagers `pay’ bands of roving monkeys to not pillage?
There is evidence to indicating they would be capable of understanding such transactions. Gomes and Boesch, for example, suggest that monkeys trade meat for sex. Then, there is Keith Chen’s monkey study which suggests that one could teach (some) monkeys about money. From the Jesuit traveller Jose de Acosta in the 1500′s we have the following charming account:
I sawe one [monkey] in Carthagene [Cartagena] in the Governour’s house, so taught, as the things he did seemed incredible: they sent him to the Taverne for wine, putting the pot in one hand, and the money in the other; and they could not possibly gette the money out of his hand, before he had his pot full of wine.
A little known fact about Canada is that it is the world’s largest producer of famous Americans. Recall, for example, John Kenneth Galbraith, Wayne Gretzky, William Shatner, Michael J. Fox, Malcolm Gladwell, Shirley Tilghman and Keanu Reeves. Some have suggested that Obama is a Canadian, leading to a split in the birther movement between the original birthers and the neo-birthers. Originalists believe that Obama was sired in a Kenyan village, imbued with an anti-colonial mindset, leavened by Saul Alinsky radicalism and smuggled into the US with the intent of turning the US into an Islamic caliphate. The neo-birthers believe that this beggars belief. It is simpler, they say, to believe that Obama is Canadian.
Nate Silver, needs no introduction. While I should have read his book by now, I have not. From my student Kane Sweeney, I learn I should have. Kane, if I may ape Alvin Roth, is a student on the job market paper this year with a nice paper on the design of healthcare exchanges. Given the imminent roll out of these things I would have expected a deluge of market design papers on the subject. Kane’s is the only one I’m aware of. But, I digress (in a good cause).
Returning to Silver, he writes in his book:
One of the most important tests of a forecast — I would argue that it is the single most important one — is called calibration. Out of all the times you said there was a 40 percent chance of rain, how often did rain actually occur? If over the long run, it really did rain about 40 percent of the time, that means your forecasts were well calibrated
Many years ago, Dean Foster and myself wrote a paper called Asymptotic Calibration. In another plug for a student, see this post. An aside to Kevin: the `algebraically tedious’ bit will come back to haunt you! I digress again. Returning to the point I want to make; one interpretation of our paper is that calibration is perhaps not such a good test. This is because, as we show, given sufficient time, anyone can generate probability forecasts that are close to calibrated. We do mean anyone, including those who know nothing about the weather. See Eran Shmaya’s earlier posts on the literature around this.
One of the differences, often commented upon, between economists and computer scientists is the publication culture. Economists publish far fewer and longer papers for journals. Computer scientists publish many, smaller papers for conference proceedings. The journals (the top ones anyway) are heavily refereed while, the top conference proceedings are less so. Economics papers have long introductions that justify the importance of what is to come as well as (usually) carefully laying out the differences between the current paper and what has come before. It is not unusual for some readers to cry: don’t bore us get to the chorus. Computer science papers have short introductions with modest attempts at justifying what is to come. It is not unusual to hear that an economics paper is well written. Rarely, have I heard that of a computer science paper. Economists sometimes sneer at the lack of heft in CS papers, while Computer Scientists refer caustically to the bloat of ECON papers. CS papers are sometimes just wrong, etc. etc.
If one accepts these differences as more than caricature, but true, do they matter? We have two different ways for organizing the incentives for knowledge production. One rewards large contributions written up for journals with exacting (some would say idiosyncratic) standards and tastes. The other rewards the accumulation of many smaller contributions that appear in competitive proceedings that are, perhaps, more `democratic’ in their tastes. Is there any reason to suppose that one produces fewer important advances than the other? In the CS model, for example, ideas, even small ones, are disseminated quickly, publicly and evaluated by the community. Good ideas, even ones that appear in papers with mistakes, are identified and developed rapidly by the `collective’. An example is Broder’s paper on approximating the permanent. On the ECON side, much of this effort is borne by a smaller set of individuals and some of it in private in the sense of folk results and intuitions. Is there a model out there that would shed light on this?
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”.
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.
Recent Comments