算法博弈论 W44 Mechanism design with payment constraints

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

1. let $p$ be the price that equalizes the supply with the demand, i.e., $A^-(p)\ge m\ge A^+(p)$
2. award $D_i(p)$ items to each participant $i$ at price $p$.
3. 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\empty$

• 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$ 中有的智能体在分配新房子的时候分到没有之前那么喜欢的房子。