randomness-deficiency and game theory

[gusl]

Randomness is a finite resource. People seem to have less of it than computers. (I'd say this is a form of "bounded rationality")

What does this imply about game theory, namely mixed strategies?

UPDATE: do correlated equilibria extend classical game theory in the required way?

Comments

[peamasii.livejournal.com]

Interesting. For example if you play rock-paper-scissors, can you objectively randomize your actions without creating/following any pattern?

[gustavolacerda.livejournal.com]

Nope.
To put it roughly, one's amount of randomness is what distinguishes the good from the bad players.

[peamasii.livejournal.com]

nash equilibrium!

[gustavolacerda.livejournal.com]

It would be interesting to try to compress a players' action sequence, and compare this with their scores / rankings. Of course, each player is interacting with another player... so maybe gzip will be measuring their joint randomness.

Still, I'd like a more objective measure of a player's skill. Maybe some sort of conditional entropy. Perhaps the entropy of their response to the last n-gram of the other player's hand / last n-gram of hand-pairs.

[selfishgene.livejournal.com]

There is an old joke about a donkey starving because he is placed equidistant from 2 piles of hay. People sometimes both try to speak at the same instant. This can lead to a complex backoff-retry loop, but it rarely lasts more than 5 seconds. So animals have some level of randomness to resolve such scenarios. I don't think there was ever much evolutionary pressure for more than that. People who are not trained in statistics use instinctive decision strategies which normally give a good enough answer.

[(Anonymous)]

This turns out to be rather complicated. You tend to fall into sequential patterns based on your opponent's actions, which causes this bizarre feedback loop with all sorts of unintuitive consequences. For example, we found situations where we could have a person playing against an AI model, increase the randomness in the AI, and the person's performance would _improve_. And yes, it's an improvement away from chance. This still confuses me.....

Here's the paper, if you're interested: http://terrystewart.ca/sites/default/files/2005-Stochastic_Resonance.pdf

[easwaran.livejournal.com]

That's not so much a joke as a serious puzzle for theory of action, decision, and motivation, called Buridan's Ass. Even if you allow for mixed strategies, how should the donkey decide between the left bale, the right bale, and a mixed strategy with an x% chance of going for the left bale? Every mixed strategy is equally good as every pure strategy here, so there's still no way to decide between any of them.

[selfishgene.livejournal.com]

Good point. I'm not really sure whether animals resolve this by internal generation of randomness or by some uncontrolled aspect of the situation. If the donkey's right eye sees the hay a millisecond before the left eye then that could lead to a bias (not clear which direction). Nevertheless it is clear that animals never actually starve in these cases because some sort of tie break mechanism exists.

[gustavolacerda.livejournal.com]

thanks, Terry.

[candid.livejournal.com]

I disagree with this.

One's amount of randomness is what distinguished the good from the bad players in a game of "RPS against a randomizer."

RPS against people involves all sorts of psychology.