# Dynamic Second Price Auction: [Bergemann and J. Välimäki]

In this post, I’m going to continue discussing the same paper on Dynamic Pivot Mechanism, by Dirk Bergemann and Juuso Välimäki, Econometrica, Vol. 78, No. 2 (March, 2010), 771–789. The focus of this post will be to discuss the section 5, where the authors have shown the efficient dynamic auction is a special case of this mechanism. This result also appeared in the paper, D. Bergemann and J. Välimäki. Efficient dynamic auctions. Cowles Foundation Discussion Paper No. 1584, Yale University, 2006.

This setting is a special case of the general pivot mechanism, since here the allocation is selecting an agent, while in the previous setting the allocation could have been a distribution over the agents. It is because of this particular setting the solution of the general MDP reduces to a multi armed bandit (MAB) problem. The pull of an arm is chosen according to the Gittin’s index policy.

1. Results

With reference to the notations as in the previous post, we can state the dynamic second price auction.

Theorem 1 (Dynamic Second Price Auction) The socially efficient allocation rule ${a^*}$ is ex post incentive compatible in the dynamic direct mechanism with the payment rule ${p^*}$, where,

$\displaystyle p_j^*(\theta_t) = \left\{\begin{array}{ll} (1-\delta) W_{-j}(\theta_t), & \mbox{if} \ a^*_t = j \\ 0, & \mbox{if} \ a^*_t \neq j \end{array}\right.$

Proof: It is easy to see that the payment has been carefully chosen, such that the utility to agent ${i}$ turns out to be the marginal contribution, as in the case of the general pivot mechanism. So, it remains to be shown that the marginal contribution is maximized at the true value of ${\theta}$. The utility of player ${i}$ consists of her (valuation – payment) at instant ${t}$ + the expected discounted marginal future contribution as before. Mathematically,

$\displaystyle \begin{array}{rcl} u_i(a^*(\theta_t), p_i^*(\theta_t), \theta_{i,t}) &=& v_i(a^*(\theta_t), \theta_{i,s}) - p_i^*(\theta_t) + \delta \mathbb{E}_{\theta_{t+1} | a^*(\theta_t), \theta_t} [M_i(\theta_{t+1})] \\ &=& W(\theta_t) - W_{-i}(\theta_t) \end{array}$

For ex-post incentive compatibility, we need to show the following ${\forall \ r_{i,t}}$,

$\displaystyle \begin{array}{rcl} u_i(a^*(\theta_t), p_i^*(\theta_t), \theta_{i,t}) &\geq& u_i(a^*(r_{i,t}, \theta_{-i,t}), p_i^*(r_{i,t}, \theta_{-i,t}), \theta_{i,t}) \\ &\Leftrightarrow& \\ W(\theta_t) - W_{-i}(\theta_t) &\geq& W(r_{i,t}, \theta_{-i,t}) - W_{-i}(r_{i,t}, \theta_{-i,t}) \\ &\Leftrightarrow& \\ W(\theta_t) &\geq& W(r_{i,t}, \theta_{-i,t}) \end{array}$

Note that, ${W_{-i}(r_{i,t}, \theta_{-i,t}) = W_{-i}(\theta_t)}$, since the optimal welfare should not change when ${i}$ is not in the game. We also have,

$\displaystyle \begin{array}{rcl} \lefteqn{W(\theta_{i,t}, \theta_{-i,t})} \\ &=& \max_{a_t} \mathbb{E}_{a_t | \theta_t} \left[ \sum_{i = 1}^I v_i(a_t, \theta_{i,t}) + \delta \mathbb{E}_{\theta_{t+1} | a_t, \theta_t} W(\theta_{t+1}) \right] \\ &\geq& \mathbb{E}_{a'_t | \theta_t} \left[ \sum_{i = 1}^I v_i(a'_t, \theta_{i,t}) + \delta \mathbb{E}_{\theta_{t+1} | a'_t, \theta_t} W(\theta_{t+1}) \right] \ \forall \ a'_t \\ \mbox{In particular,} && \\ \lefteqn{W(\theta_{i,t}, \theta_{-i,t})} \\ &\geq& \mathbb{E}_{a^*(r_{i,t}, \theta_{-i,t})| \theta_t} \left[ \sum_{i = 1}^I v_i(a^*(r_{i,t}, \theta_{-i,t}), \theta_{i,t}) + \delta \mathbb{E}_{\theta_{t+1} | a^*(r_{i,t}, \theta_{-i,t}), \theta_t} W(\theta_{t+1}) \right] \\ &=& W(r_{i,t}, \theta_{-i,t}) \end{array}$

Hence, ex-post incentive compatibility result follows. Q.E.D.