This is an exposition of some of the main ideas in the paper Robust Cooperation. My goal is to make the ideas and proofs seem natural and intuitive - instead of some mysterious thing where we invoke Löb's theorem at the right place and the agents magically cooperate. Also I hope it is accessible to people without a math or CS background. Be warned, it is pretty cheesy ok.

 

---

 

In a small quirky town, far away from other cities or towns, the most exciting event is a game called (for historical reasons) The Prisoner's Dilemma. Everyone comes out to watch the big tournament at the end of Summer, and you (Alice) are especially excited because this year it will be your first time playing in the tournament! So you've been thinking of ways to make sure that you can do well.

 

The way the game works is this: Each player can choose to cooperate or defect with the other player. If you both cooperate, then you get two points each. If one of you defects, then that player will get three points, and the other player won't get any points. But if you both defect, then you each get only one point. You have to make your decisions separately, without communicating with each other - however, everyone is required to register the algorithm they will be using before the tournament, and you can look at the other player's algorithm if you want to. You also are allowed to use some outside help in your algorithm. 

Now if you were a newcomer, you might think that no matter what the other player does, you can always do better by defecting. So the best strategy must be to always defect! Of course, you know better, if everyone tried that strategy, then they would end up defecting against each other, which is a shame since they would both be better off if they had just cooperated. 

But how can you do better? You have to be able to describe your algorithm in order to play. You have a few ideas, and you'll be playing some practice rounds with your friend Bob soon, so you can try them out before the actual tournament. 

Your first plan:

I'll cooperate with Bob if I can tell from his algorithm that he'll cooperate with me. Otherwise I'll defect. 

For your first try, you'll just run Bob's algorithm and see if he cooperates. But there's a problem - if Bob tries the same strategy, he'll have to run your algorithm, which will run his algorithm again, and so on into an infinite loop!

So you'll have to be a bit more clever than that... luckily you know a guy, Shady, who is good at these kinds of problems. 

 

---

 

You call up Shady, and while you are waiting for him to come over, you remember some advice your dad Löb gave you. 

(Löb's theorem) "If someone says you can trust them on X, well then they'll just tell you X." 

If  (someone tells you If [I tell you] X, then X is true)

Then  (someone tells you X is true)

(See The Cartoon Guide to Löb's Theorem[pdf] for a nice proof of this)

Here's an example:

Sketchy watch salesman: Hey, if I tell you these watches are genuine then they are genuine!

You: Ok... so are these watches genuine?

Sketchy watch salesman: Of course!

It's a good thing to remember when you might have to trust someone. If someone you already trust tells you you can trust them on something, then you know that something must be true. 

On the other hand, if someone says you can always trust them, well that's pretty suspicious... If they say you can trust them on everything, that means that they will never tell you a lie - which is logically equivalent to them saying that if they were to tell you a lie, then that lie must be true. So by Löb's theorem, they will lie to you. (Gödel's second incompleteness theorem)

 

---

 

Despite his name, you actually trust Shady quite a bit. He's never told you or anyone else anything that didn't end up being true. And he's careful not to make any suspiciously strong claims about his honesty.

So your new plan is to ask Shady if Bob will cooperate with you. If so, then you will cooperate. Otherwise, defect. (FairBot)

It's game time! You look at Bob's algorithm, and it turns out he picked the exact same algorithm! He's going to ask Shady if you will cooperate with him. Well, the first step is to ask Shady, "will Bob cooperate with me?" 

Shady looks at Bob's algorithm and sees that if Shady says you cooperate, then Bob cooperates. He looks at your algorithm and sees that if Shady says Bob cooperates, then you cooperate. Combining these, he sees that if he says you both cooperate, then both of you will cooperate. So he tells you that you will both cooperate (your dad was right!)

Let A stand for "Alice cooperates with Bob" and B stand for "Bob cooperates with Alice".

From looking at the algorithms,  and . 

So combining these, .

Then by Löb's theorem, .

Since that means that Bob will cooperate, you decide to actually cooperate. 

Bob goes through an analagous thought process, and also decides to cooperate. So you cooperate with each other on the prisoner's dilemma! Yay!

 

---

 

That night, you go home and remark, "it's really lucky we both ended up using Shady to help us, otherwise that wouldn't have worked..."

Your dad interjects, "Actually, it doesn't matter - as long as they were both smart enough to count, it would work. This  doesn't just say 'I tell you X', it's stronger than that - it actually says 'Anyone who knows basic arithmetic will tell you X'. So as long as they both know a little arithmetic, it will still work - even if one of them is pro-axiom-of-choice, and the other is pro-axiom-of-life. The cooperation is robust." That's really cool! 

But there's another issue you think of. Sometimes, just to be tricky, the tournament organizers will set up a game where you have to play against a rock. Yes, literally just a rock that holding the cooperate button down. If you played against a rock with your current algorithm, well you start by asking Shady if the rock will cooperate with you. Shady is like, "well yeah, duh." So then you cooperate too. But you could have gotten three points by defecting! You're missing out on a totally free point! 

You think that it would be a good idea to make sure the other player isn't a complete idiot before you cooperate with them. How can you check? Well, let's see if they would cooperate with a rock placed on the defect button (affectionately known as 'DefectRock'). If they know better than that, and they will cooperate with you, then you will cooperate with them. 

 

---

 

The next morning, you excitedly tell Shady about your new plan. "It will be like before, except this time, I also ask you if the other player will cooperate with DefectRock! If they are dumb enough to do that, then I'll just defect. That way, I can still cooperate with other people who use algorithms like this one, or the one from before, but I can also defect and get that extra point when there's just a rock on cooperate."

Shady get's an awkward look on his face, "Sorry, but I can't do that... or at least it wouldn't work out the way you're thinking. Let's say you're playing against Bob, who is still using the old algorithm. You want to know if Bob will cooperate with DefectRock, so I have to check and see if I'll tell Bob that DefectRock will cooperate with him. I would have say I would never tell Bob that DefectRock will cooperate with him. But by Löb's theorem, that means I would tell you this obvious lie! So that isn't gonna work."

Notation,  if X cooperates with Y in the prisoner's dilemma (or = D if not). 

You ask Shady, does ?

Bob's algorithm:  only if .

So to say , we would need . 

This is equivalent to , since  is an obvious lie. 

By Löb's theorem, , which is a lie. 

<Extra credit: does the fact that Shady is the one explaining this mean you can't trust him?>

<Extra extra credit: find and fix the minor technical error in the above argument.>

Shady sees the dismayed look on your face and adds, "...but, I know a guy who can vouch for me, and I think maybe that could make your new algorithm work."

So Shady calls his friend T over, and you work out the new details. You ask Shady if Bob will cooperate with you, and you ask T if Bob will cooperate with DefectRock. So T looks at Bob's algorithm, which asks Shady if DefectRock will cooperate with him. Shady, of course, says no. So T sees that Bob will defect against DefectRock, and lets you know. Like before, Shady tells you Bob will cooperate with you, and thus you decide to cooperate! And like before, Bob decides to cooperate with you, so you both cooperate! Awesome! (PrudentBot)

If Bob is using your new algorithm, you can see that the same argument goes through mostly unchanged, and that you will still cooperate! And against a rock on cooperate, T will tell you that it will cooperate with DefectRock, so you can defect and get that extra point! This is really great!!

 

---

 

(ok now it's time for the really cheesy ending)

It's finally time for the tournament. You have a really good feeling about your algorithm, and you do really well! Your dad is in the audience cheering for you, with a really proud look on his face. You tell your friend Bob about your new algorithm so that he can also get that extra point sometimes, and you end up tying for first place with him!

A few weeks later, Bob asks you out, and you two start dating. Being able to cooperate with each other robustly is a good start to a healthy relationship, and you live happily ever after! 

The End.

Discussion article for the meetup : Atlanta Meetup: Self Deception

Discussion article for the meetup : Atlanta Meetup: Self Deception

Discussion article for the meetup : MIRIxAtlanta: 19 July 2014

Discussion article for the meetup : MIRIxAtlanta: 19 July 2014

Discussion article for the meetup : Atlanta Movie Night: Introduction to Machine Learning

Discussion article for the meetup : Atlanta Movie Night: Introduction to Machine Learning

Discussion article for the meetup : Atlanta June meetup - Hacking Motivation

Discussion article for the meetup : Atlanta June meetup - Hacking Motivation

Inspired by: On learning difficult things

In his recent post, user So8res says his number one piece of advice for learning something difficult is to have study partner to learn with you. 

Since there is a decent amount of interest here in going through the MIRI course list, it might be worth finding other people here to learn and study this with, and to form pairs or groups. 

So here is a space for finding and organizing such partnerships!

---

Of course, part of the reason I wrote this is because I am interested in learning these books with people. My background: I'm currently a second year Ph.D. student in mathematics (number theory). I'm still pretty new to the type of math emphasized here. I have Probabilistic Graphical Models, Category Theory for Computer Scientists and The Logic of Provability (by George Boolos -- not on the course list, but good to get background for the Robust Cooperation paper and for understanding Loeb's theorem) all lying around. I'm also taking a class on numerical analysis. Part of my problem is that I start lots of projects and then end up fizzling out on them, and I hope having a partner will help with this. 

I've already been going through MIRI's publications with a friend from the local LW community, which has been really nice. I'm still interested in finding more partners <insert poly joke here> for going through books on the course list specifically. I'm also willing to explain things I understand, or let someone explain things to me (I've found that explaining things to someone else is a very good way of solidifying your understanding of something) when I have time. 

---

Some things to consider:

• What is the best online format for doing this? I've been doing this sort of thing with Workflowy + Mathflowy but there is probably something better. 
• Does a pair dynamic, or a group dynamic seem more likely to work? I'm hoping that there can be a collection of pairs all centered in a common community, or something like that.
• If a central community seems like a good idea, how should it be centralized?
• Probably some other issues/meta stuff.

 

Recently, issues with the way open threads currently work were brought up. Open threads aren't very visible and get crowded with comments quickly. This causes people to post things that belong in open threads in r/discussion, to not post in open threads more than a few days old, or to ignore/be unaware of new comments in open threads. I think we can do better.

Some possible solutions that were pointed out, or that I thought of are:

• Put the most recent open thread at the top of the 'Recent Comments' sidebar.
• Having open threads more often.
• Put a link to it on the main page.
• Make a new subreddit for open threads.
• Create a new medium for open threads.

Note that not all of these are orthogonal.

Having them more often has the advantage of being especially easy to implement. Adding new links seems to be relatively easy to implement as well. As far as I know, making a new subreddit isn't too difficult, but making a new medium would probably be a waste of development resources.

Personally, I like the idea of having a new subreddit for open threads. It  would increase visibility, not get overcrowded, and have the right atmosphere for a casual open thread. My evidence for believing this comes from being familiar the way Reddit works. It seems like there is some resistance to creating new subreddits here, so I don't expect this to be implemented. I would like to see the reasoning for this attitude, if it indeed exists.

 

There are similar issues for the repository threads. For repositories, having them more often defeats the purpose of having one place for a certain type of idea, and a different subreddit doesn't seem right either. Giving them their own wiki pages might be a better medium, with new threads to encourage new ideas every once in a while. The main problem for this is the trivial inconvenience of going to the wiki, and logging in. It would be nice if there was a unified log-in for this part of the site and the wiki, but I realize this may be technically difficult. I might organize a wiki page for some of the repositories myself if people think this is a good idea but no one else feels like doing it (depends on if I feel like doing it too :p ).

Thoughts?