{'fraction_non_alphanumeric': 0.032645432598707266, 'fraction_numerical': 0.009438517249435402, 'mean_word_length': 4.701118806606287, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficiency with(out) intermediation in repeated bilateral trade

This paper analyzes repeated version of the bilateral trade model where the independent payoff relevant private information of the buyer and the seller is correlated across time. Using this setup it makes the following five contributions. First, it derives necessary and sufficient conditions on the primitives of the model as to when efficiency can be attained under ex post budget balance and participation constraints. Second, in doing so, it introduces an intermediate notion of budget balance called interim budget balance that allows for the extension of liquidity but with participation constraints for the issuing authority interpreted here as an intermediary. Third, it pins down the class of all possible mechanisms that can implement the efficient allocation with and without an intermediary. Fourth, it provides a foundation for the role of an intermediary in a dynamic mechanism design model under informational constraints. And, fifth, it argues for a careful interpretation of the"folk proposition"that less information is better for efficiency in dynamic mechanisms under ex post budget balance and observability of transfers.


Introduction
When can we achieve efficient trade under private information, voluntary participation and cap on external subsidies? In a seminal article Myerson and Satterthwaite [1983] showed that under plausible assumptions on preferences and distribution of information, the answer to aforementioned question is never. 1 This paper reprises the interaction of the same three institutional constraints (incentive compatibility, individual rationality and budget balance) elegantly modeled in Myerson and Satterthwaite [1983], in a dynamic context. It asks and precisely answers the question: when can efficiency be sustained in repeated bilateral trade? from the credit issuing authority.
I show that implementation under interim and ex post budget balance are equivalent in the following sense. Fix any incentive compatible and individually rational trading rule. If it can be implemented under interim budget balance, then there exists a set of transfers that ensure that it is also implementable under ex post budget balance (converse of this is trivially true). The result is surprising because interim budget balance takes expectations over the entire future sequence of transfers, whereas ex post budget balance is bereft of dynamics-it is a static, distribution free concept.
In order to establish the equivalence result, I state and prove a history dependent version of the payoff equivalence result. Consider two incentive compatible mechanism that implement the same allocation. The expected utility of the agents in both mechanisms must differ from each other through linearly additive history dependent numbers. Starting from an implementable interim budget balanced mechanism, payoff equivalence helps construct an implementable ex post budget balanced mechanism.
The third contribution is to provide an exhaustive set of mechanisms that can implement the efficient allocation under interim (and ex post) budget balance. Once the fact of efficiency has been established, there are multiple ways of distributing the efficient surplus across the buyer, seller and intermediary. The payoff equivalence result allows us to precisely capture all such bargaining protocols through a vector of history dependent weights.
I identity a particularly simple mechanism that implements efficient allocation under interim budget balance. Every period the buyer and the seller pay a Markov fee to the intermediary to avail of its services. The fees is Markov in the sense that it only depends on the agents' types from the last period. After accepting the fees, the intermediary runs the standard Vickery-Clarkes-Groves (VCG) mechanism. It is simple to understand since it employs a mixture of a fixed fee and VCG mechanism.
It relatively detail free in that it does not depend on entire history of the contract, it has a one-period memory. I also show that with constant support of valuations and production costs the mechanism is also stationary.
While the equivalence result between interim and ex post budget balance is theoretically appealing, it can also lead the reader towards an interpretation that the intermediary is irrelevant. What, if anything, could explain the desirability of intermediation in dynamic trade? In the fourth contribution of the paper, I provide one such foundation-informational constraints.
What if the agents can access signals about the other agent's current type? What if information leakage or transmission is a concern for the design of the underlying institution? To accommodate these concerns the stronger notion of ex post incentive compatibility is invoked. I first show that for interim budget balance when the efficient allocation can be implemented under standard (Bayesian) incentive compatibility, it can also be implemented under (within period) ex post incentive compatibility. However, there is no such hope under ex post budget balance. Hence, with information sharing or inability to deter information snooping amongst the agents, intermediation can strictly improve upon welfare.
It is also plausible that information about the other's past types can be hidden from the agents, and only partial signals be made available to them, say in the form of prices. In such a situation too the equivalence between interim and ex post budget balance breaks down. I show that under observability of transfers (which is a reasonable assumption in many practical scenarios) this muted flow of information makes ex post budget balance highly restrictive. On the other hand, interim budget balance allows implementation for a larger class of parameters. 3 As a fifth and final contribution, I make an observation that the folk theorem-less information is better in dynamic mechanisms-does not hold under ex post budget balance and measurability with respect to transfers. 4 If agents observe their transfers every period, then letting them see each other's reports to the mechanism designer at the end of each period does better in terms of efficiency than hiding this information.
Related Literature. The bilateral trading problem I study has a rich tradition in static mechanism design- Chatterjee and Samuelson [1983] and Myerson and Satterthwaite [1983] being two of the early papers. Chatterjee and Samuelson [1983] looked at the second-best, in the process defining the solving for the double auction game. Myerson and Satterthwaite [1983] impose all the institutional details on the model and then establish the impossibility of achieving the first-best or efficient allocation.
On the other hand, Makowski and Mezzetti [1994], Williams [1999], and Krishna and Perry [2000] fix an efficient, incentive compatible and individually rational mechanism and show that it can never satisfy budget balance, thereby again proving the same impossibility result using a different technique.
I mainly exploit a dynamic generalization of this latter approach.
This paper belongs to the rapidly developing literature on dynamic mechanism design. 5 Therein the repeated bilateral trade problem provides an able tool to think formally about dynamic incentive and feasibility constraints as approximations for real institutions. A big picture question in the literature is: What are the apt generalizations of the possibility or impossibility of efficiency results from static mechanism design?
The most well known static mechanisms that implement the efficient allocation are the Vickery-Clarkes-Groves (VCG) and d'Aspremont and Gérard-Varet (AGV) mechanisms. Bergemann and Välimäki [2010] and Athey and Segal [2013] develop their respective dynamic generalizations. Bergemann and Välimäki [2010] directly construct a dynamic version of the VCG mechanism that satisfies an efficient exit condition. They also provide an intuitive dynamic auction implementation. Their mechanism, however, does not satisfy budget balance. Athey and Segal [2013] construct the appropriate generalization of the AGV mechanism to the dynamic environment. It satisfies ex post budget balance. However, they do not allow for individual rationality in every period, thereby demanding a very strong form of commitment from the agents. When they do allow the agents to walk away, a folk theorem is established for the underlying stochastic game. This paper is the most closely related to Athey and Miller [2007] and Skrzypacz and Toikka [2015]. Athey and Miller [2007] study the repeated bilateral trading problem under iid types, ex ante and ex post budget balance, and ex post incentive compatibility. They use a bounded budget account to show approximate efficiency under ex post budget balance. Skrzypacz and Toikka [2015] analyze the same problem with persistent types and multidimensional initial information. They establish a necessary 3 There could of course be other reasons for the desirability of intermediation such as credit constraints or lack of commitment. In this paper I focus only on informational constraints, parsing our their role in making intermediation attractive. Exploring other channels are useful avenues of future research. 4 The folk theorem that less information is better is typically attributed to Myerson [1986]. 5 Some of the early papers include Courty and Li [2000], Battaglini [2005], and Eső and Szentes [2007]. See Vohra [2012], Pavan [2016], and Bergemann and Välimäki [2019] for excellent surveys. and sufficient condition for efficiency under ex ante budget balance, thereby requiring high levels of commitment from a third party willing to subsidize trade. 6 In contemporaneous work, Yoon [2015] establishes a limit possibility result under ex ante budget balance. He shows that if the agents' types follow an irreducible Markov process, there always exits a high enough discount factor that achieves efficiency.
I depart from previous work in two important ways. First, I demand efficiency under interim and ex post budget balance, while maintaining individual rationality for both agents in each period. This creates a repeated Myerson and Satterthwaite like situation where the three constraints interact every period. Therefore, dynamics is the primary driver of possibility results. Second, I do not just look for limit results. I characterize the entire set of parameters for which efficiency can be sustained.
I also establish a dynamic generalization of the payoff equivalence result. Previous work has stated and proven ex ante versions of the payoff equivalence result for dynamic models, see for example Pavan, Segal, and Toikka [2014]. 7 These results establish that any two incentive compatible mechanisms implementing the same allocation differ in the ex ante net present value of transfers to an agent through a constant. But what can we say about the equivalence of payoffs at other points of history? I prove that the payoffs for any two mechanisms implementing the same allocation are connected by history dependent constants in each period of the dynamic mechanism. This result is used for proving the equivalence of implementation under interim and ex post budget balance, and to characterize the class of all incentive compatible and individually rational mechanisms that implement the efficient allocation.
None of the aforementioned papers provide a intuitively plausible implementation rule of the efficient allocation under budget balance. And, neither do they capture the magnitude of transfers as a function of the parameters. This paper provides a very simple mechanism of implementing the efficient mechanism with the help of an intermediary. Moreover, using the two types model, it also provides a sense of the magnitude of transfers made each period.
Finally, there is a rich literature in financial economics on the desirability of intermediation. Allen and Santomero [2001], and Gorton and Winton [2003] are some references. To the best of my knowledge, there has been no theoretical attempt at understanding how intermediation can actually increase welfare while ensuring participatory rents for the intermediary through a long-term contract. In an admittedly stylized setup, this paper shows how the presence of an intermediary can increase the efficiency of trade under informational constraints.

Model
Two agents, each with private information, agree to be in a dynamic bilateral trading relationship for a non-durable good. The buyer (B) has a hidden valuation for the good and the seller (S) is endowed with a technology to produce the good each period at a hidden cost. I assume that the buyer's valuation and the seller's cost are random variables denoted by and . 8 They are distributed according to priors 6 Using the balancing trick of Athey and Segal [2013], this condition also guarantees implementation under ex post budget balance, but then like Athey and Segal, individual rationality has to be relaxed beyond the first period.
7 The payoff equivalence result is proven by what has come to be known as the dynamic envelope formula. See also Battaglini and Lamba [2019] and Eső and Szentes [2017].
8 These shall interchangeably be referred to as their types. satisfy first order stochastic dominance. 9 The densities have full support and are denoted by , , (.|.) and (.|.), respectively. Further, V ∩ C = ∅, +1 > , +1 > , and denote Δ +1 = +1 − , Δ +1 = +1 − . For an intuitive exposition, I will often write = 1 and = . 10 Each period determines the probability of trade, that is, the production and allocation of the good from the seller to the buyer. , denotes the transfer from the buyer to the mechanism designer, and , the transfer to the seller from the mechanism designer. The per period payoffs are given by − , and , − for the buyer and seller respectively. 11 The (contractual) relationship lasts for discrete periods, where ≤ ∞. Both the agents discount future payoffs with a common discount factor . Myerson and Satterthwaite [1983], and Chatterjee and Samuelson [1983] studied the static version of this model, = 0, with continuous type spaces.
In addition to being a mediator who receives reports and recommends actions in the classical Myersonian sense, the mechanism designer here can be considered as a financial intermediary, an institution as part of a larger social contract facilitating trade, or a simple transfer scheme in case = . I will refer to this economic agent interchangeably as the mediator, mechanism designer or intermediary. 12 Taking the institutional details as given, both the buyer and seller can commit to the mechanism.
Participation constraints every period temper the role commitment will play in the model, as we elaborate below. Both agents know their first period valuation and cost respectively when the contract is signed, and these then stochastically evolve over time. All the parametric and institutional details enunciated thus far are common knowledge between the buyer and seller.
In the spirit of much of the literature, I look at dynamic (history-dependent) direct mechanisms.
Every period the agents learn their own types, and then send a report to the mechanism designer, who in turn specifies the allocation (that is, the probability of trade) and transfer rules. Unlike the static model, the amount of information revealed by the mechanism to the agents matters for future incentives (see Myerson [1986]). I will focus on the public mechanism where one agent's report is observed by the other at the end of each period. 13 Formally, a direct (public) mechanism, say , is a collection of history dependent probability and transfer vectors: , where ℎ −1 and ( , ) are, respectively, the history of reports up to − 1 and current report at time . These can also be succinctly written as (ℎ ), etc. In general, ℎ is defined recursively as ℎ = ℎ −1 , ( , ) , with 9 Mathematically speaking ( | ) is weakly decreasing in and ( | ) is weakly increasing in . 10 I choose the discrete type model for three reasons. First, it elucidates the key economic forces without having to keep track of measure theoretic details. Second, it allows us to do comparative statics for simple examples, specifically when both agents have two possible types. And, finally many applications of dynamic mechanism design use numerical methods which require a discrete state space. All results naturally converge to their appropriate continuous types counterparts, see Lamba [2014].
11 The subscript will not be used when the set of histories make the time dimension obvious. 12 Myerson [1986] would refer to the mediator as a fictitious agent separate from the intermediary. 13 In Section 7.2 I shall introduce and explore the the implications of what I call the intermediate mechanism; intermediate because it reveals the hard information of allocations and individual transfers, but hides the soft information of reports and transfers of the other agent. Each agent only observes whether or not trade happens, and transfers are measurable with respect to this information structure. The extreme case would be the opaque mechanism where the buyer gets zero information about the seller's reports, and vice-versa. This would of course entail the agents not being able to see allocations or transfers, making it a bit unrealistic for most practical applications. ℎ 0 = ∅. I will often write ℎ = ( , ), where and are the history of reports by the buyer and seller respectively. The set of possible histories at time is denoted by (for simplicity = ).
The strategies of the buyer and the seller depend on their private histories. For the buyer, the information available before his period report is given by ℎ = ℎ −1 ,ˆ , starting with ℎ 1 = {ˆ1}, whereˆ= (ˆ1, ...,ˆ) is the vector of true (actual) types of the buyer. The seller's information is defined analogously. Let the set of these private histories at time be denoted by and , respectively.
Thus, fixing the set of parameters: Γ = V × C, , (.|.), , (.|.), , for any given mechanism, we have a dynamic game described by Γ in which the strategy for the buyer, , =1 , is then simply a function that maps private history into an announcement every period, , : ↦ → V, and similarly for the seller, , : ↦ → C.

The institutional framework
The edifice of the institutional machinery has three key foundations: private information, voluntary participation and limits on external subisdy. In the mechanism design lexicon, these would respectively be associated with incentive compatibility, individual rationality and budget balance constraints.
For a fixed mechanism , and strategies = ( , ), the expected utilities on the induced allocation and transfers, after each possible history are defined as follows. and, Let = * be the expected utility vector under the truth-telling strategy * . At time , under truth-telling, I will write ( , |ℎ −1 ) and ( , |ℎ −1 ) to denote within period ex post expected utility of the buyer and seller respectively.

A change of variables
Much in the spirit of static contract theory 14 , I propose a change of variables in the structure of the mechanism from p, x to p, U . As I will later show, this transformation will be central in my endeavor to establish a tight characterization of efficiency.
In order to keep notation simple the type/variable over which expectation is taken is removed. For where −1 is the − 1 period announcement of the seller, known to the buyer. 15 14 See for example Stole [2001].

15
, and , refer to type for the buyer and type for the seller in period .
Expected utility of the buyer can be recursively defined as Utility of the buyer of type from misreporting (once) to be type , for a fixed type of the seller, can be succinctly written as ( |ℎ −1 ) and ( ; |ℎ −1 ) are defined by taking expectation over , given −1 . 16 The seller's utility, , can be similarly defined.
It is straightforward to note that a mechanism = p, x , which is a collection of history dependent allocation and transfer vectors, can be equivalently defined to be = p, U , where (fixing the allocation) the duality between transfers and expected utility vectors is completely described by equation (3).

Incentive compatibility
Exploiting the one-shot deviation principle, incentive compatibility can be defined as follows.
It states that along all truthful histories, buyer and the seller have no incentive to misreport their type. In order to define a perfect Bayesian equilibrium in the underlying dynamic game associated with this dynamic mechanism design problem, we assume that both agents believe that the other agent reports truthfully with probability one. 17 Since agents never observe the other agent's actual type, these beliefs under the above definition of incentive compatibility define a perfect Bayesian equilibrium in the dynamic game. 18 17 Note that the full support assumption of the Markov processes governing evolution of types for the buyer and seller plays a key role here. Suppose the seller has two possible types { , }, and type is an absorbing state. Then, if a type misreports to be type , the beliefs which put probability one on truthtelling are no longer consistent, and one-shot deviation property can no longer be applied. Following this report, it is confirmed that the seller would always be type .

Individual rationality
Even though commitment is assumed as part of our institutional architecture, the agents are allowed to walk away after learning their type after any history if their utility from continuing in the contract falls below their reservation thresholds, which are normalized to zero.
Definition 2. A mechanism = p, U satisfies individually rationality if A mechanism is termed implementable if it is incentive compatible and individually rational.

Budget balance
In mechanism design budget balance is seen as the limits on insurance or external subsidies available to the agents. In addition to the traditional notions of ex ante and ex post budget balance, we introduce an intermediate notion of interim budget balance.
A mechanism is interim budget balanced if The mechanism is ex ante budget balanced if interim budget balance holds for the null history. Moreover, the mechanism is ex post budget balanced if the entire vector of transfers are are point-wise equal at every history, = .
Using equations (1) and (2) we can write the expected budget surplus that a mechanism, , generates after any history ℎ −1 to be The ex ante budget surplus is denoted simply by Π = Π(ℎ 0 ).

Definition 3. A mechanism p, U satisfies interim budget balance if
This can be motivated in many ways. First, it can be viewed as a participation constraint for the mechanism designer-after any history, just like the two agents, the mechanism designer must have an incentive to continue in the relationship. Second, it is a bankruptcy constraint for the intermediary. If the contract reaches a stage the where the intermediary expects to loose money, it should be allowed to shut shop.
Definition 4. A mechanism p, U satisfies ex ante budget balance if This is the weakest possible notion of budget balance for this dynamic model. It means that the mechanism designer does not loose money in an expected ex ante sense. Importantly, it demands a very strong form of commitment from the intermediary.
Finally, the most standard (and strictest) definition of budget balance from the static literature that can be generalized to dynamic environments states the transfers should exactly equal across all histories for all time periods.
Definition 5. A mechanism = p, x satisfies ex post budget balance if A natural way to motivate this in the dynamic model is the absence of an outside insurance provider or financial intermediary. Both the agents insure each other against bad shocks, and premium paid can be recovered through continuation utility.
It is fairly easy to see a hierarchy amongst the three notions of budget balance: ex post budget balance ⇒ interim budget balance ⇒ ex ante budget balance

Objective
One of the most widely accepted objectives of mechanism design is that of efficiency. 19 We shall invoke the strongest possible version in its ex post form.
Definition 6. A mechanism = p, U satisfies efficiency if Trade happens with certainty under a positive instantaneous surplus, and does not happen otherwise. It is a direct generalization of the notion typically used in static models.

The interaction of constraints
Before we jump into the results, it worthwhile to investigate the coexistence of the various forces laid out in this section. From static mechanism design we know that it is the simultaneous interaction of private information (and hence incentive compatibility) with participation (hence individual rationality) and budget balance that leads to the impossibility of efficiency result of Myerson and Satterthwaite [1983].
If we wished to implement the efficient allocation under only individual rationality, the well known Vickery-Clarkes-Groves (VCG) mechanism does so. On the other hand, if we wished to implement the efficient allocation under only budget balance, the d'Aspremont and Gérard-Varet (AGV) mechanism 19 See Holmström and  for the various notions of efficiency.

Incentive Compatibility
Individual Rationality

Budget Balance
Objective: Efficiency Given incentive compatibility, efficient allocation is implementable under individual rationality (VCG) or budget balance (AGV) but not both (MS impossibility result) VCG AVG Figure 1: Interaction of constraints in static mechanism design does so. The three forces all together lead to a departure from efficiency. Figure 1 elucidates the three scenarios.
In order to understand how dynamics can overcome the impossibility results, we must model the simultaneous interactions of these forces every period. This cannot be captured under ex-ante budget balance, nor when individual rationality constraint is imposed only in the first period. In this paper I look at ex post and interim budget balance along with repeated individual rationality, which creates a Myerson and Satterthwaite like situation in every period. Herein, dynamics are the primary drivers of possibility results.

Characterization of ex post budget balance
A standard result in static mechanism design with quasi-linear preferences states that if there exists a mechanism that implements an allocation under ex ante budget balance, then there also exists a mechanism that implements the same allocation under ex post budget balance. 20 The intuition for this result is simple. Aggregate payment is equal to total surplus minus information rents. Ex ante budget balance ensures that the value of the underlying economic relationship is large enough to provide information rents to all types (of all agents). Given such a mechanism, we can redistribute the surplus in a way that payments add up to zero ex post. This is because there are enough resources to compensate for the difference between realized and expected payments by cross subsidizing across types.
Is there an equivalent result in mechanism design for dynamic models? The answer is yes, and I characterize this result for repeated bilateral trade. The key conceptual innovation to this end is the idea of interim budget balance.
Proposition 1. There exists an implementable mechanism p, x (or p, U ) that satisfies ex post budget balance if and only if there exists another implementable mechanism p,x or p,Û that satisfies interim budget balance.
20 See Börgers and Norman [2009]. Also, note that the converse of this result is obvious.
The proof for the static result is constructive, and the proof for Proposition 1 is no different.
However, the main challenge is in preserving incentive compatibility as we translate an interim budget balanced mechanism to satisfy ex post budget balance. I start with a mechanism that is incentive compatible and individually rational and calibrate it to to satisfy ex post budget balance while preserving the first two properties. Athey and Segal [2007], on the other hand, start with a mechanism that is incentive compatible and (ex post) budget balanced, and calibrate it to satisfy individual rationality; however, as described above, they run into the problem of preserving incentives while moving transfers and produce only a partial characterization. Commenting on this, they write: The only degree of freedom the transfers offer in transferring utility across players is a fixed constant K (if it varied with history, it would affect incentives). Thus, we look for a K that allows IR to be satisfied in the worst-case scenario for the buyer, and separately in the worst-case scenario for the seller.
The problem emanates from the interlinking of incentives. If we change transfers in period it affects incentives in period − and + . I get around this problem by operating in the p, U rather than p, x space. The following lemma characterizes the class of incentive compatible mechanisms allowing us to sidestep the problem stated by Athey and Segal [2007].
Lemma 1 should be seen as a dynamic generalization of the standard payoff equivalence result in mechanism design. It states that starting with an incentive compatible contract, we can construct another incentive compatible contract that implements the same allocation by linearly translating the expected utility vectors after every history. It is important to note that is independent of and is independent of . 21 It may not be obvious at the outset why adding history dependent constants in this fashion keeps the mechanism incentive compatible. In the appendix we show that the proof is fairly straightforward. Now, given Lemma 1, the proof of Proposition 1 is carried out in two steps. First, define the instantaneous expected budget surplus to be the following.
In terms of p, x representation of the mechanism, For the continuous types model, we can include the converse of Lemma 1. See Lamba [2014].
Starting with an implementable mechanism p, U that is interim budget balanced, choose a new mechanism with constants in Lemma 1 to be (ℎ −1 ) = Π(ℎ −1 ) and (ℎ −1 ) = (1− )Π(ℎ −1 ) for any It is easy to see that in this new mechanism, say p,Ũ , we haveΠ( As the second and final step,Π (ℎ −1 ) = 0 gives us a mechanism that satisfies "ex ante budget balance in the static sense" for every history. Thus using the standard static mechanism design tools, we can create a third mechanism p,Û (or p,x ) that satisfies ex post budget balance.

Efficiency: a full characterization
Now, we ask the main theoretical question: when can efficiency be sustained under ex post and interim budget balance while satisfying incentive compatibility and individual rationality? To this end, I generalize the techniques from static mechanism design developed in Makowski and Mezzetti [1994], Williams [1999], and Krishna and Perry [2000] to the dynamic model. Start with a repetition of the static VCG mechanism, adjusted for the discreteness of the type space: A standard VCG mechanism would make the buyer pay his externality on the seller, that is the seller's cost, and the make the seller pay her externality on the buyer, that is the buyer's valuation: This mechanism is also incentive compatible. However, for discrete types, gaps between in the type space ensure that it is not the tightest possible mechanism.
The mechanism we choose adjusts for gaps and local incentive constraints bind. 22 It converges to the original VCG mechanism as the model converges to continuous types. Call this mechanism p vcg , x vcg or p vcg , U vcg , where given transfers, the expected utility vectors are defined uniquely by equation (3).
This mechanism satisfies incentive compatibility and individual rationality, but may violate all notions of budget balance. Trade happens when > , and payments flowing to the mechanism designer then may be negative. The challenge thus is to construct a new mechanism that satisfies budget balance whenever the primitives of the model allow us to do so without disturbing incentive compatibility and individual rationality.
I take a leaf from Krishna and Perry [2000]'s book, and construct the unique incentive compatible mechanism that binds the individual rationality constraint of the "lowest" type in each period. If the mechanism thus constructed produces an expected budget surplus after every history, we are done, and only if this mechanism produces an expected budget surplus are we done. I call it the min-max dynamic VCG mechanism: starting from a VCG mechanism, while preserving incentive compatibility 22 See Kos and Manea [2009] for such a modified VCG mechanism in the static model with discrete types. and individual rationality, it produces the minimal possible utility for the agents, and the maximal possible payments to the mechanism designer after every history.

Constructing the Min-Max Dynamic VGC mechanism
Step 1. Start with the dynamic VCG mechanism, p vcg , U vcg . Note that the mechanism is incentive compatible and individually rational; and moreover it is tight: local incentive compatibility constraints hold as equalities.
According to Lemma 1, the construction entails a choice of constants: . Corresponding ex post expected utility vectors: for all , and ℎ −1 complete the description of the mechanism.
Step 3. Show that an incentive compatible and individually rational mechanism guaranteeing efficient trade under interim budget balance can exist if and only if p * , U * runs an expected budget surplus, that is, Π * (ℎ −1 ) ≥ 0 ∀ℎ −1 , ∀ .
The following result characterizes efficiency in terms of the primitives of the model. Note that the condition constitutes a set of inequality constraints for the entire set of histories.
Since this a necessary and sufficient condition, in principal, there is no hope for simplification. Though two features of the min-max dynamic VCG mechanism make the inequalities easy to digest. First, the within-period ex post expected utility vectors, ( , |ℎ −1 ), ( , |ℎ −1 ) are independent of history, ℎ −1 . Thus, the min-max dynamic VCG mechanism defined by equations (5) and (6) is also independent of history. Second, interim expected utility depends on history only through expectations.
Starting from period 2, conditioning on the type of the other agent in the previous period is the history dependence required, which makes interim expected utility Markov. Moreover, given constant support, it is also stationary. Thus, by construction interim transfers are completely defined by the vector * ( ), * ( ), * ( | ), * ( | ) ∀ ( , ) ∈ V × C Consequently, in order to check for the possibility of efficiency, we need to evaluate × +1 constraints: Π * ≥ 0 and Π * ( , ) ≥ 0 for all ∈ V and ∈ C. 23 To explore the formulation of the Π * -vector in terms of the primitives of the environment, define Π and Π ( , ) respectively to be the ex ante budget surplus and expected budget surplus after history ( , ) for the dynamic VCG mechanism: Given first-order stochastic dominance, the infimum of expected utility vectors invoked in equations (5) and (6) is attained at the numerically lowest value for the buyer and the numerically highest for the seller. Thus, it is easy to see that and, for all ( , ) ∈ V × C Equations (8) and (9) characterize the budget surplus generated in the minimal dynamic VCG mechanism after every history. In particular, equation (8)  The min-max dynamic VCG mechanism delivers two things: first it precisely characterizes efficiency in this dynamic mechanism design problem, and second it provides a working method of implementing efficiency. I will expound more on the latter point in section 6.
23 See Section 9.9 in the appendix, and Figures 2 and 3 in Section 5.1 for a fully worked out example where both the buyer and trader have two possible types.
24 In the iid model, ex ante and interim budget balance put the exact same restrictions on the set of implementable allocations. Athey and Miller [2007] establish that in a continuous type space iid model with V = C, efficiency can always be sustained for all ≥ 1 2 . The same result holds in the continuous types limit of this model.

Comparative statics
The necessary and sufficient condition in Theorem 1 in terms of the Π * -vector is a joint restriction on the overlap of support, discounting and stochastic process governing the types. Since Myerson and Satterthwaite [1983] we know that in the continuous types model, impossibility of efficiency result holds given any overlap of support. Moreover, the distance from efficiency (measured by the extent of external subsidy required to restore full efficiency) is a decreasing function of the measure of types for which > . The same intuition carries over to the dynamic model as well. In this subsection we explore the interaction between persistence of types and level of discounting, and its impact on efficiency.
Note that Γ = {V, C, , , (.|.), (.|.), } defines the set of primitives of the model. Intuitively speaking, a high is better for efficiency, and highly persistent Markov processes of types is bad for efficiency. In a dynamic mechanism with commitment, the iid model has the least informational frictions, whereas the fully persistent (or constant types) case kills any advantages that dynamics may offer. In the next two corollaries we show that for the intermediate case, the possibility of efficiency relies of relative sizes of discounting and persistence.
Corollary 2. For any Γ \ { }, there exists a * such that for all > * , the efficient allocation is implementable under interim (or ex post) budget balance.
Corollary 2 generalizes the possibility of efficiency result under ex ante budget balance in (contemporaneous work in) Yoon [2015]. It is also the mechanism design counterpart to the decentralized game studied by Athey and Segal [2013]. The key take away from this result is that with a compact support, even for arbitrarily high levels of persistence of types, we can always find a discount factor high enough that attains efficiency. Conversely, what about a fixed discount factor and arbitrarily high levels of persistence of types?
To answer this question we need to embed the notion of persistence in some parametrization.
Note that and are just indexes and the set Λ imposes fairly minimal restriction on the class of stochastic process. For example, different types could converge to one at differing rates. 25 Using this machinery, the following corollary states that even for an arbitrarily high discount factor, we can find a Markov process close enough to the identity matrix so that efficiency cannot be sustained. The two corollaries together formalize perhaps a folk wisdom that holding the (compact) supports fixed, the possibility of efficiency depends on the order of limits between discounting and persistence.  To further simplify the parameter space, inspired by Myerson [1985], that is * = * , and Π * ( , ) = Π * ( , ). The latter implies that we need to check four inequality constraints for efficiency. Figure 2 plots each of the Π * -vector for the USSTP as a function of persistence, , for three 26 Any other arrangement of the two types model will render posted prices efficient in the static model and hence in the repeated model. This was first noted by Matsuo [1989]. 27 Note that for the STP, the VCG mechanism (modified for the discrete type space) is given by: Throughout it is assumed that Π * (ℎ −1 ) ≥ 0 ∀ℎ −1 , ∀ , or more succinctly, Π * ≥ 0 and Π * ( , ) ≥ 0 for all ∈ V and ∈ C.

Under interim budget balance
As pointed out before, the ex post utility vectors in the dynamic min-max VCG mechanism, defined by Equations (5) and (6), are forward looking and independent of history. Thus, the ex post transfers in the associated mechanism p * , x * are also history independent, lending a rather simple structure to the direct mechanism.
29 Equation (9) tells us that Π * ( , ) is composed of the budget deficit due the VCG mechanism plus the surplus meted out to the lowest possible type in the VCG mechanism. Now, it can be checked that for the USSTP Π ( , > ( | ) and ( | ) > ( | ). Therefore, even though more surplus is extracted from the agents when the type realization is ( , ) the larger budget deficit of the original VCG mechanism cannot be compensated for enough culminating in the lowest value of in the Π * -vector.
In this subsection I show, in addition, the min-max dynamic VCG mechanism provides another simple, and perhaps importantly also an exhaustive method of implementing the efficient allocation under interim budget balance. First, I describe the mechanical steps of implementation, and then later expand on its simplicity and exhaustiveness.

Implementing the Min-Max Dynamic VGC mechanism
Step 1. At the start of period , the buyer and seller pay a fixed fee: , ( −1 ) and , ( −1 ). From the second period onwards this fee only depends on the type of the other agent in the previous period. Thus, the fee structure is completely described by: ,1 , ,1 , and ( ), ( ) ∀( , ) ∈ V × C.
Step 2. After the fixed fee is paid, the mechanism designer runs a simple static VCG mechanism as defined above: p vcg , x vcg . This (stationary) mechanism is repeated every period.
Step 3. Comparing U vcg and U * , by construction the fixed fees are defined by: The mechanism is quite simple: it is Markov in that transfers only depend on the current reports and report of the other agent in the previous period, and it is stationary. It is intuitive in that every period it requires a small participation fees and then runs a VCG mechanism.
The magnitude of the fixed payments with respect to other parameters of the problem are delineated for the uniform symmetric simple trading problem in Table 1. Fixed fee payments have a reasonable magnitude: the never exceed one-fourth of the highest type. Moreover, transfers decrease with the level of persistence. An increase in persistence decreases the amount of total economic surplus, and since the expected utility of the buyer and seller are already at their lowest possible value, this implies a decrease in the share of the pie for the mechanism designer, and hence a reduction in fixed fee payments.
How is the construction exhaustive in implementability? Consider the class of all possible tight mechanisms that implement the efficient allocation, that is all mechanisms where local incentive con- straints hold as equalities. 30 These mechanisms are the "right" mechanisms to consider in the discrete types framework: they are a natural dynamic analog of the static discrete model, and in the limit of the dynamic continuous type space model they cover all possible incentive compatible mechanisms since local incentive constraints always "bind" owing to the envelope theorem (see Pavan, Segal, and Toikka [2014]).
The min-max dynamic VCG mechanism is one such tight mechanism that is uniquely defined by the fact that it transfers all possible expected surplus at every history to the mechanism designer. All other mechanisms are linear translations of this mechanism. A full characterization follows.
Note that (ℎ −1 ), (ℎ −1 ), and 1 − (ℎ −1 ) − (ℎ −1 ) are the fractions of surplus Π * (ℎ −1 ) shared by the buyer, seller and the mechanism designer after history ℎ −1 . Just as before this new mechanism can be implemented using a fixed fee and VCG mashup. And, if we choose and to be Markov and stationary, the new mechanism will also adopt the Markov and stationary properties of the original min-max dynamic VCG mechanism. 31 All possible (history dependent) bargaining protocols that can implement the efficient allocation under interim budget balance are captured by the vector = (ℎ −1 ), (ℎ −1 ) . Once the fact of efficiency is established by the min-max dynamic VCG mechanism, this vector lists all possible divisions of the economic surplus that can emerge in equilibrium.
This a good place to contrast my mechanism from the bond mechanisms typically adopted in the literature (see Skrzypacz and Toikka [2015] and Yoon [2015]) in which the agents are asked to pay an upfront fees ensuring ex ante (but not interim or ex post) budget balance. In Table 2 (for the uniform symmetric simple trading problem), the maximum fixed fee payment across all possible histories in the min-max dynamic VCG mechanism is normalized to 1. The upfront payment is always 1400% more than the fixed fee payment. The bond mechanism, while plausible in certain contexts, may not work unless the agents have very deep pockets; small credit constraints will render it infeasible.
30 A formal description is provided in Section 9.1 in the appendix. 31 For the min-max dynamic VCG mechanism = = 0.

Under ex post budget balance
Unlike the case with an active mechanism designer (or intermediary), implementation under ex post budget balance does not allow differential payments to be made by the buyer and to the seller. Restriction to "direct transfers" shrinks the family of incentive compatible sharing rules of the future economic surplus, but as established in Proposition 1, it does not change the fact of efficiency.
The direct mechanism for implementation under ex post budget balance has a clear intuitive formulation. Starting from the dynamic min-max VCG mechanism, let p * , U o be the mechanism that generates exactly zero expected budget surplus after every history and distributes any extra economic surplus to both agents equally; that is ∀ ℎ −1 : The new mechanism is of course Markov and stationary starting period 2. Importantly, it generates a zero static expected budget surplus after any history: The direct mechanism implementing the efficient allocation is then completely characterized by the following payments:  Table 3 reports payments in the mechanism p * , x † for two possible histories. † ( , | , ) represents the transfer for the most favorable realization of types in terms of trade, and † ( , | , ) the least favorable. It is clear that while the former involves payments from the buyer to the seller, in the latter it is in fact the seller that compensates the buyer for the realization of bad types. The flow of funds in both directions captures the role of agents as liquidity providers in the absence of an    (12) and (13).
Before we end the implementation section, a comment on posted prices and double auctions is in order. When implementing under ex post budget balance, these two mechanisms from the static world immediately come to mind. Posted price mechanisms are robust to informational assumptions but demanding in terms of the underlying equilibrium notion. 32 No posted price mechanism can sustain the efficient allocation in a dynamic set up that takes expectations over future utility. Implementing through a double auction seems more hopeful. Though a repetition of a standard static double auction will constraint the mechanism to a form of limited liability, and hence won't sustain efficiency. A mechanism with a fixed payment every period followed by a Markovian double auction seems plausible.
This is an interesting question for future work.
32 A posted price mechanism is the one where a price is exogenously generated either deterministically or in a random fashion, and the buyer and seller simultaneously decide whether to trade at that price. Hagerty and Rogerson [1987] show that in the static bilateral trade problem the only mechanism that satisfies dominant strategy incentive compatibility and ex post individual rationality is the posted price mechanism.

Information in dynamic mechanisms
The equivalence between implementation under interim and ex post budget balance can leave one in a dilemma about the structure of our model. While the former takes expectations over the entire future sequence of transfers, the latter involves no expectation, is independent of future transfers and does not allow for any "leakages" whatsoever. In fact, the total expected utility of the two agents in the model with ex post budget balance in weakly greater than that under interim budget balance, since no part of the economic surplus has to be paid to a third party. A intuitive economic meaning of this equivalence is in making irrelevant the desirability of an intermediary. How and when must the intermediary become salient to the production of the efficient economic surplus in this repeated bilateral trade setting?
The role of an intermediary can become salient if reports to her (or prices in an indirect mechanism) either need to be transparent or can be hidden. I expand on both cases.

Robustness to information
What if the agents observe reports by the other and before revealing their type or taking a decision to walk away. The incentive and individual rationality constraints must then incorporate a robustness to the current type of the other agent. Athey and Miller [2007] motivate it in the following manner: ".. if a player were able to delay his announcement or spy on the other player's information, he might be tempted to make an untruthful announcement once learning about the other player's type." When issues of information leakage or transparency are a concern it may be better to focus on an equilibrium concept where "truthful announcement is incentive compatible regardless of any information he may learn that is not relevant to his own payoff." Hence follows (with-in period) ex post incentive compatibility.
Ex post individual rationality can be analogously defined. Athey and Miller [2007] and Miller [2012] show that efficiency cannot be implemented under ex post budget balance under the stronger notions of ex post incentive compatibility and individual rationality for iid types; it is easy to see that there is therefore no hope for Markovian private information.
In Section 9.2 in the appendix, I show that an analogue of Lemma 1, the history dependent payoff Therefore, with the help of an intermediary one can ensure robustness to information in the sense just described, which is impossible under ex post budget balance.

Hiding information?
What if on the other hand the intermediary can hide information from the agents? Would it help from the perspective of efficiency? Myerson [1986] established that maximal information to the mediator and minimal information to the agents produces the most permissible results. This subsection, considers implementation under interim and ex post budget balance for a mechanism that hides information from the agents.
I will exposit the key ideas through what I call the intermediate mechanism. Every period the agents only learn about the other agent's reported type through the realized allocation, that is whether trade happens. Thus, in the event of a trade the buyer only learns that the seller's reported type was less than his, and seller that the buyer's reported type was more than her type. No trade gives the opposite information. Importantly, transfers are observable and must be measurable with respect to this information. is the observed efficient trading rule. Note that for the mechanism designer observes the history of all reports: ℎ = ( , ). Moreover, along the truthful history we succinctly define the information partition of the agents as: and ℎ +1 = ℎ , +1 , * +1 , [ +1 ] * +1 starting at ℎ 1 = 1 , * 1 , [ 1 ] * 1 and ℎ 1 = 1 , * 1 , [ 1 ] * 1 . The partition of public histories into private history equivalence classes is defined as The min-max dynamic VCG intermediate mechanism defines the expected utility of the agents at public history ℎ to be * * (ℎ ) = E * (h ) |h ∈ ℎ and * * (ℎ ) = E * (h ) |h ∈ ℎ where I use the short hand * (ℎ ) = * ( , |ℎ − ) for = , . As a final step, the expected budget surplus generated by the mechanism is given by Then, we have the characterization of efficiency for the intermediate mechanism.

Carefully interpreting a folk proposition
The above observation is of course limited to the intermediate mechanism.
As we allow more permissibility in the measurability restriction, more prices can be employed to sustain trade, however, the most "price discrimination" is achieved in the public mechanism. In fact the public mechanism allows discriminatory prices on the basis of past and current types, resulting in the greatest possibility of efficiency (as long as transfers are observable). While a deeper analysis of dynamic mechanism design with a parametrization of how much information is shared amongst agents is beyond the scope here, we can still point towards a more careful interpretation of the observation made in Myerson [1986] that less information sharing is better in terms of allocative efficiency in dynamic models of mechanism design. To be sure, there is no error here, Myerson is absolutely correct in pointing out that less information sharing reduces information rents by pooling incentive constraints, however, measurability restrictions imposed by observability of transfers in ex post budget balance is not explicitly considered in that framework.
It is useful to note that if we are only interested in ex ante budget balance, then there is not difference between the intermediate or public mechanism in terms of when efficiency can be sustained.
It is straightforward to see that first period expected budget surplus are the same in both mechanisms: Π * = Π * * ; however the same is not true about Π * ( , ) and Π * * ( , ). In fact there is no obvious way to rank the vector. For example, for the (STP): Using these facts, I make three economically meaningful observations. First, with observability of transfers the most permissive results under ex post budget balance are obtained for the public mechanism. Second, in the event that prices do not communicate all possible underlying information, it is welfare improving to have an intermediary (interim budget balance does better than ex post budget balance). Third, even if the intermediary has the ability to hide information, it may choose not to; its decision will depend on how it evaluates the vectors Π * and Π * * .

Conclusion
I studied the repeated bilateral trade problem and the viability of various institutional rules to sustain efficient trade. In particular I introduced a novel notion of budget balance that allows for an intermediary to broker trade in a self enforcing manner. In the conclusion I briefly explore some questions for future work.
This paper is concerned with implementing the first-best outcome. It would be interesting to look at the second best when the first-best cannot be implemented, for example the allocation rule that maximizes the gains from trade. With general Markovian types, we would run into the problem of binding global incentive constraints (see Battaglini and Lamba [2019]). Solving the AR(1) or two types model should be promising. Relatedly, figuring out the optimal dynamic double auction as a pricing implementation of the second-best allocation rule would be important (see Antill and Duffie [2021] for a related model of dynamic double auction with applications to financial markets).
Understanding how the set implementable allocations change under various institutional arrangements as the level of information flow between agents is made more or less Blackwell informative is an interesting question to pursue in future work. Even when the direction is obvious: less information expands the feasible set, the exact nature or rate of expansion may not be obvious. We observed that the direction of results would also change when ex post budget balance and observability is required.
Interim budget balance does not allow the mechanism designer to draw from past surplus. It can be viewed as a constraint on the intermediary's commitment power. While this would a reasonable assumption in many contexts and an interesting benchmark in it own right, it is also important to note that the family of constraints defining interim budget balance can be generalized to a class where the mechanism designer is allowed to save. This is a potentially important area with connections to the macro-finance literature.
Finally, we assumed here that the agents have deep pockets. It is plausible to think of situations where the agents are cash constrained. There is limited understanding in dynamic mechanism design on the nature of optimal or even feasible allocations under limited liability restrictions (see Chassang and Kapon [2021] and Krasikov and Lamba [2021] for some recent work). This is also an interesting direction for future work.

Tight mechanisms
Since we operate in a discrete type space, standard Myersonian techniques are not readily available, see for example Kos and Messner [2013] on this. In order to get around that problem, for some of the results we will restrict attention to the set of mechanisms where local incentive constraints bind. From Pavan, Segal, and Toikka [2014] and Battaglini and Lamba [2019], we know that these are indeed the "right" set of mechanisms to consider: under first-order stochastic dominance, monotonic allocations that satisfy local incentive constraints are incentive compatible.

Let
, −1 (ℎ −1 ) be the incentive compatibility constraint that states that after (public) history ℎ −1 , buyer of type does not want to misreport to be type − 1. Similarly, let , +1 (ℎ −1 ) be the incentive compatibility constraint that states that after (public) history ℎ −1 , seller of type does not want to misreport to be type + 1. Since numerically larger types are better for the buyer and worse for the seller, the correct local incentive constraints to consider in the discrete type space problem are downward ( ↦ → − 1) for the buyer and upward ( ↦ → + 1) for the seller respectively. Define Then, a tight mechanism is simply one where all constraints in hold as equalities.
Definition 8. A mechanism = p, U is called tight if all elements of the set hold as equalities.
Next, define a monotonic allocation. To operationalize the notion of monotonicity, we put a partial order on the set of histories: for any ℎ = ( , ) and ℎ = (ˆ,ˆ) ∈ , ℎ ℎ if ≥ˆand ≤f or all ≤ .
A well known result then follows. The proof parallels the proof of Proposition 2 in Battaglini and Lamba [2019] and is omitted.
Lemma 2. Suppose = p, U is such that p is monotonic and all constraints in hold as equalities. Then, is incentive compatible.
Since the efficient allocation is monotonic, it follows that all tight mechanisms implementing the efficient allocation are incentive compatible. It is important to note that in the continuous types limit of the model, owing to the dynamic envelope theorem, all incentive compatible mechanisms are tight mechanisms.
9.2 Ex post incentive compatibility and proof of Lemma 1 Recollect the notion of (with-in period) ex post incentive compatibility defined in section 7.1. We use it to state and prove a stronger version of Lemma 1. Now, ex post incentive compatibility requires truthtelling for every possible current type of the other agent and every possible public history. This was introduced in Athey and Miller [2007]. A partial payoff equivalence result for ex post incentive compatibility follows.
Proof. Suppose p, U is ex post incentive compatible. Fix ℎ −1 . Then, ( , |ℎ −1 ) appears in two kinds of incentive compatibility constraints. First, Clearly, for any fixed ∈ C, the addition of the constants ( , ℎ −1 ) to ( , |ℎ −1 ) for all ∈ V does not affect any of these constraints.
Next, fix −1 . The second class of constraints we need to consider are Again, for any fixed ∈ C, this leads to addition of ( , ℎ −1 ) to ( , |ℎ −1 ) for all ∈ V which drops out of the constraint.
Therefore, linear additions of constants as defined in the lemma preserves incentives.
Taking expectations Lemma 1 follows as a corollary. Note that since the original min-max dynamic VCG mechanism constructed in section 5 is independent of history and satisfies ex post incentive compatibility statically, it is easy to see that it is in fact ex post incentive compatible.

Proof of Proposition 1
If there exists an implementable mechanism that satisfies ex post budget balance, then the same mechanism automatically satisfies interim budget balance. Conversely, suppose p, U (and equivalently p, x ) is an implementable mechanism that satisfies interim budget balance. Thus, Π(ℎ −1 ) ≥ 0 for all ℎ −1 , for all . Define the instantaneous expected budget surplus to be the following: Define a new mechanism p,Ũ as follows: ( |ℎ −1 ) = ( |ℎ −1 ) + Π(ℎ −1 ) ∀ , and for some number ∈ [0.1]. Then, by Lemma 1 the new mechanism is incentive compatible, and interim budget balance implies it is individually rational. Further, note that in this new mechanism, p,Ũ , interim budget balance is still satisfied as an equality for every history:Π(ℎ −1 ) = 0 for all ℎ −1 , for all . Thus, we haveΠ (ℎ −1 ) = 0 for all ℎ −1 , for all . Now,Π (ℎ −1 ) = 0 gives us a mechanism that satisfies "ex ante budget balance in the static sense" for every history. As a final step, we use the construction typically employed in static mechanism design to create another mechanism p,x (and hence p,Û ) that satisfies ex post budget balance.

Proof of Theorem 1
The proof proceeds as described in the construction of the min-max dynamic VCG mechanism in section 5. Define a subset of constraints which will be used in the relaxed problem: incentive constraints in and individual rationality constraints of the "lowest" types. C = 1 (ℎ −1 ), (ℎ −1 )∀ℎ −1 ∈ −1 ∀ Next, all constraints in hold as equalities for the min-max dynamic VCG mechanism.
Lemma 5. For the min-max dynamic VCG mechanism, p * , U * , all constraints in hold as equalities.
Proof. The proof for the fact that all constraints in hold as equalities follows from Lemma 4 and Lemma 1. Moreover, by construction ( , |ℎ −1 ) is monotonically increasing in , and ( , |ℎ −1 ) is monotonically decreasing in . Therefore, the respective infima are reached at type 1 and type respectively, which by construction get zero utility.
Recall the expression for the expected budget surplus and define the expected budget surplus from the min-max dynamic VCG mechanism to be Π * (ℎ −1 ).
We can keep reducing utility vectors backward till the first period, unless ℎ −1 contains , in which case the backward iteration ends there, to deduce a non-negative change in Π(ℎ −1 ). Thus, the changes do not violate any of the constraints and keep the objective to a value larger than or equal to that before the change.
Lemma 6 uniquely pins down interim expected utility vectors: ( |ℎ −1 ) and ( |ℎ −1 ∀( , ) ∈ V × C that maximize Π(ℎ −1 ) subject to the relaxed problem for all ℎ −1 , for all . Call this mechanism p * ,Û . It is to be shown that p * ,Û is implementable, that is, it satisfies all incentive compatibility and individual rationality constraints not included in .
36 Note that if −1 = we are done, so the rest of the proof assumes < .
From Lemma 5 one mechanism that delivers these interim expected utility vectors as inÛ is the min-max dynamic VCG mechanism, which by construction is implementable. Thus, must have that p * ,Û is implementable and it delivers the expected budget surplus of Π * (ℎ −1 ) for all ℎ −1 and for all .
Putting it all together we have that the min-max dynamic VCG mechanism achieves the highest expected budget surplus for every possible history in the class of implementable mechanisms which proves the result.
Note that following the same methodology we can prove something stronger-the same result for ex post incentive compatibility and ex post individual rationality.

Proof of Corollary 2
The methodology here is analogous to Athey and Segal [2013] and Yoon [2015]. Though unlike their proofs, owing to the dynamic min-max VCG mechanism, the threshold of required for efficiency to hold will be tightest possible in the construction that follows. Let Θ = V × C. First some notation.
9.9 Simple trading problem optimum for both the buyer and seller. Then a version of Lemma 1, that is the payoff equivalence result can be stated for the intermediate mechanism. Finally, the min-max dynamic VCG mechanism described in Section 7.2 delivers the precise characterization of the efficient allocation.