New Tack Wins Prisoner's Dilemma

[bemildred]

Proving that a new approach can secure victory in a classic strategy game, a team from England's Southampton University has won the 20th-anniversary Iterated Prisoner's Dilemma competition, toppling the long-term winner from its throne.

The Southampton group, whose primary research area is software agents, said its strategy involved a series of moves allowing players to recognize each other and act cooperatively.

The Prisoner's Dilemma is a game-theory problem for two players. As typically described, two accomplices are arrested and separated for interrogation by the police, who give each the same choice: confess to authorities (defect) or remain silent (cooperate). If one defects and the other cooperates, the defector walks free and the cooperator gets 10 years in jail. If both cooperate, both get six months. If both defect, both get six years. Neither suspect knows the other's choice.

"The Prisoner's Dilemma is this canonical problem of how to get cooperation to emerge from selfish agents," said Nick Jennings, a professor in computer science at Southampton University and leader of the winning team along with his Ph.D. student, Gopal Ramchurn. "People are very keen on it because they can see so many parallels in real life."

Wired News

[papau]

1. What does it all mean in real life??? - I am so confused!!! :-)

Mutual Assured Destruction (Tit for Tat where a player's first move is always to cooperate with other players, followed by echoing whatever the other players do) and its MAD equivalent of a promise to not use weaponry so long as the other side refrained from doing so as well) has been bested if the "separate rooms" idea is overcome via recognizing each other via knowing prior moves and seeing a "friendly pattern" (meaning the no communication rule is dead as we have collusion with someone among the allies agreeing to sacrifice oneself so another of the allies can win and beat all others).


"What's interesting from our point of view," he said, "was to test some ideas we had about teamwork in general agent systems, and this detection of working together as a team is a quite fundamental problem. What was interesting was to see how many colluders you need in a population. It turns out we had far too many -- we would have won with around 20."

an evolutionary variant of the game in which each player plays only its neighbors on a grid. If your neighbors do better than you do, you adopt their strategy..."Our initial results tell us that ours is an evolutionarily stable strategy -- if we start off with a reasonable number of our colluders in the system, in the end everyone will be a colluder like ours," he said."

Is this just forming teams, and taking a blow for the team? Or is the idea that democracy is inevitable as long as there is cooperation - or is it that strong convictions lose to a team that has folks willing to flip/flop?

I am so confused!!! :-) as Vinnie Barbarino would say on "Carter"

[phantom power]

2. It's about how cooperation can emerge from a basic set of rules

How do people (or other animals) learn to cooperate? There's no guarantee of payoff. Why do cooperating societies emerge?

These people are doing experiments to help us learn how that happens.

Also, we can use this information to engineer cooperating systems of software agents, or robots, eventually nano-machines, etc.

[bemildred]

3. Roughly: you can improve your results by cheating and getting

other suckers to sacrifice for you ...

The most interesting line IMHO is: "Our initial results tell us that ours is an evolutionarily stable strategy", which means once somebody starts
cheating, everybody else is forced to start cheating too.

So much for the "magic of the market" absent an effective referree.

[papau]

4. That is the way I read it also! I hate zero sum games!

:-)

[bemildred]

5. e j e is not wrong.

The really interesting question is under what circumstances
does cooperative communitarian behavior emerge (prove "evolutionarily
stable") and when do you get dog-eat-dog and/or warlike behavior.
One sees both. One factor that seems important is population
density. I would speculate that at that point where the primary
competitive pressure on humans becomes other humans, one starts
to see the ugly stuff. So you could speculate that in order to
have peaceful civilization you have to provide a measure of social
security, and without it one gets human on human predation, gangs,
competitive excesses, and giant amoral corporations.

You are correct that the zero sum nature of the game is a critical factor.
One of the pernicious fallacies in current US foreign policy is that
it is seen as a sort of zero sum economic game of hog-in-the-trough.

[papau]

6. E J E is indeed not wrong-but is the model realistic?Heuristic programing

in the 60's focused on feedback loops that "learned" (made small changes in some parameters)from the "errors" of the prior simulation. Fuzzy logic seems to be a similar probabilistic learning via changed parameters on each cycle based on last state.

They keep telling me heuristic is different from an algorithm because heuristic says how to change the algorithm for the next cycle - and folks say that this "heuristic" is a "mere" rule of thumb or guideline, as opposed to an invariant procedure like an algorithm. Granted ones grad work is spent learning which techniques are likely to lead to a proof - and granted this is not learning an invariant procedure - but I never saw much difference as it seemed to be just learning an algorithm for choosing the likely to be correct procedure.

And it always came back to feedback routines in this area of programing.

The `åõñéóêù as far as I can tell is in finding the model that gives realistic real world results - which means fits the past so that it has a chance of predicting the future. There is no past to fit to these models, there is no way to benchmark them. It lives or dies on the logic as expressed in words making sense and the program being those words in operation. In effect you know the solution, and the hard part is getting the program written in a way to prove you correct.

These folks reviewing these computer programs say they are observing the equivalent of human cooperation - I am just not sure - and I am too old and tired to spend the time convincing myself that they are - or they are not - achieving the human interaction output that they say they are.

If there is a "..." for idiots book on this I'll give it a read - until then I take these with a grain of salt.

:-)

[bemildred]

7. Not realistic at all.

Math and mathlike things are not, except occasionally by accident.

This is somewhat as e j e says, experimentation with what you can
do with simple games and simple rules, and because of the method you
can see emergent "properties" when you add a bit of complication,
and that tells you some things about what depends on what.

As I've blathered elsewhere, I find the idea that simple reductive
models offer real-world predictive capacity silly. The idea is very
attractive but does not stand up to examination. The world is not
Newton's clockwork or anything of the sort, even in physics, let alone
where you don't weed out all the "irrelevant factors".

Probably the best and most impressive example of real-world prediction
I know of is weather, which is good for about five days out a fair
fraction of the time. I don't think markets are predictable in any
general way, anymore than a roulette wheel. It is true that celestial
bodies are predictable most of the time, and many things have a kind
of "intertia" that leads them to be tomorrow much like they were
today, most of the time.

I have little use for fuzzy logic and similar approaches where you
complicate up the machine in hopes of getting less rigid or "adaptive"
behavior. It's not all bullshit, but it is also not remotely like
how living systems "think", and gives only somewhat better results,
not some whole new level of performance. The most interesting stuff,
IMHO, is still done with massive application of power, usually in
highly parallel architectures, with reasonably well understood issues
in terms of algorithmic approach. The AI stuff is sometimes interesting
but remains far from what cheap, abundant, and flexible humans can
do easily, when trained to a task. Really intelligent systems are
grown, not designed. You could say these experiments are poking
around in the roots of what you would do to design a system in
which you could "grow" intelligence.

I expect the experimenters and commentators are enthusiasts and also
trying to drum up a bit of funding now and then.

</flame>

[phantom power]

10. determinism does not imply predictability

I'm of the opinion that the world does indeed function in the manner of Newton's clockwork; it's easy to build a deterministic machine whose behavior is irreducible: the fastest algorithm for determining the state of the machine at time "t" is equivalent to running the machine itself.

The universe is such a machine, as is the earth's weather, as are we. As a friend of mine once said, "Determinism hardly matters: I'll always be able to surprise myself"

From your conversation, I think you would both be very interested in reading the work of Stuart Kauffman. He wrote a sort of educated-layman's introduction called "At Home In the Universe", describing his work on emergent systems.

I wish he'd chosen a different title, since it captures nothing of the subjects he's talking about, aside from some appealing philosophical implications.

[bemildred]

11. Yes.

I will look up Mr. Kaufman.

I disagree that the world (in general) is determinate, although I
agree with the point that determinism does not imply predictability.
I think we consider things determinate that we feel we have good
explanations for, and that we ignore the rest, not knowing what to
say about them.

But, it's an interesting question. What does "determinate" mean if
not "predictable", or to phrase another way: what good is it if a
phenomenon is determinate if you cannot predict it? Of course in the
real world what you get is sort of limited predictability in these
cases, as with the weather. The point is that chaotic behavior is
not binary, it comes in gradations and the degree of chaos is inverse
to the range of predictability.

I would say that the world is somewhat determinate, and somewhat not,
and point to quantum mechanics.

[phantom power]

13. A definition of "deterministic"

Deterministic is probably best defined this way: If a system always runs in exactly the same way given the same starting-conditions, then that system is deterministic.

Now, it's often easy to prove that a system is deterministic: you just need to examine the rules by which it works. Roughly speaking, if the rules have no ambiguity about transitions from one state to the next, that system must be deterministic.

However, just because I can show the rules have no ambiguity, that does not mean I can easily predict what a system will do. In fact, it is *also* possible to construct deterministic machines, and prove that the fastest way to predict the machine's future states is to run the machine.

So, in a deep sense, these machines are *not* predictable: the only way to see what the machine will do is to run the machine.

If you were to re-start "me" with the same initial conditions, I would also unfold in exactly the same way that I have. But neither you, me nor anybody else can *predict* what I'm going to do: we all just have to watch and see!

Regarding quantum mechanics, I've developed an opinion that the probabilitic nature of that model will someday be shown to be an artifact of a deeper, and deterministic, set of rules.

I hardly deserve to have an opinion on such things, but nobody can stop me.

[bemildred]

14. Two comments:

"Deterministic is probably best defined this way: If a system always runs in exactly the same way given the same starting-conditions, then that system is deterministic."

The Achilles Heel here is the "exact" part. This is a fiction.
There is only "approximate", so any "exact" repetition based on
"exactly" the same starting conditions is a hypothetical ideal,
i.e. a matter of belief, not observation. You can postulate such an
exact system, but can only observe approximations, that is inexactness.

In the world of the intellect we are free to explore these "well
defined" systems and to posit dimensionless points and mathematical
exactitudes, but in the messy world of observation that is not what
we see, and reason demands that belief be put to the test of observation.

"I hardly deserve to have an opinion on such things, but nobody can
stop me."

Indeed, and I would not want to, and I trust you feel the same with
regard to my heresies.

[phantom power]

15. Yes, measurement errors make it hard to address scientifically

One reason I like harp on this topic is that many people who think about these questions (not necessarily yourself) appear to slip into the following fallacy: "The world is unpredictable, and so there must be some kind of randomness underlying it all"

It's important to understand that's not necessarily true. Even if the world is deeply deterministic, it would still appear just as unpredictable to us. Equally important, no amount of measurement precision could remove that unpredictability; any system with as many moving parts as the universe will certainly be computationally-irreducible.

The universe can be both clock-work, *and* unpredictable, interesting, etc.

Now, the huge success of quantum mechanics is a far stronger argument for some kind of underlying randomness, I just suspect it's not the final word.

My new favorite dark horse is a physics based on graph-automata, a la Wolfram's pet project.

[bemildred]

16. The world seems quite orderly, and runs just fine whether

we pay attention or not, so I think we agree. What I object to is
the hubris of thinking we've got a good handle on it and that it's
"really very simple, at bottom". We don't and it isn't, it's much
better and more interesting than that.

I have sometimes wondered if the "real numbers" were named that as
a sort of PR ploy to make them better accepted.

I have been of the opinion that the world is "massively parallel" for
some time, I used to work in simulations and it kept coming up, so
I think Wolfram's work is the most promising avenue open at present,
though still in a very early stage. It seems most like how things
actually work, reality is local, and everything goes on at once based
what's happening locally.

[bemildred]

8. One last note.

This is more interesting in the context of things like Conway's
"The Game of Life" and Wolfram's cellular automata. You could
program a colony of artificial ants at the per-ant level, or
design nanobots to do some common task in your liver.

http://www.bitstorm.org/gameoflife/

http://www.wolframscience.com/nksonline/toc.html

[papau]

9. Thanks for the links - and for the record - WE AGREE!!! - :-)

:toast:

:-)

[bemildred]

12. I expect we disagree less than you might think.

:toast: