# Collective Upkeep

Erik Madsen111Department of Economics, New York University (Email:
emadsen@nyu.edu). Eran Shmaya222Department of Economics, Stony Brook
University (Email: eran.shmaya@stonybrook.edu).

###### Abstract

We design mechanisms for maintaining public goods which require periodic non-
monetary contributions. Utilitarian welfare is maximized by concentrating
contributions among low-cost group members, but such policies generally induce
some members to leave the group or misreport their preferences. To forestall
exit, contributions must be shifted from members with intermediate costs to
some high-cost members. To deter misreporting, members must be screened using
up to two membership tiers, which reward larger contributions with increased
access to the good. We apply our results to the design of platforms such as
Netflix and TikTok hosting crowd-sourced recommendation engines, which
function as public goods supported by user feedback about new content.

Keywords: Public goods provision, steady-state mechanism design,
crowdsourcing, recommendation engine

##  1 Introduction

Social and economic groups commonly band together to provide public goods by
pooling contributions from individual group members. A collective action
problem arises whenever the group benefits of these contributions exceed their
private benefits to the contributor. Institutions are needed to coordinate
contributions and ensure that group members internalize their collective
benefits.

A large literature has studied the design of institutions for overcoming this
problem, focusing on settings in which group members make monetary
contributions. In some contexts, however, members may make “in-kind” or other
nonmonetary contributions. An important example involves crowdsourced
recommendation engines maintained by online platforms such as Netflix and
TikTok. Those platforms rely on customer feedback about new content to make
informed recommendations to other members. Feedback is costly for customers to
provide, for instance because it requires consuming content of unknown quality
or because reporting one’s experience takes time and energy. Further, some of
the social value of this feedback accrues to other customers, who benefit from
improved recommendations. This feedback is therefore effectively a
contribution to a public good, and a platform wishing to efficiently elicit it
must solve a collective action problem.

We study the design of mechanisms for solving such problems. We formalize our
analysis through a model of _collective upkeep_ (Section 2). In our model, a
machine provides services to a large group of agents over a long time horizon.
The machine periodically breaks, rendering it useless until sufficient
contributions have been collected to fix it. All agents benefit from the
services provided by a working machine but dislike contributing to fix it,
with potentially heterogeneous preferences for both activities. A designer
seeking to maximize the group’s long-run welfare crafts a mechanism, which
regulates access to the machine’s services and solicits contributions from
group members. She can extract contribution promises from agents ex-interim,
i.e., after they have observed their preferences but before they learn the
machine’s current state.

We model the relationship between contributions and the long-run uptime of the
machine in a flexible, reduced-form way admitting multiple interpretations. To
facilitate application of our results and comparisons with existing work, we
describe two interpretations in detail: A fluid setting featuring a large
population of long-lived agents participating simultaneously (Section 6), and
a Poisson setting featuring a sequence of short-lived agents participating
asynchronously (Section 7).

Our setting can be viewed as a variant of classic public goods provision
problems, with the twist that contributions are nonmonetary. In particular,
they can be made at a limited rate and only when the machine is broken, and
they cannot be stored for later use. (We elaborate on this relationship in
Section 2.3.1.) Since the designer commits to directives based on information
(the state of the machine) that is not available to agents, our model
additionally has an information-design interpretation. Formally, it can be
viewed as an information design problem in which the designer’s information
and payoff function are endogenously determined by the mechanism. (We
elaborate on this relationship in Section 2.3.2.)

Under a first-best mechanism, the designer asks all agents with sufficiently
low contribution costs to contribute whenever the machine is broken (Section
3). Unfortunately, when agents have heterogeneous preferences, this mechanism
generally induces some agents with low usage benefits to leave the group.
Participation constraints must therefore be incorporated into the mechanism
design problem.

If the designer can observe agents’ preferences, the optimal mechanism ensures
participation of all agents by customizing their contribution requirements
(Section 4). In general, optimal contributions drop with an agent’s
contribution cost and rise with their usage benefit. When agent preferences
satisfy a total ordering condition, optimal contributions exhibit a tripartite
structure: High types contribute fully and low types contribute nothing, while
intermediate types make partial contributions. Notably, participation
constraints bind only for intermediate types, and so utility is non-monotone
in an agent’s type.

If the designer cannot observe agents’ preferences, a mechanism must restrict
access to the machine in order to truthfully elicit preferences (Section 5).
We show that the optimal screening mechanism offers at most two distinct
participation levels. In one, the agent enjoys full access to to the machine.
In the other, the agent enjoys only limited access while incurring a reduced
responsibility for contributions. Under this mechanism, some agents choose to
opt out of the group.

These results suggest new lessons for the design of recommendation engines.
Purely voluntary feedback leaves an unresolved collective action problem, and
in the absence of incentive constraints the average user’s experience could be
improved by collecting additional mandatory feedback from some users. However,
this policy may lead some users to stop participating. Our results indicate
that platforms may be able to more efficiently elicit feedback by mandating a
small amount from users as a baseline, while simultaneously offering a premium
membership tier with better-tailored recommendations in return for additional
feedback.

###  1.1 Related literature

Our collective upkeep model is most closely related to work studying
mechanisms for provision of excludable public goods, notably [17] and [27].
Our model differs from those in two key respects. First, group members may
differ in their cost of contribution. This heterogeneity creates a utilitarian
motive for concentrating contributions on low-cost group members, an objective
absent from existing work. Second, group members face bounds on their ability
to contribute. This constraint drives the optimality of mechanisms with
multiple access and contribution levels. By contrast, a posted price would be
optimal in a model with atomistic agents and no contribution limits, as in the
large-population limit of [27].

Recent work by [4] similarly features differing contribution costs and bounds
on contribution levels. Unlike our model, their agents cannot be excluded from
the public good, so must be incentivized to contribute through the possibility
that their contribution is pivotal. In the large-population limit, optimal
public goods provision therefore converges to zero unless the per-capita cost
of the public good vanishes. By contrast, in our setting the additional
instrument of excludability allows non-vanishing contributions to be extracted
from a large population. An additional distinction is that in our model, the
contribution bound is endogenously determined and tightens as more of the
public good is provisioned. This feature has no analog in their model.

Our setting also bears similarities to the literature studying dynamic
contribution models [1, 14, 24, 10, 25, 11, 3]. In these models, players make
incremental contributions toward the provision of a public good. Unlike in our
setting, they cannot commit to contribution plans before observing the state
of the public good, creating incentives for dynamic freeriding. We instead
focus on how dynamics constrain players’ opportunities to contribute.

As applied to crowd-sourced recommendation engines, our paper contributes to
recent work in both economics [22, 8] and computer science [15, 18, 23]
studying incentive-compatibility of crowdsourced recommendations. A common
theme of these studies is that recommendation engines are constrained in their
ability to foster experimentation when agents can observe the time that new
content has been available. In particular, potential early adopters expect the
underlying algorithm to have little information and distrust the engine’s
recommendations. In our model, the designer can obscure the time since new
content has arrived. She is instead constrained in her ability to
preferentially select agents for experimentation on the basis of their
preferences.

Methodologically, our analysis shares important features with studies of long-
run or steady-state mechanism design, especially in queuing [9] and matching
[2]. In these settings, agents view themselves as participating in a
stationary system with an endogenous state whose distribution is the same for
all agents. This assumption contrasts with the prevalent framework, where the
initial state is exogenous and agents’ incentives change systematically with
calendar time. This stationary perspective plays a central role in our dynamic
model interpretations. (See Sections 6 and 7 for details.)

##  2 Model

###  2.1 Setting

A group of agents enjoy the services provided by an excludable public good,
which for concreteness we refer to as a _machine_ , over a doubly infinite,
continuous time horizon. At each moment the machine is either _working_ or
_broken_. The machine provides services only when it is working, and a working
machine breaks periodically. A broken machine must be fixed through
contributions from group members. Each agent can contribute only when the
machine is broken and faces a limit on his rate of contribution, which without
loss we normalize to 1.

Agents value the machine according to the frequency with which they use its
services and contribute to fixing it. Agents have heterogeneous preferences
over these two outcome metrics, summarized by _types_ $\theta$ drawn from a
probability measure $\lambda$ over a (Borel) space $\Theta$. If an agent of
type $\theta$ uses the machine a fraction $r\in[0,1]$ of the time and
contributes a fraction $p\in[0,1]$ of the time, he enjoys total utility

$\displaystyle r\cdot u(\theta)-p\cdot c(\theta),$ (1)

where $u(\theta)>0$ is the agent’s usage benefit and $c(\theta)>0$ is his
contribution cost. We assume that $u,c\in\mathscr{L}^{1}(\lambda).$

###  2.2 Design problem

A designer is responsible for overseeing the machine’s upkeep. To do so, she
collects contributions from agents and regulates their access to the machine’s
services. Concretely, she chooses an _allocation_ $(R,P)$ consisting of the
long-run _usage levels_ $R:\Theta\rightarrow[0,1]$ and _contribution levels_
$P:\Theta\rightarrow[0,1]$ for all agents. Her goal is to maximize utilitarian
social welfare

$W(R,P)=\int\Big{(}R(\theta)\cdot u(\theta)-P(\theta)\cdot
c(\theta)\Big{)}\,\lambda(\mathrm{d}\theta).$ (2)

The set of feasible allocations is limited by _physical constraints_ related
to the process by which the machine breaks and is fixed. We implement these
constraints in a reduced-form way consistent with multiple interpretations.
Because these interpretations do not add any further formal content to our
analysis, we defer describing them in detail until Sections 6 and 7.

Let $Q\in[0,1]$ denote the long-run fraction of time the machine is working,
which we refer to as the machine’s _uptime_. Then the physical constraints are
given by

$\displaystyle\rho\cdot Q=\int P\,\mathrm{d}\lambda$ (B) $\displaystyle
R(\theta)\leq Q,\quad P(\theta)\leq 1-Q$ (S-$\theta$)

The _balance condition_ (B) says that the long-run rate at which the machine
breaks (on the left-hand side) must balance the long-run rate at which agents
contribute to fixing it (on the right-hand side). The parameter $\rho>0$ can
be interpreted as the machine’s breakage rate. The _simplex bounds_
(S-$\theta$) say that the agent’s usage and contributions are bounded by the
respective frequencies with which the machine is working and broken.

The set of feasible allocations may additionally be limited by _economic
constraints_ related to agents’ freedom of action. These constraints encode
interim participation and incentive compatibility requirements familiar in the
study of mechanism design.

Formally, the participation constraints are

$R(\theta)\cdot u(\theta)-P(\theta)\cdot c(\theta)\geq 0.$

The left-hand side captures an agent’s payoff from participating in the
mechanism, while the lower bound of 0 is an agent’s outside option obtained by
never using or contributing to fix the machine. The IC constraints are

$R(\theta)\cdot u(\theta)-P(\theta)\cdot c(\theta)\geq R(\theta^{\prime})\cdot
u(\theta)-P(\theta^{\prime})\cdot c(\theta).$

That is, each agent can obtain any other agent’s usage and contribution levels
by misreporting his type. Under incentive compatibility, no agent should
prefer to do so.

Given a feasible allocation $(R,P)$, the machine’s uptime $Q$ is pinned down
by the balance condition (B). Nonetheless, as we will explain later, it is
technically convenient to include $Q$ as an additional design variable and
enforce (B) by imposing it as a constraint on the designer’s welfare
maximization problem. We therefore study the designer’s problem of choosing a
_mechanism_ $(R,P,Q)$ to maximize utilitarian welfare (2) subject to the
physical constraints (B) and (S-$\theta$), as well as potentially the economic
constraints (2.2) and/or (2.2).

###  2.3 Relationship to existing models

Our model is closely related to static models of public goods provision and
information design. We now describe the precise relationship between these
settings. Both the similarities and differences are instructive for
understanding our results and our contribution to the literature, in
particular the role of our physical constraints.

####  2.3.1 Public goods provision

In a static public goods provision problem, a designer must raise
contributions simultaneously from a group of heterogeneous agents in order to
produce a collective good. As a benchmark, consider the following static
model, which is a closest approach to our collective upkeep model. Let $Q$
represent the quantity of the public good produced, $P$ be the vector of
contributions, and $R$ be the vector of allocations of the public good. The
group is a continuum of mass 1, with the distribution of preferences described
by a measure $\lambda$ over the type space $\Theta.$ Agents have linear
utility for consumption and linear costs from contribution, so that their
payoffs are as in (1). Production is governed by the linear production
function implied by the balance condition (B). The public good is excludable,
so that any $R$ such that $0\leq R(\theta)\leq Q$ is feasible.

This static benchmark is very close to the setting studied by Hellwig (2003)
and Norman (2003). The main distinction between their setting and our
benchmark is that here agents are atomistic (i.e., infinitesimal). As a
result, the designer faces no aggregate uncertainty over group preferences.
Otherwise, the benchmark is a special case of their setting, with linear
production and consumption utility.

Payoffs for all players are the same in the static benchmark and our model of
collective upkeep. Additionally, the constraints on feasible allocations in
the former model are a subset of the ones in the latter. In particular, the
economic constraints on participation and incentive compatibility are
identical in the two settings. Furthermore, the balance condition and the
simplex bound $R(\theta)\leq Q$ are required for feasibility in both settings.
The key difference between the settings is that the collective upkeep model
requires the additional simplex bound $P(\theta)\leq 1-q.$

This extra constraint not only limits each agent’s ability to contribute, but
it imposes an _endogenous_ bound governed by overall provision of the public
good. In a static setting, exogenous contribution bounds could be justified
through budget constraints or the contribution of a scarce non-monetary
resource like labor. (For an example of a public goods problem in which
exogenous contribution bounds are imposed, see the recent work of [4].)
However, in static settings there is no natural microfoundation for
contribution bounds which depend on the contributions of other agents. In our
collective upkeep setting, by contrast, such bounds arise naturally.

####  2.3.2 Information design

In a static information design problem, a sender attempts to persuade a
receiver to take their preferred action by disclosing information about an
underlying state. As a benchmark, consider the following problem, which is a
closest approach to our collective upkeep model. The receiver who can take one
of two actions, “Interact” (I) or “Avoid” (A). He receives payoff 0 from A and
a state- and type-dependent payoff from I, where the state space is
$\Omega=\\{W,B\\}$ and he receives payoff $u(\theta)$ if $\omega=W$ and
$-c(\theta)$ if $\omega=B.$ The sender’s payoffs agree with the receiver’s
except when $(\omega,a)=(B,I)$, in which case the sender receives payoff
$y-c(\theta)$ for some $y>0.$ The state is $W$ with prior probability $Q.$

With observable agent types, this problem is similar to the binary-action
information design problems studied in [19]. With unobserved types, it is akin
to ones studied in [21] and [16]. Standard arguments from these settings imply
that the binding incentive constraints involve obedience to a recommendation
of $a=I$ and (if types are unobserved) truthful reporting. As a result, the
set of incentive constraints can be reduced to the set of economic constraints
appearing in the collective action model. In particular, the participation
constraint ensures obedience to recommendations of $a=I$, while the IC
constraint ensures truthful type reporting.

The key difference between the two settings is that in the collective upkeep
problem, the variables $Q$ and $y$ are endogenously determined by the balance
condition. In particular, the rate at which the receiver chooses $a=I$ when
$\omega=B$ pins down $Q$ via the balance condition, and this linkage in turn
determines the social value $y$ to the planner of interacting with a broken
machine. This feedback loop has no analog in static information design
settings, where payoffs and the distribution of states are exogenous.

##  3 First-best mechanism

We now solve for the designer’s optimal mechanism satisfying the physical
constraints, without imposing any economic constraints. Formally, the designer
chooses $(R,P,Q)$ to maximize aggregate welfare (2) subject to the balance
condition (B) and simplex bounds (S-$\theta$) for all $\theta\in\Theta.$

###  3.1 Characterizing the optimum

An immediate observation is that welfare is increasing in agents’ usage of the
machine, while usage levels do not appear in the constraints. As a result, at
the optimum all agents should enjoy full access to the machine. Formally,
$R(\theta)=Q$ for all types at the optimum, saturating the corresponding
simplex bounds. Going forward, we enforce this choice of $R$ and drop it from
the optimization problem.

We next establish that an optimal mechanism concentrates contributions on low-
cost members. Formally, the first-best contribution levels exhibit a threshold
structure, with agents whose contribution cost falls below a threshold
$y^{\mathrm{fb}}$ contributing the maximum amount, while agents with higher
costs do not contribute at all. Let $\bar{u}=\int u~{}\mathrm{d}\lambda$ be
the group’s aggregate usage benefit from a working machine.

######  Proposition 1.

Let $y^{\mathrm{fb}}$ be the unique $y$ solving

$\bar{u}-\rho\cdot y=\int(y-c)^{+}~{}\mathrm{d}\lambda,$ (3)

and let $W^{\mathrm{fb}}$ be the common value in (3) evaluated at $y^{FB}$.
Then the mechanism $(P^{\mathrm{fb}},Q^{\mathrm{fb}})$ defined by

$\rho\cdot\frac{Q^{\mathrm{fb}}}{1-Q^{\mathrm{fb}}}=\text{Pr}_{\lambda}(c<y^{\mathrm{fb}}),\text{
and }$ (4)
$P^{\mathrm{fb}}(\theta)=(1-Q^{\mathrm{fb}})\mathbf{1}_{[c<y^{\mathrm{fb}}]}(\theta)$

solves the first-best problem and yields welfare $W^{\mathrm{fb}}$. If the
distribution of $c$ under $\lambda$ is non-atomic, then this mechanism is
uniquely optimal.333If $\lambda(\\{c(\theta)=y^{\mathrm{fb}}\\})>0$, then
there exists a range of distinct optimal mechanisms differing in their
treatment of marginal types.

To prove the optimality of a threshold contribution structure, we consider the
Lagrangian relaxation of the problem with respect to the balance condition.
Assigning a Lagrange multiplier $y$ to that constraint yields the Lagrangian

$\mathscr{L}(P,Q;y)=Q\cdot\left(\bar{u}-\rho\cdot y\right)+\int
P(\theta)\cdot(y-c(\theta))\,\lambda(\mathrm{d}\theta)$ (5)

Holding $(Q,y)$ fixed, the Lagrangian factorizes over types, allowing $P$ to
be optimized pointwise. Note that this factorization relies on the inclusion
of $Q$ as an auxiliary optimization variable.

The optimal multiplier $y^{\mathrm{fb}}$ measures the social value of fixing
the machine. Indeed, $y^{\mathrm{fb}}$ is the amount of money the designer
would be willing to pay to fix the machine immediately when it breaks down.
While this idea can be made formal using dynamic programming principles, such
techniques are not easily generalized to incorporate economic constraints. By
contrast, the Lagrangian approach taken in our proof is readily adapted to
these constraints, as we will demonstrate shortly.

###  3.2 Comparative statics

We now examine how the optimal mechanism is shaped by the breakage rate
$\rho.$ The fact that $y^{\mathrm{fb}}$ measures the social value of fixing
the machine is reflected in its response to an increase in the breakage rate
$\rho.$ Since this adjustment reduces the machine’s average lifespan, it must
decrease the social value of fixing it. As a result:

######  Corollary.

The first-best contribution threshold $y^{\mathrm{fb}}$ is decreasing in the
breakage rate $\rho$.

###### Proof.

The left-hand side of (3) is decreasing in $y$ while the right-hand side is
increasing. Since an increase in $\rho$ induces a downward shift in the
former, $y^{\mathrm{fb}}$ must decrease in $\rho.$ ∎

A lower contribution threshold means that the machine is fixed more slowly
when it breaks. As a result, machine uptime must decline with $\rho$:

######  Corollary.

Machine uptime $Q^{\mathrm{fb}}$ under the first-best mechanism is
nonincreasing in the breakage rate $\rho$ and decreasing whenever
$Q^{\mathrm{fb}}>0$.

###### Proof.

(4) implies that $Q^{\mathrm{fb}}$ is nonincreasing in $\rho$ and decreasing
whenever it is positive, while it is and nondecreasing in $y^{\mathrm{fb}}$.
Since the previous corollary established that $y^{\mathrm{fb}}$ is decreasing
in $\rho,$ it follows that $Q^{\mathrm{fb}}$ is as well. ∎

In spite of these two results, it need not be the case that the long-run
aggregate contribution level $\int P\,\mathrm{d}\lambda$ is decreasing in
$\rho.$ Recall that the bound on each agent’s contribution level is
endogenously determined by the machine’s downtime $1-Q^{\mathrm{fb}}.$ Since
downtime increases in $\rho,$ all agents asked to contribute do so more often.
This force can overwhelm the countervailing reduction in $y^{\mathrm{fb}}$.
For instance, if $\Theta$ is a singleton, then (3) implies that
$y^{\mathrm{fb}}=(u(\theta)+c(\theta))/(1+\rho)>c(\theta)$ for sufficiently
small $\rho$. In that regime, the aggregate contribution level is
$1-Q^{\mathrm{fb}}$, which is increasing in $\rho$ in light of the previous
corollary.

##  4 Mechanisms with participation constraints

We now solve for an optimal mechanism under the additional economic constraint
that all agents must prefer the mechanism to their outside option. Formally,
we impose the participation constraints (2.2) for all $\theta\in\Theta.$ For
the time being, we continue to assume that the designer observes agents’
types.

When agents are homogeneous, the first-best mechanism of a utilitarian
designer must deliver all agents a non-negative payoff and so satisfies
participation mechanically. However, when agents have heterogeneous
preferences, the first-best mechanism generally violates the participation
constraints of some agents. The optimal mechanism must therefore be re-derived
under these constraints.

###  4.1 Characterizing the optimum

As in the first-best solution, there is no reason to restrict any agent’s
access to a working machine. Indeed, such restrictions would lower social
welfare while simultaneously tighten participation constraints. Hence
$R(\theta)=Q$ for all types at the optimum. Going forward, we enforce this
choice of $R$ and drop it from the optimization problem.

In this reduced problem, the participation constraint may be rearranged to
obtain an upper bound on each agent’s contribution level:

$P(\theta)\leq Q\cdot\nu(\theta),$

where

$\nu(\theta)=u(\theta)/c(\theta)$

captures an agent’s rate of substitution between access and contributions. We
will refer to this quantity as the _valuation_ of an agent of type $\theta.$
This representation allows the two constraints (S-$\theta$) and (2.2) to be
combined into the single constraint

$\displaystyle P(\theta)\leq\min(1-Q,Q\cdot\nu(\theta))$ (SP-$\theta$)

Since participation constraints merely modify the upper bound on feasible
contribution levels, a threshold contribution structure is optimal for the
same reasons as in the first-best problem. The new feature of the problem with
participation constraints is that agents who are asked to contribute may do so
at different levels. Since the constraints (SP-$\theta$) are type-dependent,
types for whom $\nu(\theta)<(1-Q)/Q$ contribute a type-dependent amount less
than their feasible maximum. These are precisely the agent types for whom
participation constraints bind.

Let

$\ell(Q;y)=Q\cdot(\bar{u}-\rho\cdot
y)+\int\min(1-Q,Q\cdot\nu(\theta))(y-c(\theta))^{+}~{}\lambda(\mathrm{d}\theta)$
(6)

be the designer’s reduced Lagrangian under the optimal threshold contribution
rule, where recall that $y$ is the Lagrange multiplier on the balance
condition. The following theorem establishes that an optimal mechanism under
participation constraints can be obtained by solving the minimax problem
associated with $\ell$.

######  Theorem 1.

Let $W^{*}$ be the value and $(Q^{*},y^{*})$ be the smallest444The selection
of the smallest saddle point is not needed for optimality, but we adopt it as
a convention for comparability with the mechanism characterized in Proposition
1. saddle point of the concave-convex minimax problem

$\min_{y\geq 0}\max_{Q\in[0,1]}\ell(Q;y)=\max_{Q\in[0,1]}\min_{y\geq
0}\ell(Q;y),$

with $y^{*}$ defined as $+\infty$ if the minimum is not attained. Then the
mechanism $(P^{*},Q^{*})$ with

$P^{*}(\theta)=\min(1-Q^{*},Q^{*}\cdot\nu(\theta))\mathbf{1}_{[c<y^{\mathrm{fb}}]}(\theta)$

solves the designer’s problem under participation constraints and delivers
welfare $W^{*}.$ Moreover, $y^{*}\geq y^{\mathrm{fb}}$, and this inequality is
strict if $W^{*}<W^{\mathrm{fb}}$.

The cost threshold $y^{*}$ is the optimized value of the Lagrange multiplier
on the balance condition. As a result, it has a natural interpretation as the
(marginal) shadow value of fixing the machine. When participation constraints
bind, this value is larger than under the first-best mechanism. Indeed, fixing
the machine not only generates usage benefits for other agents (as in the
unconstrained problem) but additionally loosens their participation
constraints by raising the machine’s uptime. As a result, the designer can
concentrate contributions on a narrower set of low-cost agents.

Surprisingly, this latter force can be powerful enough to induce the designer
to fix the machine more often when participation constraints bind than when
they do not. (Of course, this higher uptime cannot improve social welfare over
the first-best outcome.) The following example illustrates this possibility.

######  Example.

Consider a three-type environment $\Theta=\\{L,M,H\\}$ with

| L | M | H
---|---|---|---
$u$ | 3 | 4 | 10
$c$ | 3 | 2 | 1.25
$\lambda$ | 1/3 | 1/3 | 1/3

The machine breaks at rate $\rho=5.5.$ In this setting, $y^{FB}=2.7$ and
$Q^{FB}=4/15,$ while $y^{*}=45/14$ and $Q^{*}=2/7>q^{FB}.$

###  4.2 Ordered types

In general, the set of participation-constrained agents are those with
sufficiently low contribution costs and simultaneously sufficiently low usage
benefits. When costs and benefits comove, this set takes a particularly simple
form.

######  Definition 1.

Agent types are _ordered_ if $\Theta=\mathbf{R}_{-}$ and $\nu$ is increasing
in $\theta$ while $c(\theta)=-\theta$.

The substantive content of ordered types is that the type structure is one-
dimensional and valuations are increasing while costs are decreasing along
this dimension. The identification of $\theta$ with the agent’s cost is simply
a convenient normalization. It is without loss, since types can always be
relabeled to achieve this identity.

Recall that the first-best mechanism requires agents with sufficiently low
costs to contribute. For ordered types $c$ is decreasing, and therefore the
first-best mechanism can be characterized by a type threshold
$\theta^{\mathrm{fb}}=-y^{\mathrm{fb}}$ above which agents are asked to
contribute. Meanwhile, because $\nu$ is increasing under ordered types,
participation constraints are active on an interval of intermediate types.
Intuitively, the designer’s incentives are aligned with both high-type agents
(who don’t mind contributing) and low-type ones (for whom contributing is too
costly to be socially valuable). A conflict arises only for intermediate-type
agents, who generate a large social value from contributing but do not
sufficiently enjoy using the machine.

The following proposition formalizes this reasoning. It additionally
establishes that the interval on which participation constraints bind includes
the first-best contribution threshold.

######  Proposition 2.

Suppose that first-best welfare is not achievable under participation
constraints. If types are ordered, then there exists an optimal mechanism in
which the types with active participation constraints form an interval
containing $\theta^{\mathrm{fb}}.$

###  4.3 Comparative statics

Unlike the first-best solution, the optimal threshold $y^{*}$ under
participation constraints does not exhibit unambiguous comparative statics in
the breakage rate $\rho$. There are two contrasting forces here. On the one
hand, as in the first-best problem, frequent breakdowns reduce the usage
benefits generated by fixing the machine. On the other hand, participation
constraints tighten as breakdowns become frequent, and fixing the machine more
often loosens these constraints. Fixing the machine therefore generates a
social cost savings, because it allows the designer to concentrate
contributions on low-cost agents.

The tension between these forces is illustrated by the limiting behavior of
$y^{*}$ as $\rho$ grows large. Depending on the thickness of the right tail of
the valuation distribution, contributions may become narrowly concentrated on
low-cost types (i.e., the first force dominates) or else dispersed throughout
the population of agents (the second force dominates).

######  Proposition 3.

Suppose that $\mathbb{E}_{\lambda}[\nu]=\infty$ and the distribution of $c$
under $\lambda$ has full support on $\mathbb{R}_{+}.$

  * •

If $\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=0$, then
$\lim_{\rho\rightarrow\infty}y^{*}=\infty.$

  * •

If $\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=\infty$ and $\nu$ and $c$
are negatively associated under $\lambda$, then
$\lim_{\rho\rightarrow\infty}y^{*}=0.$

The condition that $\nu$ have infinite expectation ensures that the optimal
mechanism under participation constraints generates positive welfare even for
large $\rho.$ It is not a particularly restrictive assumption given that $\nu$
is a ratio of usage benefits to costs. It is satisfied, for instance, if
$\liminf_{\varepsilon\rightarrow 0}\Pr_{\lambda}(c<\varepsilon)/\varepsilon>0$
and usage benefits are bounded away from zero. The assumption is also
compatible with both thin and thick right tails of the valuation distribution.
For instance, if $\Pr_{\lambda}(\nu>v)\sim 1/(v\cdot(\log v)^{\alpha})$ for
large $v$ for some $\alpha\geq 1$, then $\mathbb{E}_{\lambda}[\nu]=\infty$
while $\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=0$. On the other hand,
if $\Pr_{\lambda}(\nu>v)\sim 1/v^{\alpha}$ for large $v$ for some
$\alpha\in(0,1)$, then $\mathbb{E}_{\lambda}[\nu]=\infty$ while
$\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=\infty$.

When types are ordered, the right tail conditions on $\nu$ can be recast in
terms of the density of costs at zero. This is because under ordered types,
valuations are high when $\theta$ is large, which is also when costs are low.
As a result, a thick right tail is equivalent to an unbounded cost density
near zero, while conversely a thin right tail is equivalent to a vanishing
cost density.

######  Proposition 4.

Under the assumptions of Proposition 3, suppose additionally that types are
ordered and $\limsup_{\theta\rightarrow 0}u(\theta)<\infty$ while
$\liminf_{\theta\rightarrow 0}u(\theta)>0.$

  * •

If $\lim_{\varepsilon\rightarrow 0}Pr_{\lambda}(c<\varepsilon)/\varepsilon=0$,
then $\lim_{\rho\rightarrow\infty}y^{*}=\infty.$

  * •

If $\lim_{\varepsilon\rightarrow
0}\Pr_{\lambda}(c<\varepsilon)/\varepsilon=\infty$, then
$\lim_{\rho\rightarrow\infty}y^{*}=0.$

The machine’s uptime is a function both of the breakage rate and of aggregate
contribution levels. As discussed in our analysis of the first-best mechanism,
aggregate contributions need not shrink with $\rho$. Nonetheless, it turns out
that contribution levels never grow fast enough to outweigh the higher
breakage rate, and the machine’s uptime decreases in $\rho.$

######  Proposition 5.

$Q^{*}$ is nonincreasing in $\rho$.

While the assertion is intuitive, we are not aware of any standard results
regarding comparative statics of saddle points which directly imply it. The
difficulty arises from the fact that the function $\ell$ of which
$(Q^{*},y^{*})$ is a saddle point is neither sub- nor supermodular in
$(Q,y,\rho)$. To prove the result, we identify an appropriate modification of
$\ell$ which is submodular and apply standard results to that function.

##  5 Incentive-compatible mechanisms

We now solve for an optimal mechanism when the designer must induce agents not
just to participate, but also to truthfully report their preferences.
Formally, we impose the participation constraints (2.2) as well as the IC
constraints (2.2) for all $\theta,\theta^{\prime}\in\Theta.$ We refer to a
mechanism which satisfies both sets of constraints as a _screening_ mechanism.

When agents’ types are observed, there is no benefit to restricting any
agent’s access to the machine. However, when agents must self-report their
contribution costs, access restrictions become crucial for screening. The
usage levels $R$ must therefore be designed in tandem with the contribution
levels $P$.

The following result characterizes the main qualitative features of an optimal
screening mechanism.

######  Theorem 2.

There exists an optimal screening mechanism $(R^{*},P^{*},Q^{*})$ which
satisfies

$\left(R^{*}(\theta),P^{*}(\theta)\right)=\begin{cases}(Q^{*},1-Q^{*}),&\text{
if }\bar{\nu}\leq\nu(\theta)\\\ (\hat{R},\hat{P}),&\text{ if
}\underline{\nu}\leq\nu(\theta)<\bar{\nu}\\\ (0,0),&\text{ if
}\nu(\theta)<\underline{\nu}\end{cases}$

for some $0<\underline{\nu}\leq\bar{\nu}\leq\infty$ and $0<\hat{R}\leq Q^{*}$
and $0<\hat{P}\leq 1-Q^{*}.$ Moreover, if $\bar{\nu}=\infty$ then
$\hat{R}=Q^{*}$.

In words, the designer screens agents by offering up to two distinct
membership tiers: a full-access tier with high contribution requirements, and
potentially also a partial-access tier with reduced contributions. Whenever
multiple membership tiers are optimal, the high tier demands the maximum
contribution from all members in that tier. Finally, all agents have the
ability to opt out of the group and receive the $(0,0)$ allocation. Unlike the
case of visible preferences, in general some agents do opt out of the group
under an optimal screening mechanism.

The proof of this result relies on a reduction of the mechanism design problem
to a Myersonian monopoly-sale problem. In this reduction, buyers have
quasilinear utility with valuations $\nu(\theta)$ for the good. The quantity
$R(\theta)$ becomes the probability with which a buyer of type $\theta$
receives the good while $P(\theta)$ is the price he pays for it. The seller’s
objective is a weighted average of revenue (reflecting a Lagrange multiplier
on the balance condition) and the utility of each buyer type. Unlike a classic
monopoly sale problem, the simplex bound $P(\theta)\leq 1-Q$ imposes an upper
bound on the price that each buyer can pay for the good. As a result, a
posted-price mechanism may not be optimal and fractional allocations can be
beneficial for screening buyers.

We show that an optimal allocation rule corresponds to an extreme point in the
set distribution functions which satisfy a moment inequality equivalent to the
budget constraint. In general, extreme points may involve one additional point
of support for each moment inequality, implying our result. This result is
analogous to the finding of [12], who show that in an information design
context, each additional constraint adds up to one additional point of support
in the set of posteriors induced by an optimal mechanism. See also [13], who
apply this logic to characterize optimal redistributionary mechanisms.

Theorem 2 ensures that no more than two membership tiers are required at the
optimum. The following example exhibits a setting in which exactly two tiers
are required.

######  Example.

Suppose that $\Theta=\\{L,M,H\\}$, with equal probability of each type. All
types have contribution cost $c(\theta)=1$, while usage utilities are
$u(H)=5,u(M)=1,u(L)=0.1$. The breakage rate is $\rho=1$.

Under the first-best mechanism, $Q^{\mathrm{fb}}=0.5$, and all types fully
contribute, so that $(R^{\mathrm{fb}}(\theta),P^{\mathrm{fb}}(\theta))=0.5$
for all types.

Under the optimal screening mechanism, $Q^{*}=0.3$. Type $H$ receives full
access in return for a full contribution, type $M$ receives partial access in
return for a reduced contribution, and type $L$ leaves the group. The optimal
allocations are $R^{*}(H)=0.3,R^{*}(M)=0.2,R^{*}(L)=0$ and
$P^{*}(H)=0.7,P^{*}(M)=0.2,P^{*}(L)=0$.

##  6 Model interpretation: Fluid interaction with long-lived agents

In this section, we show how our reduced-form model can be interpreted as a
club comprised of a large population of long-lived agents, who use and
contribute to the machine in a fluid manner. We describe this interpretation
in detail and derive the reduced-form physical constraints from it in Section
6.1. We then apply this interpretation to the design of crowdsourced
recommendation platforms in Section 6.2.

###  6.1 Microfounded model

The group is comprised of a mass of atomistic (i.e., infinitesimal), long-
lived agents. Agents live for a random period of time drawn from a (type-
dependent) distribution $F(\cdot\mid\theta)$ with expectation $1/\kappa$ for
each type. (For simplicity, we assume that $\kappa$ is the same for all
types.) Deaths are balanced by an inflow of new agents at rate $\kappa.$ We
assume that the population of agents is in steady state, so that the empirical
distribution of agent ages $G$ is time-invariant and given by
$G(z\mid\theta)=\kappa\int_{0}^{z}(1-F(\tau\mid\theta))\,d\tau$. Agents types
are drawn from the distribution $\lambda$. Because all types have the same
expected lifespan, $\lambda$ is also the empirical distribution of agents
types in steady state.

At each moment when the machine is working, each agent can use its services,
enjoying a flow benefit $u(\theta)$ from (full) access. At each moment when
the machine is broken, each agent can contribute to fixing it, incurring a
flow cost $c(\theta)$ from (fully) contributing. Agents evaluate the payoff of
participating in the mechanism according to the expected cumulative usage
benefits minus contribution costs over their lifespan.

When the machine breaks, a random _contribution quantum_ (i.e., a cumulative
contribution aggregated across agents and time) is required to fix it. The
size of this quantum is drawn from a fixed distribution with expectation
normalized to 1, independent of the machine’s history. When the machine is
fixed, it breaks after a random _lifespan_ drawn from a fixed distribution
with expectation $1/\rho$, independent of the machine’s history.

A mechanism assigns personalized (type- and age-dependent) usage and
contribution levels based on the current machine state as well as potentially
the history of the system. We restrict attention to _admissible_ mechanisms
that induce a stationary environment for agents born at different calendar
times. Formally, an admissible mechanism must be compatible with a stationary
_system process_ $X_{t}=(\omega_{t},r_{t},p_{t}),$ where:

  * •

$\omega_{t}\in\\{W,B\\}$ is the state of the machine at time $t$

  * •

$r_{t}:\Theta\times\mathbf{R}_{+}\to[0,1]$ records the time-$t$ usage level
$r_{t}(\theta,z)$ of each agent of type $\theta$ and age $z$

  * •

$p_{t}:\Theta\times\mathbf{R}_{+}\to[0,1]$ records the time-$t$ contribution
level $p_{t}(\theta,z)$ of each agent

Note that the information in $X$ is sufficient to derive the entire history of
the system, including the lifespans of the machine (using the transition times
of $\omega$ from W to B) and the contribution quanta (using the transition
times of $\omega$ from B to W plus the contribution levels $r$). Let
$\bar{r}_{t}(\theta)=\int r_{t}(\theta,z)\,dG(z\mid\theta)$ and
$\bar{p}_{t}(\theta)=\int p_{t}(\theta,z)\,dG(z\mid\theta)$ be the group-
average usage and contribution levels for each type.

The simplest admissible mechanisms are the _Markovian_ mechanisms, which
condition current usage and contribution levels only on the current state of
the machine. Formally, a Markovian mechanism is characterized by a Borel
function $\sigma:\Theta\times\\{W,B\\}\to[0,1]$, with the interpretation that
a customer of type $\theta$ is assigned usage level $\sigma(\theta,W)$ when
the machine is working and contribution level $\sigma(\theta,B)$ when the
machine is broken.

More complex admissible mechanisms exist, for instance which vary an agent’s
access and contribution with their age or the amount of time the machine has
been broken. However, this added richness will turn out to be of no value to
the designer. As a result, we need not explicitly describe general mechanisms
or the space of system processes they induce. Instead, we merely identify a
set of necessary conditions on stationary distributions compatible with some
admissible mechanism. We then show that any distribution satisfying these
conditions is payoff-equivalent to one compatible with a Markovian mechanism.

######  Definition 2.

A stationary system process is _admissible_ if:

  1. 1.

Let $L_{1},L_{2},\dots$ be the lifespans of the machine after time $0$. Then
$L_{1},L_{2},\dots$ are i.i.d. with the lifespan distribution of expectation
$1/\rho$.

  2. 2.

Let $M_{1},M_{2},\dots$ be the contribution quanta of the machine after time
$0$. Then $M_{1},M_{2},\dots$ are i.i.d. with expectation $1$.

  3. 3.

$r_{t}(\theta)\leq\mathbf{1}_{[\omega_{t}=W]}$ and
$p_{t}(\theta)\leq\mathbf{1}_{[\omega_{t}=B]}$ for all $t$.

The first two requirements of admissibility ensure that the process respects
the independence of successive lifespans and cumulative contributions. The
final one ensures that the machine is used only when it is working and
contributions are collected only when the machine is broken.

Given any stationary system process, the associated _reduced form_ $(R,P,Q)$
is well-defined, where
$R(\theta)=\mathbb{E}\bar{r}_{t}(\theta),P(\theta)=\mathbb{E}\bar{p}_{t}(\theta),Q=\Pr(\omega_{t}=W)$
and each of these expressions is independent of $t$ by stationarity. The
normalized expected discounted payoff for an agent of type $\theta$ born at
time $t$ can be written in terms of this reduced form as

$\kappa\cdot\mathbb{E}\int_{0}^{\infty}\int_{0}^{\tau}\Big{(}r_{t+z}(\theta,z)\cdot
u(\theta)-p_{t+z}(\theta,z)\cdot
c(\theta)\Big{)}\,\mathrm{d}z\,\mathrm{d}F(\tau\mid\theta)=R(\theta)\cdot
u(\theta)-P(\theta)\cdot c(\theta),$

as in (1). By the ergodic theorem, the reduced form also represents the
deterministic long-run outcomes of the process:

$R(\theta)=\lim_{T\rightarrow\infty}\frac{1}{2T}\int_{-T}^{T}\bar{r}_{t}(\theta)\,dt,\quad
P(\theta)=\lim_{T\rightarrow\infty}\frac{1}{2T}\int_{-T}^{T}\bar{p}_{t}(\theta)\,dt,\quad
Q=\lim_{T\rightarrow\infty}\frac{1}{2T}\int_{-T}^{T}\mathbf{1}_{[\omega_{t}=G]}\,dt$

It follows that utilitarian welfare (2) equals the long-run average flow
payoffs of group members.

The following result establishes that every reduced form of an admissible
system process satisfies the physical constraints. Furthermore, all triples
$(R,P,Q)$ satisfying the physical constraints can be achieved via a Markovian
mechanism. In particular, the physical constraints are necessary and
sufficient for feasibility of an allocation.

######  Proposition 6.

  1. 1.

Fix an admissible system process. Then its reduced form satisfies the physical
constraints.

  2. 2.

Suppose that the triple $(R,P,Q)$ satisfies the physical constraints. Then
there exists a Markovian mechanism $\sigma$ and a stationary system process
$X$ such that $\sigma$ is compatible with $X$ and $(R,P,Q)$ is the reduced
form of $X$.

###  6.2 Application: Crowdsourced recommendation platforms

The fluid interpretation of our model can be applied as a stylized model of
digital content platforms such as Netflix and Tiktok, which rely on user
feedback to make content recommendations.

In this application, the agents in the model are users of the platform, while
the machine is a recommendation algorithm which makes personalized content
suggestions to users. The machine is working when it is well-informed about
the attributes of its current content library, for instance each Netflix
movie’s overall quality as well as its fit for particular user demographics.
The machine breaks when the library of available content turns over, for
instance because Netflix loses the rights to previously-available shows and
movies and licenses a new batch.

The machine is fixed by showing new content to users and eliciting feedback on
their experiences. Feedback is costly for users to give for two reasons.
First, users do not enjoy untested content on average, for instance because
match value is an important component of the user experience. Second, users
find it costly to explicitly report their experiences through ratings or more
detailed surveys.

This application can be formally mapped onto our abstract model in the
following way. Uncertainty about the available content on a recommendation
platform is summarized by a state $\omega\in\Omega$ pertaining to a content
library $X.$ Each user receives a flow payoff $v(\theta,x,\omega)$ from
consuming content $x\in X$ from the library when the library’s state is
$\omega.$ When $\omega$ is known, the algorithm recommends
$x^{*}(\theta,\omega)\in\operatorname*{arg\,max}_{x\in X}v(\theta,x,\omega),$
generating a usage benefit $u(\theta)=v(\theta,x^{*}(\theta,\omega),\omega)$
for each user. Since consumers may consume content repeatedly over time, a
choice $x$ from the content library should be interpreted as a bundle of
individual pieces of content.

When the machine breaks, $\omega$ is drawn anew from some known distribution
$\mu^{\omega}$. (For notational simplicity, the set $X$ of content is held
fixed, with the understanding that elements of $X$ are merely labels that
carry no informational content.) A mass of content of random size must be
consumed by users before $\omega$ is revealed, at which point the algorithm
can once again make informed recommendations.

While the algorithm is learning $\omega,$ users are served content from the
library according to some (potentially type-dependent) distribution
$\mu^{x}(\theta)$. Hence in the learning regime, users receive a usage benefit
$v^{0}(\theta)=\mathbb{E}_{\omega,x}(v(\theta,x,\omega)\mid\theta)$. We assume
that $v^{0}(\theta)<0$ to capture the costs of consuming poorly-targeted
content. Direct costs of providing feedback are captured by an additional flow
cost $c^{0}\geq 0$ of providing ratings. Each user’s net cost of contributing
is $c(\theta)=c^{0}-v^{0}(\theta)>0.$

A user’s commitment to provide feedback in return for access could be
implemented in several ways. The platform could bundle tested and untested
content together in its recommendations, preventing a user who accepts the
platform’s recommendations from using the algorithm without simultaneously
contributing. The platform could additionally prompt the user to periodically
provide ratings in a way which is difficult to skip.

##  7 Model interpretation: Sequential interaction with short-lived agents

In this section, we show how our model can be interpreted as a sequence of
one-shot interactions by a population of short-lived agents, who use and
contribute to the machine exactly once. We describe this interpretation in
detail and derive the reduced-form constraints from it in Section 7.1. We then
apply this interpretation to the design of incentive-aware bandit exploration
models in Section 7.2.

###  7.1 Microfounded model

Short-lived agents arrive according to a Poisson process with rate normalized
to $1$. Arriving agents’ types are drawn i.i.d. from the distribution
$\lambda$. An arriving agent can use the machine if it is working and can
contribute to fix the machine if it is broken, after which he departs forever.
Using a working machine gives an agent of type $\theta$ usage benefit
$u(\theta),$ while contributing to fix a broken machine incurs a cost
$c(\theta).$ A contribution fixes the machine with a probability we normalize
to 1.

As in our fluid interpretation (section 6), we focus on mechanisms which are
compatible with a stationary system process. In a sequential arrival
environment, the system process tracks agent arrivals, their types, the
actions they took, and the state of the machine. Of particular interest will
be Markovian mechanisms, which stochastically direct arriving agents to use or
fix the machine with probabilities that depend only on their type and the
current state of the machine, with independent randomizations across agents.

As in our analysis of the fluid interpretation, we explicitly impose only a
few necessary conditions on admissible system processes. These conditions will
imply the physical constraints and ensure implementability using Markovian
mechanisms.

######  Definition 3.

A system process is _admissible_ if:

  1. 1.

Let $N(t)$ be the number of customers arriving in the interval $[0,t]$. Then
$N(t)$, conditioned on the history of the system process before time $0$,
$N(t)$ follows a Poisson process with arrival rate $1$ and arriving customers
types are i.i.d. with distribution $\lambda$.

  2. 2.

Let $L_{1},L_{2},\dots$ be the lifespans of the machine after time $0$. Then
$L_{1},L_{2},\dots$ are i.i.d. with expectation $1/\rho$.

  3. 3.

Arriving agents use the machine only when it is working and contribute only
when it is broken.

The first requirement ensures ensures that the agent arrival process is
exogenous, and in particular that it is independent of the machine state. This
assumption can also be viewed as a nonanticipation constraint on the designer,
who does not know the future arrival process when deciding whether to send a
customer to the machine. The second requirement ensures that the system
process encodes the physical breakage process described above. The final
requirement ensures that agents can use and fix the machine only when it is
working or broken, respectively.

Every stationary system process induces a well-defined reduced form $(R,P,Q),$
where:

  * •

$Q$ is the long-run proportion of time that the machine is working.
Equivalently, it is the probability that the machine is working at any given
time.

  * •

$P:\Theta\to[0,1]$ is the long-run density of machine usage. That is, for
every Borel set $B\subset\Theta$, the long-run frequency of agents who are of
types $\theta$ and use the machine is $\int_{B}P~{}\mathrm{d}\lambda$.
Equivalently, the probability that an arriving agent has a type drawn from $B$
and uses the machine is $\int_{B}P~{}\mathrm{d}\lambda$.

  * •

$R:\Theta\to[0,1]$ is the long-run density of contributions. That is, for
every Borel set $B\subset\Theta$, the long-run frequency of agents who are of
types $\theta$ and contribute is $\int_{B}R~{}\mathrm{d}\lambda$.
Equivalently, the probability that an arriving agent has a type drawn from $B$
and contributes is $\int_{B}P~{}\mathrm{d}\lambda$.

Given these definitions, it is immediate that the expected payoff for an agent
of type $\theta$ who is born at type $t$ can be written in terms of this
reduced form as in (1), and that the long-run expected welfare of an arriving
agent is as in (2).

The following result is an analog of Proposition 6 for the sequential arrival
environment. It establishes that every admissible system process induces a
reduced-form satisfying the physical constraints. Further, all triples
$(R,P,Q)$ satisfying the physical constraints can be achieved via some
Markovian mechanism. As a result, the physical constraints are necessary and
sufficient for feasibility of an allocation.

######  Proposition 7.

  1. 1.

Fix a stationary process that satisfies Assumption 3. The reduced form
$(R,P,Q)$ induced by this process satisfy (B) and (S-$\theta$) for all
$\theta\in\Theta.$

  2. 2.

Suppose that the triple $(R,P,Q)$ satisfies (B) and (S-$\theta$) for all
$\theta\in\Theta.$ Then there exists a Markovian mechanism that induces the
reduced-form $(R,P,Q)$.

###  7.2 Connection to incentivized bandit exploration

The sequential interpretation described in Section 7.1 can be used to build a
bridge between our reduced-form setting and models of bandit exploration, for
instance [22] (hereafter KMP). To complete the bridge, we supplement the
interpretation with a microfoundation of payoffs and state transitions.

The machine is a bandit arm, which each arriving agent can choose to pull or
not. The payoff to pulling the arm is controlled by a state variable
$\omega\in\Omega,$ which renews at random times following a Poisson process
with rate $\rho$. When renewal occurs, a new state is drawn from a probability
distribution $\pi$ over states, independent of the history of the system. The
designer does not directly observe the state process. However, whenever an
agent pulls the arm, its current state is revealed to the designer.
Additionally, the designer observes renewal times.

An agent of type $\theta$ who pulls the arm in state $\omega\in\Omega$ obtains
a type- and state-dependent payoff $v(\omega,\theta)$, where $v\in
L^{1}(\pi\times\lambda)$. If the agent does not pull the arm, he receives a
payoff of 0. Let $u,c:\Theta\to\mathbf{R}$ be given by

$u(\theta)=\int\left(v(\omega,\theta)\right)^{+}\,\pi(\mathrm{d}\omega),\quad
c(\theta)=-\int v(\omega,\theta)\,\pi(\mathrm{d}\omega).$

The quantity $u(\theta)$ is the agent’s ex-interim payoff from observing the
arm’s state and making an optimal decision to pull it or not. Meanwhile, the
quantity $-c(\theta)$ is the agent’s ex-interim payoff from pulling the arm
when its state is unknown.

With this microfoundation, upkeep of the machine takes the form of periodic
exploration of the bandit arm to learn its state. The machine is working when
the arm’s state is known, in which case an agent of type $\theta$ can achieve
payoff $u(\theta)$ by making an optimal state-contingent decision about
whether to pull the arm. The machine breaks when the state of the arm renews.
When the machine is broken, some agent must make a costly contribution by
pulling the arm to learn its state.

In this interpretation, agents cannot distinguish between usage and
contribution, since both involve pulling the arm. As a result, the ex-interim
participation constraint of our reduced-form setting is equivalent to an ex-
post obedience requirement that each agent must prefer to obey a
recommendation by the designer to pull the arm. This setting can therefore be
viewed as an infinite-horizon variant of KMP, with the key distinctions that
the arm’s state renews periodically and agents may have heterogeneous
preferences.

KMP observe that when homogeneous agents do not know their order of arrival in
a finite-horizon model, obedience constraints are slack for a utilitarian
designer. In our setting, agents arrive in steady state and calendar time is
uninformative about the state of the arm and the designer’s knowledge. A
similar conclusion therefore obtains: The first-best outcome is achievable
when agents are homogeneous. However, when agents have heterogeneous
preferences, incentive constraints may bind for some agents. Our results
indicate how the informativeness of recommendations to different agents should
be adjusted to restore obedience.

##  8 Proofs

###  8.1 Proof of Proposition 1

We first observe that the designer’s problem is equivalent to the relaxed
problem in which the balance condition is enforced as the inequality
constraint

$\rho\cdot Q\leq\int P\,\mathrm{d}\lambda.$

Indeed, any mechanism which satisfies this inequality strictly can be improved
by lowering $P(\theta)$ for a positive measure of types without violating the
simplex bounds or the relaxed balance condition. Hence any optimum of the
relaxed problem satisfies the balance condition as an equality. For the
remaining of the proof, we pass to the relaxed problem.

Let $C^{S}$ be the set of all $(P,Q)$ that satisfy the simplex bounds. For
each $Q,$ let $\bar{C}^{S}(Q)=\\{P\ :\ (P,Q)\in C^{S}\\}.$ Consider the
Lagrangian relaxation of the designer’s problem with respect to the balance
condition. Let $y$ be the dual variable. The Lagrangian is given by (5) with
the domain $C^{S}\times\mathbf{R}_{+}$. The problem

$\text{maximize}_{P\in\bar{C}^{S}(Q)}\mathscr{L}(Q,P;y)$

factorizes over types and has the solution
$P(\theta)=(1-Q)\cdot\mathbf{1}_{[c(\theta)<y]}$. Let

$\ell^{\mathrm{fb}}(Q;y)=\max_{P\in\bar{C}^{S}(Q)}\mathscr{L}(Q,P;y)=Q\cdot(\bar{u}-\rho\cdot
y)+(1-Q)\int(c-y)^{+}~{}\mathrm{d}\lambda$

be the reduced Lagrangian with domain $[0,1]\times\mathbf{R}_{+}$. Since the
domain $Q\in[0,1]$ is compact, it follows from Sion’s minimax theorem that the
primal problem admits an optimal solution and strong duality holds. The dual
Lagrange function is given by

$\varphi^{\mathrm{fb}}(y)=\max_{Q\in[0,1]}\ell^{\mathrm{fb}}(Q;y)=\max\left(\bar{u}-\rho\cdot
y,\int(y-c(\theta))^{+}\lambda(\mathrm{d}\theta)\right).$ (7)

Since the function $y\mapsto\bar{u}-\rho\cdot y$ is decreasing while the
function $y\mapsto\int(y-c)^{+}\,\mathrm{d}\lambda$ is nondecreasing, the dual
problem $\min_{y\geq 0}\varphi^{\mathrm{fb}}(y)$ attains its optimum at
$y^{\mathrm{fb}}$, and its value is $W^{\mathrm{fb}}$ as stated. Finally, the
balance condition implies (4).

###  8.2 Proof of Theorem 1

As in the proof of Proposition 1, we pass to the relaxed problem in which the
balance condition is enforced as an inequality. Let $C^{SP}$ be the set of all
$(P,Q)$ that satisfy the simplex bounds and participation constraints
(SP-$\theta$). For each $Q,$ let $\bar{C}^{SP}(Q)=\\{P\ :\ (P,Q)\in
C^{SP}\\}.$ Consider the Lagrangian relaxation of the designer’s problem with
respect to the balance constraint. Let $y$ be the dual variable. The
Lagrangian is given by (5) with domain restricted to $(P,Q)\in C^{SP}$.

For every $(Q,y)$, the problem

$\text{maximize}_{P\in\bar{C}^{SP}(Q)}\mathscr{L}(Q,P;y)$

factorizes over types and has the solution
$\pi(\theta;Q,y)=\min(1-Q,Q\cdot\nu(\theta))\cdot\mathbf{1}_{[\theta>y]}$. The
function $\ell(Q,y)$ in the theorem statement is therefore the reduced
Lagrangian:

$\ell(Q;y)=\max_{P\in\bar{C}^{SP}(Q)}\mathscr{L}(Q,P;y).$

Since the domain $Q\in[0,1]$ is compact, Sion’s minimax theorem implies that
strong duality holds, the primal problem

$\max_{Q\in[0,1]}\min_{y\geq 0}\ell(Q;y)$

admits an optimum, and the optimal value is given by $W^{*}$, as stated. If,
further, the dual problem admits a (finite) solution $y^{\ast}$, then strong
duality ensures that the mechanism $(P^{*},Q^{*})$ with
$P^{*}(\theta)=\pi(\theta;Q^{*},y^{*})$ solves the designer’s problem.

Suppose instead that the dual problem admits no optimum, i.e., $y^{*}=\infty$.
We claim that $\rho\cdot
Q\geq\int_{\theta}\min(1-Q,Q\cdot\nu(\theta))\,\lambda(\mathrm{d}\theta)$ for
every $Q$. Indeed, if there existed some $Q\in[0,1]$ such that $\rho\cdot
Q<\int_{\theta}\min(1-Q,Q\cdot\nu(\theta))\,\lambda(\mathrm{d}\theta)$, then
there would exist a feasible mechanism satisfying Slater’s condition. In that
case, the dual problem would admit an optimum [6, Theorem 3.2.8], a
contradiction. This claim implies that any $(P,Q)\in C^{SP}$ satisfying the
balance condition must satisfy $P(\theta)=\min(1-Q,Q\cdot\nu(\theta))$ for
every $\theta$. Hence $(P^{*},Q^{*})$ with
$P^{*}(\theta)=\pi(\theta;Q^{*},y^{*})=\min(1-Q,Q\cdot\nu(\theta))$ must solve
the designer’s problem.

It remains to prove that $y^{*}\geq y^{\mathrm{fb}}$. If $y^{*}=\infty$ then
this inequality trivially holds as a strict inequality, so suppose that
$y^{*}<\infty.$ Let $\varphi^{\mathrm{fb}}$ and $\varphi^{*}$ be the dual
Lagrange functions of the two problems, with $\varphi^{\mathrm{fb}}$ as
defined in (7) and

$\varphi^{*}(y)=\max_{Q\in[0,1]}\ell(Q;y).$

Then $\varphi^{\mathrm{fb}}(y)=\varphi^{*}(y)$ for every $y\leq
y^{\mathrm{fb}}$, because for $y\leq y^{\mathrm{fb}}$ the maximum in (7) is
achieved by $(P,Q)=(0,1)$, which satisfies the participation constraints.
Therefore, for every $y<y^{\mathrm{fb}}$ we have that

$\varphi^{*}(y)=\varphi^{\mathrm{fb}}(y)>\varphi^{\mathrm{fb}}(y^{\mathrm{fb}})=\varphi^{*}(y^{\mathrm{fb}}),$

where the strict inequality follows from the fact that $\varphi^{\mathrm{fb}}$
is uniquely maximized at $y^{\mathrm{fb}}$. Since $y^{*}$ is the solution to
the dual problem $\min_{y\geq 0}\varphi^{*}(y)$, it follows that $y^{*}\geq
y^{\mathrm{fb}}$ as desired. Finally, if $W^{*}<W^{\mathrm{fb}}$ and
$y^{*}<\infty,$ then
$\varphi^{*}(y^{*})<\varphi^{\mathrm{fb}}(y^{\mathrm{fb}})$. Since
$\varphi^{*}(y^{\mathrm{fb}})=\varphi^{\mathrm{fb}}(y^{\mathrm{fb}})$, this
implies that $y^{\mathrm{fb}}\neq y^{*}$, as desired.

###  8.3 Proof of Proposition 2

Let $(Q^{*},P^{*})$ be the mechanism characterized in Theorem 1, with $y^{*}$
the corresponding solution to the dual problem. Let $\Theta^{*}$ be the set of
types with active participation constraints under this mechanism. By
definition, $\theta\in\Theta^{\ast}$ if and only if
$P^{*}(\theta)=Q^{*}\cdot\nu(\theta).$ If $Q^{*}=0,$ then
$\Theta^{\ast}=\mathbf{R}_{-}$ is an interval. Going forward, we assume that
$Q^{*}>0.$

Theorem 1 implies that $\theta\in\Theta^{*}$ if and only if
$c(\theta)<y^{\ast}$ and $\nu(\theta)\leq(1-Q^{*})/Q^{*}$, i.e.,
$\Theta^{\ast}$ is the intersection of $I_{r}=c^{-1}([0,y^{\ast}))$ and
$I_{l}=\nu^{-1}([0,(1-Q^{*})/Q^{*}])$. Since $c$ and $\nu$ are monotone
functions, $I_{r}$ and $I_{l}$ are both intervals. Therefore, $\Theta^{\ast}$
is itself an interval.

Let $\Theta^{\mathrm{fb}}$ be the set of types that contribute under the
mechanism characterized in Proposition 1. We claim that
$\Theta^{\mathrm{fb}}\cap\Theta^{\ast}\neq\emptyset$. Indeed, in any convex
optimization problem, all inactive constraints may be removed without
affecting the optimality of the solution. But first-best welfare is achievable
in the problem without the participation constraints in
$\Theta^{\mathrm{fb}}$, and so
$\Theta^{\mathrm{fb}}\cap\Theta^{\ast}=\emptyset$ would contradict our
hypothesis.

Recall that $c(\theta)=-\theta$ under ordered types , so that
$\Theta^{\mathrm{fb}}=(\theta^{\mathrm{fb}},0)$ with
$\theta^{\mathrm{fb}}=-y^{\mathrm{fb}}$. We claim that
$\theta^{\mathrm{fb}}\in\Theta^{\ast}$. Indeed, from Theorem 1 we know that
$y^{*}>y^{\mathrm{fb}}$ and therefore $y^{\mathrm{fb}}\in[0,y^{*})$ and
$\theta^{\mathrm{fb}}=-y^{\mathrm{fb}}\in I_{r}$. Meanwhile,
$\Theta^{\mathrm{fb}}\cap\Theta^{\ast}\neq\emptyset$ implies that
$\Theta^{\mathrm{fb}}\cap I_{l}\neq\emptyset$. Since $\Theta^{\mathrm{fb}}$ is
an interval with lower endpoint $\theta^{\mathrm{fb}}$ and $I_{l}$ is a left
half-line, it follows that $\theta^{\mathrm{fb}}\in I_{l}$.

###  8.4 Proof of Proposition 3

Let $(Q^{*},y^{*})$ be as defined in Theorem 1. We first prove that if
$\mathbb{E}_{\lambda}\nu=\infty,$ then $Q^{*}\in(0,1)$ and $y^{*}<\infty,$ so
that in particular
$Q^{*}\in\operatorname*{arg\,max}_{Q\in(0,1)}\ell(Q;y^{*}).$ The balance
condition implies the inequality $Q^{*}/(1-Q^{*})\leq 1/\rho$, so that
necessarily $Q^{*}<1.$ Next, the monotone convergence theorem implies that

$\lim_{Q\downarrow
0}\int\min(\nu(\theta),(1-Q)/Q)\,\lambda(\mathrm{d}\theta)=\mathbb{E}_{\lambda}\nu=\infty.$

Hence for $Q>0$ sufficiently small, the mechanism $(Q,P)$ with
$P(\theta)=\min(1-Q,Q\cdot\nu(\theta))$ lies in $C^{*}$ and satisfies the
balance condition as a strict inequality, verifying Slater’s condition and
therefore (as established in the proof of Theorem 1) implying that
$y^{*}<\infty$.

By construction, this mechanism satisfies participation for all agents and
therefore delivers non-negative aggregate welfare. Lowering $P(\theta)$ for a
positive measure of types until the balance condition holds with equality
therefore yields a feasible mechanism generating positive payoffs for a
positive measure of types, i.e., generating positive aggregate welfare. Since
any feasible mechanism satisfying $Q=0$ yields zero welfare, it must be that
$Q^{*}>0.$

We now establish the claimed limits. Since the reduced Lagrangian $\ell$ is a
concave function of $Q,$ its one-sided derivatives exist everywhere. Its right
derivative may be calculated by writing $\ell$ as

$\displaystyle\ell(Q;y)=\ $ $\displaystyle Q\cdot(\bar{u}-\rho\cdot
y)+Q\cdot\int\nu(\theta)\cdot(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta)$
$\displaystyle+\int\mathbf{1}_{[\nu\geq(1-Q)/Q]}(\theta)\cdot\Big{(}1-(\nu(\theta)+1)\cdot
Q\Big{)}\cdot(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta),$

Since $(1-Q)/Q$ is decreasing and continuous,

$\frac{d}{d_{+}Q}\mathbf{1}_{[\nu\geq(1-Q)/Q]}(\theta)=0$

everywhere, meaning that

$\displaystyle\frac{\partial\ell}{\partial_{+}Q}=\ $
$\displaystyle\bar{u}-\rho\cdot
y+\int\nu(\theta)\cdot(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta)$
$\displaystyle-\int\mathbf{1}_{[\nu\geq(1-Q)/Q]}(\theta)\cdot(\nu(\theta)+1)\cdot(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta).$

Regrouping terms allows this derivative to be equivalently written

$\displaystyle\frac{\partial\ell}{\partial_{+}Q}=\ $
$\displaystyle\bar{u}-\int\mathbf{1}_{[c\leq
y]}(\theta)\cdot\Big{(}\mathbf{1}_{[\nu<(1-Q)/Q]}(\theta)\cdot
u(\theta)-\mathbf{1}_{[\nu\geq(1-Q)/Q]}(\theta)\cdot
c(\theta)\Big{)}\,\lambda(\mathrm{d}\theta)$
$\displaystyle-y\cdot\left(\rho+\text{Pr}_{\lambda}(c\leq
y\land\nu\geq(1-Q)/Q)-\int\mathbf{1}_{[c\leq
y\land\nu<(1-Q)/Q]}(\theta)\cdot\nu(\theta)\,\lambda(\mathrm{d}\theta)\right).$

The optimality condition
$Q^{*}\in\operatorname*{arg\,max}_{Q\in(0,1)}\ell(Q;y^{*})$ implies the one-
sided first-order condition
$\frac{\partial\ell}{\partial_{+}Q}(Q^{*};y^{*})\leq 0.$ Meanwhile, for every
$Q>0$ the balance condition may be rewritten

$\rho=\int\mathbf{1}_{[c\leq
y\land\nu<(1-Q)/Q]}(\theta)\cdot\nu(\theta)\,\lambda(\mathrm{d}\theta)+\frac{1-Q}{Q}\cdot\Pr(c\leq
y\land\nu\geq(1-Q)/Q).$

Since the balance condition is satisfied at $(Q^{*},y^{*})$ and $Q^{*}>0,$ the
first-order condition implies

$\displaystyle\bar{u}-\int\mathbf{1}_{[c\leq
y^{*}]}(\theta)\cdot\Big{(}\mathbf{1}_{[\nu<\nu^{*}]}(\theta)\cdot
u(\theta)-\mathbf{1}_{[\nu\geq\nu^{*}]}(\theta)\cdot
c(\theta)\Big{)}\,\lambda(\mathrm{d}\theta)$ $\displaystyle\leq\ $
$\displaystyle y^{*}\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(c\leq
y^{*}\land\nu\geq\nu^{*}),$

where $\nu^{*}=(1-Q^{*})/Q^{*}.$ Since $c>0,$ this bound in turn implies the
weaker bound

$\int\mathbf{1}_{[c>y^{*}]}(\theta)\cdot
u(\theta)\,\lambda(\mathrm{d}\theta)\leq
y^{*}\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(\nu\geq\nu^{*}).$

Now, suppose that $\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=0.$ Since
$\lim_{\rho\rightarrow\infty}Q^{*}=0,$ it must be that
$\lim_{\rho\rightarrow\infty}\nu^{*}=\infty$ and therefore
$\lim_{\rho\rightarrow\infty}(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(\nu\geq\nu^{*})=0.$
Let $\underline{y}=\liminf_{\rho\rightarrow\infty}y^{*},$ and suppose by way
of contradiction that $\underline{y}<\infty.$ Then

$\liminf_{\rho\rightarrow\infty}y^{*}\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(\nu\geq\nu^{*})=0.$

Meanwhile, viewed as a function of $y$, $\mathbf{1}_{[c>y]}(\theta)$ is an
indicator function on an open set, meaning that it is lower semicontinuous.
Hence

$\liminf_{\rho\rightarrow\infty}\mathbf{1}_{[c>y^{*}]}\geq\mathbf{1}_{[c>\underline{y}]}.$

Fatou’s lemma therefore implies

$\liminf_{\rho\rightarrow\infty}\int\mathbf{1}_{[c>y^{*}]}(\theta)\cdot
u(\theta)\,\lambda(\mathrm{d}\theta)\geq\int\mathbf{1}_{[c>\underline{y}]}(\theta)\cdot
u(\theta)\,\lambda(\mathrm{d}\theta)$

Since $c$ has full support on $\mathbf{R}_{+},$ the latter integral must be
positive when $\underline{y}<\infty,$ a contradiction.

Meanwhile, the left derivative of $\ell$ may be calculated by writing the
reduced Lagrangian as

$\displaystyle\ell(Q;y)=\ $ $\displaystyle Q\cdot(\bar{u}-\rho\cdot
y)+\int\mathbf{1}_{[\nu\leq(1-Q)/Q]}(\theta)\cdot\Big{(}(\nu(\theta)+1)\cdot
Q-1\Big{)}\cdot(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta)$
$\displaystyle+(1-Q)\int(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta).$

Since $(1-Q)/Q$ is continuous and decreasing,

$\frac{d}{d_{-}Q}\mathbf{1}_{[\nu\leq(1-Q)/Q]}(\theta)=0$

everywhere, meaning that

$\displaystyle\frac{\partial\ell}{\partial_{-}Q}=\ $
$\displaystyle\bar{u}-\rho\cdot
y+\int\mathbf{1}_{[\nu\leq(1-Q)/Q]}(\theta)\cdot(\nu(\theta)+1)\cdot(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta)$
$\displaystyle-\int(y-c(\theta))^{+}\,\lambda(\mathrm{d}\theta).$

This derivative may be equivalently written

$\displaystyle\frac{\partial\ell}{\partial_{-}Q}=\ $
$\displaystyle\bar{u}-\int\mathbf{1}_{[c<y]}(\theta)\cdot\Big{(}\mathbf{1}_{[\nu\leq(1-Q)/Q]}(\theta)\cdot
u(\theta)-\mathbf{1}_{[\nu>(1-Q)/Q]}(\theta)\cdot
c(\theta)\Big{)}\,\lambda(\mathrm{d}\theta)$
$\displaystyle-y\cdot\left(\rho+\text{Pr}_{\lambda}(c<y\land\nu>(1-Q)/Q)-\int\mathbf{1}_{[c<y\land\nu\leq(1-Q)/Q]}\cdot\nu(\theta)\,\lambda(\mathrm{d}\theta)\right).$

The optimality condition
$Q^{*}\in\operatorname*{arg\,max}_{Q\in(0,1)}\ell(Q;y^{*})$ implies the one-
sided first-order condition
$\frac{\partial\ell}{\partial_{-}Q}(Q^{*};y^{*})\geq 0.$ Meanwhile, for every
$Q>0$ the balance condition may be rewritten

$\rho=\int\mathbf{1}_{[c<y\land\nu\leq(1-Q)/Q]}\cdot\nu(\theta)\,\lambda(\mathrm{d}\theta)+\frac{1-Q}{Q}\cdot\Pr(c<y\land\nu>(1-Q)/Q).$

Since the balance condition is satisfied at $(Q^{*},y^{*})$ and $Q^{*}>0,$ the
first-order condition implies

$\displaystyle\bar{u}-\int\mathbf{1}_{[c<y^{*}]}(\theta)\cdot\Big{(}\mathbf{1}_{[\nu\leq\nu^{*}]}(\theta)\cdot
u(\theta)-\mathbf{1}_{[\nu>\nu^{*}]}(\theta)\cdot
c(\theta)\Big{)}\,\lambda(\mathrm{d}\theta)$ $\displaystyle\geq\ $
$\displaystyle
y^{*}\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(c<y^{*}\land\nu>\nu^{*}).$

Let $\bar{c}=\int c\,\mathrm{d}\lambda.$ Then the left-hand side of this
inequality is in turn bounded above by $\bar{u}+\bar{c},$ so that

$\bar{u}+\bar{c}\geq
y^{*}\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(c<y^{*}\land\nu>\nu^{*}).$

Note that $\bar{u}+\bar{c}$ is independent of $Q^{*}$, $y^{*}$, and $\rho.$

Now, suppose that $\nu$ and $c$ are negatively associated under $\lambda$ and
$\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=\infty$. The first condition
implies the inequality

$\text{Pr}_{\lambda}(c<y^{*}\land\nu>\nu^{*})\geq\text{Pr}_{\lambda}(c<y^{*})\cdot\text{Pr}_{\lambda}(\nu>\nu^{*}),$

yielding the bound

$\bar{u}+\bar{c}\geq
y^{*}\cdot\text{Pr}_{\lambda}(c<y^{*})\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(\nu>\nu^{*}).$

Since $\lim_{\rho\rightarrow\infty}Q^{*}=0,$ it must be that
$\lim_{\rho\rightarrow\infty}\nu^{*}=\infty.$ Hence
$\lim_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)=\infty$ implies that
$\lim_{\rho\rightarrow\infty}(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(\nu>\nu^{*})=\infty.$
Suppose by way of contradiction that $\limsup_{\rho\rightarrow\infty}y^{*}>0.$
Since $c$ has full support on $\mathbf{R}_{+},$ the expression
$y\cdot\Pr_{\lambda}(c<y)$ is an increasing function of $y$ which is positive
for all $y>0$. Hence
$\limsup_{\rho\rightarrow\infty}y^{*}\cdot\Pr_{\lambda}(c<y^{*})>0.$ It
follows that

$\limsup_{\rho\rightarrow\infty}y^{*}\cdot\text{Pr}_{\lambda}(c<y^{*})\cdot(\nu^{*}+1)\cdot\text{Pr}_{\lambda}(\nu>\nu^{*})=\infty.$

But this limit must also be bounded above by $\bar{u}+\underline{u},$ which is
finite given that $u,c\in\mathscr{L}^{1}(\lambda),$ a contradiction.

###  8.5 Proof of Proposition 4

Let $f=\lim_{\varepsilon\rightarrow
0}Pr_{\lambda}(c<\varepsilon)/\varepsilon$, and assume that this limit exists.
Also let $u_{+}(0)=\limsup_{t\rightarrow 0}u(t)$ and
$u_{-}(0)=\liminf_{t\rightarrow 0}u(t)$.

######  Lemma 1.

If $u_{-}(0)>0$ and $u_{+}(0)<\infty,$ then
$\limsup_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)\leq u_{+}(0)\cdot f$ and
$\liminf_{v\rightarrow\infty}v\Pr_{\lambda}(\nu>v)\geq u_{-}(0)\cdot f$.

###### Proof.

For any $v>0,$ let $\chi(v)=-\inf\\{\theta\ :\ \nu(\theta)>v\\}$, with the
convention that $\chi(v)=0$ if $v\geq\sup_{\Theta}\nu(\theta).$ Note that
$\chi$ is nonincreasing given that $\nu$ is increasing. The assumption
$u_{-}(0)>0$ implies that $\nu(\theta)=-u(\theta)/\theta$ is unbounded above,
hence $\chi(v)\in(0,\infty)$ for sufficiently large $v>0$ and
$\lim_{v\rightarrow\infty}\chi(v)=0$. Going forward, we restrict attention to
$v$ large enough that $\chi(v)<\infty.$

Fix $\varepsilon\in(0,1)$ small enough that $\chi((1-\varepsilon)\cdot
v)<\infty.$ For all $v,$ the bound $c<(1-\varepsilon)\cdot\chi(v)$ implies
that $\nu>v,$ while $\nu>v$ implies that $c<(1+\varepsilon)\cdot\chi(v)$.
Hence

${\textstyle\Pr_{\lambda}(c<(1-\varepsilon)\cdot\chi(v))\leq\Pr_{\lambda}(\nu>v)\leq\Pr_{\lambda}(c<(1+\varepsilon)\cdot\chi(v)).}$

Equivalently,

${\textstyle(1-\varepsilon)\cdot
v\cdot\chi(v)\cdot\frac{\Pr_{\lambda}(c<(1-\varepsilon)\cdot\chi(v))}{(1-\varepsilon)\cdot\chi(v)}\leq
v\cdot\Pr_{\lambda}(\nu>v)\leq(1+\varepsilon)\cdot
v\cdot\chi(v)\cdot\frac{\Pr_{\lambda}(c<(1+\varepsilon)\cdot\chi(v))}{(1+\varepsilon)\cdot\chi(v)}.}$

Now let $v\rightarrow\infty$. Since $\chi$ is nonincreasing in $v$ and
satisfies $\lim_{v\rightarrow\infty}\chi(v)=0,$ we have

$\lim_{v\rightarrow\infty}\frac{\Pr_{\lambda}(c<(1-\varepsilon)\cdot\chi(v))}{(1-\varepsilon)\cdot\chi(v)}=\lim_{v\rightarrow\infty}\frac{\Pr_{\lambda}(c<(1+\varepsilon)\cdot\chi(v))}{(1+\varepsilon)\cdot\chi(v)}=f.$

Meanwhile, $\nu(-(1+\varepsilon)\cdot\chi(v))<v<\nu(-\chi(v)/(1+\varepsilon))$
for all $v,$ and so

$\frac{v\cdot\chi(v)}{1+\varepsilon}>\frac{\nu(-(1+\varepsilon)\cdot\chi(v))\cdot\chi(v)}{1+\varepsilon}=\frac{u(-(1+\varepsilon)\cdot\chi(v))}{(1+\varepsilon)^{2}},$

implying

$\liminf_{v\rightarrow\infty}\frac{v\cdot\chi(v)}{1+\varepsilon}\geq\frac{u_{-}(0)}{(1+\varepsilon)^{2}}.$

Since $u_{-}(0)$ is positive and finite by assumption, it follows that

${\textstyle\liminf_{v\rightarrow\infty}v\cdot\Pr_{\lambda}(\nu>v)\geq\frac{f\cdot
u_{-}(0)}{(1+\varepsilon)^{2}}.}$

A very similar calculation yields the bound

${\textstyle\limsup_{v\rightarrow\infty}v\cdot\Pr_{\lambda}(\nu>v)\leq\frac{f\cdot
u_{-}(0)}{(1-\varepsilon)^{2}}.}$

Since these bounds hold for any $\varepsilon\in(0,1)$, taking
$\varepsilon\rightarrow 0$ yields the claimed bounds. ∎

Combining this result with Proposition 3 immediately implies the desired
result in the first case. As for the second case, recall that under ordered
types, $c$ is decreasing in $\theta$ while $\nu$ is increasing, so that $\nu$
and $c$ are mechanically negatively associated under ordered types.
Proposition 3 therefore also implies the result for the second case.

###  8.6 Proof of Proposition 5

We prove the Proposition using the following lemma, which may be useful in
other situations to establish comparative statics of saddle points.

######  Lemma 2.

Let $X$ be a sublattice of $\mathbf{R}_{+}\times\mathbf{R}\times\mathbf{R}$
and $h:X\to\mathbf{R}$ be submodular and nonincreasing in its final argument.
Then $\operatorname*{arg\,max}_{x}\min_{y}x\cdot h(x,y,z)$ is
nonincreasing555Monotonicity is in the induced set ordering [29, Section
2.4]..

###### Proof.

Let $H(y,z)=\min_{y}h(x,y,z),$ and consider the objective function

${\textstyle g(x,z)=\min_{y}x\cdot h(x,y,z)=x\cdot H(x,z).}$

Since $h$ is submodular, it follows that $H$ is as well [29, Theorem 2.7.6].
Since $H$ is also nonincreasing in $z$, Claim 1 below implies that $g$ is also
submodular. Its maximizers are therefore nonincreasing in $z$.∎

######  Claim 1.

Let $X$ be a sublattice of $\mathbf{R}_{+}\times\mathbf{R}$ and
$f:X\to\mathbf{R}$ be submodular (supermodular) and nonincreasing
(nondecreasing) in its second component. Then $g:X\to\mathbf{R}$ given by
$g(x,y)=x\cdot f(x,y)$ is submodular (supermodular).

###### Proof.

The claim follows from general results about the product of supermodular
functions [29, Lemma 2.6.4], but we provide a simpler direct proof here as an
alternative.

We prove the submodularity case, with supermodularity following from the
submodularity result applied to $-f.$ Let $x<x^{\prime}$. Then

$g(x^{\prime},y)-g(x,y)=(x^{\prime}-x)\cdot
f(x,y)+x\cdot(f(x^{\prime},y)-f(x,y))$

is nonincreasing in $y$ since $f$ is nonincreasing in $y$ and submodular. ∎

To complete the proof of Proposition 5 using Lemma 2, consider the designer’s
primal problem $\max_{Q\in[0,1]}\min_{y\geq 0}\ell(Q;y)$, with
$\ell(Q;y)=Q\cdot h(Q,y,\rho)$ and

$h(Q,y,\rho)=\bar{u}-\rho\cdot
y+\int\min\left((1-Q)/Q,\nu(\theta)\right)(y-c(\theta))^{+}~{}\lambda(\mathrm{d}\theta).$

The function $h$ is submodular, because it is a sum of components which are
each a product of a nonincreasing function in one variable and a nondecreasing
function in another. It is also nonincreasing in $\rho$. Monotonicity of the
solution therefore follows from Lemma 2.

###  8.7 Proof of Theorem 2

As in the proof of Proposition 1, we pass to the relaxed problem in which the
balance condition is enforced as an inequality. Let $C^{\mathrm{IC}}$ be the
set of all $(R,P,Q)$ that satisfy the simplex bounds along with the
participation and IC constraints. For each $Q,$ let
$\bar{C}^{\mathrm{IC}}(Q)=\\{(R,P)\ :\ (R,P,Q)\in C^{\mathrm{IC}}\\}.$

Consider the Lagrangian relaxation of the designer’s problem with respect to
the balance constraint. Let $y$ be the dual variable. The Lagrangian is given
by (5) with domain restricted to $(P,Q)\in C^{SP}$. Let
$\ell^{\mathrm{IC}}(Q,y)$ be the reduced Lagrangian:

$\ell^{\mathrm{IC}}(Q;y)=\max_{(R,P)\in\bar{C}^{\mathrm{IC}}(Q)}\mathscr{L}^{\mathrm{IC}}(R,P,Q;y),$

where

$\displaystyle\mathscr{L}^{\mathrm{IC}}(R,P,Q;y)=\int\left(R(\theta)\cdot\nu(\theta)-P(\theta)\right)\cdot
c(\theta)\,\lambda(\mathrm{d}\theta)+y\cdot\int P\,\mathrm{d}\lambda-\rho\cdot
Q\cdot y.$

Note that the IC constraints may be rewritten

$R(\theta)\cdot\nu(\theta)-P(\theta)\geq
R(\theta^{\prime})\cdot\nu(\theta)-P(\theta^{\prime}).$

These are the familiar IC constraints in a single-good monopoly sale problem
with valuations $\nu(\theta)$, probabilities $R(\theta)$ of receiving the
good, and payments $P(\theta).$ Maximizing $\mathscr{L}^{\mathrm{IC}}$ with
respect to $(R,P)\in\bar{C}^{IC}(Q)$ is therefore equivalent to solving the
monopoly sale problem for a seller who maximizes a weighted sum of buyer
welfare and revenue, under the uniform payment bound $P(Q)\leq 1-Q$. (The
remaining simplex bounds $R(\theta)\leq Q$ can be normalized to yield a
quantity 1 of the good by redefining $\nu$, and so they do not impact the form
of the solution.)

As we show in Appendix A, the optimal mechanism with bounded payments takes
one of two forms. One possibility is a posted price which delivers the good
with the maximum probability, i.e., with $R(Q)=Q$. This case corresponds to
$\bar{\nu}=\infty$ in the theorem statement. The second is a menu with two
options: pay $1-Q^{*}$ and receive the item with the maximum probability $Q$,
or pay $\hat{P}$ and receive the item with some probability $\hat{R}$. This
case corresponds to $\bar{\nu}<\infty$ in the theorem statement.

We next observe that, since $\ell^{\mathrm{IC}}$ is the partially-optimized
Lagrangian of a convex optimization problem, standard arguments imply that it
is a concave-convex function. (Convexity in $y$ follows from the fact that
$\ell^{\mathrm{IC}}$ is the Lagrangian dual of the designer’s problem
enforcing a fixed $Q.$ Concavity in $Q$ follows from the fact that
$\ell^{\mathrm{IC}}$ is the value of the convex maximization problem with
objective $\mathscr{L}^{\mathrm{IC}}$, choice variables $(R,P)$, and parameter
$Q$.) Since the domain $Q\in[0,1]$ is compact, Sion’s minimax theorem
therefore implies that strong duality holds and the primal problem

$\max_{Q\in[0,1]}\min_{y\geq 0}\ell(Q;y)$

admits an optimum $Q^{*}$. If, further, the dual problem

$\min_{y\geq 0}\max_{Q\in[0,1]}\ell(Q;y)$

admits a (finite) optimum $y^{*}$, then strong duality ensures that the
mechanism $(P^{*},R^{*})$ that maximizes $\mathscr{L}(R,P,Q^{*};y^{*})$ solves
the designer’s problem.

Suppose instead that the dual problem admits no optimum. We claim that
$\rho\cdot Q\geq\int P~{}\mathrm{d}\lambda$ for every mechanism in
$C^{\mathrm{IC}}$. Indeed, if there existed some mechanism $(R,P,Q)\in
C^{\mathrm{IC}}$ satisfying $\rho\cdot Q<\int P\,\mathrm{d}\lambda$, then
Slater’s condition would be satisfied and the dual problem would admit an
optimum, a contradiction. Therefore, any mechanism in $C^{IC}$ satisfying the
balance condition also maximizes seller revenue among all mechanisms in
$C^{IC}$. We again appeal to the characterization in Appendix A to conclude
that in this case an optimal mechanism must have the structure stated in the
Theorem.

###  8.8 Proof of Proposition 6

Assume first that the system process is stationary and let $(R,P,Q)$ be its
reduced form. We first derive the balance condition. If $Q=0$, then the
machine is always broken, agents never contribute, and the balance condition
is satisfied. So assume that $Q>0$.

For $T>0$, let $n(T)$ be the number of times the machine breaks down during
the interval time interval $[0,T]$. We prove the balance condition by showing
that

$\rho\cdot Q=\int
P\,\mathrm{d}\lambda=\lim_{T\rightarrow\infty}\frac{n(T)}{T}\quad\text{a.s.}$

Since $Q>0$ it must be that $\lim_{T\rightarrow\infty}n(T)=\infty$ a.s.
Indeed, if $n(T)$ were bounded, then from some point onward the machine would
never be fixed, else it would eventually break again. But then from some later
point onward the machine would remain broken forever, implying $Q=0$, a
contradiction.

Let $L_{0}\geq 0$ be residual lifespan of the machine at time $0$ (so
$L_{0}=0$ if the machine is broken at time $0$), and for $i\geq 1$ let $L_{i}$
be the lifespan of the machine after the $i$-th time it is being fixed after
time $0$. For $T>0,$ let
$W(T)=\int_{0}^{T}\mathbf{1}_{[\omega_{t}=G]}\,\mathrm{d}t$. Then for every
$T>0,$

$L_{1}+\dots+L_{n(T)-1}\leq W(T)\leq L_{0}+L_{1}+\dots+L_{n(T)}.$ (8)

By the strong law of large numbers,
$\lim_{n\rightarrow\infty}n^{-1}\sum_{i=1}^{n}L_{n}=1/\rho$ a.s. Since
$\lim_{T\rightarrow\infty}n(T)=\infty$ a.s., it follows from (8) that
$\lim_{T\rightarrow\infty}W(T)/n(T)=1/\rho$ a.s. Meanwhile,
$\lim_{T\rightarrow\infty}W(T)/T=Q$ a.s. by the definition of $Q.$ Therefore
$\lim_{T\rightarrow\infty}n(T)/T=Q\cdot\rho$ a.s.

Let $M_{0}\geq 0$ be the residual contribution needed to fix the machine at
time $0$ (so $M_{0}=0$ if the machine is working at time $0$), and for $i\geq
1$ let $M_{i}$ be the aggregate contribution needed to fix the machine after
the $i$-th time breakdown subsequent to time $0$. For $T>0,$ let $C(T)$ be the
total amount of contribution in the time interval $[0,T]$. Then for every
$T>0,$

$M_{1}+\dots+M_{n(T)-1}\leq C(T)\leq M_{0}+M_{1}+\dots+M_{n(T)}.$ (9)

By the strong law of large numbers,
$\lim_{n\rightarrow\infty}n^{-1}\sum_{i=1}^{n}M_{n}=1/\rho$ a.s. Since
$\lim_{T\rightarrow\infty}n(T)=\infty$ a.s., it follows from (9) that
$\lim_{T\rightarrow\infty}C(T)/n(T)=1$ a.s. Meanwhile,
$\lim_{T\rightarrow\infty}C(T)/T=\int P~{}\mathrm{d}\lambda$ a.s. by the
definition of $P.$ Therefore $\lim_{T\rightarrow\infty}n(T)/T=\int
P~{}\mathrm{d}\lambda$ a.s.

We now establish the simplex bounds. At every point in time the realized usage
of each agent is bounded by the $1$ if the machine is working and by $0$ if it
is broken. Therefore for the population of agents of each type, expected usage
is bounded by $Q,$ the probability that the machine is working. In other
words, $R(\theta)\leq Q.$ Similarly, the realized contribution of each agent
is bounded by the $0$ if the machine is working and by $1$ if it is broken.
Therefore for the population of agents of each type, expected contributions
are bounded by $1-Q,$ the probability that the machine is broken. In other
words, $P(\theta)\leq 1-Q.$

Assume now that $(R,P,Q)$ satisfies the physical constraints, and consider the
Markovian mechanism given by $\sigma(\theta,W)=R(\theta)/Q$ and
$\sigma(\theta,B)=P(\theta)/(1-Q)$, with the convention that
$\sigma(\theta,W)=0$ if $Q=0$ and $\sigma(\theta,B)=0$ if $Q=1$. The machine
state process under this mechanism is an alternating renewal process: When the
machine becomes working, it remains working for the lifespan with expectation
$\mu_{W}=1/\rho$. When the machine becomes broken, it remains broken for a
random time with expectation
$\mu_{B}=1/\int\sigma(\theta,B)~{}\lambda(\mathrm{d}\theta)$.

The balance condition implies that $Q/(1-Q)=\mu_{W}/\mu_{B},$ which may be
rearranged to find that the long-run proportion of time that the machine is
working is $\frac{\mu_{W}}{\mu_{W}+\mu_{B}}=Q$. The quantity $Q$ must
therefore also be the probability with which the machine is working under the
steady state induced by the mechanism. It then follows from definition of
$\sigma$ that $R(\theta)=Q\cdot\sigma(\theta,W)$ is the expected usage of an
arriving agent of type $\theta$ while $P(\theta)=(1-Q)\cdot\sigma(\theta,B)$
is the expected contribution of an arriving agent of type $\theta$.

###  8.9 Proof of Proposition 7

Assume first that the system process is stationary and let $(R,P,Q)$ be its
reduced form. The proof that $(R,P,Q)$ satisfies the balance condition is very
similar to the proof of Proposition 6 and is omitted. To prove the simplex
bound, note that the non-anticipation assumption in (3) implies the so-called
PASTA (“Poison arrivals see time average”) property, under which the
probability that an arriving agent of type $\theta$ encounters a working
machine equals the steady-state uptime $Q$ [28, Section 2.4]. As a result, the
simplex bounds follow from the fact that the agent cannot use or fix the
machine more often than that action is available.

Assume now that $(R,P,Q)$ satisfies the physical constraints, and consider the
Markovian mechanism given by $\sigma(\theta,W)=R(\theta)/Q$ and
$\sigma(\theta,B)=P(\theta)/(1-Q)$, with the convention that
$\sigma(\theta,W)=0$ if $Q=0$ and $\sigma(\theta,B)=0$ if $Q=1$. The machine
state process under this mechanism is an alternating renewal process with the
same expectations as in the proof of Proposition 7. Therefore, by the same
argument as in that proof the reduced form induced by this mechanism is
$(R,P,Q).$

##  Appendix A Monopoly sale problem with bounded transfers

Consider a generalized version of Myerson’s single-good monopoly sale problem
[26]. Buyers are heterogeneous with types $\theta\in\Theta$. They have
quasilinear payoffs over allocations and payments, with valuations
$\nu:\Theta\to\mathbf{R}_{+}$ for the good. A mechanism is given by an
allocation function $r:\Theta\to[0,1]$ and payment rule
$p:\Theta\to\mathbf{R}_{+}$. (We rule out payments to buyers.) The seller’s
objective is a weighted average of buyer payoffs and payments of the form

$\int\Big{(}r(\theta)\cdot\nu(\theta)-p(\theta)\Big{)}\,\mu_{1}(\mathrm{d}\theta)+\int
p\,\mathrm{d}\mu_{2}$ (10)

for some finite measures $\mu_{1},\mu_{2}$ over $\Theta$.

A mechanism is incentive compatible (IC) if

$r(\theta)\cdot\nu(\theta)-p(\theta)\geq
r(\theta^{\prime})\cdot\nu(\theta)-p(\theta^{\prime})$

for every $\theta,\theta^{\prime}\in\Theta$. It is individually rational (IR)
if $r(\theta)\cdot\nu(\theta)-p(\theta)\geq 0$ for all $\theta\in\Theta$. The
seller chooses a mechanism to maximize (10) subject to IC and IR.

We first observe that, without loss, we may restrict attention to mechanisms
satisfying $(r(\theta),p(\theta))=(r(\theta^{\prime}),p(\theta^{\prime}))$
whenever $\nu(\theta)=\nu(\theta^{\prime}).$ Indeed, under any IC mechanism,
all types with the same valuation receive the same utility. If such a
mechanism does not offer all such types the same bundle, modify it to pool all
types on the bundle involving the highest payment. This modification does not
affect IC or IR and raises the seller’s payoff. Given the restriction to such
mechanisms, we may without loss relabel types so that the type space is the
set of valuations $\mathbf{R}_{+}.$

As usual, the set of IC and IR mechanisms can be identified with the set of
nondecreasing allocation functions. (Because the lowest type has valuation 0
for the good, the utility of the lowest type is not a free parameter in this
environment.) We may further restrict attention to right-continuous allocation
functions. Indeed, if $r(\nu)<r(\nu+)$ for some $\nu,$ then also
$p(\nu)<p(\nu+).$ Additionally, IC implies that the bundle $(r(\nu+),p(\nu+))$
must deliver that type the same utility as $(r(\nu),p(\nu)).$ Replacing that
type’s bundle with $(r(\nu+),p(\nu+))$ therefore preserves IC and IR, delivers
that type the same utility, and raises the seller’s revenue from that type.
Going forward, we assume that $r$ is both nondecreasing and right-continuous.
The payment function and buyer payoffs corresponding to each such allocation
function $r$ are

$\begin{split}&p_{r}(\nu)=\int_{0}^{\nu}v\,\mathrm{d}r(v),\\\
&U_{r}(\nu)=\int_{0}^{\nu}r(v)\,dv.\end{split}$ (11)

Standard theory says that the optimal mechanism is a posted price mechanism of
the form $r=\mathbf{1}_{[\nu_{1},\infty)}$ for some $\nu_{1}\in\mathbf{R}_{+}$
(the price). The following lemma states an analog of this result for the case
that payments are bounded. The proof follows a similar argument as in the
corresponding proof for the case of unbounded payments, as in [5, Section
2.5], with the twist that the set of extreme points of IC mechanisms is more
complicated. We also develop the argument more generally, to allow for atoms
in the type distributions. The argument is not new, but we do not know of a
reference.

######  Proposition 8.

Consider the problem of maximizing objective (10) over all IC and IR
mechanisms such that $0\leq p(\nu)\leq 1$ for every $\nu\in\mathbf{R}_{+}$.
The optimal allocation function is either of the form
$r=\mathbf{1}_{[\nu_{1},\infty)}$ for some $\nu_{1}\leq 1$ or of the form
$r=r_{0}\mathbf{1}_{[\nu_{0},\nu_{1})}+\mathbf{1}_{[\nu_{1},\infty)}$ for some
$0\leq\nu_{0}\leq\nu_{1}$ and some $0\leq r_{0}\leq 1$ such that
$r_{0}\nu_{0}+(1-r_{0})\nu_{1}=1$

The first mechanism in the lemma is the familiar posted price with price
$\nu_{1}$. The second mechanism can be implemented as a menu with two options:
pay $r_{0}\cdot\nu_{0}$ and receive the good with probability $r_{0}$, or pay
$1$ and receive the good for sure.

###### Proof.

The allocation functions $r:\mathbf{R}_{+}\to[0,1]$ of IR and IC mechanisms
with payments bounded by $1$ are nondecreasing and right-continuous, hence
also u.s.c, and satisfy $\int_{0}^{\infty}v~{}\mathrm{d}r(v)\leq 1$. We can
identify each such allocation with a finite measure over $m$ over
$\mathbf{R}_{+}$ such that

$\displaystyle m(\mathbf{R}_{+})\leq 1,\text{ and}$ (12)
$\displaystyle\int\nu~{}m(\mathrm{d}\nu)\leq 1,$ (13)

so $r$ is the cdf of $m$. The set $\mathcal{M}$ of all these measures is
convex, and, by Helly’s selection theorem, compact in the weak∗ topology.

By (11), for every buyer valuation $\nu$, the utility $U_{r}(\nu)$ is linear
and continuous in $r$ and the payment $p_{r}(\nu)$ is linear and u.s.c. in
$r$. Therefore, the objective function (10) is linear and u.s.c., which
implies that the maximum is achieved at an extreme point. The set of extreme
points of measures under a finite number of moment conditions is well-
understood (see, for example [20]).

The extreme points of $\mathcal{M}$ for which (12) is not saturated correspond
to measures with a single atom and allocation function of the form
$r=r_{1}\mathbf{1}_{[\nu_{1},\infty)}$ with $r_{1}<1$ and $r_{1}\nu_{1}\leq
1$, implementable by a mechanism that offers a price$r_{1}\nu_{1}$ in return
for receiving the item with probability $r_{1}$. This mechanism cannot be
optimal under our objective function, because both buyer utility and payments
can be increased by offering the item with probability $1$ for the same price.

The extreme points of $\mathcal{M}$ for which (12) is saturated are
probability measures. If (13) is not saturated, then $m$ is a probability
measure with a single atom, corresponding to an allocation of the form
$r=\mathbf{1}_{[\nu_{1},\infty)}$ with and $\nu_{1}\leq 1$, as in the
proposition. If (13) is saturated, then $m$ is a probability measure with at
most two atoms, corresponding to an allocation of the form
$r=r_{0}\mathbf{1}_{[\nu_{0},\nu_{1})}+\mathbf{1}_{[\nu_{1},\infty)}$ for some
$0\leq\nu_{0}\leq\nu_{1}$ and some $0\leq r_{0}\leq 1$ such that
$r_{0}\nu_{0}+(1-r_{0})\nu_{1}=1$, as in the proposition. ∎

Example 2 in [7] presents an environment in which the bound on payments is
binding and the optimal mechanism is a menu with two options. That example
involves an environment in which the seller is uncertain of the buyer’s budget
as well as their valuation. However, the solution involves a menu with
payments no higher than the lowest budget, and so it must also be the optimal
mechanism in the problem where all buyers have the same (low) budget.

## References

  * [1] Anat R. Admati and Motty Perry  “Joint Projects without Commitment”  In _The Review of Economic Studies_ 58, 1991, pp. 259–276
  * [2] Mariagiovanna Baccara, SangMok Lee and Leeat Yariv  “Optimal dynamic matching”  In _Theoretical Economics_ 15 Wiley Online Library, 2020, pp. 1221–1278
  * [3] Marco Battaglini and Thomas R. Palfrey  “Dynamic Collective Action and the Power of Large Numbers” Working paper, 2024
  * [4] Marco Battaglini and Thomas R. Palfrey  “Organizing for Collective Action: Olson Revisited”  In _Journal of Political Economy_ , 2024, pp. Forthcoming
  * [5] Tilman Börgers  “An introduction to the theory of mechanism design”  Oxford University Press, USA, 2015
  * [6] Jonathan Borwein and Adrian Lewis  “ConvexAnalysis and Nonlinear Optimization: Theory and Examples”  Springer, 2006
  * [7] Yeon-Koo Che and Ian Gale  “The optimal mechanism for selling to a budget-constrained buyer”  In _Journal of Economic theory_ 92 Elsevier, 2000, pp. 198–233
  * [8] Yeon-Koo Che and Johannes Hörner  “Recommender Systems as Mechanisms for Social Learning”  In _Quarterly Journal of Economics_ 133, 2018, pp. 871–925
  * [9] Yeon-Koo Che and Olivier Tercieux  “Optimal queue design”  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 2021, pp. 312–313
  * [10] Olivier Compte and Philippe Jehiel  “Voluntary contributions to a joint project with asymmetric agents”  In _Journal of Economic Theory_ 112, 2003, pp. 334–342
  * [11] Joyee Deb, Aniko Oery and Kevin R. Williams  “Aiming for the Goal: Contribution Dynamics of Crowdfunding”  In _American Economic Review_ , 2024, pp. Forthcoming
  * [12] Laura Doval and Vasiliki Skreta  “Constrained information design”  In _Mathematics of Operations Research_ 49 INFORMS, 2024, pp. 78–106
  * [13] Piotr Dworczak, Scott Duke Kominers and Mohammad Akbarpour  “Redistribution through markets”  In _Econometrica_ 89 Wiley Online Library, 2021, pp. 1665–1698
  * [14] Chaim Fershtman and Shmuel Nitzan  “Dynamic voluntary provision of public goods”  In _European Economic Review_ 35, 1991, pp. 1057–1067
  * [15] Peter Frazier, David Kempe, Jon Kleinberg and Robert Kleinberg  “Incentivizing Exploration”  In _Proceedings of the Fifteenth ACM Conference on Economics and Computation_ , EC ’14, 2014, pp. 5–22
  * [16] Yingni Guo and Eran Shmaya  “The interval structure of optimal disclosure”  In _Econometrica_ 87 Wiley Online Library, 2019, pp. 653–675
  * [17] Martin F. Hellwig  “Public-Good Provision with Many Participants”  In _The Review of Economic Studies_ 70, 2003, pp. 589–614
  * [18] Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins and Zhiwei Steven Wu  “Bayesian Exploration with Heterogeneous Agents”  In _The World Wide Web Conference_ , WWW ’19, 2019, pp. 751–761
  * [19] Emir Kamenica and Matthew Gentzkow  “Bayesian Persuasion”  In _American Economic Review_ 101, 2011, pp. 2590–2615
  * [20] Alan F Karr  “Extreme points of certain sets of probability measures, with applications”  In _Mathematics of Operations Research_ 8 INFORMS, 1983, pp. 74–85
  * [21] Anton Kolotilin, Tymofiy Mylovanov, Andriy Zapechelnyuk and Ming Li  “Persuasion of a privately informed receiver”  In _Econometrica_ 85 Wiley Online Library, 2017, pp. 1949–1964
  * [22] Ilan Kremer, Yishay Mansour and Motty Perry  “Implementing the “Wisdom of the Crowd””  In _Journal of Political Economy_ 122, 2014, pp. 988–1012
  * [23] Yishay Mansour, Aleksandrs Slivkins and Vasilis Syrgkanis  “Bayesian Incentive-Compatible Bandit Exploration”  In _Proceedings of the Sixteenth ACM Conference on Economics and Computation_ , EC ’15, 2015, pp. 565–582
  * [24] Leslie M. Marx and Steven A. Matthews  “Dynamic Voluntary Contribution to a Public Project”  In _The Review of Economic Studies_ 67, 2000, pp. 327–358
  * [25] Steven A. Matthews  “Achievable outcomes of dynamic contribution games”  In _Theoretical Economics_ 8, 2013, pp. 365–403
  * [26] Roger B. Myerson  “Optimal Auction Design”  In _Mathematics of Operations Research_ 6, 1981, pp. 58–73
  * [27] Peter Norman  “Efficient Mechanisms for Public Goods with Use Exclusions”  In _The Review of Economic Studies_ 71, 2004, pp. 1163–1188
  * [28] Henk C Tijms  “A first course in stochastic models”  John Wileysons, 2003
  * [29] Donald M Topkis  “Supermodularity and complementarity”  Princeton university press, 1998