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