Games of Imperfect Information
In any interesting game with imperfect information, a winning strategy will be a mixed strategy: that is, it will give some probability of differing responses to the same situation. If both players' optimal strategies are mixed strategies then the outcome of the game cannot be certainly determinant (as it can for pure strategies, since these are deterministic). But the probability distribution of outcomes to opposing mixed strategies can be calculated. A game that requires mixed strategies is defined as determined if a strategy exists that yields a minimum expected value (over possible counter-strategies) that exceeds a given value. Against this definition, all finite two player zero-sum games are clearly determined. However, the determinacy of infinite games of imperfect information (Blackwell games) is less clear.
In 1969 David Blackwell proved that some "infinite games with imperfect information" (now called "Blackwell games") are determined, and in 1998 Donald A. Martin proved that ordinary (perfect-information game) determinacy for a boldface pointclass implies Blackwell determinacy for the pointclass. This, combined with the Borel determinacy theorem of Martin, implies that all Blackwell games with Borel payoff functions are determined. Martin conjectured that ordinary determinacy and Blackwell determinacy for infinite games are equivalent in a strong sense (i.e. that Blackwell determinacy for a boldface pointclass in turn implies ordinary determinacy for that pointclass), but as of 2010, it has not been proven that Blackwell determinacy implies perfect-information-game determinacy.
Famous quotes containing the words information, games and/or imperfect:
“I believe it has been said that one copy of The Times contains more useful information than the whole of the historical works of Thucydides.”
—Richard Cobden (18041865)
“Criticism occupies the lowest place in the literary hierarchy: as regards form, almost always; and as regards moral value, incontestably. It comes after rhyming games and acrostics, which at least require a certain inventiveness.”
—Gustave Flaubert (18211880)
“The acceptance that all that is solid has melted into the air, that reality and morality are not givens but imperfect human constructs, is the point from which fiction begins.”
—Salman Rushdie (b. 1947)