The Emerging Revolution in Game Theory • Hacker News Board

Re: The Emerging Revolution in Game Theory

#21

Post by AnIrishDuck » Fri, Aug 17, 2012, 3:05 PM UTC

DennisP wrote: post #18

jorleif wrote: post #8

Earlier quoted context omitted.

Actually, the original paper is this one: http://www.pnas.org/content/early/2012/05/16/1206569109.full... Here is an description of the result and its implications http://golem.ph.utexas.edu/category/2012/07/zerodeterminant_...

Wow. Not long ago I was trying to test whether an idea for a certain kind of online interaction would work out the way I hoped. I built a simulation with agents that evolved their strategies, trying to optimize their own outcomes. Maybe that's not such a good test after all.

I don't believe this outcome is optimal from an evolutionary standpoint. It requires the other player to know what your strategy is and accept the ultimatum (I will do x% better than you). The other player still has the option to reject the ultimatum, screwing over both parties.

In other words, for this strategy to work it needs "pragmatic" other players that are (a) intelligent enough to know what the other player is doing and (b) willing to accept the unequal outcome. This strategy isn't symmetric: if you turned two of these bots against each other the total outcome would be much worse than if two TFT bots played each other.

Thus it stands to reason that TFT or some small variant is still the evolutionary winner.

Re: The Emerging Revolution in Game Theory

#22

Post by baak » Fri, Aug 17, 2012, 3:07 PM UTC

dohko wrote: post #16

So, this paper is not really demonstrating anything against the standard game theory applied to the prisoner's dilemma. In a single game, the proposition of the dilemma still holds true. The best solution is if both don't talk. In an iterative game, then things change.. but that's pretty obvious. So not sure what is so revoluationary about this paper.

I thought it said in a single game your best strategy is to talk? This guarantees you will not take the maximum penalty.

Re: The Emerging Revolution in Game Theory

#23

Post by ramblerman » Fri, Aug 17, 2012, 3:26 PM UTC

"This and similar "quant" nonsense is precisely what has led to the biggest uncollectable pile of derivative securities and assorted options of the too big to fail banking disaster we are currently confronting. All these gambling scenarios are counter productive to improvements necessary to increasing the world's real physical wealth. These studies are worse than useless, they are parasitic cancers on society."

This comment below the article made me smile. I kind of feel inclined to agree, even though it is of course too simplistic a view.

Re: The Emerging Revolution in Game Theory

#24

Post by mindcrime » Fri, Aug 17, 2012, 4:12 PM UTC

Hrrm... I'm no game theory expert, but I thought that it had been known for some time that there were strategies which could beat "tit for tat" in IPD. But this article makes it sound like "tit for tat" was the state of the art until this particular discovery.

Guess I need to go back and do some more reading on the subject. This reminds me, I've been meaning to read The Evolution of Cooperation[1] forever, and haven't found time yet. sigh

[1]: http://en.wikipedia.org/wiki/Evolution_of_cooperation

Re: The Emerging Revolution in Game Theory

#25

Post by DennisP » Fri, Aug 17, 2012, 4:47 PM UTC

AnIrishDuck wrote: post #21

DennisP wrote: post #18

Earlier quoted context omitted.

Wow. Not long ago I was trying to test whether an idea for a certain kind of online interaction would work out the way I hoped. I built a simulation with agents that evolved their strategies, trying to optimize their own outcomes. Maybe that's not such a good test after all.

I don't believe this outcome is optimal from an evolutionary standpoint. It requires the other player to know what your strategy is and accept the ultimatum (I will do x% better than you). The other player still has the option to reject the ultimatum, screwing over both parties. In other words, for this strategy to work it needs "pragmatic" other players that are (a) intelligent enough to know what the other player i…

What I'm thinking is, it appears that players with a theory of mind may not actually use the optimal evolutionary strategy. Since humans have a theory of mind, my simulation may be a poor predictor of what my users would actually do.

Re: The Emerging Revolution in Game Theory

#26

Post by masterzora » Fri, Aug 17, 2012, 4:53 PM UTC

rubidium wrote: post #17

gizzlon wrote: post #13

" Nevertheless, in a single game, the best strategy is to snitch because it guarantees that you don't get the maximum jail term. " Huh? That isn't correct is it? Snitching is best because it gives the highest payout regardless of what the other person does (snitching strictly dominates not snitching). If the other does not snitch and you do, you go free. If the other person does snitch, you should as well, because it…

You describe exactly what that sentence says...

Not really. The sentence says that the reason you defect is specifically to avoid the worst possible result. This is bad logic. The reason defect is considered dominant is because, regardless of what the other player does, your outcome is better if you defect. It is a very different statement.

Re: The Emerging Revolution in Game Theory

#27

Post by Steko » Fri, Aug 17, 2012, 5:02 PM UTC

geuis wrote: post #12

Steko wrote: post #7

Good old rock, nothing beats rock. Doh!

Do you actually think this comment is intelligent or otherwise improves the discussion others are having about this topic? For one, I am pretty much completely lost in terms of what this article is saying, and inane commentary does not help in the process of understanding.

The gist of the article is that a long held strategy has been found inferior. This has been hailed as a revolution by some (the author and no doubt some of the community he's writing about) while the longer view, which can be seen in the post's comments is that it's expected:

"This just seems to be an extension of the folk theorem to the family of probabilistic strategies. 1. Any level payoff level can be supported in equilbrium (Press & Dyson), 2. None of those equilbria survive evolutionary refinements (this paper). Interesting stuff, but not quite revolutionary as it is suggested. "

The reference I was making was a famous line from the Simpsons where Bart's strategy of "good old rock, nothing beats that" is adapted to by Lisa who picks paper. Yeah I misquoted, season 4 was a long time ago :)

http://www.youtube.com/watch?v=NMxzU6hxrNA

No it probably wasn't the most intelligent or informed comment I could have made. Sometimes the not most intelligent comments can be useful. Maybe this one wasn't one of those but, /shrug I would probably make it again.

Re: The Emerging Revolution in Game Theory

#28

Post by dllu » Fri, Aug 17, 2012, 10:45 PM UTC

adrianN wrote: post #11

cheshirecat wrote: post #4

A separate example of very advanced strategies in the simplest game: Rock Paper Scissors Programming Competition http://www.rpscontest.com Personally I think it is somehow ahead of these academic researches in some sense.

Except it is not difficult to prove that you can't win in expectation against a random RPS player. The programming competition is only fun because the players are nonrandom.

It just takes one nonrandom player in the pool of players for a more advanced strategy to gain an advantage. Consequently, it is almost certain that, given a tournament of an arbitrary set of RPS players, a very sophisticated RPS player will end up winning, whereas random players will always be relegated to mediocre results.