The most important course in AGT.

Review

Auction

Single Parameter environments

env setup:

n participants
participant i has a non-negative private valuation vi for each unit of stuff
there is a feasible set X that consists of non-negative n-vectors that describe the stuff given to all participants.

some terms

auction - mechanism

potential buyers/bidder - participants/agents

bids - reports

valuations - valuations

split to allocation and payments

direct revelation mechanisms:

the participants report preference vector b. preference profile
allocation rule select a feasible allocation vector as a function of the preference profile.
payment rule decide payments vector p as a function of the preference profile

将机制设计分成两个问题：分配问题和支付问题

participants' behavior

utility u of participant i from participation in the mechanism with allocation rule x and payment rule p for preference profile b is:

\(u_i(b)=v_ix_i(b)-p_i(b)\)

we focus on payment rules that satisfy \(p_i(b)\in[0,b_ix_i(b)]\)

i.e. 1. participants always pay (never receive payments) 2. voluntary participation for a truthful participant

allocation rules

an allocation rule x for a single-param env is called implementable if there is a payment rule p so that the direct revelation mechanism (x, p) is DSIC.

可执行的意思就是对一个分配规则，存在一个支付方式使得其 DSIC

monotone: an allocation rule x for a single-param env is monotone if for every participant i and preference reports \(b_{-i}\) by the other participants, the allocation \(x_i(z,b_{-i})\) to participant i is monotone non-decreasing in her report z.

简单点说，单调性就是出价越高，越能可能得到（更多而不是更少）物品的意思

Myerson‘s lemma

迈尔森引理

an allocation rule is implementable iff it its monotone.

if the allocation rule x is monotone, then there is a unique payment rule so that the direct revelation rule (x, p) is DSIC and \(p_i(b)=0\) whenever \(b_i=0\)

the payment rule p is given by a specific formula.

Proof

assume that the allocation rule x is implementable through the payment rule p (mechanism (x, p) is DSIC)

let \(0\le y\le z\), when participant i has private valuation z and misreport y as her preference, the DSIC property implies that \(z\cdot x_i(z,b_{-i})-p_i(z,b_{-i})\ge z\cdot x_i(y,b_{-i})-p_i(y,b_{-i})\)
when participant i has private valuation y and misreport z as her preference, the DSIC property implies that \(y\cdot x_i(y,b_{-i})-p_i(y,b_{-i})\ge y\cdot x_i(z,b_{-i})-p_i(z,b_{-i})\)
by the two inequalities above: \(y\cdot[x_i(z,b_{-i})-x_i(y,b_{-i})]\le p_i(z,b_{-i})-p_i(y,b_{-i})\le z\cdot[x_i(z,b_{-i})-x_i(y,b_{-i})]\)

necessary inequalities due to DSIC implies that: \((z-y)\cdot[x_i(z,b_{-i})-x_i(y,b_{-i})]\ge0\).

i. e. the allocation rule x is implementable only if it is monotone

when the allocation rule is piece-wise constant 分段常数

jump in \(p_i(\cdot,b_{-i})\) at point \(z=z\cdot[jump\ in\ x_i(\cdot,b_{-i})\ at\ z]\)

For general monotone allocation rule

\(\frac{dp_i(z,b_{-i})}{dz}=z\cdot\frac{dx_i(z,b_{-i})}{dz}\)

assuming \(p_i(0,b_{-i})=0\), the payment rule is given by:

\(p_i(b_i,b_{-i})=\int_0^{b_i}z\cdot\frac{dx_i(z,b_{-i})}{dz}dz\) 具体推导很精彩，y 趋近于 z 时夹逼可得。

if allocation rule x is monotone the rule p is defined as

\(p_i(b_i,b_{-i})=\int_0^{b_i}z\cdot\frac{dx_i(z,b_{-i})}{dz}dz\)

then the direct revelation mechanism (x, p) is DSIC.

proof using a figure for piece-wise constant allocation rules. 出价-得到物品函数，矩形的上半部分面积就是支付的价格 payment，下半部分就是效用 utility
total valuation = utility + payment