Maximal Procurement under a Budget
Nicole Immorlica Nicholas Wu Brendan Lucier




: Text-Guided Generation 
 of Functional 3D Environments in Minecraft
    Roberta Raileanu
    
=====================================================================




We study the problem of a principal who wants to influence an agent's observable action, subject to an ex-post budget. The agent has a private type determining their cost function. This paper endogenizes the value of the resource driving incentives, which holds no inherent value but is restricted by finite availability. We characterize the optimal mechanism, showing the emergence of a pooling region where the budget constraint binds for low-cost types. We then introduce a linear value for the transferable resource; as the principal's value increases, the mechanism demands more from agents with binding budget constraint but less from others. 






§ INTRODUCTION




In many natural scenarios, an ex-post budget constraint arises. In many institutional settings, the allocation of funds is separate from their usage; one government body might determine the amount of funding to go towards a certain goal, while a different government agency oversees the usage of those funds. In other situations, the resource being used to incentivize an agent can be non-monetary; with prizes or prestige, the agent naturally has a bounded value for the prize, and the principal's value for the prize is endogenous and determined by the mechanism.




We study the strategic interaction between a principal, endowed with a limited amount of a transferable resource, who attempts to influence the action of an agent with private information about its own costs. The scenario differs from the standard mechanism design literature in two important ways. Firstly, the principal is budget-constrained; that is, the principal cannot spend more than an upper bound regardless of the private information of the firm. Secondly, the value of the resource is endogenous to its ability to influence the agent; the principal has no value for the budget themselves, and only cares about its impact through the agent. This model is sufficiently general to also characterize many related design problems; we provide additional examples in Section <ref>.


In this paper, we extend the mechanism design and delegation literature by proposing a model for providing incentives under a budget constraint. We show that the optimal solution is implementable as a subsidy schedule, where the principal compensates the agent based on the observed change in production. We show that the schedule partitions the agent types into more and less efficient types, offering the entire budget for types that meet a threshold and discriminating on less efficient types. 


Intuitively, the primary concern for output induces a fully endogenous value of money for the principal. The principal's schedule can be understood as selecting some threshold type and splitting the agent types. All the more efficient agents are pooled; they are required to satisfy a single output threshold and given the entire budget. The more efficient agent types determine the shadow value of money; the less efficient agents face a schedule that optimizes with respect to this shadow value. The threshold trades off a welfare loss from withholding the budget from the less efficient agents with information rents it must pay the more efficient types. 

A positive measure of the most efficient types are always pooled, even as the budget increases.  To illustrate this point starkly, we consider agent cost functions that satisfy a separability condition. We show that under this separability condition, the shape of the schedule is invariant to the size of the budget. In other words, no matter how large the budget is, the threshold for the pooling region never changes.



We extend the model to allow a competitive “outside option” for the principal; that is, the unused residual budget has a linear value. 
We show that provided the value of the budget is not high, the same pooling region of the optimal schedule persists. The linear value case highlights the importance of the threshold type; as the principal's value for the resource increases, the principal asks more from types more efficient than the threshold, and asks less from types less efficient than the threshold. We can extend our methodology to a broader class allowing nonlinear, convex budget costs as well. However, the ex post budget constraint feature is critical to the results; the pooling region does not arise if the budget only needs to be satisfied ex ante. 

We also extend the model to allow competition between N agents vying to contract with the principal.  The principal can choose at most one of the agents to contract with based on their reported types.  This competition between agents relaxes the incentive constraints on the principal's schedule, as the selection rule gives agents an additional incentive to declare low costs.  We characterize the optimal transfer schedule for a principal who contracts with the best declared agent type.  We show that, unlike in the single-agent case, the optimal schedule may not be monotone under our ex post budget constraint.

The paper is structured as follows. In the next subsection, we preview the related literature in mechanism design and delegation and distinguish this particular situation from similar work. Section <ref>  details the model and assumption. Section <ref> formalizes the general mechanism design problem and highlights the important features of the model. Section <ref> discusses the model with a linear value for the resource. Section <ref> characterizes other variants of the model including our extension to multiple agents, and Section <ref> concludes.



 §.§ Literature

Our model is related to the literature on contract design in settings with moral hazard and private actions going back to <cit.> and <cit.>. In this line of work, a principal contracts with an agent to take a costly action that is not directly observable, but that results in an observable outcome that is payoff-relevant to the principal and upon which payments can be contingent. 
In contrast to this line of work, in our model the principal can observe the outcome (i.e., production) but has uncertainty over the cost function of the agent. Our work also introduces an ex-post constraint on transfers.

Additionally, our work is related to literature on monopoly regulation. Closely related work to ours is that of <cit.>, which studies a social planner problem for regulating a monopolist, and <cit.>, which introduces noisy cost observations. However, our work is distinct in multiple ways. Firstly, our environment considers a budget-constrained principal, whereas there are no constraints on transfers in the other models in the literature. Additionally, the only objective for the principal in our scenario is to maximize production, where as the principal in the monopoly regulation environment typically maximizes a weighted sum of consumer surplus and producer profits. There are other minor distinctions in our model; we allow for a broad class of cost functions for the agent, whereas the literature typically assumes particular functional forms.

Given that our work involves nonstandard value for transfers, we complement the literature on delegation. The original delegation framework was formulated to <cit.>, which introduced the general class of delegation problems and provides conditions for existence of a solution. <cit.> and follow-up delegation models <cit.> typically assume that contingent transfers are unavailable to the principal, and instead the principal retains the right to take a state-dependent action that impacts utilities of both the principal and agent. In contrast to this line of literature, our model does allow for contingent transfers between the principal and agent, but in a special way; the transfers do not factor into the principal objective and face a budget constraint. 

Given that the principal has no intrinsic value for the budget herself, our problem relates to the literature on budget-feasible mechanism design, initiated by <cit.>.  That paper studies a procurement problem where the designer wishes to purchase a utility-maximizing set items from sellers subject to a budget constraint.  A large literature followed, exploring the approximately optimal design under different combinatorial valuation functions for the principal and varying information structures and solution concepts (see, e.g., <cit.> and references therein). Our work is differentiated from this literature in that the principal is maximizing the variable action of a single agent rather than maximizing over a combinatorial set of items, and that agent has a convex cost of procurement. 

Also related is the literature on contest design.  This literature studies a setting in which a designer with a fixed budget wishes to solicit submissions to a contest.  The designer can split the budget among potentially multiple prizes.  The objective can be to optimize the aggregate quality of submissions <cit.>, or the quality of the best submission <cit.>.  Contests with multiple agents is reminiscent of the extension of our problem to multiple firms, discussed in Section <ref>.  In the contest design literature, agents work to potentially receive a prize from a set of prizes, with fixed utility values. In contrast, our work can be interpreted in the lens of contest design but providing incentives using a single perfectly divisible prize.

Methodologically, our paper uses optimal control techniques and arguments similar to <cit.> and <cit.>. Our design solution shares similar qualitative features as the hidden-information case of <cit.>, but the problems are different in a substantial way; because the control problem in <cit.> arises from a dynamic relationship, the constraint on the agent's action schedule in the design problem is bounded above by the value of the design problem and a term depending on the discount factor, whereas in our problem, the constraint on the agent's action schedule is instead given by an exogenous budget. This difference yields important distinctions in the outcome; in <cit.>, the first-best is sometimes possible, whereas it is never possible for a non-degenerate distribution of types in our case. 



§ MODEL


We first lay out the formalism for the model, and then discuss applications at the end of this section. Consider a principal-agent design problem where the principal would like to provide incentives for an agent to take a costly action. The action space is X = ℝ_+; an action x ∈ X can be interpreted as an amount of a good produced by the agent. Without loss, we normalize the space X so that the principal derives utility x from the agent taking action x. The agent has a private cost function Ψ: X ×Θ→ℝ_+, which determines the cost the agent incurs from producing x ∈ X given the agent's type θ∈Θ = [θ, θ̅] ⊂ℝ_+. Without loss, we normalize the cost function Ψ(0, θ) = 0 for all θ.

The agent's type is drawn prior to the start of the game by Nature from a full-support distribution μ∈Δ(Θ). The type is privately observed only by the agent, but the principal has belief μ over the agent type. We assume the belief μ admits a probability density function f, with corresponding cumulative distribution function F.

The principal has a budget T of a transferable resource that the agent values. The agent's utility is quasilinear in the cost and the transfer: that is, if the agent of type θ produces x and receives a transfer t, his utility is u_A(x, θ) = t -Ψ(x, θ). To be clear, we suppose the principal can observe the action x, as opposed to the moral hazard problem in <cit.> and <cit.>; instead, the principal must decide how to award funds given the observed action, without precisely knowing the agent's cost function. 

To highlight the key economic forces, we will present the baseline model where the principal has no value for the transferable resource. In Section <ref> we consider allow the principal to have a constant value the resource, and consider a generalized value function in the extensions in Section <ref>.


We assume the cost function Ψ is nonnegative, twice continuously differentiable, supermodular, and strictly increasing in both arguments. Additionally, we assume that Ψ is convex for all θ and its convexity Ψ_xx is increasing in θ. [Such assumptions appear in the cost-function considered by the hidden-information in <cit.>. However, in <cit.>, there is an additional assumption that Ψ_θθ x is nonnegative, but we do not require this.]


A couple of remarks about the assumptions and game structure are in order. The supermodularity assumption is indespensible, and intuitively requires that higher types suffer steeper costs. The C^2 differentiability assumption is technical and allows us to use cross-derivatives. The convexity assumptions ensure validity and sufficiency of first-order optimization conditions, and intuitively require that agent types are ranked in how convex their costs are.
For instance, in an example where the principal offers money to a firm, the assumption requires that the higher θ firms are less scalable (i.e. their production costs grow faster). In this setting, the type θ can be interpreted as an inefficiency parameter.

By standard arguments, we invoke the revelation principle, so we consider direct mechanisms where the agent reports his type to the principal subject to incentive compatibility and individual rationality constraints. (We will see later that all feasible direct mechanisms will be implementable by a subsidy schedule.)

More precisely, the mechanism design problem requires the principal to select functions x: Θ→ X and t: Θ→ℝ_+, in the following optimization problem:

    max_x, t      ∫_θ∈Θ x(θ) f(θ)  dθ
       subject to       t(θ) - Ψ(x(θ),θ) ≥  t(θ') - Ψ(x(θ'),θ)       ∀θ, θ'∈Θ      (IC)
              t(θ) - Ψ(x(θ),θ) ≥ 0       ∀θ∈Θ      (IR)
              t(θ) ≤ T       ∀θ∈Θ      (B)


To understand the problem, we provide three example applications of the model. 



  
Example (Emissions Reduction) Consider a policymaker trying to reduce emissions from a large population. Individuals in the population have private emissions abatement costs θ∼ F which determine how severely emissions reductions impact their utility; that is, Ψ(x, θ) is how costly an individual of type θ finds it to reduce their emissions by x. 
The policymaker cannot pay any single individual more than an upper bound T, but would like to induce the largest possible collective emissions reduction. The optimal mechanism can be implemented by a subsidy schedule, which determines how much compensation an individual receives as a function of the individual's emissions reduction.



  
Example (Altruism) Suppose an altruist or a government has pledged a budgeted sum T to spur production of a product (vaccine, baby formula) during a shortage. The altruist is the principal, and the monopoly producing the product is the agent, whose private type characterizes their production costs. The action x corresponds to the amount of the product produced, and the resource is the budgeted money. The altruist seeks to maximize production conditional on respecting the budget constraint.



  
Example (Non-monetary Incentives) Consider an academic institution interested in increasing its research output by hiring a new researcher. The institution can grant the researcher a non-monetary award (title, prize, tenure) which has no intrinsic value to the institution itself. The researcher values the award at T, and has a private cost of producing output Ψ(·, θ). The institution can assess the output of the researcher and decide with what probability to give the award. The mechanism in this example corresponds to the institution committing to a schedule that maps research output into a probability of receiving the award.



§ OPTIMAL MECHANISMS


In this section, we first present the mathematical characterization of the optimal mechanism. We then discuss some of the qualitative features of the model, notably the emergence of a pooling region. We provide some economic intuition for the optimal mechanism as splitting the type space into “efficient” and “inefficient” types and optimizing distinct shadow cost functions for the two. Finally, we show that the optimal mechanism admits a closed-form under a separability assumption on Ψ, and in this case, the size of the pooling region is invariant to T. 

Solving our mechanism relies on a lemma which characterizes the feasible schedules, or the set of allocations x: Θ→ℝ_+ for which there exists a transfer schedule t: Θ→ [0, T] that satisfies (IC), (IR), and (B). The lemma follows the standard mechanism design techniques to derive the feasible set.



    x: Θ→ X is a feasible schedule if and only if the following two conditions hold:
    
        
  * x is nonincreasing.
        
  * Ψ(x(θ),θ) + ∫_θ^θ̅Ψ_θ(x(s), s)  ds ≤ T
    
    Further, given a feasible schedule x, a transfer function that supports the schedule is given by 
    
    t(θ) = Ψ(x(θ), θ) +  ∫_θ^θ̅Ψ_θ(x(s), s)  ds



The first condition is a monotonicity constraint, and the second condition constrains the magnitude of x. Note that the normalization constraint (2) comes from the transfer bound, the IC constraints, and the envelope theorem, and so the feasible set characterization does not depend on the prior. Note the first part of the Lemma implies that these two conditions are necessary and sufficient for a feasible schedule, and the second part explicitly determines the transfer schedule that implements any feasible schedule.

The proof of Lemma <ref> is standard; we use supermodularity to show that x must be nonincreasing, and then apply the envelope theorem to the IC constraints to derive the transfer schedule. The transfer schedule in Lemma <ref> is analogous to the Myersonian transfer schedule, since the transfer schedule is also derived from using the envelope theorem to integrate out interim utility of the firm from the incentive compatibility conditions. 

The integral expression in the transfer expression is the information rent that type θ receives; since Ψ(x(θ), θ) is exactly the loss the firm experiences from producing x(θ), the transfer compensates the firm for the loss and provides additional rent, which is larger for more efficient types (lower θ). 

As a corollary, since Ψ and Ψ_θ are convex, conditions (1) and (2) jointly determine a strictly convex subset of the space of functions from Θ→ℝ_+.

Thus, as a corollary of our lemma, since the mechanism design problem maximizes a linear functional over a strictly convex set, the optimal mechanism is unique. 

    If a solution exists, the solution to the generalized mechanism design problem in (<ref>) is unique.



Further, Lemma <ref> implies that the mechanism is implementable by a subsidy schedule or action-contingent transfers; that is, the optimal mechanism x(θ), t(θ) parametrizes a well-defined function from X →ℝ_+. 


    Suppose θ < θ', and let x, t be a feasible mechanism. If x(θ) = x(θ'), then t(θ) = t(θ'). 


    By Lemma <ref>, since x must be nonincreasing and x(θ') = x(θ), x must be constant on (θ, θ'). As a minor abuse of notation, let x be that value on (θ, θ'). Then 
    
    t(θ)    = Ψ(x, θ) + ∫_θ^θ̅Ψ_θ(x(t), t)  dt 
       = Ψ(x, θ) + ∫_θ^θ'Ψ_θ(x, t)  dt + ∫_θ'^θ̅Ψ_θ(x(t), t)  dt 
       = Ψ_θ(x, θ') + ∫_θ'^θ̅Ψ_θ(x(t), t)  dt = t(θ')
 


Since x,t are both nonincreasing, the corollary implies that any feasible mechanism x(·), t(·) can be implemented as a subsidy schedule t̂: X →ℝ_+. 

With some more work, we can show the existence of a solution and characterize it with a differential equation system.


    An optimal mechanism (x, t) for (<ref>) exists and is unique. The optimal mechanism, together with a nonnegative Lagrange multiplier λ and a nonnegative, absolutely continuous costate function ρ, jointly solve the following system of differential equations with boundary constraints: 
     
    ρ(θ) > 0 ẋ(θ) = 0 
    ρ̇(θ) =  λΨ_xθ(x(θ), θ) - f(θ)
    ρ(θ̅) = 0 
    ρ(θ) = λΨ_x(x(θ),θ)  
    
            t(θ) = Ψ(x(θ),θ) + ∫_θ^θ̅Ψ_θ(x(s), s)  ds  = T

    where (<ref>) holds wherever ρ is differentiable.


To understand the result, note that the feasible set characterization in Lemma <ref> allows us to focus solely on characterizing x, subject to a nonincreasing condition and a rewritten budget constraint. We handle the budget constraint by writing the Lagrangian, and deal with the nonincreasing condition by taking an optimal control approach[See <cit.>] where `time' corresponds to the type interval, the control state variable is the required action x, and control variable is the derivative of x. We can interpret the conditions in Theorem <ref> through this control framework. The costate ρ denotes the shadow cost of the monotonicity constraint. The first condition (<ref>) is the complementary slackness condition; wherever the constraint's shadow cost ρ^* is positive, the constraint is binding (i.e. x is constant). The second condition (<ref>) dictates the costate evolution. The constraints (<ref>) and (<ref>) establish boundary conditions. The final constraint (<ref>) establishes that the budget binds at the most efficient / least costly type. 

The proof intuition follows three steps. First, we write out the Lagrangian relaxation of the problem using the feasible set characterization from Lemma <ref>. We formulate the optimization as an optimal control problem, where the control variable governs the derivative of x and is constrained to be nonpositive wherever x is differentiable. 

Second, we show that the conditions in Theorem <ref> are necessary and sufficient for an optimal mechanism. Fixing λ, the first four conditions (<ref>)-(<ref>) are necessary and sufficient for a solution to the Lagrangian relaxation control problem; necessity follows by invoking the Pontryagin maximum principle, and sufficiency follows from Arrow's sufficiency condition as proved in <cit.>. Sufficiency of λ > 0 and (<ref>) follows from Lagrangian duality; we show necessity by proving no solution to (<ref>)-(<ref>) exists for λ≤ 0. 

Finally, we prove existence. We use the theory of ordinary differential equations to show that (<ref>)-(<ref>) has a solution for λ > 0. We then use the intermediate value theorem to show that there must exist a λ such that (<ref>) holds. Since we proved in the second step that these conditions were necessary and sufficient for a solution, we thus showed that an optimal mechanism exists. Corollary <ref> implies that this solution must also be unique.

To understand how the characterization in Theorem <ref> can be used to determine the optimal mechanism, suppose λ were exogenously fixed. Consider the illustration in Figure <ref>. Complementary slackness implies that when ρ is positive, x must be constant, and whenever x is decreasing, ρ must be constant at zero, and hence x must follow the trajectory implied by the implicit equation derived from ρ̇ = 0. The boundary conditions dictate the start and end values of the costate ρ. Note that altering λ either uniformly increases or decreases x; intuitively, at the solution value of the Lagrange multiplier, the budget constraint exactly binds.




A remark on the convexity assumption on Ψ_θ is in order. The result in Theorem <ref> relies on the Pontryagin maximum principle providing a unique solution; this occurs given that the maximized Hamiltonian is concave. In the model, the Arrow sufficiency condition is that for all θ,

    xf(θ) - λΨ_θ(x,θ)

is concave in x. Assuming Ψ_θ is convex in x is equivalent to this sufficiency condition. [There are other sufficiency conditions for Pontryagin's maximum principle with weaker assumptions on the Hamiltonian. Relaxing assumptions on Ψ would require another sufficiency argument for the uniqueness of a solution characterized by the maximum principle.]

In the next sections, we discuss qualitative properties of the optimal mechanism and economic insights derived from the solution characterization in Theorem <ref>.



 §.§ Pooling

We first discuss when the principal awards the maximum T to the agent (i.e., for what types t(θ) = T). From the budget binding constraint, we know that the most efficient type θ always receives the full transfer. In this section, we provide three insights. First, we show that a positive measure of types always receive the entire transfer; we say the optimal mechanism “pools” the most efficient types. Second, we characterize the threshold type; agents more efficient than the threshold are pooled and receive the full transfer T, and the principal optimally withholds the resource from agents less efficient than the threshold. Third, we characterize when the optimal mechanism pools all types; in this case, the optimal mechanism simply pays the entire T to the agent whenever the agent meets a base action level. 


    There exists a θ̂ > θ such that the optimal mechanism x^* is constant on [θ, θ̂]. The transfer t^* is equal to T for these types.


Consider the conditions in Theorem <ref>. Since ρ(θ) > 0, complementary slackness (<ref>) implies that x^* must be constant until ρ reaches zero. Corollary <ref> implies that the optimal t^* is also constant on this set of types, and the budget binding condition (<ref>) implies that the transfer is T.


To intuitively understand why this pooling region always occurs, consider the loss in principal utility that occurs in the optimal mechanism relative to perfect information. With perfect information, the principal always gives away the entirety of the budget T and obtains the maximum action x from the agent such that Ψ(x,θ) = T. The optimal mechanism, relative to perfect information, differs in two ways. Either the principal cannot obtain the highest action because the principal deliberately withholds the resource, or the principal must concede information rent to the agent. Hence, the trade-off between the relative loss from these two effects dictates the size of the pooling region of the most efficient types.


    Suppose the optimal x^* is not constant on the entire interval of types. Let x≡ x^*(θ). Then the largest type θ̂ that receives the full transfer satisfies the following:
    
    Ψ_xθ(x, θ̂)/Ψ_x(x, θ̂)   =  f(θ̂)/F(θ̂)



    By optimality, there exists some Lagrange multiplier and costate function λ, ρ that satisfy the conditions of Theorem <ref>. At the cutoff, since x^* is not constant on the entire interval, it must be that x^* stops being constant at θ̂. Complementary slackness (<ref>) implies that ρ(θ̂) = 0. Integrating out the costate evolution (<ref>) gives 
    
    λΨ_x(x,θ̂) = F(θ̂)

    Since we assumed f was differentiable, x^* is continuous at θ̂ but the right derivative must be negative; hence, ρ̇(θ̂) = 0 since complementary slackness implies ρ must be constant at zero for some interval above θ̂. Using the costate evolution (<ref>) and taking the upper limit θ→θ̂, we get 
    
    λΨ_xθ(x,θ̂) = f(θ̂)

    Substituting out λ gives (<ref>).


To interpret this condition, 
rewrite (<ref>) as 
    Ψ_x(x, θ̂) = Ψ_xθ(x, θ̂) F(θ̂)/f(θ̂)

Under this rewriting, the condition is equivalent to the marginal benefit from paying the threshold type to be equal to the marginal information rent cost demanded.

It is possible that the principal always awards the entire T to the agent, regardless of the type. The following result characterizes when this happens. Let x̅ be such that T = Ψ(x̅, θ̅) (that is, the highest action that least efficient type θ̅ would be willing to take if given the entire budget T). Then

    The optimal mechanism pools all types (that is, the optimal x is constant) if and only if for all θ, 
    
    Ψ_x(x̅, θ) ≥ F(θ)Ψ_x(x̅, θ̅).

    Further, if the optimal mechanism pools all types, then x(θ) = x̅ and t(θ) = T for all θ.


First, suppose that x^*(θ) = x^* is constant. Let λ, ρ be the Lagrange multiplier and costate variable satisfying Theorem <ref>. By the budget binding condition (<ref>), 

    T    = Ψ(x^*, θ) + ∫_θ^θ̅Ψ_θ(x^*, s)  ds 
       =  Ψ(x^*, θ) + Ψ(x^*, θ̅) - Ψ(x^*, θ)  
       = Ψ(x^*, θ̅)

Hence, x̅ = x^*. By the upper bound condition (<ref>), integrating the costate evolution equation (<ref>), we must have 

    ρ(θ̅) = λΨ_x(x̅, θ̅) - 1 = 0

So λ = 1/Ψ_x(x̅, θ̅). Then since ρ satisfies the costate evolution condition (<ref>),

    ρ(θ) = λΨ_x(x̅, θ) - F(θ) ≥ 0

and so the result follows.

For the converse, suppose that λ̅Ψ_x(x̅, θ) ≥ F(θ) for all θ. Then construct ρ(θ) = λΨ_x(x̅, θ) - F(θ), and define x^*(θ) = x̅ and λ = 1/Ψ_x(x̅, θ̅). It is easy to check that these satisfy the condition of Theorem <ref>. Hence the optimal mechanism is x(θ) = x̅ and t(θ) = T for all θ.




  
Example Revisited (Emissions Reduction) Revisit the emissions reduction example from before. As Corollary <ref> implies, the optimal mechanism for the regulator is to offer a subsidy schedule, that pays some amount to each firm depending on their emissions reduction. Proposition <ref> implies that the regulator pays the maximum amount T for a sufficiently large reduction, which is taken by a positive measure of firms. Proposition <ref> then provides conditions for which the optimal regulator's policy has a “bang-bang” feature; that is, the regulator never gives any partial transfer, but only pays T or zero. This latter case is equivalent to providing an unconditional transfer and mandating a fixed level of emissions reduction.




















 §.§ Shadow Costs

Having established that the mechanism always admits a pooling region up to some θ̂, we provide some economic intuition for the optimal x given θ̂. That is, throughout this section, suppose the optimal mechanism has a cutoff type θ̂ < θ̅ determined by Proposition <ref>. We characterize the schedule above and below the cutoff, using the shadow value interpretation of the Lagrange multiplier λ.

First, define x̅≡ x(θ) for θ∈ [θ, θ̂]. The following result intuitively shows that the optimal x̅ solves a maximization problem for the principal, where the marginal benefit is given by the probability that the agent meets the cutoff, and the marginal cost is λΨ(·,θ̂), the shadow cost of the transfer that must be paid to the threshold type.

    Given the optimal shadow value of money λ, the highest action x̅ solves the following maximization:
    
    x̅ = max_x { x F(θ̂) - λΨ(x,θ̂) }.



    Integrating out the costate evolution from Theorem <ref>, we find that 
    
    λΨ_x(x̅,θ̂) - F(θ̂) = 0

    which is exactly the FOC for the maximization. The FOC exactly characterizes the solution since Ψ is convex in x. 


Corollary <ref> characterizes the tradeoff for the highest action x̅; intuitively, by increasing the highest action, the principal gets more production from F(θ̂) types of agents, but pays the shadow cost λΨ(·, θ̂). As mentioned before, the value of the Lagrange multiplier λ can be interpreted as the shadow value of the resource to the principal.

Now, we show that the types from (θ̂, θ̅] intuitively face a different shadow cost to the principal. This insight helps provide us an intuition for what the optimal mechanism looks like for types θ > θ̂. 


    Suppose Ψ_xθ(x, θ) / f(θ) is weakly increasing in θ and θ̂ < θ̅. Then on [θ̂, θ̅], the optimal x satisfies the point-wise maximization:
    
    x(θ) = max_x{ x f(θ) - λΨ_θ(x, θ) }
 


    Recall that by definition, since pooling ends at θ̂, ρ(θ̂) = 0. By the Bellman principle of optimality, the restriction of x to the domain [θ̂, θ̅], must be optimal for the following control subproblem:
    
    max_x      ∫_θ̂^θ̅( x(θ) f(θ) - λΨ_θ(x(θ), θ) )   dθ
       subject to      ẋ = u ≤ 0             (Monotonicity)

Note that the solution to (<ref>) point-wise maximizes the objective of the subproblem. To confirm that this is optimal, it suffices to show that x(θ) satisfies the monotonicity constraint. Note that since Ψ_θ is convex, the first-order condition for x gives 

    1 = λΨ_xθ(x, θ)/f(θ)

Note that the RHS is an increasing function of x. Since the RHS is assumed to be increasing in θ and increasing in x, it follows that x(θ) must be decreasing in θ.


To interpret the maximization problem in (<ref>), note that by increasing x(θ), the principal gains a marginal benefit of f(θ) but must pay Ψ_θ(x(θ),θ) more information rent to the best types (or equivalently, must procure Ψ_θ(x(θ),θ) of the resource). Note that the shadow resource cost is λ, so the cost is exactly the shadow information rent cost that must be paid. 

As a remark, note that the main obstacle to point-wise maximization is the monotonicity constraint; hence, one can obtain a more general variant of Proposition <ref> by ironing the shadow cost function Φ_θ(x,θ)/f(θ) (and in fact, this is what the costate variable does in Theorem <ref>). 

In sum, the optimal mechanism can be interpreted as the principal splitting the agent types into two populations, and maximizing x against different shadow cost functions. For the efficient types, the principal maximizes against the shadow production cost, λΨ; for the less efficient types, the principal maximizes against the shadow information rent cost, λΨ_θ. 



 §.§ Separable Cost Function

In this section, we show that for multiplicatively separable Ψ the mechanism admits a closed form solution, where the shape of the solution, including the pooling region from Proposition <ref>, is determined by the belief. In particular, the multiplicatively separable case is remarkable in that the size of the pooling region is independent of T, which we show in Proposition <ref>.

Firstly, we say Ψ is separable in x and θ if Ψ(x,θ) = B(θ) Γ(x), where Γ is convex by assumption. Without loss, since Ψ is assumed increasing in θ, we can renormalize the type space and redefine Θ so that Ψ(x,θ) = θΓ(x) where Γ is a strictly convex function. In this case, we can actually provide a closed-form characterization of the shape of the schedule. Let f̃ denote the left derivative of cav F, the concavification of the cumulative distribution function F on [0, ∞), and denote by (Γ')^-1 the inverse function associated with Γ' (which is increasing by assumption).

    Suppose that Ψ(x,θ) = θΓ(x), where Γ is convex. Then the optimal mechanism (x^*, t^*) induces a production schedule
    
    x^*(θ)= (Γ')^-1(f̃(θ)/λ)

    where λ is the nonnegative Lagrange multiplier chosen so that
    
    θΓ(x^*(θ)) + ∫_θ^θ̅Γ(x^*(θ))  dθ = T

    The transfer schedule is still given by Lemma <ref>.


Intuitively, this holds because the linearity of Ψ in θ allows the separation of the monotonicity constraint into a standard ironing problem. Thus, for this specific case, the optimal schedule depends on the density of the concavified cumulative distribution function of the belief, f̃. 

Since Proposition <ref> shows that x^* is an increasing transformation of f̃, the content of Proposition <ref> is that for separable cases, the shape of the optimal mechanism is entirely determined by the belief of the principal and not by the agent's cost function. Indeed, the pooling behavior of the optimal mechanism is completely identical for Ψ^A(x,θ) = θΓ^A(x) and Ψ^B(x,θ) = θΓ^B(x) for any two convex Γ^A, Γ^B.

We illustrate how this insight applies to a discrete, two-type example. Suppose θ is either 1 or 2, and the cost function takes the form Ψ(x,θ) = θ x^2. The principal believes that θ = 1 with probability μ. Figure <ref> illustrates f̃; for the two-type case, whether μ is larger than or less than 1/2 determines whether f̃(1) = f̃(2) or not. By Proposition <ref>, x^* is an increasing transformation of f̃, so the shape of f̃ also determines the shape of x^*. The optimal mechanism separates types 1 and 2 if and only if μ > 1/2. [In our modeling assumptions, we took F as continuous and differentiable. We can extend this to scenarios where F is discontinuous (equivalently, f admits point masses) by taking the limits of a sequence of continuous F_n converging to F and observing that that for the separable case, the optimizer function is continuous in f̃, which is continuous in f in the sup norm.]



Note that for the separable case, Propositions <ref> and <ref> simplify considerably:


    Suppose Ψ(x,θ) = θΓ(x), and suppose the optimal x^* is not constant on the entire interval of types. Let x≡ x^*(θ). Then the largest type θ̂ that receives the full transfer satisfies the following:
    
    1/θ̂   =  f(θ̂)/F(θ̂)



    Suppose Ψ(x,θ) = θΓ(x). Then the optimal mechanism pools all types if and only if for all θ, 
    
    θ / θ̅≥  F(θ)



In some sense, the upper bound on the schedule implied by Proposition <ref> follows from the existence of an upper bound on transfers. An initial intuition might be that the pooling region occurs because the constraint is binding, and that the binding region shrinks if T is large. However, this is not the case. The pooling arises because of the relative informational cost of separating low and high θ to relative production ability. In fact, for the separable case, we have the following result:


    Suppose Ψ(x,θ) = θΓ(x). Let θ̂ be the largest type that receives the full transfer. Then θ̂ is invariant to T and Γ.


    By Proposition <ref>, consider x_T and x_T', the optimal schedules for budgets T and T'. Since f̃ is unchanged, and x^* is an increasing transformation of f̃, the pooling region for x_T and x_T' are the same, and hence θ̂ is invariant to altering the size of the budget.


That is, the size of the pooling region does not change at all as T changes. This implies that the shape of the contract is determined primarily by the belief of the principal, and the scale of the contract is determined by the size of the budget. Hence, the existence of the pooling region at the top stems from the principal's relative tradeoff between giving up information rents and withholding a non-valuable resource. 



 §.§ Linear Subsidy Schedule


Suppose the principal only offered some linear subsidy, paying for x at a constant rate r. By setting such a subsidy schedule, very efficient types exhaust the budget and take x = T/r and less efficient types choose some x that equalizes their marginal cost with the rate: Ψ_x(x, θ) = r. We will show that the mechanism design approach can always do better; that is, some feasible schedule Pareto dominates the schedule resulting from a linear subsidy.

 
Let x_r be the outcome schedule from a linear subsidy at rate r. There exists a feasible schedule x^* in the mechanism design problem such that for all θ, x^*(θ) ≥ x_r(θ) with inequality holding strictly on a positive measure of θ.


From Proposition <ref>, we thus see that for any outcome implementable by a linear subsidy schedule, there is a feasible schedule implementable in the mechanism design problem that yields more output. So the linear subsidy schedule is dominated by the optimal outcomes that are implementable in the mechanism design problem.






























    








    








    



















§ LINEAR VALUE

In the baseline model, we supposed that the principal's objective was independent of t, which we interpret as the principal having no value for the motivational resource. In certain applications, it may be reasonable to suppose the principal does have some value for the resource (or alternatively, obtaining the resource incurs a cost to the principal per unit of resource). 

To motivate the model, we revisit our primary application, the emissions reduction example from before.



  
Example (Emissions Reduction) Let us return to the policymaker trying to induce a large number of firms to take reduce emissions. Now, in addition to providing a subsidies for emissions reductions, the policymaker could also use some of the funds to purchase emissions offsetting credits in a competitive market, where the market price for offsetting a unit of emissions is some constant k. The policymaker would like to maximize the net emissions reduction across both channels, via offsetting or reducing emissions.

Formally, consider a variation of the design problem (<ref>):

    max_x, t      ∫_θ∈Θ[  x(θ) - k t(θ) ]f(θ)  dθ
       subject to       t(θ) - Ψ(x(θ),θ) ≥  t(θ') - Ψ(x(θ'),θ)       ∀θ, θ'∈Θ      (IC)
              t(θ) - Ψ(x(θ),θ) ≥ 0       ∀θ∈Θ      (IR)
              t(θ) ≤ T       ∀θ∈Θ      (B)

where k ≥ 0 is some constant. That is, the important distinction is in the objective, where there is an additional -k t(θ) term that appears. This term could correspond to the principal obtaining some value from the unused T-t measure of resource, or the principal incurring some explicit cost to obtain the resource, with this problem degenerating to the original problem when k=0. We can characterize the optimal solution as follows:

    An optimal mechanism (x, t) for design problem (<ref>) exists, and it satisfies Lemma <ref>. There exists a nonnegative Lagrange multiplier λ, a nonnegative, absolutely continuous costate function ρ, and a nonnegative, absolutely continuous costate w, such that (x,t,λ,ρ,w) uniquely solve complementary slackness (<ref>), border conditions (<ref>) and (<ref>), a modified costate evolution given by 
     
    ρ̇(θ) =  λΨ_xθ(x^*(θ), θ) - f(θ)( 1 - k( Ψ_x(x^*(θ),θ) + Ψ_xθ(x^*(θ),θ)F(θ)/f(θ)) ) - w(θ)
   
    that holds wherever ρ is differentiable, and an additional complementary slackness constraint
    
    w(θ) > 0  x(θ) = 0.

    Further, the budget binding condition (<ref>) must hold if λ > 0.


A couple of comments on the modifications are in order. Note that the altered costate evolution features two new terms. First, 

    ψ(x,θ)=  Ψ_x(x,θ) + Ψ_xθ(x,θ) F(θ)/f(θ)

is the virtual marginal cost of the agent, similarly to the Myersonian virtual value. The second, w, is a complementary slackness variable that arises because the lower bound on x can bind and types of agents can be excluded in this case.



 §.§ Pooling

Given the additional term in the objective of the problem, we show that some features of the baseline solution still hold. Firstly, we have the following analogues of Proposition <ref> and <ref>:

    If λ > 0, there exists a θ̂ > θ such that the mechanism is constant on [θ,θ̂]. The transfer t^* is equal to T on this interval. Further, if θ̂ < θ̅, then θ̂ satisfies the following implicit equation:
    
    Ψ_xθ(x, θ̂)/Ψ_x(x,θ̂)( 1 - k Ψ_x(x,θ̂) ) = f(θ̂)/F(θ̂)

    where x = x(θ).


    If λ > 0, since the budget must bind, x(θ) > 0, and so it follows that ρ(θ) > 0, so complementary slackness implies that x must be constant and positive. Integrating out the new costate evolution, we get that since x(θ) > 0, w(θ) = 0, and so 
    
    ρ(θ) = λΨ_x(x,θ) - F(θ) (1 - k Ψ_x(x,θ))

    At the threshold θ̂, ρ(θ̂) = 0, and by a similar argument as Proposition <ref>, ρ̇(θ̂) = 0, so 
    
    λΨ_xθ(x, θ̂) = f(θ̂)( 1 - k( Ψ_x(x,θ̂) + Ψ_xθ(x,θ̂)F(θ̂)/f(θ̂)) )

    
    λ + F(θ̂)k =  f(θ̂)/Ψ_xθ(x, θ̂)( 1 - k Ψ_x(x,θ̂) )

    Combining, we get (<ref>).

With a linear value, the pooling region depends on whether the budget constraint binds. For sufficiently high values of k or high values of T, the optimal schedule may be such that the principal's optimal schedule in the absence of the budget constraint is actually feasible. Note that this could not happen in the baseline model, where the budget always binds; since the principal did not obtain any value from the resource in the baseline case, the baseline optimization problem without a budget constraint is unbounded (giving infinite resource to the agent). 

Also, with the principal having a value for the resource, it is possible that a positive measure of types are excluded from the mechanism. We provide a sufficient condition for such exclusion to happen.


Suppose Ψ_xθ(x, θ)/f(θ) is increasing in θ and k > 1/ψ(0, θ̅). Then the optimal mechanism excludes a positive measure of types.

Firstly, if k > 1/Ψ_x(0, θ) = 1/ψ(0, θ), it is not hard to check that the mechanism is degenerate: x(·) = t(·) = 0 (since intuitively, even the lowest cost type θ has a marginal cost of more than 1/k). So suppose k < 1/ψ(0, θ). By the costate evolution (<ref>), on a sequence of θ→θ̃ from the left, continuity of x implies that x is positive and decreasing. So w must be 0 and ρ = 0, so  
     
    0 = λΨ_xθ(0, θ̃) - f(θ̃) ( 1 - k (Ψ_x(0, θ̃) + Ψ_xθ(0, θ̃)F(θ̃)/f(θ̃)) )

     
    1 - kψ(0, θ̃)   =  λΨ_xθ(0, θ̃)/f(θ̃)

Note by our assumptions, the RHS is increasing, and the LHS is decreasing in θ̃. Further, the LHS goes from positive to negative from θ to θ̅ and the RHS is positive, so the intermediate value theorem implies there exists a θ̃ < θ̅ such that the equality holds. Then the optimal mechanism excludes all types θ > θ̃. 

Intuitively, this arises because the principal has a positive value for the resource; thus, intuitively, if some type of agent has an information rent-adjusted marginal cost of x as more than 1/k, the principal finds it best to exclude this agent.



 §.§ Comparison to Naive Benchmark

Recall in the baseline model, the problem was unbounded without the budget constraint, since the principal did not value the resource. With a linear value for the resource k, the problem is no longer unbounded; thus, we can compare the optimal mechanism to a naive solution, where the principal designs the mechanism (i.e. solves (<ref>)) without factoring the budget constraint, and instead “runs out” of money if the mechanism is supposed to offer t > T. 

The solution to the naive problem corresponds to the problem where the Lagrange multiplier λ is set to zero. As a result, from Theorem <ref>, the condition pinning down x when not in a flat region is missing a λΨ_xθ term, which implies that x is larger when the budget constraint does not bind. In consequence, the budget binds at a higher type than in the optimal mechanism (i.e. the naive solution spends more of the resource in expectation), and the naive solution obtains a lower x from the most efficient types of agents. Figure <ref> illustrates this with an example, where values are distributed uniformly on [1,2], k=0.3, the cost function is Ψ(x,θ) = θ x^2, and the budget is T=1. 






 §.§ Comparative Statics

We characterize how the optimal mechanism changes in terms of k in the following result. Define x̅ = x(θ); equivalently, x̅ is the x needed for the agent to get T in the mechanism. 

As k increases, x̅ increases and λ decreases: dx̅/dk > 0 and dλ / dk < 0. 


We leave the proof to the appendix; the key idea is that we identify three equations from Theorem <ref> that pin down (x̅,θ̂,λ), and apply the implicit function theorem to derive the comparative statics. To illustrate the implications of the proposition, Figure <ref> plots the optimal mechanism for Ψ(x,θ) = θ x^2, T=2, and θ uniformly distributed on [0,1]. As k increases, the x required to receive the full transfer T in the optimal mechanism decreases, and the mechanism excludes more types. However, since λ increases in k, it also is true that x(θ̅) decreases; that is, the principal becomes more lenient on the less efficient types, reducing x for higher types. 
 
Revisiting the emissions reduction example, the comparative statics in k can be interpreted as changes in the optimal subsidy schedule as the emissions offset market becomes more or less effective. The comparative statics highlight the role of the threshold θ̂: as the outside option increases, the policymaker becomes more demanding (asks for more aggressive emissions reductions x) from firms that are more efficient than the threshold, but becomes more lenient (asks for less emissions reductions x) from types that are less efficient than the threshold. 





§ VARIANTS



In this section, we discuss some other extensions of our model. We first consider a generalization with multiple agents, and derive the control problem characterizing the optimal solution. 
We also characterize the problem under an ex-ante budget constraint, and contrast the optimal mechanism to the solution characterized by Theorem <ref>. 



 §.§ Multiple Agents

Suppose the principal could contract with one of N agents, each of whose private type is drawn independently from F. That is, consider the problem:

    max_x, t      ∫_θ∈Θ 
     x(θ) (1 - F(θ))^N-1 f(θ)  dθ
       subject to       t(θ) - Ψ(x(θ),θ) ≥  t(θ') - Ψ(x(θ'),θ)       ∀θ, θ'∈Θ      (IC)
              t(θ) - Ψ(x(θ),θ) ≥ 0       ∀θ∈Θ      (IR)
              t(θ) ≤ T       ∀θ∈Θ      (B)

This problem is a restricted version of a fully-general multi-agent problem; specifically, we restrict that the principal can only contract with the best (least cost type) of the agents, and must design the contract independently of the other agents' reports. Further, the incentive constraint (IC) requires the agent reporting the best-type to not want to deviate, conditional on being the best type. Note that under this specification, the problem is equivalent to the original problem (<ref>), under a modified type distribution F̃ = 1 - (1-F)^N, where F̃ is the distribution of the lowest-cost type of N draws from F; thus, our analysis from the baseline applies to this problem.

The design problem focuses on scenarios where the principal can only interact with a single agent; for example, consider a procurement environment where the government is interested in completing a project with a non-monetary objective (such as quality, reduced emissions, or time to completion), the firms have private operational ability, and the government can only contract with a single firm for the project.

The problem in (<ref>) imposes strong incentive constraints; effectivelly, the constraints require that even if all the agents colluded on reporting to maximize agent welfare, the mechanism is still incentive compatible. As such, the value of the problem from (<ref>) provides a lower bound on the value of the multi-agent problem with weaker incentive constraints on the agents. An alternative approach might be to consider Bayesian incentive constraints; that is, agents find it incentive compatible to report truthfully, given a prior over the types of the other agents. Mechanisms with these weakened incentive constraints can look quite strange; we construct a simple example where the optimal mechanism under these constraints is even nonmonotone.

Consider a three-type scenario with two agents; each agent's cost function is θ x^2, where θ∈Θ = {1, 2, 3}. Fix the budget T = 3, and consider a scenario where the type is drawn θ = 3 with probability 1-ϵ, θ = 2 with probability δϵ, and θ = 1 with probability ϵ(1-δ), for ϵ, δ > 0. Intuitively, when ϵ is small, the agents are most likely θ = 3, so IR binds to extract as much as possible from the most common type: hence x(3) = 1, and t(3) = 3. However, conditional on an agent not being type 3, the agent is most likely to be type 1 when δ is small. In a monotone schedule, the agent of type 2 receives information rent, because type 2 could report being type 3. However, the presence of a second agent means that the designer could dramatically decrease the information rents type θ=2 receives by using the fact that type θ=2 is more likely to win (i.e. be contracted with) than type 1; as a result, the designer can pay type θ=2 less than the full budget (and potentially ask less than x = 1) and still satisfy Bayesian incentive compatibility. This has a benefit to the designer when suppressing type θ=2's information rents means a larger x from type θ=1. Table <ref> plots numerical values of the optimal BIC mechanism for this example at varying values of δ; indeed, when δ is small, the optimal mechanism is non-monotone precisely to extract a larger x(1) from the best type. 

The example highlights a key distinction in how an ex-post treatment of budget constraints fundamentally differs from a per-unit cost treatment. In the exercise of a multi-agent problem with BIC constraints, where we replace the budget constraint by inducing a resource cost in the objective of the principal, we find that the optimal mechanisms must be monotone (this can be shown via standard arguments; an envelope theorem can be applied to replace the transfers in the objective, and integration by parts implies that the principal allocates to the best virtual type). However, in the example provided, the reason the principal is willing to sacrifice production of the intermediate type θ = 2 is precisely because the resource is inherently valueless, and so the optimal mechanism actually pays the full budget to both the θ = 1 and θ = 3 types. The optimal mechanism does the former because the type is more efficient, and the latter because the θ = 3 type is more prevalent. Since the θ = 2 type is neither, the optimal mechanism trades off production from that type in order to pay less information rent to the θ = 1 type.




















































 §.§ Ex Ante Budget Constraints

An alternative formulation might require that the budget only needs to bind ex-ante (i.e., the expected transfer cannot exceed T). That is, consider the problem replacing the budget constraint (B) with

    ∫_θ^θ̅ t(θ) f(θ)  dθ≤ T       ∀θ∈Θ      (B')

The optimal solution is characterized by the following proposition.
 
    Replacing (B) with (B'), an optimal mechanism (x, t) exists, and is unique. Further, there exists a nonnegative Lagrange multiplier λ and a nonnegative, absolutely continuous costate functions ρ such that (x,λ,ρ) is unique solution that satisfies Lemma <ref> and complementary slackness (<ref>) holds, with the modified costate evolution equation
    
    ρ̇(θ) = f(θ)(1 - λ( Ψ_x(x(θ), θ) + Ψ_xθ(x(θ), θ)F(θ)/f(θ)) )

    upper boundary condition (<ref>), modified lower bound condition ρ(θ) = 0, and modified budget binding condition
    
    ∫ f(θ) ( Ψ(x(θ),θ) + ∫_θ^θ̅Ψ_θ(x(s), s)  ds)  dθ  = T



Notably, the lower boundary condition is modified to ρ(θ) = 0, and hence the pooling region that appears for the ex-post budget constraint does not appear here. Thus, the key feature of our model, the pooling region where the principal trades off between utilizing the budget less or providing information rents, does not emerge in the case where the budget is only required ex-ante.



§ CONCLUSION


 We analyze a mechanism design model where a principal interacts with an agent, where the principal has a budget of a resource it can provide as an incentive. The design problem features an ex-post budget constraint and a first-order objective maximizing the agent's action. We derive the optimal mechanism, and show that the mechanism pools sufficiently efficient types and withholds the budget from less efficient types. The pooling region threshold is crucial to understanding how the mechanism changes when the principal has a resource value; as the resource value increases, the principal demands more or less from agents depending on their type relative to the threshold. 
 
 There are several promising avenues for future research. First, one could extend our framework to dynamic incentives; adding temporal dimensions could help illustrate how optimal mechanisms evolve over time, with changing resource availability and agent behavior. Additionally, our model's applicability to various domains suggests insights for real-world implementations and empirical validations. Lastly, extending the model to allow for more general uncertainty, such as an uncertain resource value or a richer space of cost functions, could enhance the practical relevance of this paper's insights. 



agsm






§ APPENDIX: SUPPLEMENTAL MATERIAL




 §.§ Omitted Proofs


Consider any x that satisfies the two conditions. Take t given by (<ref>). Since Ψ_θ is nonnegative, t(θ) ≥Ψ(x(θ),θ), so IR is satisfied. Now, we show that t must be nonincreasing. Suppose θ≤θ'. Then 

    t(θ)    = Ψ(x(θ),θ) + ∫_θ^θΨ_θ(x(s),s)  ds 
       = Ψ(x(θ),θ) + ∫_θ^θ'Ψ_θ(x(s),s) ds + ∫_θ'^θΨ_θ(x(s),s) ds 
       ≥Ψ(x(θ),θ) + ∫_θ^θ'Ψ_θ(x(θ'),s)  ds + ∫_θ'^θΨ_θ(x(s),s) ds 
       = Ψ(x(θ),θ) + Ψ(x(θ'),θ') - Ψ(x(θ'),θ)  + ∫_θ'^θΨ_θ(x(s),s) ds 
       = [ Ψ(x(θ),θ)- Ψ(x(θ'),θ)] + t(θ')

where we used the fact that x is nonincreasing and supermodularity of Ψ in the 3rd step. Also, since x is nonincreasing, and Ψ is increasing in its first argument, the bracketed part is nonnegative, and so we have that t is nonincreasing. Hence, to check the budget constraint, we just have to check that the budget constraint holds at t(θ):

    t(θ) = Ψ(x(θ),θ) + ∫_ΘΨ_θ(x(s),s)  ds = ∫_ΘΨ_θ(x(s),s) ≤ T

Finally, to check that IC is satisfied, consider IC for type θ. We consider the deviation of θ to θ'. We first show that θ does not want to deviate up, or θ≤θ':

    t(θ) - Ψ(x(θ), θ)    =  ∫_θ^θΨ_θ(x(s), s)  ds 
       =  ∫_θ^θ'Ψ_θ(x(s), s)  ds + ∫_θ'^θΨ_θ(x(s), s)  ds 
       = ∫_θ^θ'Ψ_θ(x(s), s)  ds + t(θ') - Ψ(x(θ'), θ') 
       ≥∫_θ^θ'Ψ_θ(x(θ'), x) + t(θ') - Ψ(x(θ'), θ') 
       =  Ψ(x(θ'),θ') - Ψ(x(θ'),θ)+ t(θ') - Ψ(x(θ'), θ') 
       = t(θ') - Ψ(x(θ'),θ)

Now we check that θ does not want to deviate down to type θ' ≤θ:

    t(θ) - Ψ(x(θ), θ)    = ∫_θ^θΨ_θ(x(s), s)  ds
       = -∫_θ'^θΨ_θ(x(s), s)  ds + ∫_θ'^θΨ_θ(x(s), s)  ds 
       = -∫_θ'^θΨ_θ(x(s), s)  ds + t(θ') - Ψ(x(θ'), θ') 
       ≥ -∫_θ'^θΨ_θ(x(θ'), s)  ds + t(θ') - Ψ(x(θ'), θ') 
       = - Ψ(x(θ'),θ) + Ψ(x(θ'),θ')+ t(θ') - Ψ(x(θ'), θ') 
       = t(θ') - Ψ(x(θ'),θ)

So IC is satisfied. Thus, if x satisfies the conditions, it is feasible.

Now, we show the two conditions are necessary. Consider any feasible x: Θ→ℝ_+. Suppose θ≤θ', and θ, θ' ∈Θ. From rewriting the IC constraints, we get that 
    
    Π(x(θ); θ) - Π(x(θ'); θ) ≥ t(θ') - t(θ)

    
    Π(x(θ'); θ') - Π(x(θ); θ') ≥ t(θ) - t(θ')
Note that the Π_LF(θ) and Π_LF(θ') terms will cancel on the left hand sides. Adding these together, we get 

    -Ψ(x(θ), θ) + Ψ(x(θ'), θ) - Ψ(x(θ'), θ') + Ψ(x(θ),θ') ≥ 0

Rearranging

    Ψ(x(θ'), θ) +  Ψ(x(θ),θ') ≥Ψ(x(θ), θ) + Ψ(x(θ'), θ')

And so supermodularity of Ψ implies that x(θ') ≤ x(θ), and so the first condition must hold. To show that the transfers must take the form given, define the interim utility

    U(θ) = t(θ) - Ψ(x(θ),θ)

IC implies that 

    U(θ) = max_θ' t(θ') - Ψ(x(θ'),θ)

By the envelope theorem,

    U'(θ) = - Ψ_θ(x(θ),θ)


    U(θ) = U(θ̅) + ∫_θ^θ̅Ψ_θ(x(s),s)  ds

So transfers must be of the form 

    t(θ)    = U(θ)  
       = U(θ̅)+ Ψ(x(θ), θ) + ∫_θ^θ̅Ψ_θ(x(s),s)  ds
 
In particular, the transfer for type θ satisfies 

    T    ≥ t(θ) 
       =  U(θ̅)+ Ψ(x(θ),θ) + ∫_θ^θ̅Ψ_θ(x(s), s)  ds 
       ≥Ψ(x(θ),θ) + ∫_θ^θ̅Ψ_θ(x(s), s)  ds
 
since U(θ̅) ≥ 0 by IR. Hence, the two conditions are necessary and sufficient for a feasible schedule.



By Lemma <ref>lem:general_feasible, we can rewrite the design problem as 

    max_x      ∫_Θ x(θ) f(θ)  dθ
       subject to      Ψ(x(θ),θ) + ∫_θ^θ̅Ψ_θ(x(s), s)  ds  ≤ T             (Normalization)
              x  nonincreasing            (Monotonicity)

The Lagrangian relaxation is

    max_x      ∫_Θ x(θ) f(θ)  dθ + λ(T - Ψ(x(θ),θ) - ∫_θ^θ̅Ψ_θ(x(s), s)  ds  )  
       subject to       x  nonincreasing            (Monotonicity)

By monotonicity, x must be differentiable almost everywhere. The monotonicity constraint then requires that wherever x is differentiable, ẋ≤ 0. Letting u = ẋ and rewriting the objective function, the problem becomes 

    max_x      ∫_Θ( x(θ) f(θ) - λΨ_θ(x(θ), θ) )   dθ + λ T - λΨ(x(θ),θ)  
     
       subject to      ẋ = u ≤ 0             (Monotonicity)

The problem now is an optimal control problem with a scrap value constraint; u is the control variable, and x is the state variable. To argue that this rewriting is without loss, we adopt the <cit.> argument. The original problem optimizes over the space of nonincreasing x. Given an optimal solution x^* to (<ref>) that is absolutely continuous and nonincreasing, x^* must also be optimal over the original space, since the space of absolutely continuous nonincreasing functions is dense in the space of nonincreasing functions under the weak norm topology, and the maximization objective is continuous.

We first show that an optimal mechanism (x,t) satisfies the conditions (<ref>)-(<ref>). For a fixed λ > 0, Pontryagin's maximum principle implies that any optimal solution admits a nonnegative, absolutely continuous control variable such that (<ref>) - (<ref>) are true. Further, note that if λ = 0, (<ref>) implies that ρ(θ) = 0, but (<ref>) implies that ρ̇(θ) = - f(θ) < 0, which is impossible since ρ must be nonnegative. Hence, λ > 0, so by Lagrangian duality we must have that the budget binds, so (<ref>) holds. 

Second, we show that any solution that satisfies (<ref>)-(<ref>) must be optimal. Note that fixing λ, the maximized Hamiltonian corresponding to the control problem is concave in the state variable x, so the Arrow sufficiency condition holds.[See <cit.> for details.] Therefore, the solution maximizes the Lagrangian and and the budget constraint (<ref>) binds, the solution must be optimal in the original design problem. 

Finally, we argue that an optimal mechanism exists (uniqueness holds from Corollary <ref>). To show an optimal mechanism exists, we show that a solution to conditions (<ref>)-(<ref>) exists. 
Fixing λ, the conditions (<ref>)-(<ref>) admits a solution[More precisely, a solution in the extended sense, i.e. absolutely continuous and satisfying the differential equations almost everywhere.] (x_λ, ρ_λ) by the Caratheodory existence theorem. Define t_λ as the transfer schedule for x_λ by equation (<ref>). We now argue that a λ exists such that (<ref>) holds. To show such a λ exists, we argue that t_λ(θ) is continuous in λ, t_λ(θ) → 0 for λ→∞, and t_λ(θ) →∞ for λ→ 0; the intermediate value theorem then implies the result. 

For continuity of t_λ(θ), note that taking any sequence {λ_k }→λ, the family of control problems (<ref>) admits an optimal x_λ_k, which must converge x_λ_k→ x_λ weakly in H^1 by Theorem 3.1 from <cit.>. Hence, by construction of t_λ, t_λ_k(θ) → t_λ(θ). 

To characterize the boundary, note that as λ→∞, the limit control problem is simply 

    max_x      λ( ∫_Θ -Ψ_θ(x(θ), θ)   dθ + T - Ψ(x(θ),θ)  ) + o(λ)
    
       subject to      ẋ = u ≤ 0             (Monotonicity)

which has an optimal solution of x = 0 everywhere in the limit λ→∞, and hence t_λ(θ) → 0 as λ→∞. Finally, note that as λ→ 0, the problem becomes 

    max_x      ∫_Θ x(θ)f(θ)  dθ
       subject to      ẋ = u ≤ 0             (Monotonicity)

which is unbounded, and hence t_λ(θ) →∞ as λ→ 0. Thus, by the intermediate value theorem, there exists a λ such that t_λ(θ) = T. 



As in the proof of Theorem <ref>, we write out the Lagrangian:

    max_x      ∫_Θ x(θ) f(θ)  dθ + λ(T - θΓ(x(θ)) - ∫_θ^θ̅Γ(x(s))  ds  )  
       subject to       x  nonincreasing            (Monotonicity)

Define f(θ) = 0 for θ < θ. Then note that the optimization can be rewritten equivalently as 

    max_x      ∫_0^θ̅ x(θ) f(θ)  dθ + λ(T - ∫_0^θ̅Γ(x(s))  ds  )  
       subject to       x  nonincreasing            (Monotonicity)


To handle the monotonicity constraint, we use a generalized ironing technique. By Theorem 4.4 in <cit.>, the optimal x(θ) then maximizes J(·, θ; λ) at the optimal λ, where 

    J(x, θ; λ) = ∫_0^s ∂/∂θ^-cav_θ[ F(θ) - λθΓ'(x) ] dθ

and cav_θ denote the concavification operation in θ, where the differentiation is taken from the left (as the concavification need not be smooth in θ). Note that since (θ - θ) is linear in θ, we can rewrite J as 

    J(x, θ; λ) = ∫_0^x ∂/∂θ^-cav_θ[ F(θ) ]dθ - λΓ'(x)


    = f̃(θ) -  λΓ'(x)

Hence, the problem is reduced to a point-wise optimization at each θ: inverting Γ' implies that 

    x^*(θ)= (Γ')^-1(f̃(θ)/λ)

It remains to argue that a λ exists such that the budget constraint binds. Note that as λ→ 0, x^* →∞, and as λ→∞, x^* → 0. Hence, the intermediate value theorem implies some finite value of λ makes the budget constraint bind.


We construct a transfer schedule t that implements x_r and then show that that transfer schedule does not exhaust the budget, implying that we could increase production on some measure of types. Let θ̂_r be the largest θ such that Ψ_x(T/r, θ) ≤ r; that is, the largest θ whose marginal cost of producing at T/r is less than r.

First, suppose that θ̂_r = θ̅. Then under r, any type of firm produces T/r. So 
    
    Ψ(x_r(θ)θ) + ∫_θ^θ̅Ψ_θ(x_r(θ), θ)  dθ = Ψ(T/r, θ̅) < T/rΨ_x(T/r, θ̂_r) ≤T/rr = T

    where the first inequality follows from convexity of Ψ in x, and the third line follows from the definition of θ̂_r. Thus, the transfer schedule given by (<ref>) implements x_r without exhausting the budget.

    Now, suppose θ̂_r < θ̅. Then 
    
    Ψ(x_r(θ)θ) + ∫_θ^θ̅Ψ_θ(x_r(θ), θ)  dθ =   ∫_θ^θ̂_rΨ_θ (T/r, θ̂_r) dθ + ∫_θ̂_rΨ_θ(x_r(θ), θ) d θ
    
        =   Ψ(T/r, θ̂_r) +∫_θ̂_r[ Ψ_θ(x_r(θ), θ) + Ψ_x(x_r(θ), θ) x_r'(θ)] d θ
        - ∫_θ̂_rΨ_x(x_r(θ), θ) x_r'(θ) dθ
    
        =   Ψ(T/r, θ̂_r) +[ Ψ(x_r(θ), θ)-Ψ(x_r(θ̂_r), θ̂_r)] - ∫_θ̂_rΨ_x(x_r(θ), θ) x_r'(θ) dθ
    
        =   Ψ(x_r(θ), θ)- r ∫_θ̂_r x_r'(θ) dθ
    
        =   Ψ(x_r(θ), θ) - r (x_r(θ) - x_r(θ̂_r)) 
    
        =   Ψ(x_r(θ), θ) - r (x_r(θ) - T/r) 
    
        =    T + Ψ(x_r(θ), θ) - Ψ_x(x_r(θ),θ)x_r(θ) < T

    where (<ref>) uses the fact that the agent equalizes marginal cost with the subsidy rate, Ψ_x(x, θ) = r.




The analysis proceeds exactly as in Theorem <ref>; in this case, we plug in the transfers from Lemma <ref> into the objective and integrate by parts. The Hamiltonian becomes 

    ℋ = x f(θ)  - λΨ_θ(x, θ) - k Ψ(x,θ) f(θ) - k Ψ_θ(x, θ) F(θ) + ρ u

Applying Pontryagin, the costate evolution (<ref>) follows.



    Since Ψ_xθ(x, θ)/f(θ) is weakly increasing in θ, it is easy to check that the x that solves ρ̇ = 0 is nonincreasing. 
    First, define the subproblem on [θ̂, θ̅] with no initial conditions:
    
    max_x, t      ∫_θ̂^θ̅[  x(θ) - k (Ψ(x(θ), θ) +  ∫_θ^θ̅Ψ_θ(x(s), s)  ds ) - λΨ_θ(x(θ),θ)]f(θ)  dθ
       subject to       x  nonincreasing            Monotonicity

    Note that any solution to the conditions in Theorem <ref> restricted to [θ̂, θ̅] also solve the Pontryagin necessary conditions for this subproblem, and hence by Arrow's sufficiency theorem, the subsolution must also optimize this subproblem. 
    
    Then by Proposition <ref>, the objects x̅, the threshold type θ̂, and λ jointly solve the following three equations: 
    
    G_1(x̅,θ̂,λ; k)    = Ψ(x̅,θ̂) + ∫_θ̂^θ̅Ψ_θ(x(s),s)  ds - T    = 0 
    
            G_2(x̅,θ̂,λ; k)    =λΨ_x(x̅,θ̂) - F(θ̂)(1 - k Ψ_x(x̅, θ̂))     = 0 
    
            G_3(x̅,θ̂,λ; k)    = λΨ_x(x̅,θ̂) +  k( Ψ_x(x̅, θ̂) f(θ̂) + Ψ_xθ(x̅, θ̂)F(θ̂)) - f(θ̂)    = 0

    where x(s) solves the point-wise first-order condition from the maximized Hamiltonian of the subproblem (<ref>) at the optimal u:
    
    H'(x(s),s,λ;k) = λΨ_x(x(s),s) +  k( Ψ_x(x(s), s) f(s) + Ψ_xθ(x(s), s)F(s)) - f(s) = 0

    We apply the implicit function theorem to find the derivatives. The Jacobean of the system evaluated at (x̅,θ̂,λ) is 
    
    J = [                                       Ψ_x                                         0           ∫_θ̂^θ̅Ψ_xθ(x(s),s) dx(s)/dλ ds;                             (λ + k F)Ψ_xx                                         0                                       Ψ_x;               k(Ψ_xx f + Ψ_xxθF) + λΨ_xxθ k(2Ψ_xθf + Ψ_x f' + Ψ_xθθF) + λΨ_xθθ - f'                                      Ψ_xθ ]

        where the functions are understood to be evaluated at (x̅,θ̂,λ) where appropriate. The Jacobean is invertible since the partial ∂ G_1/∂λ is negative because dx(s)/dλ is negative, and the other nonzero entries are positive. Note that 
        
    ∂ G_1/∂ k = ∫_θ̂^θ̅Ψ_xθ(x(s),s) dx(s)/dk ds < 0

        
    ∂ G_2/∂ k = Ψ_x F

        Then from the implicit function theorem, we have 
        
    dx̅/dk = Ψ_x ∫_θ̂^θ̅Ψ_xθ(x(s),s) (  dx(s)/dλF(θ̂) -dx(s)/dk)  ds/(Ψ_x)^2 - (λ + kF)Ψ_xx∫_θ̂^θ̅Ψ_xθ(x(s),s) dx(s)/dλ ds

        
    dλ/dk =  (λ + kF)Ψ_xx F∫_θ̂^θ̅Ψ_xθ(x(s),s) dx(s)/dk ds - (Ψ_x)^2 F/(Ψ_x)^2 - (λ + kF)Ψ_xx∫_θ̂^θ̅Ψ_xθ(x(s),s) dx(s)/dλ ds

        From the observation that dx(s)/dλ < 0, it follows that the denominators are strictly positive, so the sign of each of these derivatives is the same as the sign of the numerator. It follows then that dλ / dk < 0, since dx(s)/dk is negative. To determine the sign of dx̅/dk, we apply the implicit function theorem for dx(s)/dλ and dx(s)/dk, and obtain that:
        
    ∫_θ̂^θ̅Ψ_xθ(x(s),s) (  dx(s)/dλF(θ̂) -dx(s)/dk)  ds 
       = ∫_θ̂^θ̅Ψ_xθ(x(s),s) (  - ∂ H/∂λ/∂ H/∂ xF(θ̂) - -∂ H/∂ k/∂ H/∂ x)  ds 
       = ∫_θ̂^θ̅Ψ_xθ(x(s),s) (  - Ψ_x(x(s),s)/∂ H/∂ xF(θ̂) + Ψ_x(x(s), s) f(s) + Ψ_xθ(x(s), s)F(s)/∂ H/∂ x)  ds
       = ∫_θ̂^θ̅Ψ_xθ(x(s),s) (  Ψ_x(x(s), s) f(s) + Ψ_xθ(x(s), s)(F(s) - F(θ̂))/∂ H/∂ x)  ds

        Since ∂ H /∂ x is positive, and s ≥θ̂ it follows that this quantity is positive; hence dx̅/dk is positive.





































































    By Lemma <ref>, we can reduce (IC) and (IR) into a monotonicity constraint and a transfer schedule. Adding a Lagrange multiplier λ to the budget constraint, the control problem becomes
    
    max_x      ∫_Θ x(θ) f(θ)   dθ + λ( T -  ∫_θ^θ̅(Ψ(x(θ), θ) +  ∫_θ^θ̅Ψ_θ(x(s), s)  ds  ) f(θ)  dθ)    
             ẋ = u ≤ 0

Integrating by parts, and writing the integral in one term, we get

    max_x      ∫_Θ( x(θ)- λ( Ψ(x(θ), θ) + Ψ_θ(x(θ), θ)F(θ)/f(θ)) )  f(θ)   dθ + λ T   
             ẋ = u ≤ 0

Applying Pontryagin and the Arrow sufficiency result, we get the conditions in the proposition. 



