Dynamic Auctions with Bank Accounts

1 Introduction

The theory of dynamic mechanism design shows that if auctions are repeated over time and buyers and sellers care about the aggregate outcome of all auctions (as opposed to the outcome of each individual auction), then it is possible to design mechanisms that are superior to running the same static single-shot auction in terms of both revenue and social welfare. This is in contrast to the auction formats used by search engines to sell internet advertisement, which are mostly static single-shot auctions. The advantage of static formats is that they are easy to implement and the economic principles behind them are well understood. Nevertheless, by restricting to static mechanisms, exchanges are forgoing possibly very significative gains in revenue.

What are the barriers preventing dynamic mechanisms to become more prevalent in internet advertisement? If the seller is allowed to use the full power of dynamic mechanism design and have the auction for each item depend on the outcome of the previous auctions, such dependency induces a gigantic design space, making it difficult to solve for or even to describe such auctions. This creates problems not only for the mechanism designer but also for buyers participating in the mechanism, who need to play in a mechanism where every decision may lead to unintended repercussions.

Our goal in this paper is to study a restricted family of dynamic mechanisms, called bank account mechanisms, in which single-shot auctions are augmented with a structure we call bank account, a real number for each node that summarizes the history so far. This structure allows the seller to store deficits or surpluses of buyer utility from each individual auction and even them out on the long run, satisfying individual rationality on average.

In dynamic mechanism design the incentive compatibility and individual rationality constraints are satisfied on average over all queries and not per each individual query. One can think of bank account balance as how far each individual auction is from satisfying per-query incentive constraints. In other words, bank accounts quantify how far a certain dynamic mechanism is from a static mechanism.

This last observation motivates us to introduce the notion of a bank account limit, which is the maximum bank account balance allowed. Amechanismwith zero limit corresponds to a static mechanism. We identify a trade-off between the bank account limit and the revenue extracted: the revenue extracted per stage is upper bounded by the Myerson revenue plus the bank account limit (Theorem 3), and is lower bounded by constructed deterministic bank account mechanisms (Theorem 2).

We further identify a subset of bank account mechanisms, called double-reserve auctions, that can be easily implemented and can guarantee higher revenue than simply run separate Myerson auctions for each item (Theorem 2), while ensuring the same buyer utility as separate Myerson auction.

We also put forward an algorithm to compute the optimal double-reserve auction with any given bank account limit constraints via dynamic programming. Furthermore, the algorithm admits an FPTAS for any multiplicative ✏- approximation (Theorem 4).

Finally, we empirically evaluate the revenue performance of a heuristically constructed double-reserve auction and the optimal one on an infinite sequence of i.i.d. items. Moreover, we prove a lower bound of its revenue as a function of the bank account limit for any regular distribution (Theorem 5).

In a parallel work [Zuo et al., 2016], we consider the dynamic mechanism design under ex-post IR constraints. We also prove a characterization result concerning sufficiency of bank account mechanism in that setting and establish some simple bank account mechanisms that guaratee constant approximation ratios to the optimal revenue.

RelatedWork The area of dynamic mechanism design has attracted a large body of research work in the last decade [Cavallo, 2008; Pai and Vohra, 2008; Pavan et al., 2008; Cavallo et al., 2009; Gershkov and Moldovanu, 2009; Bergemann and V¨alim¨aki, 2010; Gershkov and Moldovanu, 2010; Athey and Segal, 2013; Kakade et al., 2013; Papadimitriou et al., 2014; Pavan et al., 2014]. We refer to [Bergemann and Said, 2011] for a comprehensive survey on the topic and cite here a couple of representative papers: [Bergemann and V¨alim¨aki, 2010] study the problem of efficient mechanism design in a dynamic environment where agents receive private information over time, and generalize the idea of pivot mechanisms [Green and Laffont, 1977] to this dynamic setting. [Pavan et al., 2014] provide characterization of dynamic local and global incentive compatibility constraints, and use the characterization to design optimal dynamic mechanisms in Markov environments. However, the optimal mechanism is individually rational only when the initial signal being observed, while in our independent valuation setting, it leads to full surplus extraction from all rest stages. [Papadimitriou et al., 2014] work on the discrete (except for the last stage) and correlated valuation distribution setting, and prove hardness results to compute deterministic optimal mechanism subject to ex post individually rational constraint for the two-stage case.

The problem of optimal multidimensional mechanism design [Manelli and Vincent, 2006; 2007; Cai et al., 2012a; 2012b; Hart and Nisan, 2012; Daskalakis et al., 2013; Li and Yao, 2013; Wang and Tang, 2014; Daskalakis et al., 2015; Cai et al., 2016] is closely related to our approach, especially the bundling technique used to improve the expected revenue [Tang and Sandholm, 2012; Babaioff et al., 2014].

2 Preliminaries andModel

Problem Consider the problem for selling a sequence of items, one at each stage, to a buyer who has independent additive valuations for the items. In each stage t 2 [T], the type (or valuation) vt 2 R+ of the buyer is privately drawn from a public distribution Ft, i.e., vt ⇠ Ft. The prior distribution Ft is independent stage-wise.

The outcome of each stage t is specified by a pair (xt↪ pt), where xt 2 [0↪ 1] denotes the probability of item the buyer obtains in stage t and pt 2 R+ denotes the corresponding payment. The buyer utility (or simply utility) of this stage is

Then the seller's objective is to design some mechanism that maximizes the total revenue, PT⌧=1 pt. Let v(⌧↪⌧ 0 ) = v⌧ ↪ ▷ ▷ ▷ ↪ v⌧ 0 be the vector of buyer's types from stage ⌧ to ⌧ 0 . Similar for x(⌧↪⌧ 0 ) = x⌧ ↪ ▷ ▷ ▷ ↪ x⌧ 0 , p(⌧↪⌧ 0 ) = p⌧ ↪ ▷ ▷ ▷ ↪ p⌧ 0 , etc.

2.1 Dynamic Mechanisms

By revelation principle, it is without loss of generality to restrict attention to direct mechanisms, where the agent reports its private type to the mechanism in each stage.

Definition 1 (Direct Mechanism). A direct mechanism is a pair of allocation rule and payment rule, i.e., M = hx(1↪T)↪ p(1↪T)i, where xt : Rt+ ! [0↪ 1]↪ pt : Rt+ !R+↪ 8t.

Furthermore, the allocation x(1↪T) and payment p(1↪T) satisfy the following constraints,

• ÷ Incentive compatible (IC). Incentive compatible in perfect Bayesian equilibrium: for any history, truth-telling is the best response for current and upcoming stages in expectation.
• ÷ Individually rational (IR). Stage-wise interim individually rational: for any history, the expected utility for current and upcoming stages is non-negative.

Formally, we first define the following notation for the expected buyer utility after stage t, with given history v(1↪t) and bidding strategy b(t+1↪T), i.e.,

where v⇤ (1↪⌧) = v(1↪t)↪ bt+1(vt+1)↪ ▷ ▷ ▷ ↪ b⌧(v⌧). We use Ut without superscript to denote the utility by truthful bidding, and the formal definitions are 8t↪ v(1↪t)↪ v0t ↪ b(t+1↪T),

For for any mechanismM, denote the overall expected revenue by REV(M) = Ev(1↪T) ⇥PT⌧=1 p⌧(v(1↪⌧))⇤, overall expected buyer utility by UTL(M) = U0, and overall expected efficiency by EFF(M) = UTL(M) + REV(M).

The mechanism is deterministic, if for each stage t, and any history v(1↪t), xt(v(1↪t)) 2 ¶0↪ 1♦; the mechanism is history independent, if both xt and pt only depend on the type of current stage, vt, but not v(1↪t-1).

Mechanism 1 ((Static) Myerson Auction). Separate Myerson auction M S is the auction that sells each item separately using single-stage Myerson auction.

Let φt 2 argmaxu ⇢t(u) be the Myerson price of stage t, where ⇢t(u) = (1 - F(u)) · u. Hence REV(M S ) = PT⌧=1 ⇢⌧ (φ⌧ ).

Separate Myerson auction is deterministic and history independent. More generally, we called a mechanism separate posted-price auction, if the seller sells each item separately using single-stage posted-price.

2.2 Mechanisms with Bank Accounts

Intuitively, a bank account mechanism (BAM) is a separate auction augmented with a bank account to ensure IR on average. Instead of explicitly depending on the full history, a BAM depends on a real number, bank account balance (or simply balance).

Definition 2 (BAM). A bank account mechanism B = hz(1↪T)↪ q(1↪T)↪ d(1↪T)↪ s(1↪T)↪ bal(1↪T)i, where for each t,

• ÷ Allocation rule zt : R+ ⇥ R+ ! [0↪ 1], maps balance and value to allocation.
• ÷ Payment rule qt : R+ ⇥R+ ! R+, maps balance and value to payment.
• ÷ Deposit policy dt : R+ ⇥R+ ! R+, maps balance and value to how much money the buyer needs to add into the bank account.
• ÷ Spend policy st : R+ ! R, maps balance to how much money to spend from the bank account.
• ÷ Initial balance of stage t, balt, is a function of history v(1↪t-1), satisfying the follows, where bal1 = 0.

At stage t, a BAMworks as follows, (see Figure 1)

1. The seller spends the buyer's balance by st(balt). (So st(balt) becomes part of seller's revenue.)
2. Upon receiving buyer's report vt, the seller allocates the item to the buyer with probability zt(balt↪ vt) and charges qt(balt↪ vt).
3. The buyer deposits an amount of dt(balt↪ vt) to the bank account.

By Definition 2, bank account mechanism is a subset of direct mechanisms. A BAM is deterministic, if in each stage t, 8vt↪ balt↪ zt(balt↪ vt) 2 ¶0↪ 1♦.

We impose a limit L on the maximum value that the balance can reach, i.e.,

Intuitively, the larger the limit, the more trust needed from the buyer.

Consider the following example that illustrates the bank account mechanisms.

Example 1. Consider a two-stage example, where v1 and v2 are two i.i.d. random variables which take value 1 or 2 with probability 1◁2. A bank account mechanism B is defined as follows.

B operates as follows,

1. The first item is sold at posted-price 1.
2. If v1 = 2, the buyer offers a pre-payment of amount 0▷5 to the seller before learning v2 (d1(bal1↪ 1) = 0▷5, s2(bal2) = bal2).
3. The seller sets a posted-price r for the second item. If bal2 = 0, r = 2; if bal2 = 0▷5, r = 1.
4. The buyer learns v2, and buys the second item if and only if v2 ≥ r.

The revenue comes from both the payment when the buyer buys the items (step 1 and 4) and the pre-payment (step 2), and is 2▷25 in expectation.

2.3 Partial Characterization

The following lemma characterizes sufficient conditions for a BAM to satisfy IC and IR.

Lemma 1. Let ˆut(balt↪ v0t ; vt) denote the stage utility for bank account mechanismB, i.e.,

B is IC and IR, if the following are satisfied, 8t↪ balt↪ vt↪ v0t .

In particular, (6)(7) =) IC; (7)(8) =) IR.

In the rest of the paper, BAM refers to bank account mechanism satisfying (6)(7)(8) and qt ≥ 0.

Proof. Throughout the proof, we use short notations as follows,

We construct a direct mechanism M as follows, which has the same allocations and payments with B for any v(1↪T ).

Firstly, we prove that M is IC. According to (5),

combining with (6), 8t↪ v(1↪t-1)↪ vt↪ v0t ↪

Let v0t be bt(vt). Take expectation to (10) over vt, and subtract st from both sides,

Denote u00 t+1 = ut+1(v(1↪t-1)↪ v0t ↪ v0t+1 ; vt+1), and s00 t+2 = st+2(balt+2(v(1↪t-1)↪ v0t ↪ v0t+1 )), then

Sum over the LHS of (11), and recursively apply (12),

where sT+1 ⌘ 0. Similarly, sum over both sides of (11),

Adding (14) to (10) implies (2), soM is IC. Secondly, we prove that M is IR. By (9) and (7),

Thus 8v(1↪t), Ut(v(1↪t)) - st+1 is a constant, i.e.,

Add (15) to (9),

By (8), the RHS is non-negative, so M is IR by (3).

In summary, for any BAM, B, the equivalent direct mechanismM is IC or IR if the corresponding sufficient conditions are satisfied.

2.4 Bank Account Mechanism is WLOG

In this paper, we focus on bank account mechanisms instead of general direct mechanisms. This is formally justified by the following theorem.

Theorem 1. For any direct mechanism M, there is a constructive BAM, B, such that,

In particular, if M is deterministic, B is also deterministic.

We omit the proof here and refer readers to the full version of our paper.

3 Double-Reserve Auction

By Theorem 1, the revenue optimal bank account mechanism is optimal among any mechanism. An extreme example is that a BAM could extract almost all valuation by allocating the t-th item and charging the buyer E[vt+1] in the t-th stage for each t = 1↪ ▷ ▷ ▷ ↪ T - 1.

However, there are a list of drawbacks of such mechanisms, such as, randomized allocation rule, large bank account, and pre-payment (positive payment even not get allocated).

In this paper, we introduce a subset of practical bank account mechanisms coined double-reserve auction, which in practice can be easily implemented as a special posted-price auction: for each stage t, there are a low reserve price and a high reserve price; if the (t - 1)-th item is sold to the buyer, sell the t-th item at the low reserve price, otherwise at the high price.

Mechanism 2 (Double-Reserve Auction). A double-reserve auction B is defined upon a separate posted-price auction M and pre-specified bank account limits, ¶Lt♦Lt=1 . Let r(1↪T) be a series of auxiliary functions with rt(0) being the reserve price of M on stage t. Denote Valt(a↪ b) = R b a (1-Ft(v))dv. Then B is formally defined as, where I is indicator function.

The function rt(⇠) above is defined to meet the requirements of Lemma 1, particularly, rt(⇠) equals to the value such that Valt(rt(⇠)↪ rt(0)) = ⇠. 1

3.1 Revenue Properties of Bank Account Mechanism with Limits

We now study the revenue properties of double-reserve auction and general bank account mechanism with limits. Concretely, for double-reserve auction, we prove a revenue lower bound (Theorem 2); for general bank account mechanisms, we prove a revenue upper bound (Theorem 3).

Theorem 2. For any separate posted-price mechanism M, the double-reserve auction B defined upon M with any given bank account limits, ¶Lt♦Lt=1 , satisfies

1 rt(⇠) is unique, non-negative, and strictly decreasing.

• ÷ B is a BAM (satisfying Lemma 1);
• ÷ UTL(B) = UTL(M);
• ÷ REV(B) ≥ REV(M);
• ÷ REV(B) is increasing in L(1↪T).

Proof. 1. B is a BAM (satisfying Lemma 1).

By (16), B is deterministic. Meanwhile, by (18), balance is always completely spent at the beginning of each stage. Thus by (19), balt only has two possible values, 0 or Lt (bal1 = 0 by definition).

Since Lt  Valt(0↪ rt(0)), rt(balt) is well-defined. Moreover, according to the proof of Lemma 1, B can be implemented by a direct mechanism with stage payment as follows,

In particular, when the item is sold, the payment can be two different values, depending on whether balt is 0.

Condition (6) and (8) are satisfied by (16) and (17), while (7) is ensured as follows.

The second "=" is from integration by parts.

2. UTL(B) = UTL(M).

Denote the expected revenue improvement for stage t by t,

3. REV(B) ≥ REV(M).

Moreover, each t is weakly increasing in bank account limit Lt0 for t0  t. 2 Hence the expected revenue increases as the bank account limit increases.

where ↵t = Pr[balt = Lt], and the last "=" is from integration by parts. Hence the overall revenue improvement is non-negative, i.e., REV(B) - REV(M) = PT⌧=1 ⌧ ≥ 0. 4. REV(B) is increasing in L(1↪T).

As we proposed, double-reserve auction is easy to implement, and can improve the revenue without hurting the buyer utility under any given bank account limit. A natural question is: what is the limitation of such mechanisms comparing with the optimal mechanism under the same bank account limit? The following theorem provides an upper bound on the revenue for any mechanism under given limit.

2↵t is increasing in Lt0 . rt(Lt) is decreasing (hence the integration is increasing) in Lt0 when t = t0 . Therefore t is increasing.

Theorem 3. For any bank account mechanism B with limits ¶Lt♦Tt=1 ,

where M S denotes the separate Myerson auction. In other words, the revenue improvement comparing with separate Myerson auction is bounded by the sum of bank account limit on each stage.

Proof. Assume by contradiction that there exists a BAM, B, such that,

Then we construct a mechanism M that operates independently on each stage but generates strictly higher revenue than Myerson auction in at least one stage.

To ensure that the constructed mechanism is history independent and IC-IR within each single stage. We create a fake bank account to mimic the behavior of the real bank account in B. One can think of the balance bal t of the fake bank account as simply a number, satisfying that the distribution of bal t is the same as the distribution of the real balance (as a random-valued function of previous types).

Consider the following construction of M based on B.

where in each stage t, bal t is a random variable drawn by the following process for ⌧ from 1 to t - 1.

Thus bal t is independent of the buyer's real types, and has the same distribution with balt. Note that vt is independent of the history, hence independent of balt as well. Then

namely, at least in one stage ⌧, M generates strictly higher revenue than the optimal revenue, ⇢⌧ (φ⌧ ).

In particular, by construction M is history independent, and by (6)(8) and qt ≥ 0, M is also IC and IR within each single stage. Thus (21) contradicts the optimality of Myerson auction for single-shot case.

RHvHnuH & EffLcLHncy

1.0

0.8

0.6

0.4

0.2

0.0

HDR vs. 2PT Rn ExpRnHntLDO DLstrLEutLRn

RHv-2PT

Eff-2PT

RHv-HDR

Eff-HDR

0.0

0.2

0.4

0.6

0.8

1.0

LLPLt L

HD5 vs. 23T Rn UnLfRUP DLstULEutLRn

5Hv-23T

Eff-23T

5Hv-HD5

Eff-HD5

0.5

0.4

0.3

0.2

0.1

0.0

0.0

0.1

0.2

0.3

0.4

0.5

Figure 2: HDR vs. OPT on revenue and efficiency for different distributions.

3.2 Compute Optimal Double-Reserve Auction via Dynamic Programming

As we proved by Theorem 2, the double-reserve auction defined upon a separate posted-price auction has a quantified revenue improvement guarantee. In particular, it is better than the separate Myerson auction when defined on separate Myerson auction.

However, this construction is not guaranteed to be optimal among the double-reserve auctions. In this section, we compute optimal double-reserve auctions.

Theorem 4. The optimal double-reserve auction subject to given bank account limit can be computed through a dynamic programming algorithm.

Moreover, for any ✏ > 0, there is an FPTAS 3 to achieve an ✏-approximation of the optimal double-reserve auction.

Proof sketch. Dynamic programming (DP) algorithm.

For any double-reserve auction B, a stage does not depends on latter stages and it can only influence the latter ones through the balance. The balance balt is a random variable distributed according to a two-valued distribution, i.e., Pr[balt = Lt] = ↵t and Pr[balt = 0] = 1 - ↵t.

Moreover, ↵t+1 is uniquely defined by ↵t and rt(0), and so is the expected stage revenue. Hence B is entirely determined by r(1↪T)(0), and the optimal double-reserve auction can be computed via DP, where the state update formula is,

ht(↵t) is the maximum expected revenue from stage t to stage T with specified ↵t. Note that t and ↵t+1 are functions of ↵t and rt(0).

FPTAS for the DP: a natural FPTAS to implement the DP algorithm is to discretize ht over its domain, [0↪ 1]. One critical observation is that ht is increasing (proof omitted) and bounded (Theorem 3), so can be ✏-approximated by at most O(tL◁✏) many sample points over [0↪ 1].

4 Empirical Evaluations

In this section, we empirically evaluate the expected revenue and efficiency of the optimal double-reserve auction (OPT) and the so-called heuristic double-reserve auction (HDR) over the infinite stream of i.i.d. items as functions of the bank account limit L. The reason that we propose and evaluate HDR is that it is easy to implement, non-sensitive to prior distribution F, and yields near optimal revenue, compared to the OPT. As a result, HDR can be used as a replacement of OPT in practice.

3 Fully Polynomial Time Approximation Scheme.

To simplify notation, we remove all subscript t because of the i.i.d. assumption. Besides, by revenue and efficiency in this section, we refer to per stage revenue and efficiency.

Mechanism 3 (HDR). HDR is the better one of two doublereserve auctions, B0 and B00 .

Intuitively, with given limit L, (1) B0 is the double-reserve auction defined upon separate Myerson auction; (2) B00 is the double-reserve auction with the lower reserve r00 (L) being 0.

We provide a lower bound analysis for the revenue of HDR as a function of the limit L.

Theorem 5. The expected revenue per stage ⇡ is lower bounded by L. If F is regular, then ⇡ is further lower bounded as follows, where G = 1 - F, and ⇠ = 1 - eLF(φ)◁⇢(φ) .

Empirical Evaluations We evaluate both mechanisms on exponential distribution (λ = 1), lognormal distribution (lnN(0↪ 1)), and [0↪ 1] uniform distribution (Figure 2). For each case, we illustrate the revenue and efficiency of OPT and HDR as functions of the limit L. Note that when the limit is greater than the mean of the valuation distribution, both OPT and HDR converge to fully surplus extraction, therefore the revenue and efficiency will equal to the mean.

In all three cases, the revenue of HDR and OPT are very close, especially when L is less than 50% of the mean. In particular, the revenue improvement (compared with Myerson revenue) can be fitted as a linear function of L with coefficient roughly 0▷4 to 0▷5 when L is small. As L tends to the mean of each distribution, both HDR and OPT converge to fully surplus extraction. As for efficiency, HDR is better than OPT for most cases, except for the lognormal distribution when L  0▷6.

In summary, for all the distribution considered above, for reasonably small limit (less than 50% of the mean), the revenue improvements of both mechanism (OPT and HDR) are very close, and grows almost linearly as the limit increases. In contrast, the efficiency of HDR almost dominate that of OPT.

LLPLt L

5HvHnuH & EffLcLHncy