Multi-parameter mechanism design

Multi-parameter environments

$n$ strategic participants or agents
finite set $\Omega$ of outcomes (could be very large)
each agent $i$ has a private non-negative valuations $v_i(\omega)$ for each outcome $\omega\in\Omega$ .
the social welfare of outcome $\omega\in\Omega$ is defined as $\sum_{i=1}^nv_i(\omega)$ .

Single-item auctions

$n$ bidders (agents)
set $\Omega$ consists of $n+1$ possible outcomes
the valuation of agent $i$ is 0 in all the $n$ outcomes in which $i$ doesn’t get the item and $v_i$ for the outcome in which $i$ gets the item
very simple case
e.g. a potential buyer has different valuations for outcomes depending on who gets licenses among competitors.

Combinatorial auction

$n$ bidders
set $M$ of $m$ indivisible items
set $\Omega$ : $n$ -vectors of the form $(S_1,S_2,\cdots,S_n)$ where $S_i\subseteq M$ denotes the set of items that are assigned to bidder $i$ .
every item is given to at most one bidder
the valuation of bidder $i$ for set $S\subseteq M$ is $v_i(S)$ , i.e. the valuation of each bidder consists of $2^m$ parameters
example: spectrum auctions, allocating takeoff and landing slots at airport.

The VCG mechanism

theorem: in every multi-parameter environment, there is a DSIC social welfare maximizing mechanism.

DSIC? ✅
social welfare maximization? ✅
low computational complexity? ❎

design goals (for single-parameter environments):

assuming that the participants report their private information truthfully, maximize the social welfare
provide incentives (through payments) so that the participants report their valuations truthfully.

Every participant $i$ declares her preference $\mathbf b_i$ , i.e. a value for each possible outcome of $\Omega$ (direct revelation)

outcome: $x(\mathbf b)=\arg\max_{\omega\in\Omega}\sum_{i=1}^nv_i(\omega)$

payments? Myerson’s lemma doesn’t hold anymore.

why?

monotone when input space is multi-param?
how to define critical bid?

Payment rule (charging each agent her externalities)

the payment from each participant is equal to the decrease in social welfare that her presence causes to the remaining participants
for outcome $\omega^*=x(\mathbf b)$ , we define the payment.
$p_i(\mathbf b)=(\max_{\omega\in\Omega}\sum_{j\neq i}b_j(\omega))-\sum_{j\neq i}b_j(\omega^*)$
payment of $i$ = maximum social welfare of the rest of the participants - social welfare of the rest of the participants at outcome $\omega^*$ .

VCG mechanism aka The Vickrey, Clarke & Groves mechanism

Outcome: $\omega^*=x(\mathbf b)=\arg\max_{\omega\in\Omega}\sum_{i=1}^nv_i(\omega)$
Payment: $p_i(\mathbf b)=(\max_{\omega\in\Omega}\sum_{j\neq i}b_j(\omega))-\sum_{j\neq i}b_j(\omega^*)$
Alternative payment definition: $p_i(\mathbf b)=b_i(\omega^*)-[\sum_{j=1}^nb_j(\omega^*)-\max_{\omega\in\Omega}\sum_{j\neq i}b_j(\omega)]$
payment of $i$ = bid - rebate (increase in social welfare attributable to participant $i$ ’s presence)

Proof via the VCG mechanism

social welfare is maximized due to the definition $\omega^*=x(\mathbf b)=\max_{\omega\in\Omega}\sum_{i=1}^nb_i(\omega)$ ,

we need to show that the utility $v_i(x(\mathbf b_i,\mathbf b_{-i}))-p_i(\mathbf b_i,\mathbf b_{-i})$ of agent $i$ is maximized for $\mathbf b_{i}=\mathbf v_i$ .

v_i(x(\mathbf b_i,\mathbf b_{-i}))-p_i(\mathbf b_i,\mathbf b_{-i})=[v_i(\omega^*)+\sum_{j\neq i}b_j(\omega^*)]-[\max_{\omega\in\Omega}\sum_{j\neq i}b_j(\omega)]

so the goal of agent $i$ to maximize her utility is aligned with the general goal of maximizing social welfare.

Practical issues

Preference elicitation 偏好诱导: reporting $2^m$ parameters (issue for any direct revelation mechanism)

High computational complexity (e.g. knapsack auctions)

Low revenue

Problematic incentives: 容易受到投标者串通、假名投标

Spectrum auctions

Indirect mechanisms

they don’t need a bid from each participant for every possible outcome

they ask bids only when it’s necessary

English ascending auctions

英国升序拍卖，就是典型的文物、艺术品拍卖形式

the auctioneer increases the price gradually
bidders declare in or out at the current price
untiil there is only one interested bidder left
payment = price when the second-last bidder dropped out

notes:

non-direct revelation mechanism
dominant strategy for the participants: stay in the auction as long as the price is lower than valuation

Some variations

Christie’s, Sothby’s:

gradual increase of the price
potential buyers can drop out and return at any price 竞拍者可入可出
jump bids to aggressively raise the price 可大幅抬高价格

Japanese auction (amenable for theoretical analysis 只适合理论分析):

initial opening price
price increase at a steady state
once a participant drops out, she can’t re-enter at a later higher price

What about indirect mechanisms in multi-parameter environments? In combinatorial auctions? In spectrum auction?

Auctioning off each item separately

for every available item, run a separate single-item auction
requires one bid per item by each potential buyer
Social welfare?
- High if items are substitutes: $v(AB)\leq v_(A)+v(B)$
- Low if items are complements $v(AB)\gt v(A)+v(B)$

Substitutes and complements

substitutes

e.g. spectrum licenses for 2 different frequency block in the same geographical area, 2 different drinks.
easy computational problem
high social welfare through auction

complements

e.g. spectrum licenses for the same frequency block in neighboring geographical areas, a pair of shoes
hard computational problem
low social welfare (usually)

Simultaneous ascending auctions

aka SAA

Rookie mistakes

同步升序拍卖容易犯的错

Hold the single-item auction sequentially, one at a time
examples:
- $k$ -unit auction
- every potential buyers is interested in exactly one copy
- how will high valuation buyer behave?
  after winning a item, always bids 0
- What can go wrong?
  not social welfare maximizing
Use sealed-bid single item auctions
examples:
- 3 potential buyers for 2 TV broadcasting licenses
- each buyers wants only one licenses

同步升序拍卖的步骤

Run in parallel at the same room, with one auctioneer per item
in every step, each potential buyer bids for a set of items
activity rule:
- every potential buyer participates from the very beginning
- the number of items in the bid of a potential buyer cannot increase as the auction progresses
details can be complicated

什么是好的同步升序拍卖？

little or no resale of items
any reselling should take place at a price comparable to the auction’s selling price 任何转售应该以相同的拍卖售价进行
revenues should be meet or exceed projections
evidence of price discovery
the frequency packages assembled by the bidder should be sensible

Issues for SAA

demand reduction

2 potential buyers 2 items.

buyer 1: 10 for each item separately, 20 for both.

buyer 2: 8 for each item separately, 8 for both.

VCG: revenue=8

SAA: revenue=0

exposure problem

无法出价问题

2 potential buyers for 2 items

buyer 1: value 100 for both, value 0 for each separately

buyer 2: value 75 for either item, wants only one.

VCG: revenue=75

SAA: revenue=0

Package bidding

limited use

hierarchical packages 分层包

computing prices/payments can be tricky

unpredictable outcomes

Redistributing the frequency spectrum

2016 FCC incentive auction, US

Purchase of frequency blocks, via a reverse auction

A potential buyer 𝑖 has private valuation 𝑣" for her own frequency block
and utility 𝑝 − 𝑣" when selling it at price 𝑝

Repack not purchased frequencies

Bandwidth allocation for optimal spectrum use

Auction off the available spectrum

Summary

Mechanism design in multi-parameter environments

The VCG mechanism

Indirect mechanism

Spectrum auctions

课后习题

Problem 6.1

单物品拍卖

$X_i\sim F_i$ , $i=1,2,\cdots,n$

这些 $X_i$ 藏在 $n$ 个盒子中。

process: for i=1 to n

打开第 $i$ 个盒子，查看报价
要么接受第 i 个盒子报价，要么继续开下一个盒子

求证：prophet inequality: there exist a threshold $\tau$ , s.t. we guarantee $\frac{1}{2}\mathbb E[\max_iX_i]$ . we accept the bid once we find first $X_i\gt \tau$ . 这个系数 $\frac{1}{2}$ 不能被提高。

我们要证明 $\forall\epsilon\lt0$ , $\mathbb E[ALG]\lt\frac{1}{2-\epsilon}\mathbb E[\max_iX_i]$

Monotone Hazard Rate distribution aka MHR

$v\sim F\rightarrow$ virtual valuation $\varphi(v)=v-\frac{1-F(v)}{f(v)}$

$v$ is regular when $\varphi(v)$ is non-decreasing

$v$ is MHR when $\frac{1-F(v)}{f(v)}$ is non-increasing

$\Rightarrow\varphi(v)$ is increasing $\Rightarrow$ $v$ is regular.

Problem 6.2

define a auction: welfare maximization with monopoly reserves.

process:

let $r_i$ be the monopoly price, $r_i=\arg\max_{r\ge0}\{r(1-F_i(r))\}$ .
let $s$ denotes the agents with $v_i\ge r_i$ .
choose winners $W\subseteq S$ to maximize the social welfare: $W=\arg\max_{T\subseteq S:T\ feasible}\sum_{i\in T}v_i$ .
define payment ala Myerson’s lemma.

a) prove that if $v_i\ge r_i$ then $r_i+\varphi(v_i)\ge v_i$ (due to MHR)

$\because r_i=\arg\max_{r\ge0}\{r(1-F_i(r))\}\\ \therefore [r_i(1-F_i(r_i))]'=0\\ \therefore r_i=\frac{1-F(r_i)}{f(r_i)}\\ \because MHR,v_i\ge r_i\\ \therefore \frac{1-F(v_i)}{f(v_i)}\le\frac{1-F_i(r_i)}{f(r_i)}\\ v_i=\varphi_i(v_i)+\frac{1-F(v_i)}{f(v_i)}\le\varphi_i(v_i)+\frac{1-F_i(r_i)}{f(r_i)}=\varphi_i(v_i)+r_i$

b) let $\mathcal M^*$ be the revenue-maximizing mechanism. prove that $\mathbb E[SW(\mathcal M)]\ge\mathbb E[SW(\mathcal M^*)]$

observe that both mechanism $\mathcal M,\mathcal M^*$ select subset of $S$ as outcome

c) prove that $\mathbb E[REV(\mathcal M)]\ge\frac{1}{2}\mathbb E[SW(\mathcal M)]$

$\mathbb E[REV(\mathcal M)]=\mathbb E[\sum_{i\in W}\varphi_i(v_i)]\\ \mathbb E[REV(\mathcal M)]\ge\mathbb E[\sum_{i\in W}r_i]\\ \therefore2\times\mathbb E[REV(\mathcal M)]\ge\mathbb E[\sum_{i\in W}\varphi_i(v_i)]+\mathbb E[\sum_{i\in W}r_i]\\ \ge\mathbb E[\sum_{i\in W}v_i]=\mathbb E[SW(\mathcal M)]\\ \therefore\mathbb E[REV(\mathcal M)]\ge\frac{1}{2}\mathbb E[SW(\mathcal M)]$

d) prove that $\mathbb E[REV(\mathcal M)]\ge\frac{1}{2}\mathbb E[REV(\mathcal M^*)]$

$\mathbb E[REV(\mathcal M)]\ge\frac{1}{2}\mathbb E[SW(\mathcal M)]\ge\frac{1}{2}\mathbb E[SW(\mathcal M^*)]\ge\frac{1}{2}\mathbb E[REV(\mathcal M^*)]\\ (c),(b),v_i\ge\varphi(v_i)\forall v_i\ge r_i$

Another Problem

Set of items $M$ , $n$ agents with valuations for subset (bundles) of items (aka multi-param)

goal: set price for each item and ask their prices as payments from the agent who gets each item i.e., if agent $i$ gets bundle $S_i$ , her value $v_i(S_i)$ and her payment to the mechanism is $\sum_{j\in S_i}p_j$ .

definition

an allocation $S^*=(S_1^*,S_2^*,\cdots,S_n^*)$ of the items of $M$ to the $n$ agents at selling prices $P^*$ is called a Walrasian equilibrium if:

every agent gets has preferred bundle given prices $P^*$ , i.e., $S_i^*\in\arg\max_{S\subseteq M}\{v_i(S)-\sum_{j\in S}p_j\}$
supply agents demand, i.e., every item appear in at most one bundle and stay unsold only if $P_i^*=0$

Prove that a Walrasian equilibrium has optimal social welfare.

Let $S^*,P^*$ be a Walrasian e.g. and $S=(S_1,S_2,\cdots,S_n)$ is any other allocation of the items in $M$ to the $n$ agents. we will show that $SW^*\gt SW$ , meaning that $S^*$ is social-welfare maximizing
By the Walrasian equilibrium definition, we have that for agent $i$ :
$v_i(S_i^*)-\sum_{j\in S_i^*}p_j\ge v_i(S_i)-\sum_{j\in S_i}p_j^*$
i.e., the utility of agent $i$ for the bundle $S_i^*$ she gets in the Walrasian equilibrium is at least as high as her utility for bundle $S_i$ (given price $P^*$ )
$v_i(S_i^*)\ge v_i(S_i)-\sum_{j\in S_i}p_j^*+\sum_{j\in S_i^*}p_j^*$
summing this inequality for all agents $i$ , we have
$SW(S^*)=\sum_{i\in[n]}v_i(S_i^*)\ge\sum_{i\in[n]}(v_i(S_i)-\sum_{j\in S_i}p_j^*+\sum_{j\in S_i^*}p_j^*)\\ \sum_{i\in[n]}v_i(S_i)-\sum_{i\in[n]}\sum_{j\in S_j}p_j^*+\sum_{i\in[n]}\sum_{j\in S_j^*}p_j^*\\ =SW(S)$