. What is utility maximization problem?

It's an optimization problem. So we have an objective function which is

the sum of everybody's utility function. So, for each user I, we have a utility

function u sub I, which depends on some arguments.

Now, these arguments could be, say, throughput.

And application layer or rate the physical layer.

Later in, lecture thirteen soon we'll be talking about different layers and the

different, metrics of quality on different layers.

It could also be delay. It could be jitter, which is the variation

delay. It could be energy you spend.

It could be the distortion of your video. It could be any of these. .

Although, in most of our lectures, we'll be looking at rate of throughput in the

argument. In general, this is a function whether

it's a increasing or concave function, or not.

We'll say a few words about that in a minute.

And then, you're going to sum up across all the users of the utilities.

This is the sum utility or the so-called network utility, okay?

A network utility maximization or, in short, NUM.

We'll come back to this a few more times later in this course.

That's the objective function. What about the constraints?

There can be all kinds of constraints, technological constraints.

For example, a router cannot support, both large number of degree and large number of

bandwidth per degree. You know, it could be economic

constraints. For example, I am not willing to pay for a

certain cost in order to provide that much bandwidth supply.

And by the way, when we talk about the word, bandwidth, okay we often actually

mean capacity in bits per second rather than, the width of the frequency band

being used. Okay?

Even though a wider band other factors remaining constant implies a bigger

capacity. But these are two physically, conceptually

different terms. But, so happens increasing a lot of people

use the word bandwidth. I guess it's a cooler name than the word

capacity. So sometimes we stick to that incorrect

terminology because it's used almost universally.

Now what about the variables? Well, if these, depends on what's your

argument in an objective function, okay? If these are the arguments, maybe our

variables could be the raise on purpose themselves or it could be some other

design factor that would impact these different metrics.

So maximizing the summation of utility function of some arguments is subject to

some kind of constraint that says the variables denoted by some vector x and y,

live in certain constraint space x and y and so on.

Now, good to formulate and try to solve, hopefully distributively of many of these

problems. So, let's look at this utility function,

each term. Okay?

Let's say the argument is xi. Could be, say the data rate for a

particular n user I. And the shape of the function is denoted

by, okay, this function u sub i. So what kind of function could this be?

You see three functions, curves here in this plot.

Ux over x is a single variable function. This function a is, let's say a

logorithmic function. We'll see that there is a special fairness

notion associated with log functions in a minute.

So, it is quite nice. It's smooth, increasing, and, concave.

But you see this curve, B here is actually not smooth cuz there is a jump at this

point. Below this point, you get no utility.

Above this point, you get a strictly positive, constant utility,

Okay? So there is a jumping point.

Now, graph C is interesting. It's got some concave.

A convex part, and then it becomes concave to the point of bending completely flat.

Meaning that to give me more amps, it doesn't increase my utility any more.

So it goes through a convex. Part.

Then you went through a concave part, including part of which that is completely

flat. So not only does arguments of

geo-functions can be of various strengths, the shape can also be quite different,

okay. So, in particular, is the smooth, we often

deal with smooth functions. In fact, in all examples, you will see it

will be smooth, but it doesn't have to be. Is it increasing?

Pretty much always increasing because we're talking about something good; it's a

utility function. If you are talking about something that

measures how bad it is against some argument maybe the answer is different.

And third, is a concave nod. Now, increasing the nod is talking about

the first derivative, the utility function.

We say, you know it is non-negative. What about concavity or convexity?

And this is talking about the second derivative, okay.

So, concave means that it is smaller than equal to zero.

Whereas convex means, as you may recall from lecture four.

That the second root is bigger than or equal to zero.

Now of course this is talking about a single variable.

If a multivariable function then, this is a gradiant vector.

And these second derivatives is not a scaler anymore, but the Hessian matrix.

Again back in lecture number four. So,

Is the second derivative positive or negative?

By the law of diminishing. Marginal.

Return. Which roughly speaking says that, okay, as

the argument becomes bigger and bigger, eventually.

Even if you get happier and happier, the rate with which you become happier, will

be going down. So, for example, this kind of function is

still going up, up, up, it never drops. But, how fast you'd go as a function of a

unit increase in x x's that slows down. Okay?

In other words, the second derivative is negative,

Okay? This is an increasing function, but the

rate of increase is actually negative. So.

This is usually the case as a concave function.

But, it doesn't have to be concave at the beginning.

It says, eventually it will bend over but before eventually, it can go actually like

convex and then concave with inflection point.

Like what we observed in some of lecture seven and lecture 8's curves in diffusion

models. Okay?

And, some of the other influence models in the crowd.

So you can also have a sig model function with both convex and concave part.

In general, if a smooth increasing in concave, then it's a much nicer function

to deal with mathematically. Where do these utilities functions come

from? Usually there are three ways, one is you

can run an experiment with real human beings in a focus group study.

Put them in sofa, give them pizza and then say, well, please watch these videos or

listen to these voice calls. And then you rank them, you rate them one

to five stars. And then you vary the different kind of,

of voice cause and medias you present to them.

So these lead to often what's called MOS, Score Mean Opinion Service Score.

Okay? You run psychological experiment.

The second. Reason why certain utility functions are

picked is because of what they represent in demand function.

Okay? Utility function and demand function, in

some sense, are two sides of the same coin.

Because we're going to model individual decision making as a net utility

maximization. Very similar to what we saw in lecture two

with the auction model as a game. Where we say that, each individual here

says, I will get this much utility, okay? I'm user I.

U I of XI, good but this is now free lunch, there is no free lunch, I have to

pay something for example PI per unit of whatever I'm getting see?

Bandwidth or rate is per second, so for each bit per second I have to a unite

price PI and I'm getting this much XI in volume, so the total cost for me is piXI.

Times xi. This is how much I'm getting, this is how much I'm paying, the

difference is net utility. And that is what I would like to maximize

over my individual choice, x i. Okay, so in the market, you'd give me the

price. I react to the price by picking xi.

Well, if this u is a nice function, a smooth increasing and concave, then this

is a nice concave maximization xi, concave part, linear part.

So we can just take derivative and say u prime of x suppressing the subscript I for

simplicity notation, okay, minus a p. That's the derivative, and let it be zero.

That means, u prime of x = p. If a particular x such as father's

equation, call that x star. Then, that is the induced the demand,

induced to buy this price P given to me. And it turns out that utility's first

derivative is an invertible and a decreasing function because of our model

of utility function. So, x star is u prime inverse as a

decreasing function of the price P. So we call this u prime inverse, demand

function d. So d is a u prime inverse.

Now, give me a utility function. And take the derivative, invert it.

You've got demand function. Give me demand function.

I can also reverse engineer the utility functions.

Coming this way from utility demand function, you can do a simple exercise of

how alpha fair utility function coming up. A particular special case is just utility

being log of x. Okay?

They are the reason and so demand function is just one over p,

Okay? Easily convinced south about that.

And then, in lecture fourteen, we will talk about the other direction, give me a

demand function. I figure out, then try to reverse engineer

the underlying utility function. And the key concept in modelling demand is

so-called demand elasticity. Okay.

Essentially your price sensitivity. We know.

That demand is a function of price P. And if I look, take, look at the

derivative. Okay?

Demand may, depends on other things, too. So the partial derivative is a function of

p over p. So, partial DP, partial P.

This is sort of like my price sensitivity, right?

Price goes up, how much is my demand dropping.

But I also want to normalize it. And so, I'm going to normalize it by DP

over P. This normalized version of price

sensitivity is called a demand elasticity and often represented by the symbol, etha.

For example what is etha of log utility function?

We know the demand elasticity is just one over p.

You plug in this normalized partial derivative against p.

You see that either is actually is exactly one which is quite interesting, cuz it's

actually independent of p, Okay?

So, the second way to model utility is through so-called depend function, okay

The third way is through your concern on fairness.

Again, later in lecture twenty, we'll devote, devote the whole lecture on

different notions to quantify fairness. But, today we start introduction there of

that quantitative approach to fairness. And this introduction says that, there is

a family of functions, called alpha-fair utility functions.

Is not a function, is actually a whole family of, of functions,

Okay? And is parameterized by a single, single

scale alpha greater than zero. And that's why it's called alpha fair

utility function. What is that alpha fair utility function?

Well, first, let's define what is an alpha fair resource allocation.

Well see, suppose you tell me there is a vector x let's just say x,

Okay? So vector allocates some good resources

x1, x2 up to xn among the end users competing against each other.

And I say, that this is a particular function, vector is that alpha fair

allocation, vector if here's the definition, okay.

If for any other feasible vector y or such y.

If I look at the difference for each user, Between getting something from x factor

versus getting from the y allocation. And then I normalize it by Exxon through

the power alpha. There's where the alpha comes in.

That's some kind of alpha parameterized normalization of the difference in

drifting away from x allocation to y allocation.

And then I look at the joint impact, the collective impact to all the users in the

system summing over r. If this summation which is a single

scaler, is negative, Okay?

Less than, equal to zero then I say, this vector x is alpha-fair vector.

Now, that's a mouthful for definition. Let's process it again.

We say a vector x is alpha-fair if for all any other feasible allocation y, you can't

give me an unfeasible allocation and ask me to compare, okay.

Any other feasible allocation y, if I look at the collective.

Alpha profit must normalize the drift from x2 such vector Y, is always a bad thing.

Okay, the sum is negative, then, I say this vector indeed is alpha fair

allocation. All right, now you can disagree with the

definition, but it turns out to be a useful definition and therefore a good

definition. So, what about our utility function?

This is a vector not a function. Well it turns out that without proving

this, we'll just state the, the result, it says, if you maximize the following

parameterized utility function parameterized by alpha, so I'm writing

alpha in the subscript for this utility function as a function of x.

If you maximize this function, what does it look like?

What is a branching definition? It looks like it's simply, x to the power

one minus alpha, over one minus alpha. If alpha is not one, okay.

If alpha is one, this denominator is not defined, but you can use Lapatel's rule,

and see that when alpha is one, this actually is log of x,

Okay? Now see the familiar and important special case of log utility.

So, if this is the definition of your utility function,

Then maximizing such utility function will lead to an answer of the optimizer of x

star that satisfies the definition of alpha fair allocation.

That's why we call this the alpha fair utility function.

Another name for it is called Isoelastic Utility Function.

Okay. Why isoelastoc? It gets, gets back to our

notion in the last slide, Okay?

In a homework problem I think you easily verify that if you take this definition of

u of x, you will see the resulting demand function,

Okay? And then that implies the elasticity.

It is actually one over alpha. In particular, when alpha is one for large

utility, the corresponding demand function is just one over p and the corresponding

normalized demand elasticity is just one over alpha.

That is just one. In that case, one alpha is one.

Okay. But in general, for other non-one alphas

is one over alpha s eta. That means the elasticity of demand is all

independent of everything else, okay? Except the shape.

This problem to alpha. That's why its called isoelastic.

Later, we'll see many good uses of isoelastic or alpha fair utility function.

Including the following special case. When alpha is zero, what do we have?

That's simple. We're just looking at the allocation

itself. It's just of sum allocation for example,

some rate in maximization. When alpha is one, that's a log utility

function. It turns out that at least two of what's called a proportional fare.

If you look at this definition here, when alpha is one it means that your

normalization is simply xi itself, you're not trying to skew the shape by any means.

And, whether you like the definition or not, you can see why this is called alpha

proportional fair'cause proportional back to normalized by X.

So, when alpha is one, you have this special case called proportional fairness.

Now, when alpha's really big, for example, alpha approach infinity, then it turns out

that it approaches what's called a max-min fair.

I will later talk more about fairness, so let's leave it just like that for the

moment. And conclude this part of the video module

with simple application of this utility model,

Okay? Whether it comes form focus group study or

fairness or demand elasticity. Apply this simple utility model to talk

about a very important phenomenon called the Tragedy of Commons.

Now, this was first formally mentioned by Lloyd a long while back, 1833.

And then codified and popularized by Harding's article in 1968.

Now this article had other kinds of provocative and somewhat controversial

arguments. Tragedy of Commons is only one small part

of it but we have seen a liberal use of this term, tragedy of Commons, quite a few

times. In lecture one, when we talk about power

control, interference. That's the trade of commerce in the air.

When we were in lecture two okay, transferred commerce in terms of second

prize correctly internalizing the externality imposed on other option

competitors. In lecture, I think six, okay, voting

theory, okay. The K degree of externality imposed on

other voters and the need for something like voter count.

And later, in chapter lecture, I think, fourteen for TCP, fifteen for P2P and

eighteen for WiFi. Okay?

In all of these cases for tech networking discussion we will see a different

manifestation of Tragedy of Commons but the reason it was called Tragedy of

Commons was because it was a, a thought experiment, okay. Just like this binary

number experiment in lecture seven. It says that suppose that you've got a

piece of common grassland as the commons, okay, and there are different farmers and

each farmer says okay, should I get another cow or not?

Okay, here's a cow. Well, it looks like a, a mouse, but let's

say it's a cow, right. So, should I get a cow now?

Well, if I get a cow, the cow's going to need to eat grass, , okay.

But it, you know, the cost of eating the grass is like if there are n farmers, is

like one over n, proportional to that. But the benefits to me of the milk and

maybe selling the cow for its meat later down the road is one, one unit, okay.

So what's going on here is that if I look at my selfish maximizations, that I got a

utility okay, U of X. Alright,

And now I got to pay the price. That means I have a demand.

So function of the price. The price is just one unit.

And in this case, a rational farmer would say, I should get another cow.

And the same argument keeps on going, I should get, get another cow, get another

cow. And every farmer thinks the same way.

That won't happen. Well, the Tragedy of Commons happens.

There will be so many cows here that, at least to over utilization of this

grassland, okay? And, once it's overgrazed, then the

grassland will eventually deplete and the cows will die.

So it's actually a bad outcome for all the farmers.

This is I guess the third time in this course encountering this situation.

It's a little paradoxical that each selfish behavior actually lead to

collectively the worst phenomena for every individual.

So, what's wrong? Well, what's wrong's that the price wasn't

set right, okay? Instead of setting it to be one, maybe you

should set it to be proportional to n. And these this change will lead to the

demand function operating not on the price of one, okay but on the price of n.

Okay? Now, this is another example illustrating,

what we call negative externality, okay? It is externality just means that your

behavior and my behavior are coupled together in this impact.

It's negative, because you get another cow, it's, going to damage my prospect.

And one way to so-called, internalize, in contrast to externality.

Internalize externality. Meaning that to mitigate its negative

effect is through pricing. Later in, chapter fourteen we'll look at

mathematical theory in advanced material of Lagrange Duality that says basically,

if you price, properly enough then you often, you can internalize the negative

externality. Alright, so that's a long introduction of

the utility model. Now going to take the utility maximization

model to provide three reasons why usage based pricing for internet access make

sense. And what can we do to visualize these

three reasons, okay? We're going to visualize these three

reasons through three different demand price diagrams.

Utility, Demand, and Fairness

Networks: Friends, Money, and Bytes

Meet the Instructors