Robust Private Supply of a Public Good

Wanchang Zhang†*
arXiv:2201.00923v2 [[Link]] 5 Jan 2022

This Version: Dec 2021

First Draft: May 2021

Abstract

We study the mechanism design problem of selling a public good to a group of

agents by a principal in the correlated private value environment. We assume the
principal only knows the expectations of the agents’ values, but does not know the
joint distribution of the values. The principal evaluates a mechanism by the worst-
case expected revenue over joint distributions that are consistent with the known
expectations. We characterize maxmin public good mechanisms among dominant-
strategy incentive compatible and ex-post individually rational mechanisms for the
two-agent case and for a special N -agent (N > 2) case.

Keywords: Public good, mechanism design, information design, revenue

maximization, correlated private values, max-min, worst-case, dominant strategy
incentive compatible, ex-post individual rational, randomization, deterministic
mechanism, excludable good.

JEL Codes: C72, D82, D83.

†
Department of Economics, University of California, San Diego. Email: waz024@[Link]
*
I have benefited from discussions with Songzi Du and Joel Sobel.

1
1 Introduction
How should a profit-maximizing private sector sell a public good to a group of agents?
This question is explored by Güth and Hellwig (1986) in the independent private value
environment. However, in the real world, the private sector may not know the joint
distribution of the privates values. Instead, the private sector may form an overall
expectation about the market from, for example, the result of a market survey.
In this paper, we consider the problem of a monopolistic provider (referred to as the
principal ) selling a public good in the correlated private value environment when the principal
knows little of the information about the values of agents. Precisely, we assume the principal
only knows the expectations of the values of the agents, but does not know the joint
distribution of the values. The space of mechanisms is restricted to the set of dominant
strategy incentive compatible (DSIC) and ex-post individually rational (EPIR) mechanisms.
The principal evaluates a mechanism by its lowest expected revenue across all possible joint
distributions consistent with the known expectations, which will be referred to as its revenue
guarantee. The principal aims to find a mechanism, referred to as a maxmin public good
mechanism, that maximizes the revenue guarantee.
We observe that the principal’s problem can be interpreted as a zero-sum game between
the principal and adversarial nature. We will take the saddle point approach for our
results. Specifically, we will construct a saddle point, which is a pair of a mechanism
and a joint distribution, such that the mechanism maximizes the expected revenue over
all DSIC and EPIR public good mechanisms under the joint distribution, and the joint
distribution minimizes the expected revenue over all joint distributions consistent with
the known expectations under the mechanism. By the properties of a saddle point, the
mechanism is a maxmin public good mechanism. The joint distribution will be referred to
as a worst-case joint distribution.
Our main result offers a complete characterization of the maxmin public good mechanisms
and the worst-case joint distributions when there are two agents. We normalize the support
of each agent’s value to the unit interval [0,1]. Without loss, we assume that the expectation
of the value of agent 1 (m1 ) is weakly higher than that of the value of agent 2 (m2 ). We divide
the expectations into two cases and four areas (see Figure 1), and offer a characterization for
each case and for each area. Let us first discuss the symmetric cases where the expectations
are the same (m1 = m2 = m). For the maxmin public good mechanisms, the public good is
provided with a positive probability if and only if the sum of the reported values exceeds a
threshold. In addition, the provision rule1 is separable and strictly increasing in each agent’s
1
This is the probability that the public is provided given a reported value profile.

2
 m2
Case (I)
Case (II)
1 (1, 1)
Area (I)
Area (II)
Area (III) ( 34 , 43 )
Area (IV) (1, ln 2)

0
0 1 m1

Figure 1: For the symmetric case (m1 = m2 ), we divide the expectations into two regions:
the thick blue line is Case (I), and the thick black line is Case (II). For the asymmetric
case (m1 > m2 ), we use (the red curve) Boundary (I), (the gray curve) Boundary (II) and
(the green curve) Boundary (III) (the functional forms of these boundaries will be defined in
the main result) to divide the expectations into four regions: the light yellow area is Area
(I), the light gray area (including Boundary (II) ) is Area (II), the light red area (including
Boundary (I)) is Area (III) and the light green area (including Boundary (III)) is Area
(IV).

3
reported value. Moreover, the public good is provided with a probability of 1 when each
agent’s reported value is 1. When the symmetric mean is low (Case (I)), the value profiles
are divided into four regions and the provision rules are different across these regions. When
the symmetric mean is high (Case (II)), there is only one provision rule and it is linear in
each agent’s reported value. For the worst-case joint distribution, the support coincides with
the regions where the public good is likely to be provided. When the symmetric mean is low
(Case (I)), its marginal distribution is a combination of a uniform distribution and an equal
revenue distribution; its conditional distribution is some truncated Pareto distribution with
an atom on 1. When the symmetric mean is high (Case (II)), its marginal distribution is a
combination of a uniform distribution on [0,1) and an atom on 1; its conditional distribution
is some truncated Pareto distribution with an atom on 1.
Then let us briefly discuss the asymmetric cases2 where the expectation of the value of
agent 1 is higher than that of the value of agent 2 (m1 > m2 ). For the maxmin public
good mechanisms, the public good is provided with a positive probability if and only if the
sum of some weighted reported values exceeds a threshold. Other properties are similar to
those in the symmetric cases (albeit with a different functional form of the provision rule).
More specifically, when the expectations are close and low (Area (I)), the maxmin public
good mechanism share similar properties with that in Case (I); when the expectations are
close and high (Area (II)), the maxmin public good mechanism share similar properties with
that in Case (II). When the difference between the expectations are moderate, the value
profiles are divided into two regions and the provision rules are different across these regions.
When the difference between the expectations is high (Area (IV)), the maxmin public good
mechanism is a dictatorship mechanism where the provision rule is determined by agent 1’s
reported value only3 . Precisely, the public good is provided with a positive probability if
and only if the agent 1’s reported value exceeds a threshold w1 ∈ (0, 1]. In addition, the
provision probability is strictly increasing in agent 1’s reported value. Moreover, the public
good is provided with a probability of 1 when agent 1’s reported value is 1.
Now let us discuss the intuitions of maxmin public good mechanisms. First, the public
good will never be provided if the sum of (weighted) values falls short of some threshold
for the (a)symmetric cases. This is because the principal exercises monopoly power to
raise revenue. Second, the maxmin public good mechanisms require randomization to
hedge against uncertainty about the joint distribution. The exact functional form of the
randomization is solved by a complementary slackness condition stating that the revenue
2
We only discuss maxmin public good mechanisms here, and defer the details of worst-case joint
distributions to Section 6.
3
Equivalently, the weight on agent 2’s value is 0.

4
generated from a value profile is a linear function in the reported values for any value profile
in the support of the worst-case joint distribution. Indeed, this condition makes adversarial
nature indifferent to any feasible joint distribution whose support is the same as that of the
worst-case joint distribution. To construct the worst-case joint distribution, we first derive a
weighted virtual value for our environment so that the expected revenue can be expressed as
the inner product of the weighted virtual value and the provision rule. The worst-case joint
distribution is solved by a condition requiring the weighted virtual value is 0 for any value
profile in the support except for the value profile where each agent’s value is 1. The intuition
behind is that the principal is indifferent between providing and not providing the public
good for these value profiles. Indeed, this condition guarantees that principal is indifferent
to any feasible and monotone mechanism that provides the good with a positive probability
only if the value profile is inside the support and provides the good with probability of 1
when each agent’s value is 1.
These intuitions are useful to study the case when there are N > 2 agents. For a special
N-agent case where the symmetric expectation is high, we characterize the maxmin public
good mechanism and the worst-case joint distribution using the above conditions. We find
that the provision rule in the maxmin public good mechanism is no longer separable, but
admits a simple form: it is a polynomial function of the sum of the reported values. We
discuss the main difficulty for general cases when there are N > 2 agents in Section 7.1.
In addition, we characterize maxmin deterministic 4 public good mechanisms for the two-
agent case. There are practical concerns for studying deterministic mechanisms. To wit,
deterministic mechanisms are easier to understand and more practical than randomized
mechanisms in many situations, e.g., when the agents do not trust the randomization
device. We find that when agent 2’s expectation is low, the maxmin deterministic public
good mechanism is a dictatorship mechanism: agent 2’s reported value is irrelevant and
the public good is provided with probability of 1 if and only if agent 1’s reported value is
above a threshold. When agent 2’s expectation is high, we characterize the class of maxmin
deterministic public good mechanisms, including a linear mechanism where the public good is
provided with probability of 1 if and only if the sum of weighted reported value is above some
threshold and a posted price mechanism where the public good is provided with probability
of 1 if and only if each agent’s reported value is above some threshold.
Lastly, we consider the problem of providing an excludable good to N ≥ 2 agents. In
many situations, the principal can restrict access to the good for each agent, i.e., the provision
rule can be agent-specific. Examples of excludable goods include movies provided by a movie
theater and online courses provided by private educational institutions. We find that in the
4
The provision probability of the public good is either 0 or 1.

5
maxmin excludable good mechanism, the provision rule to each agent depends on the agent’s
reported value only. For the worst-case joint distribution, the marginal distribution for each
agent is some equal revenue distribution; the values across agents are independent.
The remaining of the paper proceeds as follows. Section 2 provides a literature review.
Section 3 presents the model. Section 4 presents preliminary analysis. Section 5 characterizes
the result for the two-agent symmetric cases. Section 6 characterizes the result for the
two-agent asymmetric cases. Section 7 characterizes maxmin mechanisms for a special N-
agent case, deterministic maxmin mechanisms for two-agent case and maxmin excludable
mechanisms for general N-agent cases. Section 8 is a conclusion. The Appendix A contains
details of the characterization of maxmin public good mechanisms and worst-case joint
distributions. All proofs are in the Appendix B and C.

2 Literature Review
This paper is closely related to a group of papers that study robust mechanism design in
different models, but all assume that the mechanism designer only knows the expectations of
the values and evaluates mechanisms under the worst-case criterion. Che (2020), Suzdaltsev
(2020) and Koçyiğit et al. (2020) consider a model of auction design. Che (2020) shows
that a second price auction with an optimal random reserve distribution is a maxmin
auction among a class of competitive mechanisms. Suzdaltsev (2020) characterizes a
linear version of Myerson’s optimal auction as a maxmin auction among deterministic
DSIC and EPIR mechanisms. Koçyiğit et al. (2020) study, among others, a setting with
symmetric expectations of bidders’ values and characterize a second price auction with a
random reserve as a maxmin auction among DSIC and EPIR mechanisms in which only the
highest bidder(s) can be allocated. Zhang (2021b) studies a model of bilateral trade and
characterizes maxmin trade mechanisms among DSIC and EPIR mechanisms. The maxmin
trade mechanism features a fixed commission rate and a uniformly random spread in the
symmetric case. Carrasco et al. (2018) study the problem of selling a single good to a buyer
and characterize maxmin selling mechanisms assuming the seller knows the first N moments
of the distribution, which includes known expectations assumption as a special case.
In addition, this paper is related to papers that assume the mechanism designer has
limited information about the joint distribution of values and evaluates the mechanism under
the worst-case criterion. Precisely, a set of papers assume the mechanism designer knows
the marginal distribution of values. Carroll (2017) studies a model of multi-dimensional
screening and finds separate screening is a maxmin mechanism. He and Li (2020) study
a model of auction and characterize, among other results, optimal random reserve for the

6
second price auction under certain conditions. Zhang (2021a) also studies the model of
auction and shows that, under different conditions, a second price auction with uniformly
distributed random reserve is a maxmin auction among DSIC and EPIR mechanisms for the
two-bidder case and a second price auction with Beta( N 1−1 , 1) distributed random reserve is
a maxmin auction among DSIC and EPIR mechanisms in which only the highest bidder(s)
can be allocated for the N-bidder case.
More broadly, this paper is related to a strand of papers that focus on the case where the
agents may have arbitrary high-order beliefs about each other unknown to the mechanism
designer, e.g., Bergemann and Morris (2005), Chung and Ely (2007), Chen and Li (2018),
Yamashita and Zhu (2018), Bergemann et al. (2016, 2017, 2019), Du (2018),Brooks and Du
(2021), Libgober and Mu (2021).

3 Model
We consider an environment where a single non-excludable public good is privately provided
to N ≥ 2 risk-neutral agents by a monopolistic provider5 . The cost of providing the public
good is normalized to 0. We denote by I = {1, 2, ..., N} the set of agents. Each agent i has
private information about her valuation for the public good, which is modeled as a random
variable vi with cumulative distribution function Fi 6 . We use fi (vi ) to denote the density
of vi in the distribution Fi when Fi is differentiable at vi ; We use P ri (vi ) to denote the
probability of vi in the distribution Fi when Fi has a probability mass at vi . We denote Vi
as the support of Fi . We assume each Vi is bounded. We assume the agents have a common
support. Then without loss of generality, we assume Vi = [0, 1] as a normalization. The
joint support of all Fi is denoted as V := ×N N
i=1 Vi = [0, 1] with a typical value profile v. The
joint distribution is denoted as F . We denote agent i’s opponent value profiles as v−i , i.e.,
v−i ∈ V−i := ×j6=i Vj .
The principal only knows the expectation mi of the private value of each agent i as
well as the support, but does not know the joint distribution of the values 7 . Formally, let
m := (m1 , m2 , · · · , mN ), and we denote by
Z
ΠN (m) = {π ∈ ∆V : ∀i ∈ I, vi π(v)dv = mi }

5
We will refer to the monopolistic provider as the principal.
6
We do not make any assumption on the distributions of these random variables. It could be continuous,
discrete, or any mixtures.
7
That is, except for the expectations, the designer know neither the marginal distributions nor the
correlation structure.

7
the collection of such joint distributions. We shall drop the subscript N when there is no
ambiguity.
The principal seeks a dominant strategy incentive compatible (DSIC) and ex-post
individually rational (EPIR) mechanism. A direct mechanism 8 (q, t) is defined as a provision
rule q : V → [0, 1] and a payment function t : V → RN where t(v) = (t1 (v), t2 (v), · · · , tN (v)).
With a little abuse of notations, each agent submits a report vi ∈ Vi to the auctioneer. Upon
receiving the report profile v = (v1 , v2 , · · · , vN ), the public good is provided with a probability
of q(v) ∈ [0, 1] and each agent i pays ti (v) ∈ R . The set of all DSIC and EPIR mechanisms
is denoted as DN when there are N agents. We shall drop the dependency of DN on the
number of agents N when there is no confusion. Formally, the mechanism (q, t) satisfies the
following constraints:

vi q(v) − ti (v) ≥ vi q(vi′ , v−i ) − ti (vi′ , v−i ) ∀i, v, vi′ (DSIC)

vi q(v) − ti (v) ≥ 0 ∀i, v (EPIR)

We are interested in the principal’s expected revenue in the dominant strategy equilibrium
in which each agent truthfully reports her valuation of the public good. Then the
expected revenue of a DSIC and EPIR mechanism (q, t) when the joint distribution is
R P
π is U((q, t), π) ≡ v∈V π(v) N
i=1 ti (v)dv. The principal evaluates each such mechanism
(q, t) by its worst-case expected revenue over the uncertainty of joint distributions that are
consistent with the known expectations. Formally, the principal evaluates a mechanism (q, t)
R P
by GR((q, t)) = inf π∈Π(m) v∈V π(v) N i=1 ti (v)dv, referred to as (q, t)’s revenue guarantee.
The principal’s goal is to find a mechanism with the maximal revenue guarantee among
DSIC and EPIR mechanisms. Formally, the principal aims to find a mechanism (q ∗ , t∗ ),
referred to as a maxmin public good mechanism, that solves the following problem:

sup GR((q, t)) (MPGM)

(q,t)∈D

We observe that the problem (MPGM) can be interpreted as a two-player sequential

zero-sum game. The two players are the principal and adversarial nature. The principal first
chooses a mechanism (q, t) ∈ D. After observing the principal’s choice of the mechanism,
adversarial nature chooses a joint distribution π ∈ Π(m). The principal’s payoff is
U((q, t), π), and adversarial nature’s payoff is −U((q, t), π). Now instead of solving directly
for such a subgame perfect equilibrium we can solve for a Nash equilibrium ((q ∗ , t∗ ), π ∗ ) of
8
It is without loss of generality to restrict attention to direct mechanisms since we focus on dominant
strategy mechanisms and therefore the Revelation Principle holds.

8
the simultaneous move version of this zero-sum game, which corresponds to a saddle point
of the payoff functional U, i.e.,

U((q ∗ , t∗ ), π) ≥ U((q ∗ , t∗ ), π ∗ ) ≥ U((q, t), π ∗ )

for any (q, t) and any π. The properties of a saddle point imply that the principal’s
equilibrium strategy in the simultaneous move game, (q ∗ , t∗ ), is also his maxmin strategy
(i.e. his equilibrium strategy in the subgame perfect equilibrium of the sequential game).
For our main result, we will explicitly construct a saddle point ((q ∗ , t∗ ), π ∗ ) for each given
expectation vector m for the two-agent case.

4 Preliminary Analysis
We use the following proposition to simplify the problem: its proof is standard but included
in the Appendix B for completeness.

Proposition 1 (Revenue Equivalence). Maxmin public good mechanisms have the following
properties:
1. q(·, v−i ) is nondecreasing in vi for all v−i .
Rv
2. ti (vi , v−i ) = vi q(vi , v−i ) − 0 i q(s, v−i )ds.

Proposition 1 is a version of Myerson (1981). The provision rule is monotonic and the
payment rule of the maxmin public good mechanisms can be characterized by the provision
rule only.
Now let us consider the problem that fixing any joint distribution π, the principal
designs an optimal mechanism (q, t). For exposition, we assume π is differentiable. We
denote the density of value profile v = (v1 , v2 , · · · , vN ) as π(v). We define πi (vi ) :=
R R1
[0,1] N−1 π(vi , v−i )dv−i . We define πi (v−i ) := 0
π(vi , v−i )dvi . We denote the density of vi
conditional on v−i as πi (vi |v−i ), the cumulative distribution function of vi conditional on
R
v−i as Πi (vi |v−i ) := si ≤vi πi (si |v−i )dsi . We define Πi (vi , v−i ) ≡ π(v−i )Πi (vi |v−i ). An direct
implication of Proposition 1 is that the expected revenue of (q, t) under the joint distribution
π is
XN Z
E[ ti (v)] = q(v)Φ(v)dv
i=1 v

where
N
X N
X
Φ(v) = π(v) vi − [πi (v−i ) − Πi (vi , v−i )]
i=1 i=1

9
We refer to Φ(v) as the weighted virtual value 9 when the value profile is v. Thus the problem
of designing an optimal mechanism given a joint distribution can be viewed as maximizing
the product of the provision rule and the weighted virtual values given that the provision
rule is feasible and satisfies the monotonicity condition stated in Proposition 1.
Next let us consider the problem that fixing any mechanism (q, t), adversarial nature
chooses a joint distribution π that minimizes the expected revenue. We observe this is a
semi-infinite dimensional linear program. By Theorem 3.12 in Anderson and Nash (1987),
we establish the strong duality, which implies the following lemma.

Lemma 1. If π is a best response for adversarial nature to a given mechanism (q, t), then
there exists some real numbers λ1 , · · · , λN , µ such that

N
X N
X
λi vi + µ ≤ ti (v) ∀v ∈ V (1)
i=1 i=1

N
X N
X
λi vi + µ = ti (v) ∀v ∈ supp(π) (2)
i=1 i=1

Here (1) is the feasibility constraint in the dual program; (2) is the complementary
slackness condition, which states that the revenue from the value profile v is some linear
function in each agent’s value if v belongs to the support of the worst-case joint distribution.

5 Symmetric Case
In this section, we focus on the two-agent symmetric case, i.e., N = 2 and m1 = m2 := m.
We divide m into two cases and then characterize the maxmin public good mechanism and
the worst-case joint distribution for each case.

5.1 Case (I): Low Expectations (m < 43 )

Symmetric Maxmin Public Good Mechanism (I)
Let v = (v1 , v2 ) be the reported value profile of the two agents. Let r1 be the solution to the
following equation:
r1 ln r1 3
− + r1 = m (3)
2 4
P 1−Πi (vi |v−i ) PN 1−Πi (vi |v−i )
9
Note Φ(v) = π(v) N i=1 (vi − πi (vi |v−i ) ) when π(v) is not 0. Here φ(v) := i=1 (vi − πi (vi |v−i ) ) is the
virtual value in our environment, which is the sum of the conditional virtual value of each agent. However,
it turns out the weighted virtual values is more convenient for our analysis because it is well defined even
for π(v) = 0. Henceforth we directly work with the weighted virtual values.

10
 v2
SRI (1)
SRI (2)
1 SRI (3)
SRI (4)

r1

0
0 r1 1 v1

Figure 2: Provision regions of Symmetric Maxmin Public Good Mechanism (I)

Let a := 1−21ln r1 . Divide the value profiles into four regions as follows: SRI (1) :=
{(v1 , v2 )|v1 + v2 ≥ r1 , v1 ≤ r1 , v2 ≤ r1 }; SRI (2) := {(v1 , v2 )|v1 ≥ r1 , v2 ≤ r1 }; SRI (3) :=
{(v1 , v2 )|v1 ≤ r1 , v2 ≥ r1 }; SRI (4) := {(v1 , v2 )|v1 ≥ r1 , v2 ≥ r1 }. The provision rule is as
follows: 
a
 r1 (v1 + v2 − r1 )
 v ∈ SRI (1)

 a
 a ln v1 + r1 v2 − a ln r1

 v ∈ SRI (2)
q ∗ (v1 , v2 ) = a ln v2 + ra1 v1 − a ln r1 v ∈ SRI (3)




 a ln v1 + a ln v2 + 1 v ∈ SRI (4)


0 otherwise
The payment rule is characterized by Proposition 1.
Symmetric Worst-Case Joint Distribution (I)
Let π ∗ (v1 , v2 ) denote the density of the value profile (v1 , v2 ) whenever the density exists. Let
P r ∗ (v1 , v2 ) denote the probability mass of the value profile (v1 , v2 ) whenever there is some
probability mass on (v1 , v2 ). Let SV (I) := {v|v1 + v2 ≥ r1 }. Symmetric Worst-Case Joint
Distribution (I) has the support SV (I) and is defined as follows:

r1


 (v1 +v2 )3
v1 + v2 ≥ r1 , v1 6= 1, v2 6= 1
∗ r1
π (v1 , v2 ) = 2(1+v2 )2
v1 = 1, 0 ≤ v2 < 1

 r1

2(v1 +1)2
0 ≤ v1 < 1, v2 = 1

r1
P r ∗(1, 1) =
4

11
 v2

1 mass

r1

0
0 r1 1 v1

Figure 3: Symmetric Worst-Case Joint Distribution (I)

Equivalently, Symmetric Worst-Case Joint Distribution (I) can be described by its

marginal distributions and conditional distributions. The marginal distributions are as
follows: π1∗ (v1 ) = π2∗ (v2 ) = 2r11 for 0 ≤ v1 , v2 ≤ r1 , π1∗ (v1 ) = 2vr12 and π2∗ (v2 ) = 2vr12 for
1 2
r1 < v1 , v2 < 1, P r1∗ (1) = P r2∗ (1) = r21 . That is, the marginal distribution of each agent is a
combination of a uniform distribution and some equal revenue distribution. The conditional
2r12
distributions are as follows: if 0 ≤ vj ≤ r1 , then πi∗ (vi |vj ) = (vi +vj )3
for r1 − vj ≤ vi < 1
r12 2vj2
and P ri∗ (vi = 1|vj ) = (1+vj )2
; if r1 < vj < 1, then πi∗ (vi |vj ) = (vi +vj )3
for 0 ≤ vi < 1
vj2 1
and P ri∗ (vi = 1|vj ) = if vj = 1, then πi∗ (vi |vj = 1) = (vi +1)
(1+vj )2
; 2 for 0 ≤ vi < 1 and
∗ 1
P ri (vi = 1|vj = 1) = 2 . That is, the conditional distribution is some truncated generalized
Pareto distribution with some mass on 1 (the exact distribution depends on the other agent’s
value).

Remark 1. Symmetric Worst Case Joint Distribution (I) exhibits negative correlation when
vi ∈ [0, r1 ) and positive correlation when vi ∈ [r1 , 1]. 10

Theorem 1. When m < 43 , Symmetric Maxmin Public Good Mechanism (I) and
Symmetric Worst-Case Joint Distribution (I) form a Nash equilibrium. In addition,
the revenue guarantee is 12 exp(W−1 (−2m exp(− 32 )) + 32 ).
10
Precisely, when 0 ≤ vi < vi′ < r1 , the distribution of vj conditional on vi′ is first order stochastic
dominated by the distribution of vj conditional on vi ; when r1 ≤ vi < vi′ ≤ 1, the distribution of vj
conditional on vi′ first order stochastic dominates the distribution of vj conditional on vi .

12
 Let us illustrate Symmetric Maxmin Public Good Mechanism (I). First, we guess
(A1) that in the maxmin solution, the principle provides the public good with positive
probability if and only if the sum of the reported values exceeds certain threshold r1 ∈ (0, 1),
i.e., v1 + v2 > r1 where r1 ∈ (0, 1). Second, note that in the maxmin solution, it is without
loss to assume (B) that the provision probability is 1 when the value profile is (1, 1).11
Third, we conjecture that the support of the worst-case joint distribution π ∗ coincides with
the provision region. We assume that q ∗ (r1 , r1 ) = a for some a ∈ [0, 1]. Then we divide
the support into four regions: SRI (1), SRI (2), SRI (3) and SRI (4). The idea is to solve for
the provision probability q ∗ for each region sequentially using the complementary slackness
condition (2) and finally solve for a by using (B). The details are deferred to the Appendix
A.
Next, we illustrate Symmetric Worst-Case Joint Distribution (I). The worst-case
joint distribution exhibits the property that the weighted virtual value is positive only for
the highest type (1,1), zero for the other value profiles in the support and weakly negative
for value profiles outside the support12 . Formally, in the worst-case joint distribution, we
have
Φ(1, 1) > 0 (4)

Φ(v) = 0 ∀v1 + v2 ≥ r1 and v 6= (1, 1) (5)

Φ(v) ≤ 0 ∀v1 + v2 < r1 (6)

Now if the joint distribution satisfies (4), (5) and (6), then any feasible and monotone
mechanism in which the public good is provided with some positive probability if and only
if v1 + v2 > r1 and the public good is provided with probability of 1 when (v1 , v2 ) = (1, 1)
is optimal for the principal. Then, the only remaining issue is whether we can construct
a joint distribution satisfying (4), (5) and (6). We give an affirmative answer by taking a
constructive approach. The details of the construction are deferred to the Appendix A.

5.2 Case (II): High Expectations (m ≥ 43 )

Symmetric Maxmin Public Good Mechanism (II)
√
Let v = (v1 , v2 ) be the reported value profile of the two agents. Let r2 := 1 − 2 1 − m. Let
11
This does not affect the monotonicity constraints because the value profile (1, 1) is the highest type in
our environment.
12
By the definition of the weighted virtual values, the weighted virtual values are weakly negative for
value profiles outside the support.

13
 v2
SRII

r2

0
0 r2 1 v1

Figure 4: Provision regions of Symmetric Maxmin Public Good Mechanism (II)

SRII := {(v1 , v2 )|v1 + v2 ≥ 1 + r2 }. The provision rule is as follows:

(
1
∗ (v
1−r2 1
+ v2 − 1 − r2 ) v ∈ SRII
q (v1 , v2 ) =
0 otherwise

The payment rule is characterized by Proposition 1.

Symmetric Worst-Case Joint Distribution (II)
Let π ∗ (v1 , v2 ) denote the density of the value profile (v1 , v2 ) whenever the density exists. Let
P r ∗ (v1 , v2 ) denote the probability mass of the value profile (v1 , v2 ) whenever there is some
probability mass on (v1 , v2 ). Symmetric Worst-Case Joint Distribution (II) has the support
SRII and is defined as follows:

(r2 +1)2


 (v1 +v2 )23 v1 + v2 ≥ 1 + r2 , v1 6= 1, v2 6= 1
(r +1)
π ∗ (v1 , v2 ) = 2
2(1+v2 )2
v1 = 1, r2 ≤ v2 < 1

 (r +1)2
2

2(v1 +1)2
r2 ≤ v1 < 1, v2 = 1

(r2 + 1)2
∗
P r (1, 1) =
4
Equivalently, Symmetric Worst-Case Joint Distribution (II) can be described by
its marginal distributions and conditional distributions. The marginal distributions are
as follows: π1∗ (v1 ) = π2∗ (v2 ) = 21 for r2 ≤ v1 , v2 < 1, P r1∗(1) = P r2∗(1) = 1+r
2
2
. That
is, the marginal distribution of each agent is a combination of a uniform distribution on

14
 v2

1 mass

r2

0
0 r2 1 v1

Figure 5: Symmetric Worst-Case Joint Distribution (II)

[r2 , 1) and an atom on 1. The conditional distributions are as follows: if vj = r2 , then

2
P ri∗ (vi = 1|vj = r2 ) = 1; if r2 < vj < 1, then πi∗ (vi |vj ) = 2(1+r 2)
(vi +vj )3
for 1 + r2 − vj ≤ vi < 1
2
and P ri∗ (vi = 1|vj ) = (1+r 2)
(1+vj )2
; if vj = 1, then πi∗ (vi |vj = 1) = (v1+r 2
i +1)
2 for r2 ≤ vi < 1

and P ri∗(vi = 1|vj = 1) = 1+r 2

2
. That is, the conditional distribution is (generically)
some truncated generalized Pareto distribution with some mass on 1 (the exact distribution
depends on the other agent’s value).

Remark 2. Symmetric Worst Case Joint Distribution (II) exhibits negative correlation when
vi ∈ [1 + r2 , 1); the negative correlation breaks when vi = 1.

Theorem 2. When m ≥ 43 , Symmetric Maxmin Public Good Mechanism (II) and

Symmetric Worst-Case Joint Distribution (II) form a Nash equilibrium. In addition,
√
the revenue guarantee is 2(2 − m − 2 1 − m).

Let us illustrate Symmetric Maxmin Public Good Mechanism (II). First, we guess
(A2) that in the maxmin solution, the principle provides the public good with some positive
probability if and only if the sum of the reported values exceeds certain threshold 1 + r2 in
which r2 ∈ [0, 1], i.e., v1 +v2 > 1+r2 where r2 ∈ [0, 1]. Note the threshold here is higher than
that in Case (I). Intuitively, as the expectations of the values become higher, the principal
exercises more monopoly power to raise revenue. Second, similarly, in the maxmin solution,
it is without loss to assume (B). Third, similarly, we conjecture that the support of the worst
case joint distribution π ∗ is the area in which v ∈ SRII . Together with (iv) in Proposition

15
1, (A2) and (2), we obtain that for any v ∈ SRII ,
Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (7)
1+r2 −v2 1+r2 −v1

Then following similar procedures for solving for provision probability q ∗ (v) when v ∈ SRI (1)
in Case (I), we obtain Symmetric Maxmin Public Good Mechanism (II). For
Symmetric Worst-Case Joint Distribution (II), we have

Φ(1, 1) > 0 (8)

Φ(v) = 0 ∀v1 + v2 ≥ 1 + r2 and v 6= (1, 1) (9)

Φ(v) ≤ 0 ∀v1 + v2 < 1 + r2 (10)

The construction procedure for the joint distribution is similar. Therefore we omit it. To
make sure that Symmetric Worst-Case Joint Distribution (II) satisfies the mean
constraints, we must have Z 1
1 1 + r2
xdx + =m (11)
r2 2 2
√
Therefore we obtain that r2 = 1 − 2 1 − m for any m ≥ 34 .

6 Asymmetric Case
In this section, we focus on the two-agent asymmetric case, i.e., N = 2 and m1 6= m2 .
Without loss of generality, we restrict attention to the case in which m1 > m2 . Let
A := {(m1 , m2 )|1 ≥ m1 > m2 ≥ 0} be the set of all asymmetric expectations. We will
divide the set A into four areas and then characterize the maxmin public good mechanism
and the worst-case joint distribution for each area.

6.1 Area (I): Close and Low Expectations

r 2r−1 1 r 1 r
Let Boundary(I) := {(m1 , m2 )| 1+r ( (1−r)2 ln r + 1−r ) = m1 , 1+r (− (1−r)2 ln r − 1−r ) = m2 , 0 <

r < 1}. It can be shown that Boundary (I) is indeed equivalent to some increasing
r 2r−1 1
function BI (m1 )) where 0 < m1 < 1. To see this, note Z1I (r) := 1+r ( (1−r)2 ln r + 1−r )
r 1 r
and Z2I (r) := 1+r (− (1−r)2 ln r − 1−r ) are both increasing w.r.t. r. In addition, m1 > BI (m1 ).

To see this, it can be shown that Z I (r) := Z1I (r) − Z2I (r) > 0 for 0 < r < 1. Now let
Area(I) := {(m1 , m2 )|m2 < m1 , m2 > BI (m1 ), 43 > m1 > 0}. We propose a pair of strategy
profile as follows.

16
 v2
ARI (1)
ARI (2)
1 ARI (3)
ARI (4)

s2

0
0 s1 1 v1

Figure 6: Provision regions of Asymmetric Maxmin Public Good Mechanism (I)

Asymmetric Maxmin Public Good Mechanism (I)

Let v = (v1 , v2 ) be the reported value profile of the two agents. Let s1 ∈ [0, 1], s2 ∈ [0, 1] be
the solution to the following system of equations:

s1 s2 s21 s1 s2
m1 = ( 2
ln − ln s1 + ) := H1I (s1 , s2 ) (12)
s1 + s2 (s1 − s2 ) s2 s2 − s1

s1 s2 s22 s2 s1
m2 = ( 2
ln − ln s2 + ) := H2I (s1 , s2 ) (13)
s1 + s2 (s1 − s2 ) s1 s1 − s2
1
Let c := s s
(1− s2 ) ln s1 −(1− s1 ) ln s2
. Divide the value profiles into four regions as follows:
1− 1 2
s1
ln s
2
ARI (1) := {(v1 , v2 )|s2 v1 + s1 v2 ≥ s1 s2 , v1 ≤ s1 , v2 ≤ s2 }; ARI (2) := {(v1 , v2 )|v1 ≥ s1 , v2 ≤
s2 }; ARI (3) := {(v1 , v2 )|v1 ≤ s1 , v2 ≥ s2 }; ARI (4) := {(v1 , v2 )|v1 ≥ s1 , v2 ≥ s2 }. The
provision rule is as follows:

c s2 s1


 ln
s1 (ln (v1 + s2 − v )
s1 1
− ln (v2 + s1 − v ))
s2 2
v ∈ ARI (1)
 s2

 c s2 s1 s2


 ln
s1 ((1 − s1
) ln v1 − ln (v2 + s1 − v)
s2 2
+ s1
ln s1 ) v ∈ ARI (2)
 s2

q ∗ (v1 , v2 ) = c
s (ln (v1 + s2 −
ln s1
s2
v ) − (1 − ss21 ) ln v2 −
s1 1
s1
s2
ln s2 ) v ∈ ARI (3)

 2
 s2



c
s ((1 −
ln s1 s1
) ln v1 − (1 − ss21 ) ln v2 ) + 1 v ∈ ARI (4)

 2

 0 otherwise

The payment rule is characterized by Proposition 1.

17
Asymmetric Worst-Case Joint Distribution (I)
Let π ∗ (v1 , v2 ) denote the density of the value profile (v1 , v2 ) whenever the density exists. Let
P r ∗ (v1 , v2 ) denote the probability mass of the value profile (v1 , v2 ) whenever there is some
probability mass on (v1 , v2 ). Let AV (I) := {v|s2v1 + s1 v2 ≥ s1 s2 }. Asymmetric Worst-Case
Joint Distribution (I) has the support AV (I) and is defined as follows:

2s1 s2


 (s1 +s2 )(v1 +v2 )3
s2 v1 + s1 v2 ≥ s1 s2 , v1 6= 1, v2 6= 1
π ∗ (v1 , v2 ) = s1 s2
(s1 +s2 )(1+v2 )2
v1 = 1, 0 ≤ v2 < 1

 s1 s2

(s1 +s2 )(1+v1 )2
0 ≤ v1 < 1, v2 = 1

s1 s2
P r ∗(1, 1) =
2(s1 + s2 )
Equivalently, Asymmetric Worst-Case Joint Distribution (I) can be described by
its marginal distributions and conditional distributions. The marginal distributions are as
s1 s2 s1 s2
follows: πi∗ (vi ) = sj
2
for 0 ≤ vi ≤ si , πi∗ (vi ) = (s1 +s 2 )(vi )
2 for si < vi < 1,
(s1 +s2 )( s (si −vi )+vi )
i
s1 s2
P ri∗ (1)
= .
That is, the marginal distribution of each agent is a combination of
(s1 +s2 )
some generalized Pareto distribution and some equal revenues distribution. The conditional
2( s i (sj −vj )+vj )2
distributions are as follows: if 0 ≤ vj ≤ sj , then πi∗ (vi |vj ) = j
(vi +vj )3
for si − ssji vj ≤ vi <
s
( si (sj −vj )+vj )2 2vj2
1 and P ri∗(vi = 1|vj ) = j
(1+vj )2
; if sj < vj < 1, then πi∗ (vi |vj ) = (vi +vj )3
for 0 ≤ vi < 1
vj2 1
and P ri∗ (vi = 1|vj ) = vj = 1, then πi∗ (vi |vj = 1) = (vi +1)
(1+vj )2
; if 2 for 0 ≤ vi < 1 and

P ri∗ (vi = 1|vj = 1) = 21 . That is, the conditional distribution is some truncated generalized
Pareto distribution with some mass on 1 (the exact distribution depends on the other agent’s
value).

Remark 3. When (m1 , m2 ) ∈ Boundary(I), s2 = 1 and s1 ∈ (0, 1).

Lemma 2. For any given (m1 , m2 ) ∈ Area(I), there exists a solution s1 , s2 to the system of
equations (12) and (13).

Theorem 3. When (m1 , m2 ) ∈ Area(I), Asymmetric Maxmin Public Good

Mechanism (I) and Asymmetric Worst-Case Joint Distribution (I) form a Nash
equilibrium. The revenue guarantee is ss11+s
s2
2
.

Let us illustrate Asymmetric Maxmin Public Good Mechanism (I). First, we guess
that (A3) that in the maxmin solution, the principal provides the public good with positive
probability if and only if the sum of weighted reported values exceeds certain threshold, i.e.,
s2 v1 +s1 v2 > s1 s2 where s1 , s2 ∈ (0, 1] and s1 6= s2 . Second, similarly, in the maxmin solution,

18
 v2

1 mass

s2

0
0 s1 1 v1

Figure 7: Asymmetric Worst-Case Joint Distribution (I)

it is without loss to assume (B). Third, similarly, we conjecture that the support of the worst
case joint distribution π ∗ is the area in which v ∈ AV (I). We assume that q ∗ (r1 , r1 ) = c
for some c ∈ [0, 1]. Then we divide the support into four regions: ARI (1), ARI (2), ARI (3)
and ARI (4). Similar to Case (I), the idea is to solve for the provision probability q ∗ for
each region sequentially using the complentary slackness condition (2) and finally solve for c
by using (B). The details are deferred to the Appendix A. For Asymmetric Worst-Case
Joint Distribution (I), we have
Φ(1, 1) > 0 (14)

Φ(v) = 0 ∀s2 v1 + s1 v2 ≥ s1 s2 and v 6= (1, 1) (15)

Φ(v) ≤ 0 ∀s2 v1 + s1 v2 < s1 s2 (16)

The construction procedure for the joint distribution is similar. Therefore we omit it. To
make sure that Asymmetric Worst-Case Joint Distribution (I) satisfies the mean
constraints, we have a system of two equations (12) and (13). Lemma 2 states that a
solution exists.

6.2 Area (II): Close and High Expectations

2 2
Let Boundary(II) : {(m1 , m2 )| (1+r)(1−r
2r 2
) 1
ln 1+r + 1+r
2r
= m1 , 1+r
2r 2
1
ln (1 + r) − 2r + 12 = m2 , 0 <
r ≤ 1}. It can be shown that Boundary(II) is indeed equivalent to some decreasing function
2)
BII (m1 ) where 0 < m1 ≤ 1. To see this, note Z1II (r) := (1+r)(1−r
2r 2
1
ln 1+r + 1−r
2r
+ 1+r
2
is

19
 v2
ARII

t2

0
0 t1 1 v1

Figure 8: Provision regions of Asymmetric Maxmin Public Good Mechanism (II)

increasing w.r.t r and Z2II (r) := 1+r

2r 2
ln (1 + r) − 2r1 + 12 is decreasing w.r.t. r. In addition,
m1 > BII (m1 ). To see this, it can be shown that Z II (r) := Z1II (r)−Z2II (r) > 0 for 0 < r < 1.
Now let Area(II) := {(m1 , m2 )|m2 < m1 , m2 ≥ BII (m1 ), 1 ≥ m1 > 43 }. We propose a pair
of strategy profile as follows.
Asymmetric Maxmin Public Good Mechanism (II)
Let v = (v1 , v2 ) be the reported value profile of the two agents. Let t1 , t2 be the unique
solution to the following equation:

(1 + t1 )(1 + t2 )(1 − t1 )2 1 + t2 (1 − t1 t2 )(1 − t1 ) 1 + t1

m1 = ln + + := H1II (t1 , t2 ) (17)
2(t1 − t2 )2 1 + t1 2(t1 − t2 ) 2

(1 + t1 )(1 + t2 )(1 − t2 )2 1 + t1 (1 − t1 t2 )(1 − t2 ) 1 + t2

m2 = ln + + := H2II (t1 , t2 ) (18)
2(t1 − t2 )2 1 + t2 2(t2 − t1 ) 2
Let ARII := {(v1 , v2 )|(1 − t2 )v1 + (1 − t1 )v2 ≥ 1 − t1 t2 }. The provision rule is as follows:

1 t2 −1 1−t1

ln
1+t2 (ln (v1 + 1−t1 1
(v − t1 ) + 1) − ln (v2 + (v
t2 −1 2
− 1) + t1 )) v ∈ ARII
∗
q (v1 , v2 ) = 1+t1
 0 otherwise

The payment rule is characterized by Proposition 1.

Asymmetric Worst-Case Joint Distribution (II)
Let π ∗ (v1 , v2 ) denote the density of the value profile (v1 , v2 ) whenever the density exists. Let
P r ∗ (v1 , v2 ) denote the probability mass of the value profile (v1 , v2 ) whenever there is some

20
probability mass on (v1 , v2 ). Asymmetric Worst-Case Joint Distribution (II) has the support
SRII and is defined as follows:

(1+t1 )(1+t2 )


 (v1 +v2 )3 (1 − t2 )v1 + (1 − t1 )v2 ≥ 1 − t1 t2 , v1 6= 1, v2 6= 1
(1+t )(1+t )
π ∗ (v1 , v2 ) = 1
2(1+v2 )2
2
v1 = 1, t2 ≤ v2 < 1

 (1+t )(1+t )
1 2
 2
2(1+v1 )
t1 ≤ v1 < 1, v2 = 1

(1 + t1 )(1 + t2 )
P r ∗ (1, 1) =
4
Equivalently, Asymmetric Worst-Case Joint Distribution (II) can be described by
its marginal distributions and conditional distributions. The marginal distributions are as
follows: πi∗ (vi ) = tj(1+t
−ti
1 )(1+t2 ) ∗
1−t1 t2 2 for ti ≤ vi < 1, P ri (1) =
1+ti
2
. That is, the marginal
2( 1−ti
vi + 1−ti
)
distribution of each agent is a combination of a uniform distribution on [ti , 1) and an atom
on 1. The conditional distributions are as follows: if vj = tj , then P ri∗(vi = 1|vj = tj ) = 1;
ti −tj 1−t1 t2 2
2( 1−tj
vj +
1−tj
)
1−t1 t2 1−ti
if tj < vj < 1, then πi∗ (vi |vj ) = (vi +vj )3 for 1−tj
− v
1−tj j
≤ vi < 1 and
ti −tj 1−t t
( 1−t vj + 1−t1 2 )2
P ri∗ (vi = 1|vj ) = j
; if vj = 1, then πi∗ (vi |vj = 1) = (v1+t
(1+vj )2
j i
i +1)
2 for ti ≤ vi < 1
∗ 1+ti
and P ri (vi = 1|vj = 1) = 2 . That is, the conditional distribution is (generically)
some truncated generalized Pareto distribution with some mass on 1 (the exact distribution
depends on the other agent’s value).
Remark 4. When (m1 , m2 ) ∈ Boundary(II), t2 = 0 and t1 ∈ (0, 1].

Lemma 3. For any given (m1 , m2 ) ∈ Area(II), there exists a solution t1 , t2 to to the system
of equations (17) and (18).
Theorem 4. When (m1 , m2 ) ∈ Area(II), Asymmetric Maxmin Public Good
Mechanism (II) and Asymmetric Worst-Case Joint Distribution (II) form a Nash
equilibrium. The revenue guarantee is (1+t1 )(1+t
2
2)
.
Let us illustrate Asymmetric Maxmin Public Good Mechanism (II). We guess
(A4) that in the maxmin solution, the principal provides the public good with positive
probability if and only if the sum of weighted reported values exceeds certain threshold, i.e.,
(1 − t2 )v1 + (1 − t1 )v2 > 1 − t1 t2 where t1 , t2 ∈ [0, 1). Second, similarly, in the maxmin
solution, it is without loss to assume (B). Third, similarly, we conjecture that the support
of the worst case joint distribution π ∗ is the area in which v ∈ ARII . Together with (iv) in
Proposition 1, (A4) and (2), we obtain that for any v ∈ ARII ,
Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (19)
1−t1 t2 1−t 1−t1 t2 1−t
1−t2
− 1−t1 v2 1−t1
− 1−t2 v1
2 1

21
 v2

1 mass

t2

0
0 t1 1 v1

Figure 9: Asymmetric Worst-Case Joint Distribution (II)

Then following similar procedures for solving for provision probability q ∗ (v) when v ∈ ARI (1)
in Area (I), we obtain Asymmetric Maxmin Public Good Mechanism (II). For
Asymmetric Worst-Case Joint Distribution (II), we have

Φ(1, 1) > 0 (20)

Φ(v) = 0 ∀(1 − t2 )v1 + (1 − t1 )v2 ≥ 1 − t1 t2 and v 6= (1, 1) (21)

Φ(v) ≤ 0 ∀(1 − t2 )v1 + (1 − t1 )v2 < 1 − t1 t2 (22)

The construction procedure for the joint distribution is similar. Therefore we omit it. To
make sure that Asymmetric Worst-Case Joint Distribution (II) satisfies the mean
constraints, we have a system of two equations (17) and (18). Lemma 3 states the solution
exists and is unique.

6.3 Area (III): Moderate-Distance Expectations

Let Boundary(III) := {(m1 , m2 )|r(1 − ln r) = m1 , r ln r+1
r
= m2 , 0 < r ≤ 1}. It can
be shown that Boundary(III) is indeed equivalent to some increasing function BIII (m1 )
where 0 < m1 ≤ 1. To see this, note Z1III (r) := r(1 − ln r) and Z2III (r) := r ln r+1
r
are
both increasing w.r.t. r. In addition, m1 > BIII (m1 ). To see this, it can be shown that
Z III (r) := Z1III (r) − Z2III (r) > 0 for 0 < r ≤ 1. Now let Area(III) := {(m1 , m2 )|m2 ≤
BI (m1 ), m2 < BII (m1 ), m2 > BIII (m1 ), 1 ≥ m1 > 0}. We propose a pair of strategy profile

22
 v2
ARIII (1)
ARIII (2)
1

0
0 u2 u1 1 v1

Figure 10: Provision regions of Asymmetric Maxmin Public Good Mechanism (III)

as follows.
Asymmetric Maxmin Public Good Mechanism (III)
Let v = (v1 , v2 ) be the reported value profile of the two agents. Let u1 , u2 be the unique
solution to the following equation:

u1 (u2 + 1) (u2 − u1 )2 u1 u2 − u1
m1 = ( 2
ln −ln u1 +1− ) := H1III (u1, u2 )
u1 + 1 (u2 − u1 + 1) 1 + u2 (1 + u2 )(1 + u2 − u1 )
(23)
u1 (u2 + 1) 1 1 + u2 1 1
m2 = ( 2
ln + − ) := H2III (u1, u2 )
u1 + 1 (u2 − u1 + 1) u1 1 + u2 (1 + u2 )(1 + u2 − u1 )
u1
(24)
ln 1+u2 III
Let d := 1 ln u1 −ln (1+u2 ) . Divide the value profiles into two regions as follows: AR (1) :=
u1 −u2

{(v1 , v2 )|v1 + (u1 − u2 )v2 ≥ u1 , v1 ≤ u1 , v2 ≤ 1}; ARIII (2) := {(v1 , v2 )|v1 ≥ u1, v2 ≤ 1}. The
provision rule is as follows:
 d 1

 ln
u1 (ln (v1 + (v
u2 −u1 1
− u1 )) − ln (v2 + (u2 − u1 )v2 + u1 )) v ∈ ARIII (1)
 1+u2

q ∗ (v1 , v2 ) = ln
d
u1 ((1 + 1
u2 −u1
) ln v1 − ln (v2 + (u2 − u1 )v2 + u1 ) − 1
u2 −u1
ln u1 ) v ∈ ARIII (2)

 1+u2

0 otherwise

The payment rule is characterized by Proposition 1.

Asymmetric Worst-Case Joint Distribution (III)
Let π ∗ (v1 , v2 ) denote the density of the value profile (v1 , v2 ) whenever the density exists.

23
Let P r ∗(v1 , v2 ) denote the probability mass of the value profile (v1 , v2 ) whenever there is
some probability mass on (v1 , v2 ). Let AV (III) := {v|v1 + (u1 − u2 )v2 ≥ u1 }. Asymmetric
Worst-Case Joint Distribution (III) has the support AV (III) and is defined as follows:

2u1 (u2 +1)


 (u1 +1)(v1 +v2 )3
v1 + (u1 − u2 )v2 ≥ u1 , v1 6= 1, v2 6= 1
u1 (u2 +1)
π ∗ (v1 , v2 ) = (u1 +1)(1+v2 )2
v1 = 1, 0 ≤ v2 < 1

 u1 (u2 +1)

(u1 +1)(1+v1 )2
u2 ≤ v1 < 1, v2 = 1

u1 (u2 + 1)
P r ∗ (1, 1) =
2(u1 + 1)
Equivalently, Asymmetric Worst-Case Joint Distribution (III) can be described by
its marginal distributions and conditional distributions. The marginal distributions are as
u1 (u2 +1) u1 (u2 +1)
follows: π1∗ (v1 ) = (u1 +1)( u 1
(v1 −u1 )+v1 )2
for u2 ≤ v1 ≤ u1, π1∗ (v1 ) = (u1 +1)(v1 )2
for u1 < v1 < 1,
2 −u1
u1 (u2 +1) u1 (u2 +1) u1
P r1∗ (1) = (u1 +1)
. π2∗ (v2 ) = (u1 +1)((u2 −u1 )v2 +u1 +v2 )2
for 0 ≤ v2 < 1, P r2∗(1) = u1 +1
. That is,
the marginal distribution of agent 1 is a combination of some generalized Pareto distribution
and some equal revenue distribution, while the marginal distribution of agent 2 is some
generalized Pareto distribution with an atom on 1. The conditional distributions are as
2
follows: if 0 ≤ v2 < 1, then π1∗ (v1 |v2 ) = 2((u2 −u(v11)v+v2 +u
2)
3
1 +v2 )
for u1 − (u1 − u2 )v2 ≤ v1 < 1 and
((u2 −u1 )v2 +u1 +v2 )2 1+u2
P r1∗ (v1 = 1|v2 ) = (1+v2 )2
; if v2 = 1, then π1∗ (v1 |v2 = 1) = (v1 +1)2
for u2 ≤ v1 < 1
1
1+u2 2( u (v1 −u1 )+v1 )2
and P r1∗(v1 = 1|v2 = 1) = 2
. If u2 ≤ v1 < u1 , then π2∗ (v2 |v1 ) = 2 −u1
(v1 +v2 )3
1
u1 −v1 (u (v1 −u1 )+v1 )2
for u1 −u2
≤ v2 < 1 and P r2∗ (v2 = 1|v1 ) = 2 −u1
(1+v2 )2
; if u1 ≤ v1 < 1, then
2v12 v12
π2∗ (v2 |v1 ) = (v1 +v2 )3
for 0 ≤ v2 < 1 and P r2∗(v2 = 1|v1 ) = (1+v1 )2
; if v1 = 1, then
1
π2∗ (v2 |v1
= 1) = for 0 ≤ v2 < 1 and
(v1 +1)2
= 1|v1 = 1) = 21 . That is, the
P r2∗ (v2
conditional distribution is some truncated generalized Pareto distribution with some mass
on 1 (the exact distribution depends on the other agent’s value).

Lemma 4. For any given (m1 , m2 ) ∈ Area(III), there exists a solution u1 , u2 to to the
system of equations (23) and (24). In addition, u1 > u2 .

Theorem 5. When (m1 , m2 ) ∈ Area(III), Asymmetric Maxmin Public Good

Mechanism (III) and Asymmetric Worst-Case Joint Distribution (III) form a
u1 (u2 +1)
Nash equilibrium. The revenue guarantee is u1 +1
.

Let us illustrate Asymmetric Maxmin Public Good Mechanism (III). We guess

(A5) that in the maxmin solution, the principal provides the public good with positive
probability if and only if the sum of weighted reported values exceeds certain threshold, i.e.,
v1 + (u1 − u2 )v2 > u1 where 0 ≤ u2 < u1 < 1. Second, similarly, in the maxmin solution, it

24
 v2

1 mass

0
0 u1 u2 1 v1

Figure 11: Asymmetric Worst-Case Joint Distribution (III)

is without loss to assume (B). Third, similarly, we conjecture that the support of the worst
case joint distribution π ∗ is the area in which v ∈ AV III . Together with (iv) in Proposition
1, (A5) and (2), we obtain that for any v ∈ ARIII (1),
Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (25)
u1 −v1
u1 −(u1 −u2 )v2 u1 −u2

and that for any v ∈ ARIII (2),

Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (26)
u1 −(u1 −u2 )v2 0

Then following similar procedures for solving for provision probability q ∗ (v) when v ∈ ARI (1)
and v ∈ ARI (2) in Area (I), we obtain Asymmetric Maxmin Public Good Mechanism
(III). For Asymmetric Worst-Case Joint Distribution (III), we have

Φ(1, 1) > 0 (27)

Φ(v) = 0 ∀v1 + (u1 − u2 )v2 ≥ u1 and v 6= (1, 1) (28)

Φ(v) ≤ 0 ∀v1 + (u1 − u2 )v2 < u1 (29)

The construction procedure for the joint distribution is similar. Therefore we omit it. To
make sure that Asymmetric Worst-Case Joint Distribution (III) satisfies the mean

25
 v2
ARIV

0
0 w1 1 v1

Figure 12: Provision regions of Symmetric Maxmin Public Good Mechanism (I)

constraints, we have a system of two equations (23) and (24). Lemma 4 states the solution
exists and is unique.

6.4 Area (IV): Distant Expectations

Let Area(IV ) := {(m1 , m2 )|m2 ≤ BIII (m1 ), 1 ≥ m1 ≥ 0}. We propose a pair of strategy
profile as follows.
Asymmetric Maxmin Public Good Mechanism (IV)
Let v = (v1 , v2 ) be the reported value profile of the two agents. Let w1 , w2 be the unique
solution to the following equation:

m1 = w1 (1 − ln w1 ) := H IV (w1 , w2 ) (30)

w1 + w2
m2 = w1 ln := H IV (w1 , w2 ) (31)
w1
Let ARIV := {(v1 , v2 )|v1 ≥ w1 }. The provision rule is as follows:
(
ln v1
− ln +1 v ∈ ARIV
q ∗ (v1 , v2 ) = w1
0 otherwise

The payment rule is characterized by Proposition 1.

Asymmetric Worst-Case Joint Distribution (IV)
Let π ∗ (v1 , v2 ) denote the density of the value profile (v1 , v2 ) whenever the density exists. Let

26
P r ∗ (v1 , v2 ) denote the probability mass of the value profile (v1 , v2 ) whenever there is some
probability mass on (v1 , v2 ). Let AV (IV ) := [w1 , 1] × [0, w2]. Asymmetric Worst-Case Joint
Distribution (IV) has the support AV (IV ) and is defined as follows:

2w1


 (v1 +v2 )3
v1 ≥ w1 , v1 6= 1, v2 6= w2
π ∗ (v1 , v2 ) = w1
(1+v2 )2
v1 = 1, 0 ≤ v2 < w2

 w1

(w2 +v1 )2
r1 ≤ v1 < 1, v2 = w2

w1
P r ∗ (1, w2) =
w2 + 1
Equivalently, Asymmetric Worst-Case Joint Distribution (IV) can be described
by its marginal distributions and conditional distributions. The marginal distributions
are as follows: π1∗ (v1 ) = wv21 for w1 ≤ v1 < 1, P r1∗(1) = w1 ; π2∗ (v2 ) = (w1w+v1 2 )2 for
1
0 ≤ v2 < w2 , P r2∗ (w2 ) = w1w+w
1
2
. That is, the marginal distribution of agent 1 is some equal
revenue distribution, while the marginal distribution of agent 2 is some generalized Pareto
distribution with some probability mass on w2 . The conditional distributions are as follows:
2 2
if 0 ≤ v2 < w2 , then π1∗ (v1 |v2 ) = 2(w 1 +v2 )
(v1 +v2 )3
for w1 ≤ v1 < 1 and P r1∗(v1 = 1|v2 ) = (w 1 +v2 )
(1+v2 )2
; if
w1 +w2
v2 = w2 , then π1∗ (v1 |v2 = w2 ) = (w2 +v1 )2
for w1 ≤ v1 < 1 and P r1∗ (v1 = 1|v2 = w2 ) = ww12+w+1
2
.
2 2
If w1 ≤ v1 < 1, then π2∗ (v2 |v1 ) = (v2(v 1)
1 +v2 )
∗ (v1 )
3 for 0 ≤ v2 < w2 and P r2 (v2 = w2 |v1 ) = (w +v )2 ; if
2 1

v1 = 1, then π2∗ (v2 |v1 = 1) = (1+v1 2 )2 for 0 ≤ v2 < w2 and P r2∗ (v2 = w2 |v1 = 1) = w21+1 . That
is, the conditional distribution is some truncated generalized Pareto distribution with some
probability mass on 1 for agent 1 or on w2 for agent 2 (the exact distribution depends on
the other agent’s value).

Remark 5. When (m1 , m2 ) ∈ Boundary(III), w2 = 1 and w1 ∈ (0, 1].

Remark 6. Asymmetric Maxmin Public Good Mechanism (IV) exhibits positive correlation.

Lemma 5. For any given (m1 , m2 ) ∈ Area(IV ), there exists a solution w1 , w2 to the system
of equations (30) and (31).

Theorem 6. When (m1 , m2 ) ∈ Area(IV ), Asymmetric Maxmin Public Good

Mechanism (IV) and Asymmetric Worst-Case Joint Distribution (IV) form a Nash
w1
equilibrium. The revenue guarantee is exp(W−1 (− exp(1) ) + 1).

Let us illustrate Asymmetric Maxmin Public Good Mechanism (IV). We guess

(A6) that in the maxmin solution, the principal provides the public good with positive
probability if and only if the reported value of agent 1 exceeds certain threshold, i.e., v1 > w1
where w1 ∈ (0, 1]. Second, in the maxmin solution, it is without loss to assume q ∗ (1, v2 ) = 1

27
 v2

w2 mass

0
0 w1 1 v1

Figure 13: Asymmetric Worst-Case Joint Distribution (IV)

for any v2 . Third, we conjecture that the support of the worst case joint distribution π ∗ is
the area in which v ∈ AV IV . Together with (iv) in Proposition 1, (A6) and (2), we obtain
that for any v ∈ AV IV ,
Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (32)
w1 0

In the maxmin solution, q ∗ (v1 , v2 ) is independent of v2 . It is essentially reduced to one-

agent case, to which the solution is known, e.g., Carrasco et al. (2018). Thus we obtain
Asymmetric Maxmin Public Good Mechanism (IV). For Asymmetric Worst-Case
Joint Distribution (IV), we have

Φ(1, 1) > 0 (33)

Φ(v) = 0 ∀v1 ≥ w1 and v1 6= 1 (34)

Φ(v) ≤ 0 ∀v1 < w1 (35)

The construction procedure for the joint distribution is similar. Therefore we omit it. To
make sure that Asymmetric Worst-Case Joint Distribution (IV) satisfies the mean
constraints, we have a system of two equations (30) and (31). Lemma 5 states the solution
exists and is unique.

28
7 Discussions
7.1 More than two agents
The idea and the methodology are useful to study the case when there is N > 2 (any general
number) agents. Specifically, we need to use the complementary slackness condition (2) to
solve for the maxmin public good mechanism, and use Φ(v) = 0 for any value profile in the
support except for v = (1, · · · , 1) to solve for the worst-case joint distribution. However, we
| {z }
N
are not able to provide a complete characterization for the maxmin public good mechanism.
The difficulty arises from two sources: we have to divide the expectations into many cases as
N is getting large; for each case, we may have to divide the value profiles into many regions
and characterize the provision rule for each region. Nonetheless, we are able to provide a
characterization of the maxmin public good mechanism and the worst-case joint distribution
N−1
for a special case in which the symmetric expectation m ≥ 1 − (N −1) NN
.
N-agent Symmetric Maxmin Public Good Mechanism
Let v = (v1 , v2 , · · · , vN ) be the reported value profile of the N agents. Let r be the solution
N −(r+N −1)N−1 ) PN
to m = (r+N −1)(N (N −1)N N . Let SRN := {(v1 , v2 , · · · , vN )| i=1 vi ≥ N − 1 + r}. The
provision rule is as follows:
( P
( Ni=1 vi )
N−1 −(r+N −1)N−1
v ∈ SRN
q ∗ (v1 , v2 , · · · , vN ) = N N−1 −(r+N −1)N−1
0 otherwise

The payment rule is characterized by Proposition 1.

N-agent Symmetric Worst-Case Joint Distribution
Let π ∗ (v1 , v2 , · · · , vN ) denote the density of the value profile (v1 , v2 , · · · , vN ) whenever the
density exists. Let P r ∗ (v1 , v2 , · · · , vN ) denote the probability mass of the value profile
(v1 , v2 , · · · , vN ) whenever there is some probability mass on (v1 , v2 , · · · , vN ). Let A(v)
denote the set of agents whose value is not 1 given a value profile v. Formally, A(v) :=
{i|vi 6= 1 given a value profile v}. N-agent Symmetric Worst-Case Joint Distribution has
the support SRN and is defined as follows:

|A(v)|!(r + N − 1)N
π ∗ (v) = P , v ∈ SRN , v 6= (1, · · · , 1)
N N −1 ( N
i=1 vi ) |A(v)|+1 | {z }
N

∗ (r + N − 1)N
P r (1, · · · , 1) =
| {z } NN
N

(N −1)N−1
Theorem 7. For N-agent symmetric case, when m ≥ 1 − NN
, N-agent Symmetric

29
Maxmin Public Good Mechanism and N-agent Symmetric Worst-Case Joint
−1)N
Distribution form a Nash equilibrium. In addition, the revenue guarantee is (r+N
N N−1
.

7.2 Deterministic mechanisms

In this section, we restrict attention to deterministic DSIC and EPIR public good mechanisms
and characterize the maxmin public good mechanisms in this class of mechanisms for the
two-agent case. Note that Proposition 1 still holds, with an additional property that q(v) is
either 0 or 1 for any v.

Definition 1. Provision boundary of a given deterministic DSIC and EPIR public good
mechanism with a provision rule q is a set of value profiles B := {v̄ = (v¯1 , v¯2 )|q(v̄) =
0; for any small ǫ > 0, q(v¯1 + ǫ, v¯2 ) = 1 or q(v¯1 , v¯2 + ǫ) = 1}.13

We observe the provision boundary exhibits a monotone property, which is summarized

below. 14

Observation 1. If v̄, v̄ ′ ∈ B and v¯1 > v¯1 ′ , then v¯2 ≤ v¯2 ′ .

The main idea is as follows. We divide all deterministic DSIC and EPIR public
mechanisms into four classes according to the provision boundary. By strong duality, we
will focus on the dual program. We propose a relaxation of the dual program by omitting
many constraints. Then we are faced with a finite dimensional linear programming problem.
Then we derive an upper bound of the value of the relaxation for each class. Finally we show
that the upper bound is tight by constructing a deterministic public good mechanism and a
worst-case joint distribution.
√
Theorem 8. (i) When m2 ≥ 2( 2 − 1), any deterministic DSIC and EPIR public
good mechanism satisfying the following properties is a maxmin deterministic public good
mechanism:
p p
(a). (1 − 2(1 − m1 ), 1) ∈ B, (1, 1 − 2(1 − m2 )) ∈ B.
p p
(b). B is below (including) the line boundary 2(1 − m2 )v1 + 2(1 − m1 )v2 = 1 − (1 −
p p
2(1 − m1 ))(1 − 2(1 − m2 )).
(c). Payments are characterized by Proposition 1.q q q q
The worst-case joint distribution put point mass 1−m 2
1
, 1−m2
2
and 1 − 1−m1
2
− 1−m2
2
p p
on value profile (1− 2(1 − m1 ), 1), (1, 1− 2(1 − m2 )) and (1, 1) respectively. The revenue
13
For technical reasons, we assume the public good provision probability on the provision boundary is 0.
This is to have a minimization problem for Nature. Otherwise we have to replace min with inf. See also in
Carrasco et al. (2018).
14
To see this, since v̄ ′ ∈ B and v¯1 > v¯1 ′ , q(v1 , v¯2 ′ ) = 1. Then by definition, v¯2 ≤ v¯2 ′ .

30
 q q
1−m1 1−m2 2
guarantee is 2(1 − 2
− 2
).
√
(ii) When m2 < 2( 2 − 1), the deterministic maxmin public good mechanism is a
dictatorship mechanism: provide the public good if and only if agent 1’s reported value exceeds
√
1 − 1 − m1 ; payments are characterized by Proposition 1. Any joint distribution whose
√ √
marginal distribution for agent 1 puts point mass 1 − m1 and 1 − 1 − m1 on the value
√
1 − 1 − m1 and 1 respectively is a worst-case joint distribution. The revenue guarantee is
√
(1 − 1 − m1 )2 .

Here are two examples of maxmin deterministic public good mechanisms when m2 ≥
√
2( 2 − 1).

Example 1. Linear Mechanism: the public good is provided with probability of 1 if and only
p p p p
if 2(1 − m2 )v1 + 2(1 − m1 )v2 > 1 − (1 − 2(1 − m1 ))(1 − 2(1 − m2 )).

Example 2. Posted Price Mechanism: the public good is provided with probability of 1 if
p p
and only if v1 > 1 − 2(1 − m1 ) and v2 > 1 − 2(1 − m2 ).

7.3 Excludable good

In this section, we consider the design of profit-maximizing excludable good mechanism when
the principal only knows the expectations of the private values of the agents. That is, we
consider the same problem with the only difference that we allow for agent-specific provision
rules. We use qiE (v) ∈ [0, 1] to denote the provision rule for agent i when the reported value
profile is v.

Proposition 1’ (Revenue Equivalence). Maxmin excludable public good mechanisms have

the following properties:
1. qiE (·, v−i ) is nondecreasing in vi for all v−i .
R vi E
2. tE E
i (vi , v−i ) = vi qi (vi , v−i ) − 0 qi (s, v−i )ds.

Proposition 1’ is a simple adaption of Proposition 1. Therefore we omit the proof. Then

consider the problem that fixing any joint distribution π, the principal designs an optimal
mechanism (q E , tE ). An direct implication of Proposition 1’ is that the expected revenue of
(q E , tE ) under π is
XN N
Z X
E
E[ ti (v)] = qiE (v)ΦE
i (v)dv
i=1 i=1

where ΦE = π(v)vi − [πi (v−i ) − Πi (vi , v−i )]. Here ΦE

i (v) i (v) is the weighted virtual value of
type vi of agent i when the value profile is v. Next consider the problem that fixing any

31
mechanism (q E , tE ), adversarial nature chooses a joint distribution π that minimizes the
expected revenue.

Lemma 1’. If π is a best response for adversarial nature to a given mechanism (q E , tE ),

then there exists some real numbers λ1 , · · · , λN , µ such that

N
X N
X
λi vi + µ ≤ tE
i (v) ∀v ∈ V (36)
i=1 i=1

N
X N
X
λi vi + µ = tE
i (v) ∀v ∈ supp(π) (37)
i=1 i=1

Lemma 1’ is a simple adaption of lemma 1. Therefore we omit the proof. Now we give
the construction of the maxmin excludable public good mechanism and the worst-case joint
distribution for the general N−agent case.
N-agent Maxmin Excludable Public Good Mechanism
Let v = (v1 , v2 , · · · , vN ) be the reported value profile of the N agents. Let γi be the solution
to mi = γi − γi ln γi . The provision rule is as follows:
(
ln vi
1− vi ≥ γi
qiE∗ (vi , v−i ) = ln γi
0 otherwise

The payment rule is characterized by an adaption of Proposition 1.

N-agent Independent Equal Revenue Distribution
The marginal distribution of each agent i’s value is the equal revenue distribution supported
on [γi , 1], i.e., Fi∗ (vi ) = 1 − γvii for vi ∈ [γi , 1) and Fi∗ (1) = 1. N-agent Independent Equal
Revenue Distribution is the one in which all values are independently distributed.

Theorem 9. For N-agent case, N-agent Excludable Maxmin Public Good

Mechanism and N-agent Independent Equal Revenue Distribution form a Nash
P
equilibrium. In addition, the revenue guarantee is Ni=1 γi .

8 Concluding Remarks
In this paper we characterize maxmin public good mechanisms among DSIC and EPIR
mechanisms for the two-agent case given general expectations and for a special N-agent
case given high symmetric expectations. An important direction for future research is to
extend the analysis beyond the dominant strategy mechanisms. Another direction is to study

32
situations in which the principal knows other aspects of the joint distribution of values, e.g.,
the marginals distributions and other moments.

9 Appendix A
9.1 Characterization of Symmetric Maxmin Public Good
Mechanism (I)
We first consider v ∈ SRI (1). Together with (iv) in Proposition 1, (A1) and (2), we obtain
that for any v ∈ SRI (1),
Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (38)
r1 −v2 r1 −v1

To solve for the provision probability, first we take first order derivatives with respect to v1
and v2 respectively, and we obtain
R v2
∂q ∗ (v1 , v2 ) ∂ r1 −v1
q ∗ (v1 , x)dx
(v1 + v2 ) − = λ1 (39)
∂v1 ∂v1
R v1
∂q ∗ (v1 , v2 ) ∂ r1 −v2
q ∗ (x, v2 )dx
(v1 + v2 ) − = λ2 (40)
∂v2 ∂v2
Then, we take cross partial derivative, with some algebra, we obtain

∂q ∗ (v1 , v2 )
(v1 + v2 ) =0 (41)
∂v1 ∂v2

Thus, when v ∈ SRI (1), q ∗ (v1 , v2 ) is separable, which can be written as

q ∗ (v1 , v2 ) = f (v1 ) + g(v2 ) (42)

Plugging (42) into (39) and (40), we obtain

r1 f ′ (v1 ) − (f (v1 ) + g(r1 − v1 )) = λ1 (43)

r1 g ′ (v2 ) − (g(v2 ) + f (r1 − v2 )) = λ2 (44)

Note both (43) and (44) involve the two functions f and g. We guess (C) that f (v1 ) + g(r −
v1 ) = 0 and g(v2 ) + f (r1 − v2 ) = 0 when v ∈ SRI (1), then we can easily solve (43) and (44),

33
and we obtain
λ1
f (v1 ) = v1 + c1 (45)
r1
λ2
g(v2 ) = v2 + c2 (46)
r1
In order for (C) to hold, we must have

λ 1 = λ 2 , c1 + c2 + λ 1 = 0 (47)

Now plugging (45),(46) and (47) into (42), we obtain for any v ∈ SRI (1),

λ1
q ∗ (v1 , v2 ) = (v1 + v2 − r1 ) (48)
r1

Then, given q ∗ (r1 , r1 ) = a, we obtain λ1 = a, and therefore, when v ∈ SRI (1),

a
q ∗ (v1 , v2 ) = (v1 + v2 − r1 ) (49)
r1

Finally, plugging (49) into (38), we obtain that µ = −ar1 . Now consider v ∈ SRI (2). Given
λ1 = λ2 = a, µ = −ar1 , (iv) in Proposition 1, (A1) and (2), we obtain for any v ∈ SRI (2),
Z v1 Z v2
∗ ∗
av1 + av2 − ar1 = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (50)
r1 −v2 0

a
Note that q ∗ (x, v2 ) = r1
(x + v2 − r1 ) when x ≤ r1 . Plugging it into (50), we obtain for any
v ∈ SRI (2),
Z r1 Z v1 Z v2
∗ a ∗
av1 + av2 − ar1 = (v1 + v2 )q (v) − (x + v2 − r1 )dx − q (x, v2 )dx − q ∗ (v1 , x)dx
r1 −v2 r1 r1 0
(51)
We take first order derivatives with respect to v1 and v2 respectively, and we obtain
R v2
q ∗ (v1 , x)dx
∂q ∗ (v1 , v2 ) ∂ 0
(v1 + v2 ) − =a (52)
∂v1 ∂v1
R v1 ∗
∂q ∗ (v1 , v2 ) av2 ∂ r1 q (x, v2 )dx
(v1 + v2 ) − − =a (53)
∂v2 r1 ∂v2
Then, we take cross partial derivative, with some algebra, we obtain

∂q ∗ (v1 , v2 )
(v1 + v2 ) =0 (54)
∂v1 ∂v2

34
Thus, when v ∈ SRI (2), q ∗ (v1 , v2 ) is separable, which can be written as

q ∗ (v1 , v2 ) = f (v1 ) + g(v2 ) (55)

Plugging (55) into (52) and (53), we obtain

v1 f ′ (v1 ) = a (56)

av2
(r1 + v2 )g ′ (v2 ) − =a (57)
r1
The solution to (56) and (57) is

f (v1 ) = a ln v1 + c1 (58)

a
g(v2 ) = v2 + c2 (59)
r1
Then we plug (58) and (59) into (50), with some algebra, we obtain that

c1 + c2 = −a ln r1 (60)

Therefore, for any v ∈ SRI (2),

a
q ∗ (v1 , v2 ) = a ln v1 + v2 − a ln r1 (61)
r1

Symmetrically, for v ∈ SRI (3),

a
q ∗ (v1 , v2 ) = a ln v2 + v1 − a ln r1 (62)
r1

Finally consider v ∈ SRI (4). Given λ1 = λ2 = a, µ = −ar1 , (iv) in Proposition 1, (A1) and
(2), we obtain for any v ∈ SRI (4),
Z v1 Z v2
∗ ∗
av1 + av2 − ar1 = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (63)
0 0

Note that q ∗ (x, v2 ) = a ln v2 + ra1 x − a ln r1 when x ≤ r1 and q ∗ (v1 , x) = a ln v1 + ra1 x − a ln r1

when x ≤ r1 . Plugging them into (63), we obtain for any v ∈ SRI (4),
Z r1 Z v1
∗ a
av1 + av2 − ar1 = (v1 + v2 )q (v) − (a ln v2 + x − a ln r1 )dx − q ∗ (x, v2 )dx
0 r1 r1
Z r1 Z v2 (64)
a
− (a ln v1 + x − a ln r1 )dx − q ∗ (v1 , x)dx
0 r 1 r1

35
We take first order derivatives with respect to v1 and v2 respectively, and we obtain
R v2
∂q ∗ (v1 , v2 ) ar1 ∂ r1
q ∗ (v1 , x)dx
(v1 + v2 ) − − =a (65)
∂v1 v1 ∂v1
R v1
∂q ∗ (v1 , v2 ) ar1 ∂ r1
q ∗ (x, v2 )dx
(v1 + v2 ) − − =a (66)
∂v2 v2 ∂v2
Then, we take cross partial derivative, with some algebra, we obtain

∂q ∗ (v1 , v2 )
(v1 + v2 ) =0 (67)
∂v1 ∂v2

Thus, when v ∈ SRI (2), q ∗ (v1 , v2 ) is separable, which can be written as

q ∗ (v1 , v2 ) = f (v1 ) + g(v2 ) (68)

Plugging (68) into (65) and (66), we obtain

ar1
(r1 + v1 )f ′ (v1 ) − =a (69)
v1
ar1
(r1 + v2 )g ′(v2 ) − =a (70)
v2
The solution to (69) and (70) is

f (v1 ) = a ln v1 + c1 (71)

g(v2 ) = a ln v2 + c2 (72)

By (B), we have c1 + c2 = 1. Therefore, for any v ∈ SRI (4),

q ∗ (v1 , v2 ) = a ln v1 + a ln v2 + 1 (73)

Then we plug (73) into (64) and checked that (64) holds with some algebra. Finally, as
1
q ∗ (r1 , r1 ) = a = 2a ln r1 + 1, we obtain that a = 1−2 ln r1
.

9.2 Characterization of Symmetric Worst-Case Joint Distribution

(I)
We start from constructing the joint distribution for the boundary value profiles, i.e., either
v1 = 1 or v2 = 1. Assume P r ∗(1, 1) = b. Consider value profiles (v1 , 1) in which 0 ≤ v1 < 1.

36
 R
Define S ∗ (v1 , 1) ≡ [v1 ,1) π ∗ (x, 0)dx + P r ∗ (1, 1) for 0 ≤ v1 < 1; S ∗ (1, 1) ≡ P r ∗(1, 1) = b.
∗
Then we have π ∗ (v1 , 1) = − ∂S ∂v(v11 ,1) for 0 ≤ v1 < 1. Since the weighted virtual values for
value profiles (v1 , 1) in which 0 ≤ v1 < 1 are zeroes, we obtain for 0 ≤ v1 < 1,

π ∗ (v1 , 1)(v1 + 1) − S ∗ (v1 , 1) = 0 (74)

Note (74) is a simple ordinary differential equation, to which the solution is

2b 2b
S ∗ (v1 , 1) = , π ∗ (v1 , 0) = ∀0 ≤ v1 < 1 (75)
v1 + 1 (v1 + 1)2
R
Then consider value profiles (1, v2 ) in which 0 ≤ v2 ≤ 1. Define S ∗ (1, v2 ) ≡ [v2 ,1)
π ∗ (1, x)dx+
P r ∗ (1, 1) for 0 ≤ v2 < 1. Symmetrically, we obtain that

2b 2b
S ∗ (1, v2 ) = , π ∗ (1, v2 ) = ∀0 ≤ v2 < 1 (76)
1 + v2 (1 + v2 )2

Now we will construct the joint distribution for the interior value profiles in the support,
R
i.e., v1 + v2 ≥ r1 and v1 6= 1, v2 6= 1. Define S ∗ (v1 , v2 ) ≡ [v1 ,1) π ∗ (x, v2 )dx + π ∗ (1, v2 ) for
(v1 ,v2 ) ∗
v1 + v2 ≥ r1 and v1 = 6 1, v2 6= 1. Then we have π ∗ (v1 , v2 ) = − ∂S ∂v1
for v1 + v2 ≥ r1
and v1 6= 1, v2 6= 1. Since the weighted virtual values for value profiles (v1 , v2 ) in which
v1 + v2 ≥ r1 and v1 6= 1, v2 6= 1 are zeroes, we obtain for v1 + v2 ≥ r1 and v1 6= 1, v2 6= 1,
Z
∗ ∗
π (v1 , v2 )(v1 + v2 ) − S (v1 , v2 ) − π ∗ (v1 , x)dx − π ∗ (v1 , 1) = 0 (77)
[v2 ,1)

By taking the cross partial derivative, we find S ∗ (v1 , v2 ) is not separable. We take the guess
and verify approach to solve for (77). We guess that for v1 + v2 ≥ r1 and v1 6= 1, v2 6= 1,

2b
S ∗ (v1 , v2 ) = (78)
(v1 + v2 )2

4b 2b
R 4b 2b
Then the LHS of (77) is (v1 +v 2 )3 (v1 + v2 ) − (v +v )2 − [v ,1) (v +x)3 ds −
1 2 2 1 (v1 +1)2
, which can be
shown to be 0 with some algebra. Thus, we verified the guess.
To solve for b, we use the fact that π ∗ (v) is a distribution. We note the marginal
distribution for agent 2 (the same for agent 1) is as follows: π2∗ (v2 ) = S(r1 − v2 , v2 ) =
2b
(r1 −v2 +v2 )2
= r2b2 for 0 ≤ 2b
v2 ≤ r1 , π2∗ (v2 ) = S(0, v2 ) = (0+v 2)
2 =
2b
v22
for r1 < v2 < 1 and
1
P r2∗ (v2 = 1) = S ∗ (0, 1) = 2b. Since the integration is 1, we obtain
Z
2b 2b
· r1 + + 2b = 1 (79)
r12 (r1 ,1) v22

37
Thus, we obtain
r1
b= (80)
4
So far we have constructed Symmetric Worst-Case Joint Distribution (I). The
final step is to make sure that Symmetric Worst-Case Joint Distribution (I) satisfies
the mean constraints, which will allow us to solve for the monopoly reserve r1 . Given
the marginal distribution for agent 2 (the same for agent 1), we have the following mean
constraint, Z r1 Z 1
2b 2b
2
xdx + 2
xdx + 2b = m (81)
0 r1 r1 x

Plugging (80) into (81), we obtain

r1 (3 − 2 ln r1 )
=m (82)
4

Note that the LHS of (82) is strictly increasing15 with respect to r1 for r1 ∈ (0, 1). In
addition, the LHS of (82) is 34 when r1 = 1. Therefore, for any m ∈ (0, 34 ), there is a unique
solution r1 ∈ (0, 1) to (82). Indeed, r1 = exp(W−1 (−2m exp(− 32 )) + 32 ).

9.3 Characterization of Asymmetric Maxmin Public Good

Mechanism (I)
We first consider v ∈ ARI (1). Together with (iv) in Proposition 1, (A3) and (2), we obtain
that for any v ∈ ARI (1),
Z v1 Z v2
∗ ∗
λ1 v1 + λ2 v2 + µ = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx (83)
s s
s1 − s1 v2 s2 − s2 v1
2 1

To solve for the provision probability, first we take first order derivatives with respect to v1
and v2 respectively, and we obtain
R v2
∗
∂q (v1 , v2 ) ∂ s
s2 − s2 v1
q ∗ (v1 , x)dx
1
(v1 + v2 ) − = λ1 (84)
∂v1 ∂v1
R v1
∗
∂q (v1 , v2 ) ∂ s
s2 − s2 v2
q ∗ (x, v2 )dx
1
(v1 + v2 ) − = λ2 (85)
∂v2 ∂v2
15 1−2 ln r1
The first order derivative is 4 > 0 for r1 ∈ (0, 1).

38
Then, we take cross partial derivative, with some algebra, we obtain

∂q ∗ (v1 , v2 )
(v1 + v2 ) =0 (86)
∂v1 ∂v2

Thus, when v ∈ ARI (1), q ∗ (v1 , v2 ) is separable, which can be written as

q ∗ (v1 , v2 ) = f (v1 ) + g(v2 ) (87)

Plugging (87) into (84) and (85), we obtain

s2 s2 s2
(v1 + s2 − v1 )f ′ (v1 ) − (f (v1 ) + g(s2 − v1 )) = λ1 (88)
s1 s1 s1
s1 s1 s1
(v2 + s1 − v2 )g ′ (v2 ) − (g(v2 ) + f (s1 − v2 )) = λ2 (89)
s2 s2 s2
Note both (88) and (89) involve the two functions f and g. We guess (C3) that
f (v1 ) + g(s2 − ss21 v1 ) = 0 and g(v2 ) + f (s1 − ss21 v2 ) = 0 when v ∈ ARI (1), then we can
easily solve (88) and (89), and we obtain

λ1 s2
f (v1 ) = s2 ln (v1 + s2 − v1 ) + c1 (90)
1 − s1 s1

λ2 s1
g(v2 ) = s1 ln (v2 + s1 − v2 ) + c2 (91)
1 − s2 s2
In order for (C3) to hold, we must have

λ1 λ2
s2 + = 0, c1 + c2 = 0 (92)
1 − s1 1 − ss21

Now plugging (90),(91) and (92) into (87), we obtain for any v ∈ ARI (1),

λ1 s2 s1
q ∗ (v1 , v2 ) = s2 (ln (v1 + s2 − v1 ) − ln (v2 + s1 − v2 )) (93)
1 − s1 s1 s2
s
c(1− s2 )
Then, given q ∗ (s1 , s2 ) = c, we obtain λ1 = ln
s1
1
, and therefore, when v ∈ ARI (1),
s2

c s2 s1
q ∗ (v1 , v2 ) = s1 (ln (v1 + s2 − v1 ) − ln (v2 + s1 − v2 )) (94)
ln s2 s1 s2

39
Finally, plugging (94) into (93), we obtain that µ = − c(sln1 −s
s1
2)
. Now consider v ∈ ARI (2).
s2
s s
c(1− s2 ) c(1− s1 )
Given λ1 = ln
s1
1
, λ2 = − ln
s1
2
, µ = − c(sln1 −s
s1
2)
, (iv) in Proposition 1, (A3) and (92), we
s2 s2 s2

obtain for any v ∈ ARI (2),

Z v1 Z v2
c s2 s1
s1 ((1− )v1 −(1− )v2 −(s1 −s2 )) = (v1 +v2 )q ∗ (v)− ∗
q (x, v2 )dx− q ∗ (v1 , x)dx
ln s2 s1 s2 s
s1 − s1 v2 0
2
(95)
Note that q ∗ (x, v2 ) = lncs1 (ln (x + s2 − ss12 x) − ln (v2 + s1 − ss21 v2 )) when x ≤ s1 . Plugging it
s2

into (95), we obtain for any v ∈ ARI (2),

c s2 s1
s1 ((1 − )v1 − (1 − )v2 − (s1 − s2 )) = (v1 + v2 )q ∗ (v)
ln s2 s1 s2
Z s1
c s2 s1
− s (ln (x + s 2 − x) − ln (v2 + s 1 − v2 ))dx
s1 − s1 v2 ln s2 s1 s2
s 1

Z v1 2 Z v2
∗
− q (x, v2 )dx − q ∗ (v1 , x)dx
s1 0
(96)

We take first order derivatives with respect to v1 and v2 respectively, and we obtain
R v2
∂q ∗ (v1 , v2 ) ∂ 0
q ∗ (v1 , x)dx c s2
(v1 + v2 ) − = s1 (1 − ) (97)
∂v1 ∂v1 ln s2 s1
R v1
∂q ∗ (v1 , v2 ) c s1 s1 v2 ∂ s1
q ∗ (x, v2 )dx c s1
(v1 +v2 ) + s1 (1− ) s1 − =− s1 (1− ) (98)
∂v2 ln s2 s2 s2 v2 + s1 − v
s2 2
∂v2 ln s2 s2
Then, we take cross partial derivative, with some algebra, we obtain

∂q ∗ (v1 , v2 )
(v1 + v2 ) =0 (99)
∂v1 ∂v2

Thus, when v ∈ ARI (2), q ∗ (v1 , v2 ) is separable, which can be written as

q ∗ (v1 , v2 ) = f (v1 ) + g(v2 ) (100)

Plugging (100) into (97) and (98), we obtain

c s2
v1 f ′ (v1 ) = s1 (1 − ) (101)
ln s2 s1

40
 c s1 s1 v2 c s1
(s1 + v2 )g ′(v2 ) − s1 (1 − ) s1 =− s1 (1 − ) (102)
ln s2 s2 s2 v2 + s1 − v
s2 2
ln s2 s2
The solution to (101) and (102) is

c s2
f (v1 ) = s1 (1 − ) ln v1 + c1 (103)
ln s2 s1

c s1
g(v2 ) = − s1 ln (v2 + s1 − v2 ) + c2 (104)
ln s2 s2
Then we plug (103) and (104) into (96), with some algebra, we obtain that

c s2
c1 + c2 = ln s1 (105)
ln ss21 s1

Therefore, for any v ∈ ARI (2),

c s2 s1 s2
q ∗ (v1 , v2 ) = s1 ((1 − ) ln v1 − ln (v2 + s1 − v2 ) + ln s1 ) (106)
ln s2 s1 s2 s1

Symmetrically, for v ∈ ARI (3),

c s2 s1 s1
q ∗ (v1 , v2 ) = s1 (ln (v1 + s2 − v1 ) − (1 − ) ln v2 − ln s2 ) (107)
ln s2 s1 s2 s2
s s
c(1− s2 ) c(1− s1 )
Finally consider v ∈ AR (4). Given λ1 = I
ln
s1
1
, λ2 = − ln
s1
2
, µ = − c(sln1 −s
s1
2)
, (iv) in
s2 s2 s2

Proposition 1, (A3) and (92), we obtain for any v ∈ ARI (4),

Z v1 Z v2
c s2 s1
s1 ((1 − )v1 − (1 − )v2 − (s1 − s2 )) = (v1 + v2 )q ∗ (v) − ∗
q (x, v2 )dx − q ∗ (v1 , x)dx
ln s2 s1 s2 0 0
(108)
s2
Note that q ∗ (x, v2 ) = ln
c
s1 (ln (x + s2 − s1
x) − (1 − ss21 ) ln v2 − ss12 ln s2 ) when x ≤ s1 and
s2
q ∗ (v1 , x) = ln
c
s1 ((1 − ss21 ) ln v1 − ln (x + s1 − ss21 x) + ss12 ln s1 ) when x ≤ s2 . Plugging them into
s2

(108), we obtain for any v ∈ ARI (4),

Z v1 Z v2
c s2 s1 ∗ ∗
s1 ((1 − )v1 − (1 − )v2 − (s1 − s2 )) = (v1 + v2 )q (v) − q (x, v2 )dx − q ∗ (v1 , x)dx
ln s2 s1 s2 s1 s2
Z s1
c s2 s1 s1
− ( s1 (ln (x + s2 − x) − (1 − ) ln v2 − ln s2 ))dx
0 ln s2 s1 s2 s2
Z s2
c s2 s1 s2
− ( s1 ((1 − ) ln v1 − ln (x + s1 − x) + ln s1 ))dx
0 ln s2 s1 s2 s1
(109)

41
We take first order derivatives with respect to v1 and v2 respectively, and we obtain
R v2
∂q ∗ (v1 , v2 ) cs2 s2 1 ∂ s2
q ∗ (v1 , x)dx c s2
(v1 + v2 ) − s1 (1 − ) − = s1 (1 − ) (110)
∂v1 ln s2 s1 v1 ∂v1 ln s2 s1
R v1
∂q ∗ (v1 , v2 ) cs1 s1 1 ∂ r1
q ∗ (x, v2 )dx c s1
(v1 + v2 ) + s1 (1 − ) − =− s1 (1 − ) (111)
∂v2 ln s2 s2 v2 ∂v2 ln s2 s2
Then, we take cross partial derivative, with some algebra, we obtain

∂q ∗ (v1 , v2 )
(v1 + v2 ) =0 (112)
∂v1 ∂v2

Thus, when v ∈ ARI (4), q ∗ (v1 , v2 ) is separable, which can be written as

q ∗ (v1 , v2 ) = f (v1 ) + g(v2 ) (113)

Plugging (113) into (110) and (111), we obtain

cs2 s2 1 c s2
(s2 + v1 )f ′ (v1 ) − s1 (1 − ) = s1 (1 − ) (114)
ln s2 s1 v1 ln s2 s1

cs1 s1 1 c s1
(s1 + v2 )g ′(v2 ) + s1 (1 − ) = − s1 (1 − ) (115)
ln s2 s2 v2 ln s2 s2
The solution to (114) and (115) is

c s2
f (v1 ) = s1 (1 − ) ln v1 + c1 (116)
ln s2 s1

c s1
g(v2) = − s1 (1 − ) ln v2 + c2 (117)
ln s2 s2

By (B), we have c1 + c2 = 1. Therefore, for any v ∈ ARI (4),

c s2 s1
q ∗ (v1 , v2 ) = s1 ((1 − ) ln v1 − (1 − ) ln v2 ) + 1 (118)
ln s2 s1 s2

Then we plug (118) into (109) and checked that (109) holds with some algebra. Finally, as
q ∗ (s1 , s2 ) = c = lncs1 ((1− ss21 ) ln s1 −(1− ss12 ) ln s2 )+1, we obtain that c = (1− s2 ) ln s11 −(1− s1 ) ln s2 .
s2 s1 s2
1− s
ln s1
2

42
10 Appendix B
10.1 Proof of Proposition 1
(i) q(·, v−i ) nondecreasing:
Dominant strategy incentive compatibility for a type vi of agent i requires that for any
vi′ 6= vi :
vi q(vi , v−i ) − ti (vi , v−i ) ≥ vi q(vi′ , v−i ) − ti (vi′ , v−i )

DSIC also requires that:

vi′ q(vi′ , v−i ) − ti (vi′ , v−i ) ≥ vi′ q(vi , v−i ) − ti (vi , v−i ).

Adding the two inequalities, we have that:

(vi − vi′ )(q(vi , v−i ) − q(vi′ , v−i )) ≥ 0

It follows that q(vi , v−i ) ≥ q(vi′ , v−i ) whenever vi > vi′ .

R vi
(ii) ti (vi , v−i ) = vi q(vi , v−i ) − 0
q(s, v−i )ds:
Define
Ui (vi , v−i ) = vi q(vi , v−i ) − ti (vi , v−i )

By the two inequalities in (i), we get

(vi′ − vi )q(vi , v−i ) ≤ Ui (vi′ , v−i ) − Ui (vi , v−i ) ≤ (vi′ − vi )q(vi′ , v−i )

Dividing throughout by vi′ − vi :

Ui (vi′ , v−i ) − Ui (vi , v−i )

q(vi , v−i ) ≤ ≤ q(vi′ , v−i )
(vi′ − vi )

As vi ↑ vi′ , we get:
dUi (vi , v−i )
= q(vi , v−i )
dvi
Then we get Z vi
ti (vi , v−i ) = vi q(vi , v−i ) − q(s, v−i ) − Ui (0, v−i )
0

Note Ui (0, v−i ) ≥ 0 by the EPIR constraint. If Ui (0, v−i ) > 0, then we can reduce it to
0 so that we can increase the revenue from all value profiles and the value of the problem

43
will be strictly greater. Thus, for any maxmin public good mechanism, Ui (0, v−i ) = 0 and
Rv
ti (vi , v−i ) = vi q(vi , v−i ) − 0 i q(s, v−i ).

10.2 Proof of Lemma 1

Given a DSIC and EPIR mechanism (q, t), the (P) primal minimization problem of Nature
is as follows (with dual variables in the bracket):

N
Z X
(P rimal) min ti (v)dF
F ∈Π(m1 ,··· ,mN )
i=1

s.t. Z
vi dF = mi (λi ) ∀i
Z
dF = 1 (µ)

It has the following (D) dual maximization problem:

N
X
(Dual) max λi mi + µ
λ1 ,··· ,λN ,µ∈R
i=1

s.t.
N
X N
X
λi vi + µ ≤ ti (v) (dF ) ∀v
i=1 i=1
P
Note that the value of (P) is bounded by N as N i=1 ti (v) ≤ N. In addition, the trivial joint
distribution that put all probability mass on the point (m1 , · · · , mN ) is in the interior of
the primal cone. Then by Theorem 3.12 in Anderson and Nash (1987), strong duality holds.
Then, by the Complementary Slackness, (2) holds. And (1) is the feasibility constraint of
(D).

10.3 Proof of Theorem 1

(i): Symmetric Maxmin Public Good Mechanism (I) is a best response to Symmetric
Worst-Case Joint Distribution (I). Note Symmetric Worst-Case Joint Distribution (I)
satisfies (74) and (77). Also note there is a probability mass on the value profile (1,1). Thus
(4), (5) and (6) hold. Then any feasible and monotone mechanism in which the public good
is provided with some positive probability if and only if v1 + v2 > r1 and the public good is
provided with probability 1 when (v1 , v2 ) = (1, 1) is a best response for the principal. It is

44
easy to see that Symmetric Maxmin Public Good Mechanism (I) is such a mechanism.
(ii): Symmetric Worst-Case Joint Distribution (I) is a best response to Maxmin
Public Good Mechanism (I). We use the duality theory to show (ii). First note that
by (79) and (81), all the three constraints in (P) holds. By the weighted virtual value
representation, the value of (P) given Symmetric Worst-Case Joint Distribution (I) and
Symmetric Maxmin Public Good Mechanism (I) is simply P r(1, 1)×(1+1) = r21 . Second, the
constraints in (D) hold for all value profiles. To see this, note for any value profile v = (v1 , v2 )
outside the support of Symmetric Worst-Case Joint Distribution (I), since λ1 = λ2 = a > 0,
we have
λ1 v1 + λ2 v2 + µ < λ1 r1 + λ2 0 + µ = 0

For any value profile v = (v1 , v2 ) inside the support of Symmetric Worst-Case Joint
Distribution (I), the constraints (the complementary slackness) hold given (38), (50) and
(62). Finally, the value of (D) given the constructed λ1 , λ2 , µ is λ1 m + λ2 m + µ, which, by
r1
some algebra, is equal to 2
. By the linear programming duality theory, (ii) holds and the
revenue guarantee is r21 .

10.4 Proof of Theorem 2

(i): Symmetric Maxmin Public Good Mechanism (II) is a best response to
Symmetric Worst-Case Joint Distribution (II). The proof is similar to the proof of (i)
of Theorem 1.
(ii): Symmetric Worst-Case Joint Distribution (II) is a best response to Symmetric
Maxmin Public Good Mechanism (II). We use the duality theory to show (ii). First
note that by construction, all the constraints in (P) holds. By the weighted virtual value
representation, the value of (P) given Symmetric Worst-Case Joint Distribution (II) and
2
Symmetric Maxmin Public Good Mechanism (II) is simply P r(1, 1) × (1 + 1) = (r2 +1) 2
.
Second, the constraints in (D) hold for all value profiles. To see this, note for any value
profile v = (v1 , v2 ) outside the support of Symmetric Worst-Case Joint Distribution (II),
1+r2
since λ1 = λ2 = 1−r2
> 0, we have

λ1 v1 + λ2 v2 + µ < λ1 r2 + λ2 · 1 + µ = 0

For any value profile v = (v1 , v2 ) inside the support of Symmetric Worst-Case Joint
Distribution (II), the constraint (the complementary slackness) holds given (7). Finally,
the value of (D) given the constructed λ1 , λ2 , µ is λ1 m + λ2 m + µ, which, by some algebra,
(1+r2 )(2m−(1+r2 )) (1+r2 )2
is equal to 1−r2
= 2
. By the linear programming duality theory, (ii) holds

45
 (1+r2 )2
and the revenue guarantee is 2
.

10.5 Proof of Lemma 2

∗ ∗
To facilitate the exposition, we define new functions H1I (s1 , s2 ) and H2I (s1 , s2 ) as follows.

I
 H1 (s1 , s2 )
 s1 6= s2 , s1 6= 0, s1 6= 0
∗
H1I (s1 , s2 ) := −2s1 ln s1 +3s1
4
s1 = s2 6= 0


0 s1 = 0 or s2 = 0

I
 H2 (s1 , s2 )
 s1 6= s2 , s1 6= 0, s1 6= 0
∗
H2I (s1 , s2 ) := −2s1 ln s1 +3s1
4
s1 = s2 =
6 0


0 s1 = 0 or s2 = 0
We start from establishing the following claims regarding some properties of the functions
∗ ∗
H1I (s1 , s2 ) and H2I (s1 , s2 ), which will play a crucial role in establishing Lemma 2.
∗ ∗
Claim 1. H1I (s1 , s2 ) and H2I (s1 , s2 ) are both continuous for s1 ∈ [0, 1] and s2 ∈ [0, 1].
∗
Proof of Claim 1. We will first establish the continuity of H1I (s1 , s2 ). Note when s1 6=
s2 , s1 6= 0, s2 6= 0, the continuity holds as H1I (s1 , s2 ) is some analytic function. Therefore
−2s1 ln s1 +3s1
it suffices to show that lims2 →s1 6=0 H1I (s1 , s2 ) = 4
, lims1 →0 H1I (s1 , s2 ) = 0 and
lims2 →0 H1I (s1 , s2 ) = 0. To see these, note

lim H1I (s1 , s2 ) = lim H1I (s1 , s2 )

s2 →s1 6=0 s2 −s1 :=ǫ→0
2 s1
s1 (s1 + ǫ) s1 ln s1 +ǫ + ǫ(ǫ + s1 )
= lim ( − ln s1 )
ǫ→0 s1 + s1 + ǫ ǫ2
s2
s1 − 1 + 2ǫ + s1
= lim ( s1 +ǫ − ln s1 )
ǫ→0 2 2ǫ
s21
s1 (s1 +ǫ)2 + 2
= lim ( − ln s1 )
ǫ→0 2 2
−2s1 ln s1 + 3s1
=
4

The third equality and the fourth equality hold by the L’Hôpital’s Rule. Also note that
limx→0 x ln x = 0 and limx→0 x2 ln x = limx→0 x · limx→0 x ln x = 0, which imply that
∗
lims1 →0 H1I (s1 , s2 ) = 0 and lims2 →0 H1I (s1 , s2 ) = 0. By symmetry, the continuity of H2I (s1 , s2 )
can be similarly established.
∗
Claim 2. Fix any s2 ∈ (0, 1], H1I (s1 , s2 ) is strictly increasing w.r.t. s1 for s1 ≤ s2 .

46
 ∗
Proof of Claim 2. Taking first order derivative w.r.t. s1 to H1I when s1 6= s2 , s1 6= 0, s2 6= 0,
with some algebra, we obtain that
∗
∂H1I (s1 , s2 ) s22 s21 (s1 + 3s2 ) s1
= [− ln − (s1 − s2 )2 ln s1 + s1 (3s1 + s2 )]
∂s1 (s1 − s2 )2 (s1 + s2 )2 s1 − s2 s2

Then it suffices to show that for any s1 ∈ (0, s2 ),

s21 (s1 + 3s2 ) s1

− ln − (s1 − s2 )2 ln s1 + s1 (3s1 + s2 ) > 0 (119)
s1 − s2 s2
s1 s1
Let z1 := s2
∈ (0, 1). Plugging s2 = z1
into (119), it suffices to show that for z1 ∈ (0, 1),

z12 (3 + z1 )
ln z1 − (z1 − 1)2 ln s1 + z1 (3z1 + 1) > 0 (120)
1 − z1

Note that −(z1 −1)2 ln s1 > 0 and that 1 −z1 > 0, then it suffices to show that for z1 ∈ (0, 1),

z1 (1 − z1 )(3z1 + 1)
h(z1 ) := ln z1 + >0 (121)
z12 (3 + z1 )

Now taking first order derivative to h(z1 ), with some algebra, we obtain that for z1 ∈ (0, 1),

(z1 − 3)(1 − z1 )2
h′ (z1 ) = <0 (122)
z12 (3 + z1 )2

Note that h(1) = 0, then together with (122), (121) holds.

∗
∂H1I (s1 ,s2 ) 1−6 ln s1
Claim 3. ∂s1
→ 24
as s2 → s1 6= 0.

47
Proof of Claim 3.
∗ ∗
∂H1I (s1 , s2 ) ∂H1I (s1 , s2 )
lim = lim
s2 →s1 6=0 ∂s1 ǫ:=s2 −s1 →0 ∂s1
(s1 + ǫ) 2 −s21 (4s1 + 3ǫ) ln s1s+ǫ 1
+ ǫ3 ln s1 − ǫs1 (ǫ + 4s1 )
= lim
ǫ→0 (s1 + s1 + ǫ)2 −ǫ3
−s21 (3 ln s1s+ǫ
1
− 4ss11 +3ǫ
+ǫ
) + 3ǫ2 ln s1 − s1 (4s1 + 2ǫ)
= lim
ǫ→0 −12ǫ2
2 3 s1
−s1 (− s1 +ǫ + (s1 +ǫ)2 ) + 6ǫ ln s1 − 2s1
= lim
ǫ→0 −24ǫ
−s1 ( (s1 +ǫ)2 − (s12s+ǫ)
2 3 1
3 ) + 6 ln s1
= lim
ǫ→0 −24
1 − 6 ln s1
=
24

where the third equality, the fourth equality and the fifth equality hold by the L’Hôpital’s
Rule.
∗
Claim 4. Fix any s1 ∈ (0, 1), H1I (s1 , s2 ) is strictly increasing w.r.t. s2 for s2 ∈ (0, 1).
∗
Proof of Claim 4. Taking first order derivative w.r.t. s2 to H1I when s1 6= s2 , s1 6= 0, s2 6= 0,
with some algebra, we obtain that
∗
∂H1I (s1 , s2 ) s22 2s1 s2 (s1 + s2 ) s1
= 2 2
[( + s21 ) ln − (s1 − s2 )2 ln s1 − s1 (s1 + 3s2 )]
∂s2 (s1 − s2 ) (s1 + s2 ) s1 − s2 s2

Then it suffices to show that for any s1 ∈ (0, 1),

s21 (s1 + 3s2 ) s1

− ln − (s1 − s2 )2 ln s1 + s1 (3s1 + s2 ) > 0 (123)
s1 − s2 s2

Let z2 := ss21 ∈ (0, 1) ∪ (1, ∞). Plugging s2 = s1

z2
into (123), it suffices to show that for
z2 ∈ (0, 1) ∪ (1, ∞),

z2 (z22 + z2 + 2)
ln z1 − (z1 − 1)2 ln s1 − z2 (z2 + 3) > 0 (124)
z2 − 1

Note that −(z2 − 1)2 ln s1 > 0, then it suffices to show that for z2 ∈ (0, 1) ∪ (1, ∞),

z2 (z22 + z2 + 2)
ln z1 − z2 (z2 + 3) > 0 (125)
z2 − 1

48
Note that z2 > 0, then it suffices to show that for z2 ∈ (1, ∞),

(z2 + 3)(z2 − 1)
i(z2 ) := ln z2 − >0 (126)
z22 + z2 + 2

and that for z2 ∈ (0, 1),

i(z2 ) < 0 (127)

Now taking first order derivative to i(z2 ), with some algebra, we obtain that for z2 ∈ (0, ∞),

′ (z2 + 1)(z2 + 4)(1 − z2 )2

i (z2 ) = >0 (128)
z2 (z22 + z2 + 2)2

Note that i(1) = 0, then together with (128), (126) and (127) hold.
∗
∂H1I (s1 ,s2 ) 5−6 ln s1
Claim 5. ∂s2
→ 24
as s2 → s1 6= 0.
Proof of Claim 5.
∗ ∗
∂H1I (s1 , s2 ) ∂H1I (s1 , s2 )
lim = lim
s2 →s1 6=0 ∂s2 ǫ:=s2 −s1 →0 ∂s2
(s1 + ǫ) 2 (2s1 (s1 + ǫ)(2s1 + ǫ) − ǫs21 ) ln s1s+ǫ
1
+ ǫ3 ln s1 + ǫs1 (4s1 + 3ǫ)
= lim
ǫ→0 (s1 + s1 + ǫ)2 −ǫ3
ǫs21
(2s21 (2ǫ + 3s1 ) − s21 ) ln s1s+ǫ
1
− (2s1 (2s1 + ǫ) − s1 +ǫ
) + 3ǫ2 ln s1 + s1 (4s1 + 6ǫ)
= lim
ǫ→0 −12ǫ2
s1 (4s1 +5ǫ) s31
4s1 ln s1s+ǫ
1
− s1 +ǫ
− (2s1 − ) + 6ǫ ln s1 + 6s1
(s1 +ǫ)2
= lim
ǫ→0 −24ǫ
s21 2s31
− s4s 1
1 +ǫ
+ (s1 +ǫ)2
− (s1 +ǫ)3
+ 6 ln s1
= lim
ǫ→0 −24
5 − 6 ln s1
=
24

where the third equality, the fourth equality and the fifth equality hold by the L’Hôpital’s
Rule.

Now we are ready to prove Lemma 2. Fix any m1 ∈ (0, 43 ). Let s∗2 (m1 ) ∈ (0, 1)
denote the solution to −2s2 ln4s2 +3s2 = m1 . Let s∗1 (m1 ) ∈ (0, 1) denote the solution
to 1+s s1
( 2s1 −12 ln s1 + 1−s
1 (1−s1 )
1
1
) = m1 . Then by Claim 1, Claim 2, Claim 4, when s1 ∈
[s∗1 (m1 ), s∗2 (m1 )], there exists a strictly decreasing function F I such that s1 = F I (s2 ) ≤ s2
∗
is the unique solution to H1I (s1 , s2 ) = m1 for any s2 ∈ [s∗2 (m1 ), 1]. By Claim 2, 3, Claim
∗ ∗
∂H1I (s1 ,s2 ) ∂H1I (s1 ,s2 )
4 and Claim 5, the continuous functions16 ∂s1
and ∂s2
are strictly positive and
∗ ∗
16 ∂H1I (s1 ,s2 ) 1−6 ln s1 ∂H1I (s1 ,s2 ) 5−6 ln s1
When s1 = s2 , let ∂s1 = 24 and ∂s2 = 24 , then by Claim 3 and Claim 5,

49
bounded on the compact set [s∗1 (m1 ), s∗2 (m1 )] × [s∗2 (m1 ), 1]. Then by the (Global) Implicit
∗
Function Theorem, F I (s2 ) is continuous on [s∗2 (m1 ), 1]. Plugging s1 = F I (s2 ) to H2I (s1 , s2 ),
∗ ∗
we obtain GI (s2 ) := H2I (F I (s2 ), s2 ). Given the continuity of H2I and F I , we see that GI
is also continuous at any s2 ∈ [s∗2 (m1 ), 1]. Note that when s2 = s∗2 (m1 ), F I (s2 ) = s2 and
therefore GI (s2 ) = m1 ; when s2 = 1, GI (s2 ) = BI (m1 ). Then by the Intermediate Value
Theorem, there exists s2 ∈ [s∗2 (m1 ), 1] such that GI (s2 ) = m2 for any m2 ∈ (BI (m1 ), m1 ).

10.6 Proof of Theorem 3

(i): Asymmetric Maxmin Public Good Mechanism (I) is a best response to
Asymmetric Worst-Case Joint Distribution (I). The proof is similar to the proof
of (i) of Theorem 1.
(ii): Asymmetric Worst-Case Joint Distribution (I) is a best response to Asymmetric
Maxmin Public Good Mechanism (I): we use the duality theory to show (ii). First
note that by construction, all the constraints in (P) holds. By the weighted virtual value
representation, the value of (P) given Asymmetric Worst-Case Joint Distribution (I) and
Asymmetric Maxmin Public Good Mechanism (I) is simply P r(1, 1) × (1 + 1) = ss11+s s2
2
.
Second, the constraints in (D) hold for all value profiles. To see this, note for any value
profile v = (v1 , v2 ) outside the support of Asymmetric Worst-Case Joint Distribution (I),
since λ1 > 0 and λ2 = ss21 λ1 >0, we have

λ1 v1 + λ2 v2 + µ < λ1 s1 + λ2 · 0 + µ = 0

For any value profile v = (v1 , v2 ) inside the support of Asymmetric Worst-Case Joint
Distribution (I), the constraints (the complementary slackness) hold given (83),(95) and
(108). In addition, the value of (D) given the constructed λ1 , λ2 , µ is λ1 m1 + λ2 m2 + µ,
s
c(1− s2 ) s1 s1 s2
which, by some algebra, is equal to ln
s1
1
(m1 + m
s2 2
− s1 ) = s1 +s2
. Finally, by Lemma 2,
s2
the solution to (12) and (13) exists. By the linear programming duality theory, (ii) holds
and the revenue guarantee is ss11+s
s2
2
.

10.7 Proof of Lemma 3

∗ ∗
To facilitate the exposition, we define new functions H1II (t1 , t2 ) and H2II (t1 , t2 ) as follows.
(
∗ H1II (t1 , t2 ) t1 6= t2
H1II (t1 , t2 ) := −t21 +2t1 +3
4
t1 = t2
∗ ∗
∂H1I (s1 ,s2 ) ∂H1I (s1 ,s2 )
∂s1 and ∂s2 are continuous.

50
 (
II ∗ H2II (t1 , t2 ) t1 6= t2
H2 (t1 , t2 ) := −t21 +2t1 +3
4
t1 = t2
We start from establishing the following claims regarding some properties of the functions
∗ ∗
H1I (s1 , s2 ) and H2I (s1 , s2 ), which will play a crucial role in establishing Lemma 3.
∗ ∗
Claim 6. H1II (t1 , t2 ) and H2II (t1 , t2 ) are both continuous for t1 ∈ [0, 1] and t2 ∈ [0, 1].
∗
Proof of Claim 6. We will first establish the continuity of H1II (t1 , t2 ). Note when t1 =6 t2 ,
the continuity holds as H1II (t1 , t2 ) is some analytic function. Therefore it suffices to show
−t21 +2t1 +3
that limt2 →t1 H1II (t1 , t2 ) = 4
. To see this, note we have

lim H1II (t1 , t2 ) = lim H1II (t1 , t2 )

t2 →t1 t2 −t1 :=ǫ→0

(1 + t1 )(1 − t1 )2 (1 + t1 + ǫ) ln 1+t1 +ǫ
1+t1
− ǫ(1 − t1 )(1 − t1 (t1 + ǫ)) 1 + t1
= lim +
ǫ→0 2ǫ2 2
(1 + t1 )(1 − t1 )2 (1 + ln 1+t1 +ǫ
1+t1
) − (1 − t1 )(1 − t21 − 2t1 ǫ) 1 + t1
= lim +
ǫ→0 4ǫ 2
(1 + t1 )(1 − t1 )2 1+t11 +ǫ + 2t1 (1 − t1 ) 1 + t1
= lim +
ǫ→0 4 2
−t21 + 2t1 + 3
=
4

where the third equality and the fourth equality hold by the L’Hôpital’s Rule. By symmetry,
∗
the continuity of H2II (t1 , t2 ) can be similarly established.
∗
Claim 7. Fix any t2 ∈ [0, 1], H1II (t1 , t2 ) is strictly increasing w.r.t. t1 for t1 ∈ (0, 1).
∗
Proof of Claim 7. Taking first order derivative w.r.t. t1 to H1II when s1 6= s2 , with some
algebra, we obtain that
∗
∂H1II (t1 , t2 ) (1 − t1 )(1 + t2 ) 2(1 + t1 )(1 − t1 ) 1 + t2
= 2
[(−1 − 3t1 − ) ln + 2(t2 − 1)]
∂t1 2(t1 − t2 ) t1 − t2 1 + t1

Then it suffices to show that for any t1 ∈ (0, 1),

2(1 + t1 )(1 − t1 ) 1 + t2
(−1 − 3t1 − ) ln + 2(t2 − 1) > 0 (129)
t1 − t2 1 + t1
1+t2
Let z3 := 1+t1
∈ [ 12 , 1) ∪ (1, 2]. Plugging t2 = z3 (1 + t1 ) − 1 into (129), it suffices to show
that for z3 ∈ [ 21 , 1) ∪ (1, 2],

2 2
t1 (2z3 − (3 − ) ln z3 ) + (−1 − ) ln z3 + 2z3 − 4 > 0 (130)
1 − z3 1 − z3

51
Then it suffices to show that for z3 ∈ [ 21 , 1) ∪ (1, 2],

2
2z3 − (3 − ) ln z3 > 0 (131)
1 − z3

2
(−1 − ) ln z3 + 2z3 − 4 > 0 (132)
1 − z3
2z3 (1−z3 )
To show (131), let j(z3 ) := − ln z3 + 1−3z3
. Taking first order derivative, with some
algebra, we obtain that
(6z3 − 1)(1 − z3 )2
j ′ (z3 ) = (133)
z3 (1 − 3z3 )2
Observe that implies that j(z3 ) is increasing for z3 ≥ 21 . Also note j(1) = 0. Then j(z3 ) > 0
for z3 > 1 and j(z3 ) < 0 for z3 ∈ [ 12 , 1). Therefore (131) holds. To show (132), let
k(z3 ) := ln z3 + (1−z3z3)(2z
−3
3 −4)
. Taking first order derivative to k(z3 ), with some algebra,
we obtain that
(9 − 2z3 )(1 − z3 )2
k ′ (z3 ) = (134)
z3 (z3 − 3)2
Observe that implies that k(z3 ) is increasing for z3 ≤ 2. Also note k(1) = 0. Then k(z3 ) > 0
for 2 ≥ z3 > 1 and j(z3 ) < 0 for z3 ∈ [ 21 , 1). Therefore (132) holds.

∗
∂H1II (t1 ,t2 ) (1−t1 )(5t1 +7)
Claim 8. ∂t1
→ 12(1+t1 )
as t2 → t1 .

Proof of Claim 8.
∗ ∗
∂H1II (t1 , t2 ) ∂H1II (t1 , t2 )
lim = lim
t2 →t1 ∂t1 ǫ:=t2 −t1 →0 ∂t1
2 1+t +ǫ
(1 − t1 )(1 + t1 + ǫ) ((1 + 3t1 )ǫ − 2(1 − t1 )) ln 1+t1 1 − 2ǫ(t1 − 1 + ǫ)
= lim
ǫ:=t2 −t1 →0 2 −ǫ3
(1+3t1 )ǫ−2(1−t21 )
(1 − t1 )(1 + t1 )((1 + 3t1 ) ln 1+t1 +ǫ
1+t1
+ 1+t1 +ǫ
− 2(t1 − 1) − 4ǫ)
= lim
ǫ→0 −6ǫ2
1+3t1 (1+t1 )(3+t1 )
(1 − t1 )(1 + t1 )( 1+t1 +ǫ
+ (1+t1 +ǫ)2
− 4)
= lim
ǫ→0 −12ǫ
1+3t1 2(1+t1 )(3+t1 )
(1 − t1 )(1 + t1 )(− (1+t1 +ǫ)
2 − (1+t1 +ǫ)3
)
= lim
ǫ→0 −12
(1 − t1 )(5t1 + 7)
=
12(1 + t1 )

where the third equality, the fourth equality and the fifth equality hold by the L’Hôpital’s
Rule.

52
 ∗
Claim 9. Fix any t1 ∈ [0, 1], H1II (t1 , t2 ) is strictly decreasing w.r.t. t2 for t2 ∈ (0, 1).
∗
Proof of Claim 9. Taking first order derivative w.r.t. t2 to H1II when t1 6= t2 , with some
algebra, we obtain that
∗
∂H1II (t1 , t2 ) (1 + t1 )(1 − t1 )2 2(1 + t2 ) 1 + t2
= 2
[(1 + ) ln + 2]
∂t2 2(t1 − t2 ) t1 − t2 1 + t1

Then it suffices to show that for any t1 ∈ [0, 1] and t2 6= t1 ,

2(1 + t2 ) 1 + t2
(1 + ) ln +2<0 (135)
t1 − t2 1 + t1

Plugging t2 = z3 (1 + t1 ) − 1 into (135), it suffices to show that for z3 ∈ [ 12 , 1) ∪ (1, 2],

2z3
(1 + ) ln z3 + 2 < 0 (136)
1 − z3
2(1−z3 )
To show (136), let l(z3 ) := ln z3 + 1+z3
. Taking first order derivative, with some algebra,
we obtain that
1 4
l′ (z3 ) = + >0 (137)
z3 (1 + z3 )2
Also note l(1) = 0. Then l(z3 ) > 0 for z3 > 1 and l(z3 ) < 0 for z3 ∈ [ 21 , 1). Therefore (136)
holds.
∗
∂H1II (t1 ,t2 ) 2
(1−t1 )
Claim 10. ∂t2
→ − 12(1+t 1)
as t2 → t1 .

Proof of Claim 10.

∗ ∗
∂H1II (t1 , t2 ) ∂H1II (t1 , t2 )
lim = lim
t2 →t1 ∂t2 ǫ:=t2 −t1 →0 ∂t2
1+t +ǫ
(1 + t1 )(1 − t1 )2 (2(1 + t1 ) + ǫ) ln 1+t1 1 − 2ǫ
= lim
ǫ:=t2 −t1 →0 2 −ǫ3
2(1+t )+ǫ
(1 + t1 )(1 − t1 )2 ( 1+t11+ǫ + ln 1+t 1 +ǫ
1+t1
− 2)
= lim
ǫ→0 −6ǫ2
2 1+t1 1
(1 + t1 )(1 − t1 ) (− (1+t 1 +ǫ)
2 + 1+t +ǫ )
1
= lim
ǫ→0 −12ǫ
2 2(1+t1 )
(1 + t1 )(1 − t1 ) ( (1+t1 +ǫ)3 − (1+t11+ǫ)2 )
= lim
ǫ→0 −12
(1 − t1 )2
=−
12(1 + t1 )

53
where the third equality, the fourth equality and the fifth equality hold by the L’Hôpital’s
Rule.

Now we are ready to prove Lemma 3. Fix any m1 ∈ ( 43 , 1). Let t∗2 (m1 ) ∈ (0, 1)
−t2 +2t +3
denote the solution to 2 4 2 = m1 . Let t∗1 (m1 ) ∈ (0, 1) denote the solution to
2
(1+t1 )(1−t1 ) 1+t 2
1
2t21
ln 1+t1
+ 2t11 = m1 . Then by Claim 6, Claim 7 and Claim 9, there exists a strictly
∗
increasing function F II such that t1 = F II (t2 ) ≥ t2 is the solution to H1II (t1 , t2 ) = m1 for
any t2 ∈ [0, t∗2 (m1 )]. In addition, F II (t2 ) ∈ [t∗1 (m1 ), t∗2 (m1 )]. By Claim 7, Claim 8, Claim
∗ ∗
∂H1II (t1 ,t2 ) ∂H1II (t1 ,t2 )
9 and Claim 10, the continuous function17 ∂t1
(and ∂t2
) is strictly positive
(and strictly negative) and bounded on the compact set [t1 (m1 ), t2 (m1 )] × [0, t∗2 (m1 )]. Then
∗ ∗

by the (Global) Implicit Function Theorem, F II (t2 ) is continuous on [0, t∗2 (m1 )]. Plugging
∗ ∗
t1 = F II (t2 ) to H2II (t1 , t2 ), we obtain GII (t2 ) := H2II (F II (t2 ), t2 ). Given the continuity of
∗
H2II and F II , we see that GII is also continuous at any t2 ∈ [0, t∗2 (m1 )]. Note that when
t2 = t∗2 (m1 ), F II (t2 ) = t2 and therefore GII (t2 ) = m1 ; when s2 = 0, GII (t2 ) = BII (m1 ). Then
by the Intermediate Value Theorem, there exists t2 ∈ [0, t∗2 (m1 )]] such that G(s2 ) = m2
for any m2 ∈ [BII (m1 ), m1 ). Finally, when m1 = 1, then t1 = 1 and (18) becomes
2
(1 + t2 ) ln 1+t2
+ t2 = m2 . Note when t2 = 0, then L.H.S.= ln 2; when t2 = 1, then L.H.S.
= 1. Therefore by the Intermediate Value Theorem, there exists t2 ∈ [0, 1) that solves (18)
for any m2 ∈ [BII (1), 1).

10.8 Proof of Theorem 4

(i): Asymmetric Maxmin Public Good Mechanism (II) is a best response to
Asymmetric Worst-Case Joint Distribution (II).The proof is similar to the proof
of (i) of Theorem 1.
(ii): Asymmetric Worst-Case Joint Distribution (II) is a best response to
Asymmetric Maxmin Public Good Mechanism (II): we use the duality theory to
show (ii). First note that by construction, all the constraints in (P) holds. By the
weighted virtual value representation, the value of (P) given Asymmetric Worst-Case
Joint Distribution (II) and Asymmetric Maxmin Public Good Mechanism (II) is simply
P r(1, 1) × (1 + 1) = (1+t1 )(1+t
2
2)
. Second, the constraints in (D) hold for all value profiles. To
see this, note for any value profile v = (v1 , v2 ) outside the support of Asymmetric Worst-Case
Joint Distribution (II), since λ1 > 0 and λ2 > 0, we have

λ1 v1 + λ2 v2 + µ < λ1 t1 + λ2 · 1 + µ = 0
∗ ∗
17 ∂H1II (t1 ,t2 ) (1−t1 )(5t1 +7) ∂H1II (t1 ,t2 ) 2
(1−t1 )
When t1 = t2 , let ∂t1 = 12(1+t1 ) and ∂t2 = − 12(1+t 1)
, the by Claim 8 and Claim
∗ ∗
∂H1II (t1 ,t2 ) ∂H1II (t1 ,t2 )
10, ∂t1 and ∂t2 are continuous.

54
For any value profile v = (v1 , v2 ) inside the support of Asymmetric Worst-Case Joint
Distribution (II), the constraints (the complementary slackness) hold given (19). In addition,
the value of (D) given the constructed λ1 , λ2 , µ is λ1 m1 + λ2 m2 + µ, which, by some algebra,
is equal to (1+t1 )(1+t
2
2)
. Finally, by Lemma 3, the solution to (17) and (18) exists. By the
linear programming duality theory, (ii) holds and the revenue guarantee is (1+t1 )(1+t
2
2)
.

10.9 Proof of Lemma 4

We start from establishing the following claims regarding some properties of the function
H2III (u1 , u2 ), which will play a crucial role in establishing Lemma 4.

Claim 11. Fix any u1 ∈ (0, 1], H2III (u1 , u2) is strictly decreasing w.r.t. u2 for u1 ∈ (0, 1).

Proof of Claim 11. Taking first order derivative w.r.t. u2 to H2III , with some algebra, we
obtain that

∂H2III (u1, u2 ) u1 1 + u2 + u1 1 + u2
= 2
[− ln + 2]
∂u2 (1 + u1 )(u2 − u1 + 1) 1 + u2 − u1 u1

Then it suffices to show that for any u2 ∈ (0, 1),

1 + u2 + u1 1 + u2
− ln +2<0 (138)
1 + u2 − u1 u1

Let z4 := 1+uu1
2
∈ (1, ∞). Plugging u2 = z4 u1 − 1 into (138), it suffices to show that for
z4 ∈ (1, ∞),
z4 + 1
− ln z4 + 2 < 0 (139)
z4 − 1
To show (139), let n(z4 ) := − ln z4 + 2(zz44+1
−1)
. Taking first order derivative, with some algebra,
we obtain that
(z4 − 1)2
n′ (z4 ) = − (140)
z4 (z4 + 1)2
Observe that implies that n(z4 ) is strictly decreasing for z4 ≥ 1. Also note n(1) = 0. Then
n(z3 ) < 0 for z4 > 1. Therefore (139) holds.

∂H2III (1,u2 ) 1
Claim 12. ∂u1
→ − 12 as u2 → 0.

55
Proof of Claim 12.

∂H2III (1, u2) −(2 + u2 ) ln (1 + u2) + 2u2

lim = lim
u2 →0 ∂u2 u2 →0 2u32
− 1 − ln (1 + u2 ) + 1
= lim 1+u2
u2 →0 6u22
1 1
(1+u2 )2
− 1+u 2
= lim
u2 →0 12u2
− (1+u2 2 )3 + (1+u1 2 )2
= lim
u2 →0 12
1
=−
12

where the second equality, the third equality and the fourth equality hold by the L’Hôpital’s
Rule.

Claim 13. Fix any u2 ∈ [0, 1], H2III (u1 , u2) is strictly increasing w.r.t. u1 for u1 ∈ (0, 1).

Proof of Claim 13. Taking first order derivative w.r.t. u1 to H2III , with some algebra, we
obtain that

∂H2III (u1 , u2) 1 2u1 (1 + u1 ) 1 + u2

= [(u 2 + 1)(1 + ) ln
∂u1 (1 + u1 )2 (1 + u2 − u1 )2 u2 − u1 + 1 u1
+(1 + u2 − u1 )2 − (1 + u2 − u1 ) − (1 + u1 )(u2 + 1 + u1 )]

Then it suffices to show that for any u1 ∈ (0, 1),

2u1 (1 + u1 ) 1 + u2
(u2 +1)(1+ ) ln +(1+u2 −u1 )2 −(1+u2 −u1 )−(1+u1 )(u2 +1+u1 ) > 0 (141)
u2 − u1 + 1 u1

Plugging u2 = z4 u1 − 1 into (141), with some algebra, it suffices to show that for z4 ∈ (1, ∞),

2z4 ln z4 2z4
u21 ( + (z4 − 1)2 + z4 + 1) + u1 [(z4 + ) ln z4 + 2] > 0 (142)
z4 − 1 z4 − 1

Then it suffices to show that for z4 ∈ (1, ∞),

2z4 ln z4
+ (z4 − 1)2 + z4 + 1 > 0 (143)
z4 − 1

2z4
(z4 + ) ln z4 + 2 > 0 (144)
z4 − 1
Note both (143) and (144) hold trivially when z4 > 1.

56
 ∂H2III (1,u2 ) 5
Claim 14. ∂u2
→ 24
as u2 → 0.

Proof of Claim 14.

∂H2III (1, u2 ) (u2 + 1)(u2 + 4) ln (1 + u2 ) + u2 (u22 − 3u2 − 4)

lim = lim
u2 →0 ∂u1 u2 →0 4u32
(2u2 + 5) ln (1 + u2 ) + 3u22 − 5u2
= lim
u2 →0 12u22
3
1+u2
+ 2 ln (1 + u2 ) + 6u2 − 3
= lim
u2 →0 24u2
3 2
− (1+u2 )3 + 1+u 2
+6
= lim
u2 →0 24
5
=
24

where the second equality, the third equality and the fourth equality hold by the L’Hôpital’s
Rule.

Now we are ready to prove Lemma 4. To facilitate the analysis, we rewrite Area(III)
as Area(III) = {(m1 , m2 )|m1 ≥ BI−1 (m2 )), m1 < BII
−1 −1
(m2 ), m1 < BIII (m2 ), 0 < m2 < 43 }.
This can be done since BI , BII and BIII are all strictly monotone functions, and therefore
the inverse functions exist. Next, fix any m2 ∈ (0, ln 2]. Let u∗1 (m2 ) ∈ (0, 1] denote the
solution to u1 ln u1u+1
1
= m2 . Let u∗∗ u1 1 u1
1 (m2 ) denote the solution to 1+u1 (− (1−u1 )2 ln u1 − 1−u1 ) =
m2 . Then by Claim 11 and Claim 13, there exists a strictly increasing function F1III
such that u2 = F1III (u1 ) ≤ u1 is the unique solution to H2III (u1 , u2 ) = m2 for any
u1 ∈ [u∗∗ ∗
1 (m2 ), u1 (m2 )]. In addition, F1
III
∈ [0, u∗1(m2 )]. Note the continuous functions
III
∂H2 (u1 ,u2 ) ∂H III (u ,u )
∂u1
(and 2 ∂u21 2 ) is strictly negative (and strictly positive) and bounded on the
compact set [u∗∗ ∗ ∗
1 (m2 ), u1 (m2 )]×[0, u1 (m2 )]. Then by the (Global) Implicit Function Theorem,
F1III (u1 ) is continuous on [u∗∗ ∗ III III
1 (m2 ), u1 (m2 )]. Plugging u2 = F1 (u1 ) to H1 (u1 , u2 ), we
obtain GIII III III
1 (u1 ) := H1 (u1 , F1 (u1 )). Given the continuity of H1
III
and F1III , we see
that GIII
1 is also continuous at any u1 ∈ [u∗∗ ∗ ∗
1 (m2 ), u1 (m2 )]. Note that when u1 = u1 (m2 ),
−1
F1III (u1 ) = u1 and therefore GIII (u1 ) = BIII (m2 ); when u1 = u∗∗ III
1 (m2 ), F1 (u1 ) = 0 and
−1
therefore GIII 1 (u1 ) = BI (m2 ). Then by the Intermediate Value Theorem, there exists
−1 −1
u1 ∈ [u∗∗ ∗ III
1 (m2 ), u1 (m2 )) such that G1 (u1 ) = m1 for any m1 ∈ [BI (m2 ), BIII (m2 )). Then
fix any m2 ∈ (ln 2, 43 ). Let u∗2 (m2 ) ∈ (0, 1) denote the solution to 1+u
2
2 ln 1+u2 2 −1
( u2 + u2u(1+u 2)
).
2
Then by Claim 11 and Claim 13, there exists a strictly increasing function F2III such that
u2 = F2III (u1 ) ≤ u1 is the unique solution to H2III (u1 , u2) = m2 for any u1 ∈ [u∗∗
1 (m2 ), 1].
III ∗
In addition, F2 ∈ [0, u2(m2 )]. By Claim 11, Claim 12, Claim 13 and Claim 14, continuous

57
 ∂H III (u ,u ) ∂H III (u ,u )
function18 2 ∂u21 2 (and 2 ∂u11 2 ) is strictly negative (and strictly positive) and bounded
on the compact set [u∗∗ ∗
1 (m2 ), 1] × [0, u2 (m2 )]. Then by the (Global) Implicit Function
Theorem, F1III (u1 ) is continuous on [u∗∗ III III
1 (m2 ), 1]. Plugging u2 = F2 (u1 ) to H1 (u1 , u2 ), we
obtain GIII III III
2 (u1 ) := H1 (u1 , F2 (u1 )). Given the continuity of H1
III
and F2III , we see that
∗∗ −1
GIII
2 is also continuous at any u1 ∈ [u1 (m2 ), 1]. Note that when u1 = 1, G
III
(u1 ) = BII (m2 );
∗∗ III III −1
when u1 = u1 (m2 ), F1 (u1 ) = 0 and therefore G1 (u1 ) = BI (m2 ). Then by the
Intermediate Value Theorem, there exists u1 ∈ [u∗∗ III
1 (m2 ), 1) such that G2 (u1 ) = m1 for
any m1 ∈ [BI−1 (m2 ), BII
−1
(m2 )).

10.10 Proof of Theorem 5

(i): Asymmetric Maxmin Public Good Mechanism (III) is a best response to
Asymmetric Worst-Case Joint Distribution (III). The proof is similar to the proof of
(i) of Theorem 1.
(ii): Asymmetric Worst-Case Joint Distribution (III) is a best response to
Asymmetric Maxmin Public Good Mechanism (III): we use the duality theory
to show (ii). First note that by construction, all the constraints in (P) holds. By
the weighted virtual value representation, the value of (P) given Asymmetric Worst-Case
Joint Distribution (III) and Asymmetric Maxmin Public Good Mechanism (III) is simply
P r(1, 1) × (1 + 1) = u1u(1+u
1 +1
2)
. Second, the constraints in (D) hold for all value profiles. To see
this, note for any value profile v = (v1 , v2 ) outside the support of Asymmetric Worst-Case
Joint Distribution (III), since λ1 > 0 and λ2 > 0, we have

λ1 v1 + λ2 v2 + µ < λ1 u1 + λ2 · 0 + µ = 0

For any value profile v = (v1 , v2 ) inside the support of Asymmetric Worst-Case Joint
Distribution (III), the constraints (the complementary slackness) hold given (26). In
addition, the value of (D) given the constructed λ1 , λ2 , µ is λ1 m1 + λ2 m2 + µ, which, by
some algebra, is equal to u1u(1+u
1 +1
2)
. Finally, by Lemma 4, the solution to (23) and (24) exists.
u1 (1+u2 )
By the linear programming duality theory, (ii) holds and the revenue guarantee is u1 +1
.

10.11 Proof of Lemma 5

Fix any m1 ∈ [0, 1]. Let w1∗ (m1 ) ∈ [0, 1] denote the solution to (30). Note that H IV (w1 , w2 )
is continuous and strict increasing w.r.t. w2 . Also note that H IV (w1∗ (m1 ), 0) = 0 and
18 ∂H2III (u1 ,u2 ) 1 ∂H2III (u1 ,u2 ) 5
When (u1 , u2 ) = (1, 0), let ∂u2 = − 12 and ∂u1 = 24 , then by Claim 12 and Claim 14,
∂H2III (u1 ,u2 ) ∂H2III (u1 ,u2 )
∂u2 and ∂u1 are continuous.

58
H IV (w1∗ (m1 ), 1) = BIII (m1 ). Then by the Intermediate Value Theorem, there exists (unique)
w2 ∈ [0, 1] such that H IV (w1∗ (m1 ), w2 ) = m2 for any m2 ∈ [0, BIII (m1 )].

10.12 Proof of Theorem 6

(i): Asymmetric Maxmin Public Good Mechanism (IV) is a best response to
Asymmetric Worst-Case Joint Distribution (IV). The proof is similar to the proof of
(i) of Theorem 1.
(ii): Asymmetric Worst-Case Joint Distribution (IV) is a best response to
Asymmetric Maxmin Public Good Mechanism (IV): we use the duality theory
to show (ii). First note that by construction, all the constraints in (P) holds. By
the weighted virtual value representation, the value of (P) given Asymmetric Worst-Case
Joint Distribution (IV) and Asymmetric Maxmin Public Good Mechanism (IV) is simply
P r(1, w2) × (1 + w2 ) = w1 . Second, the constraints in (D) hold for all value profiles. To
see this, note for any value profile v = (v1 , v2 ) in which v1 < w1 , since λ1 = − ln1w1 > 0 and
λ2 = 0, we have
λ1 v1 + λ2 v2 + µ < λ1 w1 + λ2 · 0 + µ = 0

For any value profile v = (v1 , v2 ) in which v1 < w1 , the constraints (the complementary
slackness) hold given (32). Finally, the value of (D) given the constructed λ1 , λ2 , µ is
λ1 m1 + λ2 m2 + µ, which, by some algebra, is equal to w1 . By the linear programming
duality theory, (ii) holds and the revenue guarantee is w1 .

11 Appendix C
11.1 Proof of Theorem 7
(i): N-agent Symmetric Maxmin Public Good Mechanism is a best response to
N-agent Symmetric Worst-Case Joint Distribution. First we verify that N-agent
Symmetric Worst-Case Joint Distribution is a legal joint distribution, i.e., its integral is 1
over [0, 1]N . Note it is symmetric, then it suffices to derive the marginal distribution for agent
−1
1 and show its integral is 1 over [0,1]. When v1 = 1, with some algebra, P r(v1 = 1) = r+NN
;
1
PN −2 N −2
j
when r ≤ v1 < 1, with some algebra, f (v1 ) = N N−1 j=0 j
(N − 1 − j)(r + N − 1) (v1 −

59
r)N −2−j . Therefore the integral is

Z 1  N −2 
1
N −2 X r+N −1
f (v1 )dv1 + P r(v1 = 1) = N −1 (r + N − 1)j (1 − r)N −1−j +
r N j=0
j N
N −2  
1−r X N −2 r+N −1
= N −1 (r + N − 1)j (1 − r)N −2−j +
N j=0
j N
1−r N −2 r+N −1
= (r + N − 1 + 1 − r) +
N N −1 N
=1

Next we show the weighted virtual value is 0 for any v ∈ SRN and v 6= (1, · · · , 1). We
| {z }
N
discuss two cases: a). |A(v)| = 1. Without loss, we can assume v1 6= 1 and vj = 1 for any
j 6= 1. Then
Z 1
∗
Φ(v1 , 1, · · · , 1) = (v1 + N − 1)π (v1 , 1, · · · , 1) − π ∗ (x, 1, · · · , 1)dx − P r ∗(1, · · · , 1)
| {z } | {z } v1
| {z } | {z }
N −1 N −1 N −1 N
N Z 1 N
(r + N − 1) (r + N − 1) (r + N − 1)N
= (v1 + N − 1) · − dx −
N −1 (v1 + N − 1)2
N
v1 N N −1 (x + N − 1)2 NN
=0

b). |A(v)| > 1.

N
X X Z 1 X
∗
Φ(v) = ( vi )π (v) − π ∗ (x, v−j )dx − π ∗ (1, v−j )
i=1 j∈A(v) vj j∈A(v)
X |A(v)|!(r + N − 1)N
=( vj + N − |A(v)|) · P
N N −1 ( j∈A(v) vj + N − |A(v)|)|A(v)|+1
j∈A(v)
X Z 1
|A(v)|!(r + N − 1)N
− P dx
vj N N −1 (x + i∈A(v),i6=j vi + N − |A(v)|)|A(v)|+1
j∈A(v)
X (|A(v)| − 1)!(r + N − 1)N
− P
N N −1 ( i∈A(v),i6=j vj + N + 1 − |A(v)|)|A(v)|
j∈A(v)

=0

Therefore, N-agent Symmetric Worst-Case Joint Distribution exhibits the property that the
weighted virtual value is positive only for the highest type (1, · · · , 1), zero for the other value
| {z }
N
profiles in the support and weakly negative for value profiles outside the support. Then any

60
feasible and monotone mechanism in which the public good is provided with some positive
P
probability if and only if N i=1 vi > r+N −1 and the public good is provided with probability
1 when v = (1, · · · , 1) is a best response for the principal. It is easy to see that N-agent
| {z }
N
Maxmin Public Good Mechanism is such a mechanism.
(ii): N-agent Symmetric Worst-Case Joint Distribution is a best response to N-agent
Symmetric Maxmin Public Good Mechanism. We use the duality theory to show (ii).
First we will show that all the constraints in (P) holds. Note that N-agent Symmetric
Worst-Case Joint Distribution is a legal joint distribution by the argument in (i). Also given
R1
the marginal distribution for agent 1, by some algebra, we have r v1 f (v1 )dv1 + P r(v1 =
N N−1
1) · 1 = (r+N −1)(N −(r+N −1)
(N −1)N N
)
. By the weighted virtual value representation, the value
of P given N-agent Symmetric Maxmin Public Good Mechanism and N-agent Symmetric
(r+N −1)N
Worst-Case Joint Distribution is simply P r ∗ (1, · · · , 1) × N = N N−1
. Second, we will
| {z }
N
show that all the constraints in (D) hold for all value profiles. To see this, note for any value
P PN R vi
profile v ∈ SRN , by some algebra, we have ( N i=1 vi )q(v) − P
i=1 r+N −1− j6=i vj q(s, v−i )ds =
(N −1)(r+N −1)N−1 PN
N N−1 −(r+N −1)N−1
( i=1 vi − (r2 + N − 1)). Consider the following dual variables: λi =
(N −1)(r+N −1)N−1 N
for any i and µ = − N (N
N N−1 −(r+N −1)N−1
−1)(r+N −1)
N−1 −(r+N −1)N−1 . Then the complementary slackness

holds by the above equation. Since λi > 0 for any i, we have

X
λi vi + µ < λi (r + N − 1) + µ = 0
i=1

for any value profile v ∈

/ SRN . Finally, the value of (D) given the constructed λi , µ is, by
PN −1)(r+N −1)N−1 −1)N
some algebra, i=1 λi m + µ = N(NN−1 −(r+N −1)N−1
(Nm − (r2 + N − 1)) = (r+N
N N−1
. By the
N
linear programming duality theory, (ii) holds and the revenue guarantee is (r+N −1)
N N−1
.
N
(r+N −1)(N −(r+N −1)N−1 ) N N−1 −(r+N −1)N−1
′
Finally, Let H(r) := (N −1)N N
. Note H (r) = (N −1)N N−1
≥ 0 for
(N −1)N−1
0 ≤ r ≤ 1, we have m = H(r) ≥ H(0) = 1 − NN
.

11.2 Proof of Theorem 8

To facilitate the analysis, we first consider a benchmark case in which there is only one agent
whose expectation is known to be m. Carrasco et al. (2018) has shown that the optimal
√
revenue guarantee RG(m) := maxτ ∈[0,1] τ · m−τ 1−τ
and the maximizer τ ∗
:= 1 − 1 − m. In
addition, RG(m) is strictly increasing in m.
Now we divide all deterministic, DSIC and EPIR public good mechanisms into the
following four classes:
Class 1 : the provision boundary touches on the value profiles (d1 , 0) and (0, d2) for some

61
0 ≤ d1 ≤ 1, 0 ≤ d2 ≤ 1.
Class 2 : the provision boundary touches on the value profiles (d1 , 0) and (d2 , 1) for some
0 ≤ d2 ≤ d1 ≤ 1.19
Class 3 : the provision boundary touches on the value profiles (0, d1 ) and (1, d2) for some
0 ≤ d2 ≤ d1 ≤ 1.
Class 4 : the provision boundary touches on the value profiles (d1 , 1) and (1, d2) for some
0 ≤ d1 ≤ 1, 0 ≤ d2 ≤ 1.
The following lemmas establish a upper bound of revenue guarantee for each class of
mechanisms respectively.

Lemma 6. RG(m1 ) is an upper bound of the revenue guarantee for any mechanism in Class
1.

Proof. We propose a relaxation of (D) by omitting many constraints. Specifically, the only
remaining constraints are for the four vertices (0,0), (1,0), (0,1) and (1,1) and the value
profiles (d1 , 0) and (0, d2 ). Formally, we have the following relaxed problem (D’):

max λ1 m1 + λ2 m2 + µ
λ1 ,λ2 ,µ∈R

s.t.
µ≤0 (145)

λ1 d 1 + µ ≤ 0 (146)

λ2 d 2 + µ ≤ 0 (147)

λ1 + µ ≤ d 1 (148)

λ2 + µ ≤ d 2 (149)

λ1 + λ2 + µ ≤ 0 (150)

Note the value of (D’) (denoted by val(D ′ )) is weakly greater than the value of (D). Now we
are trying to find a upper bound of the value of (D’) across 0 ≤ d1 , d2 ≤ 1. We discuss four
cases:
Case 1 : λ1 ≤ 0, λ2 ≤ 0. Note then by (145), val(D ′ ) ≤ 0 for any 0 ≤ d1 , d2 ≤ 1.
Case 2 : λ1 ≥ 0, λ2 ≥ 0. Note by (150), we have λ1 m1 + λ2 m2 + µ ≤ λ1 + λ2 + µ ≤ 0. Thus,
val(D ′ ) ≤ 0 for any d1 , d2.
Case 3 : λ1 ≥ 0, λ2 ≤ 0. Now we are left with (146), (148) and (150) as they imply the
other three constraints. We further ignore (150), which will make the value of (D’) (weakly)
19
d2 ≤ d1 is implied by the monotone property of the provision boundary (Observation 1).

62
greater. Note at least one of (146) and (148) is binding, otherwise we can increase the value
of (D’) by increasing λ1 by a small amount. We thus discuss two situations:
(a) : λ1 d1 + µ = 0.
d1
We plug µ = −λ1 d1 into (148), and we obtain λ1 ≤ 1−d 1
. Then we have λ1 m1 +λ2 m2 +µ ≤
d1 (m1 −d1 )
λ1 m1 + µ = λ1 (m1 − d1 ) ≤ max{0, 1−d1 } ≤ RG(m1 ). The first inequality is implied by
d1
λ2 ≤ 0 and the second inequality is implied by 0 ≤ λ1 ≤ 1−d 1
.
(b) : λ1 + µ = d1 .
d1
We plug µ = d1 −λ1 into (146), and we obtain λ1 ≥ 1−d 1
. Then we have λ1 m1 +λ2 m2 +µ ≤
λ1 m1 + µ = λ1 (m1 − 1) + d1 ≤ d1 (m 1 −d1 )
1−d1
≤ RG(m1 ). The first inequality is implied by λ2 ≤ 0
d1
and the second inequality is implied by λ1 ≥ 1−d 1
.
Case 4 : λ1 ≤ 0, λ2 ≥ 0. Similar to Case 3, we obtain λ1 m1 +λ2 m2 +µ ≤ RG(m2 ) ≤ RG(m1 )
where the second inequality is implied by the monotonicity of RG(·).

Lemma 7. RG(m1 ) is an upper bound of the revenue guarantee for any mechanism in Class
3.

Proof. We propose a relaxation of (D) by omitting many constraints. Specifically, the only
remaining constraints are for the four vertices (0,0), (1,0), (0,1) and (1,1) and the value
profiles (d1 , 0) and (d2 , 1). Formally, we have the following relaxed problem (D”):

max λ1 m1 + λ2 m2 + µ
λ1 ,λ2 ,µ∈R

s.t.
µ≤0 (151)

λ1 d 1 + µ ≤ 0 (152)

λ1 d 2 + λ2 + µ ≤ 0 (153)

λ1 + µ ≤ d 1 (154)

λ2 + µ ≤ 0 (155)

λ1 + λ2 + µ ≤ d 2 (156)

Note the value of (D”) (denoted by val(D ′′ )) is weakly greater than the value of (D). Now
we are trying to find a upper bound of the value of (D”) across 0 ≤ d1 , d2 ≤ 1. We discuss
four cases:
Case 1’ : λ1 ≤ 0, λ2 ≤ 0. Note then by (151), val(D ′′ ) ≤ 0 for any 0 ≤ d1 , d2 ≤ 1.
Case 2’ : λ1 ≥ 0, λ2 ≤ 0. We further ignore (151), (153), (155) and (156), which will make

63
the value of D” (weakly) greater. Then by similar argument with Case 3 in the proof of
Lemma 6, we obtain λ1 m1 + λ2 m2 + µ ≤ RG(m1 ).
Case 3’ : λ1 ≤ 0, λ2 ≥ 0. Then λ1 m1 + λ2 m2 + µ ≤ λ2 m2 + µ ≤ 0. The first inequality is
implied by λ1 ≤ 0 and the second inequality is implied by (149).
Case 4’ : λ1 ≥ 0, λ2 ≥ 0. Now we are left with (152), (153) and (156) as they imply the
other three constraints. Note at least one of (152), (153) and (156) is binding, otherwise we
can increase the value of (D”) by increasing λ1 by a small amount. We thus discuss three
situations:
(a′ ) : λ1 d1 + µ = 0.
We plug µ = −λ1 d1 into (153) and (156), and we obtain

λ2 ≤ λ1 (d1 − d2 ) (157)

λ2 ≤ d2 − λ1 (1 − d1 ) (158)
d2
Compare the RHS of (157) and (158). (i) When λ1 ≤ 1−d 2
, (157) is binding. Then
d2
λ1 m1 + λ2 m2 + µ = λ1 (m1 − d1 ) + λ2 m2 ≤ λ1 (m1 − d1 (1 − m2 ) − d2 m2 ) ≤ max{0, 1−d 2
(m1 −
d2
d1 (1 − m2 ) − d2 m2 )} ≤ max{0, 1−d2 (m1 − d2 )} ≤ RG(m1 ). The first inequality is implied by
d2
(157) and the third inequality is implied by d1 ≥ d2 . (ii) When λ1 ≥ 1−d 2
, (158) is binding.
d2
Also (158) and λ2 ≥ 0 imply that λ1 ≤ 1−d1 . Then λ1 m1 + λ2m2 + µ = λ1 (m1 − d1 ) + λ2m2 ≤
d2 d2
λ1 (m1 − d1 − (1 − d1 )m2 ) + d2 m2 ≤ max{ 1−d 1
(m1 − d1 − (1 − d1 )m2 ) + d2 m2 , 1−d 2
(m1 − d1 −
d1 d2
(1 − d1 )m2 ) + d2 m2 } ≤ max{ 1−d1 (m1 − d1 ), 1−d2 (m1 − d2 )} ≤ RG(m1 ). The first inequality
d2 d2
is implied by (158), the second inequality is implied by 1−d 2
≤ λ1 ≤ 1−d 1
, and the third
inequality is implied by d1 ≥ d2 .
(b′ ) : λ1 d2 + λ2 + µ = 0.
We plug µ = −λ1 d2 − λ2 into (152) and (156), and we obtain

λ2 ≥ λ1 (d1 − d2 ) (159)

d2
λ1 ≤ (160)
1 − d2
Then we have λ1 m1 +λ2 m2 +µ = λ1 m1 +λ2 m2 −λ1 d2 −λ2 ≤ λ1 (m1 −d2 −(d1 −d2 )(1−m2 )) ≤
RG(m1 ). The first inequality is implied by (159) and the second inequality holds by (160)
and the same argument as in (i) of (a′ ).
(c′ ) : λ1 + λ2 + µ = d2 .
We plug µ = d2 − λ1 − λ2 into (152) and (153), and we obtain

λ2 ≥ λ1 (d1 − 1) + d2 (161)

64
 d2
λ1 ≥ (162)
1 − d2
d2
(i’) When λ1 > 1−d1
, (161) is not binding. Then we have λ1 m1 + λ2 m2 + µ = λ1 m1 + λ2 m2 +
d2 d1
d2 − λ1 − λ2 ≤ λ1 m1 − λ1 + d2 ≤ max{0, 1−d 1
(m1 − d1 )} ≤ max{0, 1−d 1
(m1 − d1 )} ≤ RG(m1 ).
The first inequality is implied by λ2 ≥ 0 and the second inequality is implied by (162) and
d2
the third inequality is implied by d1 ≥ d2 . (ii’) When λ1 ≤ 1−d 1
, (161) is binding. Then we
have λ1 m1 + λ2 m2 + µ = λ1 m1 + λ2 m2 + d2 − λ1 − λ2 ≤ λ1 (m1 − d1 − (1 − d1 )m2 ) + d2 m2 ≤
RG(m1 ). The first inequality is implied by (161) and the second inequality is implied by
d2 d2
1−d2
≤ λ1 ≤ 1−d1
and the same argument as in (ii) of (a′ ).

Lemma 8. RG(m1 ) is an upper bound of the revenue guarantee for any mechanism in Class
3.

Proof. By similar argument with the proof of Lemma 7, RG(m2 ) is an upper bound of the
revenue guarantee for any mechanism in Class 3. Then Lemma 8 holds by m1 ≥ m2 and the
monotonicity of RG(·).
√ q q
Lemma 9. When m2 ≥ 2( 2−1), 2(1− 1−m
2
1
− 1−m2 2
2
) is an upper bound of the revenue
guarantee of any mechanism in Class 4; otherwise RG(m1 ) is an upper bound of the revenue
guarantee of any mechanism in Class 4.

Proof. We propose a relaxation of (D) by omitting many constraints. Specifically, the only
remaining constraints are for the four vertices (0,0), (1,0), (0,1) and (1,1) and the value
profiles (d1 , 1) and (1, d2 ). Formally, we have the following relaxed problem (D3):

max λ1 m1 + λ2 m2 + µ
λ1 ,λ2 ,µ∈R

s.t.
µ≤0 (163)

λ1 d 1 + λ2 + µ ≤ 0 (164)

λ1 + λ2 d 2 + µ ≤ 0 (165)

λ1 + µ ≤ 0 (166)

λ2 + µ ≤ 0 (167)

λ1 + λ2 + µ ≤ d 1 + d 2 (168)

Note the value of (D3) (denoted by val(D3)) is weakly greater than the value of (D). Now
we are trying to find a upper bound of the value of (D3) across 0 ≤ d1 , d2 ≤ 1. We discuss

65
four cases:
Case 1”: λ1 ≤ 0, λ2 ≤ 0. Note then by (163), val(D3) ≤ 0 for any 0 ≤ d1 , d2 ≤ 1.
Case 2”: λ1 ≤ 0, λ2 ≥ 0. Then λ1 m1 + λ2m2 + µ ≤ λ2 m2 + µ ≤ 0 where the second inequality
is implied by (167).
Case 3”: λ1 ≥ 0, λ2 ≤ 0. Then λ1 m1 + λ2m2 + µ ≤ λ1 m1 + µ ≤ 0 where the second inequality
is implied by (166).
Case 4”: λ1 ≥ 0, λ2 ≥ 0. Now we are left with (164), (165) and (168) as they imply the
other three constraints. Note at least one of (164), (165) and (168) is binding, otherwise
we can increase the value of (D3) by increasing λ1 by a small amount. Also note that it is
without loss to restrict attention to d1 6= 1 and d2 6= 1, because (164) or (165) would imply
λ1 m1 + λ2 m2 + µ ≤ 0 otherwise. We thus discuss three situations:
(a′′ ) : λ1 + λ2 d2 + µ = 0.
We plug µ = −λ1 − λ2 d2 into (164) and (168), and we obtain

d1 + d2
λ2 ≤ (169)
1 − d2

1 − d2
λ1 ≥ λ2 (170)
1 − d1
1−d2
Then λ1 m1 + λ2 m2 + µ = λ1 (m1 − 1) + λ2 (m2 − d2 ) ≤ λ2 ( 1−d1
(m1 − 1) + m2 − d2 ) ≤
max{0, (1 − 1−m 1
1−d1
− 1−m2
1−d2
)(d1 + d2 )}. The first inequality is implied by (170) and the second
inequality is implied by (169).
(b′′ ) : λ1 d1 + λ2 + µ = 0.
1−m1
By similar argument with (a′′ ), we can show λ1 m1 + λ2 m2 + µ ≤ max{0, (1 − 1−d1
−
1−m2
1−d2
)(d1 + d2 )}.
(c′′ ) : λ1 + λ2 + µ = d1 + d2 .
We plug µ = d1 + d2 − λ1 − λ2 into (164) and (165), and we obtain

d1 + d2
λ1 ≥ (171)
1 − d1

d1 + d2
λ2 ≥ (172)
1 − d2
1−m1 1−m2
Then λ1 m1 + λ2 m2 + µ = λ1 (m1 − 1) + λ2 (m2 − 1) + d1 + d2 ≤ (1 − 1−d1
− 1−d2
)(d1 + d2 ).
The inequality is implied by (171) and (172).
Let K(d1 , d2 ) := (1 − 1−m 1−d1
1
− 1−m 2
1−d2
)(d1 + d2 ). We are now solving for
max0≤d1 <1,0≤d2 <1 K(d1 , d2). First it is without loss to assume m1 ≥ d1 , because otherwise
1 − 1−m1
1−d1
− 1−m
1−d2
2
≤ 0. Now fix any 0 ≤ d1 ≤ m1 . Taking first order derivative with respect

66
to d2 , we obtain that

∂K(d1 , d2 ) m1 − d1 (1 − m2 )(1 + d1 )(1 − d1 )

= 3
[(1 − d2 )2 − ] (173)
∂d2 (1 − d1 ) m1 − d1

(1−m2 )(1+d1 )(1−d1 ) (d1 −m1 )2 +1−m21

Let G(d1 ) := m1 −d1
. Note G′ (d1 ) = (m1 −d1 )2
≥ 0. (i) If G(d1 ) ≥ 1, then
∂K(d1 ,d2 )
∂d2
≤ 0 for any d2 . Then K(d1 , d2 ) ≤ K(d1 , 0) = d1 (m2 − 1−m 1
1−d1
) ≤ d1 (1 − 1−m 1
1−d1
) ≤
q
RG(m1 ). (ii) If G(d1 ) ≤ 1, let d∗2 (d1 ) := 1 − (1−m2 )(1+d1 )(1−d1 )
m1 −d1
. Note ∂K(d 1 ,d2 )
∂d2
≤ 0 when
∂K(d1 ,d2 )
d2 ≥ d∗2 (d1 ) and ∂d2
≥ 0 when d2 ≤ d∗2 (d1 ). Therefore d∗2 (d1 ) is the maximizer. With
some algebra, we have
s
(m1 − d1 )(1 + d1 ) √
K(d1 , d∗2 ) = ( − 1 − m2 )2 (174)
1 − d1

(m1 −d1 )(1+d1 ) 1+d1

√ √
Let L(d1 ) := 1−d1
. First note L(d1 ) = G(d1 )
1 − m2 > 1 − m2 . Therefore
d2 −2d1 +2m1 −1
it suffices to maximize L(d1 ) subject to G(d1 ) ≤ 1. Note L′ (d1 ) Let = 1 (1−d 1)
2 .
∗
p ′ ∗ ′ ∗
d1 := 1 − 2(1 − m1 ). Then L (d1 ) ≥ 0 when d1 ≤ d1 and L (d1 ) ≤ m1 . 0 when d1 ≤ d1 ≤
p
Note G(d∗1 ) = 2(1 − m2 ). Then if m2 ≤ 12 , then by the monotonicty of G(·) and L(·) (when
d1 ≤ d∗1 ), d1 such that G(d1 ) = 1 is the maximizer. Then by (i), K(d1 , d2 ) ≤ RG(m1 ). If
p
m2 > 12 , then d∗1 is the maximizer, and d∗2 (d∗1 ) = 1 − 2(1 − m2 ), then, with some algebra,
q q q q
1−m1 1−m2 2 1−m1
K(d1 , d2 ) ≤ 2(1 − 2
− 2
) . Finally, compare 2(1 − 2
− 1−m 2
2 2
) with
√ q q
RG(m1 ) when m2 > 21 . When m2 ≥ 2( 2 − 1), 2(1 − 1−m 2
1
− 1−m 2
2 2
) ≥ RG(m1 );
q q
otherwise 2(1 − 1−m 2
1
− 1−m2
2 2
) < RG(m1 ).

To prove Theorem 8, it suffices to show that the upper bounds identified in Lemma 6,
√
Lemma 7 and Lemma 8 are attainable. Note this is obvious when m2 ≤ 2( 2 − 1), as
√
we can just ignore agent 2. When m2 ≥ 2( 2 − 1), by the proof of Lemma 8, consider
d∗1 +d∗2 (d∗1 ) d∗1 +d∗2 (d∗1 ) (d∗1 +d∗2 (d∗1 ))(1−d∗1 d∗2 (d∗1 ))
the dual variables λ1 = 1−d∗1
, λ2 = 1−d∗2 (d∗1 )
and µ = − (1−d∗1 )(1−d∗2 (d∗1 ))
. Note
q q
λ1 m1 + λ2 m2 + µ = 2(1 − 1−m 2
1
− 1−m 2
2 2
) . Then it suffices to show that the constructed
dual variables satisfy the constraints of (D) for any mechanism in the Theorem 8. Note by
the above argument, λ1 v1 + λ2 v2 + µ = 0 for the value profiles (d∗1 , 1) and (1, d∗2 (d∗1 )). Then
by linearity, any value profile in the line boundary satisfies λ1 v1 + λ2 v2 + µ = 0. Because
λ1 > 0 and λ2 > 0, we have λ1 v1 + λ2 v2 + µ < 0 for any value profile below the provision
boundary B. Therefore the the constraints of (D) hold for any value profile below the
provision boundary B. Now consider any value profile (v1 , v2 ) above the provision boundary
B. Then λ1 v1 +λ2 v2 +µ−t(v) = λ1 v1 +λ2 v2 +µ−b1 (v1 )−b2 (v2 ) ≤ λ1 +λ2 +µ−d∗1 −d∗2 (d∗1 ) = 0
where (v1 , b2 (v1 )) and (b1 (v2 ), v2 ) lie in the provision boundary B. The first equality holds

67
by t(v) = b2 (v1 ) + b1 (v2 ), the inequality holds because λ1 > 0, λ2 > 0 and b1 , b2 are non-
increasing, and the last equality holds by our construction.

11.3 Proof of Theorem 9

(i): N-agent Maxmin Excludable Public Good Mechanism is a best response to N-
agent Independent Equal Revenue Distribution. Note under N-agent Independent
Equal Revenue Distribution, ΦE E
i (v) = 0 if γi ≤ vi < 1 for any i and Φi (v) > 0 if vi = 1
and v is in the support for any i. Then any feasible and monotone mechanism in which the
public good is provided to agent i with some positive probability if and only if vi > γi and
the public good is provided with probability 1 to agent i when vi = 1 is a best response for
the principal. It is easy to see that N-agent Maxmin Excludable Public Good Mechanism is
such a mechanism.
(ii): N-agent Independent Equal Revenue Distribution is a best response to N-agent
Maxmin Excludable Public Good Mechanism. We use the duality theory to show (ii).
The primal and the dual are simple adaptions of those in the proof of Lemma 1. First
note that N-agent Independent Equal Revenue Distribution is a legal joint distribution.
And given the definition of γi , it satisfies all of the mean constraints. By the weighted
virtual value representation, the value of the primal given N-agent Independent Equal
Revenue Distribution and N-agent Maxmin Excludable Public Good Mechanism is simply
PN
i=1 γi . Second, the constraints in the dual hold for all value profiles. To see this, we
P
first construct the dual variables as follows: λi = − ln1γi for any i and µ = N γi
i=1 ln γi . Note
vi −γi
that tE∗ E∗
i (v) = − ln γi if vi ≥ γi and ti (v) = 0 if vi < γi by Proposition 1’. Then for any
value profile inside the support of N-agent Independent Equal Revenue Distribution, the
constraints of the dual hold with equality (complementary slackness). For any value profile
outside the support of N-agent Independent Equal Revenue Distribution, the constraints also
hold because λi vi + lnγiγi < 0 if vi < γi . Finally, the value of the dual given the constructed
P PN
dual variables is N i=1 λ i mi + µ, which, by some algebra, is equal to γi . By the linear
PNi=1
programming duality theory, (ii) holds and the revenue guarantee is i=1 γi .

68
References
Anderson, E. J. and Nash, P. (1987). Linear programming in infinite-dimensional spaces:
theory and applications. John Wiley & Sons.

Bergemann, D., Brooks, B., and Morris, S. (2017). First-price auctions with general
information structures: Implications for bidding and revenue. Econometrica, 85(1):107–
143.

Bergemann, D., Brooks, B., and Morris, S. (2019). Revenue guarantee equivalence. American
Economic Review, 109(5):1911–29.

Bergemann, D., Brooks, B. A., and Morris, S. (2016). Informationally robust optimal auction
design.

Bergemann, D. and Morris, S. (2005). Robust mechanism design. Econometrica, 73(6):1771–

1813.

Brooks, B. and Du, S. (2021). Optimal auction design with common values: An
informationally robust approach. Econometrica, 89(3):1313–1360.

Carrasco, V., Luz, V. F., Kos, N., Messner, M., Monteiro, P., and Moreira, H. (2018).
Optimal selling mechanisms under moment conditions. Journal of Economic Theory,
177:245–279.

Carroll, G. (2017). Robustness and separation in multidimensional screening. Econometrica,

85(2):453–488.

Che, E. (2020). Distributionally robust optimal auction design under mean constraints.

Chen, Y.-C. and Li, J. (2018). Revisiting the foundations of dominant-strategy mechanisms.
Journal of Economic Theory, 178:294–317.

Chung, K.-S. and Ely, J. C. (2007). Foundations of dominant-strategy mechanisms. The

Review of Economic Studies, 74(2):447–476.

Du, S. (2018). Robust mechanisms under common valuation. Econometrica, 86(5):1569–

1588.

Güth, W. and Hellwig, M. (1986). The private supply of a public good. Journal of Economics,
46(1):121–159.

He, W. and Li, J. (2020). Correlation-robust auction design.

69
Koçyiğit, Ç., Iyengar, G., Kuhn, D., and Wiesemann, W. (2020). Distributionally robust
mechanism design. Management Science, 66(1):159–189.

Libgober, J. and Mu, X. (2021). Informational robustness in intertemporal pricing. The

Review of Economic Studies, 88(3):1224–1252.

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

73.

Suzdaltsev, A. (2020). An optimal distributionally robust auction. arXiv preprint

arXiv:2006.05192.

Yamashita, T. and Zhu, S. (2018). On the foundations of ex post incentive compatible

mechanisms.

Zhang, W. (2021a). Correlation robustly optimal auctions. arXiv preprint arXiv:2105.04697.

Zhang, W. (2021b). Robust bilateral trade mechanisms with known expectations. arXiv
preprint arXiv:2105.05427.

70