6
$\begingroup$

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"?

$\endgroup$
  • $\begingroup$ How deeply have you researched Game Theory? (I'm asking for context.) Even in games with incomplete information, whether "deterministic" (Battleship) or involving "quantum indeterminacy" (Prisoner's Dilemma), there are optimal strategies (for instance, binary search extended to a 2D model in Battleship, and minimax in simultaneous games.) Even Rock, Paper, Scissors seems to have an optimal strategy: arstechnica.com/science/2014/05/… $\endgroup$ – DukeZhou Apr 21 '17 at 16:48
  • $\begingroup$ Great question, btw! This is a central issue in my own research. $\endgroup$ – DukeZhou Apr 21 '17 at 16:50
  • $\begingroup$ I have little experience in game theory asides from reading a few things here and there. Regarding your examples, I was curious if there was any approaches to the problem in a more general sense $\endgroup$ – k.c. sayz 'k.c sayz' Apr 21 '17 at 16:52
  • $\begingroup$ Ok. I'm going to attempt a formal answer. Mega-props for bringing up Hofstadter, btw. $\endgroup$ – DukeZhou Apr 21 '17 at 16:53
  • $\begingroup$ Id read this paper out of the University of Alberta: science.sciencemag.org/content/early/2017/03/01/… $\endgroup$ – Jaden Travnik Apr 21 '17 at 17:10
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I see.... correct me if I am wrong, but are you basically saying that right now we do not even have an rigour analytical framework to trace the problem? $\endgroup$ – k.c. sayz 'k.c sayz' Apr 21 '17 at 17:28
  • $\begingroup$ @colourincorrect Quite the opposite. The framework has been rigorously defined and continues to be validated on problems of increasing intractability. Perfect play is not objectively perfect, just more optimal than the opponent's play. But superrationality is still new and requires more research and validation from a mathematical (as opposed to metaphysical) perspective. Superrationality is being studied in the context of games of imperfect information, such as Prisoner's Dilemma, and if validated, that validation will be mathematical. Right now it is an hypothesis. $\endgroup$ – DukeZhou Apr 21 '17 at 17:45
  • $\begingroup$ "...we do not even have an rigour analytical framework to trace the problem" as in in terms of super-rationality, and an "objective utility function" to "correctly evaluate" situations I ask $\endgroup$ – k.c. sayz 'k.c sayz' Apr 21 '17 at 17:47
  • $\begingroup$ @colourincorrect Game Theory is that framework. There are absolutely strategies for dealing with different levels of indeterminacy, such as P < .5 In simultaneous games, P can never objectively be > .5 , because of hidden information (i.e. the most basic form is a binary Schroedinger box) Thus no rational agent plays the lottery to win, unless the odds are flawed in a favorable way, which does rarely occur and has been, famously, exploited by mathematicians. $\endgroup$ – DukeZhou Apr 21 '17 at 17:54
  • $\begingroup$ @colourincorrect It is actually a good idea to look at Blackjack, and more recently, Poker for an understanding of how strategy changes if probability can be raised above .5. Even 50.000000000000000000001% probability will lead to gain given a sufficient number of hands. The trick is to determine if probability of a given event is truly above this threshold, which also involves confidence levels (analysis of the dataset to reduce margin of error for a sufficient confidence level, such as with a point estimate.) Recent winning strategies for poker are a function of mathematics. $\endgroup$ – DukeZhou Apr 21 '17 at 17:58
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ apologies for the late response: i didn't see it. is there a source for this? i think i agree with your claim, but wouldn't information incompleteness also imply that the payoff matrix is unknown? wouldn't that affect play? $\endgroup$ – k.c. sayz 'k.c sayz' Oct 21 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.