You are currently browsing the monthly archive for March 2011.

Department of self-promotion: sequential tests, Blackwell games and the axiom of determinacy.

This puzzle, which appeared on the blog associated with the cute webcomic xkcd, would make a good exercise in a game-theory course:

Alice secretly picks two different real numbers by an unknown process and puts them in two (abstract) envelopes.  Bob chooses one of the two envelopes randomly (with a fair coin toss), and shows you the number in that envelope.  You must now guess whether the number in the other, closed envelope is larger or smaller than the one you’ve seen.

Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?

A good start is to notice that the possibility that Alice may randomize is a red herring. You need a strategy with a greater than 50% chance of winning against any pair she may choose. If you can do this, it takes care of her randomized strategies for free. (A familiar argument to those who enjoy computing values of zero-sum games.)

In which I talked about Olszewksi and Sandroni’s paper Manipulability of future independent tests’ and coupling of stochastic processes.

I am visiting the rationality center in the Hebrew University, and I am presenting some papers from the expert testing literature. Here are the lecture notes for the first talk. If you read this and find typos please let me know. The next paragraph contains the background story, and can be safely skipped.

A self-proclaimed expert opens a shop with a sign at the door that says Here you can buy probabilities’. So the expert is a kind of a fortune-teller, he provides a service, or a product, and the product that the expert provides is a real number: the probability of some event or more generally the distribution of some random variable. You can ask for the probability of rain tomorrow, give the expert some green papers with a picture of George Washington and receive in return a paper with a real number between 0 and 1. The testing literature asks whether you can, after the fact, check the quality of the product you got from the expert, i.e. whether the expert gave you the correct probability or whether he just emptied your pocket for a worthless number.

So, let ${X}$ be a set of realizations. Nature randomizes an element from ${X}$ according to some distribution and an expert claims to know Nature’s distribution. A test is given by a function ${T:\Delta(X)\rightarrow 2^X}$: the expert delivers a forecast ${\mu\in\Delta(X)}$ and fails if the realization ${x}$ turned out to be in ${T(\mu)}$. A good test will be such that only `true’ experts, i.e. those who deliver the correct ${\mu}$, will not fail. Read the rest of this entry »

There are two equivalent ways to understand the best response property of a Nash Equilibrium strategy. First, we can say that the player plays a mixed strategy whose expected payoff is maximal among all possible mixed strategies. Second, we can say that the player randomly chooses a pure strategy from the set of pure strategies whose expected payoff is maximal among all possible pure strategies.

So far so good, and every student of game theory is aware of this equivalence. What I think is less known is that the two perspectives are not identical for ${\epsilon}$-best response and ${\epsilon}$-equilibrium: A mixed strategy whose expected payoff is almost optimal might put some positive (though small) probability on a pure strategy which gives a horrible payoff. In this post I am going to explain why I used to think the difference between the two perspectives is inconsequential, and why, following a conversation with Ayala Mashiah-Yaakovi about her work on subgame perfect equilibrium in Borel games, I changed my mind.

Amsrefs is a package for preparing bibliographic lists. If, like me, you use bibtex then you may find this post informative. If you enter your bibliographic items into the tex file manually, \emph-asizing titles and consulting Chicago Manual of Style to check whether the publisher should appear before or after the publication year then please have mercy on your co-authors and start eating with fork and knife. You spill typos all over the place.

So I have tried using amsrefs recently. Pro: Bibliographic items are entered in the tex file using a command similar to \bibitem, no need to keep a separate bib file and running  bibtex. This is more convenient, especially if your folders are as messy as mine. Cons: Bibliographic items are not sorted, they  appear in the pdf in the same order they appear in the tex file. Worse, all the entries in your bibliographic list appear in the pdf document, even those you don’t cite in the main text. The referee will search for their name, find the paper in the list of references, then search for the citation and get pissed when it’s not there: apparently you know about their paper but have nothing to say about it. Another con: You are in charge of capitalization of the journal and paper titles. Chicago Manual of Style anybody ?

Bottom line: I think I will return to bibtex. Am I missing anything ?