You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions. All the features of this course are available for free. It does not offer a certificate upon completion.
Auction Definitions
Loading...
来自 Princeton University 的课程
Networks: Friends, Money, and Bytes
81 个评分
从本节课中
How Does Google Sell Ad Spaces?
How does Google sells the ads that appear on its search results page through auctions? We learn about different types of auction mechanisms, including those for single and multiple items. QUESTION 3: We explore PageRank, the famous algorithm that underlies how Google orders its list of search results whenever we type in a query.
与讲师见面
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
Before we can analyze auctions, let's first understand, when will auctions be
useful? So take a step back.
Now, auction is one of the many ways to do resource allocation in a crowd or network.
We'll see many other examples later in the course.
And in an auction, it's particularly useful when the seller does not really
understand who really should get the item or the items, and how much to charge.
So when you're confused or not sure about this, these questions, then, you want to
search for the right price. For the right price, then maybe auction is
a good mechanism for you. When you're not sure about the pricing
signal. And most of the analysis of auctions
assume two kinds of behaviors about the valuations.
Now, you may recall C times R, click through rate expected times the average
revenue per click that was the valuation in the case of Google selling ad spaces.
And when you're talking about other kinds of auction, could be a house, could be a
the spectrum by the government for 3G license, or any other item.
Right. You have some kind of intrinsic view by
yourself. Subjective, but you know it.
Vi for the Ith buyer as the valuation. I would assume that these valuations are
private, meaning that the auctioneer or the other potential buyers do not know
your valuation, neither do you know the others.
And furthermore, it's independent. So VI, it just depends on I.
It doesn't depend on the VJs where J is not = to I.
And of course, in many cases the valuation is not completely private, for example, on
eBay as we have seen in an example, you get a glimpse of other people's potential
valuation, just by watching the announcement of the asked prices.
And whenever there is a secondary market. For example, houses, for closure houses on
auction block. The secondary market existence means that,
when you think about evaluation of a house, is influenced by other people's
evaluation, if you want to ever sell it again in the secondary market.
But, having said that, lets assume private and independent evaluation for what we
need to do with add space auctions. So in order to compare one auction
mechanism with another, one allocation with another, we'll have to think about
the metrics to compare them with. So what does each party in this ecosystem
want? For the seller obviously the most
important one is the revenue. How much do I generate by this particular
way to allocate and price? For the buyers, each of them, it is the
payoff that matters. It's the difference between the valuation
of getting this item, and the price they have to pay as the Ith buyer.
And later we'll look at the difference between happiness and the price.
We call that net utility. In this case we call this a payoff.
Now of course valuation is determined by you and as I said, we assume it's
independent of others, but the price is not completely determined by you, it's
determined by what other buyers do and the rules of this auction.
So the auction will decide what prices you have to pay.
So clearly if you know the auction rule changed, you may change your bidding
behavior because your payoff is the difference between the valuation and the
price. Now the auction designer, which could be
the seller itself will like to be sure the auction induces an efficient and fair
outcome. Now how do we define efficiency and
fairness. We'll see some example in other contexts
later in the course. But for today we will take proxy, as a
proxy the truthful bidding property that says if you view this item with a
valuation of VI then just bid, that's your bid exactly the I.
You think that sounds pretty intuitive. Actually, you will see that, in quite a
few cases, that's not necessarily true. So today, we will simplify the picture,
and say that truthful bidding is so desirable that we want to maintain it.
But actually, it may not lead to revenue maximization or payoff maximization in all
cases. So that's how we're going to compare
auctions. And then, we're going to analyze auctions
as games. Just like last lecture, when we talked
about disputed power control, and look at the power control game in cellular
networks. We can view auctions as games.
As mentioned, each game is defined by three tubbles.
Set of players, strategy space per player, and a payoff function per player.
So who are the players in the auction game?
Simple. It's just the set of buyers and their end
of them.. We'll assume that it's a fixed seller.
And who are they, what are the strategy spaces?
For each player I, each buyer I, basically, there is a set of bids that
she's willing to submit. I'll make this simple by saying it can be
any positive real number. What is interesting is the payoff
function. First of all there are two possible
outcomes. You may get the item in the single item
case. In a multiple item case you may get some
item okay, or maybe you don't get it. Now this outcome of allocation is
determined clearly by the collection of all the bits submitted by everyone.
So this defined by the vector b, not just your own, not just bi, but all the b's.
B1, B2 up to Bn. And in the case that you get the item.
I don't know, congratulations, now let's take a look at your payoff.
It is your valuation minus the price you pay.
Again, the price is a function of the entire b vector.
And the auction designer will determine the shape of this function.
How do you map the whole vector bids into a single number called the price to the
winner? We'll come back to that in a minute.
But whatever that might be, this difference is your payoff.
[inaudible] UI, the notation for payoff, which clearly is a function of co-vector b
as well. That's the coupling of all the actions by
the buyers. But in case you don't get it, then you get
nothing. You get zero, because you pay nothing, you
receive nothing. Now, vi minus pi could be positive, could
be negative, could be zero. We don't know, depends on what is the
valuation and what is the price. Again, valuation is assumed to be private,
no one knows, and independent, doesn't depends on anyone else.
But the prize clearly depends on others' behavior, the others' bidding behavior.
And what is interesting is that, by deciding a different function that maps
bidding behavior to prize, you will, in turn, induce different bidding behavior.
Okay. Different auction rules will induce
different bidding strategies in this auction game.
For example, lets take a look at a, a simple example.
Coming back to this. This is the definition of payoff function,
branching to two possibilities, determined by the b vector in one case, you look at
the difference. This part of difference determined by the
b vector. So, let's just look at this part.
P I as a function of vector B. And maybe I should just say let it be B I.
Okay, your own bid so if you win it then [inaudible] is the first prize.
You pay the first prize, and that is exactly what we saw.
And, it sounds quite intuitive. Okay, see what envelope, then just, you
know, you give it to whoever is the highest bidder and that decides the
allocation. As to the pricing, just pay the price that
person bid it. Then in this case your payoff, UI, is just
VI minus BI. Right?
Your own valuation minus your own business, if you get it.
So you may think what should I bid. Well, if I bid bigger than my valuation,
I'll get a negative utility or payoff. That's not good.
If I bid exactly as my valuation that's not good either cuz I get zero.
I may as well just not bid the item. So, I'm going to bid a little below the I,
but if I bid too low, I may not get item, so how should I bid in order to maximize
my payoff? And was impact on Google's revenue that's
actually pretty complicated question. We won't have time to talk about that
today. Instead we're going to look at the
intuitively not making sense but actually very sensible second price this says.
The price you pay is actually somebody else bid.
And this J user is exactly the second highest bidder.
And your utility or payoff, trying to differentiate U from V is your V minus
this BJ somebody else J. And it so happens that by decoupling the
winning and losing decision from the actual price, you pay.
Remember, utility depends on both allocation and the pricing.
Decoupled allocation decision and the pricing decision actually induces truthful
bidding behavior from all the potential buyers.
