We will start our journeys together throughout these twenty questions with a

question on our wireless, cellular mobile network.

And this shows a typical picture of a cellular network.

The entire physical space is divided into many cells, a hexagon area here.

With a base station here, and many mobile stations, like your cell phones or

tablets. And in this course, we ask the question,

how does my smartphone work in CDMA network?

In both main versions of 3G networks, CDMA is a key component of the technology,

okay? And we will look at two critical issues.

Number one is a technical one, okay? How can we control interference in the

air? Your signal will case interference to my

transmission, just like in a coctail party.

Well, maybe controlling the transmit power is a degree of freedom we can use and that

is something we'll talk about. Transmit power control including a very

simple but clever algorithm that can distributively control the transmitted

powers, so that we don't end up shouting at the top of our lungs altogether.

And this is the algorithm that was implemented in all the 2.5G and the 3G

standards. And this shows us a particular way to

control what we call the Tragedy of the Commons or so called Negative Network

Effect. Another purpose of this lecture in

answering this question is to introduce two powerful modeling methodologies.

One is called Optimization Theory. We're looking at a special case called a

linear programing here. Now, optimization is something we do all

the time in our daily lives. For example, if you want to maximize your

happiness and your degree of freedom is to chose between taking this course versus

going to the movie theater. Okay?

And the constraint is, you will have a limited number of hours each day, you may

decide to pick one or the other and optimization theory is a mathematical way

to make precise many of those English languages.

We also introduce, in addition to constrained decision making, a model to

think about strategic behavior of intelligent agents which could be human

beings, which could be networking devices and that's called game theory.

Introduce the basic terminology of both, and both would be used a lot throughout

the course. And, indeed, the next question, which is,

how does Google sell this add spaces? On a search page, we'll be using game

theory to model and analyze a particular mechanism of allocating resources, in this

case, as spaces and that mechanism is called auction.

The auction is something that some of us are familiar with, and we'll look at

different forms of auction and how an object is allocated among competing buyers

and what price shall it be charged for. We look at a graph like this, so could buy

part a graph, skipping the details to the actual lecture.

This preview suffice to say, there are many potential buyers, and many objects

and we need to find a match. What kind of match will provide a fair and

efficient allocation? That is the question we'll have to answer.

We'll look at examples from Google as well as from eBay allocation of a single

object. We'll see that a smart idea is to say that

object, if there's only one, goes to the highest bidder but the price is actually

charged based on the second highest bidder's price which sounds very counter

intuitive at the beginning. But we will see, this turns out to be a

smart way to mitigate the negative network effect or to, so called, internalize

network externality. Now, of course, Google's main business is

provide a search service and to provide a ranking of relevant web pages to your

search query. Now, how can Google rank relevant pages?

Let's say there are four relevant webpages, the actual problem is much, much

bigger scale than this. But, suppose we just have four, and there

are some links among these node, the node are the webpages, each link is a

directional hyperlink between one page and the other.

You might think, if a lot of pages point to a given page, that page should be more

important. Turns out, that is a good starting point

of a line of thoughts that lead to what's called, Page Rank Algorithm, named after

one of the two co-founders of Google. This is a powerful algorithm.

We'll see efficient way to execute it and to compute different node importance

scores. We'll pick up this theme later in Lecture

eight. We'll also show how page rank by Google is

strikingly similar, in fact, there's an exact mathematical parallel to Qualcomm's

CDMA power control algorithm. We'll see that while the networks are very

different when it's a webpage network, there is a wireless device networks.

There are many underlying commonalities in how they treat the challenging problems

there. And then, we'll move on in question four

to Netflix. If you have used Netflix, whether DVD, or

online streaming service, you have noticed that Netflix recommends movies to you.

How does Netflix do that? That is the question.

And we will talk about the interesting story behind the famous Netflix prize, an

open online international competition a few years ago where Netflix offered $one

million for teams that can do a better job of recommendation.

We're going to define, what is the job of a recommender?

Specifically, in Netflix's case, what is the figure of merit?

How can you compare one recommender's performance versus the other?

And it turns out, a powerful idea in the winning solution of Netflix prize is

collaborative filtering. It leverages the fact that different users

have different similarities and, in their behavior, and their, tendency to like or

dislike certain movies. So, if I want to estimate how user one

might like certain movies that she has watched yet, I may actually leverage my

knowledge about the other user's ratings of this movie and we see a smart idea to

leverage that understanding to enable up very accurate a recommender system.

Along the way we'll also expand our portfolio of optimization theory from so

called a Linear Programming, LP to the so called least squares, which is non-linear

quadratic optimization and we will see how that extension can be carried out.

Now, question five is something that perhaps, all of us have encountered.

We probably have all have used Amazon to do some shopping online.

And when you go to Amazon and say I want to buy a new HDTV.

You see there are two, or in fact, many options, okay?

Now, one product may have three and a half stars, the other may have five stars, as

of the average number of stars in the ratings.

And they say, well, it looks like this is a better product by average rating count

at least. But suppose I also tell you, which Amazon

does, that there are 500 reviews behind this average, and there are only two

reviews behind this average. This is a little extreme case to

illustrate a point, but in this extreme case, you can say that, well, then, I'm

not quite sure if I should trust this average of four stars anymore because

somehow the sample size is not big enough. Was there 500 of these maybe this is more

trustworthy and I rather prefer this 3.5 star product.

So, when can we trust an average rating? And, how can we incorporate the size of

the reviewer population? And, do we trust that 500 reviewers will

all be independent in the way that they evaluate?

It turns out that assuming independence and unbiased opinion, there is very

interesting way to incorporate the size of the review a population in the so called

Bayesian analysis. And we'll see how ranking can change once

you take that into account and we'll try to reverse engineer how Amazon does the

job by looking at the trend of the review scores, by looking at the size of reviewed

population and the reputation of the reviewers.

Now, these are what we called opinion aggregation problems, okay?

We try to summarize different opinions by many different users in a network into a

single number, and we know simple averaging doesn't always work.

The opinion aggregation becomes even more challenging if the result aggregation is a

binding resolution. So in question six, we will ask how could

Wikipedia even work? Wikipedia, as well know, is a free open

online and dynamic encyclopedia. While has many limitations, it by large

has worked very well over the years. Now, one of the issues that for certain

articles there's a lot of debates, certain political, religious article for example.

So, how can these contributors and the editors come to any agreement?

How can they form consensus? And we're going to look at consensus

modeling through two things, one is voting, the other is bargaining.

We'll look at the classical result of voting theory, okay?

By Arrow's is an impossibility results that says that, even when you are facing a

very mild situation, okay? For example, all the votes make perfect

sense. You can still come up with a, a voting

output, the final voting results that doesn't make sense.

For example, if there are three candidates, A, B, and C.

Then, the output may say that A is better than B, B is better than C, and C is

better than A, which is a cyclic and therefore logically inconsistent result.

And we'll look at how that could that become the case and how we can better

internalize so called network externalities to enable a more meaningful

voting system. Then, we'll also look at bargaining.

How two parties can bargain to try to reach an agreement even though the

agreement points may be different and therefore, their individual utilities, or

payoffs, or happiness will be different as a result.

Now, consensus formation is a tough subject, and we will see some gap between

the theory and the practice. Now, that gap actually will become even

bigger as we go into the next two questions.

Question seven is on how can we viralized the YouTube video?

Now, understanding, the viralization of a product or service art is something that

is very important and yet hard to accomplish.

And we will take a look at a particular model for a viral phenomena in a crowd,

where independence of opinion breaks down and we have what we call cascade of

information. After some point, everybody simply follows

what's already been done by the crowd at that point.

For example, you have may have one guy on the street corner, with a nosebleed, and

decide to tilt his head to look at the sky.

And then, if you got a few other people tilting their heads, then you may see that

many people start to aggregate and cause a cascade.

They all start tilting their head towards the sky to see what's going on up there.