Algorithmic Game Theory and Applications
Lecture 18:
Auctions and Mechanism Design II:
a little social choice theory, the VCG Mechanism, and Market Equilibria
Copyright By PowCoder代写 加微信 powcoder
Reminder: Food for Thought: sponsored search auctions Question
How should advertisement slots on your Google search page be auctioned? You may have already heard that Google uses a so-called
“Generalized Second Price Auction” mechanism to do this. But why do they do so? Is there any “better” way?
Before we can even begin to address such questions (which are in fact largely outside the scope of this course), it is useful to get a better understanding of the broader picture in economic theory within which auction theory and mechanism design operate.
Again, reference reading for today’s lecture includes: Chapters 9, 11, 12, 13, & 28 of AGT book.
Also very useful are the revelant chapters of the excellent textbook:
A. Mas-Colell, M. Whinston, & J. Green, Microeconomic Theory, 1995.
Lecture 18 2 / 18
Walrasian Market Equilibrium
An Exchange Economy
n agents, and m divisible goods (commodities, serices, etc.).
Each agent i starts with an initial endowment of goods, wi = (wi,1,…,wi,m) ∈ Rm≥0.
Each agent i has a utility function, ui(x), that defines how much it “likes” a given bundle x ∈ Rm≥0 of goods.
Assume utility functions satisfy certain “reasonable” conditions:
(1) Continuity; (2) Quasi-concavity; (3) Non-satiation
Assume agent endowments satisfy certain “reasonable conditions”.
E.g., each agent has a positive endowment of every good. (Much less
suffices: e.g., each agent has something another agent “wants”, and
the graph of this is strongly-connected.)
Give a price vector, p ≥ Rm≥0, each agent i has an optimal demand
set, Di (p) ⊆ Rm≥0. This is the set of bundles of goods, xi , that
maximize agent i’s utility, and which i can afford to buy at prices p
by selling its endowment wi at prices p.
Lecture 18 3 / 18
Background: existence of market equilibrium Market (price) equilibrium for an exchange economy
A non-zero price vector, p∗ ≥ 0, together with bundles, xi∗, of goods for each agent i, constitutes a market (price) equilibrium for an exchange economy, if at prices p∗, for every agent i, xi∗ is an optimal demand bundle, and moreover with these demands the market clears (i.e., basically supply = demand). In other words:
For all agents i, xi∗ ∈ Di(p∗). (All agents optimize utility at prices p∗) i xi∗ ≤ i wi . (Demands do not exceed supply for any commodity.) Furthermore, for all goods j, if (i xi∗)j < (i wi)j, then pj∗ = 0.
(In other words, only free goods can have excess supply.)
Lecture 18 4 / 18
Background: existence of market equilibrium Market (price) equilibrium for an exchange economy
A non-zero price vector, p∗ ≥ 0, together with bundles, xi∗, of goods for each agent i, constitutes a market (price) equilibrium for an exchange economy, if at prices p∗, for every agent i, xi∗ is an optimal demand bundle, and moreover with these demands the market clears (i.e., basically supply = demand). In other words:
For all agents i, xi∗ ∈ Di(p∗). (All agents optimize utility at prices p∗) i xi∗ ≤ i wi . (Demands do not exceed supply for any commodity.) Furthermore, for all goods j, if (i xi∗)j < (i wi)j, then pj∗ = 0.
(In other words, only free goods can have excess supply.)
Theorem ([Arrow-Debreu, 1954])
Every exchange economy has a market (price) equilibrium.
Lecture 18 4 / 18
Background: existence of market equilibrium Market (price) equilibrium for an exchange economy
A non-zero price vector, p∗ ≥ 0, together with bundles, xi∗, of goods for each agent i, constitutes a market (price) equilibrium for an exchange economy, if at prices p∗, for every agent i, xi∗ is an optimal demand bundle, and moreover with these demands the market clears (i.e., basically supply = demand). In other words:
For all agents i, xi∗ ∈ Di(p∗). (All agents optimize utility at prices p∗) i xi∗ ≤ i wi . (Demands do not exceed supply for any commodity.) Furthermore, for all goods j, if (i xi∗)j < (i wi)j, then pj∗ = 0.
(In other words, only free goods can have excess supply.)
Theorem ([Arrow-Debreu, 1954])
Every exchange economy has a market (price) equilibrium.
Their proof is non-algorithmic. It crucially uses a fixed point theorem.
Lecture 18 4 / 18
two quotes
(MSR), 2006: “If your laptop can’t find it, then neither can the market.”
Mas-Colell,Whinston, & Green, 1995 (standard graduate text in Microeconomic Theory): “A characteristic feature [of] economics is that for us the equations of equilibrium constitute the center of our discipline. By contrast, other sciences put more emphasis on the dynamic laws of change. The reason... is that economists are good at recognizing a state of equilibrium, but are poor at predic- ting precisely how an economy in disequilibrium will evolve...”
Or, to paraphrase: “Modern economic theory is largely non-algorithmic.” By contrast, computer science is very good at “dynamics” (algorithmics).
A sizable portion of Algorithmic Game Theory research, broadly speaking, aims to remedy this difficiency of modern economic theory.
Lecture 18 5 / 18
A side question: Do we really need money?
Lecture 18 6 / 18
A side question: Do we really need money?
Note that money is itself extraneous to the goals of agents in an exchange economy. Why do we need it?
Couldn’t we achieve the same “goals” of the market without money?
In other words, couldn’t we organize a “barter economy” to conduct a simultaneous exchange of goods between all agents, in a way that achieves Pareto optimal bundles of goods for every agent?
Recall: Pareto optimal means that there is no other reallocation of everyone’s goods in which everybody’s utility is at least as high, and somebody’s utility is strictly higher.
Note: the The First Fundamental Theorem of Welfare Economics says that allocations of goods in any market equilibrium are Pareto optimal.
Lecture 18 6 / 18
A side question: Do we really need money?
Note that money is itself extraneous to the goals of agents in an exchange economy. Why do we need it?
Couldn’t we achieve the same “goals” of the market without money?
In other words, couldn’t we organize a “barter economy” to conduct a simultaneous exchange of goods between all agents, in a way that achieves Pareto optimal bundles of goods for every agent?
Recall: Pareto optimal means that there is no other reallocation of everyone’s goods in which everybody’s utility is at least as high, and somebody’s utility is strictly higher.
Note: the The First Fundamental Theorem of Welfare Economics says that allocations of goods in any market equilibrium are Pareto optimal.
It is intuitively clear that such an exchange is difficult to do without money. We shall see that some things become impossible to do without money.
Lecture 18 6 / 18
Background: Impossibility theorems in social choice theory
Let C be a set of outcomes, and let L be the set of total orderings on C. A social choice function is a function f : Ln → C.
f can be strategically manipulated by player (voter) i, if for some ≺1,...,≺n∈L,wehavec≺i c′,andc=f(≺1,...,≺n),andthere existssomeotherordering≺′i suchthatc′ =f(≺1,...,≺′i,...,≺n).
f is called incentive compatible (strategy-proof) if it can not be strategically manipulated by anyone.
f is a dictatorship if there is some player i such that for all ≺1,...,≺n,f(≺1,...,≺n)=ci,whereci isthemaximumoutcome for player i, i.e., ∀b ̸= ci, b ≺i ci.
Theorem [Gibbard-Satterthwaite’73,’75]
If |C| ≥ 3, and f : Ln → C is an incentive compatible social choice function
which is onto C (i.e., all outcomes are possible), then f is a dictatorship.
Lecture 18 7 / 18
Arrow’s Theorem
The Gibbard-Satterthwaite Theorem is closely related to the following famous theorem:
Arrow’s Impossibility Theorem
There is no “really good” way to aggregate people’s preference orders (over ≥ 3 alternatives) into a societal preference order.
“Really good” here means it should satisfy the following three criteria: Unanimity: if everybody has the same preference order, then that
should become the societal preference order.
Independence of irrelevant alternatives: The societal preference between any pair of outcomes a and b should depend only on the preference between a and b of all individuals, and not on their preferences for other alternatives c ̸= a, b.
Non-dictatorship: no individual’s preferences should dictate the societies preferences.
Lecture 18 8 / 18
Let’s bring money back into the picture
Let V be the set of “voters”.
Suppose that instead of a “preference ordering”, each voter i ∈ V has a (non-negative) “monetary value function”: vi : C → R≥0, where vi(c) says how much money a win by candidate c is worth for voter i.
Suppose we want to choose a candidate c∗ that maximizes the total value for the entire voter population, i.e., we want to choose:
f(v1,...,vn) = c∗ ∈ argmaxvi(c)
But voters could be dishonest and lie about their true value function. (Voter i can declare a different non-negative valuation function vi′.)
Question: Can we incentivize the voters to tell the truth?
Lecture 18 9 / 18
Let’s bring money back into the picture
Let V be the set of “voters”.
Suppose that instead of a “preference ordering”, each voter i ∈ V has a (non-negative) “monetary value function”: vi : C → R≥0, where vi(c) says how much money a win by candidate c is worth for voter i.
Suppose we want to choose a candidate c∗ that maximizes the total value for the entire voter population, i.e., we want to choose:
f(v1,...,vn) = c∗ ∈ argmaxvi(c)
But voters could be dishonest and lie about their true value function. (Voter i can declare a different non-negative valuation function vi′.)
Question: Can we incentivize the voters to tell the truth? Yes, if we are allowed to ask them to pay money!
Lecture 18 9 / 18
The Vickrey-Clarke-Groves (VCG) Mechanism
Each voter i ∈ V is asked to submit their nonnegative valuation function, vi′. (vi′ may or may not be i’s actual valuation function vi.)
The mechanism then computes an optimal candidate, f (v1′ , . . . , vn′ ) := c∗, that maximizes total value:
f(v1′,...,vn′):=c∗ ∈argmaxvk′(c)
This candidate c∗ is chosen as the winner of the election. Moreover, each voter i has to pay an amount pi(c∗) to the
mechanism, which is independent of vi′, defined by:
pi(c∗):=(max vj′(c′))− vj′(c∗)
j∈V \{i} j∈V \{i}
Key Point: These payments align the incentives of all voters: each voter i, even knowing the valuation functions vj′ declared by voters j ̸= i, will want todeclareafunctionvi′ thatyieldsawinnerc∗ =f(v1′,...,vn′)which
maximizesvi(c∗)+k∈V\{i}vk′(c∗).So,itshoulddeclarevi′ :=vi.
Lecture 18 10 / 18
Basic properties of VCG Proposition
Letf(v1′,...,vn′)=c∗ betheoutcomechosenasthewinnerbytheVCG mechanism, based on their declared (non-negative) valuation functions v1′,...,vn′. Then for every voter i both its payment pi(c∗) and its purported utility ui′(c∗) = vi′(c∗) − pi (c∗) are non-negative, i.e.:
1.) p(c∗)≥0 and 2.) u′(c∗):=v′(c∗)−p(c∗)≥0 i iii
Proof: 1.) pi (c∗) = (max vj′(c′)) − vj′(c∗) ≥ 0.
2.) vi′(c∗) − pi (c∗)
= (max v′(c))−(max v′(c′))≥0
j∈V \{i} j∈V \{i}
= ( vj′(c∗)) − (max c′∈C
j∈V j∈V\{i}
c∈C i c′∈C j
i∈V j∈V\{i}
(The last ≥ 0 holds because we require vj′(c) ≥ 0 for all j and all c ∈ C.) Lecture 18 11 / 18
VCG is incentive-compatible (i.e., strategy-proof) Theorem ([Vickrey, 1961],[Clarke, 1971], [Groves,1973])
The VCG mechanism is incentive compatible (i.e., strategy proof).
In other words, declaring their true valuation function vi is a (weakly) dominant strategy for all players i.
Proof: Suppose players declare valuations v1′ , . . . , vn′ . Suppose player i ’s truevaluationisvi.Letc∗ =f(vi,v′ ),andletc′′ =f(v′,v′ ).Recall
c ∗ ∈ arg maxc vi (c ) + k ∈V \{i } vk′ (c ). In other words, for all c ∈ C ,
vi (c∗) + k∈V \{i} vk′ (c∗) ≥ vi (c) + k∈V \{i} vk′ (c). Thus, ui (c∗) = vi(c∗)−pi(c∗) = vi(c∗)+( vk′(c∗))−(max vj′(c′))
k∈V \{i} vi (c′′) + (
c′∈C vk′ (c′′)) − (max
vj′(c′))
vi (c′′) − pi (c′′) = ui (c′′).
Lecture 18
Example: Vickrey’s second-price sealed-bid auction
Recall: There is a single item being auctioned.
Each bidder, i, declares its own monetary value (price), bi, for getting
The highest bidder, say i∗, gets the item, and pays the second highest
bid price, say p∗ = bj.
The overall utility for bidder i∗ who got the item is vi∗ − p∗.
Both the valuation and payment (and thus utility) for all others who don’t get it is 0.
Recall: Theorem: the Vickrey auction is incentive compatible: every bidder i’s dominant strategy is to declare its true valuation vi.
In fact, this is precisely the VCG mechanism, applied in the setting of a single-item auction, where the set of “candidates”, now “outcomes”, is given by “who gets the item?”.
The machanism makes sure that the item goes to the person who values it most, because that maximizes i vi(outcome).
Lecture 18 13 / 18
An ascending price auction closely related to Vickrey’s
In practice, Vickrey’s sealed-bid auction are often not used.
There are a variety of (good) reasons for this. (For example, bidder valuation may not be independent. This leads, e.g., to Winner’s curse. Thus information about other people’s valuation matters a lot.) Instead, often an Ascending price (English) auction is used:
The price starts at a low reserve price, and is repeatedly incremented by a small amount, ε > 0, until all but one of the bidders drops out saying “I don’t want it at that high a price”.
At that point, the one remaining bidder gets the item, at the last price.
It is intuitively clear that if we model these auctions as (Bayesian) games with private valuations then the outcome of the English auction should be “essentially the same” as that of the Vickrey auction.
Things change a lot if we model them with interdependent valuations. (A model we haven’t discussed: players don’t know exactly their own valuation. Their valuation depends on everybody’s private signal.). That is one reason why an English auction is often preferred.
(Because it diminishes phenomena like winner’s curse.)
Lecture 18 14 / 18
Why not use VCG for multi-item auctions?
Suppose there is a set J of items, with |J| = k > 1, up for auction.
Suppose each bidder i is “single-minded” and values only one subset Ji ⊆Joftheitems,sohehasavaluationvi(J′)=vi∗>0forany
J′ ⊇ Ji, and vi(J′) = 0 for all J′ ̸⊇ Jj. (So, we can specify valuation vi by just giving (vi∗, Ji ).)
Note: if Ji ∩ Ji′ ̸= ∅, then auction can’t satisfy both bidders i and i′. Suppose, we want the auction outcome to maximize total value for all
Why not use the VCG mechanism?
A problem: for VCG we have to compute an outcome, c∗, that maximizes the total value i vi (c∗).
This is NP-hard in general, even when we always have vi∗ = 1: easily encodes maximum independent set.
Lecture 18 15 / 18
Proof of NP-hardness
Here is the simple reduction from the maximum independent set problem: Let G = (V,E) be any graph, with V = {s1,…,sn}.
We associate with each edge e ∈ E an item in the auction.
We associate a player (bidder), i, with every vertex si ∈ V.
We let Ji be the set of edges adjacent to vertex vi .
We let vi∗ = 1 for all i (i.e., every player has value 1 for its desired set).
Then finding an outcome c∗ of the auction (i.e., a collection of disjoint sets Ji , indicating those bidders who get their desired set) such that this outcome maximizes i vi(c∗) is equivalent to finding a maximum independent set in the graph G.
Lecture 18 16 / 18
Algorithmic Mechanism Design
So, achieving incentive compatibility by means of VCG may involve solving NP-hard problems.
Why not try the standard approximation approach used for coping with NP-hardness?
Problem: if the mechanism outputs only an approximate solution, and yet tries to compute VCG-like prices for it, then incentive compability totally breaks down.
In some auction settings (like single-minded bidders), it is possible to design non-VCG mechanisms which are: (1) incentive compatible, (2) where prices and allocations are polynomial-time computable, and (3) such that the outcome yields a total valuation within the best possible approximation ratio of optimal (any better approximation ratio would be NP-hard).
These are the kinds of problems addressed by Algorithmic Mechanism Design.
Lecture 18 17 / 18
There are other multi-item auction settings where the (exact) VCG mechanism remains useful and can be efficiently computed.
One important and beautiful example of this is Matching markets (multi-item unit-demand auctions).
The setting of matching markets also gets us much closer to the setting of sponsored search auctions (also known as position auctions). These can be viewed as special subcases of matching markets and unit-demand auctions.
We will discuss these next time.
We will then end our lectures by presenting a general formal framework for Mechanism Design.
Lecture 18 18 / 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com