To what extent do optimal strategies exist?

[mathcam]

Well, I think you have to be more specific. If you assume the rationality of all players (which is indeed the assumption for most of game theory), and assure that the roles in the game are made public before the game starts, then yes, I feel pretty confident that there's an optimal strategy for each player.

When playing against an irrational enemy with an optimal strategy, you should expect to win more than if they were being 100% rational. Right?

Actually, no. For example, optimal strategy (at least in the sense of game theory) for rock-paper-scissors is to choose randomly every time. Re-doing draws, you'll expect to win 1/2 of the time. And now note that even if you are playing against a complete dimwit who picks his nose and picks rock every time, you still only expect to win 1/2 of the time. Your optimal strategy

guarantees

you the most you can possibly be guaranteed. And often your optimal strategy

limits

you to this as well.

In contrast, you might argue that using psychology you could expect to do better than win 1/2 of the time. There are two fallacies in this thinking: a) You simply

can't

do better than 1/2, even using every psychological trick in the book, if your opponent has decided to play randomly his/herself, and b) If someone knows more of the psychology than you, you risk winning

less

than 1/2 of the time.

I don't know enough about AI to answer your open question, but I'm pretty sure that the problem is not NP-complete...we're just recursively generating probabilities (see my post in optimal doc strategy), which is certainly polynomial time.

Cam

[mathcam]

Now

that

would be a very cool simulation. I'd sure like to hear the results from that.

I think you can O() the problem.

We can get a Buddhist monk to lie down on his side and medidate on the problem?

Cam

[mathcam]

Yeah, but poker's a lot harder. Each unknown person has three possible classifications: cop, mafia, or townie, and not the plethora of possibilities you get for poker hands. Plus, you never get people

bluffing

at being mafia. Everyone is attempting, to some degree, to blend in.

Cam

[mathcam]

A rational player is one that follows an optimal strategy when one exists.

Cam

[mathcam]

You make exactly the point that defeats your argument, ID. The optimal strategy for a player is independent of what the people in the game actually say. It doesn't

matter

whether someone claims to be mafia or not, just as you mention, so a computer doesn't have to take into account all these psychological phenomena.

Cam