0:33

And so in terms of proving that this star is the right thing to do,

in the middle cost range.

So first of all, it's very easy to analyze the case where C is

less than delta- delta squared.

Because now, if ij are not already connected, the value that they're getting

from their relationship is going to be less than or equal to delta squared.

And if they add a direct link, they are going to get a delta

minus c for that relationship, possibly some extra bits too.

And if c is less than delta minus delta squared,

then delta minus c is bigger than delta squared.

And so, the value that they're going to get is at least what they've got before,

and so both of these individuals will be better off, right?

So ui and uj of adding this link is better off.

But also, in the connections model, everybody else benefits,

or is not hurt by adding new links.

So you get benefits from the shortest paths, if we add extra links,

that just shortens your paths.

So everybody else is doing at least as well as they were before,

plus these two individuals are doing strictly better.

Therefore, it's better to add the links.

So here, the idea that when c is less than delta- delta squared,

when you get the complete network, that's straightforward, okay?

So what we're going to do is instead, look at the case where c is bigger than delta-

delta squared, so we don't want to form the complete network.

And we're going to do two things.

First, we're going to show that the value of a component

is highest when a component is a star, okay.

2:17

And then we'll actually show that if you're going to arrange people,

you're best off doing it in a star.

And then you don't want to have multiple stars,

you'd be better off having one star.

And then we can just compare whether it's better to have

a big star with everybody in it, or no star at all, okay?

And that'll be the difference between the medium cost and the really high cost, so

when costs get high enough, a star is not even valuable.

So basically what we're going to show, is that if you're going to arrange people

when c is bigger than delta- delta squared, you better do it in a star.

And then is a question of whether a star is valuable, okay?

So value of a star with k players, what is it?

Well, with k different players, then we've got 1 person in the middle,

k- 1 other individuals out here, so we've got k- 1 links in total.

And so each one of those links gives a value of delta- c

to each of its participants.

There's two people in it, k- 1 links.

So the direct value of connections is 2 (k- 1) [delta- c].

And then the indirect values that we're getting wre coming from the fact that each

one of these indirect people, there's k- 1 of them, right?

They have k- 2 other neighbors, each at a distance of 2,

so each of these k- 1 people have k- 2 neighbors,

each one of those gives a benefit of delta squared.

So the overall value of a star Is 2(k -1)[delta-

c] + (k -1)(k- 2) delta squared.

Okay, so that's the value of a star.

Now let's look at the value of some other configuration,

that involves k players and m links,

where m has to be at least k- 1 in order to connect these k players together.

Okay, so if you've got m links, first of all,

what's the value you can get out of the links directly?

Well again, same kind of calculation, you've got m links, 2 people in each link,

delta- c, so that's going to be the value there, of the direct value.

And the most you could be getting indirectly is,

you've got k players,

k- 1 other people that they could be connected to,

2m of those connections are direct connections.

So the remaining connections, this is how many remaining indirect connections there

can be, and at most they could be with delta squared, okay?

So this is the maximum possible value we can imagine for

some other component with m links, okay?

So let's take the difference between these two, so let's take this,

we'll take the difference between these two different, right?

So take this expression, subtract off this expression and what do we get?

If you subtract this from that, well, you can do the arithmetic.

The difference is going to turn out to be 2(m-(k-1)[delta

squared- (delta- c)], okay?

5:48

And if you remember correctly,

we're in the region where we have got

delta squared > delta- c, right,

because we're in a region where c > delta-

delta squared, so we've got that holding.

That means that this thing is positive, and

so if m > k- 1, then this whole difference is positive.

Okay, so this is more valuable, this is more valuable.

The first expression is more valuable than the second expression,

in a situation where m > k- 1.

So if we're using more then m links,

we're doing worse than if we just did the star, okay?

7:08

Well, we get the direct value of connections, and then at most,

we can have all but 1 relationship in the delta squared.

Some relationship, at least one of them has to be the distance delta cubed, okay?

And then if you do the difference between these, all we've done is move some

relationships which could be closer, to some that are further away.

So we get the same value in direct connections,

the same number of indirect connections, but some of them are at higher distances.

It's gotta be lower value than a star, so the star is better, okay?

So what we've shown is, if we're going to connect k individuals, the best way to do

it, when we've got c > delta- delta squared, is via a star, right?

8:02

Okay, so now what we can do is say okay, well, what are the possibilities,

maybe 2 stars are better than 1?

So we can check that if 2 star components each give non-negative utility,

then 1 star with all those people generates a higher utility.

And so what we can do is just look at,

what's the value from the separate components, right?

So we've got k people in one of the stars, k' in the other star,

2 stars, what are the values?

If you put them all together, now we've got k plus k' people together.

8:39

So before, we have this value, 1 star, we have k plus k' people together.

Compare this expression to this expression, and it's easy to check.

The first parts of these are identical, right?

And you can just go through, and

check that the second expression, here, is larger than this one.

Okay, so just simple arithmetic,

you can verify this expression is bigger than this expression, and

therefore having 1 star is better than 2 stars, and what's the reason?

The reason is, if you've got 2 separate stars, you're not getting

the value of indirect connections, sorry, actually there's one difference here.

9:33

And in terms of indirect connections,

we're getting more people indirectly connected than we had before.

And so the second expression overall is higher,

both in terms of the direct connections, and the indirect connections.

You're better off having one giant star than two separate stars, okay?

So what we've shown is if you're going to connect people, you want to

connect them in one star, rather than in some other possible configurations.

Put them all together in one star.

So then the last thing we have to do, so

efficient networks are going to be either collections of stars, or empty networks.

Again, here’s the situation where c > delta- delta squared,

right, so we’re in this case.

So either a star or the empty network, and

now what we can do is, check the value of a star and

the most, So check, putting all people together in a star, when is that valuable?

So if putting some people together in a star is valuable,

putting more people together in a star is going to be even more valuable.

And when is a star have a positive value, with everybody's involved?

Look at the value of the star when bigger than 0, and

that's that last expression that we saw in the medium crossed-range.

If c is bigger than that, then it makes sense not to connect anybody,

just keep everybody separate.

If c is smaller than that, then a star is the best thing, and

what we've shown is a star is the unique efficient architecture in that setting.

And then for cheap things, it's easy to see that we've got the complete network.

So this does this kind of analysis, and again,

to emphasize that there wasn't anything special about deltas and

delta squared, it just mattered that there was some value.

When you think of some value of a distance, one relationship,

that's bigger than a value of distance-2 relationship,

bigger than a value of a distance-3 relationship.

You could plug those in everywhere for delta, delta squared, and so forth,

and exactly the same propositions would hold.

You'd have something where star architectures are going to be the valuable

things.

11:47

Now, a couple things just to say about this model, the model's obviously special.

And the special nature of it is, that there's not sort of diminishing returns.

If I add ten more people to the society and I have indirect connections to them?

I still get ten extra indirect connection values,

it's not as if they're less valuable than the first ten indirect connections.

So if you start putting in diminishing returns,

then it can be that you get other kinds of architecture.

So we can start enriching these models, and

one thing to emphasize is this is a simple one, it gives us some intuitions.

More generally, we can embellish these, resolve them,

see what works, is sort of the methodology that is being emphasized here.

Okay, so that's the look at the efficient networks and the connections model.

Next, let's see whats pairwise-stable,

wee if there's some differences between those two things.