Revenue Maximization for Buyers with Costly Participation∗

Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Yannai A. Gonczarowski† Nicole Immorlica‡ Yingkai Li§ Brendan Lucier¶

Abstract
We study mechanisms for selling a single item when buyers have private costs for participating in the
mechanism. An agent’s participation cost can also be interpreted as an outside option value that she must
forego to participate. This substantially changes the revenue maximization problem, which becomes non-
convex in the presence of participation costs. For multiple buyers, we show how to construct a (2 + ϵ)-
approximately revenue-optimal mechanism in polynomial time. Our approach makes use of a many-buyers-
to-single-buyer reduction, and in the single-buyer case our mechanism improves to an FPTAS. We also bound
the menu size and the sample complexity for the optimal single-buyer mechanism. Moreover, we show that
posting a single price in the single-buyer case is in fact optimal under the assumption that either (1) the
participation cost is independent of the value, and the value distribution has decreasing marginal revenue or
monotone hazard rate; or (2) the participation cost is a concave function of the value. When there are multiple
buyers, we show that sequential posted pricing guarantees a large fraction of the optimal revenue under similar
conditions.

1 Introduction
In the textbook example of revenue optimization, a monopolist seller wishes to sell a single item to a collection of
buyers whose values are drawn independently from known distributions. In this idealized economic environment,
the nature of the optimal mechanism was solved by Myerson (1981). However, actual economic environments
depart significantly from this ideal. One significant assumption is that each buyer’s cost from participation is
normalized to zero. While convenient, this assumption is not without loss: it requires that agents are perfectly
indifferent between participating in an auction and leaving empty-handed, versus not attending the auction in
the first place.
In this paper we relax this assumption, allowing each buyer to have a private cost for participation in the
mechanism (or, equivalently, a private value for an outside option she must forgo to participate). Thus, a buyer’s
type includes both a valuation of the item for sale and a cost for participation, and the seller chooses a mechanism
for selling the item to maximize the expected revenue given a Bayesian prior over each buyer’s type. This
is a generalization of the model in Menezes and Monteiro (2000) and Celik and Yilankaya (2009) where the
participation cost is public information.
Our model can be interpreted in various ways. One interpretation is an oligopoly model with exclusive
competition (Champsaur and Rochet, 1989). For example, suppose there are multiple firms who wish to sell
different items to a single buyer by holding auctions simultaneously in different locations, and the buyer can
participate in at most one auction. Then from the perspective of any one seller, if we fix the other sellers’
strategies (selling mechanisms), the utility of the buyer for participating in a competing auction can be modeled
as a private cost for participation. Thus, the best response problem in this oligopoly model is the optimal
mechanism for buyers with participation costs. Another example is to view our model as a setting where buyers
must make investment decisions for boosting their values for winning the auction (Gershkov et al., 2021). Without
investment, the buyers have no value for winning the auction. The investments are costly for the buyers, and
the buyers must decide whether to invest before the auction starts. In these interpretations, the previous papers
(Champsaur and Rochet, 1989; Gershkov et al., 2021) have focused on settings equivalent to public, commonly

∗ Thefull version of the paper can be accessed at [Link]

† Department of Economics and Department of Computer Science, Harvard University. Email: yannai@[Link]. Research
carried out while at Microsoft Research New England Lab.
‡ Microsoft Research New England Lab. Email: nicimm@[Link].
§ Cowles Foundation for Research in Economics, Yale University. Email: [Link]@[Link]. Yingkai Li thanks Sloan Research

Fellowship FG-2019-12378 for financial support. Research carried out while this author was an intern in Microsoft Research New
England Lab and a PhD candidate at Northwestern University.
¶ Microsoft Research New England Lab. Email: brlucier@[Link].

Copyright © 2024
41 Copyright for this paper is retained by authors
 known participation costs. In contrast, the model that we study has private participation costs, which can be
arbitrarily correlated to the value of the item.
At first glance, one may wonder whether this setting is in fact equivalent to a single-dimensional setting
in which a buyer’s type is simply her value minus her participation cost. However, such a transformation can
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

substantially impact a buyer’s choices. Consider a single buyer with the choice between paying $3.1 for getting
the item for sure or paying $1 for getting the item with probability 50%1 (or not participating at all). If the buyer
has a value of $5 for the item and a participation cost of $1, she would strictly prefer the first option (paying $3.1
and getting the item for sure, for a resulting utility of 5 − 3.1 − 1 = $0.9). However, if instead of having a value
of $5 and a participation cost of $1, the buyer has a value of 5−1 = $4 and a participation cost of $0, she would
strictly prefer the second option (paying $1 and getting the item with probability 50%, for a resulting expected
utility of 12 · 4 − 1 = $1). So there is more at play here than is conveyed by the difference between the value and
the participation cost.
As we show, known results about the structure of the revenue-maximizing mechanism in the standard setting
without participation costs may fail to hold in the presence of participation costs, even in the single-buyer case.
Indeed, even when there is only one buyer, the seller can strictly benefit by offering lotteries (see Example 1
below). This is in sharp contrast to the idealized environment with participation costs normalized to zero, where
it is always optimal to simply post a single take-it-or-leave-it price (Myerson, 1981). We therefore embark on
a study to adapt and extend canonical economic and computational results on revenue maximization to this
generalized environment.

1.1 Our Contributions

A Characterization of Incentive Compatible Mechanisms. We begin by providing a structural
characterization of incentive compatible mechanisms in the presence of participation costs. Recall that in the
classic setting where participation costs are normalized to zero, a (direct-revelation) mechanism has each buyer
i declare her valuation vi , then maps this profile of values into an allocation xi and payment pi for each buyer.
In our setting, a direct-revelation mechanism takes as input a tuple (vi , ci ) of value and participation cost from
each agent. The question is which (two-dimensional) allocation and payment rules are incentive compatible and
individually rational in this environment.
For a single buyer, one way to construct a truthful mechanism is to ignore the participation cost entirely
and choose a monotone allocation rule that depends only on the reported value. The agent is then free to opt
out whenever her expected utility under the allocation rule is less than her participation cost. We call such
mechanisms opt-out-or-revelation mechanisms. Our first result is that, in fact, every mechanism for a single
buyer is revenue-equivalent to an opt-out-or-revelation mechanism, which further allows us to therefore restrict
attention to such mechanisms without loss, and incentive compatibility reduces to monotonicity of the allocation
rule. This enables us to establish a payment identity for our setting, analogous to the classic one of Myerson
(1981), and establish a virtual-value interpretation of revenue maximization in the presence of participation costs.
We would like to extend this characterization of incentive compatibility to multiple buyers. However, since
each agent’s expected utility from the mechanism can depend on which other agents participate, we must be
careful when modeling participation choices. Given a fixed allocation rule, there may be multiple equilibria of the
“participation game” between agents choosing whether or not to opt in.2 The choice of equilibrium can impact the
mechanism’s revenue, and hence what we mean by the revenue of a given allocation rule is potentially ambiguous.
One way to resolve this ambiguity is to encode participation choices into the mechanism protocol itself. For
example, we could imagine the mechanism approaching agents one at a time, asking them sequentially whether
they would like to opt in or out (potentially after revealing information about the agents who had previously
chosen to opt in). After all participation decisions have been made, the mechanism then applies a direct-
revelation allocation rule that depends only on the participating agents’ reported values. We call such mechanisms
sequential opt-out-or-revelation mechanisms. As in the single-buyer case, we show that every mechanism (and
every equilibrium of agent participation behavior) is outcome-equivalent to a sequential opt-out-or-revelation

1 Note that with the remaining 50% probability, the buyer will not get the item and she still needs to pay the cost since she chose

to participate in the mechanism.

2 For example, consider the mechanism that chooses a participating agent at random to receive the item for free. If there are two

agents, each with value 3 and participation cost 2, then there will be three equilibria of participation: one where only the first agent
participates, one where only the second agent participates, and one where each agent participates with probability 2/3.

Copyright © 2024
42 Copyright for this paper is retained by authors
 mechanism. This allows us to extend our characterization of incentive compatible mechanisms and our virtual-
value interpretation of revenue maximization to the setting with multiple buyers.
Computing an Approximately Revenue-Optimal Mechanism. Characterization in hand, we next
turn to the problem of constructing an approximately revenue-optimal mechanism. Our benchmark is the highest
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

revenue achievable by any mechanism and any equilibrium of participation choices by the agents. We show how
to construct a mechanism that achieves a constant fraction of this benchmark, less an additive ϵ loss. Moreover,
the equilibrium of participation in our mechanism is unique up to tie-breaking.3

Theorem 1.1. For any ϵ > 0 and any n buyers with types drawn from a product distribution supported on
[0, 1]2n , a mechanism with expected revenue 12 OPT − ϵ can be computed in time polynomial in n, 1/ϵ, and either
the maximum density of the participation cost in any agent’s type distribution (for continuous distributions) or
the maximum support size of any one agent’s type distribution (for discrete distributions).

Our assumption only requires independence across different buyers. For each buyer, the value can be
arbitrarily correlated with the participation cost. Our construction employs a reduction from the many-buyer
mechanism design problem to a single-agent problem. Such methods have been used with great success in related
settings, such as selling to agents with budget constraints and other revenue optimization problems (Alaei, 2014;
Alaei et al., 2012a). This reduction framework typically has three steps:
1. Compute an approximately revenue-optimal mechanism for a single buyer, possibly subject to additional
constraints (e.g., an upper bound on the ex-ante probability of selling the item).
2. Optimize over the choice of constraints for each buyer participating in the mechanism, then construct the
optimal interim allocation rule for each buyer subject to their constraints.
3. Combine the constructed interim allocation rules into a multi-agent ex post allocation rule.
As it turns out, implementing each of these three steps poses substantial challenges in our setting with
participation costs. We will discuss each of them in turn.

Step 1: Solving The Single-Buyer Problem.

Our first step is to construct a revenue-optimal mechanism for a single buyer. Recall that when there is only
one buyer, we can restrict attention to opt-out-or-revelation mechanisms. For this case we provide an FPTAS
algorithm for computing the optimal mechanism.

Theorem 1.2. For any ϵ > 0 and any distribution over buyer types supported on [0, 1]2 , a single-buyer mechanism
with expected revenue OPT − ϵ can be computed in time poly (1/ϵ).

A key challenge in this mechanism design problem is that revenue maximization is inherently non-convex
in the presence of participation costs. Recall that a given buyer type will opt out of the mechanism entirely if
her expected utility drops below her participation cost. This means that over the space of incentive compatible
allocation rules, revenue can be a discontinuous and not necessarily concave function of allocation probability.4
This immediately rules out many convex programming and duality-based approaches to revenue maximization
that are common in the algorithmic mechanism design literature.
To address this challenge, we instead discretize the type space and directly optimize over feasible allocation
rules. This involves tracking not only the allocation rule itself, but also the utility obtained by each buyer type,
as this is necessary for determining which buyer types will opt into the mechanism.
We note that the mechanism returned by our FPTAS can have a menu of lotteries of size potentially linear
in the number of buyer costs. We show that this is not an artefact of the approximation: the menu size of the

3 In other words, an agent might be indifferent between participating or not participating, and either choice could be supported at

equilibrium. Such indifference occurs with vanishing probability and does not impact the mechanism’s revenue.
4 For example, suppose the agent’s type (v , c ) is equally likely to be (7, 4) or (3, 1). A mechanism that sells the item for sure
i i
at a price of 2.5 would sell to the agent of type (7, 4), whereas the agent of type (3, 1) wouldn’t participate. On the other hand, a
mechanism that charges a price of 1.2 for a 50% chance at the item would sell to the agent of type (3, 1) whereas agent type (7, 4)
would opt out. But a mechanism that randomizes uniformly between these two allocation rules obtains revenue 0, since neither agent
type would choose to participate.

Copyright © 2024
43 Copyright for this paper is retained by authors
 revenue-maximizing mechanism is also at most linear in the number of possible costs. Moreover, this bound on the
menu size is tight up to a multiplicative factor of 2, even in the special case that the participation cost is perfectly
correlated with the value. We also bound the number of samples required to learn an up-to-ϵ revenue-maximizing
mechanism absent direct access to the underlying distribution.
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Step 2: Optimizing Bounds on the ex-ante Allocation Probabilities

We now turn back to the multi-agent mechanism design problem. In any valid mechanism, the total sum
of ex-ante probabilities of allocating the item to each buyer can be at most 1. The next step of our reduction
is to choose how to divide this unit of probability among the agents in our mechanism. Unfortunately, we face
the same challenge as in the single-buyer problem: the non-convexity of revenue maximization in the presence
of participation costs. This blocks us from using convex-programming techniques to optimize over the allocation
constraints, as is typical for applications of this approach.
We address this challenge by discretizing the set of potential ex-ante allocation probabilities, then directly
optimizing over potential assignments of constraints to individual buyers via dynamic programming. One
important observation is that we must take a buyers’ participation decisions into account when estimating the
ex-ante probability of allocation. I.e., if we want to find the allocation rule that optimizes revenue subject to
allocating the item with total probability at most q, then any buyer type who opts out of the mechanism should
not count toward this q, and of course the allocation rule itself determines which types opt in or out. Moreover,
these decisions can be distorted by the discretization of the type space. For this reason, we permit some slack in
our ex-ante allocation constraints and we must bound the accumulation of errors in the estimated probability of
allocation.
An additional complication arises when adapting our single-buyer FPTAS analysis to revenue maximization
with ex-ante allocation constraints. As it turns out, the revenue-optimal mechanism that sells with probability
at most q < 1 might not be a single allocation rule. Rather, the seller may want to randomize over multiple
mechanisms with different (and potentially also random) allocation and payment rules. This can be beneficial
because the seller is permitted to announce the realized mechanism before the buyer chooses whether to opt in,
and doing so could influence the buyer’s participation decision. Searching over all possible distributions over
mechanisms is computationally infeasible. Fortunately, we show that to maximize revenue subject to an ex-ante
allocation probability it suffices to consider distributions over at most two mechanisms, each satisfying one of our
discretized allocation probabilities. The optimal mechanism in this restricted class can be computed efficiently
by dynamic programming.

Step 3: Contention Resolution.

The final step in our construction is to combine the single-agent interim allocation rules into a single multi-
agent allocation mechanism. One way to do this is to try allocating to each agent independently using her own
interim allocation rule, then use contention resolution techniques if any conflicts arise. (I.e., if we try to allocate
to multiple agents at the same time, choose which of them should receive the item, if any.) Unfortunately, the
presence of participation costs once again creates a problem: contention resolution modifies the interim allocation
rule experienced by each agent, and this can influence each agent’s decision of whether to participate in the
mechanism.
We address this challenge by employing an online contention resolution scheme, such that the order in
which we resolve allocations is aligned with a sequential opt-out-or-revelation implementation of our mechanism.
Specifically, we employ a variation of an online rounding method due to Alaei et al. (2012b). For each agent
sequentially, the mechanism will pre-determine whether that agent is eligible to participate in the mechanism or
not. If so, that agent will face an allocation rule that is identical to the single-agent interim rule constructed
in our reduction, and hence her participation incentives will be unchanged. An appropriate choice of eligibility
probabilities for each agent yields an ex post implementable allocation rule while reducing the total revenue by
at most one half. This ultimately leads to the mechanism promised in Theorem 1.1.
Conditions for the Optimality of Posted-Price Mechanisms. Even for a single buyer, we’ve shown
that the optimal mechanism may require the use of lotteries. But are there conditions under which it is optimal
to post a fixed take-it-or-leave-it price, as is the case without participation costs?
We show that if either (1) the valuation distribution is independent of the participation cost distribution
and has decreasing marginal revenue or monotone hazard rate (Definition 2); or (2) the participation cost is a
concave function of the value; then the optimal mechanism simply posts a (carefully chosen) single price for the

Copyright © 2024
44 Copyright for this paper is retained by authors
 item. It turns out that, under these conditions, the optimal price is in fact equal to the standard monopoly price
for the (single-dimensional) distribution of the difference between the value and the participation cost. This is
not a coincidence: conditional on only posting a single take-it-or-leave-it price, a mechanism cannot distinguish
between types with the same difference between value and participation cost, and hence the mechanism’s revenue
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

depends only on this difference.

Finally, in the multi-buyer setting, as suggested by Gershkov et al. (2021), characterizing the exact
revenue-optimal mechanism may not be tractable even when the participation costs are known and all buyers
are symmetric. This is because the buyers do not satisfy the von Neumann–Morgenstern expected utility
characterization for their preference over lotteries, and the revenue-optimal mechanism may not be symmetric
even in this simplified case, as the set of feasible mechanisms is not convex (see Appendix D for more details). In
contrast, we show that even in the asymmetric setting, if for each buyer, either (1) the valuation distribution is
independent of the participation cost distribution and has decreasing marginal revenue; or (2) the participation
cost is a concave function of the value; then a sequential posted price mechanism guarantees a constant fraction of
the optimal revenue.5 Relative to our general mechanism construction from Theorem 1.1, this result imposes more
constraints on the buyers but yields an improved approximation factor and takes the simpler form of sequential
take-it-or-leave-it prices.

1.2 Related Work Our paper closely relates to the literature on auctions with private outside options and
endogenous participation. Rochet and Stole (2002) illustrate that some general lessons from that work are not
robust to the presence of a private value for the outside option when there are production costs (which our model
does not have). Follow-up work in economics focuses mainly on qualitative features of the optimal mechanisms
with costly participations, such as showing that distortion at the top or bottom is not required. There are
various extensions of the model by considering the optimal mechanisms when selling congestible goods (Jebsi
and Thomas, 2006), when principals are risk-averse (Basov and Yin, 2010), or when considering the optimal
income taxation rule (Lehmann et al., 2011). A recent paper by Ashlagi et al. (2021) considers consumer surplus
maximization when buyers have outside options, and buyers can only misreport their outside-option values by
downward deviation. Relative to that economics literature, our work provides a general characterization of
the optimal mechanism through a payment identity and virtual-value analysis, polynomial time algorithms for
computing the (approximately) optimal mechanisms, and natural sufficient distributional conditions for price
posting to be optimal or to guarantee a large fraction of the optimal revenue.
There is a body of literature examining mechanism design with perfectly correlated outside options, i.e., the
outside-option value is a deterministic and publicly known function of each agent’s item value (Jehiel et al., 1996;
Krishna and Perry, 1998; Jullien, 2000; Figueroa and Skreta, 2009).6 The assumption of perfectly correlated
outside options significantly simplifies the optimal design problem, as illustrated in Jullien (2000) and Section 5.2
of our paper. However, in our study, the main challenges arise when the agents’ outside option values are still
stochastic even conditional on their item values.
The model of costly participation also relates to the literature on return on investment (ROI) constraints
(Golrezaei et al., 2021a,b; Lucier et al., 2023). In these papers, the ROI constraints for each agent can be seen as
the additional utility the agent can gain by investing money in activities beyond the auction.
Our setting also relates to so-called “one-and-a-half dimensional” or “interdimensional” mechanism design
settings. In that domain, a buyer has one dimension representing her willingness to pay, and an additional “half
dimension” representing a constraint on her demand. For example, in the FedEx problem (Fiat et al., 2016) the
“half dimension” is the buyer’s deadline, and the buyer is only willing to accept the item before this deadline.
For buyers with budgets (Che and Gale, 1998; Devanur and Weinberg, 2017), the “half dimension” is the buyer’s
budget constraint, which places a cap on the maximum value she can pay for the item offered by the seller. In
our setting, a buyer’s participation cost can also be viewed as a “half dimension” of sorts since it only affects her
decision of whether or not to participate in the auction; conditional upon participating in the auction, the cost
does not affect the buyer’s utility in the auction.

5 Our result for the multi-buyer setting allows for a setting in which some of the buyers satisfy condition (1) while the others satisfy

condition (2).
6 Jehiel et al. (1996); Figueroa and Skreta (2009) motivate the perfectly correlated outside options through agents’ externalities in

allocations. In their model, the principal can control the outside option each agent receives, while in our model, the outside option
values are exogenous and stochastic.

Copyright © 2024
45 Copyright for this paper is retained by authors
 Our paper also falls into the scope of designing simple and approximately optimal mechanisms (Hartline
and Roughgarden, 2009). This line of work mainly focuses on the case in which all buyers have zero cost for
participation. For the single-item setting, sequential posted pricing guarantees a 1− 1/e fraction of the optimal
revenue (Yan, 2011). For multi-item setting, sequential posted pricing guarantees a constant fraction of the
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

optimal revenue when buyers have unit-demand valuations (Chawla et al., 2010; Cai et al., 2019), and selling
items separately or as bundles guarantees a constant fraction of the optimal revenue when buyers have additive
valuations (Babaioff et al., 2020; Cai et al., 2019). When buyers have non-linear utilities (e.g., budgeted utility),
Feng et al. (2020) show that constant-fraction approximation results (e.g., sequential posted pricing) for linear
buyers can be generalized to non-linear buyers when the type distributions of the buyers satisfy some closeness
property. There are numerous results on this topic. See the survey of Roughgarden and Talgam-Cohen (2019)
for a detailed discussion on approximately optimal mechanisms in various other settings.
Finally, our results on the menu and sampling complexity of the revenue-optimal mechanism also contribute
to the literature on menu sizes of optimal and approximately optimal mechanisms (e.g., Fiat et al., 2016; Hart
and Nisan, 2017; Babaioff et al., 2017; Devanur and Weinberg, 2017; Gonczarowski, 2018; Saxena et al., 2018;
Devanur et al., 2020) and to the literature on the sample complexity of learning up-to-ϵ optimal mechanisms
(e.g., Cole and Roughgarden, 2014; Morgenstern and Roughgarden, 2015; Devanur et al., 2016; Gonczarowski and
Nisan, 2017; Hartline and Taggart, 2019; Gonczarowski and Weinberg, 2018; Guo et al., 2019).

1.3 Roadmap In Section 2 we formalize our model and describe our revelation principle: that any mechanism
is revenue-equivalent to a truthful equilibrium of a sequential opt-out-or-revelation mechanism. In Section 3 we
characterize the truthful allocation rules for sequential opt-out-or-revelation mechanisms, and provide a virtual-
value interpretation of revenue maximization.
In Section 4 we consider revenue optimization for a single buyer. We present our FPTAS in Section 4.1,
and bound the menu and sample complexity of the optimal mechanism in Sections 4.2 and 4.3. Continuing with
the single-buyer setting, in Section 5 we present sufficient conditions for a posted-price mechanism to be revenue
optimal.
In Section 6 we turn to the multi-agent setting. We present our O(1)-approximate mechanism in Section 6.1.
In Section 6.2 we establish conditions under which sequential posted pricing is approximately optimal. We
discussion two alternative models for costly participation and open questions in Section 7.

2 Model and Preliminaries

A seller has a single item to offer for sale to n buyers. Each buyer i has a private valuation vi ≥ 0 for getting
the item and a private cost ci for participating in the mechanism.7 Let ti ≡ (vi , ci ) represent the private type
of buyer i and let F̄i be the seller’s prior distribution over ti with density f¯i . Let Fi and Gi be the marginal
distributions of values and costs with densities fi , gi . Note that a buyer’s value and cost may be correlated under
F̄i . Let F̄ = ×i F̄i be the product distribution of the buyers’ type profiles.
Mechanisms. A (possibly non-direct-revelation) mechanism is a communication protocol. This protocol can
be represented by a game tree that determines which players can (simultaneously) send and/or receive messages
at each round (i.e., node of the tree) and how those messages influence the progression of the protocol. The leaves
of the game tree specify rounds in which the protocol halts, at which point the mechanism terminates and outputs
the allocation and payments for each buyer. To capture participation decisions, we will assume that each agent’s
message space includes a special message ψ. If the first message (and only the first message) sent by an agent is
ψ, then the agent is said to have opted out of the mechanism and they receive utility equals zero.
We provide a generalized notion of a revelation mechanism, such that any mechanism can be transformed into
an outcome-equivalent sequential opt-out-or-revelation mechanism. Intuitively, in such a mechanism agents only
report their values, and there are fixed allocation and payment rules that map these reports to the mechanism’s
outcome. But the mechanism is not restricted to simultaneous reports: it can approach agents sequentially to
solicit their reports, and when it is an agent’s turn to report she can opt out of the mechanism rather than report

7 Although it is most natural to consider non-negative values for participation costs, negative values for participation costs can

capture the potential social benefit for the buyer to participate the auction, which is not modeled in her valuation for the item.
Introducing negative values for participation costs will lead to different observations for the optimality of posted pricing, which will
be discussed formally in Section E.

Copyright © 2024
46 Copyright for this paper is retained by authors
 her value. We formalize this class of mechanisms below.

Definition 1. A sequential opt-out-or-revelation mechanism proceeds as follows:

Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

• There is a (possibly random, possibly adaptive) order τ over the agents. For each agent i in this order, the
mechanism sends a message Ei that can depend on the protocol history. Agent i then either opts out (by
reporting ψ) or reports a declared value ṽi ≥ 0. Write R̄ = R ∪ {ψ} for this message space.

• Once all agents have reported, the outcome is determined by an allocation function x : R̄n → ∆({0, 1}n ) and
payment function p : R̄n → Rn , such that each buyer i reporting ψ receives xi = pi = 0.

• There exists an equilibrium in which each buyer i that opts into the mechanism reports her value vi truthfully.
That is, there exists a profile of strategies σ such that for any buyer i, any σi (ti , Ei ) ∈ {ψ, vi }, and any order
τ,

Et−τi ∼F̄−τi [uτi (M(σ(t, E))) | Eτi ] ≥ Et−τi ∼F̄−τi [uτi (M(b, σ−τi (t−τi , E−τi ))) | Eτi ] , ∀b ∈ R̄.

Note that this class includes traditional simultaneous-move direct revelation mechanisms, as this corresponds
to each Ei being an empty message. When there is only a single buyer, a sequential opt-out-or-revelation
mechanism has an especially natural form: it is simply a direct-revelation mechanism (characterized by a truthful
allocation and payment rule) in which each buyer type (vi , ci ) is permitted to opt out, and will do so precisely if
her expected utility from the mechanism is less than ci .
In Section A we prove that any mechanism protocol can be converted into a sequential opt-out-or-revelation
mechanism with the same distribution over outcomes (and hence the same expected revenue).

Lemma 2.1. For any type distribution F̄ , any mechanism M, and any Bayes-Nash equilibrium of the corre-
sponding game, there exists a sequential opt-out-or-revelation mechanism M
c and a truthful equilibrium of M
c that
generates the same distribution over outcomes.

Posted-Price Mechanisms. When there is a single buyer (n = 1), we say that a sequential opt-out-or-
revelation mechanism M posts a price if there exists a price p such that the mechanism awards the item with
probability 1 for a price of p if the buyer participates and reports a value of no less than p, and otherwise the item
is not awarded and p = 0. With n ≥ 2 buyers, we say that a sequential opt-out-or-revelation mechanism M is a
sequential posted price mechanism if there exist prices pi and an order over the buyers such that the mechanism
awards the item with probability 1 for a price of pi to the first buyer i—according to this order—who participates
and reports a value of no less than pi (and no other buyers are charged any price), and the item is not awarded
and no buyer is charged any price if no such buyer exists. Each buyer is informed about the availability of the
item when he sees the price. P
Revenue Maximization. For any mechanism M, let Rev(t, σ; M) = i pi (σ(t)) be the revenue of
mechanism M given type profile t and strategy profile σ, and let Rev(F̄, σ; M) = Et∼F̄ [Rev(t, σ; M)] be the
expected revenue given distribution F̄ . We will omit the strategy σ in the notation if it is clear from the context.
Let

OPT(F̄ ) = max max Rev(F̄, σ; M)

M σ∈BNE(F̄,M)

be the optimal expected revenue of the seller given distribution F̄ under the Bayes–Nash equilibrium with highest
expected revenue. Let ϕ(v) = v− 1−F (v)
f (v) be the virtual value of the buyer with value v and valuation distribution F .

Definition 2. For any valuation distribution F with density function f and virtual value function ϕ,

• F is regular if the virtual value ϕ(v) is non-decreasing;

• F has decreasing marginal revenue (DMR) if f (v)ϕ(v) is non-decreasing;

• F has monotone hazard rate (MHR) if ϕ′ (v) ≥ 1 for all v.

Copyright © 2024
47 Copyright for this paper is retained by authors
 3 Virtual Values and the Suboptimality of Posted Prices
Lemma 2.1 shows that it is without loss to restrict to mechanisms that employ single-dimensional allocation and
payment rules and give agents the opportunity to opt out. But which allocation and payment rules are truthful
for the buyers who choose to opt in? In this section we show that, similar to the case without participation
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

costs, truthfulness corresponds to monotonicity of interim allocation rules. We establish a Myerson-style payment
identity and virtual value characterization of truthful revenue maximization.
For most of this section we will focus on the setting where there is only a single buyer in the market, so we will
omit the subscript i from our notation. That said, all of the characterization results in this section extend directly
to the multi-buyer setting by interpreting them as conditions on the interim allocation and payment experienced
by each bidder; see the remark at the end of this section. Note also that all results in this section apply even
when the distribution over types allows for correlation between valuations and participation costs.
In the following example, we show that the private participation costs setting is qualitatively different from
the setting in which the participation costs are normalized to zero, by providing a distribution over values and
participation costs—these will even be independently distributed—such that offering lotteries to the buyer can
strictly improve the expected revenue compared to posting a single fixed price.8
Example 1. The value and cost of the buyer will be independently distributed. The value distribution has CDF
1
F (v) = 1 − v−1 for v ∈ [2, 5) and F (v) = 1 for v ≥ 5. Note that F is a regular distribution. The participation
cost is 0 with probability 0.15 and 2 with probability 0.85. In this example, the optimal posted-price mechanism
is to post price 2, resulting in revenue 0.86̄. However, consider the mechanism that offers two probability-price
lotteries (1, 3), ( 32 , 43 ). The buyer with value 5 will choose the lottery (1, 3) and receives utility 2 regardless of his
participation cost. Moreover, the buyer with value in [2, 5) will choose the lottery ( 32 , 43 ) if his participation cost
is 0, and not participate in the auction if his participation cost is 2. The expected revenue of this mechanism
is 41 × 3 + 34 × 0.15 × 43 = 0.9, which is strictly higher than 0.86̄. The multiplicative gap between the optimal
mechanism and optimal pricing is therefore higher than 1.038.
A classic approach to designing the revenue-optimal mechanism for a single-item setting when the participation
cost is known to the seller is to use a payment identity and virtual value analysis.

Lemma 3.1. (Myerson, 1981) In the single-item single-buyer setting, if the buyer has participation cost 0, for
any truthful mechanism RM with allocation x and payment p, it holds that x is non-decreasing and the payment
v
satisfies p(v) = vx(v) − 0 x(z) dz + p0 for some constant p0 . The expected revenue given distribution F is

Rev(F ; M) = Ev∼F [x(v)ϕ(v)] + p0 .

In this section, we provide an analog of the payment identity when buyers have private participation costs.
That is, we show that it is without loss to consider a truthful mechanism as if the participation cost is 0, in which
case the buyer will participate if and only if her utility from participating is at least her participation cost.

Lemma 3.2. It is without loss R v for the seller to commit to a monotone non-decreasing allocation rule x(v) and
payment rule p(v) = vx(v) − 0 x(z) dz + p0 for some constant p0 , and for the buyer to participate and truthfully
Rv
reveal v if and only if u(v; x, p) = 0 x(z) dz − p0 ≥ c where c is the participation cost.

Proof. In Section 2, we have shown that it is without loss to consider the opt-out-or-revelation mechanism where
the buyer truthfully reveals her value conditional on participation. By Lemma 3.1, the allocation
Rv satisfying
the incentive constraint must be non-decreasing, and the payment satisfies p(v) = vx(v) − 0 x(z) dz + p0 for

8 There is an interesting conceptual connection between this example and the observation of Deneckere and McAfee (1996) that

a seller may be able to strictly increase her revenue by introducing a damaged good into the market. Note that our setting with a
private participation cost can be converted into a two-item setting. In this two-item setting, one of the items would correspond to
participating and winning while the other would correspond to participating and not winning—the latter having negative value with
probability 1 (if the original participation cost is positive)—and the mechanism is constrained to ex-post allocate exactly one item
to the buyer. Example 1 shows that price posting in our costly participation setting— which in the transformed two-item setting
translates to preventing the item with negative value from being sold—may not maximize revenue. Therefore, in the transformed
two-item setting, Example 1 is interpreted as showing that the seller can strictly increase her revenue by introducing a new item with
negative value—a good so damaged that its value to the buyer is in fact always negative.

Copyright © 2024
48 Copyright for this paper is retained by authors
 x(v) xc (v)

p(v) − p0
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

pc (v) − p0

c + p0

0 vc (x) v 0 vc (x) v

Figure 1: The figure on the left is an illustration of the payment p(v) and the cutoff value vx (c) where c − p0 ≥ 0.
The figure on the right illustrates the interim allocation rule xc (v) when the participation cost is c. Here pc (v) is
the incentive compatible payment rule for allocation rule xc (v). The figure illustrates that pc (v) = p(v) + c for
any v ≥ vx (c).

R v constant p0 . Finally, the utility of the buyer for participating the auction is u(v; x, p) = v · x(v) − p(v) =
some
0
x(z) dz − p0 , and she therefore maximizes utility by participating in the auction if and only if her utility is at
least c.
Rv
Given any allocation rule x and corresponding payment p(v) = v · x(v) − 0
x(z) dz + p0 , let vx (c) =
inf v≥0 {v · x(v) − p(v) ≥ c}, and
(
x(v) v ≥ vx (c)
xc (v) =
0 v < vx (c).

That is, vx (c) is the minimum value at which a buyer with participation cost c will choose to participate in a
mechanism with allocation rule x, and xc (v) is the resulting allocation rule taking the participation decision into
account. For any joint distribution F̄ , let F̄c be the conditional value distribution when the participation cost is
c. We define the virtual value of the buyer given conditional valuation distribution F̄c as ϕc (v) = v − 1−fˆF̄(v)
c (v)
.
c

Lemma 3.3. Given any distribution F̄ with marginal cost distribution G, and any mechanism M with allocation
x and payment rule p with parameter p0 , the revenue of the seller is
 
Rev(F̄ ; M) = Ec∼G Ev∼F̄c [xc (v)ϕc (v)] − (1 − F̄c (vx (c))) · max{−p0 , c} .
The proof of Lemma 3.3 is given in Section B. Intuitively, the term Ev∼F̄c [xc (v)ϕc (v)] represents the difference
in social welfare and the agent’s expected utility, similar to the characterization in Myerson (1981). The additional
term (1 − F̄c (vx (c))) · max{−p0 , c} in our setting is the additional utility the agent obtains from either saving her
participation cost c, or the utility −p0 the mechanism provides to the lowest type. Such additional utility for the
buyer are subtracted to correctly calculate the expected revenue.
In this paper, we focus on the problem of revenue maximization, so it is without loss to consider p0 ≥ 0.
When participation costs are non-negative, it is without loss to further assume that p0 = 0. The proof of the
following lemma is given in Section B.
Rv
Lemma 3.4. For any mechanism with allocation and payment x, p such that p(v) = vx(v) − 0 x(z) dz + p0 for
some constant p0 , there
R v exists another mechanism with allocation and payment x̂, p̂ with weakly higher revenue
and p̂(v) = vx̂(v) − 0 x̂(z) dz + p̂0 where p̂0 ≥ 0. This can be strengthened to p̂0 = 0 if the participation costs are
non-negative.
Remark: Multiple Buyers. We note that Lemmas 3.2, 3.3, and 3.4 extend immediately to the case of
multiple buyers by interpreting x and p as a buyer’s interim allocation and payment rules. In the multi-buyer
case it is important to note that the interim allocation rule for agent i is evaluated in expectation not only
over the types of the other agents, but also over their (possibly randomized) participation decisions. For weakly
monotone interim allocation rules, the revenue obtained by the seller from each buyer is the virtual surplus less
the participation cost adjustment, as in Lemma 3.3.

Copyright © 2024
49 Copyright for this paper is retained by authors
 4 Revenue Optimization for a Single Buyer
4.1 An FPTAS Algorithm We now turn to the problem of optimizing over the space of allocation rules
identified in the previous section. We will assume that both the value and the cost are supported in [0, 1].9 We
show that by discretizing the valuation space and the allocation space of the mechanism, the loss in optimal
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

revenue is small, and for the discretized problem, the optimal mechanism can be computed efficiently using
dynamic programming. The following two lemmas quantify the discretization errors, with proofs provided in
Section B.

Lemma 4.1. Let (Ω, F, P ) be any probability measure, and let t1 , t2 : Ω → R2 be two 2-dimensional random
variables. If supω∈Ω ∥t1 (ω) − t2 (ω)∥∞ ≤ ϵ, then |OPT(t1 ) − OPT(t2 )| ≤ 3ϵ, where OPT(tk ) is the optimal
expected revenue when the valuation and participation cost follow the same distribution as the random variable tk .

Lemma 4.2. For any distribution F̄ supported on [0, 1]2 and for any pair of mechanisms M and M c with allocation
rules x and x̂ such that x(v) ∈ [x̂(v), x̂(v) + ϵ] for all ϵ, we have Rev(F̄ ; M) ≥ Rev(F̄ ; M) − ϵ.
c

Having bounded the errors we accumulate due to discretization, we are ready to describe our FPTAS. The
following is a restatement of Theorem 1.2 from the introduction.
2
Theorem 4.1. For any
distribution F̄ supported on [0, 1] , for any ϵ ∈ (0, 1), there exists an algorithm with
running time poly 1ϵ that computes a mechanism with revenue at least OPT(F̄ ) − O(ϵ).

Proof. Let F̄ ′ be the type distribution F̄ with each value rounded down to the nearest multiple of ϵ. Let qi
be the marginal probability that the value equals i · ϵ, and let F̄i′ be the distribution over participation costs
conditional on the event that the rounded value is i · ϵ. By Lemma 4.1, we have OPT(F̄ ′ ) ≥ OPT(F̄ ) − 3ϵ. Let
M be the optimal mechanism for distribution F̄ ′ with allocation only taking values on the discretization grid.
By Lemma 4.2, we have Rev(F̄ ′ ; M) ≥ OPT(F̄ ′ ) − ϵ. Combining the inequalities, we have

Rev(F̄ ; M) ≥ Rev(F̄ ′ ; M) ≥ OPT(F̄ ′ ) − ϵ ≥ OPT(F̄ ) − 4ϵ

where the first inequality holds since the value distribution in F̄ first order stochastically dominates F̄ ′ .
We now turn to computing the mechanism M, which we will do by dynamic programming. For i, j ≤ 1ϵ and
k ≤ ϵ12 , let R(i, j, k) be the optimal revenue from types with value at or below i · ϵ when the allocation and utility
of buyers with value i · ϵ are j · ϵ and k · ϵ2 respectively. We initialize the matrix by R(1, j, k) = 0 for any k ≤ j
and R(1, j, k) = −∞ for k > j. For any i ≥ 2, we have

(4.1) R(i, j, k) = max

′
R(i − 1, j ′ , k − j) + qi · F̄i′ (k · ϵ2 ) · (i · j − k) · ϵ2 .
j ≤j

To interpret this expression, we note that first term of (4.1), maxj ′ ≤j R(i − 1, j ′ , k − j), is the revenue from types
with value at most (i − 1)ϵ. Indeed, the allocation of type with value (i − 1)ϵ should not exceed the allocation of
type with value i · ϵ, and hence the choice of j ′ is at most j. Moreover, when the allocation and utility of type
with value i · ϵ are j · ϵ and k · ϵ2 respectively, Lemma 3.2 implies that the utility of type with value (i − 1)ϵ is
exactly (k − j)ϵ2 (which is why we have k − j as the third argument), which is independent of the choice of j ′ .
The second term of (4.1) is the expected revenue from types with value at most i · ϵ. Note that qi · F̄i′ (k · ϵ2 )
is the total probability of those types that have incentives to participate in the auction, and (i · j − k) · ϵ2 is the
payment of those types, which is derived by subtracting the utility k · ϵ2 from the expected value i · j · ϵ2 , if they
choose to participate.
In order to compute the matrix of R, we need to compute 1ϵ × 1ϵ × ϵ12 = ϵ14 numbers, and computing each
number requires taking the maximum over at most 1ϵ numbers. Thus the matrix R can be computed in time
O( ϵ15 ).
Once R has been filled, note that Rev(F̄ ′ ; M) = maxj,k R(1/ϵ, j, k). To recover the allocation rule of M from
R, note that if j ′ is the value of j maximizing R(1/ϵ, j, k) then M allocates jϵ to agents with value 1. The rest of
the allocation rule can be recovered similarly by unrolling the recursion from (4.1): for each i ≤ 1/ϵ, if j ′ is the
choice that maximizes R(i − 1, j ′ , k − j), then agents with value (i − 1)ϵ are allocated j ′ ϵ.
9 Any bounded distribution can be normalized such that the support is in [0, 1].

Copyright © 2024
50 Copyright for this paper is retained by authors
 4.2 Menu Complexity By the taxation principle, the optimal mechanism for the single buyer problem is
essentially posting a menu of allocations and payments for the buyer to choose from. Let d be the size of the
support for the cost distribution. Example 1 shows that it can be optimal to offer a menu of at least 2 options
to the buyer when d ≥ 2. In this section, we provide an upper bound, as a function of d, on the number of menu
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

entries required in the optimal mechanism, i.e., on the menu size of the optimal mechanism. The main idea is to
reduce the problem to d different revenue maximization problems with public budgets. The proof is deferred to
Section B.

Theorem 4.2. For selling a single item to a single buyer with private participation cost, when the size of the
support for the cost distribution is d, the menu size required for the optimal mechanism is at most 2d + 1.

The following proposition provides a lower bound on the menu complexity even when the participation cost
is perfectly correlated with the value. This implies that the bound for the menu complexity in Theorem 4.2 is
tight up to a multiplicative factor of 2.

Proposition 4.1. (Jullien, 2000; Li, 2022) For selling a single item to a single buyer with private participa-
tion cost, for any d ≥ 1, there exists an instance where the participation cost cv is a non-negative, increasing,
and strictly convex function of v, the support sizes of both the marginal value and marginal cost distribution are
d, and the menu size required for the optimal mechanism is d.10

4.3 Sample Complexity In this section, we consider a setting in which the joint distribution F̄ is unknown to
the seller, who instead only has access to samples from this distribution, and upper bound the number of samples
required to learn an up-to-ϵ optimal auction. The proof is deferred to Section B.

Theorem 4.3. For selling a single item to a single buyer with private participation cost, for any constant ϵ > 0,
if the joint distribution F̄ is supported on [0, 1] × [0, 1], there exists a mechanism with access to O(ϵ−6 log ϵ−1 )
samples that obtains expected revenue at least OPT(F̄ ) − ϵ.

Note that in contrast to the traditional single-item auction for a single buyer without participation costs
where the sample complexity is Õ(ϵ−2 ) (c.f., Guo et al., 2019), the sample complexity bound in our model is
significantly higher. The increase of sample complexity originates from two sources. First, we are learning a
two-dimensional correlated distribution instead of a single-dimensional distribution, which is intrinsically harder.
Second, the space of optimal mechanisms we search for is larger. Instead of only considering posted pricing
mechanisms for auction without participation costs, we need to optimize over mechanisms with menu complexity
O(d).

5 Optimality of Posted Pricing in the Single-Buyer Setting

Recall that as illustrated in Example 1, in general it is not revenue-optimal to post a single take-it-or-leave-it price
when buyers have participation costs. In Theorem 4.1 we compute an approximately revenue-optimal mechanism,
which may involve a menu with multiple lotteries. But are there conditions under which this complexity is
unnecessary, and we recover the simplicity of the posted-price mechanisms that are optimal when participation
costs are zero?
In this section, we show that under natural assumptions on the joint distribution, posting a deterministic
take-or-leave-it price is optimal for the seller. We will focus on the case in which the private participation cost is
non-negative, and by Lemma 3.4, we set p0 = 0 and omit it in the notation.

5.1 Independent Participation Costs In this section, we consider the setting where the cost distribution is
independent from the valuation distribution. In this case, we provide two sufficient conditions on the valuation
distribution such that posted pricing is optimal for revenue maximization.

10 Li
(2022) considers a single-agent setting about selling information. They characterize the optimal mechanism in their setting
by solving a relaxed problem that looks identical to selling a single item with costly participation where the cost of participation is a
deterministic and convex function of the valuation. Therefore, we can directly apply the characterization in their relaxed problem to
immediately show our lower bound on menu complexity. However, note that Li (2022) does not derive any result when the cost can
be stochastic (e.g., independent of the value) or when there are multiple agents.

Copyright © 2024
51 Copyright for this paper is retained by authors
 5.1.1 DMR Valuation Distribution We start by analyzing the case in which the valuation distribution has
decreasing marginal revenue. We begin with a technical lemma that encapsulates a useful implication of the
decreasing marginal revenue property, with proof provided in Section C.
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Lemma 5.1. If the valuation distribution F has decreasing marginal revenue, then for any c ≥ 0 and any v ≥ c,
we have that f (v)(ϕ(v) − c) is monotone non-decreasing in v.

Theorem 5.1. With independent values and participation costs, and with non-negative participation costs, if the
value distribution F has decreasing marginal revenue and bounded support,11 there exists a revenue-maximizing
mechanism that is a posted price mechanism.

The details of the proof is provided in Section C. Intuitively, DMR is an assumption stating that the seller
can always extract higher revenue (or equivalently increase virtual welfare) by allocating the item to the agent
with higher value instead of lower value when there is no participation cost. In Theorem 5.1, we show that the
extra negative impact of the participation cost on revenue is decreasing as we reduce the probability of selling
the item to a given agent (this is transparent from Lemma 3.3). So by shifting the allocation from lower-value
agents to higher-value agents, we simultaneously increase the virtual welfare and decrease the negative impact
of participation costs (as the agent will participate less often). Shifting the allocation in this way as much as
possible ultimately leads to a step function corresponding to posted pricing, which must then be optimal.

Remark 1. In this section we have focused on the case in which the participation cost is non-negative. In
Section E, we show that a deterministic mechanism can guarantee at least 50% of the optimal revenue when the
participation cost could be positive or negative. Note that, in this context, a deterministic mechanism is equivalent
to setting a price p0 for participating the auction, and an additional price p for winning the item. The presence
of the additional participation cost p0 is intuitive: a negative participation cost means that an agent has a strict
incentive to participate in the auction regardless of outcome, and p0 serves to extract a portion of that participation
utility as revenue.

5.1.2 MHR Valuation Distribution We move on to analyzing the case in which the valuation distribution
has monotone hazard rate. Note that if the valuation distribution F satisfies monotone hazard rate, the derivative
of the virtual value is ϕ′ (v) ≥ 1 for all v ≥ 0, and hence distribution F is regular as well.

Lemma 5.2. (Devanur and Weinberg, 2017) If the valuation distribution F is regular, then f (v)ϕ(v) is non-
decreasing in v for v ∈ [0, v ∗ ] where v ∗ = inf v {ϕ(v) ≥ 0}.

Theorem 5.2. With independent values and participation costs, and with non-negative participation costs, if the
value distribution F has monotone hazard rate, there exists a revenue optimal mechanism that is a posted price
mechanism.

The details of the proof is provided in Section C. Note that there is asymmetry between the conditions we
require on the value distribution and the cost distribution to establish optimality of posting a price. We have
shown that, for any distribution over participation costs, posting a price is optimal as long as the value distribution
satisfies monotone hazard rate or decreasing marginal revenue. However, even if the cost distribution is uniform,
posting a fixed take-it-or-leave-it price need not be optimal without further assumptions on the value distribution.
The following example illustrates such a scenario.

Example 2. The value of the buyer is 1 or 2 with probability 12 each. The participation cost is uniformly
distributed in [0, 1]. The optimal posted price mechanism is to post a price of 1, generating revenue 12 . However,
the mechanism that offers the menu of two probability-price lotteries (1, 1), ( 32 , 13 ) has revenue 59 . The multiplicative
gap between the optimal mechanism and optimal pricing is therefore higher than 1.111.
11 The boundedness assumption is to avoid a situation in which the optimal mechanism is not well defined, i.e., for any mechanism,

there exists another mechanism with strictly higher revenue. For example, if the buyer has participation cost 0, and the CDF of the
1
value is F (v) = 1 − v+1 for v ≥ 0, the supreme of the revenue is only attained in the limit by offering a take-or-leave-it price p → ∞.
Note that bounded support is a sufficient condition to guarantee this property, but it may not be necessary.

Copyright © 2024
52 Copyright for this paper is retained by authors
 5.2 Perfectly Correlated Participation Costs In this section, we assume the participation cost is perfectly
correlated with the value. That is, there is a publicly known mapping from each value v to the unique
corresponding participation cost cv , and moreover cv is monotone increasing in v.12 Note that as illustrated
in Proposition 4.1, when the participation cost is convex in the value, the optimal mechanism may not be posted
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

pricing. In fact, the menu complexity can be infinite for continuous valuation distributions. In contrast, when
the participation cost cv is concave in v, posted pricing is always revenue maximizing. The proof of the following
theorem is provided in Section C.
Theorem 5.3. If the participation cost cv is a non-negative and concave function of v, then for any value
distribution F , there exists a revenue optimal mechanism that is a posted price mechanism.

6 Mechanisms for Multiple Buyers

6.1 An Approximately Optimal Mechanism for Multiple Buyers For the multi-buyer setting, as
illustrated in Section 2 (and in Section A), optimizing revenue involves not only the mechanism’s allocation rule
but also the equilibrium participation behavior of the agents. As with the single-buyer case, revenue maximization
is inherently non-convex in this environment (see Section D.1 for further discussion).
In this section, we provide a polynomial time algorithm for computing a mechanism that is a constant
approximation to the optimal revenue. Our solution will take the form of a sequential opt-out-or-revelation
mechanism in which the agents’ participation decisions are unambiguous.13 We will describe our algorithm for
continuous type distributions. At the end of this section we discuss how to adapt our procedure to discrete
distributions provided as an explicit assignment of probabilities to a finite collection of types. The following
restates Theorem 1.1 from the introduction.
Theorem 6.1. For any product distribution F̄ = ×i=n F̄i with F̄i supported on [0, 1]2 with density of the
conditional participation cost being at most η ≥ 1, for any ϵ ∈ (0, 1), there exists an algorithm with running
time poly nη that computes a mechanism with revenue at least 12 OPT − ϵ.


ϵ

As discussed in the introduction, the main idea of our construction is to reduce to the single-buyer revenue
maximization problem, employing a reduction framework introduced by Alaei (2014). To do this we consider the
ex-ante relaxation of the optimal mechanism, efficiently compute the ex-ante optimal mechanism for each buyer,
and sequentially offer those mechanisms to the buyers. One challenge for adopting this approach is that given an
ex-ante constraint in the single-buyer problem, the efficient computation result through dynamic program only
finds the best fixed mechanism, while it might be necessary for the seller to randomize over mechanisms. That
is, the seller chooses a distribution over mechanisms, informs the buyer about the realization, offers the buyer
the realized mechanism, and then the buyer makes the participation decision. Such randomization cannot be
collapsed as a single mechanism with randomized allocations since it affects the buyer’s participation decisions
and eventually the expected revenue. The issue of requiring randomized mechanisms also arises when discretizing
the allocation spaces. If we only consider a fixed mechanism, even if randomized allocation rules are allowed in the
fixed mechanism, increasing the allocation probabilities to the discretized grid may violated the interim feasibility
constraints, while decreasing the allocation probabilities may exclude the buyer from participating in the auction.
Fortunately, such issue of randomization can be alleviated by showing that in order to approximate the optimal
ex-ante revenue, it is sufficient to consider the randomization over two fixed mechanisms over a discretized space
of allocation rules. We formalize this in Lemma D.1 below, but first we describe the way to discretize the type
distributions.
Formally, given a type distribution F̄ , we will approximate F̄ via the following sequence of rounding operations.
First consider the discretization grid Ψ0 = {0, ϵ, 2ϵ, . . . , 1}. Given type distribution F̄ , let F̄ ′ be the distribution
that rounds all values down to the discretization grid Ψ0 (i.e., down to the nearest multiple of ϵ). Write zk for
the marginal probability that the rounded value equals kϵ, and let F̄k′ be the distribution over participation costs
conditional on the event that the rounded value is kϵ. Moreover, consider an additional distribution F̄ † that is like

12 The case in which the participation cost c is monotone non-increasing in v is rather trivial since the individual rationality
v
constraint only binds for the lowest type.
13 Each agent will be offered a menu of allocations and payments. While the menu offered to agent i can depend on the behavior

of others, the agent’s outcome will be otherwise independent of other agents’ decisions given the menu. Agent i will therefore opt in
precisely when the expected utility from the menu exceeds the participation cost.

Copyright © 2024
53 Copyright for this paper is retained by authors
 F̄ ′ but with two changes. First, each marginal value probability zk is rounded up to the nearest multiple of ϵ2 ; call
these rounded probabilities zk† . Second, for each conditional cost distribution F̄k′ , we will round all participation
costs up to the nearest multiple of ϵ2 . Write F̄k† for the resulting rounded conditional cost distribution.14 Write Ψ1
for the discretization grid consisting of {0, ϵ2 , 2ϵ2 , . . . , 1}, so that each F̄k† is supported on Ψ1 . Let OPTq (F̄ ) be the
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

optimal revenue for distribution F̄ given ex-ante allocation constraint q and let OPT [ q (F̄ ) be the optimal revenue
15
for distribution F̄ given ex-ante constraint q, only randomizing over two fixed mechanisms with allocations and
ex-ante probabilities on the discretized grid Ψ0 .
Now that we have described our intended rounding of the type distribution, we can show that the errors
obtained under this rounding is small when we restrict our mechanism to have ex-ante sale probabilities that are
multiples of ϵ. Moreover, such rounding errors allow us to compute the profile of optimal ex ante probabilities
efficiently. The proof of the following lemma is provided in Section D.2.
Lemma 6.1. For any ϵ̂ > 0, there exists an algorithm with running time poly nϵ̂ that computes a profile of

{qi† }i∈[n] subject to the constraint that i∈[n] qi† ≤ 1, and the corresponding mechanisms {Mi,q† }i∈[n] such that
P
i

{qi† }i∈[n] maximizes i∈[n] Rev(F̄i ; Mi,q† ) and

P
i

[ † (F̄i† ) − ϵ̂,
Rev(F̄i ; Mi,q† ) ≥ OPT ∀i.
i q i

n


Proof. [Proof of Theorem 6.1] By Lemma 6.1, for any ϵ̂ > 0, with running time poly ϵ̂ , we compute the profile
of {qi† }i∈[n] and the corresponding mechanisms {Mi,q† }i∈[n] such that
i

[ † (F̄i† ) − nϵ̂.
X X
Rev(F̄i ; Mi,q† ) ≥ OPT q
i i
i∈[n] i∈[n]

Finally, to complete the proof of Theorem 6.1 we must show how to combine the single-agent mechanisms
Mi,q† to construct a multi-agent mechanism with similar total revenue. Fix any order of the buyers, and consider
i
a sequential mechanism that attempts to sell the item to each buyer i in order. As long as the item has not yet
been sold, each buyer i will be offered the mechanism (i.e., the allocation rule) Mi,q† with probability 2−P1 q†
i j<i j
(and with the remaining probability buyer i will not be given an opportunity to participate). We claim that
under this procedure, each buyer i is offered the mechanism Mi,q† with probability between 1/2 − nηϵ̂ and 1/2,
i

and hence the total probability that buyer i obtains the item is at least ( 12 − nηϵ̂)qj† and at most 21 (qi† + ηϵ̂).
Indeed, by induction, each buyer j < i receives the item with total probability at most 12 (qj† + ηϵ̂), and hence the
probability that the item is unsold when buyer i is to be approached is at least 1 − 12 j<i (qj† + ηϵ̂). Taking into
P
account the probability that we offer anything to buyerPi when the item is unsold, we conclude that buyer i is
† †
1− 12 1− 21
P
j<i (qj +ηϵ̂) j<i qj
offered mechanism Mi,q† with probability at least 2−
P † ≥ 1/2 − nηϵ̂ and at most P † = 1/2,
i j<i qj 2− j<i qj
as claimed. Therefore, the expected revenue from this sequential mechanism is at least
 X  X
1 1 [ † (F̄i† ) − nϵ̂

− nηϵ̂ Rev(F̄i ; Mi,q† ) ≥ − nηϵ̂ OPT q
2 i 2 i
i∈[n] i∈[n]
 
 
1 X
≥ − nηϵ̂  max OPTqi (F̄i ) − 6nϵ̂
2 {qi }i∈[n]
i∈[n]
 
1 1
≥ − nηϵ̂ OPT − 3nϵ̂ ≥ OPT − 4nηϵ̂
2 2
ϵ
where the second inequality holds by applying Lemma D.1. For any ϵ > 0, by setting ϵ̂ = 4nη , the expected
revenue loss is ϵ, and the running time is poly nη


ϵ .

14 Note that distribution F̄ † is not a well defined distribution since the total probability measure may exceed 1. However, the

expected revenue Rev(F̄ † ; M) given any mechanism M is well defined.

15 An ex-ante allocation constraint is an upper bound on the probability that the agent will receive the item, in expectation over

all sources of randomness including the agent’s own type.

Copyright © 2024
54 Copyright for this paper is retained by authors
 Remark: Relationship to Correlation Gap. Note that the technique of correlation gap (Yan, 2011;
Alaei et al., 2013) for obtaining the approximation of e/(e − 1) does not apply here directly since the buyers does
not satisfy the expected utility representation given the allocation and payment rules, and the ex-ante optimal
mechanisms for each agent offers complex menus instead of posting prices.
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Remark: Continuous versus Discrete Type Distributions. Our analysis above introduces runtime
a dependency on η, the maximum density of the conditional participation cost in type distribution F̄ . This
dependency arises because of errors in estimated agent utility that are introduced when rounding values to the
nearest multiples of ϵ, which was needed to define our dynamic program over allocation rules. Of course, η is
well-defined only for continuous type distributions. Alternatively, if each agent i’s type distribution were listed
explicitly as a discrete set of types Ti and their associated probabilities, then instead of rounding values to multiples
of ϵ we could replace the value grid Ψ0 with the (at most) |Ti | values in the support of agent i’s distribution.
Doing so would remove the errors in our utility estimates (since we are using the exact values) and therefore
avoid any dependency on η. However, this introduces a polynomial runtime dependence on maxi |Ti | since our
dynamic program for agent i will need to include |Ti | values. Also, since the distribution is not continuous it
might happen that there is a non-vanishing fraction of agent types who are indifferent between participating and
not participating in the resulting allocation rule, but in this case the rule can be perturbed by an arbitrarily
small amount to make the participation probability unambiguous. The end result is that in Theorem 6.1 we could
replace η with maxi |Ti | if each distribution F̄i is a discrete distribution over Ti types.

6.2 Approximate Optimality of Posted Pricing In this section, we show that with additional assumptions
on buyers’ type distributions, sequential posted pricing is approximately optimal for revenue maximization. The
following lemma provides a reduction framework for single-item environments that lifts approximation results
for posted pricing from a single buyer to multiple buyers, and so avoids the direct analysis of interaction among
different buyers.

Lemma 6.2. (Feng et al., 2020) For a single-item environment, if there exists γ ≥ 1 such that for each buyer
i, for any constraint on the sale probability qi ≤ 1, the approximation ratio of (possibly randomized) posted pricing
for the single-buyer problem given sale probability constraint qi is at most γ, then the approximation ratio of
sequential posted pricing is at most γe/(e − 1) for the multi-buyer problem.

Note that when agents have private participation costs, it is important to specify the timeline for the agents to
make participation decisions, as different timeline will affect the equilibrium choice of the agents for participation.
In this section, for sequential posted pricing mechanisms, we assume that each agent only needs to make the
participation decision after seeing the realized price offered by the seller.
Since Lemma 6.2 allows us to reduce the analysis to the single-buyer problem with allocation constraints, in
the following two Lemmas, we will prove such approximation results for both independent participation costs and
perfectly correlated participation costs. Both of the proofs are provided in Section D.3.

Lemma 6.3. In the single-buyer setting with independent and non-negative participation costs, if the value
distribution F has decreasing marginal revenue and bounded support, for any mechanism that sells the item
with probability q ∈ [0, 1], there exists a (possibly randomized) posted price mechanism with weakly higher expected
revenue that sells the item with probability at most q.

Lemma 6.4. In the single-buyer setting with the participation cost being a non-negative and concave function of
v, for any mechanism that sells the item with probability q ∈ [0, 1], there exists a (possibly randomized) posted
price mechanism with at least half of the expected revenue that sells the item with probability at most q.

Combining Lemma 6.2 with Lemmas 6.3 and 6.4, we have the following approximation result.

Theorem 6.2. In the multi-buyer setting, if for each buyer both the participation cost is non-negative and either
of the following holds:
• the participation cost is independent of the value, and the value distribution F has decreasing marginal
revenue and bounded support; or

Copyright © 2024
55 Copyright for this paper is retained by authors
 • the participation cost is a concave function of the value;
then there is a sequential posted pricing mechanism that generates at least a 21 (1 − 1/e) fraction of the optimal
revenue. If the former condition holds for each buyer, then the guaranteed fraction of the optimal revenue is
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

1 − 1/e.

7 Discussions
In this paper we characterize the optimal mechanisms when buyers have private participation costs, show how to
compute approximately revenue-optimal mechanisms in polynomial time, and provide sufficient conditions on the
value distributions or the cost distributions such that posted pricing is optimal or approximately optimal. In this
section, we will provide further discussions on the alternative models for costly participation and the remaining
open questions.

7.1 Alternative Communication Models In this paper we focus on the class of sequential opt-out-or-
revelation mechanisms, in which the seller has the capability to send messages to the buyers before they choose
whether to participate. This advance communication is useful for coordinating the buyers’ participation decisions.
One might naturally wonder about alternative models that differ in how much communication is allowed before
participation decisions are made. We enumerate some possibilities here, each suitable for different applications.
Two-Way Communication. The buyers and the seller can communicate repeatedly in an unrestricted
manner before participation decisions are made. For example, the seller can elicit private value and cost
information from the buyers and provide recommendations for participation. A generalized revelation principle
by Myerson (1982) is applicable in this context.
One-Way Communication. The seller can send messages to the buyers before participation decisions are
made, but a buyer cannot communicate with the seller before paying the cost of participation. The sequential
opt-out-or-revelation mechanisms studied in this paper fall within this model.
No Communication. Neither the seller nor the buyers can communicate prior to participation. All buyers
must make their participation decisions simultaneously. In this case, the classic revelation principle by Myerson
(1981) applies.

In the single-buyer setting, these three models coincide. As a result, all the results presented in Sections 4 and 5
apply seamlessly in any of these models. In the multi-buyer setting, however, a more restrictive communication
model reduces the space of feasible mechanisms, which has the potential to reduce optimal revenue. Nevertheless,
it turns out that the mechanisms we devised in Section 6 – which employ one-way communication – are also
approximately optimal with respect to the broader class of mechanisms in the two-way communication model.
This is because the approximation mechanisms we devised in Section 6 remain approximately optimal when
compared to the ex-ante relaxation benchmark. This benchmark serves as an upper bound for the optimal revenue
even in the two-way communication model. Therefore, the approximation mechanisms proposed in Section 6 are
still approximately optimal when two-way communication is allowed.
On the other hand, our designed mechanisms heavily rely on the ability to make sequential participation
decisions, rendering them infeasible in the no-communication model. An important future direction to explore
is whether it’s possible to compute an (approximately) optimal mechanism in the no-communication model for
multiple buyers in polynomial time. Additionally, it’s intriguing to investigate whether the revenue gap between
the no-communication model and the two-way communication model is at most a constant.

7.2 Open Questions Following our work, many interesting questions remain open even in the single-buyer
setting, including:
1. For the setting with independent item values and non-negative participation costs, is posted pricing a
constant approximation to the optimal revenue without additional assumptions?
2. Can the exact optimal mechanism be computed in time polynomial in the size of the support?
3. For multi-item settings (e.g., unit-demand valuations) with non-negative participation costs, do there exist
simple mechanisms (e.g., item pricing) that generate a constant fraction of the optimal revenue, under
assumption such as DMR or MHR on the item value distributions?

Copyright © 2024
56 Copyright for this paper is retained by authors
 References
Alaei, S. (2014). Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM
Journal on Computing, 43(2):930–972.
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Alaei, S., Fu, H., Haghpanah, N., and Hartline, J. (2013). The simple economics of approximately optimal
auctions. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 628–637. IEEE.

Alaei, S., Fu, H., Haghpanah, N., Hartline, J. D., and Malekian, A. (2012a). Bayesian optimal auctions via
multi-to single-agent reduction. In 13th ACM Conference on Electronic Commerce, EC’12, page 17.

Alaei, S., Hajiaghayi, M., and Liaghat, V. (2012b). Online prophet-inequality matching with applications to ad
allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 18–35.

Ashlagi, I., Monachou, F., and Nikzad, A. (2021). Costly signaling with heterogeneous outside options. working
paper.

Babaioff, M., Gonczarowski, Y. A., and Nisan, N. (2017). The menu-size complexity of revenue approximation.
In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 869–877.

Babaioff, M., Immorlica, N., Lucier, B., and Weinberg, S. M. (2020). A simple and approximately optimal
mechanism for an additive buyer. Journal of the ACM (JACM), 67(4):1–40.

Basov, S. and Yin, X. (2010). Optimal screening by risk-averse principals. The BE Journal of Theoretical
Economics, 10(1).

Border, K. C. (1991). Implementation of reduced form auctions: A geometric approach. Econometrica, 59:1175–
1187.

Cai, Y., Devanur, N. R., and Weinberg, S. M. (2019). A duality-based unified approach to bayesian mechanism
design. SIAM Journal on Computing, STOC(16):160–200.

Celik, G. and Yilankaya, O. (2009). Optimal auctions with simultaneous and costly participation. The BE Journal
of Theoretical Economics, 9(1).

Champsaur, P. and Rochet, J.-C. (1989). Multiproduct duopolists. Econometrica, 57(3):533–557.

Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. (2010). Multi-parameter mechanism design and sequential
posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 311–320.
ACM.

Che, Y.-K. and Gale, I. (1998). Standard auctions with financially constrained bidders. The Review of Economic
Studies, 65(1):1–21.

Che, Y.-K., Kim, J., and Mierendorff, K. (2013). Generalized reduced-form auctions: A network-flow approach.
Econometrica, 81(6):2487–2520.

Cole, R. and Roughgarden, T. (2014). The sample complexity of revenue maximization. In Proceedings of the
46th Annual ACM Symposium on Theory of Computing (STOC), pages 243–252.

Deneckere, R. J. and McAfee, R. P. (1996). Damaged goods. Journal of Economics & Management Strategy,
5(2):149–174.

Devanur, N. R., Goldner, K., Saxena, R. R., Schvartzman, A., and Weinberg, S. M. (2020). Optimal mechanism
design for single-minded agents. In Proceedings of the 21st ACM Conference on Economics and Computation,
page 193–256.

Devanur, N. R., Huang, Z., and Psomas, C.-A. (2016). The sample complexity of auctions with side information.
In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 426–439.

Copyright © 2024
57 Copyright for this paper is retained by authors
 Devanur, N. R. and Weinberg, S. M. (2017). The optimal mechanism for selling to a budget constrained buyer:
The general case. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 39–40.
Feng, Y., Hartline, J., and Li, Y. (2020). Simple mechanisms for non-linear agents. arXiv preprint
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

arXiv:2003.00545.
Fiat, A., Goldner, K., Karlin, A. R., and Koutsoupias, E. (2016). The fedex problem. In Proceedings of the 2016
ACM Conference on Economics and Computation, pages 21–22.
Figueroa, N. and Skreta, V. (2009). The role of optimal threats in auction design. Journal of Economic Theory,
144(2):884–897.
Gershkov, A., Moldovanu, B., Strack, P., and Zhang, M. (2021). A theory of auctions with endogenous valuations.
Journal of Political Economy, 129(4):1011–1051.
Golrezaei, N., Jaillet, P., Liang, J. C. N., and Mirrokni, V. (2021a). Bidding and pricing in budget and roi
constrained markets. arXiv preprint arXiv:2107.07725.
Golrezaei, N., Lobel, I., and Paes Leme, R. (2021b). Auction design for roi-constrained buyers. In Proceedings of
the Web Conference 2021, pages 3941–3952.
Gonczarowski, Y. A. (2018). Bounding the menu-size of approximately optimal auctions via optimal-transport
duality. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 123–131.
Gonczarowski, Y. A. and Nisan, N. (2017). Efficient empirical revenue maximization in single-parameter auction
environments. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages
856–868.
Gonczarowski, Y. A. and Weinberg, S. M. (2018). The sample complexity of up-to-ε multi-dimensional revenue
maximization. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science
(FOCS), pages 416–426.
Guo, C., Huang, Z., and Zhang, X. (2019). Settling the sample complexity of single-parameter revenue
maximization. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), page
662–673.
Hart, S. and Nisan, N. (2017). Approximate revenue maximization with multiple items. Journal of Economic
Theory, 172:313–347.
Hartline, J., Mirrokni, V., and Sundararajan, M. (2008). Optimal marketing strategies over social networks. In
Proceedings of the 17th international conference on World Wide Web, pages 189–198.
Hartline, J. and Taggart, S. (2019). Sample complexity for non-truthful mechanisms. In Proceedings of the 20th
ACM Conference on Economics and Computation (EC), pages 399–416.
Hartline, J. D. and Roughgarden, T. (2009). Simple versus optimal mechanisms. In Proceedings of the 10th ACM
conference on Electronic commerce, pages 225–234.
Jebsi, K. and Thomas, L. (2006). Optimal pricing of a congestible good with random participation. Economics
Letters, 92(2):192–197.
Jehiel, P., Moldovanu, B., and Stacchetti, E. (1996). How (not) to sell nuclear weapons. The American Economic
Review, pages 814–829.
Jullien, B. (2000). Participation constraints in adverse selection models. Journal of Economic Theory, 93(1):1–47.
Krishna, V. and Perry, M. (1998). Efficient mechanism design. Available at SSRN 64934.
Lehmann, E., Parmentier, A., and Van der Linden, B. (2011). Optimal income taxation with endogenous
participation and search unemployment. Journal of Public Economics, 95(11-12):1523–1537.

Copyright © 2024
58 Copyright for this paper is retained by authors
 Li, Y. (2022). Selling data to an agent with endogenous information. In Proceedings of the 23rd ACM Conference
on Economics and Computation, pages 664–665.
Lucier, B., Pattathil, S., Slivkins, A., and Zhang, M. (2023). Autobidders with budget and roi constraints:
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Efficiency, regret, and pacing dynamics. arXiv preprint arXiv:2301.13306.

Menezes, F. M. and Monteiro, P. K. (2000). Auctions with endogenous participation. Review of Economic Design,
5:71–89.
Morgenstern, J. and Roughgarden, T. (2015). On the pseudo-dimension of nearly optimal auctions. In Proceedings
of the 29th Annual Conference on Neural Information Processing Systems (NIPS), pages 136–144.

Myerson, R. B. (1981). Optimal auction design. Mathematics of operations research, 6(1):58–73.

Myerson, R. B. (1982). Optimal coordination mechanisms in generalized principal–agent problems. Journal of
mathematical economics, 10(1):67–81.
Rochet, J.-C. and Stole, L. A. (2002). Nonlinear pricing with random participation. The Review of Economic
Studies, 69(1):277–311.
Roughgarden, T. and Talgam-Cohen, I. (2019). Approximately optimal mechanism design. Annual Review of
Economics, 11:355–381.
Saxena, R. R., Schvartzman, A., and Weinberg, S. M. (2018). The menu complexity of “one-and-a-half-
dimensional” mechanism design. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 2026–2035. SIAM.
Yan, Q. (2011). Mechanism design via correlation gap. In Proceedings of 22nd ACM Symposium on Discrete
Algorithms, pages 710–719.

Copyright © 2024
59 Copyright for this paper is retained by authors
 A A Generalized Revelation Principle
Let R̂ ≡ R2 ∪ {∅} be the augmented outcome space, where ∅ represents not participating the auction. Hence the
utility of any buyer i for outcome ∅ is 0.
For the private participation cost setting, consider any interactive protocol between the seller and the buyer.
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

For any i, let τi be the ith buyer that first interacts with the seller. Let Ei be the message the seller send to
buyer τi before the interaction. Similar to the argument in Myerson (1981), any mechanism can be transformed
into a generalized version of revelation mechanism M c : R2n → R̂n where all buyers participate the auction.
Moreover, conditional on information Ei , for any buyer τi and any (vτi , cτi ), if there exists (v−τi , c−τi ) such that
′
M((v
c τ , v−τ ), (cτ , c−τ )) = ∅, then M((v
i i i i
c τ , v−τ
i i
′
), (cτi , c′−τi )) = ∅ for all (v−τ i
, c′−τi ). Note that since the buyers’
utility conditional on participation is invariant of the participation cost, for any buyer τi with value vτi , for any
pair of participation cost (cτi , c′τi ) such that M((v
c τ , v−τ ), (cτ , c−τ )) ̸= ∅ and M((v
i i i i
c τ , v−τ ), (c′ , c−τ )) ̸= ∅ for
i i τi i
some (v−τi , c−τi ), we have
h i
Ev−τi ,c−τi uτi (M((v
c τ , v−τ ), (cτ , c−τ ))) | Ei
i i i i
h i
′
= Ev−τi ,c−τi uτi (M((vc τ , v−τ ), (cτ , c−τ ))) | Ei .
i i i i

Finally, it is sufficient to show that this mechanism can be implemented as a sequential opt-out-or-revelation
mechanism in our setting. For any order i and corresponding buyer τi , let F̄τ′i be the distribution over (vτi , cτi )
conditional on M((vc τ , v−τ ), (cτ , c−τ )) = ∅ for some (equivalently all) (v−τ , c−τ ). Moreover, let Gτ (vτ ) be
i i i i i i i i

the distribution over participation costs cτi conditional on value vτi and M((v
c τ , v−τ ), (cτ , c−τ )) ̸= ∅ for some
i i i i
(equivalently all) (v−τi , c−τi ). Recall that R̄ ≡ R ∪ {ψ} is the augmented report space where ψ represents not
participating the auction. Let M be the sequential opt-out-or-revelation mechanism that interacts with buyers
according to order τ , sends information Ei to buyer τi before the interaction, and maps the reported valuations
to the profile of allocations and payments constructed as follows. For any buyer τi not participating the auction,
or equivalently reporting ψ, the allocation and payment for buyer i is zero. Moreover, when buyer i reports ψ,
mechanism M resamples (vτi , cτi ) according to distribution F̄τ′i , and when buyer i reports vτi , mechanism M
resamples cτi according to distribution Gτi (vτi ). Then mechanism M runs M c on the generated type profile of all
n buyers. It is easy to verify that for the mechanism M, there exists an equilibrium where each buyer participates
(i.e., does not play ψ) in M and reports truthfully on her valuation if and only if her outcome is not ∅ in M. c
Moreover, under mechanism M, this equilibrium generates the same distribution over outcomes for all buyers as
the truthful equilibrium of M, c and therefore the same revenue as in M.
c

B Missing Proof for Characterization and Computation

Lemma 3.3. Given any distribution F̄ with marginal cost distribution G, and any mechanism M with allocation
x and payment rule p with parameter p0 , the revenue of the seller is
 
Rev(F̄ ; M) = Ec∼G Ev∼F̄c [xc (v)ϕc (v)] − (1 − F̄c (vx (c))) · max{−p0 , c} .

Proof. For any participation cost c, the buyer with cost c participates in the mechanism if and only if v ≥ vx (c).
First we consider the case cR+ p0 > 0, in which case vx (c) R v > 0. Moreover, the payment of a buyer having any
v
value v ≥ vx (c) is v · x(v) − 0 x(z) dz + p0 = v · xc (v) − 0 xc (z) dz − c, and the payment of a buyer having any
value v < vx (c) is 0 since such a buyer does not participate the auction. This is illustrated in Figure 1. Note that
by Myerson (1981), we have
 Z v 
Ev∼F̄c v · xc (v) − xc (z) dz = Ev∼F̄c [xc (v)ϕc (v)]
0

and thus the expected revenue given cost c ≥ −p0 is

 Z v 
Ev∼F̄c v · xc (v) − xc (z) dz − c · 1 [v ≥ vx (c)]
0
= Ev∼F̄c [xc (v)ϕc (v)] − (1 − F̄c (vx (c))) · c,

Copyright © 2024
60 Copyright for this paper is retained by authors
 R v For the case c ≤ −p0 , we have
where 1 is the indicator function. R v vx (c) = 0. Thus the payment of a buyer having
any value v ≥ 0 is v · x(v) − 0 x(z) dz + p0 = v · xc (v) − 0 xc (z) dz + p0 , and again by Myerson (1981), the
expected revenue given cost c is
 Z v 
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Ev∼F̄c v · xc (v) − xc (z) dz + p0 = Ev∼F̄c [xc (v)ϕc (v)] + p0 .

0
Taking expectation over c ∼ G gives us the desired characterization.
Rv
Lemma 3.4. For any mechanism with allocation and payment x, p such that p(v) = vx(v) − 0 x(z) dz + p0 for
some constant p0 , there
R v exists another mechanism with allocation and payment x̂, p̂ with weakly higher revenue
and p̂(v) = vx̂(v) − 0 x̂(z) dz + p̂0 where p̂0 ≥ 0. This can be strengthened to p̂0 = 0 if the participation costs are
non-negative.
Rv
Proof. Suppose first that p0 < 0. Given any allocation x and letting v ′ = supv {v · x(v) − 0 x(z) dz ≤ p0 }, define
(
x(v) v ≥ v ′
x̂(v) =
x(v ′ ) v < v ′ ,
Z v
p̂(v) = vx̂(v) − x̂(z) dz.
0
One can verify that the revenue of the seller is weakly higher with allocation x̂ and payment p̂ since the types in
mechanism with x and p with negative payment will not participate under the new mechanism while the types
with positive payment will participate and pay the same amount.
When p0 > 0 and the participation costs are non-negative, given any allocation and payment x, p, we can
instead define
( Rv
x(v) v ≥ supv { 0 x(z) dz ≤ p0 }
x̂(v) = Rv
0 v < supv { 0 x(z) dz ≤ p0 },
Z v
p̂(v) = vx̂(v) − x̂(z) dz.
0
The revenue of the seller is then unchanged if we use the mechanism with allocation x̂ and payment p̂, instead of
x and p, since all types of the buyer have the same allocation and payment in best response.
Lemma 4.1. Let (Ω, F, P ) be any probability measure, and let t1 , t2 : Ω → R2 be two 2-dimensional random
variables. If supω∈Ω ∥t1 (ω) − t2 (ω)∥∞ ≤ ϵ, then |OPT(t1 ) − OPT(t2 )| ≤ 3ϵ, where OPT(tk ) is the optimal
expected revenue when the valuation and participation cost follow the same distribution as the random variable tk .
Proof. Due to the symmetry between t1 and t2 , it is sufficient to show that OPT(t1 ) − OPT(t2 ) ≤ 3ϵ. For
simplicity, we write tk (ω) for the pair (vk (ω), ck (ω)). Note that by Lemma 3.2, it is sufficient to assume
x(v), p(v) are the
R v optimal allocation and payment function with parameter p0 . Let x̂(v) = x(v + ϵ) and
p̂(v) = vx̂(v) − 0 x̂(z) dz − 2ϵ + p0 . Next we show that Rev(t2 ; x̂, p̂) ≥ OPT(t1 ) − 3ϵ. Since x̂ is non-decreasing, x̂
and p̂ are incentive compatible for the buyer without participation cost, and the buyer will truthfully reveal her
valuation to the mechanism if the utility for participation is at least her participation cost. Note that
Z v Z v
p̂(v) = vx̂(v) − x̂(z) dz − 2ϵ + p0 = vx(v + ϵ) − x(z + ϵ) dz − 2ϵ + p0
0 0
Z v+ϵ Z v+ϵ
= vx(v + ϵ) − x(z) dz − 2ϵ + p0 ≥ vx(v + ϵ) − x(z) dz − 3ϵ + p0
ϵ 0
= p(v + ϵ) − 3ϵ.
The above inequality holds since x(z) ≤ 1 for any z. Moreover, we have
Z v Z v
u(v; x̂, p̂) = x̂(z) dz + 2ϵ + p0 = x(z + ϵ) dz + 2ϵ + p0
0 0
Z v+ϵ
≥ x(z) dz + ϵ + p0 = u(v + ϵ; x, p) + ϵ
0

Copyright © 2024
61 Copyright for this paper is retained by authors
 where the inequality holds again because x(z) ≤ 1 for any z. Finally, combining the inequalities, we have
Z
Rev(t2 ; x̂, p̂) = p̂(v2 (ω)) · 1 [u(v2 (ω); x̂, p̂) ≥ c2 (ω)] dP (ω)
Ω
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Z
≥ (p(v2 (ω) + ϵ) − 3ϵ) · 1 [u(v2 (ω) + ϵ; x, p) + ϵ ≥ c2 (ω)] dP (ω)
ZΩ
≥ (p(v1 (ω)) − 3ϵ) · 1 [u(v1 (ω); x, p) ≥ c1 (ω)] dP (ω) ≥ OPT(t1 ) − 3ϵ.
Ω

The first inequality holds by combining the above inequalities, and the second inequality holds since
∥t1 (ω) − t2 (ω)∥∞ ≤ ϵ and both p and u are monotone in v.

Lemma 4.2. For any distribution F̄ supported on [0, 1]2 and for any pair of mechanisms M and M c with allocation
rules x and x̂ such that x(v) ∈ [x̂(v), x̂(v) + ϵ] for all ϵ, we have Rev(F̄ ; M) ≥ Rev(F̄ ; M)
c − ϵ.

Proof. Let p, p̂ and u, û be the payment functions and utility functions in mechanisms M and M
c respectively.
By Lemma 3.2, we have
Z v Z v
p(v) = vx(v) − x(z) dz ≥ vx̂(v) − (x(z) + ϵ) dz ≥ p̂(v) − ϵ
0 0

and
Z v Z v
u(v) = x(z) dz ≥ x̂(z) dz = û(v).
0 0

For any type with value v and participation cost c, since the utility for participation is higher in mechanism M,
the agent has incentive to participate in mechanism M only if he also has incentive to participate in mechanism
M.
c Moreover, the payment difference is at most ϵ. Combining the observations, the expected revenue loss of
mechanism M is at most ϵ.
Theorem B.1. For selling a single item to a single buyer with private participation cost, when the size of the
support for the cost distribution is d, the menu size required for the optimal mechanism is at most 2d + 1.
Proof. Suppose the support of the cost distribution is {c1 , . . . , cd } where cj < cj+1 for any 1 ≤ j ≤ d − 1.
By Lemma 3.2, it is without loss to consider a single allocation rule and a corresponding incentive compatible
payment rule and let the buyer decide whether to participate or not and, contingent on participation,
R v choose her
desired allocation and price. Suppose x∗ is the optimal allocation function and p∗ (v) = vx∗ (v) − 0 x∗ (z) dz + p∗0
is the corresponding payment. Recall that vx∗ (c) is the threshold value at which a buyer with participation cost
c will participate in the mechanism with allocation rule x∗ . Define c0 ≡ −p∗0 and vx∗ (c0 ) ≡ 0. Note that for any
allocation x satisfying
Z vx∗ (cj+1 ) Z vx∗ (cj+1 )
(B.1) x(z) dz = x∗ (z) dz
vx∗ (cj ) vx∗ (cj )

for all j ∈ {0, . . . , d − 1}, the cutoff value for the buyer to participate the auction vx∗ (cj ) is not affected for
any j ∈ {1, . . . , d}. Thus it is sufficient to consider the optimization problem between vx∗ (cj ) and vx∗ (cj+1 )
respectively for any j ∈ {0, . . . , d − 1}. Note that the allocation x must be non-decreasing between vx∗ (cj ) and
vx∗ (cj+1 ), and satisfy the integration constraint in Equation (B.1). Thus the revenue maximization problem is
reduced to maximizing the expected virtual value xc (v)ϕc (v) for values between vx∗ (cj ) and vx∗ (cj+1 ), subject
to the integration constraint for the allocation rule. This is mathematically equivalent to solving a revenue
maximization problem subject to a public budget constraint, which is also virtual value maximization subject to
an integration constraint on the allocation rule. In Devanur and Weinberg (2017), the authors have shown that
the menu size of the optimal mechanism for this optimization problem is at most 2. Thus we need at most 2d
menu entries for d separate programs to optimize the allocation below the cutoff vx∗ (cd ). Note that for optimizing
the allocation above the cutoff vx∗ (cd ), the integration constraint is not required, and similar to Myerson (1981),
a single menu entry is sufficient for the revenue maximization problem with linear buyers. Thus in total the menu
size required is at most 2d + 1.

Copyright © 2024
62 Copyright for this paper is retained by authors
 Before the proof of Theorem 4.3, we first show that the difference in optimal revenue is small when the
estimation error on the discrete probability distribution is small.
Lemma B.1. Let T ⊆ [0, 1] × [0, 1] be a set with finite size, and let F̄1 , F̄2 be two distributions supported on T . If
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

maxt∈T F̄1 (t) − F̄2 (t) ∞ ≤ ϵ, then |Rev(F̄1 ; M) − Rev(F̄2 ; M)| ≤ |T | · ϵ for any mechanism M with non-negative
payment.
Proof. Again it is sufficient to show that Rev(F̄1 ; M) − Rev(F̄2 ; M) ≤ |T | · ϵ, and the case for Rev(F̄1 ; M) −
Rev(F̄1 ; M) ≤ |T | · ϵ holds symmetrically. Note that
X
Rev(F̄1 ; M) − Rev(F̄2 ; M) = Rev(t; M)(F̄1 (t) − F̄2 (t)) ≤ |T | · ϵ
t∈T

since Rev(t; M) ≤ 1 for any t ∈ T by individual rationality. Hence Lemma B.1 holds.
Theorem B.2. For selling a single item to a single buyer with private participation cost, for any constant ϵ > 0,
if the joint distribution F̄ is supported on [0, 1] × [0, 1], there exists a mechanism with access to O(ϵ−6 log ϵ−1 )
samples that obtains expected revenue at least OPT(F̄ ) − ϵ.
Proof. For any joint distribution F̄ , we construct the discrete distribution F̄ ′ supported on the grid with
increment 6ϵ in support [0, 1] × [0, 1] by rounding down the value and rounding up the participation cost to
the discretized points. By Lemma 4.1, we have OPT(F̄ ′ ) ≥ OPT(F̄ ) − 2ϵ .
Note that the size of the support of distribution F̄ ′ is 36ϵ−2 . We construct the distribution F̄ ′′ by rounding
down the value and rounding up the participation cost to the multiples of 6ϵ for any sample t ∼ F̄ .16 Note that
it is easy to verify that F̄ ′′ is the empirical distribution for F̄ ′ . Moreover, for any t in the support of distribution
ϵ3
F̄ ′ , by Hoeffding’s inequality (Lemma F.1), with O(ϵ−6 log ϵ−1 ) samples, |F̄ ′ (t) − F̄ ′′ (t)| ≤ 288 with probability
ϵ3 ϵ3
at least 1 − 288 . By union bounds, with probability at least 1 − 8ϵ we have that |F̄ ′ (t) − F̄ ′′ (t)| ≤ 288 for all t
in the support of distribution F̄ . Let M be the optimal mechanism for empirical distribution F̄ and let M′ be
′ ′′

the optimal mechanism for distribution F̄ ′ . By Lemma 3.4, both M and M′ have non-negative payment, and
ϵ ϵ
Rev(F̄ ; M) ≥ Rev(F̄ ′ ; M) ≥ (1 − )(Rev(F̄ ′′ ; M) − )
8 8
ϵ ϵ
≥ OPT(F̄ ′′ ) − ≥ Rev(F̄ ′′ ; M′ ) −
4 4
ϵ ϵ ϵ ϵ
≥ (1 − )(Rev(F̄ ′ ; M′ ) − ) − ≥ OPT(F̄ ′ ) − ≥ OPT(F̄ ) − ϵ.
8 8 4 2
The first inequality holds since decreasing the value and increasing the participation cost weakly decreases the
expected revenue of the mechanism. The second and the fifth inequalities hold by applying Lemma B.1 and the
ϵ3
observation that with probability at least 1 − 8ϵ , we have that |F̄ ′ (t) − F̄ ′′ (t)| ≤ 288 for all t in the support of
distribution F̄ ′ .

C Missing Proofs for Pricing in Single-Buyer Setting

Lemma 5.1. If the valuation distribution F has decreasing marginal revenue, then for any c ≥ 0 and any v ≥ c,
we have that f (v)(ϕ(v) − c) is monotone non-decreasing in v.
Proof. If f ′ (v) ≤ 0, we have
∂f (v)(ϕ(v) − c) ∂f (v)ϕ(v)
= − f ′ (v) · c ≥ 0.
∂v ∂v
If f ′ (v) > 0, we have
∂f (v)(ϕ(v) − c) ∂f (v)(v − c) − (1 − F (v))
= = f ′ (v)(v − c) + 2f (v) ≥ 0
∂v ∂v
where the inequality holds for v ≥ c.
16 To clarify, F̄ ′ rounds the true underlying distribution to the discrete support while F̄ ′′ rounds the empirical distribution to the

discrete support.

Copyright © 2024
63 Copyright for this paper is retained by authors
 x̂(v)
1
x(v)
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

0 µ vc (x̂) v̄

Figure 2: Given any allocation rule x(v) (dashed line), x̂ (solid line) is the allocation rule for a posted price
R v̄ R v̄
mechanism such that 0 x(v) dv = 0 x̂(v) dv. The area of the shaded region is c.

Theorem C.1. With independent values and participation costs, and with non-negative participation costs, if the
value distribution F has decreasing marginal revenue and bounded support,17 there exists a revenue-maximizing
mechanism that is a posted price mechanism.

Proof. Here we will prove the result for a slightly more general setting, where the participation costs can be
correlated with the values, but the conditional value distribution F̄c has identical and bounded support, and has
decreasing marginal revenue for any participation cost c.
Denote the value upper boundR v̄ by H < ∞. For any allocation rule x and associated payment rule p, let
v̄ = supv≤H {x(v) < 1}, and µ = 0 (1 − x(z)) dz. Note that µ is finite since H < ∞. Let
(
1 v≥µ
(C.2) x̂(v) =
0 v < µ.

Allocation rule x̂ is illustrated in Figure 2. For any participation cost c, it is easy to verify that
(
1 v ≥ vc (x̂)
x̂c (v) =
0 v < vc (x̂).
RH RH Rv Rv
where vc (x̂) = v̄ − µ + c. Moreover, 0 x(z) dz = 0 x̂(z) dz and 0 x(z) dz ≥ 0 x̂(z) dz for any v ∈ [0, H]. Thus
by Lemma 3.3, for any c ≥ 0, the revenue of mechanism with allocation x given participation cost c is
Z H
R(x; c) = Ev∼F [xc (v)ϕc (v)] − (1 − F̄c (vx (c))) · c = f¯c (v)(xc (v)ϕc (v) − c) dv
vx (c)
Z H
≤ f¯c (v)xc (v)(ϕc (v) − c) dv
vx (c)
H
Z v Z H Z v
= f¯c (v)(ϕc (v) − c) xc (z) dz − xc (z) dz d[f¯c (v)(ϕc (v) − c)]
0 vx (c) 0
v=vx (c)
H
Z v Z H Z v
≤ f¯c (v)(ϕc (v) − c) x̂c (z) dz − x̂c (z) dz d[f¯c (v)(ϕc (v) − c)]
0 vx̂ (c) 0
v=vx̂ (c)
Z H Z H
(C.3) = f¯c (v)x̂c (v)(ϕc (v) − c) dv = f¯c (v)(x̂c (v)ϕc (v) − c) dv = R(x̂; c).
vx̂ (c) vx̂ (c)

17 The boundedness assumption is to avoid a situation in which the optimal mechanism is not well defined, i.e., for any mechanism,

there exists another mechanism with strictly higher revenue. For example, if the buyer has participation cost 0, and the CDF of the
1
value is F (v) = 1 − v+1 for v ≥ 0, the supreme of the revenue is only attained in the limit by offering a take-or-leave-it price p → ∞.
Note that bounded support is a sufficient condition to guarantee this property, but it may not be necessary.

Copyright © 2024
64 Copyright for this paper is retained by authors
 The first inequality holds because c ≥ 0 and xc (v) ∈ [0, 1] for any v. The third and the fourth equalities hold by
integration by parts. The fifth equality holds because x̂c (v) = 1 for any v ≥ vx̂ (c). The second inequality follows
from the combination of two observations:
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

R v (c)
1. xc (v) = 0 for any v ≤ vx (c) and x̂c (v) = 0 for any v ≤ vx̂ (c). This further implies that 0 x xc (z) dz =
R vx̂ (c)
0
x̂c (z) dz = 0. Hence
H H
Z v Z v
f¯c (v)(ϕc (v) − c) xc (z) dz = f¯c (v)(ϕc (v) − c) x̂c (z) dz .
0 0
v=vx (c) v=vx̂ (c)

Rv Rv
2. By the construction of x̂, we have 0 x(z) dz ≥ 0 x̂(z) dz ≥ 0 for any v ≥ 0, which implies vx (c) ≤ vx̂ (c) for
any c. Moreover, by Lemma 5.1, f¯c (v)(ϕc (v) − c) is non-decreasing in v for any v ≥ vx̂ (c) ≥ c and v ≤ H.
Hence, we have
Z H Z v
xc (z) dz d[f¯c (v)(ϕc (v) − c)]
vx (c) 0
Z H Z v
≥ xc (z) dz d[f¯c (v)(ϕc (v) − c)]
vx̂ (c) 0
Z H Z v
≥ x̂c (z) dz d[f¯c (v)(ϕc (v) − c)]
vx̂ (c) 0
Rv
where the first inequality holds since vx (c) ≤ vx̂ (c), 0 x(z) dz ≥ 0 and f¯c (v)(ϕc (v) − c) is non-decreasing in
Rv Rv
v. The second inequality holds since 0 x(z) dz ≥ 0 x̂(z) dz and f¯c (v)(ϕc (v) − c) is non-decreasing in v.

Taking expectation over c, Theorem 5.1 holds.

Theorem C.2. With independent values and participation costs, and with non-negative participation costs, if the
value distribution F has monotone hazard rate, there exists a revenue optimal mechanism that is a posted price
mechanism.

Proof. For any allocation rule x(v), let c′ = inf c≥0 {ϕ(vx (c)) − c ≥ 0} and let v ′ = vx (c′ ). We first focus on the
case that both c′ and v ′ are finite, i.e., there exists c ≥ 0 such that ϕ(vx (c)) − c ≥ 0.18 For any allocation rule
x(v), let
(
1 v ≥ v′
x̂(v) =
x(v) v < v ′ .

Allocation x̂ is illustrated in Figure 3. By Lemma 3.3, since we set p0 = 0, the expected revenue of any mechanism
with allocation rule x from the buyer with participation cost c ≥ 0 is
Z ∞
Ev∼F [xc (v)ϕ(v)] − (1 − F (vx (c))) · c = f (v)(xc (v)ϕ(v) − c) dv.
vx (c)

We separate the discussion into two cases. For any participation cost c such that vx (c) ≤ v ′ , we have vx (c) = vx̂ (c).
In this case, since ϕ(v) ≥ 0 for any v ≥ v ′ , allocation x̂ only increases the allocation to types with positive virtual
value ϕ(v) compared to x, which increases the expected revenue. For any participation cost c such that vx (c) > v ′ ,
we have vx (c) ≥ vx̂ (c) > v ′ ≥ 0. In this case, for any ṽ ∈ [vx̂ (c), vx (c)], we have

ϕ(ṽ) − c ≥ ϕ(vx̂ (c)) − c ≥ ϕ(v ′ ) − c′ = 0,

18 Since the value is independent of the participation cost, the virtual value function is invariant of the participation cost of the

buyer.

Copyright © 2024
65 Copyright for this paper is retained by authors
 1
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

0 µ v ′ = v̄
Figure 3: Given any allocation rule x(v) (black dashed line), x̂ (red solid line) is the allocation rule that increases
the allocation to 1 for value aboves v ′ and x̂′ (blue dashed line) is the allocation rule that corresponds to posting
price µ. The two shaded regions in the figure have the same area.

where the first inequality holds since ṽ ≥ vx̂ (c). The second inequality holds because ϕ(v)−v is non-decreasing in v
due to the MHR assumption, and vx̂ (c) ≥ v ′ . Thus increasing the allocation to 1 for values between [vx̂ (c), vx (c)]
only weakly increases the revenue. Therefore, the mechanism with allocation rule x̂ generates weakly higher
revenue compared to x. R v̄
Let v̄ = supv {x̂(v) < 1 and F (v) < 1} and µ = 0 (1 − x(z)) dz. We claim that µ is finite. In the case that
v ′ is finite or the maximum value in the support is H < ∞, we have that v̄ ≤ min{v ′ , H} is finite, and hence µ
is finite. In the case that v ′ is infinite and v̄ is infinite, let m be the value such that ϕ(m) = 0.19 Suppose µ is
infinite. Then for sufficiently large c, we have

Z vx (c)
ϕ(vx (c)) − c ≥ vx (c) − m − c = c + (1 − x(z)) dz − m − c > 0
0

where the first inequality holds because ϕ′ (v) ≥ 1 since F is MHR, and the equality holds by the definition of
vx (c). The last inequality holds since because µ is infinite, for any m there exist a sufficiently large c such that
R vx (c)
0
(1 − x(z)) dz > m. Note that this contradicts to the condition that v ′ is infinite, and hence µ must be finite.
Let

(
1 v≥µ
x̃(v) =
0 v < µ.

This is well defined since µ is finite. Allocation x̃ is illustrated in Figure 3. For any participation cost c such that
vx̂ (c) ≥ v̄, we have that vx̂ (c) = vx̃ (c) and the revenues are the same for both mechanisms. For any participation
cost c such that vx̂ (c) < v̄, we have that c < c′ since vx̃ (c′ ) = vx (c′ ) = v ′ and v̄ ≤ v ′ . In this case, let ϕ̂ be
the virtual value function such that ϕ̂(v) = ϕ(v) − c if and only if ϕ(v) − c < 0, and ϕ̂(v) = 0 otherwise. By
Lemma 5.2, it is easy to verify that the valuation distribution with virtual function ϕ̂ has decreasing marginal

19 For an MHR distribution, the value m with virtual value zero is always finite (Hartline et al., 2008).

Copyright © 2024
66 Copyright for this paper is retained by authors
 revenue. we have that
Z v̄ Z ∞
R(x̂; c) = f (v)(x̂c (v)ϕ(v) − c) dv + f (v)(x̂c (v)ϕ(v) − c) dv
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

vx̂ (c) v̄
Z v̄ Z ∞
≤ f (v)x̂c (v)(ϕ(v) − c) dv + f (v)(x̃c (v)ϕ(v) − c) dv
vx̂ (c) v̄
Z v̄ Z v̄ Z ∞
= f (v)x̂c (v)ϕ̂(v) dv + f (v)(x̂c (v)(ϕ(v) − c − ϕ̂(v))) dv + f (v)(x̃c (v)ϕ(v) − c) dv
vx̂ (c) vx̂ (c) v̄
Z v̄ Z v̄ Z ∞
= f (v)x̂c (v)ϕ̂(v) dv + f (v)(x̃c (v)(ϕ(v) − c − ϕ̂(v))) dv + f (v)(x̃c (v)ϕ(v) − c) dv
vx̂ (c) vx̃ (c) v̄
Z v̄ Z v̄ Z ∞
≤ f (v)x̃c (v)ϕ̂(v) dv + f (v)(x̃c (v)(ϕ(v) − c − ϕ̂(v))) dv + f (v)(x̃c (v)ϕ(v) − c) dv
vx̃ (c) vx̃ (c) v̄

= R(x̃; c).

The first inequality holds because the allocation x̂c (v) ∈ [0, 1] for any v and x̂c (v) = x̃c (v) for any v ≥ v̄. The
third equality holds since ϕ(v) − c − ϕ̂(v) is non-negative, vx̃ (c) ≥ vx̂ (c), and ϕ(v) − c − ϕ̂(v) = 0 for any value
v ≤ vx̃ (c). The last statement holds because under allocation x̃, we have c′ − c = vx̃ (c′ ) − vx̃ (c) and hence
ϕ(v) − c ≤ ϕ(x̃(c)) − c ≤ ϕ(vx̃ (c′ )) − c′ = 0 for any value v ≤ x̃(c) since the valuation distribution is MHR.
The second inequality holds by applying Inequality (C.3) since ϕ̂ can be viewed as the virtual value function for
distribution with decreasing marginal revenue, and the allocation rules are converted through the same format.
Taking expectation over c, Theorem 5.2 holds.

Theorem C.3. If the participation cost cv is a non-negative and concave function of v, then for any value
distribution F , there exists a revenue optimal mechanism that is a posted price mechanism.

Proof. For any mechanism M, let v0 be the minimum value of any agent that participates the auction. Then
agents of this type will be indifferent between participating and not participating, and hence have utility u0 = cv0 .
Let x0 = uv00 .
Now consider the following alternative revenue maximization problem for a single buyer. This alternative
problem will have the same distribution over values as the original setting, but all participation costs are set
equal to 0. Instead of participation costs, we impose three constraints on the class of mechanisms that can be
used. First, the seller is constrained to only sell the item to agents with value above v0 subject to the incentive
constraint. Second, the allocation returned by the mechanism is constrained to be at least x0 . Third, the utility
of an agent with value v0 is constrained to be exactly u0 .
What is the revenue-optimal mechanism for this alternative problem? Since there are no participation costs,
a direct implication of Myerson (1981) is that the revenue optimal mechanism M′ in this alternative setting,
subject to the allocation and utility constraints, is a step function. Specifically, since the minimum allocation
is at least x0 , this corresponds to a mechanism with menu size 2, where one of the menu entries is (x0 , 0) and
the other is (1, p) with p ≥ v0 − u0 . The utility function of mechanism M′ is illustrated in Figure 4 as the red
solid line. Note that since mechanism M is also a feasible mechanism for this alternative revenue maximization
problem, we must have Rev(M) ≤ Rev(M′ ) (where revenue is calculated with respect to the new setting).
Now consider any mechanism that is feasible for the new setting. Since the participation cost cv is concave
in v, the utility of an agent participating in the mechanism with value v ≥ v0 is at least v · x0 ≥ cv . Therefore,
returning to the original problem formulation with participation costs, any agent with value v ≥ v0 (and hence
participation cost cv ) will choose participate in the auction in the original setting. This means that for both
M and M′ (both of which are feasible in the new setting), the revenue remains unchanged when executing
the mechanism in the original setting. This implies that in the original setting, Rev(M) ≤ Rev(M′ ). Finally,
since the payment for menu entry (x0 , 0) is 0, removing this entry from the mechanism M′ weakly improves the
expected revenue. The resulting mechanism is a posted-price mechanism. Hence, if the participation cost cv is
non-negative and concave in v, posted pricing is a revenue optimal mechanism.

Copyright © 2024
67 Copyright for this paper is retained by authors
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

u0

0 v0

Figure 4: The black (respectively red) solid curve is the utility function of the agent (without paying the cost)
given any mechanism M (respectively M′ ), and the black dashed curve is the participation cost function cv . All
three curves intersect at point (v0 , u0 ).

D Multi-buyer Setting
D.1 Non-Convexity When there are multiple buyers, a common approach in mechanism design is to represent
the mechanism by interim allocations and payments. In particular, let

xi (vi , ci ) ≜ Ev−i ,c−i [xi (v, c)] and pi (vi , ci ) ≜ Ev−i ,c−i [pi (v, c)] .

In Border (1991); Che et al. (2013), the authors provide sufficient and necessary conditions on the set of interim
allocations that are implementable. Then the revenue maximization problem can be formalized as the following
optimization program.
" #
X
max Ev,c pi (vi , ci )
x,p
i
s.t. xi (vi , ci ) · vi − pi (vi , ci ) ≥ xi (vi′ , c′i ) · vi − pi (vi′ , c′i ), ∀i, v, v ′ , c, c′
xi (vi , ci ) = pi (vi , ci ) = 0 or xi (vi , ci ) · vi − pi (vi , ci ) ≥ c, ∀i, v, c
x is implementable according to Border (1991).

It is easy to see that the above optimization problem is not a convex program. A natural conjecture is that
whether one could reformulate the problem such that it can be represented as a convex program. In the following
example, we show that this is not the case.

Example 3. There are two identical buyers. For each buyer, with probability 1, his value is 2 and his participation
cost is 1. In this case, the optimal mechanism is to sell the item to buyer 1 with price 1 (or sell the item to buyer
2 with price 1) with expected revenue 1. Note that this mechanism is asymmetric. In fact, for any symmetric
mechanism, the probability the item is sold to each buyer is at most 1/2, and to satisfy the individual rationality
constraint, the payment from each buyer is non-positive. Thus the revenue from the symmetric mechanism is at
most 0, which is smaller than the optimal revenue.

Note that if the environment is symmetric and the problem can be represented as a convex program, there
must exist a symmetric mechanism that is optimal. However, the above example illustrates that the optimal
mechanism is not symmetric for the multi-buyer setting in symmetric environments, which rules out the possibility
of restructuring the optimization program into a convex one. This observation illustrates a distinction between
our model and other inter-dimensional problems, where the optimization program for the latter cases are often
linear programs. Note that in general for non-convex programs, we cannot hope to derive succinct closed-form
solutions or compute it in polynomial time. However, for the problem of revenue maximization for buyers with
participation costs, we propose simple mechanisms that are approximately optimal under reasonable assumptions
on the distributions.

D.2 Missing Proofs for Computation Before the proof of Lemma 6.1, we introduce the following two
lemmas for bounding the discretization errors.

Copyright © 2024
68 Copyright for this paper is retained by authors
 Lemma D.1. For any product distribution F̄ = ×i=n F̄i with F̄i supported on [0, 1]2 , for any ϵ P ∈ (0, 1) and the
corresponding discretized distribution F̄ † , for any profile of ex-ante probabilities {qi }i∈[n] with i qi ≤ 1, there
exists another profile of ex-ante probabilities {qi† }i∈[n] in grid Ψ0 with i qi† ≤ 1 such that
P
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

[ † (F̄i† ) ≥
X X
OPT q OPTqi (F̄i ) − 5nϵ.
i
i∈[n] i∈[n]

Proof. Recall that F̄ ′ is the distribution that rounding the values down to the discretization grid Ψ0 . Let M, M′
and M† be the optimal mechanisms with allocation and payment rule (x, p), (x′ , p′ ) and (x† , p† ) under distributions
F̄i , F̄i′ and F̄i† .
First note that OPTqi (F̄i† ) ≥ OPTqi (F̄i′ ) since F̄i† is constructed by decreasing the participation cost compared
to F̄i′ . Next we bound the expected revenue loss between F̄i and F̄i′ given any ex-ante constraint qi . Consider a
random boosting zj drawn from the distribution over value difference within in interval [j · ϵ, (j + 1)ϵ) between
distributions F̄ and F̄ ′ for all j ≤ 1ϵ . Let M0 be the mechanism that announces the realization of zj for all j, and
then offer allocation x(j · ϵ2 + zj ) with payment p(j · ϵ2 + zj ) − x(j · ϵ2 + zj ) · zi if the buyer reports value j · ϵ2 .20
It is easy to verify that all values in the support of F̄i′ has incentives to report truthful in mechanism M0 , and
the expected allocation of mechanism M0 given F̄i′ coincide with the expected allocation of M given F̄i . Thus,

OPTqi (F̄i† ) ≥ OPTqi (F̄i′ ) ≥ Rev(F̄i′ ; M0 ) ≥ Rev(F̄i ; M) − max x(j · ϵ2 + zj ) · zj

j,zj

(D.4) ≥ Rev(F̄i ; M) − ϵ = OPTqi (F̄i ) − ϵ.

Now consider another mechanism M1 with parameter j ∗ such that for any value below j ∗ · ϵ2 , allocation x† is
rounded down to the multiples of ϵ, and for any value above j ∗ · ϵ2 , allocation x† is round up to the multiples
of ϵ. Allocation for value j ∗ · ϵ2 is rounded randomly. Parameter j ∗ and the rounding probability at j ∗ · ϵ2 is
chosen such that the ex-ante feasibility is preserved. Note that in M1 , the realization of the random rounding
] qi (F̄i† ) be the optimal revenue for distribution F̄i† given ex-ante constraint qi
is disclosed to the buyer. Let OPT
only using randomize over mechanisms with allocations on the discretized grid Ψ0 . We have

(D.5) ] qi (F̄i† ) ≥ Rev(F̄i† ; M1 ) ≥ Rev(F̄i† ; M† ) − ϵ = OPTqi (F̄i† ) − ϵ.

OPT

Given a profile of ex-ante constraints {qi }i∈[n] , there exists a profile over random ex-ante constraints
h {qi′ }i∈[n]
i
with corresponding fixed mechanisms Mi,qi′ that are qi′ feasible such that E[qi′ ] = qi and Eqi′ Rev(F̄i† ; Mi,qi′ ) =
] qi (F̄i† ). This is done by essentially examining the ex-ante allocation probability of each realized mechanism
OPT
for each buyer i, and rename that realized ex-ante allocation probability as variable q ′ . Moreover, consider
another
P profile of random ex-ante probabilities {q̃i }i∈[n] by rounding each realization of qi′ to the grid Ψ0 . We
have i∈[n] E[q̃i ] ≤ i∈[n] E[qi′ ] ≤ 1. Note that a feasible mechanism given ex-ante constraint q̃i is to offer the
P

mechanism Mi,qi′ with probability qq̃′′i and offer the mechanism with constant zero allocation and payment with
i

probability 1 − qq̃′′i where qi′′ is rounding qi up to the multiples of ϵ. The buyer is informed about which mechanism
i
is offered before participation. Note that in this construction, mechanism Mi,qi′ is also qi′′ feasible. Therefore,
given this randomized mechanism, the ex-ante sale probability is q̃i and the expected revenue is
 
[ q̃i (F̄i† ) ≥ Eq̃i ,q′ ,q′′ q̃i · Rev(F̄i† ; Mi,q′ ) ≥ Eq′ Rev(F̄i† ; Mi,q′ ) − 2ϵ · Rev(F̄i† ; Mi,q′ )
h i h i
Eq̃i OPT i i
qi′′ i i i i

h i
(D.6) ≥ Eqi′ Rev(F̄i† ; Mi,qi′ ) − 2ϵ = OPT ] qi (F̄i† ) − 2ϵ

where the second inequality holds since |qi′′ − q̃i | ≤ 2ϵ and the third inequality holds since Rev(F̄i† ; Mi,qi′ ) ≤ 1.
Note that given the distribution over ex-ante probabilities {q̃i }i∈[n] , to improve the sum of ex-ante revenue, we
can greedily select a deterministic profile of ex-ante probabilities {q̃i† }i∈[n] by ranking the realizations according

20 Mechanism M may be a distribution over mechanisms, and in this case, mechanism M is also a distribution over mechanisms
0
by applying this procedure for each realization of the mechanisms in M.

Copyright © 2024
69 Copyright for this paper is retained by authors
 [ q̃ (F̄ † )
OPT
to the ratio of realized i
q̃i
i
, with the exception that there may exist one buyer i∗ such that q̃i† is selected
randomly over two possible realizations. Note that q̃i† ∈ Ψ0 for any i ̸= i∗ since q̃i only randomize over ex-ante
probabilities in grid Ψ0 . Finally, by setting qi† = q̃i† for any i ̸= i∗ , and letting qi†∗ be the expected value of q̃i†
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

round down to multiples of ϵ, we have

h i h i
[ † (F̄i† ) ≥ [ † (F̄i† ) − ϵ ≥ [ q̃i (F̄i† ) − ϵ
X X X
OPT q Eq̃†∗ OPT q̃ Eq̃i OPT
i i i
i∈[n] i∈[n] i∈[n]

] qi (F̄i† ) − 3nϵ ≥ OPTqi (F̄i† ) − 4nϵ ≥

X X X
≥ OPT OPTqi (F̄i ) − 5nϵ
i∈[n] i∈[n] i∈[n]

where the last three inequalities are implied by inequalities (D.4), (D.5) and (D.6).

Lemma D.2. In the single-buyer setting, for
any distribution F̄ supported on Ψ0 × Ψ1 and any q ∈ [0, 1], there
exists an algorithm with running time poly 1ϵ that computes the mechanism with ex-ante sale probability at most
[ q (F̄i† ).
q that optimizes OPT

Proof. We first use dynamic program to compute the optimal revenue from fixed mechanisms for q in grid Ψ0 .
For i, j ≤ 1ϵ , k ≤ ϵ12 and s ≤ ϵ13 , let R(i, j, k, s) be the optimal revenue from types with value below i · ϵ when the
allocation and utility of value i · ϵ are j · ϵ and k · ϵ2 respectively, and the total ex-ante allocation probability for
types at most i · ϵ is at most s · ϵ3 . The optimal revenue from ex-ante constraint q is determined by the entry
maxj,k R( 1ϵ , j, k, ϵq3 ).
To simplify notation, let pi be the integer such that the probability of value i · ϵ in distribution F̄ is pi · ϵ, and
zij be the integer such that conditional on value, the probability such that the participation cost is at most j · ϵ2
is zij · ϵ. We initialize the matrix by R(1, j, k, s) = 0 for any k ≤ j and s ≥ pi · j · z1k , and R(1, j, k, s) = −∞
otherwise. For any i ≥ 2, we have

R(i, j, k, s) = max
′
R(i − 1, j ′ , k − j, s − pi · j · zik ) + qi · F̄i′ (k · ϵ2 ) · (i · j − k) · ϵ2 .
j ≤j

To interpret this expression, R(i − 1, j ′ , k − j, s − pi · j · zik ) is the revenue from types with values at most (i − 1)ϵ.
Note that the expected allocation from value (i − 1)ϵ is pi · j · zik the the utility is k · ϵ2 , and hence the total
ex-ante allocation from values at most (i − 1) · ϵ cannot exceed s − pi · j · zik . Moreover, the allocation of type
with value (i − 1)ϵ should not exceed the allocation of type with value i · ϵ, and hence the choice of j ′ is at most
j. Finally, when the allocation and utility of type with value i · ϵ are j · ϵ and k · ϵ2 respectively, by Lemma 3.2,
the utility of type with value (i − 1)ϵ is exactly (k − j)ϵ2 . This utility is independent of the choice of j ′ .
The second term is the expected revenue from types with value at most i · ϵ. Note that qi · F̄i′ (k · ϵ2 ) is the
total probability of those types that have incentives to participate in the auction, and (i · j − k) · ϵ2 is the payment
of those types, which is derived by subtracting the utility k · ϵ2 from the expected value i · j · ϵ2 , if they choose to
participate.
Finally, given any q ∈ [0, 1], it is sufficient to brute-force search for all pairs of ex-ante probabilities in grid
Ψ0 such that their convex combination coincides with q. This operation takes at most ϵ12 comparisons.

Lemma 6.1. For any ϵ̂ > 0, there exists an algorithm with running time poly nϵ̂ that computes a profile of

{qi† }i∈[n] subject to the constraint that i∈[n] qi† ≤ 1, and the corresponding mechanisms {Mi,q† }i∈[n] such that
P
i

{qi† }i∈[n] maximizes i∈[n] Rev(F̄i ; Mi,q† ) and

P
i

[ † (F̄i† ) − ϵ̂,
Rev(F̄i ; Mi,q† ) ≥ OPT ∀i.
i q i

Proof. First we compute the mechanism Mi,q† that generates revenue OPT [ † (F̄i† ) for any buyer i and qi† in grid
i qi
Ψ0 . By Lemma D.2 this requires nϵ̂ · poly 1ϵ̂ computations. For i ∈ [n] and j ∈ [⌊ 1ϵ̂ ⌋], let R(i, j) be the optimal

Copyright © 2024
70 Copyright for this paper is retained by authors
 [ j·ϵ̂ (F̄1† ) for
revenue from the first i buyers with total allocation probability j · ϵ̂. We initialize by R(1, j) = OPT
1
any j ∈ [⌊ ϵ̂ ⌋]. We set

R(i, j) = max [ (j−j ′ )·ϵ̂ (F̄i† ),

R(i − 1, j ′ ) + OPT ∀i ≥ 2, j ∈ [⌊ 1ϵ̂ ⌋].
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

′
j ≤j

The dynamic program takes at most ϵ̂13 operations. Therefore, we compute the profile of ex-ante probabilities
{qi† }i∈[n] in time poly nϵ̂ .

Note that directly running mechanism Mi,q† on the actual distribution F̄i for buyer i, rather than the rounded
i

distribution F̄i† , may violate the desired ex-ante constraint qi† . This is because the fraction of agents who opt out
of the mechanism may differ between qi† and F̄i , since our rounding of values can change the utility enjoyed by
the agent by as much as ϵ̂. However, since the density of the cost distribution is at most η, this change in utility
can influence the probability the item is sold by at most ηϵ̂, and hence the ex-ante probability the item is sold
given F̄i is at most qi† + ηϵ̂. Moreover, the revenue given F̄i is

[ † (F̄i† ) − ϵ̂.
Rev(F̄i ; Mi,q† ) ≥ OPT
i q i

D.3 Missing Proofs for Approximations of Pricing

Lemma 6.3. In the single-buyer setting with independent and non-negative participation costs, if the value
distribution F has decreasing marginal revenue and bounded support, for any mechanism that sells the item
with probability q ∈ [0, 1], there exists a (possibly randomized) posted price mechanism with weakly higher expected
revenue that sells the item with probability at most q.

Proof. For any mechanism with allocation rule x and sale probability q ≤ 1, construct the posted price mechanism
x̂ as in Equation (C.2). By Theorem 5.1, the revenue of the mechanism with allocation x̂ is weakly higher than
x. Next we consider two cases.
If the probability the item is sold given allocation rule x̂ is at most q, then x̂ is a feasible posted price
mechanism with higher revenue, which implies that Lemma 6.3 holds.
If the probability the item is sold given allocation rule x̂ is higher than q, then there exists an allocation
rule x̃ that posts (a possibly randomized) price higher than x̂ that sells the item with probability q. To prove
Lemma 6.3, it is sufficient to show that the per-unit price (expected payment divided by expected allocation)
charged in mechanism with allocation rule x̃ is always higher than x for any type of the buyer, since mechanism
with allocation rule x̃ sells the item with probability exactly q, while mechanism with allocation rule x sells the
item with probability at most q.
Note that by the definition of allocation
R v̄ rule x̃, the per-unit price charged under allocation rule x̃ is always
higher than x̂, where the latter equals 0 (1−x(z)) dz. For allocation rule x, if a type with value v ≤ v̄ participates
the auction, the per-unit price for this type is
Rv Z v Z v̄
vx(v) − 0 x(z) dz
≤v− x(z) dz ≤ (1 − x(z)) dz.
x(v) 0 0

Finally, for a type with value v > v̄ participating the

R v̄ auction, the per-unit price for this type equals that for a
type with value v̄, which is also upper bounded by 0 (1 − x(z)) dz.

Lemma 6.4. In the single-buyer setting with the participation cost being a non-negative and concave function of
v, for any mechanism that sells the item with probability q ∈ [0, 1], there exists a (possibly randomized) posted
price mechanism with at least half of the expected revenue that sells the item with probability at most q.

Proof. We first show that given any sale probability constraint q, the ex-ante optimal mechanism has menu
complexity of 3. Similar to the proof of Theorem 5.3, for any ex-ante feasible mechanism M, let v0 be the
minimum value of the agent that participates the auction with utility u0 , and let x0 = uv00 . Consider the following
revenue maximization problem without concerns for participation costs. The seller can only sell the item to agents

Copyright © 2024
71 Copyright for this paper is retained by authors
 with value above v0 subject to the incentive constraint and the sale probability constraint q. In addition, the
minimum allocation of the agent is x0 , and the utility of the agents with value v0 is u0 . It is easy to verify that by
Alaei et al. (2013), the revenue optimal mechanism M′ in this setting has at most two steps. Since the minimum
allocation is at least x0 , this corresponds to a mechanism with menu size 3. Moreover, one of the menu entries
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

is (x0 , 0). Note that this menu entry does not contribute to the expected revenue. Again similar to the proof of
Theorem 5.3, both M and M′ have the same revenue across the two settings, and hence in the original setting,
Rev(M) ≤ Rev(M′ ).
Now we focus our attention on the original setting. In mechanism M′ , for any menu entry (x, p) with p > 0,
let qx be the probability the agent chooses this menu entry in the ex-ante optimal mechanism. By definition we
have qx < q. Thus by posting price p to the agent, with probability qp ≥ qx , the agent will accept the price and
the expected revenue is at least p · qp ≥ p · qx . If qp ≤ q, then posting price p is feasible and generates higher
revenue than the contribution of the menu entry (x, p) in the ex-ante optimal mechanism. If qp > q, there exists
a higher price p̂ ≥ p such that the item is sold with probability exactly q. In this case, the revenue from posting
price p̂ is p̂q ≥ pq ≥ p · qx . Therefore, by posting the optimal price such that the item is sold with probability at
most q, the revenue is a 2-approximation to the ex-ante optimal.

E Negative Participation Costs

In this section, we show that posted pricing is approximately optimal when the participation cost can take negative
value with positive probability. Note that in this case, by Lemma 3.4, the parameter in the payment function
satisfies p0 ≥ 0.

Proposition E.1. For the single-buyer setting, if the conditional value distribution F̄c has identical and bounded
support, and has decreasing marginal revenue for any participation cost c, there exists a deterministic mechanism
with at least half of the optimal revenue.

Proof. Let H < ∞ be the maximum value of the buyer. For any allocation rule x and associated payment rule
with parameter p0 ≥ 0, let q be the probability
R v̄ the agent participates the auction given allocation and payment
x and p. Let v̄ = supv≤H {x(v) < 1}, µ = 0 (1 − x(z)) dz, and let
(
1 v≥µ
x̂(v) =
0 v < µ.

For any participation cost c, it is easy to verify that

(
1 v ≥ max{vc (x̂), µ}
x̂c (v) =
0 v < max{vc (x̂), µ},
RH RH
where vc (x̂) = 0 if c ≤ −p0 and vc (x̂) = v̄ − µ + c + p0 if c > −p0 . Moreover, 0 x(z) dz = 0 x̂(z) dz and
Rv Rv
0
x(z) dz ≥ 0 x̂(z) dz for any v ≥ 0. By Inequality (C.3), for any c ≥ 0, we have R(x, p0 ; c) ≤ R(x̂, p0 ; c). Next
we consider the case that c < 0. For the case that −p0 < c < 0, the revenue of mechanism with parameter p0 is
Z H
R(x, p0 ; c) = f¯c (v)xc (v)ϕc (v) dv − (1 − F̄c (vx (c))) · c
vx (c)
Z H
≤ f¯c (v)x̂c (v)ϕc (v) dv − (1 − F̄c (vx (c))) · c
vx̂ (c)
Z H
≤ f¯c (v)x̂c (v)(ϕc (v) − c) dv − (1 − F̄c (vx (c))) · c
vx̂ (c)

= R(x̂, p0 ; c) − (1 − F̄c (vx (c))) · c.

The first inequality holds by applying Inequality (C.3), and the second inequality holds since c < 0. Finally we
consider the case c ≤ −p0 . Here the buyer will always participate the auction for all values, vx (c) = vx̂ (c) = 0,

Copyright © 2024
72 Copyright for this paper is retained by authors
 and
Z H
R(x, p0 ; c) = f¯c (v)xc (v)ϕc (v) dv + p0
0
Downloaded 10/31/24 to [Link] . Redistribution subject to SIAM license or copyright; see [Link]

Z H
≤ f¯c (v)x̂c (v)ϕc (v) dv + p0 = R(x̂, p0 ; c),
0

and the inequality holds again by applying Inequality (C.3). Combining three cases and taking expectation over
c, we have

R(x, p0 ) = Ec∼G [R(x, p0 ; c)]

 
≤ Ec∼G [R(x̂, p0 ; c)] − Ec∼G (1 − F̄c (vx (c))) · c · 1 [−p0 < c < 0]
 
≤ R(x̂, p0 ) + Ec∼G (1 − F̄c (vx (c))) · p0 .
 
Note that the term of Ec∼G (1 − F̄c (vx (c))) · p0 = p0 ·q. Moreover, there exists a mechanism that charges price p0
for the item, and buyer participates in it with probability at least q. The revenue of this posted price mechanism
is at least p0 · q. Thus the revenue of allocation x with with parameter p0 ≥ 0 is upper bounded by twice of the
optimal revenue of posted pricing.

F Hoeffding’s inequality
Lemma F.1. (Hoeffding’s inequality) For any Bernoulli random variable with probability p for value 1, let
H(n) be the number of 1 values given n trials. For any ϵ > 0, we have
 
1
Pr H(n) − p ≥ ϵ ≤ 2 exp(−2ϵ2 n).
n

Copyright © 2024
73 Copyright for this paper is retained by authors