Consider the problem of a revenue maximizing seller with two items for sale, one today and one tomorrow, to a single buyer. The buyer knows her value for today's item, but for tomorrow's item she only has a prior. The seller knows the joint distribution (for which the buyer's prior is the conditional). How should the seller behave in order to maximize expected revenue? If there was no item tomorrow, this would be a simple application of Myerson's theorem (Myerson, 1981): the seller makes an offer easily calculated from the buyer's prior. But, the second item makes things much more complicated. We have a dynamic mechanism design problem.
Dynamic mechanisms have been studied extensively in quite general settings; see for example Bergemann and Said (2011) and Bergemann and Välimäki (2019) for recent surveys. But, in contrast to previous work, our focus here is computation. We propose the two-stage mechanism problem as a useful surrogate of dynamic mechanisms for the purpose of exploring the problem's computational complexity. It is certainly extremely simple, and yet surprisingly hard. To see why, suppose that the two valuations, for today and tomorrow, are independent random variables. It is then tempting to assume that, in this simple case, running Myerson's mechanism in each round should work (we refer to this as the non-adaptive mechanism). Is it optimal among all truthful and ex-post individually rational mechanisms? Even if not, it must surely at least be a good approximation? The answer is "no"! Example 1. Let X 1 and X 2 be the random variables indicating the value of the buyer for the first and second stage item. X 1 takes value 2 i with probability 2 -i for i = 1, . . . , n, and value 0 with probability 2 -n . X 2 takes value 2 i with probability 2 -i for i = 1, . . . , 2 n , and value 0 with probability 2 -2 n . It can be verified that the optimal static mechanism for both X 1 and X 2 extracts revenue at most 2: Consider setting some price 2 k . The expected revenue is at most 2 k • i≥k 2 -i ≤ 2. Therefore, running the optimal static mechanism at each stage extracts revenue at most 4. On the other hand, there exists a dynamic mechanism that extracts revenue n: on the first stage the buyer pays her report v (1) . On the second stage the item is given for free with probability v (1)
E[X 2 ] is a probability. An easy calculation shows that truthful reporting (weakly) maximizes the buyer's utility. The revenue extracted is E [ X 1 ] = n. The intuition here is that if the expected value of the future item is large, the buyer is willing to pay her value on the first stage for a better probability of getting allocated the future item.
We note that similar behaviors have been exhibited before, e.g. see Courty and Li (2000); Krähmer and Strausz (2016). And, in fact, for the exact same valuations as Example 1, we can extract more revenue than the non-adaptive mechanism using a deterministic mechanism. Here, we overall prove that, even when restricted to ex-post IR mechanisms, there is revenue loss by a non-constant factor between: non-adaptive mechanisms and the optimum deterministic adaptive mechanism (even for uncorrelated distributions); the optimum deterministic and the optimum randomized mechanism; the optimum randomized mechanism and the optimum social welfare. See Section 6 for the precise statements and proofs.
Let us focus on deterministic, ex post individually rational mechanisms. How hard can it be to find the optimum one? The reason we insist on determinism and ex post IR is because we believe that they draw the boundary of mechanisms in which people are likely to choose to participate. That is, the ex post IR constraint rules out mechanisms in which the seller asks an advance payment equal to the expected surplus. Ruling out such mechanisms (which would be feasible under ex-ante or ex-interim IR constraints) is of practical importance. For example, in online ad auctions advertisers' bids are interpreted as willingness to pay, and typically the platform cannot (legally) charge advertisers more than the amount declared as maximum. Our main result (Theorem 3) is that, for the two stage case, it is strongly NP-complete, given a prior with finite support, to find the optimum such mechanism. However, as we discuss below, we do show that we can compute the optimal randomized mechanism in polynomial time. 1 We first characterize the mechanisms of interest (Section 2). It turns out that there is always an optimum deterministic mechanism that is semi-adaptive (Lemma 2). A non-adaptive mechanism is one that makes two independent offers, one now and one in the future, without eliciting any input from the buyer. In contrast, a semi-adaptive mechanism starts by eliciting the buyer's type (and takes care that she is truthful), and then makes two offers simultaneously, one for now and one for the future. The buyer can take or leave the first offer now, and come back in the second stage to take or leave the second offer (which she knows now). So, our task is reduced to designing a function, informed by the whole joint distribution, that maps the support of the buyer's first stage type distribution to two prices. One of the reasons this task is daunting is that truthfulness is quite subtle in this context, and incentive compatibility constraints are a big part of the problem's difficulty. We must give the buyer the right incentives (both right now and in future expectation) so she will not misrepresent her type. This is done by choosing price pairs such that, for any other current valuation, the buyer is best off, in expectation, telling the truth. Low prices now must be counterbalanced carefully with higher prices in the future, and the inequalities involve integrals of the cumulative conditional distributions of the future valuation.
In Section 3 we describe our NP-completeness proof, from Independent Set. It is quite elaborate. The first stage types (values in the support of the first stage distribution) are the nodes. For each type, two of the possible current prices stand out as potentially optimal, and choosing between them is tantamount to deciding whether a node will be in the maximum independent set. The optimum revenue achieved is a strictly increasing function of the independent set size. The truthfulness constraints enforce that no two adjacent nodes are included, and this necessitates an elaborate design of the conditional distributions associated with the nodes.
Before we proceed to our next set of results, it is worth pointing out that the source of the complexity of the two-stage mechanism is not the multi-dimensionality of the buyer's private information. Finding the optimal deterministic one-shot mechanism for selling two (possibly correlated) items to a single buyer is computationally tractable (Chen et al. (2018)). 2 The key fact that allows for good algorithms is that for a constant number k of items, the optimal mechanism for any number N of types (where a type here is a vector of k values) has at most d = 2 k possible prices, one for each bundle of items, which is again a constant. This allows to partition the d-dimensional space of price vectors into cells, such that 1 A similar contrast was noted in the case of Myerson's mechanism with correlated buyers, see Dobzinski et al. (2011), Papadimitriou and Pierrakos (2011). 2 And in fact, it remains tractable for any constant number of items.
for each cell the buyer has the same behavior. In contrast, in the dynamic problem the optimal deterministic mechanism for 2 items and N types (where a type is a vector of two values) might have N different price pairs (one price for each item), which is not a constant. In fact, in our construction we have two candidate price pairs for each type, leading to an exponential number of candidate solutions. Thus, the dynamic problem is computationally much harder than the static one. Furthermore, as we prove later, the dynamic problem is tractable (at least for two items) when stages are independent, as well as when randomization is allowed. Therefore, correlation and determinism are both necessary for our hardness result.
Finally, even though we do not know whether computing the optimal deterministic ex-ante IR mechanism is tractable for correlated stages, notice that this task is trivial for independent stages, even for D > 2 items: the optimal mechanism offers a take-it-or-leave-it price for the first item (recall that the buyer knows her value for this one) and all the remaining items for a take-it-or-leave-it price equal to their expected value (which will be always accepted by a risk-neutral buyer).
In Section 4 we present positive results for deterministic mechanisms. First, if the support of the distribution of the first stage valuation is a constant, then the problem becomes easy: once we have fixed the second stage prices (there is only a constant number of them), we can easily optimize the first stage prices, by writing a simple linear program. A similar simple linear program suffices even when the second stage prices are not fixed, but we have decided between which second stage types each price should be in. The overall number of linear programs we need to solve is the number of second stage types raised to the power of first stage types, which is polynomial. Second, if we are given the first stage prices and we want to optimize the second stage prices, we can find a (1 -) approximately optimal mechanism in time polynomial in 1/ and the size of the input, for all > 0 (that is, there exists an FPTAS), based on an integer program that happens to be totally unimodular. These two positive results point to the source of one major difficulty in proving NP-completeness of the problem: in our construction the prices of both items must vary over types. Our last positive result for deterministic mechanisms is a polynomial time algorithm for computing the optimal deterministic mechanism when the stages are independent. The two driving factors of this result are (1) the allocation of the first stage item is a monotone function, and, (2) the first stage price of a type t i is either zero, or her valuation for the first item. Since all first stage types have the same second stage distribution (since the stages are independent), the IC constraints severely limit the amount that we can price discriminate between different first stage types. Combining this observation with the two aforementioned facts we can show that the number of optimal mechanisms is a small polynomial: a simple enumeration is computationally tractable.
We proceed to study randomized mechanisms. A deterministic and optimal mechanism can often be expressed as the solution to an integer program (but finding an optimal solution to an integer program is an NP-complete problem). The relaxed program,foot_0 which can be solved in polynomial time, typically encodes the optimal randomized mechanism. In Section 5 we show that the problem of finding the optimum randomized mechanism can be solved in time polynomial in the number of types (where a type here specifies the buyer's values for all items, across stages), and in fact for any finite number of stages of sale and for any constant number of buyers. We show how to optimize over mechanisms that satisfy a number of different notions of incentive compatibility (some of which are with loss of generality, but, as we argue, might be worth optimizing over). Several reasons why this LP should be have an exponential number of variables and constraints must be overcome. For example, our mechanisms elicit from each buyer and each stage only the value of the buyer for the item in that stage. Thus, for our choice of incentive compatibility, naively there are exponentially many ways a buyer can misreport: when strategizing about what to report on the current stage, our buyers consider all (exponentially many) functions from future realizations of her value to future reports. Carefully defining the IC constraints by backward induction resolves this issue. A second issue is that one seems to need to "remember" in each stage the utility accumulated so far for each buyer in order to achieve ex-post individual rationality, which requires that the total utility of a buyer is non-negative at the end, once all uncertainty has been resolved. We overcome this obstacle by reducing ex-post IR mechanisms to stage-wise ex-post IR mechanisms (the utility in each stage is non-negative).
See Table 1 for a summary of our results.
We briefly discuss research in dynamic mechanism design that is most related to the current work. For an extensive review of the literature see Bergemann and Said (2011) and Bergemann and Välimäki (2019). The study of revenue maximization in an environment where the agent's private information changes over time was initiated by Baron and Besanko (1984). Revenue optimal dynamic auctions are studied more recently by Courty and Li (2000), Es ő and Szentes (2007) and Pavan et al. (2009Pavan et al. ( , 2010Pavan et al. ( , 2014)). A common constraint in these works is that the principal has to satisfy all of the sequential incentive constraints, but only a single ex-ante participation constraint.
Subsequent to the preliminary version of this paper, Ashlagi et al. (2016) provide characterizations of the optimal ex-post IR, periodic incentive compatible dynamic mechanism, with m independent stages and n buyers. Ashlagi et al. (2016) show that there exists an optimal mechanism that has stage utility equal to zero for all stages, except maybe the last, where the seller might have to pay the buyers. Surprisingly, their mechanism can be described via updates, at every stage, to a scalar variable that guides the future allocation and payments. The authors use this characterization to give a mechanism that obtains a 1 2 approximation to the optimal revenue for the single buyer problem. Mirrokni et al. (2016a) study dynamic mechanisms with an interim IR constraint. They define a class of mechanisms called bank account mechanisms. Bank account mechanisms maintain a state variable, the balance, that is updated throughout the execution of the mechanism depending on a "spending" and "depositing" policy. The allocation and payment at each stage depend on the report and the balance. Mirrokni et al. (2016b) study revenue maximization for bank account mechanisms subject to an ex-post IR constraint. In Section 5 we use their reduction from ex-post IR mechanisms to stage-wise ex-post IR mechanisms in order to simplify our linear program. Mirrokni et al. (2020) study the design of non-clairvoyant dynamic mechanisms. An oblivious dynamic mechanism decides on the allocation and payment for stage k using information only about the current and past stages, i.e. it is oblivious about the buyers' value distributions D k+1 , . . . , D m . Their mechanism ObliviousBalance runs at each stage a combination of Myerson's optimal auction, a second price auction, and the money burning mechanism of Hartline and Roughgarden (2008). Their mechanism obtains a 1 5 approximation to the optimal revenue. Mirrokni et al. (2019) show that optimal dynamic auctions are virtual welfare maximizers, under some definition of virtual welfare. Specifically, in each stage d the optimal dynamic auction is a second price auction on an appropriately defined virtual value space. In order for the virtual welfare maximizing allocation rule to be monotone, ironing is necessary, but unlike ironing in Myerson's optimal auction, the ironing step is interdependent across the values of different buyers. Liu and Psomas (2018) study prior-independent dynamic mechanisms, and more specifically, they show an analogue of the classic Bulow-Klemperer result in auction theory. m items are auctioned off in m consecutive stages to n independent and identical buyers. They show that recruiting 3n more buyers and executing a simple second price auction at each stage yields more revenue than the optimal dynamic auction, even when the buyers' values are correlated across stages, under a monotone hazard rate assumption on the stage (marginal) distributions. This result can be turned into a 4-approximation algorithm by simulating the 3n additional buyers. For the general case, beyond marginals that have monotone hazard rate, we are not aware of any algorithms that give a constant approximation, even for a single buyer and two correlated stages.
Agrawal et al. ( 2018) study revenue maximization for a buyer who is not fully rational, but instead uses some specific form of learning behavior. They give a simple state-based mechanism that gives simultaneously a constant approximation to revenue extracted by the optimal auction for a k-lookahead buyer for all k, a buyer who is a no-regret learner, and a buyer who is a policy-regret learner.
The Two-stage Mechanism problem involves a seller with 2 items to sell to a single buyer. The items are sold in two consecutive stages, one item per stage. The buyer privately learns her types over time. In the beginning of stage i she learns her type for that stage. The buyer can have one of |V (1) | types in the first stage. The i-th first stage type t i occurs with probability Pr[t i ]. A buyer with first stage type t i has valuation v (1) i for the first item, and a probability distribution f i over valuations/second stage types for the second item. We assume that each type t i has a different first stage valuation v
(1) i , and therefore we use type and valuation interchangeably. 4 The joint distribution is known to the seller and the buyer. We 2) for the valuation of the second stage item, and V (2) for the support of the distribution in stage 2. We assume that 0 is always in the support of f i , for all i.
The order of events is as follows: (1) The buyer privately learns her type t i ∈ V (1) for stage 1, and sends a message to the mechanism, (2) the seller implements an allocation x 1 ∈ {0, 1} for item 1 and charges a payment p, (3) the buyer obtains stage utility u 1 = v (1) i • x 1p, (4) the buyer privately learns her value (second stage type) v (2) for the second stage item, and sends a message to the mechanism, (5) the seller implements an allocation x 2 ∈ {0, 1} for item 2 and charges a payment q, (6) the buyer obtains stage utility u 2 = v (2) • x 2q. The buyer's overall utility is u 1 + u 2 , i.e. the buyer is additive without discount. Motivated by practical considerations (e.g. in advertising auctions bidders must submit a bid, not an abstract signal/message) we restrict the set of messages the buyer can send to the mechanism to be types, i.e. the buyer sends a type b (1) ∈ V (1) and a value b (2) ∈ V (2) in the first and second stage, respectively.
We focus on dynamic, direct and deterministic mechanisms. A deterministic mechanism for this problems consists of an allocation, payment rule pair (x 1 , p) for stage 1, and an allocation, payment rule pair (x 2 , q) for stage 2. x 1 and p map V (1) to {0, 1} and R, respectively. x 2 and q map V (1) × V (2) to {0, 1} and R, respectively. That is, the allocation and payment in the second stage can depend on the report in the first stage. Note, however, that the buyer does not report all the values she has observed so far in each stage 2, but only her value in stage 2. Our goal is to design a mechanism that maximizes the seller's expected revenue, subject to dynamic incentive compatibility and ex post individual rationality.
The dynamic revelation principle (Myerson, 1986;Sugaya and Wolitzky, 2021) states that there is no loss of generality in restricting attention to dynamic direct mechanisms where buyers report their information truthfully (the buyer's reported type coincides with her true type). However, the dynamic revelation principle does not require that a buyer reports their information truthfully in the second stage after a lie in the first stage (see Pavan et al. (2014) for an application of the dynamic revelation principle in a similar context). As we see later in this section, our mechanisms will satisfy a stronger notion of incentive compatibility, where a buyer reports her true value in the second stage, no matter what the report in the first stage was. This should be intuitively obvious since the second stage utility v (2) x 2 (t i , v (2) )q(t i , v (2) ) is unaffected by the first stage type t i (beyond its effects on the mechanism itself). Dynamic incentive compatibility (DIC) can be defined by backward induction. In the last stage, assuming honest reports so far, it should be incentive compatible for the buyer to report her true type (using the standard notion of incentive compatibility in static mechanism design). That is, assuming an honest first stage report t i ∈ V (1) , and all v (2) ∈ V (2) (such that v (2) is drawn from f i with positive probability), and for all b (2) ∈ V (2) we have
(1) Then, in the first stage, it should be incentive compatible for the buyer to report her true type. Since the second stage mechanism satisfies Equation (1), when calculating her expected future utility after being honest in stage one, she should assume that she will report her true second stage type honestly as well. Let u 2 (t ; v (2) , b (2) ) = v (2) x 2 (t , b (2) )q(t , b (2) ) be the second stage utility when the buyer with second stage value v (2) reports b (2) , and her first stage report was t . For all t i , t ∈ V (1) we have that
A mechanism is ex-post individual rational (ex-post IR) if it guarantees non-negative utility for the buyer. That is, the buyer's utility should be non-negative in all outcomes output by the mechanism, assuming she reports truthfully. For stage 2 this implies that for all t i ∈ V (1) and all v (2) ∈ V (2) the mechanism satisfies
Since v (2) occurs with non-zero probability for all t i , it must be that in the first stage allocation and payments satisfy v
Without loss of generality we therefore have that v (1) i x 1 (t i )p(t i ) ≥ 0 (since, if q(t i , 0) is negative, we can always increase it to zero, and decrease p(t i ) appropriately, without affecting incentives). As we will see in Section 5, and as already shown by Mirrokni et al. (2016b), an ex-post IR mechanism can be turned into a stage-wise ex-post IR mechanism (non-negative utility in each stage) with at least as much expected revenue.
What can we say about the structure of deterministic revenue-optimal dynamic mechanisms? The point of this paper is that they are quite complex. Nonetheless, we can significantly restrict our search space. So far we have allowed mechanisms to be adaptive: the allocation and payment in the second stage depend on both the first stage and second stage reports. Call a mechanism semi-adaptive if it depends only on the buyer's declared type. Slightly overloading notation, in such a mechanism the buyer reports a type t for the first stage, and the seller, based on it, produces a price p(t ) for the first stage and a price q(t ) for the second (a price can be infinity, in which case the seller does not offer this item). Notice that these mechanisms satisfy a much stronger notion of truthfulness: the buyer is honest in stage two even after a lie in stage one. This seemingly weaker protocol is optimal.
[m3G; v1.314] P.6 (1-29) C. Papadimitriou, G. Pierrakos, A. Psomas et al. Games and Economic Behavior
There is a revenue-optimal deterministic mechanism that is semi-adaptive.
Similar results are known for deterministic contracts in sequential screening models. For example, Courty and Li (2000), Krähmer and Strausz (2011) show that optimal deterministic contracts can be implemented as a menu of option contracts. The proof Lemma 2 is similar to the proof of these results; we provide it here for completeness.
Proof of Lemma 2. Suppose that in a deterministic revenue-optimal mechanism satisfying dynamic incentive compatibility and ex-post individual rationality, the price on the second stage q(t i , v (2) ) depends on the buyer's types on both stages, t i = (v (1) i , f i ) andv ( 2) . Fix any first-stage type
i , f i ), and let u * = arg min u≥q(t i ,u) q(t i , u) be the second stage valuation which minimizes that second stage price, among all second-stage valuations for which the item is allocated.
• v (2) > q(t i , u * ): the buyer could declare type u * in order to buy the item for the minimum price. Therefore, since the mechanism is incentive compatible, it must charge
we can assume without loss of generality that the price is again q(t i , u * ), since the buyer would anyway not buy the item for the current price
: the buyer's utility remains zero for any price q(t i , v (2) ) ≥ q(t i , u * ); however, the seller's revenue is maximized when selling the item for price
Finally, any buyer with a different first-stage type t j = (v (1) j , f j ) that attempts to deviate and declare type t i on the first stage, would also, with loss of generality, deviate her second-stage valuation to u * .
Note that it is not clear whether the same is true for randomized mechanisms. Our proof crucially used the fact that, no matter what my true valuation is, the buyer prefers a smaller posted-price. But, in the case of randomized mechanisms, we do not have an order over distributions of prices: one distribution may be more attractive to one type, while another distribution is more attractive for another type. For example, consider a lottery that offers the item for a price of 8 with probability 1/2, and with probability 1/2 doesn't offer the item. This lottery looks more attractive than a posted price of 12 to a buyer whose value is in the interval [8,16). If the buyer's value is larger than 16, then the posted price looks more attractive.
Once we restrict ourselves to semi-adaptive mechanisms, the mechanism becomes two functions p, q mapping the support of the prior to the reals. Let p(t) be the price charged for the first stage item, and q(t) the price charged for the second stage item, when the buyer reports a type t. Let u(t, t ) be the expected utility of the buyer when her true type in the first stage is t and she declares t . This utility is the utility of the first stage plus the expected utility for the second stage, when offered a take-it-or-leave-it price q(t ). We want u(t, t) ≥ u(t, t ) for all t, t ∈ V (1) .
A nice, compact form to express our DIC constraints is using the reverse cumulative distribution of the second stage:
The observation here is that the buyer's second stage utility for a type t, when charged price q in stage 2, is ∞ q Ft (x)dx. So, for any two possible first-stage types t = (v (1) , Ft ) and report t = (b (1) , Ft ), the IC constraints are:
• If both t and t receive the item on the first stage:
Ft (x)dx.
• If neither receives the item on the first stage: q(t) = q(t ).
• If t receives the item on the first stage, but t does not:
Ft (x)dx.
We write Rev(t i , p i , q i ) to denote the seller's revenue, when charging the (i-th) type t i the first stage price p i and second stage price q i . We will write Rev (1) or Rev (2) when we want to refer only to the revenue from the first or second stage, respectively.
[m3G; v1.314] P.7 (1-29)
C. Papadimitriou, G. Pierrakos, A. Psomas et al.
Fi when there is (dotted) an (i, j) edge for j > i, and when there isn't (dashed). (For interpretation of the colors in the figure(s), the reader is referred to the web version of this article.)
In this section we briefly describe the construction of our main result.
Theorem 3. Finding the optimal deterministic two-stage mechanism is strongly NP-hard.
Given a graph G = (V , E), we construct a joint distribution of valuations such that the optimal feasible revenue (for deterministic DIC and ex-post IR mechanisms) is a strictly increasing function of the maximum independent set in G.
More specifically, with each vertex i ∈ G we associate a type t i with valuation v (1) = B i for the first stage. For each type t i , we want to have two candidate price pairs:
The former will give more revenue, but for every edge (i, j) ∈ E, it will be a violation of the DIC constraints to offer to type t i the pair (B i , C i ) and to type t j the pair (B j , C j ). Thus, if the difference r in expected revenue between (B i , C i ) and (A i , D i ) is the same for all i, charging the former for all the vertices of an independent set S and the latter for the rest of the vertices will be a valid pricing, with revenue i∈V Rev(t i , A i , D i ) + r|S|. In order to impose the desired structure between (B i , C i ) and (A i , D i ), we have an extra type t * , with valuation v (1) = P * on the first stage. t * appears with very high probability. This way we make most of our revenue from this type, and thus force every revenue-optimal mechanism to charge this type the optimal prices, (P * , Q * ). The IC constraints for type t * introduce strong restrictions on the prices for other types.
The restriction on each edge (i, j) is forced by the IC constraints for t i and t j , via a careful construction of the distributions over their second-stage valuations. The second stage distribution of t i is Ft i and is carefully tuned in the range [D j-1 , D j ] (note that C j is in this interval) depending on whether or not (i, j) ∈ E. For ease of notation we write F i instead of F t i . See Fig. 1.
The distribution of valuations on the first stage is rather simple. Let n = |V | denote the number of vertices in G. With probability 1p, the buyer is of type t * and has first-stage valuation v (1) = P * = n; with probability p • w i , the buyer is of type t i and has first-stage valuation v (1)
. The parameters p and w i are defined later. Notice that the first stage has support of size n + 1.
We will show that it is always possible to charge type t i either her full value B i on the first stage, or slightly less:
For type t * , we always want to charge the full price, P * . Observe that
For the second stage we are interested in prices C i or D i for t i , and Q * for t * . Although we only have n types, it will be convenient to think about two more special prices, which we denote C n+1 and D n+1 . We define C i , D i and Q * later; for now let us mention that
The crux of the reduction lies in describing the distributions of the second-stage valuations for each type. It will be
[m3G; v1.314] P.8 (1-29)
C. Papadimitriou, G. Pierrakos, A. Psomas et al.
The choices of the cumulative distributions in our construction are summarized in Table A.2, in Appendix A. Type t i never has nonzero second-stage valuation less than C i , thus the cumulative distribution Fi (x) for x ∈ (0,
Intuitively, this will make C i an attractive price for the seller. Notice that γ n ≈ e is a constant. At each special price thereafter, Fi decreases by some multiplicative factor that is related to γ . The exact value of Fi (x)
for x ∈ (D j-1 , D j ) depends on whether there is an edge (i, j) in G. 5 After D n+1 , the distribution for all types t i is the same. Fi halves at each 2 k D n+1 , and it is 0 after Q * = 2 8γ 4(n+1) D n+1 .
The distribution F * is simpler to describe. F * (x) is equal to h 1 for x ∈ (0, C 1 ), and decreases by a multiplicative factor of γ 2 at each special price thereafter. Type t * never has valuations between D n+1 and
. Intuitively, this will make Q * an attractive price for the seller. Notice also the contrast between this and the gradual decrease of Fi 's.
We describe how to fix the last parameters in Appendix A. We prove the soundness of our construction in Appendix B; the proof of completeness is postponed to Appendix C.
We have three positive results for deterministic mechanisms. We give here a brief sketch of the proofs and postpone further details to the appendix.
Our first result shows that given first stage prices, optimizing over second stage prices (in a way that the joint mechanism is DIC) can be approximated by a fully polynomial-time approximation scheme (FPTAS), that is, an algorithm that for all > 0 runs in time polynomial in the size of the input and 1 , and returns a mechanism whose revenue is (at least) a (1 -) factor of the optimal revenue. For this result, we subdivide the range of second-stage prices into a grid of accuracy 1/K (by taking K large enough we obtain an FPTAS), and consider 0 -1 variables who act like indicators for the event "the price q i is not larger than the jth grid point." It turns out that the DIC constraints become totally unimodular. Therefore, the corresponding linear program (which can be solved in polynomial time) has an integral optimum. For more details see Appendix D.
Theorem 4. If the prices in the first stage are fixed, then the optimum deterministic mechanism can be approximated by an FPTAS.
Our second result says that if the number of first stage types |V (1) | is a constant, the NP-hardness result no longer holds, and the optimum deterministic mechanism can be computed in polynomial time (polynomial in the support of the second stage distribution, |V (2) |). For this result, we notice that once we have fixed, for each type, the interval between secondstage valuations in which the second-stage price for this type lies (larger than all if the item is not allocated to this type), then the DIC constraints become linear inequalities. This is because the cumulative distributions are piecewise constant, and thus the integrals in the DIC constraints become linear functions once we know the interval in which the bounds of each integral lie. Since there are |V (2) | |V (1) | ways to map the |V (1) | second-stage prices to the |V (2) | second-stage intervals, and we assume that |V (1) | is constant, we only need to solve a polynomial number of LPs.
Theorem 5. If the number of types (the support of first-stage valuations) is constant, then the optimum deterministic mechanism can be computed in polynomial time.
Our last result states that for independent stages, the optimum deterministic mechanism can be computed in polynomial time. We observe that once correlation is removed the IC constraints between different types are transitive: satisfied DIC constraints between types t i , t j and t j , t k imply satisfied constraints between t i and t k . Moreover, the allocation function (for the first stage item) is monotone, and the prices of the types that are allocated the first stage item have the following structure. Either the first stage price is equal to the valuation, or the second stage price is zero. Using these observations we can significantly reduce the search space and find the optimal mechanism in polynomial time, essentially by enumerating. For more details see Appendix E. Theorem 6. If the stages are independent, the optimum deterministic mechanism can be computed in polynomial time.
Can we do better by using randomization? In this section, we construct an LP for the optimum randomized adaptive mechanism for multiple buyers and multiple stages. Specifically, we study the case of k independent buyers and D stages. We show how to compute the optimal randomized mechanism under two definitions of dynamic incentive compatibility (DIC): DIC in dominant strategies (D-DIC) and DIC in Bayesian strategies (B-DIC). We also show that it's possible to compute
the optimal mechanism when these notions are satisfied only under honest private histories ("on-path" truthful), as well as under all private histories (i.e. truthfulness even after a past lie).
The problem we consider here is the natural generalization of the problem in Section 2. There are k buyers and D items, sold in D consecutive stages, one item in each stage. Buyers have additive utility functions, without discounting across time, that is, the final utility of a buyer is the non-discounted sum of her stage utilities. In stage d buyer i has type/valuation v
). In other words, the type in stage d for buyer i can depend on the realized types from previous stages for buyer i (but is independent of the types of other buyers in this stage or any other stage). The joint distribution is known to the seller, as well as all the buyers, but the realizations are private. That is, the input to the seller's problem is for every buyer i ∈ [k], and every possible vector of valuations across stages
i ) the probability Pr[ v i ] that this vector of values is realized. We assume that the value zero is in the support of every stage distribution (no matter what the values were for the previous stages), for all buyers. Let
i | be the number of types of buyer i. We note that typically, |T i | grows exponentially with D (and in what follows we give algorithms that run in time polynomial in the |T i |s). Also, let
be the set of possible type vectors in stage d.
A dynamic (direct) mechanism consists of, for each buyer i ∈ [k] and stage d ∈ [D], an allocation rule x d i and a payment rule p d i that maps reported values v [d] = (v (d) 1 , . . . , v (d) k ) ∈ V [d] to an allocation in [0, 1] and a payment in R, respectively. Both of these functions can depend on the public history of reported valuations so far h [d-1] = (v [1] , . . . , v [d-1] ), as well as the outcomes of the mechanism (allocations and payments) ω [d-1] = (ω 1 , . . . , ω d-1 ), where ω t = (x, q 1 , . . . , q k ) if in stage t the item's allocation was x ∈ {0, 1, . . . , k} and the payment of buyer i was q i . We therefore write x d i (h [d-1] , ω [d-1] ; v [d] ) for the allocation and p d i (h [d-1] , ω [d-1] ; v [d] ) for the payment. Note that the number of outcomes is exponential in the number of stages; as we will see later in this section, without loss of generality we can focus on mechanisms whose allocation and payment rules in stage d do not depend on ω [d-1] .
The order of events in stage d is as follows:
(i) Each buyer i privately learns her type v (iii) The mechanism allocates the item to buyer i with probability x d i (h [d-1] , ω [d-1] ; v [d] ) and charges p d i (h [d-1] , ω [d-1] ; v [d] )
(and note that the allocation and payment could be correlated). (iv) Each buyer i obtains (realized) stage utility u
ip d i if they were allocated the item (and u
were not allocated but were charged a payment).
(v) The public history so-far is updated to include the reported types v[d] , and the outcome in stage d (which buyer got the item and payments).
We note that, importantly, when the buyer decides what to report in step (ii), they evaluate the stage utility from stage d in expectation over the realization of the stage d lottery, i.e. they calculate u
Feasibility A mechanism is feasible if it allocates the item in stage d to at most one buyer in expectation. That is, for all d ∈ [D], for all histories h [d-1] , ω [d-1] and possible reports v [d] , i∈ [k] x d i (h [d-1] , ω [d-1] ; v [d] ) ≤ 1.
The dynamic revelation principle (Myerson, 1986;Sugaya and Wolitzky, 2021) states that there is no loss of generality in restricting attention to dynamic direct mechanisms where buyers report their information truthfully "on-path", that is, the mechanism does not need to guarantee truth-telling after a lie in a previous stage. This distinction was not important for the deterministic two stage mechanism of Section 2, since optimal mechanisms for the weaker notion ended up being semi-adaptive (which satisfies the stronger notion). However, this might not be the case for the multi-agent, multi-stage problem we study here (since, e.g., the future utility of a buyer in stage 2 is calculated using both the public history and the private history, while her stage utility only depends on the public history and the current value).
It is intuitively clear that asking for truth-telling even after lies is a strictly harder computational task, since it needs to take care of multi-stage deviations (and there are exponentially many of these, even for two stages). We show that, in our setting, optimizing with respect to mechanisms that satisfy either notion of incentive compatibility is computationally feasible. Roughly speaking, optimizing with respect to the stronger notion will boil down to writing a linear program with an IC constraint for each buyer and each public history and private history (which is a polynomial number of constraints with respect to the size of the input/the joint distribution over types). Optimizing with respect to the weaker notion boils down to writing an IC constraint for each buyer and each public history (since the assumption here is that a buyer has been honest so far, her private history matches the public history), which is a smaller number of constraints. For the remainder of this section we will focus on the computationally harder task of computing the optimal mechanism that satisfies the stronger notion of incentive compatibility; we explain how our solution can be adjusted to work for the weaker notion after we prove our main theorem.
A mechanism is dynamic incentive compatible (DIC) if, informally, each buyer i is better off reporting her true value v
in each stage d. We consider two variations of DIC. The first one, DIC in dominant strategies (D-DIC) requires that truthful reporting in stage d maximizes the utility of each buyer, regardless of the past (i.e. for all histories), and regardless other buyers' reports. The second one, DIC in Bayesian strategies (B-DIC) requires that truthful reporting in stage d maximizes the utility of each buyer, regardless of the past, and in expectation over the other buyers' truthful reports in this stage and the future. We note that often D-DIC is too strict of a requirement in general dynamic mechanism design settings and might come with loss of generality (see for example Bergemann andVälimäki (2010, 2019)). However, in our setting, natural mechanisms satisfy this seemingly strong requirement. For example, running a second-price auction in each stage, which is also welfare optimal, satisfies this notion. We therefore suggest that, even though this class might be with loss of generality, it is worth optimizing over. We start by defining D-DIC. Naively, since re-reporting of past types is not allowed, the incentive constraints must account for multi-shot deviations. For example, lying only in stage one could decrease a buyer's utility, and so does lying only in stage two; and yet lying on both stages increases her expected utility. Therefore, when deciding to lie, the buyer must choose in advance among all exponentially many different strategies that deviate from the truth now and in the future. Notice that the number is exponential even for two stages: the optimization is over functions from true pairs of types to declared pairs of types. This is the first obstacle in writing a polynomial size LP. However, similarly to Section 2, we can define both variations of DIC via backward induction. Specifically, for the last stage D, for all buyers i ∈ [k], for all histories of reported types h [D-1] = (b [1] , . . . , b [D-1] ), and past outcomes of the mechanism ω [D-1] = (ω 1 , . . . , ω D-1 ), and for all last stage reports v
-i ) be the expected utility of buyer i for participating in the last stage D, when the public history is h [D-1] , ω [D-1] , the private history of buyer i is h -i . By the previous argument, this utility is calculated assuming truthful reporting for buyer i in stage D: -1] , ω [D-1] ; v [D] )p D i (h [D-1] , ω [D-1] ; v [D] ) .
We note that
-i ) (and generally U d i (.)) for "on-path" truthfulness, i.e. when the mechanism doesn't require truth after lies, is defined slightly differently, by taking an additional maximum over the report in stage D, i.e. it is equal to -1] , ω [D-1] ; v (D) -i , v)
.
For the second to last stage, let u D-1 i (h [D-2] , ω [D-2] ;
) be the stage utility of buyer i when the history is h [D-2] , ω [D-2] , all other buyers report v (D-1)
i , but she reports v. We note that the stage utility does not depend on the buyer's private history h
, v] be the public history (in stage D)
] and is independent of the report.
Then, for D-DIC we have that for all h
Note that the definition of U D i includes the expectation over types in stage D, therefore in the second term (which captures the remaining utility from participating in the mechanism) we only need to take an expectation over the outcome of the mechanism in stage D -1.
Proceeding backwards for all stages d, for D-DIC we have that for every buyer i, all histories so-far h
all reports for the other buyers in stage d (v
), all types of buyer i v
)],
[m3G; v1.314] P.11 (1-29)
C. Papadimitriou, G. Pierrakos, A. Psomas et al.
where (1) u d i (h [d-1] , ω [d-1] ;
is the stage utility of buyer i when the history is h [d-1] , ω [d-1] , all other buyers report v
i , but she reports v, (2) h [d] and ĥ[d] are the two public histories in stage d + 1 that correspond to truthful and non-truthful reporting of buyer i in stage d, and (3)
) is the expected utility of buyer i for participating in the mechanism in stages d + 1 through D (which depends on the private history h[d-1] i and the other buyers' future reports v
) is typically referred to as the continuation utility, and is equal to:
and ω z: = ω z , . . . , ω . Equivalently,
) can be written recursively as
) .
For "on-path" truthfulness, we need to take an additional maximum over the report of stage d + 1 inside this expectation, i.e.
) is equal to
) .
For B-DIC we need to take an additional expectation over v
, where each v (t) j for buyer j is drawn from the marginal conditioned on h
, the history of reports of buyer j. Note that this argument assumes that all other buyers have been truthful so far. Using identical arguments as above, we have that for every buyer i, all histories so-far
i , ω [d-1] , all v (d) i , and all stage d deviations v: [d-1] , ω [d-1]
i (h [d-1] , ω [d-1] ;
Individual rationality A mechanism is ex-post individual rational (ex-post IR), if once all uncertainty is resolved, every buyer always has non-negative utility. Given a history of h
, ω [d-1] ) be the utility buyer i has accumulated so far, i.e. the sum of values for the items she received minus the payments, where the allocations and payments are according to ω [d-1] , and values are according to h [d-1] and h [d] i . A dynamic mechanism outputs for every stage d ∈ [D], history h [d-1] , ω [d-1] and stage d reports v [d] a distribution over stage d outcomes: an outcome ω d = (x, q 1 , . . . , q k ) occurs with probability Pr[ω d ] (that depends on h [d-1] , ω [d-1] and v [d] ) specifies which buyer x ∈ {0, 1, . . . , k} won the item (if any) and the payment q i for each buyer i. The exact distribution depends on the correlation between x d i (.)
and p d i (.). Formally, an ex-post individual rational mechanism satisfies, for all stages d ∈ [D], all public histories h [d-1] , ω [d-1] and private histories h[d-1] i that match the public history (i.e. we only guarantee individual rationality if the reports so far have been honest), stage d reports v [d] and stage d outcomes ω d = (x, q 1 , . . . , q k ) that occur with positive probability:
where I(e) is the standard indicator function for an event e (takes the value 1 if e occurs, and zero otherwise). Since we guarantee ex-post IR with respect to the public history (that is, we provide no guarantees for buyers that have lied), we will omit the private history of a buyer when talking about the IR constraints, and assume it matches the public history. Before we give our main result we make a number of simplifications to the expression above for ex-post IR.
The reason an adaptive mechanism keeps track of the allocations and payments so far is so that is can ensure that the ex-post IR constraint is satisfied. Of course, having a variable for every possible past outcome is prohibitively costly: even when the number of types is small, the number of possible outcomes grows exponentially with the number of stages. Fortunately, one can show that without loss of generality, we can focus on stage-wise ex-post IR mechanisms, that is, non-negative stage utility. Formally, a mechanism is stage-wise ex-post IR if for all stages d ∈ [D],
C. Papadimitriou, G. Pierrakos, A. Psomas et al.
public history h [d-1] and private history h[d-1] i that matches the public history, stage d reports v [d] and stage d all outcomes ω d = (x, q 1 , . . . , q k ) that occur with positive probability (which depends on the history and reports):
Equivalently, if buyer i does not receive the item she should not pay, and if she receives the item she should pay at most her (reported) value.
The equivalence between ex-post IR and stage-wise ex-post IR can be shown via an easy reduction (from ex-post IR to stage-wise ex-post IR), see for example Mirrokni et al. (2016b). For completeness we include this reduction in Appendix F. The main idea is that given an ex-post IR mechanism M, one can construct a stage-wise ex-post IR mechanism M that charges each bidder exactly their bid for each of the first D -1 stages, and in the last stage charges the difference between the total payments in M and the total payments so far in M . Therefore, we can restrict ourselves to mechanisms that guarantee ex-post non-negative utility in each stage, and that only take as input, in each stage, the history of reported values so far.
Correlation between allocation and payment A final issue when writing a linear program is the choice of variables. The "standard" way, by which we mean the most common formulation for one-shot mechanisms, is to have, for each buyer and each vector of reports, a variable for the expected allocation and a variable for the expected payment. Taking this to the dynamic setting, we would have for each stage, history, buyer and reports a variable for the expected allocation and a variable for the expected payment. But, because of the ex-post IR constraint when implementing the corresponding mechanism, correlation is necessary. To see this most clearly, consider an example where the LP, in a certain situation (i.e. stage, history etc) allocated an item to buyer i with probability 1/2 and the expected payment was p. How would we implement this in an ex-post IR way, so that the buyer's utility is always non-negative? For example, we would need to ensure that when the item is not allocated the payment is zero. Thus, correlation between payment and allocation is necessary, a feature that seems difficult to work if the goal is to write a poly-sized linear program. 6 Fortunately, a simple correlation scheme will allow us to by-pass this issue.
Consider a feasible, stage-wise ex-post IR, and DIC (D-DIC or B-DIC) mechanism given via allocation probabilities and expected payments. That is, for every stage d, histories h [d] , ω [d] , buyer i, and possible reports v [d] , x d i (h [d] , ω [d] ; v [d] ) is the probability that this buyer is allocated item d, and p d i (h [d] , ω [d] ; v [d] ) is the expected payment. Stage-wise ex-post individual rationality implies that v i • x d i (h [d] , ω [d] ; v [d] )p d i (h [d] , ω [d] ; v [d] ) ≥ 0. We can implement this mechanism in a way that the ex-post IR constraint is respected even after the random outcome for stage d is selected (feasibility and truthfulness will be immediately implied). With probability x d i (h [d] , ω [d] ; v [d] ) we allocate the item to buyer i and charge her p d i (h [d] , ω [d] ; v [d] )/x d i (h [d] , ω [d] ; v [d] ). With probability 1x d i (h [d] , ω [d] ; v [d] ) we do not allocate to i, and charge her nothing. The expected utility of the buyer remains v i • x d i (h [d] , ω [d] ; v [d] )p d i (h [d] , ω [d] ; v [d] ). Furthermore, when the item is allocated, her utility is v ip d i (h [d] , ω [d] ; v [d] )/x d i (h [d] , ω [d] ; v [d] ) ≥ 0, and zero when not allocated, so the stage-wise ex-post IR constraint is satisfied.
The optimal randomized mechanism LP Finally, we are ready to describe our LP for computing randomized adaptive mechanism for k > 1 buyers and D > 2 stages. Recall that the input to our problem is, for every buyer i ∈ [k], and every possible vector of valuations across stages We prove the D-DIC case first and discuss how to alter the proof to take care of the B-DIC case, and "on-path" truthfulness, afterward.
Theorem 7. For any number of stages D, and a constant number of independent buyers k, the optimal, adaptive, randomized D-DIC mechanism can be found in time poly(D, |T | 2k+3 ).
i (h [d-1] ; v [d] ) and p d i (h [d-1] ; v [d] ) for the probability of allocating item d and the payment, respectively, to buyer i when the reports on stage d are according to v [d]
is the report of buyer j), and the history up until stage d is according to h [d-1]
[m3G; v1.314] P.13 (1-29) C. Papadimitriou, G. Pierrakos, A. Psomas et al. Games and Economic Behavior
• Objective: Our objective is to maximize expected revenue, which can be expressed in our variables as R = D d=1 h [d-1] v [d] Pr [h [d-1] , v [d] ] k i=1 p d i (h [d-1] ; v [d] ).
Notice is that Pr[h [d-1] , v [d] ] can be easily computed from our input. It is the product over buyers i of Pr[v (1) i ,. . . ,v (d) i ]; the latter term can be calculated by summing up the probabilities of all possible (at most |T | of them) futures for buyer i.
• Feasibility: We need to ensure that we are not over-allocating any item, i.e. allocating an item with probability more than 1.
, h [d-1] , v [d] :
• Stage-wise ex-post IR: The stage utility should be non-negative for any buyer i, all stages d, histories h [d-1] , valuations [d-1] ; v [d] )p d i (h [d-1] ; v [d] ) ≥ 0.
The number of constraints is O (k
). • Incentive compatibility: In order to express D-DIC compactly, we introduce the following intermediate variables. Let
, t) be the expected utility of buyer i from participating in the mechanisms in stages d + 1 through D, when the public history up until stage d is h [d-1] , buyer i's private history is h
i , the other agents' stage d and future reports are according to v
, and buyer i's true stage d type is t. The number of these variables is O (k
thus the total number of variables remains polynomial in the size of the input for a constant k. Furthermore, as we've already discussed, the future expected utility can be easily calculated. Thus, we can recursively define U i (d
, t) as follows (and we define U i (D + 1; .) = U i (D + 2; .) = 0 for all i to make the recursion easier to write):
Writing our DIC constraints is now much simpler. Specifically, for the case of D-DIC, we have that for all stages d ∈ [D], buyers i ∈ [k], histories up until stage d h [d-1] and h[d-1] i , possible true values v, misreports v for buyer i, and all possible stage d and future valuations for the remaining buyers v
Given a solution to this LP, we can implement a mechanism as follows. On the first stage the mechanism elicits reports v [1] for the first stage item, and allocates the item to buyer i with probability x 1 i (v [1] ); if the item is allocated to i, her payment is p 1 i (v [1] )/x 1 i (v [1] ), which as we've already argued is non-negative, and if the item is not allocated, the payment is zero. In the second stage reports v [2] are submitted to the mechanism, and the mechanism allocates to buyer i with probability x 2 i (v [1] ; v [2] ); if the item is allocated the payment is p 2 i (v [1] ; v [2] )/x 2 i (v [1] ; v [2] ), and so on. The probability of allocating an item is at most 1 by the feasibility constraints. Similarly, incentive compatibility is satisfied via a similar argument.
We note that we do not have variables for histories outside the support, but we can easily handle such deviations (while maintaining feasibility, truthfulness and ex-post IR) as follows. First solve the LP as is to get a mechanism M; then, at runtime, if the report of buyer i at some stage is outside the support, "pretend" that the buyer reported the lowest value in her support. Importantly, we now have a valid history as an input to the future allocation variables. Call this mechanism M ; notice that M remains truthful (deviating outside the support is the same as deviating to the lowest value in the support), and ex-post IR (if the buyer does get the item, the payment is at most the lowest value, which is a lower bound on her real value).
Given a D-DIC and ex-post IR mechanism M we now show that there is a corresponding feasible solution to our LP. In full generality, in stage d elicits reports v [d] , and depending on the history and outcomes h [d] , ω [d] i . We can then easily write variables that are a feasible solution to the above LP: x d i (h [d] : andp d i (h [d] :
It is easy to check that all the LP constraints are satisfied, and the revenue of M is exactly the value of R for the feasible solution we described.
For B-DIC we have the exact same statement:
Theorem 8. For any number of stages D, and a constant number of independent buyers k, the optimal, adaptive, randomized B-DIC mechanism can be found in time poly(D, |T | 2k+3 ).
The only difference in the LP itself is the incentive compatibility constraints. For D-DIC we had
For B-DIC, we simply take an expectation over v
, an operation that we can afford computationally (since it's a sum of O (|T | k ) terms). The proof of correctness remains virtually unchanged (noting that none of the arguments used D-DIC in a non-trivial way).
Finally, for on-path truthfulness, we only need to write incentive constraints whenever the public history matches the private history. However, we do also need to update the definition of the intermediate variable
, t) (the expected utility from stages d + 1 onward when the public history is h [d-1] , the private history is h
for buyer i and the true stage d type is t, while other buyer's reports are according to v
) to take into account the fact that an honest report in stage d + 1 might not maximize the stage utility after a lie in stage d.
Instead, we should consider every possible misreport v(d+1) i :
) .
The proof of correctness remains virtually unchanged.
In this section we focus again on the single buyer setting. So far, we have considered deterministic and randomized mechanisms. In this section we compare them in terms of the expected revenue generated, against each other and against two other benchmarks:
• the optimal non-adaptive mechanism -i.e. running an independent Myerson's mechanism on each stage; and • the optimal social welfare SW -the expected utility of the buyer from receiving both items for free.
The following is immediate: Fact 9. For any distribution of valuations, Rev (non-adaptive) ≤ Rev (deterministic) ≤ Rev (randomized) ≤ SW But are these inequalities strict for some valuation distributions? And by how much? Theorem 10. Let v * = max v∈V (1) ∪V (2) v be the maximal buyer's valuation in any stage, and assume that all valuations are integral.
Then in any two-stage mechanism, the maximum, over all mechanisms, ratio:
• between SW and any of {Rev (non-adaptive) , Rev (deterministic) , Rev (randomized)} is exactly the harmonic number of v * , H v * = v * i=1 1/i;
• between either of {Rev (deterministic) , Rev (randomized)} and Rev (non-adaptive) is at least log 1/2 v * (and at most O (log v * )); and • between Rev (randomized) and Rev (deterministic) is at least log 1/3 v * (and at most O (log v * )).
Furthermore, even when the valuations on the different stages are independent, there exists a two-stage mechanism with ratio of (log log v * ) between either of Rev (deterministic), Rev (randomized) and Rev (non-adaptive).
To compare non-adaptive mechanisms to optimal social welfare, we can assume without loss of generality that the mechanism occurs in a single stage.
Lemma 11. Let v * be the maximal buyer's valuation, and assume that all valuations are integral. For a single stage mechanism, the maximum ratio between SW and Rev (non-adaptive) is at least
Proof. Suppose that the buyer has valuation 2 with probability 1/2, 4 with probability 1/4, etc. until 2 n with probability 2 -n (and 0 also with probability 2 -n ), i.e. a truncated equal revenue distribution. The expected social welfare is SW =
For any choice of price 2 k chosen by the non-adaptive mechanism, the expected revenue is
The lemma follows by noticing that v * = 2 n .
The construction above is extremely useful in proving such lower bounds. In fact it is also used in our NP-hardness result. The distribution used is approximately the well known equal-revenue distribution. To unify our notation we refer to it as pow2 [1, n]. In general:
and v = 0 with probability 2 a-b-1 . Note in particular that the expectation is
We conclude this introductory subsection by proving a tight version of the above proposition, namely Lemma 13. Let v * be the maximal buyer's valuation, and assume that all valuations are integral. The maximum, over all single stage mechanisms, ratio between SW and Rev (non-adaptive) is exactly the harmonic number of v * .
Proof.
where Rev (p = t) denotes the expected revenue from charging t. Finally, note that the inequality can be made tight by setting Pr
In a single stage setting, the optimal randomized mechanism does not achieve more revenue than a posted price; therefore the same bound immediately holds for adaptive deterministic and randomized mechanisms.
Corollary 14. Let v * be the maximal buyer's valuation, and assume that valuations are integral. The maximum, over all single stage mechanisms, ratio between SW and any of {Rev (non-adaptive) , Rev (deterministic) , Rev (randomized)} is exactly the harmonic num- ber of v * .
[m3G; v1.314] P.18 (1-29) C. Papadimitriou, G. Pierrakos, A. Psomas et al. Games and Economic Behavior
In this paper we studied dynamic mechanisms with full commitment and limited commitment. When the seller can commit to a contract, we showed that computing the optimal deterministic mechanism for the simple two-stage case is an NP-hard problem, and identified some tractable special cases: independent stages, fixed first stage prices and constant first stage support. The optimal randomized mechanism can be computed via a linear program whose size is polynomial in the support of the type distribution, even when we consider multiple stages and multiple buyers. We also proved that when the seller cannot commit to a future contract (but has limited commitment power) we have a very different kind of obstacle to overcome: multiple communication rounds.
There are still many interesting directions to pursue. In the two-stage deterministic case, constant approximations might still be achievable in the general, NP-hard case (our current proof does not even establish APX-completeness). Also, there may be other tractable special cases. Our reduction constructs complicated second-stage distributions. For example, what if the valuation distribution is "affiliated" (higher first stage valuation implies higher second stage valuation)? Is this case tractable? And if so, can these results be extended to multiple stages and multiple buyers?
Another open question, from an algorithmic point of view, is relaxing the ex-post IR constraint. In the economics literature we have seen something similar in the work of Courty and Li (2000) where airplane tickets refunds are sold before the agents see their valuation for them, and refunds are allowed. Is the two-stage mechanism equivalently tractable in this case?
Regarding the limited commitment case, an interesting open problem is whether there exists an examples with arbitrarily many rounds of communication. Finally, can we quantify the revenue loss one occurs by restricting to a single round of communication?
[m3G; v1.314] P. 19 (1-29) C. Papadimitriou, G. Pierrakos, A. Psomas et al. Games and Economic Behavior Type
Proof. Follows from multiplying the correct combination of entries of
We first show that charging the pair (P * , Q * ) maximizes the revenue that can be obtained from type t * (Claim 20), and that (B i , C i ) yields the optimal revenue from type t i (Claim 21). Observe that even if we could charge the optimal prices from every type, our expected revenue would be (1p)Rev(t * , P * , Q * ) + p w i Rev(t i , B i , C i ), which improves over (B.1) by less than prn = /16. Intuitively, this means that any deviation that results in a loss of prn in terms of revenue, cannot compete with (B.1).
Next, we show (Claim 22) that if (i, j) ∈ E, then we cannot charge both t i and t j the optimal prices (B i , C i ) and B j , C j . In fact, we need a robust version of this statement: Specifically, for some small parameters ζ (1) ,ζ (2) i (to be defined later), we show that we cannot charge both t i and t j prices in B iζ (1)
What can we charge type t i instead? In Claim 23 we show that charging less than C i would require us to either not sell the item on the first stage, or charge type t * less than the optimal price. On the former case, we would lose pw i on the second stage. In either case the lost revenue is again greater than what we could potentially gain over (B.1). Therefore, we must charge t i more than C i on the second stage. Claim 24 shows that charging D i is the best option in this case.
Therefore an upper bound to the revenue we can make is the following: charge (B i , C i ) for all i belonging to some independent set S , and B j , D j for all other j / ∈ S . (It is easy to see than in our construction even these prices won't satisfy the IC constraints.) Now, the revenue given by these prices is:
[m3G; v1.314] P.20 (1-29)
C. Papadimitriou, G. Pierrakos, A. Psomas et al. Games and Economic Behavior
Therefore, the total expected revenue is
which is at most the expression in (B.1).
We begin by setting our padding parameters: let ζ (1) = 4 , and for each i let ζ
(2) i = 4γ 2 h i . In particular, this implies that for every i, ζ
(2) andζ (2) * = 8h * . We now have that ζ
(2)
(1) * , which we will use later in the proof. Most importantly, recall that losing 8 from the revenue from type t * , is equivalent to a loss of (1p) 8 > 16 from the total expected revenue, which immediately implies that the expected revenue is less than (B.1).
We now prove that prices (P * , Q * ) maximize the revenue from type t * , in a robust sense: Claim 20. Charging type t * prices (P * , Q * ) maximizes the revenue from that type. Furthermore, if p * < P Proof. Clearly, P * is the most that we can charge type t * on the first stage. It is left to show that Q * maximizes the revenue on the second stage.
On the second stage, we have:
Recall that F * changes on C i 's and D i 's, so those are the only candidates we should compare with Q * . For any C i , we have
Similarly, for D i ,
Similarly, we show that (B i , C i ) maximize the revenue from type t i .
Proof. Since Fi is constant for all x ≤ C i , the claim for this domain follows trivially. We will prove that Rev (2) (t i , C i ) > Rev (2) (t i , D i ) and deduce from Claim 24 that the claim continues to holds for any other x.
Below we show that if there is an edge (i, j), then we cannot charge both t i and t j close to their optimal prices:
Proof. Without loss of generality, let i < j. Assume (towards contradiction) that the conclusion is false. Then we get q j q i Fi < p ip j , which is a contradiction to the IC constraints for type t i :
[m3G; v1.314] P.21 (1-29) C. Papadimitriou, G. Pierrakos, A. Psomas et al. Games and Economic Behavior
where the third line follows by ζ (2) i h i + ζ (1) < -.
B.6. Restriction imposed by charging (P * , Q * ) for type t *
The claim below essentially shows that we cannot go around the restriction on prices for neighbors by reducing the prices:
* and q * > Q *ζ (2) * , then in any IC solution either:
• p i > B i -note that this means that type t i cannot purchase the item on the first stage; or • q i > C i -note that this substantially decreases our revenue for type t i on the second stage; or
Proof. The negation of the claim gives us two configurations: having p i ≤ B i and q i < C iζ
(2) i , and having p i < B iζ (1) and q i ≤ C i . We will show the claim is true by contradiction, i.e. both these configurations are violating.
Assume first that p i ≤ B i and
i . Consider the IC constraint comparing t * 's utility when telling the truth and when claiming that she is type t i :
where the third line follows from ζ
(2)
We now return to the other violating configuration, namely p i < B iζ (1) and q i ≤ C i . We now have
where the third line follows from ζ
(2)
We now show that D i is the optimal price on the second stage for type t i , conditioned on charging more than C i .
Claim 24. ∀y
Proof. It is easy to see that the second stage revenue is maximal for one of the "special points" where F i changes. At D i we have:
.
We now compare with each of type of special point:
• What happens if we set q i = C i+1 ?
The equation in the second line follows from the recursive definition of r i ; the last inequality follows from γ > 1 + 4 . Now, using that r i > 2γ
• What happens if we set q i = D i+1 ?
Proof. We need to show that all the following are always true:
1.
It follows from Table A.4 that the left hand sides hold. For the right hand sides, first notice that F j is always lower than Fi in the intervals we're interested in. The first inequality is tight for Fi , thus
And:
• For j we have the following:
Proof. The IC constraints between t i and t * are either
In both cases, the inequalities can be verified easily using Proof. The IC constraint between t i and t j for this pricing is:
The first term is equal to γ , and when there is no (i, i + 1) edge, the second term is equal to 1γ , thus the left hand side is immediate. The right hand side is satisfied trivially, since Fi+1 is always below Fi between C i and C i+1 and Fi gives a tight constraint.
• j > i + 1: Again, .4 we can see that the first term is always j -1i + , and the second term is 1when (i, j) / ∈ E.
For the right hand side we have
. Since F j is below Fi between C i and D i , and
Here we include a proof of Theorem 4.
Theorem 4. If the prices in the first stage are fixed, then the optimum deterministic mechanism can be approximated by an FPTAS.
This result shows us something very important about the structure of hard instances and what a possible reduction can look like: the mechanism gadgets cannot have fixed prices for one of the two stages; variation on both stages is required.
Proof. Our problem is to find optimal second stage prices, when we have committed to charging every first stage type t i , i ∈ [n], a payment of p i in the first stage. For now, assume that all types are allocated the item on the first stage (this fact will not be used in a crucial way, and an almost identical algorithm works). A first question is whether there even exist second stage prices that do not violate the IC constraints. Then, if there exist such prices, how would we optimize over them in order to maximize the seller's revenue? As it turns out, these sub-problems are easy; we can construct an FPTAS using an integer program.
It will be useful to think about the incentive constraints as follows: given first stage prices p i , p j and a second stage price q i the incentive constraints between types t i and t j give a certain interval in which q j is allowed to be. Specifically, for p i > p j , we can define a lower bound lb i, j (p i , p j , q i ) and an upper bound ub i, j (p i , p j , q i ) for q j as follows:
where q max is the maximum value in the support of V (2) . The integer program works as follows: first discretize the second stage, i.e. we only consider prices of the form k for some > 0 and k ∈ [m], where m is an integer large enough so that
• m is larger than the maximum value in the support of V (2) . We have a binary variable x k i for each type t i and price k , such that if x k i = 1 the second stage price is greater than k . Also, we have a constant a k i for the revenue of charging type t i price k (a k i is easily calculated from the input distribution). Since p i and p j are given, we simply write lb i, j (k) and ub i, j (k).
The integer program is as follows:
The first two constraints encode incentive compatibility, by guaranteeing that q j ∈ [lb ij (q i ), ub ij (q i )] for all i, j: (1) if i is charged at least k , then j is charged at least lb ij (k), (2) if j is charged at least ub ij (k), then i is charged at least k (or, equivalently, if i is charged at most k , then j is charged at most ub ij (k)). The third constraint simply encodes that x k i is non-increasing.
Observe that the constraints matrix is totally unimodular: every entry is 0, +1 or -1, and every row has at most two non-zero entries with different signs (Papadimitriou and Steiglitz, 1982). Thus the relaxation gives us an integer solution (Papadimitriou and Steiglitz, 1982). algorithm tries all of them. Therefore, our problem is reduced to finding the optimal mechanism for a given subset of losing types.
Observe that our IC constraints between winning types t i , t j reduce to: p(t i )p(t j ) = q(t j ) q(t i ) F (x)dx.
(E.1) Having a tight equality means that if we know three of p(t i ), p(t j ), q(t i ), q(t j ) , we can immediately compute the fourth. The IC constraints between a winning t i and a losing t j are: v jp(t i ) ≤ q(t i ) q(t j ) F (x)dx ≤ t ip(t i ).
(E.2)
The following observation is immediate from the IC constraints, and it will be useful in proving the rest of the structural claims:
Observation 30. Take any truthful mechanism, and change the prices only for type t i , such that the utility for type t i does not change. Then the mechanism remains truthful. Now, finding two of the three unknown prices becomes much easier thanks to the following claim: Claim 31. There exist an optimum mechanism that satisfies Claim 29, and such that for any winning type t i either: p(t i ) = v i ; or q(t i ) = 0.
Proof. Let q next be the maximum point in the support of the second stage distribution such that q next < q(t i ), if such a point exists, and 0 otherwise. Suppose that for any > 0, p(t i ) ≤ v iand q(t i ) ≥ q next + / F (q next ). Then we can increase p(t i ) by , and decrease q(t i ) by / F (q next ). First, prices remain non-negative. Second, the expected utility of type t i remains the same: the first stage utility decreases by , and the second stage expected utility increases by / F (q next ) • Pr[v (2) ≥ q(t i ) -/ F (q next )] = (where we used the fact that F (q next ) = Pr[v (2) ≥ q next ] = Pr[v (2) ≥ x], for all x ∈ [q next , q(t i )], since q(t i ) is not on the support of the second stage). Thus, truthfulness is preserved by Observation 30. Finally, the expected payment of type t i does not decrease, so expected revenue does not decrease.
Essentially the same argument also proves monotonicity for the first-stage prices.
Claim 32 (First-stage price monotonicity). There exists an optimum mechanism that satisfies Claims 29-31, and such that if t i and t j are both winning, then v i > v j =⇒ p(t i ) ≥ p(t j ).
Proof. Similar to Claim 31, if p(t i ) < p(t j ) we can increase p(t i ) and decrease q(t i ). The latter is nonzero by (E.1).
Observe that Claim 32 implies that if q(t i ) = 0 for some winning type, then for all (winning types) t j > t i , p(t j ) = p(t i ) (since we cannot offer a lower price for the second stage). Building on the price monotonicity, we can therefore use another brute-force/enumeration step to further reduce our problem to the case where we know which winning types have p(t i ) = v i and which have q(t i ) = 0. Thus, we can assume we know one of the prices for every winning type; we just need to find the other price for one of them. In the following claim we show how to solve the problem exactly using the fact that some of the second-stage prices actually lie on the support of the distribution.
Claim 33. In every optimum mechanism, at least two of the following three conditions are satisfied:
• there exists a winning type t i such that q(t i ) is on the support of the second-stage distribution (and it is nonzero);
• the second-stage price for all the losing types (observe that it is always the same for all of them), q(0), is on the support of the second-stage distribution;
• one of the constraints between a loser and a winner (E.2) is tight.
Proof. Our proof uses another gradual price increase argument. As long as neither of the first two conditions is satisfied, we can gradually increase the second-stage prices for all types simultaneously. Doing this with the right proportions maintains the IC constraints. Furthermore the revenue strictly increases: the prices increase, but as long as we don't cross any price in the support, the probabilities of selling the item to each type remain the same.
By definition, the expected revenue of M and M is the same: (part of) the payments in M simply get "pushed" to the last stage in all possible outcomes. Also, M is clearly stage-wise ex-post IR for the first D -1 stages. For the last stage, consider an outcome where buyer i gets the item (the case that buyer i doesn't get the item is identical): the buyer's utility is p i (h [d] ; ω [d-1] ; v [d] ; ω d ) + D-1 d=1 p i (h [d] ; ω [d-1] ; v [d] ; ω d ) p i (h [d] ; ω [d-1] ; v [d] ; ω d ),
where I{.} is the indicator function. Notice that the RHS is precisely the ex-post utility of i in the last stage in M, according to ω [D-1] , h [D-1] and the outcome in the last stage, and thus it is non-negative.
Finally, for incentive compatibility, we show the single buyer case, for multiple buyers and D-DIC or B-DIC, the proof is identical. Consider the expected utility of the buyer in stage d, when her true value is v, public and private histories are where the d-th terms can be taken out of the expectation since the expectation is with respect to the events after stage d. Notice that this is the IC constraint for M and is therefore satisfied.
The relaxation of an integer program arises by replacing integrality constraints, e.g. a constraint of the form x i ∈ {0, 1}, with linear constraints, e.g.x i ∈ [0, 1].
We note that this restriction makes the problem computationally easier.
For the special prices, C n+1 and D n+1 , assume that all Fi 's behave as in the "no edge" case.
For example, a natural way to encode this correlation is to have a variable for the probability of each possible (allocation,payment) outcome, which leads to exponentially many variables.