[APPLAUSE] MARC DONNER: I’m not

the speaker. I’m just the introducer. So I’m Marc Donner. I’m an engineering director here

in the New York office. It’s my distinct pleasure and

honor to introduce Joe Halpern, who’s the head of the

CS department at Cornell. He started off as an honest

mathematician and then fell into computer science, sort

of the way many of the rest of us did. Over the course of years, he’s

done very many interesting things, including teaching

mathematics in Ghana for two years. But I’ll let him tell the

rest of the story. He’s going to talk tonight

about scrip systems– not script, scrip. So funny money to you, or

something on that order. But there’s lots of them around,

and I will let him tell the story. Joe. [APPLAUSE] JOSEPH HALPERN: Can you

hear me back there? OK. So the rules of the game are,

do not wait until the end to ask questions. Ask them whenever you feel

like asking them. If I think it’s inappropriate,

or it makes more sense to wait until the end, I’m in charge. I’ll tell you to wait. So this is joint work with Ian

Kash, who was my student. He’s at Microsoft in

Cambridge, England. And Eric Freedman, who’s

is now [INAUDIBLE]. He was at Cornell. So as Mark said, scrip

is funny money. It’s all over the

place, actually. You can think, as Marc

pointed out– oh, how’d I get to the end? Scrip has been widely used. I’ll explain the Babysitting

Co-op story. That’s coming up. It’s used in systems like Karma

and Brownie Points and Dandelion and AntFarm. So these are all computer

systems, so are the following– Agoric, Mariposa, Yootles,

Mirage, Egg. So here, they’ve been used

to prevent free riding– I’ll explain that– and for resource allocation. But they’re also used

in the real world. Think of airline miles. They’re scrip, right? It’s a way of keeping track of

things, which you can use to get free trips and

other things. In Ithaca, we have Ithaca Hours,

which is scrip money that you can use to pay

some businesses. It can be very effective,

because you can think of scrip as a market mechanism. And they “can yield orderly

systems beyond the ability of any individual to plan,

implement, or understand.” So this is saying, basically, the

market is a good thing. But they are far from perfect. So we wanted to understand

scrip systems. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: They’re sort

on the border of scrip and real money. So I mean, this isn’t a talk

on what is really scrip. But I think to some extent,

they share some of the features of scrip. So let me explain the Capitol

Hill Babysitting Co-op story. This is a story that

I read about in an article by Paul Krugman. Yes, Nobel Prize winning

Paul Krugman. But there is a journal article

in an econ journal that his article is based on. So the story goes like this. A bunch of yuppies in Washington

all had kids. And they decided they would

form a babysitting co-op. They would babysit

for each other. High tech. And so of course, they didn’t

want to pay each other. But somehow, they wanted to

keep track of who was babysitting, because they

didn’t want free riding. They didn’t want it to be the

case that, gee, people babysat for me 20 times. And I never babysat

for anybody else. So the way they did it

is they had tokens. Tokens are scrip. So everybody had some tokens. And if you wanted somebody to

babysit for you, you had to give them a token. And you got a token when you

babysat for someone else. So think of this scrip as

functioning like bookkeeping. It had no value in the

outside world. It was just a system

of tokens. Now, what was interesting is at

the beginning, the system worked terribly. Nobody was going out. Everybody was staying home. We have this great system. How come nobody is going out? So these were Washington

yuppies, right? So they legislate it. You have to go out. It’s good for you. Go out at least once a month. Get out of the house. Didn’t work. Then they brought in a bright,

young economist, said, your problem is you haven’t got

enough tokens in the system. So they printed more tokens. Worked like a charm. People started going out. They said, well, gee, if

printing some tokens is good, it’s got to be even better

to print more tokens. They printed more tokens. Yes, Washington. The system crashed. Nobody went out anymore. OK, time out. So think about, why did nobody

go out at the beginning? And why did people stop

going out when they printed more tokens? Any intuitions here? Everybody is afraid

of running out. If you’ve only got one

or two tokens– of course, if you have zero

tokens, you can’t go out, because if you don’t have a

token, you can’t get somebody to babysit for you. That’s the whole point. And if you only have one or two,

you might be wondering, well gee, what happens if my

mom gets sick, and I really need to go out? Or there’s some special

occasion? So it’s clear if there are very

few tokens in the system, people are afraid of going out

because they’re worried about running out of scrip. Now, what’s the problem

when they printed a whole bunch of scrip? What went wrong then? Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Yeah, so

let’s make precise why they don’t have any– you’re right. They don’t have any value. Why don’t we have any value? What’s some intuition? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Sorry? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: There’s

a lot of them. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: They don’t

want to babysit anymore. They don’t need any more. That’s exactly right. In other words, if everybody has

20 tokens, they say, why the hell do I need to go babysit

for somebody else? 20 tokens? So there’s no problem. I’m happy to go out. I’ve got 20 tokens. But I don’t have anybody who

wants to babysit for me, because everyone else

has 20 tokens, too. And they would say they

don’t need a 21st. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: OK, so

in our framework, and also in this story– which, by the way, was based

in a real-life situation. There really was a Washington

Babysitting Co-op. There’s no auctions, right? So it’s not you can say,

OK, I’ll pay you three tokens to babysit. So throughout this talk– I’ll mention this again at the

end, because I think it’s an interesting research

question here– you have to assume that the

price of a job is fixed, one token per job. No bargaining, no

side payments. That’s the market. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Regardless. There’s no inflation, no

nothing, although I’ll talk about that, too. OK, so that’s where

we came in. We wanted to understand. Now, why do we want

to understand? What was the research question

to us as computer scientists? What’s the right amount of money

to pump into the system? What’s the right amount of scrip

to pump into the system? Well, if you say, well,

too little is bad. Too much is bad. Now, too little is bad because

if people don’t have enough. They’re worried they’re

going to run out. Too much is bad because

everybody has too much. They don’t way to babysit. Well, what’s the sweet

spot in the middle? We wanted to understand that. OK, so that was our technical

question. Are we all together? So now I’m going to have some

technical slides, which I hope I can explain well. But you understand that’s

our motivation. That’s what we want to do. Oh, sorry. Let’s do this again. So our approach, we wanted to

develop a microeconomic model. Think game theory. I’m coming at it from the point

of view of game theory. I’ll explain all of this. And I want to try to figure out

what the optimal behavior is for agents in that model. What’s the right thing to do if

you’re rational and smart, understand how the

system works? What should you do? I want to show there’s a stable

outcome that’s a Nash equilibrium. I’ll explain what Nash

equilibrium is. In fact, let me explain

it now. So this is game theory. So how many people don’t know

what Nash equilibrium is? It’s OK if you don’t know. So let me explain. So have you heard of the

movie “A Beautiful Mind?” John Nash, right? He got a Nobel Prize. This is what he got

the prize for. It was his Ph.D. thesis,

by the way. So in game theory, the point

is we have a bunch of strategic agents. They all have a strategy. Strategy is just what

you’re going to do in every situation. Now, we’re going to say a

collection of strategies is an equilibrium– is a Nash equilibrium. If everybody is best responding

given what everybody else is doing, that

even if I know what all the rest of you are doing, I have

no motivation to do anything else other than what

I’m doing. So fix a strategy

for everybody. We’re going to say that set of

strategies, that collection of strategies, is a Nash

equilibrium if even if you knew what everybody else was

doing, you would have no temptation to change what

you were doing. That’s a Nash equilibrium. It’s a stable situation because

nobody wants to change what they’re doing. It’s not necessarily

a good situation. You might be totally

unhappy with the equilibrium you’re in. But nevertheless, you can’t

do better by unilaterally changing to something else. So we’re trying to understand. And a Nash equilibrium

isn’t perfect. I could give a whole other talk

on problems with Nash equilibrium and ways

to get around it. But that’s not this talk. It is the case that in many

situations of interest, especially people really

understand the system, where what they end up doing is

playing a Nash equilibrium. So we wanted to understand

Nash equilibria in this setting with scrip systems. Are we together? That’s the goal. And we wanted to use the

understanding to maybe tell system designers how to

build better systems. So here’s the formal model. It’s not as bad as it looks. So let me explain

it intuitively. This is some of the math

you’re going to get. But I’ll try to make it easy. So our pictures, we’ve got

a bunch of agents in. And for the purposes of this

slide, let me assume that all agents are the same. And I’ll explain in what

ways they’re the same. So in each round, one

agent is chosen randomly to make a request. What I mean by make a request,

you need babysitting. So I’m going to assume that the

need for babysitting comes from the outside. It’s not something you’re

planning strategically. You wake up one morning. You read in the paper

great movie playing. I want to go out, right? So I want babysitting tonight. So nature chooses somebody at

random to need something, to want babysitting. So think in terms

of babysitting. Now in our general model,

we assume that there are different types of players. So some players, if you like,

are needier than others. So if you like, what this is

assuming is everybody’s equally likely to want

babysitting. But you can imagine some

people tend to want babysitting more than others. They like going out. That’s OK. We allow that in the

general model. But for this talk, let

me not assume that. Now, the one strategic choice

you have is if I say, look, I need some babysitting,

who’s willing to babysit for me tonight? Raise your hands. That’s a strategic choice. You might decide, I’m not

interested in babysitting. Why might you say I’m

not interested? It’s because I have 20 tokens. I don’t really want a 21st. So you have to decide whether

or not you want to babysit. Well, once you’ve decided, out

of all the people who raised their hands that said, I’m

willing to babysit, I’m going to choose one at random. Now again, in our general model,

we assume that the choice isn’t necessarily

totally random. You could imagine some people

advertise better than others. So if you’ve got good

advertising, you’re more likely to be chosen than

somebody who’s a lousy advertiser, or their

reputation effects. But for the purposes of this

talk, just to simplify things, let’s assume you’re

chosen at random. Everybody’s equally likely

to get chosen. Now, the rest of it is

the obvious thing. When the person who makes the

request gives one token to the other person– so think of a

token as being $1, but it’s funny money, scrip– and you get one unit

of utility. Utility, think of it as a

measure of happiness. So the person who gets the

babysitting done gets one unit of utility, and the person

who does the babysitting and pays $1– so dollars and utilities

are not the same. The tokens are just

bookkeeping. What you really care

about is happiness. So you get one unit of

happiness if you get babysitting done for you. You lose alpha units of

happiness if you do babysitting. And we’re going to assume that

alpha is a lot less than one. Otherwise, the system would

never get off the ground. If the amount of unhappiness

you incurred by babysitting was more than the amount of

happiness you were going to get by having somebody babysit

for you, of course you’d never babysit, right? Because all you’re getting is

a token, and the token buys you babysitting in the future. So babysitting isn’t worth the

pain of doing babysitting, you’d never do it, right? So we’re going to assume that

you get one unit of happiness if you babysit, and you lose

alpha units of happiness doing the babysitting. But alpha’s a lot

less than one. Everybody else breaks even. And of course, the person who

asks to have the babysitting done has to pay $1 to the

person who does the babysitting. But the dollar has nothing

to do with happiness. Think of it simply

as bookkeeping. It’s a token. And the other thing we’re

going to assume is that there’s what’s called

discounting. So a unit of happiness tomorrow

is not as good as a unit of happiness today. So I’ll pay you back on Tuesday

for the dollar you’re giving me today. They dollar’s actually worth

less on Tuesday than it’s worth today. So we’re assuming– so technically, we have a

discount factor delta. Think of delta as being less

than one but close to one. So $1 today is worth delta

dollars tomorrow. So think of delta as 0.9, delta

squared the next day, delta cubed the day after that,

delta to the fourth the day after that. Question? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So yeah, I’m

told to repeat questions. And the question is, why do

I assume a delta at all? So if you don’t want

to assume that– and we’re going to think of

this– think of delta as being very, very close to 1. But in fact, it seems that in

real life, people act as if there’s a delta less than 1,

that getting something today is better than getting the

same thing tomorrow. So this seems to be a real

psychological phenomenon. It’s not like we made it up. Now, in fact, for our results,

we need to assume that n is relatively large, although it

turns out 100 is good enough, as a practical matter. And delta is pretty

close to 1. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So the

question is, is this independent of a termination

effect? So in this world, there’s

no termination. People live forever. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Stay tuned. You’ll see what the results

are saying. Think of me as the

system designer. This is the total utility

for an agent. So this is saying for each

round r, look at how much utility you get in round r,

which is either 0 or 1 or negative alpha. Those are the only possible

utility quantities. If you get babysitting

done for you in round r, then uir is 1. If you do babysitting for

somebody in round r, uir is negative alpha. And if you don’t babysit

or get babysitting done, this is 0. And the delta of the r just says

something 10 rounds out, you multiply by delta

to the 10th. So this is your total utility. For me, the system designer,

what I care about is maximizing social welfare. The social welfare is just

going to be the sum of everybody’s utility. I want everybody to be

as happy as possible. I want to design a system where

I’m going to have very high total utility. Are we together? So I just add everybody’s

utility. Here, I’m weighting everybody

the same way. And of course, I’m going to

maximize total utility– just sort of keep this in the back of

your mind– by making sure that whenever somebody wants

babysitting done, they’ll have a token to pay for it. And I’ll have somebody who’s

willing to do babysitting. So again, think of

the Washington Babysitting Co-op story. So there are two things

that can go wrong. If there are very few tokens–

if you’ve got a system of 10,000 people and you have 100

tokens, and it’s clear that most people most the time

don’t have a token, bad. Bad from the point of view of a

system designer who wants to maximize social welfare because

if you don’t have very many tokens, even if you have

10,000 people and 20,000 tokens, there’s a non-trivial

chance somebody won’t have a token. Just look at fluctuations. So I want a job done. I don’t have a token. I’m unhappy. I could have been happier

if I had a token to pay for it, right? Conversely, if I want a job

done and there’s lots of tokens floating around,

intuitively– I haven’t said why yet– but

nobody’s going to volunteer. I’m also unhappy. I have lots of money to pay for

you, but nobody is raising their hand. So I want to maximize two

prob– and as you’ll see later, what’s going to happen

is too few tokens in the system will be bad for social

welfare, because a lot of times when somebody wants a job

done, they won’t have a token to pay for it. Too many tokens in the system

will be bad for social welfare, because a lot of times

when somebody wants a job done, nobody will

raise their hands. Question? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: OK. So again, I’ll repeat. So the question was, they could

start asking for five tokens for babysitting

rather than one. I’m not allowing that. So in this system,

prices are fixed. Now, again, it’s very

interesting to ask what happens if you allow markets,

where you can say, look, how much are you willing to

bid for this job? I won’t do it for one, but maybe

I’ll do it for three. So we’re not allowing that. Again, I claim this is

quite realistic. There are many markets in the

world where prices are fixed. Certainly, in Ithaca, where I

live, they have Ithaca Hours. There are fixed prices for

things that are posted. Think of all the things that

you’re aware of in the world where there are fixed,

posted prices. Now, I understand there’s other

situations where there’s bargaining. But bargaining incurs

overhead. So customers and producers like

it much better when there are fixed prices, again, as

an empirical statement. So again, this is Google. Google works by bids

and market design. I understand that. And it’s very interesting to ask

how things would change in this framework if we

allowed bidding. But let me at least claim there

are lots of real-world scenarios where there are

fixed, posted prices. So it’s not like we’re making

up something that never happens in the real world. And as a technical matter, what

I’m about to tell you in this talk says nothing about

what happens when there’s auctions for goods, although

I’ll come back to that at the end. Questions? Yeah. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So the question

was, are my results robust under a no-trade negative

utility penalty? Except I don’t understand

what that is. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Well,

the utilities are just what I have there. So your utility is either

0, negative alpha, or 1 in each round. And there’s nothing hidden. That’s the utility. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So think of

social welfare as overall happiness, which is literally

defined as the sum of everybody’s utility. So this is the utility for

a particular agent, i. So 10,000 agents, each one

has their utility. Just add them all up. That’s social welfare,

by definition. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So the question

is, is this situation going to result in a situation

where a few people do all the work? In fact, not just in practice,

we can prove theoretically, no. Things will be quite uniform. But stay tuned. Let me get to technical

results. So I think at this point,

I will stop questions and keep going. So our assumptions–

so let me repeat. I was saying this before. For ease of exposition, and this

is not we assume in the full paper, I’ve assumed that

agents are homogeneous in the following sense. They have the same cost, alpha,

for performing work. And of course, in the real

world, that might be true. But in many cases,

it might not. So I might love babysitting

your kids. My cost for babysitting

your kids is very low. Or I might hate babysitting

you kids. They’re real brats. And the cost would be high. So there’s no reason to assume

that all agents– some people love babysitting. Some people hate it. I’ve assumed that everybody has

the same probability of being chosen if a volunteer. So among the people

who raise their hands, I choose at random. So everybody is equally

likely. I don’t have to assume that. I’ve assumed that everybody

gets the same utility for having a job done. Of course, in the real

world, I might love going out to a movie. Movies are good, but

I don’t mind staying at home and reading. I’ve assumed everybody uses

the same discount factor. Think of discount factor as

measuring your patience. So roughly speaking, it’s

saying, how patient are you? If you get $1 today, but you’re

not going to be able to use it for three weeks,

are you OK with that? So your discount factor

is between 0 and 1. I’m going to assume that people

are pretty patient. Discount factor is close to 1. But a discount factor that’s

close to 0 is saying, hey, if I don’t get to spend my money

right away– think of my kids when they were young– it’s not good for anything. So money two days from now

is basically worthless. So you think of a discount

factor like a quarter. So a dollar today is work,

like, 1/16 of a dollar tomorrow and 1/64 of a dollar

three days from now, pretty close to 0. So if you’re very impatient,

your discount factor is close to 0. If you’re very patient, your

discount factor is very close to 1. Are we together? That’s the technical content. So again, I’m assuming

that everybody has the same time factor. That might not be true. And in our general model, we

have what economists call different types of agent, where

a pipe is characterized by their alpha, the probability

of being chosen. All these five factors,

we have a number for each of them. And that tuple of five numbers

characterizes an agent. And again, let me repeat. I said it three times,

I think. The price of a job is fixed. So there’s been other work, some

of it based on our work. So Hens et al did their

work independently. They’re economists. A slightly different model. They said that there was no

cost for volunteering. That is, babysitting

is no pain at all. But they assumed that agency

utilities change over time. We don’t. And they assumed that agents

choose whether to provide service, request service,

or opt out. So they have a slightly

different model. But again, they’re investigating

scrip systems. Aperjis and Johari actually had

a paper that followed onto ours, but their focus was on

finding equilibrium prices, which ours isn’t. But I’m a being [INAUDIBLE],

telling you about other work. So back to what we were doing. We’re interested in what seems

to be the most natural kind of strategy, which is that

you have a threshold. And the way to think about the

threshold, so suppose my threshold is $7. Why should I work? Under what circumstances

will I work? What’s the intuition? So again, let me ask you, to

make sure that we’re all on the same page here. What would induce you to raise

your hand if somebody says, I need a babysitter? Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: You know you

have something coming up? Well, in this model,

you don’t. Because remember, you’re

chosen at random. But you can figure out the

probability that you’ll have something coming up. But why might one person be

more likely to raise their hand than another? Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Yeah,

less tokens, right? So basically, the intuition

is, if you have very few tokens, you’re nervous. Why are you nervous? So suppose you have

two tokens. You’re nervous that you might

want something three times in a row before you get

a chance to– I mean, raising your hand

doesn’t guarantee that you’re going to get work, right? Raising your hand just says, I

am one of the 25 people who raised their hand. I have a probability 1 over

25 of being chosen. So intuitively, you volunteer

for a job if you feel like you’re running low, whatever

that means. And that’s what we’re going

to be talking about. At what point do I start

getting nervous? When do I start feeling

like I’m running low? And if you feel like you have

a lot of money, you don’t raise your hand. So that’s the way

you’re thinking. You’re following a threshold

strategy. So a threshold strategy says,

I have a threshold, let’s say, of $7. And what that means is if I

have a less– or 7 tokens. If I have less than 7

tokens, I volunteer. If I have 7 or more, I don’t. Are we together? That seems like the most

natural strategy. You have some fixed threshold. Very easy to implement,

obviously, in a computer system. You have some fixed threshold

that says, below that I raise my hand. Above that, I don’t. That’s a threshold strategy. Oh, I did it again. Two buttons– better human factors. So why do I want to satisfy

stuff, and why don’t I? This is just an argument

for thresholds. If I have lots of money,

I don’t raise my hand. If I’m running short,

I do raise my hand. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Right. So the question is, do

all the agents have prior independent alphas? And the answer is, they all

have the same alpha. In the general model,

they don’t. So in the general model, part of

your type or personality is your alpha. And we allow for finitely

many types. There could be a very large

number of agents, but there might be seven types

of agents. So your type is characterized

by five numbers. One of them is the alpha. So your second question was,

what about auctions? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So the question

is, do they have insight into the success

of prior auctions? In a precise sense, as we’ll

see, they don’t have to. So the answer is,

it’s irrelevant. But let me make that precise. OK, so everybody understands

the threshold strategy? You understand why it’s the

obvious thing to do? So threshold strategy, let me

call it Sk, is a volunteer if I have less than k dollars. So think of k as your

comfort level. And so the question we’re asking

technically is, is it reasonable– [PHONE RINGING] JOSEPH HALPERN: Ah,

not my phone. Your phone. So I feel like the airline

pilot that says everybody should turn off their

cell phones. So is it reasonable to play a

threshold strategy, and how does the system behave

if everyone plays a threshold strategy? The way we’re going to formalize

that, we’re going to prove that there’s a Nash

equilibrium where everybody plays a threshold strategy. Actually, there’s an easy Nash

equilibrium where everybody plays a threshold strategy. That’s where everybody plays the

threshold strategy of 0. A threshold strategy of 0 says

you never volunteer, because you volunteer if you have less

than $0, and you’ll never have less than $0. So that’s a threshold strategy

where k is 0. That’s a special case,

where k is 0. And I claim if everybody plays

the strategy S0, which is never volunteer, that’s

an equilibrium. Why is it an equilibrium? Well, I claim if none of you are

ever going to volunteer, the best thing for me to

do is not to volunteer. Why should I volunteer? Well, if I volunteer,

you will happily– so if you need babysitting, if

I say, OK, yes, I’m going to do it, you say, great,

I’ll take you. Babysit. Here’s a token. OK, now you have a token. What can you do with a token? Well, next time you want

babysitting, you say, oh, who wants to volunteer? But all the rest of you are

never volunteering. What good is my token doing? So clearly, if everybody else

is following the strategy of never volunteer, my best

response is never volunteer. So there is a Nash equilibrium

where nobody ever volunteers. That’s obviously not

very interesting. So we’re interested in the

question of, is there a non-trivial equilibrium at

threshold k where everybody plays k, and they’re happy with

that, and k is not 0? And how does it behave? And you’ll see it does very

interesting things. So you had asked, do you know

what other people are doing and the successive– let me sort of start addressing

that question. So here are some technical

stuff. So bear with me a few seconds. I think I can explain this, and

there isn’t that much of it, anyway. But I think it’s sort of cool. So out of curiosity, how

many people have heard of maximum entropy? Even if you don’t know what it

is, how many people have at least heard of it? A fair number of you. OK. So it turns out that

I’ll explain it. I don’t assume you know it. The maximum entropy

characterizes the distribution of money in the system. And knowing that, we can use

that to prove that there is not technically a Nash

equilibrium but an epsilon Nash equilibrium. So a Nash equilibrium says,

given what everybody else is doing, what I’m doing is

the best response. Epsilon says, what I’m doing is

the best response to within a very small epsilon. Like, there might be something

I could do that’s better. But it can’t be more–

think of epsilon as being, like, 0.001. It’s not going to be more

than epsilon better. So if I don’t want to spend

hours thinking about what’s the best thing to do, I’m happy

with just playing my threshold strategy. Well, maybe out there, there’s

something a bit better, but it’s not going to

be a lot better. You can make epsilon as small

as you want, as it happens. So I mentioned that it’s also

a Nash equilibrium if everybody plays a threshold of

0, never volunteering, but it’s not interesting. Now, here’s the interesting

thing for system designs. What we’re going to show is,

so no matter how much money there is in the system, there’s

an equilibrium. But, now it turns out as you

pump more and more money into the system– start at 0, pump

more money into the system– social welfare improves. So if you’re a system designer,

you want to pump more and more money into the

system up until a certain critical point. So again, going back to

Washington Babysitting Co-op story, you can see that

if you start with $0– that means nobody can ever do

any babysitting, because they have no tokens– putting more money into

the system, that increases social welfare. People are going

to be happier. They’re going to be able to pay

for babysitting until you get to a certain point where

there’s lots of money floating around in the system,

and nobody is going to want to volunteer. That’s the intuition,

but what we show is it’s a critical point. So things get better and better

and better and better until there is a crash. And it’s a sharp crash. It’s like you fall

off a cliff. So if you’re a system designer,

there’s sort of a magic amount of money. All that matters, it turns out,

is the average amount of money per person. So there’s a particular

number, like 7. If you’re a system designer,

independent of the number of people in the system, you want

to have an average of $7 per person in the system. You want to get as close

to that as you can. But if you have a little

bit more than that– so putting in more and more

money up until you get to $7 makes things better and

better and better. The total amount of happiness in

the system keeps increasing up until you get to

this cliff point. And then you fall off the cliff,

and then nobody’s ever going to volunteer anymore,

and people are extremely unhappy. No babysitting gets

done at all. So now, this assumes, of course,

that everybody’s totally rational. Now, of course, in the real

world, even if you totally understand this, not everybody’s

rational. So if I were a system designer,

I wouldn’t push my luck and go all the way

to 7 or even 6.999. You want to back off a bit. And I’ll talk about that

later in the talk. But this is the lesson for

system designers, that there is a magic number, which is the

average amount of money per person. And that’s what you

want to hit. Well, you don’t exactly

want to hit it. You probably, in the

real world, want to get fairly close. But you don’t want to

push your luck. But if you go over it, the

system will crash. Very bad. Crash in the sense of nobody

will ever volunteer. Are we together? So that’s what the mathematics

is telling us. They’ve actually observed this

phenomenon in the real world, I think in “Second

Life,” actually. If somebody knows more

about this– I mean, somebody mentioned

this to me after talk. “Second Life” is

a game, right? And apparently, this phenomenon

has been observed. So we can sort of simulate it. But it happens. OK, next few slides

are technical. Bear with me. If you’re totally

non-mathematical, it’s probably, maybe, a

time to tune out. But I will try to make it as

accessible as possible. And then we’ll get back to what

we learned from this. So formally, we can view this

system as what’s called a Markov chain. OK, how many people have

heard of Markov chains? Oh, fair number of you. OK, but I’ll try to make

sense of this. So a Markov chain consists of

a collection of states and transitions between states. So if you’re in this state,

you’ll move to another state with a certain probability. So think of it as what

we call a graph. So a bunch of nodes, and

nodes are the states. The states are connected by

edges, and the edges have probabilities on them. And the way to think about this,

if you’re at this node, you look at where the

edges are going. Each edge is labeled

with a number. That’s a probability. The sum of the numbers is 1. It says with a probability

1/3, you’re going here. With a probability 1/4, you’re

going here, and with a probability of, whatever,

about 5/12, you’re going over here. So each of the edges is labeled

with a number that’s a probability. That a Markov chain. So it doesn’t tell you exactly

what’s going to happen. You can sort of figure out

how likely is each path. If I’m here, I’m going

to go here. Then I’m going to go here. What’s the probability

of doing this? That’s a Markov chain. So what are the states? The states are just a tuple that

describes how much money each agent has. So imagine I’ve got 1,000

agents, and I’ve got $2,000 in the system, 2,000 tokens. A state just describes how those

2,000 tokens are split up between the agents. You’ve got three, you’ve

got two, you’ve got 27. You’re sitting there

with 300 of them. A bunch of people have zeros. OK, that’s a state. Who has how much money? Are we together? Now, if you’re in a certain

state, what’s the probability of moving to another state? Well, the only other state I

can move to, if I’m talking about tokens, is one person

gets one more token, and somebody else gets

one less token. That’s the only move that

I’m allowed, right? So if you have 300, and you need

babysitting done, and you volunteered, then one of your

300 is going over to him. You have 299, and you have

whatever you had plus one. Are we together? Those are the state transitions,

but there are lots of possible transitions,

because somebody is chosen at random. So everybody is equally likely

to be chosen to want babysitting. Now, I can’t tell you what the

transition function is until I tell you what strategy

everybody’s following. So suppose we fix everybody else

at following a threshold of 7, let’s say. Once I fix everybody else at

following a threshold of 7, then I could describe this

as a Markov chain, because I can say, look. With equal likelihood, each

one of you is going to be chosen to want something. We’re in a particular state. Remember, a state is a tuple

saying how much money everybody has. OK, so if there is 200 of you

here, with a probability 1 over 200, Marc has chosen

to want something. If he has greater than $0,

he can say, OK, who’s willing to do a job. If he has 0, that’s it. He’s chosen, but nothing

happens. So with a probability 1,

we stay in the same state if he’s chosen. But otherwise, everybody who

has less than $7 will volunteer, because they will

all have a threshold of 7. So everybody with fewer than $7

will volunteer, and one of them is chosen at random

to do the job. And Marc’s money goes down by

$1, and whoever’s chosen to do the job, their money

goes up by $1. That’s the transition. So it’s easy, once we know

everybody else’s strategy, everybody else’s threshold, to

compute the transitions. Is that clear? Even if you don’t understand– there’s no deep math going on. That’s the Markov chain. Now, a key fact about this

Markov chain is if you run it for a while– nature chooses somebody at

random, you see what happens. What’s going to happen

after a while– and this is just, there’s books

and books on Markov theories, so I’ll explain

why this happens. You’re going to end up in a

situation where each state is equally likely. This is a standard, like theorem

two in any standard book of Markov chains. I’m not going to prove it, but

a key observation is that the transitions are symmetrical. What I mean by that, and that

I will explain, is that the probability of going from state

1 to state 2 is exactly the same as the probability

of coming back from state 2 to state 1. And I’ll explain why

in a second. So then we’ll open

up your favorite book on Markov chains. And there’s lots. And one of the theorems says

in any situation where the probabilities are symmetric,

after a while, you end up in a situation where all states

are equally likely. So let me explain

the symmetry. So again, symmetry means that

the probability of going from state 1 to state 2 is exactly

the same as the probability of coming back from 2 to 1. Well, what’s the probability

of going from state 1 to state 2? Remember, the only states I’m

interested in is ones where the transition means I have

$1 less, and let’s say Stu has $1 more. Those are the only possible

transitions. So let’s look at a situation

where I’m the one who wanted babysitting done. So that happened with

probability 1 over n that I was chosen. And let’s look at

all the people– again, I fixed the threshold,

let’s say, at 7. So let’s fix all the people

who have less than $7. They’re going to volunteer. And Stuart is one of them. And each one is equally

likely to get chosen. So the probability of making

that transition is 1 over n times 1 over m, where m is

the number of volunteers. What’s the probability

of coming back? Well, it’s the probability that

Stuart is chosen to want babysitting, which is 1 over n,

and the probability that I volunteer, and I get chosen. But in the long run, if the

threshold that everybody is playing is k, after a while,

nobody will ever have more than k dollars, because if you

add more than k, you’re going to come down to k. You’ll never volunteer until

you’re at k or below, and you’ll never go above k. So after the system’s employed–

do you see that? So if the threshold is 7, you

might start out life– I don’t care how you

start out life. You might start out

with, like, $50. But if everybody is playing

a threshold of $7, you’ll have $50. Then you want something done. You’ll want $49, $40. You’ll never volunteer until

you’re below $7. And once you’re below $7, you’ll

never rise above it. So after some initial period– I don’t care what state

we started out in– we’ll be in a situation

where nobody has more than $7, right? So let me talk about, again,

whether, probability of 1 over m coming back. So again, the probability of me

wanting something is 1 over n, and Stuart being chosen

is 1 over m. That means that m people

had less than $7. Well, coming back, is the

probability of Stuart being chosen, that’s 1 over n. And what’s the probability

that there’s going to be a volunteer? Well, there’s one fewer

volunteers– Stuart. But there’s one more

volunteer. That’s me, and I will have less

than m dollars, because even if I had m before,

I gave Stuart $1, so I have less than m. So it’s the same one

over n times what. There’s exactly the same

volunteers when I wanted a job done as when Stuart wants a job

done, except that before Stuart volunteered and I

didn’t– because you don’t volunteer for yourself– and now I’m volunteering

as Stuart is. So it’s trivial. And as I say, there’s this

theorem, which I’m not going to prove, that says if you

have that situation, all states are equally likely. Seems good. We understand the

system, right? There’s one slight problem. Oh, god. I did it again. You can see I’m a high-tech

kind of guy. So I don’t care about exactly

how much money Stuart has and exactly how much money Marc

has and exactly much money [INAUDIBLE] has. I really care about the

distribution of money. What I really care about is what

fraction of people have less than k dollars. Why do I care what fraction

of people have less than k dollars? Why should I care about that? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Sorry? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Well, let’s get

a more practical answer. Why do I care about the

number of people who have less than k dollars? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: It tells me

the number of volunteers. And why do I care about that? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Yeah. So look, I’m trying

to figure out– so suppose all the rest of your

are following threshold strategy k. I’m trying to figure out

what I should do. I’m noise. I’m not going to affect

anything. So I’m trying to figure

out my best response. All the rest of you are

clamped at following a threshold strategy of 7. Are we together? And I’m trying to figure out

what I should do in response. Well, what should I be

comfortable with? Should I set my threshold

at 10? Should I set my threshold

at 3? What’s the right number? Well, what I want to

know is, what’s my competition if I volunteer? I mean, what I need

to figure out– here, I’m sitting there

with 10 tokens. And is that a good

number or not? Should I feel comfortable

having 10 tokens? Well, what do I need to

know to figure it out? Well, what I need to know is,

how likely am I to run out of tokens before I can replenish? If I’m worried that I’m going to

run out of tokens before– in other words, I’m worried that

I’m going to be chosen to want something 11 times before

I get a chance to volunteer and be chosen. Are we together? Because then I’ll be unhappy. I mean, it’s always possible

that I get chosen 11 times in a row. I mean, this is random. It could be coin lands heads

11 times in a row. But I have to figure out how

likely that is, right? So what I have to figure out is

the probability that I’ll be chosen 11 times before I get

a chance to make a token. That’s what I’m interested in. So I need to know what my

competition’s going to be like when I volunteer. Now, if all the rest of you

are following a threshold strategy of 7, my competition

is exactly the number of people who have less than $7. Does that make sense? That’s what I want

to understand. So I don’t care whether it’s

Stuart who volunteers or David who volunteers or Marc

who volunteers. I don’t care who volunteers. I just want to know how

many of you volunteer. The names of the people who

volunteer is totally irrelevant. So I don’t want to know who

has $5 and who has $3. I want to know what fraction

of people have $5 and $3, and $6– well, actually, all I really

care about is what fraction of people have less than $7. Are we together? That’s the technical

point here. You’ve got that, you’re

in good shape. Now look at what happens. Suppose I tell you there

are $2 in the system. Well, what could happen? It could be– you’re

the agents. One person has the $2. How many ways are there

for that to happen? Do you remember your [INAUDIBLE]

from high school? We have n agents. How many ways are there that

one of them has $2? Not very hard. n ways, right? OK. The other possibility is

those $2, two different people each have $1. So I’m thinking, how

could the $2 be spread around the system? Well, either one person has both

dollars, or two different people each have $1. How many ways are there

for two different people to have $1? Remember this from

high school? n choose 2– n times n minus 1 over 2. So n choose 2– that’s how do

you choose 2 people out of n to have $1– is n squared. It’s n squared over 2 or n

times n minus 1 over 2. So there’s n ways that one

person has $2, n choose 2 ways that two people each have $1. n choose 2 is much bigger than

n. n squared is much bigger than n for large values of n. So it’s far more likely that

if I have $2 in the system, that each of two people will

each have $1 than that one person has $2. Now, that generalizes. And in fact, this is an instance

of what physicists call the concentration

phenomenon. OK, here’s the math. Actually, I’ll skip the

math, because I’m getting close to 7:30. So what maximum entropy

does, so given– OK, let me say a little bit. Given a distribution mu– so

think of mu of i as being the number of agents that have i

dollars– the fraction of agents that have i dollars. So it’s n of you. Suppose n is 200. If 18 of you have $3, that

means 9% of you have $3. So mu of 3 would be 0.09,

9 over 100, right? So mu of i is the fraction

of agents with i dollars. Now, the entropy of the

distribution mu– this is the entropy function– is my of i log mu of i. So it’s the fraction of agents

that have $3 times the log of the fraction of agents

that have $3. Sum that up, put a minus sign

in front, that’s the entropy of a distribution. For those of you who are

familiar with it, that’s what it is. If not, don’t worry about it. But it turns out that this is

the key, the key mathematical fact, that the number

of agents if the– there are lots of different ways

to distribute capital N dollars, like $10,000 among

500 people– that’s if one person could have $5,000, one

person could have $0. There’s lots of different

ways of doing it. But it turns out that ways

that end up having a distribution of money that’s

very close to the maximum entropy distribution dominate

all other ways so that the likelihood of having the

distribution of money be characterized by probability

mu is characterized by the entropy of mu. The distribution with the

greatest entropy or distributions close to that are

far, far more likely than anything else. What does that mean

in practice? This is an answer to your

question about why I don’t have to know anything about

previous auctions. I know if n is reasonably

large– yes, so as long as I know how

much money is in circulation, if n is reasonably large, then

I know almost for sure, like with probability– in 9,999 circumstances

out of 10,000– very, very close to 1. I know for sure what fraction

of agents have $0, what fraction of agents have $1, what

fraction of agents have $2, within a very small fudge

factor of epsilon. It’s characterized by the

distribution of maximized entropy, that maximizes this

expression of this, the entropy expression. It’s the distribution that

maximizes the entropy as the one that almost surely

characterizes the fraction of agents that had each varying

amount of money. So I don’t have to know

anything else. I know what my competition

is going to be like. If the threshold is 7, I know

almost for sure, like I would bet huge sums of money on it–

you’re much safer betting on this than crossing the street. That’s how sure you are– how many agents are going to

volunteer in each round. I don’t know who they are. So I don’t know which agents

have $3, which ones have $5. But I know what fraction of

agents will have $3, what fraction will have $5, and in

particular, if the threshold is 7, what fraction will

have less than $7. So I know what my competition

is going to be like. I know every time I raise my

hand, almost for sure, how many other people are going

to raise their hands. Each round is going to be 112

people raising their hand, almost for sure– different people. Are we together? That’s sort of the power

of mathematics here. So I can now figure out– it’s a fairly straightforward

computation– what my threshold ought to be. That’s the point where the

likelihood of the cost of not raising my hand exceeds the

cost of raising my hand. In other words, how likely is

it that I’m going to run out of money if I have 10 tokens? How likely will I run out? Knowing what my competition’s

like, I can figure out how likely I am to be chosen every

time I raise my hand. I can figure out how many times

it’s going to be before I run out of money, with

all probability. Because I have the complete

probabilistic model, I can figure out what’s the right

amount of tokens I should have if I’m going to do

a best response? OK, that’s what this tells me. Now, here’s a sanity check, even

if you don’t understand any of the mathematics. So what I’ve done now is I

said clamp everybody at following at threshold of 7. Now, suppose I change that and

say clamp everybody at following a threshold of 10. Should my threshold

go up or down? What’s your intuition? So if I know all the rest of you

are following a threshold of 10, compared to 7– so I figured out my

best response. Let’s say my best response, if

you’re following the threshold of 7, the right thing for me

to do is to have 10 tokens. Suppose I raised your

threshold to 10. So you’re going to raise your

hand as long as you have 10 tokens or less. Should I raise my threshold or

lower my threshold or no clue? Any intuitions? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Raise. Why? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: OK, let’s make

it a bit more precise. You’re sort of right. So that’s the right answer. If other people are raising

their threshold, I should raise my threshold. But why? There’s a really good

intuitive answer. Anybody else? Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: You’ll have

more competitors. That was exactly the

right answer. If everybody else is raising

their hands– before, they were all raising

their hand if they had less than $7. Now they’re raising their hand

if they have less than $10. You have to be a little bit

careful, because if the threshold is 10, the

distribution changes. Because before, they only had

amounts between 0 and 7. Now they have amounts

between 0 and 10. So there’s a slight

subtlety here. But nevertheless, it’s

the case– and it’s not hard to show– that if everybody’s raising

their threshold to 10, you’re going to have more competition

than when the threshold was 7. So you ought to raise

your threshold. So your best response function,

as a function of what everybody else’s threshold

is, is increasing. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: No, it’s not

raising their price. It’s raising when they’re

willing to volunteer– raise their threshold. It’s not a price. The price is always one token. There’s no change in price. So it’s raising your

comfort level. Before, you were only going to

volunteer if you had fewer than 7 tokens. Now you’re going to volunteer

if you have fewer than 10 tokens. Does that help? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Yeah,

but you shouldn’t– I mean, let’s just stick

to thinking about tokens and not price. So using this, what happens

is there’s– so for the technically oriented,

there’s the theorem by a famous mathematician named

Alfred Tarski, that more or less says, if you have a

monotonic function, so the best response function, which is

what should I do given what you’re doing? So you as everybody else. So if I know everybody else’s

best response is 7, what’s my best response? If I know everybody else

is clamped at 10, what’s my best response? If everybody’s clamped at 15,

what’s my best response? That best response function

is monotonic. As I raise what everybody

else’s threshold is, my threshold, my best

response goes up. If you have a monotonic

function, there’s a fixed point. The fixed point means everybody

else is doing 12, my best response is 12, that’s

an equilibrium. In other words, if everybody

is playing 12, they’re best responding to everybody

else playing 12. So even if I know that all the

rest of you are playing 12, because 12 is a fixed point,

then I’m playing the best response, and that’s

a Nash equilibrium. So this theorem basically says

that as long as delta is close to 1, and there’s enough

agents– enough turns out to be, like, 100– then this is basically saying

that there’s an epsilon best reply that’s a threshold

strategy. And the best reply function

is monotonic. And from that, we can conclude

that there’s a greatest and least fixed point, and we can

find the fixed point iterating best replies. Let me skip over this, and let

me jump to the punchline, that we have a Nash equilibrium

and threshold strategies. But this is what I was

saying before. How much money– suppose you know that. You’re the system designer. No matter how much money you

pump into the system, there’s a threshold. That’s good. There’s a magic number, like

12, that the agents can actually learn by just playing

and discovering. Just best responding to each

other, they can figure out what the best response is. So there is a Nash

equilibrium. We’re all going to play 12. We’re all going to

happily play 12. And it’s nontrivial. Again, it’s a Nash equilibrium

if we all play threshold of 0. That’s not interesting. But there’s a non-trivial

Nash equilibrium. But that hasn’t answered the

question, that what’s the right amount of money to

pump into the system? And there, the key is– we did experiments. We can both prove this

mathematically and observe it by simulation, that as you pump

more and more money into the system, you look at the

total happiness of the system. Remember, you’re

totally happy. You’ve increased happiness by

making sure that when somebody wants a job done, they have

money, following the threshold strategy, and they’re unlikely

to run out of money. Again, it’s always possible

to run out. You’re using a threshold of 10,

it’s always possible that 10 times in a row, very quickly,

you’ll want a job done before you get a chance

to make an extra dollar. It’s possible, but unlikely. As you pump more money

into the system, that likelihood goes down. But then you want that will it

be the case that people will volunteer, and so there’s a

magic threshold where people all of a sudden stop

volunteering. And that was a surprise. There was a cliff, that it

happens all of a sudden that you reach this magic number, and

people stop volunteering. And this says something. So now, let me talk about

system design issues. I’ll try to finish up in the

next five minutes or so. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: No. So we’re not clamping

the threshold. We’re looking at what’s

the equilibrium. And the equilibrium will change

as you pump money into the system. So now I’m not setting

the threshold. Now I’m assuming everybody

is a rational agent. They’re all going to play in

that Nash equilibrium. So in other words, if I set

everybody at 7, then you might think, well gee, why

should I play 7? 12 is better for me, right? So the equilibrium is

everybody’s playing 12, and that’s also the best response. 12 is the best response to

everybody playing 12. Am I making sense? Not so happy. So AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: OK, so what

I’m claiming is there’s a unique, technically greatest,

fixed point. So once you fix the money

supply, there is a magic number that you can compute– and I can even give you

the procedure, but let me not do that now– that gives you a fixed point. That is, there is a

magic threshold– let me say, 12, but

it’s not 12. But it is a function of

the money supply and the number of agents. What really matters, it turns

out, is not the money supply or the number of agents

separately. It’s the average amount

of money per person. So it’s the money supply

divided by the number of agents. So that turns out to be the

key parameter, the only parameter that matters. But once you fix that– so for

every average amount of money per person, once

you fix that– there’s a magic threshold– let me say 12, but it’s not– such that that’s the greatest

fixed point. So it’s everybody playing 12

is the best response to everybody else playing 12. And there might be other fixed

points, but there will be smaller than 12. So that’s what we’re

looking at. But that was assuming that the

system size was fixed. Now, imagine a real-world

system that’s dynamic. People enter and leave. And particularly, you’re

interested in systems where lots of people are coming in. You have a growing peer-to-peer

system, and you want people to do

jobs for you. This really happens in

real systems, right? It’s not like I’m

making it up. And the system grows. And now you say, well, OK. I’m the system designer. What’s my goal? Well, what I’ve learned from

this talk is what I want to keep is the average amount of

money per person fixed. So if the right average amount

of money was, let’s say, 7, so if another 200 people enter

the system, I want to pump 1,400 more tokens

into the system. So I don’t want to do what the

Babysitting Co-op did and pump lots of tokens in for

no good reason. There’s a magic number. But of course, if more people

join the co-op, then you want to increase. Now, what’s the right

way of doing this if you’re a system designer? So one obvious way of doing

this is, OK, every time somebody comes into the system,

you give them $7. Why is that not a good

idea on the internet? Now, you’re a system designer,

and you want to keep the average amount of money per

person fixed at 7, now your system’s growing. You just had 1,000 people

joining the system. This really happens. And you could say, OK, one way

to keep the average amount of money– it was $7 before. Make sure each person

coming in gets $7. Of course, the average is

still going to be 7. Why is that a bad idea? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Zombies. Two accounts. You’re all saying

the same thing. It’s called– AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Right. It’s called the sybil problem. That’s the technical

terminology. But it’s I come in,

I get my $7. I ask for seven jobs,

now I’m down to 0. No problem. I leave. My twin brother comes

in, gets the $7 and spends the $7 and leaves. But then I also have

a triplet– I have another sister

out there. She comes in, gets $7, spends

it all, and leaves. This is the zombie,

a sybil problem. Many people are terminal. So that’s a very bad idea if

you’re a system designer. So what do you do instead? Redistribute. So what we suggest is bring

people in with $0 So suppose the system doubles in size. Before, you had 1,000. Now you have 2,000 people. You want to bring in a new 1,000

people with $0, because otherwise, you’re going

to get the sybil problem, or zombie problem. But you still want to keep the

average amount of money at $7 per person. Well, you just give everybody

double the amount of money they had before– the people who were

there before. The new people get $0. So we have inflation here. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Yes, but you

still keep the average amount of money at $7 per person,

and that turns out to be what you want. You want to keep the

averages right. Oh, equivalently, you have

the price of a job. Notice that giving everybody

twice as much money as they had before, effectively, is

saying the price of a job used to be $1. Now it’s $0.50. Yeah. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: That would be

another way of doing it. And again, this would tell you

what would be the right price to set it at to solve

the zombie problem. So you could say it costs $7 to

enter the system, and I’m going to give you $7. So that would be another

way of doing it. It would maintain the average

amount of money at $7, but you have no temptation, although it

turns out you do, and I’ll come back to that,

to have zombies. Are we together? I mean, this is the kind of

thing a system designer has to think about. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So you’ve got to

think about these things as a systems person. And the hope is that the number

of people who are entering is relatively small

relative to the number of people that are there. So what it means is when

you enter, you’d have to do some work. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: OK, so maybe

now you have to– I’m not denying what

you’re saying. So you need to think, maybe

the right thing to do is charge a small amount

to enter. You can’t win here. So if you give everybody $7,

then you’re going to have a sybil problem. And otherwise– AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So we didn’t,

because we didn’t have the exponential growth in

our simulation. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Right. So again, these are

things you– so we didn’t do it. And I think as a systems

person, you clearly have to do it. So let me just do one

or two slides. I know I’m over 7:30, so let me

try to finish up quickly. Now, in the real world,

as I said, not everybody is rational. Now, these are tokens. There’s no happiness

value associated to these tokens, right? You don’t die happy if you have

$1 million stuffed under your mattress, I’m told. But– AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: In the real

world, there are people who like to have money for the sake

of having money, but we call them hoarders. And there’s other people who

are altruistic and love babysitting your kids. You don’t have to pay me. Your kids are just so great. I’ll do it for free. Well, we call those altruists. So I mean, I think there

are many types of irrational behavior. I’m not trying to suggest– irrational only in the sense

that they’re not treating these as just pure

tokens, right? I don’t want to say,

necessarily, altruists are really irrational. Hoarders are really irrational,

but the irrational– Marc, just give me one

or two more minutes. From the point of view of– I know I’m over time. From the point of view of our

framework in the system. But my guess is that in the real

world, you’ll find all sorts of different flavors of

irrationality but a few rather common flavors of

irrationality. And I’m suggesting hoarding and

altruism are going to be fairly common flavors

of irrationality. So it turns out that hoarding

has the effect of removing money from the system. So if you understand that 10% of

the people in the world are going to be hoarders, well, so

what happens now is that critical point just moved

over a little bit. You should pump a bit more

money into the system. And that turns out to be just

right mathematically, as well as intuitively. Does that make sense? Putting money under your

mattress is taking the money out of the system. So you put in a bit more money

into the system to compensate. Now, altruists have the opposite

effect, sort of, but it’s a bit more complicated. Roughly, they’re like adding

money to the system, because they’re going to do

work for free. Having some altruists

in the system makes everybody better off. So if I know there’s, like, 10

people out there who will work for free, well gee, great. Because those few times when

with very, very low probability I ran out of money,

you’re there to babysit for me because you just love my

kids, and you’re willing to do it for free. Great. Social welfare increases,

right? You like babysitting my kids. It didn’t hurt you. And I’m happier, right? So a few altruists are good. AUDIENCE: Grandparents. JOSEPH HALPERN: Grandparents. That’s right. They’re called grandparents. But too many can hurt

social welfare. Let me give you the intuitive–

or I can give you the graph. So this is what happens. You add altruists

to the system. Things get better and better. But then there’s a crash. Any intuition for the crash? I can give it to you, but does

anybody have a sense for– again, real-world phenomenon. It has a real-world

explanation. And this, actually, I mean, in

the academic world, I can give you phenomena like this. If you think there’s a lot of

people who are willing to referee a paper. [INAUDIBLE], any thoughts? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Exactly. So suppose I’m perfectly

rational. And I say, hey, why should

I work to get a token? There’s a bunch of guys out

there who are willing to babysit for me for

nothing, right? Now, it’s not true– so

actually, this only makes sense when we assume that– so in our slightly more

complicated model, well, you don’t always volunteer, even if

you’re an altruist, or even if you need the money. Let’s say Friday night I’d

love to volunteer. Sorry, I can’t. With some probability

beta, I’m busy, and I just can’t volunteer. So we’ve assumed in this paper

that beta is 1, that as long as you have less than your

threshold amount of money, you’ll volunteer for sure. But in our more general result,

we assume that there’s a certain probability that even

if you’re an altruist, or even if you need the money, you

won’t volunteer, because hey, you’re busy. In the real world, in the

real systems world. right now, as it happens, you

don’t have to spare cycles to do the job. It’s just a busy time. So we assume that with some

probability beta, you won’t volunteer, even if normally,

you would. Well, in that case, imagine

there’s a bunch of people who are altruists, and I say,

why should I volunteer? Because when I want something

done, there is a good chance that somebody out there

is an altruist and will do it for free. Now, unfortunately, that chance

isn’t high enough. So it’s still not worth it for

me to volunteer, but there’ll be a bunch of times where I’m

going to want something done, and there simply won’t

be a volunteer. So in a system that’s tuned

right with no altruists, you can be better off than in

a system where there are altruists, because in terms of

total social welfare, there will be times when I’m just

going to have to, because there’s nobody out there

volunteering for me. And we can do this

by simulation, but that’s the intuition. OK, just about done. Sybils have subtlety. So remember, sybils

are these zombies. So you can stop the obvious

sybil attack by saying, OK, you come in with $0, so it

looks like you have no incentive to bring in sybils. Ah, not so fast. You do have an incentive

to bring in sybils, provided that– so suppose you raise

your hands. Now, suppose I had

five sybils. And suppose, OK, I tell all my

sybils, who are just me with different IP addresses or

something, OK, I need a job. All of us raise our hands. And of course, if any one of us

is chosen, it’s like I do the work, and I get the token. If we can do that– and again,

whether or not we can do that depends on features of the

system, and I’m not really talking about that. But if we can do that, that

means having sybils, I can arrange it so my probability

of getting chosen is higher than it would be

without sybils. Does that make sense? Having a sybil just doubled my

probability of getting chosen, because now there are

two hands going up, instead of one. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Right. So it works if I have sybils

and nobody else does. Now, of course, then we

get an arms race. Everybody has sybils, right? If everybody has another

sybil, I’m right back where I started. So there’s all sorts

of issues here. So it turns out that, again, we

can show, by simulation– and I can’t remember if

we actually had a theorem about this– that sybils have diminishing

returns. Like even if nobody else is

going to have sybils, two sybils, that helps. Three sybils helps. More sybils helps, but the

amount it helps goes down pretty rapidly. So it seems to me, in this

kind of a situation, you probably do want to charge

a little bit to enter the system, even if you’re going

to come in with $0. But again, this is a systems

question, not a theoretical question. A few sybils can be good. Let me skip this. So we have other results

and how to infer the types of agency. What’s your alpha? What’s your beta, the

probability that you’ll be able to work, even

if you want to? So if we have different kinds

of agents, unlike this [INAUDIBLE], and everyone’s

homogeneous, it turns out we can infer that, which is

something that marketers want to do, from the distribution

of wealth. We understand how the system is

going to evolve over time, so we do have some answers

to question about convergence time. It turns out that in general,

multiple equilibria will exist, even in threshold

strategy. But the one that we looked at

was the greatest fixed point that has these properties. So these are technical results

for those interested in them. One thing we looked at– last thing. This is the very last thing I

want to say, is that we said, well, how hard is it to

learn what to do? It’s not like somebody tells

you, hey, the right threshold to play is 12, right? You’re entering the system. How do you know? Well, it turns out– again,

precisely, if you don’t have this exponential growth, if the

amount of growth in the system is relatively small, so

you have relatively few new entrants for the amount of

people there, you can learn the right thing to do simply

by experiment. Let me try 10. let me try 11. Let me try 12. Let me try 15. Very little experimentation

will get you to the right place. This works if most people in

the system know what to do. So they’re not experimenting. But now, if you have a bunch of

people entering the system, and they’re all experimenting

at the same time, totally breaks down. You get chaotic behavior. You get really weird stuff. We don’t totally understand

what’s going to happen. So we do provide some

theoretical results for learning large, anonymous

systems. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: I’m not sure. It depends very, very much on

what you assume about– I can make it converge

if I make enough assumptions, so yes. But I’m not going to try to tell

you those assumptions are all reasonable. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: No, because

we’re still keeping the price of a job fixed. So the question is,

is it equivalent to an auction where– AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Right. So let me just stop, so Marc

won’t feel like I’m abusing everybody’s time here. So just to summarize, that it

turns out mathematically, it turns out rather amazingly– like I said, we certainly

didn’t expect this. And actually, the way we got

here is I had Ian, who was my student at the time,

do simulations. Simulations were saying,

there really is a nice best reply function. There really is an

equilibrium. And it felt like, there must

be something going on mathematically. And I had done other work where

I used maximum entropy. And somehow, I sort of stared at

it for a while, and I said, this sort of feels like

the other work. Ian, go think about it. That’s why we have students. And it turned out, magic,

maximum entropy worked. So I don’t want to say that,

boy, we were so brilliant, we knew all this stuff was

going to happen. We really did it– and I’m a theoretician. I usually start by

proving theorems. This is probably the first

paper of my life where I started by telling a student,

do simulations, because I don’t really have a good sense

of what’s going to happen. This simulation showed we were

getting really rapid convergence with about 100

agents, and it looked like there was a nice equilibrium

and threshold strategies. And we said, god, this is

happening every time. There must be some theorem

here that explains what’s going on. So then we proved the theorem. But I told the story not

the way it happens. Of course, now that I’m giving

the talk, I tell you about the theorem, and I explain it. But that’s not how

it happened. So for a theoretician, it’s

sort of nice that you can totally characterize what’s

going on in the system for a fixed number of agents using

maximum entropy and using the monotonicity and best-reply

functions. That’s the technical meat of

the paper here, but if you don’t follow that, don’t

worry about it. For the system designer, the

message here is the right quantity to manage, the only

quantity you care about, is the average amount of

money per person. And more money is better up to

a point, but that point is a critical point. There’s a cliff there, and you

might want to trade off efficiency for some

robustness. You want to back off from the

cliff just a teeny bit. We can sort of understand how

to deal with, if you like, standard irrational behavior,

like hoarders and altruists and with sybils. But I think there’s a

lot more to be done. And one of the things that I

think I would really like to do– so let me just close with

this– is understand the impact of auctions. So people were asking

at the beginning, shouldn’t you have auctions? And my intuition says it depends

on the kind of market. If you have a market with many

buyers and sellers, auctions won’t buy you much, whereas

if you have rather small, specialized markets, auction’s

the right thing to do. Now, that’s an intuition. The mathematician in me wants

to formalize that. But let me just give

you the intuition. I can go to the large grocery

store near my house, which is a Tops or a Wegmans. And even at 10 o’clock at

night– now, it happens that Wegmans is open 24 hours a day,

but even imagine a store that closes at midnight. And I can see there’s a

lot of tomatoes left. And I know that by tomorrow,

they’re going to go bad. They do not auction tomatoes. There’s a fixed price

for tomatoes. Now, I know I can also

go to the [INAUDIBLE] in Egypt or in Jerusalem, and

there, you can bargain for vegetables. But certainly in large grocery

stores, you can’t, and they’ve decided it’s not worth it. Now, there’s lots of

reasons and stuff. There’s overhead in allowing

auctions, right? You don’t have them in

large grocery stores. You do have them in more

personal, smaller settings like markets. So I think there’s a technical

question here. Assuming you’re a system

designer, there’s real overhead in building

a system with– OK, I know Google does it, so

it’s the wrong place to be saying this– but certainly in some kinds

of markets, instituting an auction, there’s

real overhead. And definitely, producers and

consumers like the certainty of fixed prices. I can plan a whole lot better

if I know this is going to cost $5 for the next year. I mean, I can figure out what

my expenses are going to be. My intuitions is with very large

markets with a large number of buyers and sellers,

you didn’t have to have an auction, because you’re going

to end up at a certain fixed price, anyway. Things aren’t going to change

much, again, assuming everything’s stable. Things change if you have, all

of a sudden, explosive growth in the number of players. Then you get inflation. And we can see these phenomena. Yeah? AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: OK,

so they do. So again, I’m not saying

it’s silly. It’s not that common, though. So again, I definitely– you

should not take what I’m saying as auction’s bad,

fixed price is good. I am saying that auctions incur

some overhead, and you have to think hard about

when to do them. They don’t have them

all the time. I assume they do it at the

very end of the day. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Maybe so,

but these were yuppies. They didn’t want to get into– I mean, again, think about

the sociological context. You don’t want it

to be the case. So it’s not like I’m going out

to the workforce and posting an ad on the internet. This is a group of 30 people. They all know each other. They’re not going to bargain

about the price of babysitting. I mean, maybe they should. OK, there’s some interesting. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Yeah, they’re

part of the economy. So markets– it’s 12

minutes to 8:00. I mean, I don’t mind cutting it,

and you come to me and ask me questions. I’m here. Couple more questions,

and maybe we’ll– AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Absolutely, it’s

a cultural phenomenon. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Believe

me, I know. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Well,

I don’t know about the slug in the face. And they like to

tell tourists– oh, I’ve been to–

well, not Tehran, but many other countries. And my daughter calls me in to

bargain for her when she wants to do some shopping at

the Jerusalem market. And she says I’m a better

bargainer than she is. But they like to pretend

the prices are fixed. They certainly won’t slug you in

the face if you take their first offer. They’re very happy– AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Well, they might

think you’re a fool. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Right. Well, depends. but yeah, it’s definitely

a cultural phenomenon. There are many issues here. I’m not trying to say

there aren’t. But I think there’s more to it

than just a cultural effect. I think there are markets

where it’s much simpler. As I say, for a producer,

there’s a comfort knowing a fixed price. There are some real benefits. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: So this

is the interesting– I talk a lot to economists. So I think you can say you leave

money on the table if you don’t have auctions. It’s more efficient

to have auctions. In some settings, I

believe it’s true. And the question is, what’s

the cost of inefficiency? I mean, I have the paper

title written. The paper’s going to be calls,

“The Cost of Inefficiency.” AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: There’s

how much time, and you’re a system designer. It’s more complicated. I mean, I think there are

many, many issues. So– MARC DONNER: Two

more questions. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: To take

a random stock. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Sure. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: Again,

it depends very much on the setting. That’s an instance of where you

might argue that there’s a price to be paid for the

efficiency of auctions. And so my own feeling is I would

love, as a theoretician, to be able to characterize the

features of markets that make fixed prices the way to go. And you’ve sort of given

me one instance. And my gut tells me, as a

theoretician, that there ought to be a theorem here that

characterizes them. But future work. OK, well, 20 questions, and

there’s room for one. AUDIENCE: [INAUDIBLE]. JOSEPH HALPERN: That’s

a great question. My results have nothing

to say about it. So we were assuming there’s

only one market. There’s a fixed price. You can’t go elsewhere

to get your job done. Now, you’re talking about a

situation where there’s several markets, right? So that if you don’t like my $1

price, you can go somewhere else and get it for $0.75. AUDIENCE: Right. JOSEPH HALPERN: Right. That introduces a whole bunch

of complicating factors. I’m sure all of my

results go away. So as a technical matter, I have

nothing to say about it. But it’s certainly an

interesting question. But again, why doesn’t

everybody go there? So you have to assume– as an economist, you have to

understand what are the features of the various

markets. I mean, if all markets are the

same, then in the end, there will be one market. Because if the discount market

is in every way as good as the non-discount market, then why

would you ever shop at the non-discount market except for

maybe if you don’t realize the discount market is there. So it’s founded not in

irrationality but lack of information. So Marc says that was the last

question, but I’m willing to stick around if you have

more questions. MARC DONNER: Thank you

all very much. [APPLAUSE]

Ponzi scheme.

Awesome

The baby-sitting story & his disdain for "Washington" & "Washington Yuppies" is highly funny … & explains the theoretical problem pretty well.

I don't understand what is the advantage of a scrip system where prices are fixed (no negotiation of multiple token for a babysitting or competition on prices).

If you allow prices to vary, then well-understood price mechanism kicks in and prices emerge without running into price control problems.

Overall, the analysis and assumptions are disappointing. There is no measurable or comparable unit of utility (utils) and there is no reason to assume they are the same for different people.