## “Demand Uncertainty and Dynamic Allocation with Strategic Agents,” A. Gershkov & B. Moldavanu (2010)

Consider a social planner, who discounts the future, trying to give away an indivisible object efficiently to agents who arrive over time; in the context of firms, this is often called “dynamic yield management.” Often, papers assume that agents are nonstrategic. But in many cases – consider possible home-buyers – agents will pretend not to be interested in a house if they think the seller will lower the price after they see little interest among buyers. Strategic action is important. If we knew everyone’s arrival time and valuation, this is just a relatively straightforward optimal stopping problem. What is the distribution of arrival times was unknown? In that case, private information about arrival time is important because the first few arrivals give the seller information about the distribution of arrival rates. Can we reach the dynamic first best even if everything is private information?

The answer, it turns out, is yes. This might surprise you if you know Gershkov and Moldavanu’s AER from a couple years back. In that paper, the uncertainty was about the distribution of private values, not arrivals. Generally, there does not exist an efficient mechanism under that kind of uncertainty. The case with uncertainty about arrival rate is different because agents can only pretend to arrive later, whereas with private values they could pretend to have either lower or higher private values. This one-sided deviation is important.

Here’s an example. Let bidder values be distributed U[0,1], and arrival times be a renewal with time between arrivals either distributed U[1,2] or U[2,3]. Papers from that 80s show that, if I know the actual arrival times and private values, the optimal dynamic mechanism just sells immediately after any agent arrives with a private value above a cutoff, and sells at a price equal to that cutoff. The cutoff x[1,2] if arrivals are distributed U[1,2] is higher than x[2,3] if arrivals are distributed U[2,3].

This introduces an incentive problem. Say the true arrivals are U[1,2], you are the first arrival, and you have a private value higher than x[1,2] but lower than x[2,3]. Since there is at least one unit of time until the next guy arrives, you can “delay” your arrival by up to one unit of time and be sure no one else will arrive. Truthfully revealing your arrival time and value means you are not allocated the object and therefore make profit zero; your private value is below x[1,2]. If you instead deviate by lying and saying you have arrival time after t=2, then you are allocated the object (since x[2,3] is now the cutoff, and that is below your private value), and you make positive profit.

Can this be fixed? Sure. Just pay anyone who reports arrival in [1,2] a subsidy of x[1,2]-x[2,3]. It is simple to prove that no one will want to deviate from the truth given these subsidies, so optimal dynamic efficiency can be obtained. You might prefer to only have payments made or given to agents who are allocated an object, though: otherwise there is a big incentive to “just show up” in order to get the subsidy. In this example, there is no efficient mechanism without subsidies: in order to keep the agent with value between x(2,3) and x(1,2) from lying about his arrival time, he must get “some” payoff from reporting truthfully. That can’t be a subsidy, so he must get the object with some probability. But then we no longer have dynamic efficiency.

More generally, with subsidies you can always incentivize everyone to report truthfully (and hence can efficiency allocate the good). The intuition is the same as in the example: pay a subsidy large enough that everyone’s utility is decreasing in their revealed arrival time. In particular, the earlier you arrive, the higher the subsidy you get. This will work as long as the subsidy is sufficiently large because there only one-sided deviations about arrival time are allowed: no one can “arrive” before their actual arrival time, so even a huge early arrival payment won’t can’t incentivize anyone to arrive “too early.” In some circumstances, the required subsidy is zero: this means that only the agent allocated the object will pay or get paid. It also means, roughly, that the efficient mechanism is the optimal dynamic mechanism.

When can we get away with no subsidies? This is quite difficult to prove. Gershkov and Moldavanu give some classes of distributions which require no subsidies, but the negative result is more intuitive: if arriving later makes the seller more pessimistic about future arrivals, then subsidies are required. The reason is as in the example; that property gives bidders an incentive to wait to “arrive” until the seller lowers the private value cutoff for which the object is sold.

A few comments. First, generally, this paper is not about finding the optimal mechanism (in terms of seller revenue) but is about finding any sort of efficient mechanism. The examples in the introduction do not all have this flavor, unfortunately. Second, and this is a problem in many mechanism design papers, strictly speaking mechanisms can only be run by monopoly firms or social planners. You might think that outside of a monopoly, a firm can take residual demand given other mechanisms as the private values it will face, but this usually can’t be done because the choice of mechanism by the firm will affect the distribution of private values seen. In general, the problem of so-called “competing mechanisms” is very difficult.