Budget constraints

limit the amount of money that an agent can pay

in practice: in a sponsored search auction, every bidder is asked for her bid-per-click and her daily budget.

small but drastic change in modeling the behavior of participant $i$ with budget $B_i$ and valuation $v_i$.

utility for outcome $\omega$ with payment $p_i$ $$ \begin{cases} v_i(\omega)-p_i, p_i\le B_i\ -\infty, p_i\gt B_i \end{cases} $$

A single-item auction with budget constraints

given the item to a random participant
payment = 0
Can we do better with DSIC auctions?

scenario: $n$ bidder for a single items. Budgets of 1 for each bidder. Is there a (nearly) social welfare maximizing DSIC mechanism?

use a priority order of the agents if those agents of value greater than 1, give the item to agent to highest priority.

Multi-unit auctions

$m$ identical items, each participant $i$ has a valuation $v_i$ for each item and can get more than one items. (valuation $k\times v_i$ for $k$ items)

public budgets (known to the seller in advance)

market clearing price: aggregate demand = supply

Demand of participant $i$ at price $p$ $$ D_i(p)=\begin{cases} \min{\lfloor\frac{B_i}{p}\rfloor,m}, p\lt v_i\ 0, p\gt v_i \end{cases} $$ $D_i(0)=m,D_i(\infty)=0$. the demand $D_i(p)$ is decreasing in terms of price.

drops in demand can be from an arbitrary positive integer to 0 (when price gets higher than the valuation) or by a unit (decrease of quantity $\lfloor\frac{B_i}{p}\rfloor$)

aggregate demand: $$ A(p)=\sum_{i=1}^nD_i(p)\ A^-(p)=\lim_{q\uparrow p}\sum_{i=1}^nD_i(q)\ A^+(p)=\lim_{q\downarrow p}\sum_{i=1}^nD_i(q) $$

Uniform-price auction

let $p$ be the price that equalizes the supply with the demand, i.e., $A^-(p)\ge m\ge A^+(p)$
award $D_i(p)$ items to each participant $i$ at price $p$.
decide arbitrarily the number of items given to participants with $v_i=p$ so that all items are sold

some fact:

uniform-price auction is not DSIC:

e.g. 2 copies, 2 agent: $B_1=+\infty,v_1=6,B_2=v_2=5$.

assume truthful bids:

if price < 5, the aggregate demand is $A(p)=3$

when the price becomes 5, $D_1(5)=2,D_2(5)=0$

so the uniform-price auction gives 2 items to participant 1 at price 5, utility = 2.
assume participant 1 misreport 3 as her bid,

if price < 3, the aggregate demand is $A(p)\ge3$

when the price becomes 3, $D_1(3)=1$ (其实这里没有定义，因为有剩余的物品，所以就给了), $D_2(3)=1$.

so the uniform-price auction gives 1 item to participant 1 at price 3, utility = 3.

in addition, the uniform-price auction

respects participants' budgets
monotone allocation rule
wrong payments

Clinching auction

together with the current price $p$, the auction keeps track of the current demands $s$ (initially $m$) and the residual budget $\hat B_i$ for every participant $i$

residual demand: $$ \hat D_i(p)=\begin{cases} \min{\lfloor\frac{\hat B_i}{p}\rfloor,s}, p\lt v_i\ 0, p\gt v_i \end{cases} \ \hat D_i^+(p)=\lim_{q\downarrow p}\hat D_i(q) $$ the auction iteratively increases the current price and participant $i$ "clinches" some items at price $p$ whenever they are uncontested, i.e., when the aggregate residual demand of the remaining participants is strictly lower than the current supply $s$.

Pseudo-code

Initialization: $p=0,s=m,\hat B_i=B_i$ for every participant $i$.

While $s\gt0$ (there is supply)

increase price $p$ to the next higher value of $v_i$ or the next value $\frac{\hat B_i}{k}$ for some integer $k$
let $i$ be the participant with the highest residual demand $\hat D_i^+(p)$.
While $\sum_{j\neq i}\hat D_j^+(p)\lt s$ (low residual demand ignoring participant $i$)
if $\sum_{j=1}^n\hat D_j^+(p)\gt s$ (high aggregate demand)

give an item to participant $i$ at price $p$. decrease $\hat B_i$ by $p$ and $s$ by $1$.

recompute the participant $i$ with the highest residual demand $\hat D_i^+(p)$
otherwise, if $\sum_{j=1}^n\hat D_j^+(p)\le s$ (low aggregate demand)

give $\hat D_j^+(p)$ item to every participant $j$ at price $p$

give items to participants with $v_i=p$

set $s=0$

An example

2 items, 2 participants: $B_1=+\infty,v_1=6,B_2=v_2=5$

assuming truthful bids, the first item is given to participant 1 at price $\frac{5}{2}$ and the second one at price $5$. (utility=4.5)

does the participant have any incentive to misreport? NO. we'll proof later.

The clinching auction in addition

always terminates
allocates exactly $m$ items
respects budgets
DSIC when budgets are public

why?

The allocation rule is monotone and the payments are the ones defined using Myerson's Lemma

DSIC proof:

assuming public budgets, the only control participant $i$ has is in the moment is when she stops participating
every item clinched with price $p\lt v_i$ ($p\gt v_i$), contributes positively (negatively) to the utility
thus, truth-telling guarantees non-negative utility
with a false bid $b_i\lt v_i$, the auction behaves the same up to the price $p=b_i$ and, then, participant $i$ can't claim items she would clinch in the interval $[b_i,v_i]$ and which would increase the utility.
with a false bid $b_i\gt v_i$, the auction behaves the same up to price $p=v_i$ and any additional items participant $i$ may get at price $\gt v_i$ will decrease her utility.

Mechanism design without money

House allocation

$n$ participants, each with her own house
each participant has a ranking of all houses.
how can we redistribute the houses s.t. the participants are as happy as possible?
Top trading cycle (TTC) algorithm

Top trading cycle algorithm

$N$: set of participants

while $N\neq\emptyset$

construct the directed graph $G$ with the participants as nodes and edge $(i,j)$ if the most preferred house for participant $i$ is that belonging to $j$.
compute all directed cycles in $G$
for every edge $(i,j)$ of ever cycle $C$, give the house of $j$ to $i$
remove the nodes of $C$ from set $N$.

Some facts

algorithm TTC is DSIC
first, every participant who gets a house at round $k$
prefers it compared to any other house, besides the ones given in earlier rounds
got it from someone who also got a house in round $k$
proof idea: no false reporting can give to participant $i$ a house that was given in a previous round
why? in any previous round, there is no edge from someone who got a house to participant $i$.
interesting: the algorithm that sometimes doesn't redistribute any house is DSIC.

block coalition: a set of participants s.t. there is a way to redistribute their houses so that all prefer the new allocation

core allocation: an allocation that has no blocking coalition

The allocation computed by TTC is the unique core allocation

Proof:

step 1: an allocation of houses to agents can be in the core only if it is the outcome of the TTC algorithm

any allocation in the core should look like the outcome of the TTC algorithm regularizing the house allocated to agents of group $N_1$. otherwise, $N_1$ would be a blocking coalition.

step 2: it is indeed a core allocation

consider any set of agents $S$, different from $N_1,N_2,\cdots$

这样会导致 $S$ 中有的智能体在分配新房子的时候分到没有之前那么喜欢的房子。