Perfect play in information incomplete games

Question

As titled, is there such thing as perfect play (or at least "perfectly optimal") in a game with incomplete information? Or at least a proof as to show why there cannot?

Naively (and seemingly obviously), the answer would be a resounding no, since the agent would be likely be forced to pick between "lottery events".

But in practice (using competitive video games as an analogy), we'd see that players would stick to a meta-game that is well equipped to defend against a majority of events that might happen, given incomplete information. Of course the response to that would be that there probably exists a "hard-counter" for any given meta-game, but if it is indeed the case that the meta-game is the "most-optimal" it probably is the case also that such a hard counter puts the player in an unfavourable position most of the time, thus the "hard-counter" itself is not optimal. Thus we'd likely see that any given first encounter players would still stick to their "optimal meta-game" rather than a hard counter of their optimal play.

A more rigour analogy would be to ask: "Under Hofstadter's notion of superrationality, how would agents play information incomplete games", but I couldn't find any readings on trying to import the notion of super-rationality into information incomplete games.

Alternatively: is there such thing as a "perfectly optimal meta-game"?

Answer 1

This may be an evolving answer, because the question is, in some sense, a (useful) rabbit hole. I apologize if I don't go deeply into meta-games per se, as it's a little outside of my scope, which is non-chance games of perfect information, but I think it's worthwhile to think about the underlying problem of indeterminacy in relation to games in general.

Bounded Rationality* is a useful concept because it pre-supposes a condition of computational intractability. Computational intractability can be introduced into games in several forms:

• Complexity
• Hidden Information
• Randomness ("quantum" indeterminacy)

_{[For more details on my use of "quantum" in regards to randomness, see Deterministic Games.]}

The underlying purpose of game theory is to determine "optimal" strategies for any given problem. I put optimal in quotes because optimality is a spectrum, and subjective in a condition of computational intractability.

Thus, we cannot know if AlphaGo plays optimally, only that it played more optimally than Lee Sedol in 4 out of 5 games.

This is distinct from strongly solved games such as tic-tac-toe, where we can know with total certainty that a choice is optimal, because the problem of tic-tac-toe is computationally tractable.

Part of the confusion may be semantic, because the concepts are subtle and profound, and require language, what TS Eliot might have called "the intolerable wrestle with words and meanings." (For instance, I used hidden information above to avoid having to distinguish between incomplete and imperfect information.)

• Perfect Play is generally defined as a strategy that leads to the best possible outcome for a participant, regardless of the choices of the opponent.

Thus minimax is of central importance, and provided the foundation for game theory.

Even in games with incomplete information, whether "deterministic" (Battleship) or involving "quantum indeterminacy" (Prisoner's Dilemma), there are optimal strategies. For simultaneous games such as Dilemma and all of the numerous extensions minimax is used. In Battleship, there are at least three strategies of increasing optimality, and although there doesn't appear to be a strategy that can yield P > .5, if one player employs a more optimal strategy, they will win in aggregate. Even Rock, Paper, Scissors seems to have an optimal strategy, which blows my mind, and carries the caveat that I need to look into it more.

• Thus, perfect play, as defined, is certainly achievable, but does not necessarily connote (objectively) optimal choices, which is a little confusing, because "perfect" implies objectivity, a condition which is only possible in regard to tractable problems.

It is also important to note that there may not be a "winning" strategy in the sense of being better off than the opponent, and in this condition, perfect or optimal play is mitigation of loss.

---

*In terms of incomplete information games specifically, I think there's a case for extending the concept of Bounded Rationality is extended to include information that cannot be observed or "known".

Colloquially, this would include the "unknowns" (both known and unknown) and the "unknowable" (quantum indeterminacy and superpositions).

Answer 2

This second answer attempts to address perfect play in relation to incomplete information specifically.

An element in the difficulty in answering this question may be that the concept of perfect play is widely applied to solved games in the domain of Combinatorial Game Theory as opposed to strictly economic Game Theory.

In relation to games with incomplete information:

• Perfect play, defined as the best possible choice, without regard to the opponents choice, may be achieved in games with incomplete information

It's important to note that perfect play may not result in a win. In tic-tac-toe the result is a draw. In certain games, for a disadvantaged player, it may result in the "best" possible loss.

• Perfect play in classic Prisoner's Dilemma is the minimax strategy.

The conundrum is that in this model, it does not lead to the optimal outcome, only the optimal outcome without regard to the other agent's choice.

In classic Prisoner's Dilemma, the supperational strategy is more risky because there is no information on the other agent (probability for either choice is always 50%) and it doesn't limit downside.

---

Superrational strategies can be shown to be mathematically supportable by extending Prisoner's Dilemma to iterative and cyclic variants. This is partly because in iterative variants, choice are a form of communication between agents. However, the superrational strategy may not be a winning strategy, as the motive of the superrational agent may be said to be maximization benefit, as opposed to limiting downside exclusively. In in iterative Prisoner's Dilemma, the superrational agent may have to sacrifice a couple of iterations (turning the other cheek) in order to incentivize the rational agent to change strategy and cooperate, and to determine if the other agent is irrational, in which case the superrational agent may switch to the rational strategy of minimizing maximum downside and maximizing minimum benefit.

In classic iterated Dilemma, choices are the exclusive form of communication between agents, and each choice becomes part of a dataset on the other agent's decision making. Information is still incomplete, but less incomplete with each iteration.

Superrational strategies for games of incomplete information then become viable via statistical analysis.

Answer 3

It depends on the game. In zero sum non cooperative games yes, there's always a GTO strategy.

The easiest example is Rock, Paper, Scissors, where playing 1/3 of each randomly would be the only optimal strategy. In this case a break even one too, in some games though GTO has a positive expected value against any strategy that's not GTO itself.

Usually online video games strategies and metas are heavily based on adaptation to population tendencies though, which in of itself it's not perfect play, but it can have a better expected value than perfect play against a non optimal opponent.