# Information-Robust Optimal Auctions

Wanchang Zhang Department of Economics, University of California, San Diego.
Email<EMAIL_ADDRESS>I thank Songzi Du and Joel Sobel for helpful comments.

(Current Draft: May 8, 2022
First Draft: April 20, 2022)

###### Abstract

A single unit of a good is sold to one of two bidders. Each bidder has either
a high prior valuation or a low prior valuation for the good. Their prior
valuations are independently and identically distributed. Each bidder may
observe an independently and identically distributed signal about her prior
valuation. The seller knows the distribution of the prior valuation profile
and knows that signals are independently and identically distributed, but does
not know the signal distribution. In addition, the seller knows that bidders
play undominated strategies. I find that a second-price auction with a random
reserve maximizes the worst-case expected revenue over all possible signal
distributions and all equilibria in undominated strategies.
Keywords: Robust mechanism design, information design, independent private
value, second-price auctions, random reserves, undominated strategies.
JEL Codes: C72, D44, D82.

##  1 Introduction

The classic auction theory assumes that the seller knows bidders’ information
structure and derives optimal (revenue-maximizing) mechanisms (e.g., Myerson,
(1981)). However, optimal mechanisms vary with the model of bidders’
information structure and substantially less is known about how optimal
auctions would perform if the model were misspecified. More importantly, the
seller may not know bidders’ information structure in practice, and therefore
it is not clear how the seller should come up with a model of the information
structure.
To address these issues, I assume that the seller does not know every aspect
of bidders’ information structure and evaluates a mechanism using the worst-
case expected revenue over uncertainties about information structures.
More specifically, I consider a model in which two bidders are competing for a
single-unit good sold by a revenue-maximizing seller. Each bidder has two
possible prior valuations towards the good, either 1 or 0. Their prior
valuations are independently and identically distributed. The joint
distribution of their prior valuation profile is common knowledge among the
seller and the bidders. Each bidder may observe an independently and
identically distributed signal about her prior valuation. While the
information structure (that signals are independently and identically
distributed as well as the signal distribution) is common knowledge between
the bidders, the seller only knows that signals are independently and
identically distributed but does not know their distributions. A signal
distribution that is consistent with the the prior valuation distribution is
referred to as a possible signal distribution. The seller seeks a mechanism
from a vast class of mechanisms with the only requirement that the mechanism
“secures” bidders’ participation: there is a message for each payoff type of
each bidder that guarantees a non-negative payoff regardless of the other
bidder’ messages. In addition, the seller knows that bidders play undominated
strategies111The assumption that bidders play undominated strategies (or
“admissible strategies”) is often considered as a reasonable assumption for an
individual’s “rationality” in the literature on decision theory and game
theory. See, for example, Kohlberg and Mertens, (1986). In the literature on
implementation theory, Palfrey and Srivastava, (1991) use the concept of
undominated Nash equilibrium, which is the same refinement on the set of
equilibria considered in this paper. Yamashita, (2015) studies robust
mechanism design problems assuming that bidders play undominated strategies.
In contrast to my model, bidders may not play a Bayesian equilibrium in his
model.  in a mechanism. The seller believes that an adversarial Nature chooses
a possible signal distribution and an equilibrium in undominated strategies to
minimize the expected revenue.
The joint mechanism design and information design problem is not a standard
zero-sum game, as a given mechanism and a given information structure need not
have a unique equilibrium in undominated strategies. Moreover, an equilibrium
in undominated strategies may not exist at all. I address the issues of
equilibrium multiplicity and existence by using a new solution concept, with a
flavour similar to the one used in Brooks and Du, 2021b : a maxmin solution is
a triple of a mechanism, a possible signal distribution, and an equilibrium in
undominated strategies such that, i) fixing the mechanism, the possible signal
distribution and the equilibrium in undominated strategies minimize the
expected revenue, and ii) fixing the possible signal distribution, the
mechanism and the equilibrium in undominated strategies maximize the expected
revenue. Indeed, these statements remain true regardless of which equilibrium
in undominated strategies is played. The maxmin solution has an associated
revenue guarantee, which is the expected revenue in the constituent
equilibrium under the constituent signal distribution. The revenue guarantee
is both a tight lower bound on the expected revenue for the mechanism across
all possible signal distributions and all equilibria in undominated strategies
and a tight upper bound on the expected revenue for the signal distribution
across all mechanisms and all equilibria in undominated strategies.
The main result (Theorem 1) constructs a maxmin solution. First, the maxmin
mechanism is a second-price auction with a random reserve. The distribution of
the random reserve is atomless and admits a density function everywhere on
$[0,1]$. Remarkably, a simple dominant-strategy mechanism arises as a robustly
optimal mechanism across all participation-securing mechanisms, which include
all dominant-strategy mechanisms as well as nondominant-strategy mechanisms
used in practice, e.g., first-price auctions and all-pay auctions. Therefore,
even if nondominant-stategy mechanisms are allowed, the seller would use a
dominant-strategy mechanism to maximize the revenue guarantee in my setting,
which is a priori unanticipated. The result is consistent with the prevalence
of second-price auctions used in practice for selling a good. Indeed, the
result provides a rationale for using a second-price auction from the
perspective of robustness. Moreover, the rationale is strong, as it is
established across a vast class of mechanisms that incorporates arguably any
conceivable practical mechanisms. Second, the minmax signal distribution is an
equal-revenue distribution, defined by the property of a unit-elastic demand:
in the monopoly pricing problem, the monopoly’s revenue from charging any
price in the support of this distribution is the same. Equal-revenue
distributions are familiar in several literatures: they emerge endogenously in
many robust mechanism design environments and information design environment,
e.g., Bergemann and Schlag, (2008), Carrasco et al., (2018), Zhang, 2021a ,
Roesler and Szentes, (2017), Condorelli and Szentes, (2020), Chen and Yang,
(2020), etc. Finally, the constituent equilibrium is the truth-telling
equilibrium in which bidders always truthfully report their true signals.
Let me give a heuristic illustration of the result. I start with the minmax
signal distribution. This signal distribution has the property that each
bidder’s “virtual value” (this is the standard Myerson’s virtual value) is
zero except when the bidder observes the highest possible signal. Therefore,
the seller is indifferent between a wide range of mechanisms under this signal
distribution. Indeed, the seller is indifferent between all Bayesian incentive
compatible and Bayesian individually rational mechanisms in which 1) the
participation constraint is binding for a bidder with the lowest possible
signal, and 2) the good is fully allocated to the bidder(s) with the highest
possible signal(s), given that the truth-telling equilibrium is played. This
is because the seller is indifferent between allocating and not allocating the
good when both bidders’ virtual values are zeros.
Given that the adversarial Nature chooses the worst-case equilibrium in
undominated strategies, second-price auctions would be natural candidates for
a maxmin mechanism, as the truth-telling equilibrium is the unique equilibrium
in undominated strategies if the mechanism is a second-price auction (with or
without a reserve). In addition, given that the adversarial Nature chooses the
worst-case signal distribution, certain randomization device is expected to be
employed in a maxmin mechanism as it would hedge against uncertainties over
the signal distributions. Hence, I propose a second-price auction with a
random reserve as a candidate for a maxmin mechanism. The distribution of the
random reserve is then constructed so that the minmax signal distribution
minimizes the expected revenue in the truth-telling equilibrium across all
possible signal distributions. More elaborately, given a second-price auction
with a random reserve, the adversarial Nature solves an expected revenue
minimization problem subject to the constraint that the signal distribution is
possible. I construct a Lagrangian and use the first-order condition to derive
a differential equation that the distribution of the random reserve satisfies
so that the minmax signal distribution is a solution to the Nature’s
constrained minimization problem.
The remainder of the introduction discusses related work. Section 2 presents
the model. Section 3 characterizes the main result. Section 4 discusses and
extends the main result. Section 5 is a conclusion.

###  1.1 Related Work

This paper lies at the intersection of several different literatures. The
first literature is the classic auction design literature, initiated by the
seminal work of Myerson, (1981) who characterizes optimal auctions in the
independent private value environment. Crémer and McLean, (1988) characterize
optimal auctions in the private value environment for generic correlation
structures. Strikingly, the seller is able to extract the full surplus by
carefully design side bets.
While these results are of significant theoretical interest, they rely on the
common knowledge assumption. The “Wilson doctrine” (Wilson,, 1987) motivates
the robust mechanism design literature that searches for economic institutions
not sensitive to unrealistic assumptions about the information structure. This
paper contributes to the robust mechanism design literature. My model is
indeed equivalent to the private value model in which the seller knows that
bidders’ valuations are independently and identically distributed and knows
the mean of each bidder’s valuation. In this regard, the closest related work
is Suzdaltsev, (2020), who considers a model of auction design using exactly
the same framework, and characterizes the optimal deterministic reserve price
for a second-price auction. He shows that it is optimal to set the reserve
price to seller’s own valuation, which is zero in my setting. In contrast, I
do not place any restrictions on the mechanism except for a participation
security constraint, and characterize a maxmin mechanism for the two-bidder
case. Importantly, the revenue guarantee under my proposed mechanism is
strictly higher than that under his mechanism for the two-bidder case. In this
sense, this paper complements his work.
This paper is closely related to Che, (2019), Brooks and Du, 2021a , He and
Li, (2022) and Zhang, 2021a . Che, (2019) considers a model of auction design
in the private value environment and assumes that the seller only knows the
mean of bidders’ valuation distribution. He characterizes a second-price
auction with a random reserve as a maxmin mechanism within a class of
mechanisms termed as competitive mechanisms. Interestingly, the formats of
maxmin mechanisms in both papers are second-price auctions, albeit with
different random reserves. In this regard, this paper provides further support
on using second-price auctions for selling a good. In addition, we both assume
that bidders play undominated strategies. However, there are several
differences. First, the seller in his model does not know how bidders’
valuations are correlated, whereas the seller in mine knows that bidders’
valuations are independently and identically distributed. That is, the seller
knows more in my model, and therefore the revenue guarantee in my model is an
upper bound of the one in his model. Second, my solution concept is stronger
in that I allow the seller to choose a mechanism from the class of all
participation-securing mechanisms, which is a strict superset of the class of
competitive mechanisms.
Brooks and Du, 2021a  consider a model of auction design in the interdependent
value environment and assume that the seller knows only the mean of bidders’
prior valuation. They finds, among others, that a proportional auction, in
which the aggregate allocation is equal to the minimum of the sum of bidders’
signal and 1, and each bidder’s individual allocation is proportional to their
signal, is a maxmin mechanism across all participation-securing mechanisms for
the symmetric case. In their model, the seller knows neither the joint
distribution of bidders’ prior valuation profile nor how bidders’ signals are
correlated. This is in sharp contrast to my model, in which the seller knows
the joint distribution of bidders’ prior valuation profile and knows that
bidders’ signals about their prior valuations are independently and
identically distributed. Therefore, the revenue guarantee is an upper bound of
the one in their model. Indeed, they find that in the minmax information
structure, bidders’ prior valuation are perfectly correlated, so essentially a
common value model emerges endogenously. Hence, our methodologies differs. In
their model, the Nature’s minimization problem is a linear program using a
powerful tool of Bayes correlated equilibrium in Bergemann and Morris, (2013),
whereas the Nature’s minimization problem is a non-linear program in mine. In
addition, the solution concept in their paper is stronger than the one in
mine, as there are no restrictions on the set of equilibria that the Nature
can choose.
He and Li, (2022) and Zhang, 2021a  both consider a model of auction design in
the private value environment and assume that the seller knows the marginal
distribution of a generic bidder’s valuation but does not knows the
correlation structure between bidders’ valuations. Under different conditions
on the marginal distributions, they characterize, among others, that second-
price auctions with random reserves are maxmin mechanisms within (standard)
dominant-strategy mechanisms. One of the main differences is that the sets
over which the seller evaluates worst-case expected revenue are different: the
seller knows the marginal distribution but not the correlation structure in
those two papers, whereas the seller knows the correlation structure but not
the marginal distribution (except for the mean) in this paper. In addition,
the solution concept in this paper is stronger: the class of mechanisms
considered in this paper is much wider than the class of dominant-strategy
mechanisms.
This paper is also related to Carrasco et al., (2018), Zhang, 2021b  and
Zhang, 2022b . Carrasco et al., (2018) consider a model of monopoly selling in
which the seller sells a good to a single buyer when the seller knows an
arbitrary number of moment conditions. When there is only one bidder, my model
is reduced to to their special case in which the seller knows only the mean.
However, adding a second bidder with independently and identically distributed
valuations, there is strictly more competition in my model. Therefore, the
seller guarantees a higher revenue in my model. Zhang, 2021b  considers a
model of bilateral trade and characterizes optimal dominant-strategy
mechanisms when the profit-maximizing intermediary knows only the mean of each
trader’s valuations. Zhang, 2022b  considers a model of public good provision
and characterizes optimal dominant-strategy mechanisms when the profit-
maximizing principal knows only the mean of each agent’s valuation. One of the
main differences from those two papers is that this paper studies auction
designs. Moreover, the designers in those two papers knows less: the designers
do not know how agents’ valuations are correlated.
Finally, this paper is related to the information design literature: see
Kamenica, (2019) and Bergemann and Morris, (2019) for recent surveys. The
closest related paper in this literature is Chen and Yang, (2020) who study
information design problems in the auction model. More specifically, they
assume that bidders acquire independently and identically distributed signals.
The seller, after observing the choice of the distribution but not the signal
realizations, designs a revenue-maximizing mechanisms. They find, among
others, that the seller-worst information structure is an equal-revenue
distribution for the two-bidder case. It has been an open question whether
strong duality holds in the independent private value model. This paper
provides a positive answer to (a version of) this question for the two-bidder
case. Indeed, the result in this paper implies that the seller-worst
information structure is an equal-revenue distribution for the two-bidder
case. In addition, when there are more than two possible prior valuations, I
provide a sufficient condition such that the result still holds (Corollary 3),
which implies that the seller-worst information structure is an equal-revenue
distribution for the two-bidder case when that sufficient condition holds.
That sufficient condition covers many prior valuation distributions that are
not covered in their paper. In this regard, this paper complements their work.

##  2 Model

###  2.1 Information

A seller sells a single unit of good. For exposition, I assume that the supply
cost of the good is zero. There are two bidders, indexed by $i\in\\{1,2\\}$,
competing for the good. Each bidder’s prior valuation, denoted by $v_{i}$, is
identically and independently drawn from a Bernoulli distribution $F$ on
$\\{0,1\\}$. I denote by $v=(v_{1},v_{2})$ the prior valuation profile. I
denote by $F\times F$ the joint distribution of the prior valuation profile.
$F\times F$ is common knowledge among the seller and the bidders. I denote by
$\mu=E[v_{i}]=Pr(v_{i}=1)$ the expectation of each bidder’s prior valuation.
To rule out trivial cases, I assume that $\mu\in(0,1)$.
Each bidder $i$ may observe an independently and identically distributed
signal $s_{i}$ about $v_{i}$. The fact that $s_{1}$ and $s_{2}$ are
independently and identically distributed and the signal distribution are
common knowledge between the two bidders. In contrast, the seller knows that
$s_{1}$ and $s_{2}$ are independently and identically distributed but does not
know the signal distribution. In addition, bidders play undominated
strategies, which is known by the seller. Following Roesler and Szentes,
(2017), I say a signal distribution is possible if each signal of a bidder
provides her with an unbiased estimate about her valuation, or
$E[v_{i}|s_{i}]=s_{i}$. Using Blackwell’s characterization (Blackwell,, 1953),
the prior valuation distribution $F$ is a mean-preserving spread of a possible
signal distribution. I denote the set of possible signal distributions by
$\mathcal{G}_{F}$ with a typical element $G$. Because $F$ is a Bernoulli
distribution on $\\{0,1\\}$, a signal distribution is possible if and only if
the mean is $\mu$. Formally,

$\mathcal{G}_{F}=\\{G:[0,1]\to[0,1]|\int_{0}^{1}sdG(s)=\mu\quad\text{and $G$
is a CDF}\\}.$

###  2.2 Mechanism

A mechanism $\mathcal{M}$ consists of measurable sets of messages $M_{i}$ for
each $i$ and measurable allocation rules $q_{i}:M\to[0,1]$ and measurable
payment rules: $t_{i}:M\to\mathbb{R}$ for each $i$, where $M=M_{1}\times
M_{2}$ is the set of message profiles, such that $q_{1}(m)+q_{2}(m)\leq 1$ for
each $m\in M$. Bidders’ preferences are quasilinear. Given a mechanism
$\mathcal{M}$ and a simultaneously submitted message profile $m$, bidder $i$
with a signal of $s_{i}$ has a utility

$U_{i}(s_{i},m)=s_{i}\cdot q_{i}(m)-t_{i}(m).$

I require the mechanism to satisfy a participation security constraint: For
each $i$, there exists a message $m_{i}\equiv 0\in M_{i}$ such that for each
$s_{i}\in[0,1]$ and each $m_{-i}\in M_{-i}$,

$U_{i}(s_{i},(0,m_{-i}))\geq 0.$

Bidder $i$ with a signal $s_{i}$ can guarantee a non-negative utility by
sending this message, regardless of messages sent by the other bidder.

###  2.3 Equilibrium

Given a mechanism $\mathcal{M}$ and a signal distribution $G$, I have a game
of incomplete information. A Bayes Nash Equilibrium (BNE) of the game is a
strategy profile $\sigma=(\sigma_{i})$, $\sigma_{i}:[0,1]\to\Delta(M_{i})$,
such that $\sigma_{i}$ is best response to $\sigma_{-i}$: let
$U_{i}(s_{i},\mathcal{M},G,\sigma)=\int_{s_{-i}}U_{i}(s_{i},(\sigma_{i}(s_{i}),\sigma_{-i}(s_{-i})))dG(s_{-i})$
where $U_{i}(s_{i},(\sigma_{i}(s_{i}),\sigma_{-i}(s_{-i})))$ is the
multilinear extension of $U_{i}$ in Equation (2.2), then for any
$i,s_{i},\sigma_{i}^{\prime}$,

$U_{i}(s_{i},\mathcal{M},G,\sigma)\geq
U_{i}(s_{i},\mathcal{M},G,(\sigma_{i}^{\prime},\sigma_{-i})).$

The set of all Bayes Nash Equilibria in undominated strategies for a given
mechanism $\mathcal{M}$ and a given signal distribution $G$ is denoted by
$\Sigma(\mathcal{M},G)$.
Given a mechanism $\mathcal{M}$, the expected revenue at a signal distribution
$G$ and an equilibrium $\sigma$ is

$R(\mathcal{M},G,\sigma)=\int_{s_{1}}\int_{s_{2}}[t_{1}(\sigma_{1}(s_{1}),\sigma_{2}(s_{2}))+t_{2}(\sigma_{1}(s_{1}),\sigma_{2}(s_{2}))]dG(s_{2})dG(s_{1}).$

I refer to the integrand as the interim revenue given the signal profile
$(s_{1},s_{2})$ at the equilibrium $\sigma$.

###  2.4 Solution concept

I adopt the following solution concept:
A maxmin solution is a triple $(\mathcal{M},G,\sigma)$ of a mechanism, a
possible signal distribution, and a strategy profile, with profit
$R=R(\mathcal{M},G,\sigma)$, such that the following conditions are satisfied:
C1. For any possible signal distribution $G^{\prime}$ and any equilibrium in
undominated strategies $\sigma^{\prime}$ in $\Sigma(\mathcal{M},G^{\prime})$,
$R\geq R(\mathcal{M},G^{\prime},\sigma^{\prime})$.
C2. For any mechanism $\mathcal{M}^{\prime}$ and any equilibrium in
undominated strategies $\sigma^{\prime}$ in $\Sigma(\mathcal{M}^{\prime},G)$,
$R\geq R(\mathcal{M}^{\prime},G,\sigma^{\prime})$.
C3. Strategy profile $\sigma$ is in $\Sigma(M,G)$.
I refer to $R$ as the revenue guarantee of the solution. Note that if
$\Sigma(\mathcal{M},G^{\prime})=\emptyset$, then the condition C1 holds
trivially; similarly, if $\Sigma(\mathcal{M}^{\prime},G)=\emptyset$, then the
condition C2 holds trivially.
My solution concept is similar to but weaker than the “strong maxmin solution”
in Brooks and Du, 2021b : On the one hand, we both allow general
participation-securing mechanisms. On the other hand, I restrict attention to
equilibria in undominated strategies, whereas they do not place any
restrictions on equilibria.

##  3 Main Result

In this section, I first formally define a mechanism $\bar{\mathcal{M}}$
(Section 3.1), a possible signal distribution $\bar{G}$ (Section 3.2) and a
strategy profile $\bar{\sigma}$ (Section 3.3), then I present the formal
statement of the result (Section 3.4) that the proposed mechanism, the
proposed signal distribution together with the proposed strategy profile
constitute a maxmin solution. Finally, I prove the formal statement (Section
3.5).

###  3.1 Mechanism $\bar{\mathcal{M}}$

The mechanism $\bar{\mathcal{M}}$ is a second-price auction with a random
reserve whose cumulative distribution function $\bar{H}$ is as follows:

$\bar{H}(x)=\left\\{\begin{array}[]{lll}-\frac{x(1-a)(\ln{x}-\ln{a})}{(x-a)\ln{a}}&&{\text{if
$x\in(0,a)\cup(a,1]$},}\\\ -\frac{1-a}{\ln{a}}&&{\text{if $x=a$},}\\\
0&&{\text{if $x=0$},}\end{array}\right.$

where $a\in(0,1)$ is the unique solution to

$\tilde{a}(1-\ln{\tilde{a}})=\mu.$

To see that $\bar{H}$ is a distribution on $[0,1]$, note first that
$\bar{H}(x)$ is continuous, following from $\lim_{x\to
a}\bar{H}(x)=\bar{H}(a)$ and $\lim_{x\to 0}\bar{H}(x)=\bar{H}(0)=0$ using
L’Hôpital’s rule. Second, it can be shown that $\bar{H}(x)$ is strictly
increasing (Lemma 1). Third, $\bar{H}(1)=1$. In addition, it is
straightforward to show that $\bar{H}(x)$ is differentiable at any $x\neq 0$
using L’Hôpital’s rule, i.e., $\bar{H}$ is a continuous distribution (Lemma
1). See Figure 1 for an illustration.

$0$$1$$x$$0$$1$$\bar{H}(x)$ Figure 1: CDF of the Random Reserve in
$\bar{\mathcal{M}}$

######  Lemma 1.

$\bar{H}(x)$ is strictly increasing. In addition, $\bar{H}(x)$ is
differentiable at any $x\neq 0$. Moreover, $\lim_{x\to
0}x\bar{H}^{\prime}(x)=0$.

###### Proof.

For any $x\neq 0$ or $a$,
$\bar{H}^{\prime}(x)=-\frac{(1-a)(x-a\ln{x}-\mu)}{(x-a)^{2}\ln{a}}$. Define
$J(x)\equiv x-a\ln{x}$. Because $J^{\prime}(x)=1-\frac{a}{x}$ and
$J^{\prime\prime}(x)=\frac{a}{x^{2}}>0$, $J(x)$ is minimized at $x=a$ and the
minimized value is equal to $a-a\ln{a}=\mu$. Therefore for any $x\neq 0$ or
$a$, $\bar{H}^{\prime}(x)>0$. In addition, $\lim_{x\to
a}\bar{H}^{\prime}(x)=-\frac{1-a}{2a\ln{a}}>0$ using L’Hôpital’s rule (twice).
Moreover, $\lim_{x\to
0}x\bar{H}^{\prime}(x)=-\frac{(1-a)(x^{2}-ax\ln{x}-x\mu)}{(x-a)^{2}\ln{a}}=0$
using L’Hôpital’s rule. ∎

More formally, the mechanism
$\bar{\mathcal{M}}=(\bar{M},\bar{q}_{i},\bar{t}_{i})_{i\in\\{1,2\\}}$ is
defined as follows. It is a direct mechanism, i.e., $\bar{M}=[0,1]^{2}$. With
slight abuse of notations, I denote by $(s_{1},s_{2})$ the reported message
profile. If $s_{1}>s_{2}$, then $\bar{q}_{1}(s_{1},s_{2})=\bar{H}(s_{1})$,
$\bar{q}_{2}(s_{1},s_{2})=0$,
$\bar{t}_{1}(s_{1},s_{2})=s_{1}\bar{H}(s_{1})-\int_{s_{2}}^{s_{1}}\bar{H}(x)dx$,
$\bar{t}_{2}(s_{1},s_{2})=0$; if $s_{1}<s_{2}$, then
$\bar{q}_{1}(s_{1},s_{2})=0$, $\bar{q}_{2}(s_{1},s_{2})=\bar{H}(s_{2})$,
$\bar{t}_{1}(s_{1},s_{2})=0,\bar{t}_{2}(s_{1},s_{2})=s_{2}\bar{H}(s_{2})-\int_{s_{1}}^{s_{2}}\bar{H}(x)dx$;
if $s_{1}=s_{2}=x$, then
$\bar{q}_{1}(s_{1},s_{2})=\bar{q}_{2}(s_{1},s_{2})=\frac{\bar{H}(x)}{2}$,
$\bar{t}_{1}(s_{1},s_{2})=\bar{t}_{2}(s_{1},s_{2})=\frac{x\bar{H}(x)}{2}$.

###  3.2 Signal distribution $\bar{G}$

$\bar{G}$ is an equal-revenue distribution as follows:

$\bar{G}(x)=\left\\{\begin{array}[]{lll}1-\frac{a}{x}&&{\text{if $a\leq
x<1$},}\\\ 1&&{\text{if $x=1$}.}\end{array}\right.$

Note that $\bar{G}$ is a possible signal distribution because $a$ is a
solution to Equation (3.1). Define $\bar{R}\equiv 2a-a^{2}$. As will be shown
(Section 3.5.2), $\bar{R}$ is an upper bound of the expected revenue for any
participation-securing mechanism and any equilibrium under the signal
distribution $\bar{G}$.

###  3.3 Strategy profile $\bar{\sigma}$

Finally, let $\bar{\sigma}$ be the truth-telling strategy profile in the
mechanism $\bar{\mathcal{M}}$ under the signal distribution $\bar{G}$: for all
$i$ and $s_{i}$, $\bar{\sigma}_{i}(s_{i})$ puts probability one on $s_{i}$.
This completes the construction of the solution.

###  3.4 Formal statement: Theorem 1

######  Theorem 1.

$(\bar{\mathcal{M}},\bar{G},\bar{\sigma})$ is a maxmin solution with a revenue
guarantee of $\bar{R}$.

###  3.5 Proof of Theorem 1

####  3.5.1 Lower Bound on Revenue for $\bar{\mathcal{M}}$

I first establish C1 in the definition of a maxmin solution.

######  Proposition 1.

For any possible signal distribution $G$ and any equilibrium in undominated
strategies $\sigma$ in $\Sigma(\bar{\mathcal{M}},G)$,
$R(\bar{\mathcal{M}},G,\sigma)\geq\bar{R}$.

###### Proof.

Given the mechanism $\bar{\mathcal{M}}$, truth-telling is the unique
equilibrium in undominated strategies under any signal distribution.
Therefore, I focus on the truth-telling equilibrium and show that $\bar{G}$
minimizes the expected revenue across possible signal distributions. Given a
signal profile $(s_{1},s_{2})$, let $s(1)$ be $\max\\{s_{1},s_{2}\\}$ and
$s(2)$ be $\min\\{s_{1},s_{2}\\}$. Then in the truth-telling equilibrium, the
expected revenue given the mechanism $\bar{\mathcal{M}}$ and an arbitrary
signal distribution $G$ can be expressed as follows:

$\begin{split}E[t_{1}(s_{1},s_{2})+t_{2}(s_{1},s_{2})]&=\int_{0}^{1}\int_{0}^{1}[s(1)\bar{H}(s(1))-\int_{s(2)}^{s(1)}\bar{H}(x)dx]dG(s_{1})dG(s_{2})\\\
&=\int_{0}^{1}\int_{0}^{1}s(1)\bar{H}(s(1))dG(s_{1})dG(s_{2})-\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\bar{H}(x)\mathbbm{1}_{s(2)\leq
x\leq s(1)}dxdG(s_{1})dG(s_{2})\\\
&=\int_{0}^{1}\\{\underbrace{(1-G^{2}(x))[x\bar{H}^{\prime}(x)+\bar{H}(x)]}_{\text{the
first term}}-\underbrace{\bar{H}(x)[2G(x)(1-G(x))]}_{\text{the second
term}}\\}dx,\end{split}$

where the first term of the last line is obtained using integration by
parts222$x\bar{H}(x)$ is differentiable everywhere by Lemma 1. and the fact
that $s(1)$’s cumulative distribution function is $G^{2}$, and the second term
of the last line is obtained using Fubini’s theorem and the fact that $s(2)$’s
cumulative distribution function is $G^{2}+2G(1-G)$. Note that
$\int_{0}^{1}(1-G(x))dx=\mu$ holds for any possible signal distribution, using
integration by parts. Then to show that $\bar{G}$ minimizes
$\mathcal{L}(G,\bar{H})\equiv\int_{0}^{1}\\{(1-G^{2}(x))[x\bar{H}^{\prime}(x)+\bar{H}(x)]-\bar{H}(x)[2G(x)(1-G(x))]\\}dx$,
it suffices to show that there exists a real number $\lambda$ such that
$\bar{G}$ minimizes

$\mathcal{L}(G,\bar{H},\lambda)\equiv\int_{0}^{1}\\{(1-G^{2}(x))[x\bar{H}^{\prime}(x)+\bar{H}(x)]-\bar{H}(x)[2G(x)(1-G(x))]-\lambda(1-G(x))\\}dx.$

This is because
$\mathcal{L}(\bar{G},\bar{H},\lambda)\leq\mathcal{L}(G,\bar{H},\lambda)$
implies $\mathcal{L}(\bar{G},\bar{H})\leq\mathcal{L}(G,\bar{H})$ for any
possible signal distribution $G$ by adding $\lambda\mu$ to both sides. Now
take $\lambda=-\frac{2(1-a)}{\ln{a}}$. I am going to point-wise minimize the
integrand of $\mathcal{L}(G,\bar{H},\lambda)$ for any $x\neq 0,a$ or 1. First,
with slight rewriting, the integrand of $\mathcal{L}(G,\bar{H},\lambda)$
becomes

$\mathcal{I}(G,\bar{H},\lambda)\equiv[\bar{H}(x)-x\bar{H}^{\prime}(x)]G^{2}(x)-2[\bar{H}(x)+\frac{1-a}{\ln{a}}]G(x)+\bar{H}(x)+x\bar{H}^{\prime}(x)+\frac{2(1-a)}{\ln{a}}.$

This is a simple quadratic function of $G(x)$. By simple calculation,
$\bar{H}(x)-x\bar{H}^{\prime}(x)=\frac{x[\bar{H}(x)+\frac{1-a}{\ln{a}}]}{x-a}>0$
for any $x\neq 0$ or $a$, following from $\bar{H}(x)$ being strictly
increasing and $\bar{H}(a)=-\frac{1-a}{\ln{a}}$. Then, for any $a<x<1$,
$G(x)=1-\frac{a}{x}$ is the unique minimizer of (3.5.1). For any $0<x<a$,
$G(x)=0$ is the unique minimizer of (3.5.1) as $1-\frac{a}{x}<0$ if $0<x<a$.
This implies that the signal distribution $\bar{G}$ minimizes
$\mathcal{L}(G,\bar{H},\lambda)$ and therefore minimizes the expected revenue
across possible signal distributions. By simple calculation, the minimized
expected revenue is equal to $2a-a^{2}$. The details about the construction of
the distribution $\bar{H}$ as well as the Lagrangian multiplier $\lambda$ are
provided below ∎

Construction of $\bar{H}$ and $\lambda$. Consider a second-price auction with
a random reserve whose cumulative distribution function is $H$. Assuming that
$H(x)$ is differentiable at any $x\in(0,1]$ and $\lim_{x\to 0}xH(x)$ exists,
then the expected revenue under a signal distribution $G$ can be expressed as
$\mathcal{L}(G,H)$. I subtract $\lambda\mu$ from $\mathcal{L}(G,H)$ where
$\lambda$ is some real number, and obtain $\mathcal{L}(G,H,\lambda)$. Then a
sufficient condition for $\bar{G}$ to be a minimizer of $\mathcal{L}(G,H)$ is
that $\bar{G}(x)$ point-wise minimizes the integrand of
$\mathcal{L}(G,H,\lambda)$. The first order condition with respect to $G(x)$
is as follows:

$-2G(x)[xH^{\prime}(x)+H(x)]-2H(x)(1-2G(x))+\lambda=0.$

Plugging $G(x)=1-\frac{a}{x}$ to (3.5.1),

$(x-a)H^{\prime}(x)+\frac{a}{x}\cdot H(x)=\frac{\lambda}{2}.$

Solving this differential equation: for any $x\neq 0$ or $a$,

$H(x)=\frac{x(\frac{\lambda}{2}\ln{x}+c)}{x-a},$

where $c$ is some constant. Using $H(1)=1$, I obtain that $c=1-a$. In order
for $\lim_{x\to a}H(a)$ to exist, the nominator of (3.5.1) has to be 0 when
$x=a$, leading to that $\lambda=-\frac{2(1-a)}{\ln{a}}$.

######  Remark 1.

The assumption that bidders play undominated strategies is important for this
result. Without this assumption, there indeed exist a possible signal
distribution and an equilibrium such that the expected revenue in the
mechanism $\bar{\mathcal{M}}$ is lower than $\bar{R}$. Take the signal
distribution to be a point mass on $\mu$, i.e., bidders observe no signal at
all, and consider the strategy profile where one bidder reports $\mu$ and the
other bidder reports 0. It is straightforward to verify that this strategy
profile is an equilibrium (in which one of the bidders uses a dominated
strategy). The expected revenue in this equilibrium under this signal
distribution is $\mu\cdot\bar{H}(\mu)-\int_{0}^{\mu}\bar{H}(x)dx$, which is
lower than $2a-a^{2}$ for any $\mu$. For a parametric example, when $\mu=0.5$,
the former is about 0.1223, whereas the latter is about 0.3385.

####  3.5.2 Upper Bound on Revenue for $\bar{G}$

Next, I establish C2 in the definition of a maxmin solution.

######  Proposition 2.

For any participation-securing mechanism $\mathcal{M}$ and any equilibrium in
undominated strategies $\sigma$ in $\Sigma(\mathcal{M},\bar{G})$,
$R(\mathcal{M},\bar{G},\sigma)\leq\bar{R}$.

###### Proof.

Indeed, I will establish a slightly stronger statement: $\bar{R}$ is an upper
bound on the expected revenue for any participation-securing mechanism and any
equilibrium.
First, to identify an upper bound on the expected given a signal distribution,
it is without loss to restrict attention to direct mechanisms, i.e.,
$M=[0,1]^{2}$, as the revelation principle holds. Next, for exposition, I
parameterize each type $s_{i}$ by its quantile $z_{i}$.333See Carroll, (2017)
and Zhang, 2022a  for a similar method. Formally, I define the inverse
quantile function as follows:

$\bar{s}(z_{i})=\min\\{\tilde{s_{i}}|\bar{G}(\tilde{s_{i}})\geq
z_{i}\\}=\left\\{\begin{array}[]{lll}\frac{a}{1-z_{i}}&&{\text{if $0\leq
z_{i}<1-a$},}\\\ 1&&{\text{if $z_{i}\geq 1-a$}.}\end{array}\right.$

I denote the signal profile by $z=(z_{1},z_{2})\in[0,1]^{2}$. Note that
$z_{1}$ and $z_{2}$ follow independently and identically distributed uniform
distributions on $[0,1]$. Then, for any direct mechanism
$(q_{i}(z),t_{i}(z))_{i\in\\{1,2\\}}$ where $q_{i}(z)\in[0,1]$ is the
allocation probability to bidder $i$ given the parameterized signal profile
$z$ and $t_{i}(z)\in\mathrm{R}$ is the payment made by bidder $i$ given $z$,
(2.3) and (2.2) together imply that for all $i$, all $z_{i}$, and all
$z_{i}^{\prime}$,

$U_{i}(z_{i})\equiv\bar{s}(z_{i})Q_{i}(z_{i})-T_{i}(z_{i})\geq\bar{s}(z_{i})Q_{i}(z_{i}^{\prime})-T_{i}(z_{i}^{\prime}),$
$\bar{s}(z_{i})Q_{i}(z_{i})-T_{i}(z_{i})\geq 0,$

where $Q_{i}(z_{i})=\int_{z_{-i}}q_{i}(z_{i},z_{-i})dz_{-i}$ and
$T_{i}(z_{i})=\int_{z_{-i}}t_{i}(z_{i},z_{-i})dz_{-i}$ are the expected
allocation to type $z_{i}$ of bidder $i$ and the expected payment made by type
$z_{i}$ of bidder $i$, respectively.
For $z_{i}^{\prime}\geq z_{i}$, (3.5.2) implies that

$(\bar{s}(z_{i}^{\prime})-\bar{s}(z_{i}))Q_{i}(z_{i}^{\prime})\geq
U_{i}(z_{i}^{\prime})-U_{i}(z_{i})\geq(\bar{s}(z_{i}^{\prime})-\bar{s}(z_{i}))Q_{i}(z_{i}).$

Then $U_{i}(z_{i})$ is Lipschitz, thus absolutely continuous w.r.t. $z_{i}$,
and so equal to the integral of its derivative. In addition, note that
$\bar{s}(z_{i})$ is differentiable for all $z_{i}$ except for $z_{i}=1-a$.
Then applying the envelope theorem to (3.5.2) at each point of
differentiability, I obtain that

$\frac{\partial U_{i}(z_{i})}{\partial
z_{i}}=\frac{\partial\bar{s}(z_{i})}{\partial
z_{i}}Q_{i}(z_{i})=\left\\{\begin{array}[]{lll}\frac{a}{(1-z_{i})^{2}}Q_{i}(z_{i})&&{\text{if
$0\leq z_{i}<1-a$},}\\\ 0&&{\text{if $z_{i}>1-a$}.}\end{array}\right.$

Thus,

$U_{i}(z_{i})=\left\\{\begin{array}[]{lll}U_{i}(0)+\int_{0}^{z_{i}}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}&&{\text{if
$0\leq z_{i}<1-a$},}\\\
U_{i}(0)+\int_{0}^{1-a}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}&&{\text{if
$z_{i}\geq 1-a$}.}\end{array}\right.$

Therefore, the expected revenue from bidder $i$ satisfies

$\begin{split}\int_{0}^{1}T_{i}(z_{i})dz_{i}&=\int_{0}^{1}[\bar{s}(z_{i})Q_{i}(z_{i})-U_{i}(z_{i})]dz_{i}\\\
&=\int_{0}^{1-a}\\{\bar{s}(z_{i})Q_{i}(z_{i})-U_{i}(0)-\int_{0}^{z_{i}}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}\\}dz_{i}+\\\
&\int_{1-a}^{1}\\{\bar{s}(z_{i})Q_{i}(z_{i})-U_{i}(0)-\int_{0}^{1-a}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}\\}dz_{i}\\\
&\leq\int_{0}^{1-a}\\{\bar{s}(z_{i})Q_{i}(z_{i})-\int_{0}^{z_{i}}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}\\}dz_{i}+\\\
&\int_{1-a}^{1}\\{\bar{s}(z_{i})Q_{i}(z_{i})-\int_{0}^{1-a}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}\\}dz_{i}\\\
&=\\{\int_{0}^{1-a}[(\bar{s}(z_{i})-(1-a-z_{i})\frac{a}{(1-z_{i})^{2}})Q_{i}(z_{i})]dz_{i}+\\\
&\int_{1-a}^{1}[\bar{s}Q_{i}(z_{i})-\int_{0}^{1-\frac{1}{e}}[\frac{a}{(1-\tilde{z_{i}})^{2}}Q_{i}(\tilde{z_{i}})]d\tilde{z_{i}}]dz_{i}\\}\\\
&=\\{\int_{0}^{1-a}[(\bar{s}(z_{i})-(1-z_{i})\frac{a}{(1-z_{i})^{2}})Q_{i}(z_{i})]dz_{i}+\int_{1-a}^{1}[(\bar{s}(z_{i})Q_{i}(z_{i})]dz_{i}\\}\\\
&=\int_{1-a}^{1}Q_{i}(z_{i})dz_{i},\end{split}$

where the first inequality holds because (3.5.2) implies that $U_{i}(0)\geq
0$, the third equality is obtained via integration by parts, the last equality
holds because $\bar{s}(z_{i})-(1-z_{i})\frac{a}{(1-z_{i})^{2}}=0$ for $0\leq
z_{i}<1-a$ and $\bar{s}(z_{i})=1$ for $z_{i}>1-a$.
Then, the expected revenue from all the bidders satisfies

$\begin{split}\sum_{i=1}^{2}\int_{0}^{1}T_{i}(z_{i})dz_{i}&=\int_{0}^{1-a}\int_{1-a}^{1}q_{1}(z_{1},z_{2})dz_{1}dz_{2}+\int_{0}^{1-a}\int_{1-a}^{1}q_{2}(z_{1},z_{2})dz_{2}dz_{1}\\\
&+\int_{1-a}^{1}\int_{1-a}^{1}[q_{1}(z_{1},z_{2})+q_{2}(z_{1},z_{2})]dz_{1}dz_{2}\\\
&\leq 2a(1-a)+a^{2}=2a-a^{2},\end{split}$

where the inequality holds because $q_{i}(z)\leq 1$ and $q_{1}(z)+q_{2}(z)\leq
1$ for all $i$ and $z$. This finishes the proof. ∎

This argument is standard (Myerson,, 1981). The parameterization makes the
proof clean.
Finally, recall that the truth-telling strategy profile $\bar{\sigma}$ is an
equilibrium in undominated strategies in the mechanism $\bar{\mathcal{M}}$
under the signal distribution $\bar{G}$, as the mechanism $\bar{\mathcal{M}}$
is a dominant-strategy mechanism. Then, Theorem 1 follows immediately from
Proposition 1 and 2.

##  4 Discussion and Extension

###  4.1 Value of randomization

Recall that Suzdaltsev, (2020) characterizes the optimal deterministic reserve
price for the second-price auction in the same framework, which is zero in my
setting. For the two-bidder case, my proposed mechanism, which involves
randomization, achieves a strictly higher revenue guarantee. For a parametric
example, if $\mu=0.5$, then the revenue guarantee under my proposed mechanism
is about 0.3385, whereas the one under his mechanism is 0.25. Intuitively,
randomization hedges against uncertainty towards signal distributions,
rendering a higher revenue guarantee. To my knowledge, it is an open question
what the optimal deterministic mechanism is in this setting. Therefore, the
difference between the revenue guarantee of my mechanism and the one of his
can be interpreted as an upper bound on the “value of randomization”.

###  4.2 Cost of correlation

Recall that Che, (2019) finds that a second-price auction with a random
reserve maximizes the revenue guarantee across a wide range of mechanisms in
the private value environment in which the seller only knows the expectation
of the value distribution. That is, values across bidders can be correlated.
As expected, the revenue guarantee of my proposed mechanism is strictly higher
in my setting for the two-bidder case than the one in his setting. This is
because the seller in my setting knows more: he knows that the correlation
structure is the independent one. For a parametric example, if $\mu=0.5$, then
the revenue guarantee of his mechanism in his setting is about 0.317, which is
strictly smaller than 0.3385. Intuitively, independently and identically
distributed signal distributions makes my setting more competitive. Indeed, in
his worst-case value distribution, the competitor of the high-valuation bidder
always has the lowest possible valuation. To my knowledge, it is not known
what the maxmin mechanism is across all participation-securing mechanisms
(even across all dominant-strategy mechanisms) in his setting. Therefore, the
difference between the revenue guarantee in my paper and the one in his paper
can be interpreted as an upper bound on the “cost of correlation”.

###  4.3 Other maxmin solutions

######  Corollary 1.

Let $\bar{\mathcal{M}}^{*}$ be a second price auction with a random reserve
whose cumulative distribution is $H^{*}$. Then
$(\bar{\mathcal{M}}^{*},\bar{G},\bar{\sigma})$ is a maxmin solution with a
revenue guarantee of $\bar{R}$ if $H^{*}$ satisfies the following properties:
P1. $H^{*}(x)=\bar{H}(x)$ for $x\geq a$.
P2. $H^{*}(x)-x\cdot(H^{*})^{\prime}(x)\geq 0$ for $x<a$.

###### Proof.

By the proof of Proposition 1, the property $P1$ implies that for any $a<x<1$,
$G(x)=1-\frac{a}{x}$ is the unique minimizer of
$\mathcal{I}(G,H^{*},\lambda)$. Moreover, the properties $P1$ and $P2$
together imply that for any $0<x<a$, $G(x)=0$ is the unique minimizer of
$\mathcal{I}(G,H^{*},\lambda)$, as $\mathcal{I}(G,H^{*},\lambda)$ is a
(weakly) convex function of $G$. ∎

In a maxmin solution, there is some flexibility for the distribution of a
random reserve when the reserve is below $a$. One example that satisfies $P2$
is that $H^{*}(x)=\bar{H}(a)$ for $x<a$, i.e., there is a probability mass of
size $\bar{H}(a)$ on zero.

###  4.4 Knowing the second moment

Suppose that the seller knows only the second moment of the signal
distribution as well as that the two signals are independently and identically
distributed. Let $\delta$ denote the known second moment, i.e.,
$\delta=\int_{0}^{1}x^{2}dG(x)$. Then I will show that the second-price
auction with the uniformly distributed random reserve ($\hat{\mathcal{M}}$),
the equal-revenue distribution with $a=1-\sqrt{1-\delta}$ ($\hat{G}$), and the
truth-telling strategy profile ($\hat{\sigma}$) constitute a maxmin solution
in this case.

######  Corollary 2.

If the seller knows only the second moment of the signal distribution as well
as that the two signals are independently and identically distributed, then
$(\hat{\mathcal{M}},\hat{G},\hat{\sigma})$ is a maxmin solution with a revenue
guarantee of $\delta$.

###### Proof.

It suffices to show that $\hat{G}$ minimizes the expected revene in the truth-
telling equilibrium under the mechanism $\hat{\mathcal{M}}$. First, using
integration by parts, the constraint $\delta=\int_{0}^{1}x^{2}dG(x)$ can be
rewritten as $\delta=2\int_{0}^{1}x(1-G(x))dx$. Similar to the proof of
Proposition 1, I construct a Lagrangian as follows:

$\hat{\mathcal{L}}(G,\hat{H},\lambda)\equiv\int_{0}^{1}\\{(1-G^{2}(x))[x\hat{H}^{\prime}(x)+\hat{H}(x)]-\hat{H}(x)[2G(x)(1-G(x))]-2\lambda
x(1-G(x))\\}dx.$

Let $\lambda$ be 1. It is straightforward that the integrand of
$\hat{\mathcal{L}}(G,\hat{H},\lambda)$ is a constant of 0 because
$\hat{H}(x)=x$, implying that any signal distribution with the known second
moment yields the same expected revenue in the truth-telling equilibrium under
the mechanism $\hat{\mathcal{M}}$. Alternatively, observe that the interim
revenue at the signal profile $(s_{1},s_{2})$ is
$\frac{s_{1}^{2}+s_{2}^{2}}{2}$ in the truth-telling equilibrium under the
mechanism $\hat{\mathcal{M}}$. This also implies that the expected revenue is
$\delta$ for any signal distribution with the known second moment. ∎

###  4.5 Beyond Binary Prior Valuations

Suppose that there are more than two possible prior valuations. Recall that
$G$ is a possible signal distribution if and only if $F$ is a mean-preserving-
spread of $G$ (Blackwell,, 1953). Formally, the set of possible signal
distributions can now be defined as follows:

$\mathcal{G}_{F}=\\{G:[0,1]\to[0,1]|\int_{0}^{x}F(s)ds\geq\int_{0}^{x}G(s)ds,\forall
x\in[0,1],\int_{0}^{1}sdG(s)=\mu\quad\text{and $G$ is a CDF}\\}.$

######  Corollary 3.

If $\int_{0}^{x}F(s)ds\geq\int_{0}^{x}\bar{G}(s)ds$ for all $x\in[0,1]$, then
$(\bar{\mathcal{M}},\bar{G},\bar{\sigma})$ is a maxmin solution with a revenue
guarantee of $\bar{R}$.

###### Proof.

Note that this condition guarantees that $\bar{G}$ is a possible signal
distribution. Then Corollary 3 follows immediately from Theorem 1. ∎

To illustrate, consider an example in which $\mu=\frac{1}{2}$ and there are
three possible prior valuations: $0$, $\frac{1}{2}$ and 1. Their probabilities
are $b$, $1-2b$ and $b$, respectively. By simple calculation,

$\int_{0}^{x}\bar{G}(s)ds=\left\\{\begin{array}[]{lll}x-a-a\ln{x}+a\ln{a}&&{\text{if
$x\geq a$},}\\\ 0&&{\text{if $x<a$},}\end{array}\right.$

where $a(1-\ln{a})=\frac{1}{2}$ in this example.

$\int_{0}^{x}F(s)ds=\left\\{\begin{array}[]{lll}bx&&{\text{if
$x\leq\frac{1}{2}$},}\\\ \frac{1}{2}b+(x-\frac{1}{2})(1-b)&&{\text{if
$x>\frac{1}{2}$}.}\end{array}\right.$

It is straightforward to show that if $0.2588\approx-2a\ln{\frac{1}{2}}\leq
b\leq\frac{1}{2}$, this distribution is a mean-preserving spread of $\bar{G}$.
For another example, suppose $\mu=\frac{3}{4}$. Consider a prior valuation
distribution which is a combination of a uniform distribution on $[0,1)$ and
an atom of size $\frac{1}{2}$ on 1. Then, it can be shown that
$\int_{0}^{x}\bar{G}(s)ds-\int_{0}^{x}F(s)ds$ is decreasing in $x$ if $a\leq
x\leq 1-\sqrt{1-2a}\approx 0.515$, and is increasing in $x$ for
$1-\sqrt{1-2a}<x\leq 1$. Here $a(1-\ln{a})=\frac{3}{4}$. This implies that
$\int_{0}^{x}\bar{G}(s)ds-\int_{0}^{x}F(s)ds\leq 0$ for any $x\in[0,1]$, as
$\int_{0}^{1}\bar{G}(s)ds-\int_{0}^{1}F(s)ds=0$. Therefore, this distribution
is also a mean-preserving spread of $\bar{G}$.

##  5 Concluding Remarks

In this paper, I find that a second-price auction with a random reserve is a
maxmin mechanism across all participation-securing mechanisms for the two-
bidder case. The key step of the result is the construction of a saddle point,
which implies that (a version of) strong duality holds for two-bidder case in
my setting. It remains an open question that if strong duality holds for more-
than-two-bidder cases. This paper provides the first step towards a broad
study of robust auction design problems in the independent private value
model.

## References

  * Bergemann and Morris, (2013) Bergemann, D. and Morris, S. (2013).  Robust predictions in games with incomplete information.  Econometrica, 81(4):1251–1308.
  * Bergemann and Morris, (2019) Bergemann, D. and Morris, S. (2019).  Information design: A unified perspective.  Journal of Economic Literature, 57(1):44–95.
  * Bergemann and Schlag, (2008) Bergemann, D. and Schlag, K. H. (2008).  Pricing without priors.  Journal of the European Economic Association, 6(2-3):560–569.
  * Blackwell, (1953) Blackwell, D. (1953).  Equivalent comparisons of experiments.  The annals of mathematical statistics, pages 265–272.
  * (5) Brooks, B. and Du, S. (2021a).  Maxmin auction design with known expected values.
  * (6) Brooks, B. and Du, S. (2021b).  Optimal auction design with common values: An informationally robust approach.  Econometrica, 89(3):1313–1360.
  * Carrasco et al., (2018) 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, (2017) Carroll, G. (2017).  Robustness and separation in multidimensional screening.  Econometrica, 85(2):453–488.
  * Che, (2019) Che, E. (2019).  Distributionally robust optimal auction design under mean constraints.  arXiv preprint arXiv:1911.07103.
  * Chen and Yang, (2020) Chen, Y.-C. and Yang, X. (2020).  Information design in optimal auctions.  Available at SSRN 3673680.
  * Condorelli and Szentes, (2020) Condorelli, D. and Szentes, B. (2020).  Information design in the holdup problem.  Journal of Political Economy, 128(2):681–709.
  * Crémer and McLean, (1988) Crémer, J. and McLean, R. P. (1988).  Full extraction of the surplus in bayesian and dominant strategy auctions.  Econometrica, 56(6):1247–1258.
  * He and Li, (2022) He, W. and Li, J. (2022).  Correlation-robust auction design.  Journal of Economic Theory, 200:105403.
  * Kamenica, (2019) Kamenica, E. (2019).  Bayesian persuasion and information design.  Annual Review of Economics, 11:249–272.
  * Kohlberg and Mertens, (1986) Kohlberg, E. and Mertens, J.-F. (1986).  On the strategic stability of equilibria.  Econometrica: Journal of the Econometric Society, pages 1003–1037.
  * Myerson, (1981) Myerson, R. B. (1981).  Optimal auction design.  Mathematics of Operations Research, 6(1):58–73.
  * Palfrey and Srivastava, (1991) Palfrey, T. R. and Srivastava, S. (1991).  Nash implementation using undominated strategies.  Econometrica: Journal of the Econometric Society, pages 479–501.
  * Roesler and Szentes, (2017) Roesler, A.-K. and Szentes, B. (2017).  Buyer-optimal learning and monopoly pricing.  American Economic Review, 107(7):2072–80.
  * Suzdaltsev, (2020) Suzdaltsev, A. (2020).  Distributionally robust pricing in independent private value auctions.  arXiv preprint arXiv:2008.01618.
  * Wilson, (1987) Wilson, R. (1987).  Game-theoretic analyses of trading processes.  In Advances in Economic Theory, Fifth World Congress, pages 33–70.
  * Yamashita, (2015) Yamashita, T. (2015).  Implementation in weakly undominated strategies: Optimality of second-price auction and posted-price mechanism.  The Review of Economic Studies, 82(3):1223–1246.
  * (22) Zhang, W. (2021a).  Correlation robustly optimal auctions.  arXiv preprint arXiv:2105.04697.
  * (23) Zhang, W. (2021b).  Robust bilateral trade mechanisms with known expectations.  arXiv preprint arXiv:2105.05427.
  * (24) Zhang, W. (2022a).  Auctioning multiple goods without priors.  arXiv preprint arXiv:2204.13726.
  * (25) Zhang, W. (2022b).  Robust private supply of a public good.  arXiv preprint arXiv:2201.00923.


any $t\in V(T)$. Thus for every $H^{\prime}\in\mathrm{Spasm}\left\lparen
H\right\rparen$, we have that $H^{\prime}$ has a guarded cutvertex
decomposition with guard size at most $c$ and then Lemma 6.6 implies that
every graph in $\mathrm{Spasm}\left\lparen H\right\rparen$ has treewidth at
most $c$.

###  6.2 Half-colorful matchings

In this section, we look at half-colorful matchings, which are the main reason
why certain FPT cases cannot be solved in polynomial time. First, if we have
guraded cutvertex decomposition where $\lambda(t)$ is large for some node $t$,
then this can be used to extract a large half-colorful matching.

######  Lemma 6.16.

Let $(T,\beta,g)$ be a guarded cutvertex decomposition of a colored graph $H$
with guard size at most $c$ and the bags having at most $c$ colors. If
$\lambda(t)\geq k$ for some $t\in V(T)$, then $H$ contains a half-colorful
matching of size $k/c^{2}-1$.

###### Proof.

Let $x_{1}$, $\dots$, $x_{k}$ be vertices of $\lambda(t)$. By definition,
$x_{i}$ has a neighbor $y_{i}$ that is in $\alpha(t_{i})$ for some child
$t_{i}$ of $t$ and all the $t_{i}$’s are distinct. The $x_{i}$’s are in
$\beta(t)$, hence they come from at most $c$ different color classes. Thus
there are at least $k/c$ of them from the same color class, say, $C_{0}$. By
Lemma 6.7, each color can appear at most $c$ times on the $y_{i}$’s. This
means that we can select $k/c^{2}-1$ of the $y_{i}$’s such that they are from
distinct color classes different from $C_{0}$. This gives a half-colorful
matching of the required size.

The following lemma shows that a half-colorful matching can be cleaned in
certain way, assuming there are no large flowers in the graph (in which case
we know that he problem is hard anyway).

######  Lemma 6.17.

Let $H$ be a colored graph where there is no $c$-flower centered at any color
class for some $c\geq 1$. If there is a half-colorful $k$-matching centered at
color class $C_{0}$, then there is a set $S\subseteq C_{0}$ with $|S|\leq 3c$,
vertices $x_{1}$, $\dots$, $x_{k-3c}$ in $C_{0}$, and $k-3c$ color classes
$C_{i_{1}}$, $\dots$, $C_{i_{k-3c}}$ such that $x_{j}$ is the unique neighbor
of $C_{i_{j}}$ in $C_{0}\setminus S$.

###### Proof.

Let us consider all triples $(x,y,C_{i})$ where $x,y\in C_{0}$ are two
distinct vertices and $C_{i}$ is a color class different from $C_{0}$ such
that $x,y\in N(C_{i})$. These triples can be considered as 3-element subsets
of a universe $U$ consisting of the vertices of $C_{0}$ and elements
representing the color classes different from $C_{0}$. Let us select a maximum
collection of pairwise disjoint triples. We claim that if there are $m$
pairwise disjoint triples, then there is an $m$-flower centered at $C_{0}$ in
$H$. Indeed, the triple $(x,y,C_{i})$ means that there is a path from $x$ to
$y$ in $H^{\textup{\textbullet}\setminus 0}$ that has either one internal
vertex in $C_{i}$ (if $x$ and $y$ have common neighbor in $C_{i}$) or two
internal vertices in $C_{i}$ (if $x$ and $y$ have distinct neighbors in
$C_{i}$). Thus by the assumption of the lemma, the maximum collection contains
less than $c$ triples. Let $S$ be the set of all vertices of $C_{0}$ appearing
in the $m$ selected triples and let $\mathcal{C}$ contain all the color
classes appearing in these triples; we have $|S|+|\mathcal{C}|\leq 3m<3c$.

Suppose that $x_{1}y_{1}$, $\dots$, $x_{k}y_{k}$ is a half-colorful matching
where every $x_{i}$ is in $C_{0}$. Let us ignore those edges $x_{i}y_{i}$ of
the matching where $x_{i}\in S$ or the color class of $b_{i}$ is in
$\mathcal{C}$. This way, we ignore at most $|S|+|\mathcal{C}|\leq 3c$ edges,
hence at least $k-3c$ of them remain. Assume without loss of generality that
$x_{1}y_{1}$, $\dots$, $x_{k-3c}y_{k-3c}$ are among the remaining edges and
let $C_{i_{j}}$ be the color class of $y_{j}$. It is clear that $x_{j}$ is a
neighbor of the color class $C_{i_{j}}$ in $C_{0}\setminus S$. Moreover, if
there it has another neighbor $x^{\prime}_{j}\in C_{0}\setminus S$, then
$(x_{j},x^{\prime}_{j},C_{i_{j}})$ is a triple where
$x_{j},x^{\prime}_{j}\not\in S$ and $C_{i_{j}}\not\in\mathcal{C}$. However,
this means that the triple would be disjoint from each of the selected $m$
triples, contradicting the maximality of the selection. Thus $x_{1}$, $\dots$,
$x_{k-3c}$ satisfies the requirements of the lemma.

Finally, we show how a half-colorful matching with the properties given in
Lemma 6.17 can be exploited in a reduction from counting perfect matchings.

######  Lemma 6.18.

Let $H$ be a colored graph and suppose that we are given a set $S\subseteq
C_{0}$ with $|S|\leq c$, vertices $x_{1}$, $\dots$, $x_{k}$ in $C_{0}$, and
$k$ color classes $C_{1}$, $\dots$, $C_{k}$ such that $x_{j}$ is the unique
neighbor of $C_{j}$ in $C_{0}\setminus S$. Then given a $k+k$ vertex bipartite
graph $G$ and oracle access to $\mathrm{Sub}(H\to\star)$, we can count the
number of perfect matchings in $G$ in time $f(c)|V(H)|^{O(1)}$.

###### Proof.

We sketch the proof under the simplifying assumption that there is no color
class outside $C_{0}$, $\dots$, $C_{k}$, there are no edges inside color
classes or between $C_{i}$ and $C_{j}$ with $i,j>0$, and there are no isolated
vertices. It is easy to extend the proof to the general case.

Let $H_{0}$ be the graph $H$ with all the edges incident to $C_{0}\setminus
S=\\{x_{1},\dots,x_{k}\\}$ removed. Suppose that $a_{1}$, $\dots$, $a_{k}$,
$b_{1}$, $\dots$, $b_{k}$ are the vertices of $G$. We define the graph $H_{G}$
by starting with $H_{0}$, and for every edge $a_{i}b_{j}$ of $G$, we connect
$N(a_{i})\subseteq C_{i}$ with $b_{j}$.

The vertices of $C_{0}$ in $H$ are of two types: let $C^{1}_{0}$ contain those
vertices that are adjacent to exactly one color class $C_{i}$ and let
$C^{2}_{0}$ contain the remaining vertices, which are adjacent to more than
one class. Clearly, we have $C^{2}_{0}\subseteq S$ and in particular
$|C^{2}_{0}|\leq c$. For every $v\in C^{2}_{0}$, let us choose two edges that
connect it with two different color classes; let $F$ be the set of these
$2|C^{2}_{0}|\leq 2c$ edges.

With oracle access to $\mathrm{Sub}(H\to\star)$, we can use standard
inclusion-exclusion techniques to count the number of subgraphs of $H_{G}$
that are isomorphic to $H$ and moreover contains every vertex of $S$ and every
edge of $F$. We claim that the number of such subgraphs is exactly the number
of perfect matchings in $G$.

Consider a subgraph $H^{*}\subseteq H_{G}$ isomorphic to $H$ and let
$f:V(H)\to V(H_{G})$ be a corresponding embedding. Because every edge of $F$
appears in the subgraph, it is clear that $f$ has to map vertices of
$C^{2}_{0}$ in $H$ to vertices of $C^{2}_{0}$ in $H_{G}$, because no other
vertex in $H$ can be adjacent to two different color classes. It follows that
it is also true that $f$ maps vertices of $C^{1}_{0}$ in $H$ to vertices of
$C^{1}_{0}$ in $H_{G}$. Let $C^{1,i}_{0}$ be the subset of $C^{1}_{0}$
containng those vertices of $C^{1}_{0}$ that is adjacent only to color class
$C_{i}$. Then exactly $|C^{1,i}_{0}|-1$ of these vertices appear in $S$. As
every vertex of $S$ appears in the subgraph $H^{*}$, these vertices of $H_{G}$
are adjacent only to color class $C_{i}$, and there are no isolated vertices
in $H$, it follows that $f$ should map vertices of $C^{1,i}_{0}\cap S$ of $H$
to vertices of $C^{1,i}_{0}\cap S$ of $H_{G}$ and maps exactly one vertex of
$C^{1,i}_{0}$ to $C_{0}\setminus S$ in $H_{G}$. Thus the subgraph $H^{*}$
describes a matching of $H_{G}$: the edges of $H^{*}$ connect every $x_{i}$ to
a distinct color class $C_{j}$. Also, it is not hard to see that $H^{*}$
actually uses every edge betwen $x_{i}$ and this color class $C_{j}$ and
$H^{*}$ uses every edge incident to $S$. This means that the number of edge
sets of $H_{G}$ that form subgraphs isomorphic to $H$ is exactly the number of
perfect matchings in $G$.

###  6.3 Algorithm

The goal of this section is to prove the algorithmic result in Lemma 6.4.
Given a colored graph $H$, we say that two vertices $u,v\in V(H)$ are similar
if they have the same color and they have the same open neighborhood, that is,
$N_{H}(u)=N_{H}(v)$. Note that if $u$ and $v$ are similar, then this means in
particular that they are not adjacent. Clearly, similarity is an equivalence
relation. We say that a partition $\Pi$ of $V(G)$ respects similarity if each
class of $\Pi$ consists of vertices similar to each other (but it is possible
that vertices in different classes are also similar).

We say that a colored graph $G$ is ordered if it is equipped with a total
order $<$ on its vertices, for example, the vertex set is $[n]$ for some
integer $n\geq 1$. Let $H$ and $G$ be two ordered graphs and let $\Pi$ be a
partition of $V(H)$. We say that a subgraph embedding $\phi:V(H)\to V(G)$ is
$\Pi$-ordered if whenever $u,v\in V(H)$ are in the same class and $u<v$ holds,
then we have $\phi(u)<\phi(v)$. We denote by $\textup{$\Pi$-OrdEmb}(H\to G)$
the number of $\Pi$-ordered embeddings from $H$ to $G$.

Observe that if $u$ and $v$ are similar vertices of $H$ and $\phi$ is a
subgraph embedding from $H$ to $G$, then the values of $\phi(u)$ and $\phi(v)$
can be exchanged and the resulting mapping is still a valid subgraph embedding
from $H$ to $G$. In fact, every subgraph embedding from $H$ to $G$ can be
obtained from a $\Pi$-ordered subgraph embedding by permuting the values of
$\phi$ inside each class of $\Pi$. Thus, as the following lemma states, the
number of embeddings can be recovered easily from the number of $\Pi$-ordered
subgraph embeddings.

######  Lemma 6.19.

Let $H$ and $G$ be two ordered graphs and let $\Pi=(P_{1},\dots,P_{p})$ be a
partition of $V(H)$ respecting similarity. Then we have

$\mathrm{Emb}(H\to G)=\textup{$\Pi$-OrdEmb}(H\to
G)\cdot\prod_{i=1}^{p}(|P_{i}|!).$

For an ordered graph $G$ and subset $S\subseteq V(G)$, we say that $S$ is
$\Pi$-prefix if whenever $u,v\in V(H)$ are in the same class of $\Pi$ with
$u<v$ and $v\in S$ holds, then $u\in S$ holds as well. If $\phi:V(H)\to V(G)$
is a $\Pi$-ordered subgraph embedding and $i$ is some vertex of $G$, then the
set $S_{\leq i}=\\{v\in V(H)\mid\phi(v)\leq i\\}$ of vertices that are mapped
to vertices of $G$ not greater than $i$ is a $\Pi$-prefix set.

###### Proof (of Lemma 6.4).

It will be convenient to assume that that the tree decomposition is tight:
every vertex of $\sigma(t)$ has a neighbor in $\alpha(t)$. As discussed in
Section 6.1.2, this can be achieved by easy transformations and these
transformations do not increase the size of the sets $\lambda(t)$. Then
$t^{\prime}\in h_{t}(v)$ is equivalent to $\sigma(t^{\prime})=g(t)\cup\\{v\\}$
(if the decomposition is not tight, then $\sigma(t^{\prime})=g(t)\cup\\{v\\}$
is possible even if $v$ is not adjacent to any vertex of $\alpha(t^{\prime})$
and hence $t^{\prime}\not\in h_{t}(v)$).

Let us define a partition $\Pi$ of $V(H)$ the following way. For every $t\in
V(T)$, we partition $\beta(t)\setminus(g(t)\cup\lambda(t))$ according to
similarity and let each such class be a class of $\Pi$ (by Lemma 6.5(1), these
classes are disjoint). If a vertex does not appear in any of these classes,
then let it appear in a singleton class of $\Pi$. Observe that $\Pi$ respects
similarity. We present an algorithm for computing $\textup{$\Pi$-OrdEmb}(H\to
G)$. Then Lemma 6.19 can be used to compute $\mathrm{Emb}(H\to G)$.

The algorithm uses two layers of dynamic programming: the outer dynamic
programming procedure uses the standard method of considering the nodes of the
tree decomposition in a bottom-up order, and additionally there is an inner
dynamic programming procedure at each node $t$, which restricts, for
increasing values of $i$, that the vertices of $\beta(t)\setminus g(t)$ can be
mapped only to the first $i$ vertices.

The outer dynamic programming. For a node $t\in V(T)$, let
$H_{t}=H[\gamma(t)]$. For a set $S\subseteq V(H)$, let $\mathcal{F}_{S}$ be
the set of all injective mappings from $S$ to $V(G)$. The goal of the outer
dynamic programming procedure is to compute, for every node $t\in V(T)$ and
function $f\in\mathcal{F}_{\sigma(t)}$, the size of the set

$\mathcal{W}_{t,f}=\\{\phi\in\textup{$\Pi$-OrdEmb}(H_{t}\to G):\text{$\phi$
restricted to $\sigma(t)$ is $f$}\\}.$

If $r$ is the root of $H$, then $H_{r}=H$ and $\sigma(r)=\emptyset$ holds,
hence $\textup{$\Pi$-OrdEmb}(H_{t}\to G)=\mathcal{W}_{t,f}$, where $f$ is the
unique empty function $\emptyset\to V(H)$. There is a slight abuse of notation
here: in $\textup{$\Pi$-OrdEmb}(H_{t}\to G)$, we would need to use the
restriction of $\Pi$ to $V_{t}$ instead of $\Pi$. However, observe that every
class of $\Pi$ is either contained in $V_{t}$ or disjoint from $V_{t}$, so
this does not create any ambiguity.

We compute the values in a bottom up way: when computing
$\\#\mathcal{W}_{t,f}$, we assume that
$\\#\mathcal{W}_{t^{\prime},f^{\prime}}$ is already available for every child
$t^{\prime}$ of $t$ and every $f\in\mathcal{F}_{\sigma(t^{\prime})}$. To
compute $\\#\mathcal{W}_{t,f}$, we solve a slightly more restricted problem:
we fix the value of the embedding not only on $\sigma(t)$, but on
$g(t)\supseteq\sigma(t)$. For every $t\in V(T)$ and
$\overline{f}\in\mathcal{F}_{g(t)}$, we define

$\overline{\mathcal{W}}_{t,\overline{f}}=\\{\phi\in\textup{$\Pi$-OrdEmb}(H_{t}\to
G):\text{$\phi$ restricted to $g(t)$ is $\overline{f}$}\\}.$

Clearly, we have
$\\#\mathcal{W}_{t,f}=\sum_{\overline{f}\in\mathcal{F}_{g(t)},\overline{f}_{|\sigma(t)}=f}\\#\overline{\mathcal{W}}_{t,\overline{f}}$,
thus computing the values $\\#\overline{\mathcal{W}}_{t,\overline{f}}$ is
sufficient to compute $\\#\mathcal{W}_{t,f}$.

The inner dynamic programming. The goal of the inner dynamic programming is to
compute $\\#\overline{\mathcal{W}}_{t,\overline{f}}$ for a given $t\in V(T)$
and $\overline{f}\in\mathcal{F}_{g(t)}$, assuming that the values
$\\#\mathcal{W}_{t^{\prime},f^{\prime}}$ are available for every child
$t^{\prime}$ of $t$ and $f^{\prime}\in\mathcal{F}_{\sigma(t^{\prime})}$. To
describe the subproblems of the inner dynamic programming, we need some
further definitions.

For any subset $g(t)\subseteq S\subseteq\beta(t)$, we define

$V_{t,S}:=S\cup\bigcup_{v\in S\setminus g(t)}\bigcup_{t^{\prime}\in
h_{t}(v)}\alpha(t^{\prime})=S\cup\bigcup_{\textup{$t^{\prime}$ is a child of
$t$, $\sigma(t^{\prime})\subseteq S$}}\alpha(t^{\prime})$

and $H_{t,S}:=H[V_{t,S}]$. That is, $V_{t,S}$ contains the subset $S$ of
$\beta(t)$, and those branches of the tree decomposition that are rooted at
some child $t^{\prime}$ of $t$ that is hanging at some vertex in $S$, or more
formally, $\sigma(t^{\prime})\subseteq S$. Here we use the assumption
$|\sigma(t^{\prime})\setminus g(t)|\leq 1$, which implies that
$\sigma(t^{\prime})\subseteq S$ is equivalent to $t^{\prime}\in h_{t}(v)$ for
some $v\in S$.

For every $t\in V(T)$, we define $\mathcal{S}_{t}$ to contain every subset $S$
with $g(t)\subseteq S\subseteq\beta(t)$ that is a $\Pi$-prefix subset of
$V(H)$. From the way we defined $\Pi$, it is clear that $\beta(t)$ itself is a
$\Pi$-prefix subset of $V(H)$, hence $\beta(t)\in\mathcal{S}_{t}$. It is not
difficult to bound the size of $\mathcal{S}_{t}$.

######  Claim 6.20.

For every $t\in V(T)$, we have $|\mathcal{S}_{t}|=2^{d}\cdot|V(G)|^{c\cdot
2^{c}}$ and the collection $\mathcal{S}_{t}$ can be constructed in time
$2^{O(d)}|V(G)|^{2^{O(c)}}$.

###### Proof.

The partition $\Pi$ classifies the vertices of
$\beta(t)\setminus(g(t)\cup\lambda(t))$ according to the similarity relation.
By Lemma 6.5(3), these vertices have at most $2^{|g(t)|}\leq 2^{c}$ possible
neighborhoods and they have $c$ possible colors, thus $\Pi$ partitions
$\beta(t)\setminus(g(t)\cup\lambda(t))$ into at most $c\cdot 2^{c}$ classes
$P_{1}$, $\dots$, $P_{s}$. If a $\Pi$-prefix set contains exactly $j$ vertices
of one such class $P_{i}$, then we know that it contains exactly the first $j$
vertices of $P_{i}$. Thus each set in $\mathcal{S}_{t}$ can be completely
specified by describing its intersection with $\lambda(t)$ and specifying the
size of its intersection with each $P_{i}$. As $|\lambda(t)|\leq d$ by
assumption, this gives $2^{d}\cdot n^{c\cdot 2^{c}}$ different possibilities.

We are now ready to define the subproblems of the inner dynamic programming.
For every $t\in V(T)$, $\overline{f}\in\mathcal{F}_{g(t)}$,
$S\in\mathcal{S}_{t}$, and $0\leq i\leq|V(G)|$, we define

$\\#\overline{\mathcal{W}}_{t,\overline{f},S,i}=\\{\phi\in\textup{$\Pi$-OrdEmb}(H_{t,S}\to
G):\text{$\phi$ restricted to $g(t)$ is $\overline{f}$ and $\phi(v)\leq i$ for
every $v\in\beta(t)\setminus g(t)$}\\}.$

That is, we need to map only $H_{t,S}$, but we have a restriction on where the
vertices of $\beta(t)\setminus g(t)$ can be mapped. As we have observed that
$\beta(t)\in\mathcal{S}_{t}$ holds, the value
$\\#\overline{\mathcal{W}}_{t,\overline{f},\beta(t),|V(G)|}$ is defined, and
it is equal to $\\#\overline{\mathcal{W}}_{t,\overline{f}}$.

Solving the subproblems. The inner dynamic programming proceeds by solving the
subproblems by increasing value of $i$: when computing
$\\#\overline{\mathcal{W}}_{t,\overline{f},S,i}$, we assume that that values
$\\#\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i^{\prime}}$ are
available for every $i^{\prime}<i$ and $S^{\prime}\in\mathcal{S}_{t}$.

For $i=0$, determining $\\#\overline{\mathcal{W}}_{t,\overline{f},S,i}$ is
trivial: its value is 1 if $S=g(t)$ and it is 0 if $S\supset g(t)$ (as then an
embedding would need to map a vertex of $S\setminus g(t)$ to the first $i=0$
vertices). For $i\geq 1$, consider vertex $i$ of $G$. If an embedding of
$\overline{\mathcal{W}}_{t,\overline{f},S,i}$ maps no vertex to $i$, or maps a
vertex not in $\beta(t)\setminus g(t)$ to $i$, then this embedding already
appears in $\overline{\mathcal{W}}_{t,\overline{f},S,i-1}$. In particular, if
$i\in\overline{f}(g(t))$, then every mapping of
$\overline{\mathcal{W}}_{t,\overline{f},S,i}$ maps a vertex of $g(t)$ to $i$,
hence we have
$\\#\overline{\mathcal{W}}_{t,\overline{f},S,i}=\\#\overline{\mathcal{W}}_{t,\overline{f},S,i-1}$.
Thus in the following, we can assume that $i\not\in\overline{f}(g(t))$. Let us
fix a vertex $v\in\beta(t)\setminus g(t)$ and count the number of embeddings
$\phi\in\overline{\mathcal{W}}_{t,\overline{f},S,i}$ that map $v$ to $i$;
summing these values for every $v\in\beta(t)\setminus g(t)$ and adding the
number $\\#\overline{\mathcal{W}}_{t,\overline{f},S,i-1}$ of embeddings that
do not map any vertex of $\beta(t)\setminus g(t)$ to $i$ gives exactly the
required value $\\#\overline{\mathcal{W}}_{t,\overline{f},S,i}$. We consider
two cases depending on whether $v$ is in $\lambda(t)$ or not.

Case 1. $v\not\in\lambda(t)$. There are three obvious conditions that are
necessary for the existence of embeddings in
$\overline{\mathcal{W}}_{t,\overline{f},S,i}$ that map $v$ to $i$.

  * •

Vertex $i$ needs to have the same color as $v$.

  * •

For every neighbor $u$ of $v$ in $H$ (note that $u$ has to be in $g(t)$ by
Lemma 6.5(3)), vertex $\overline{f}(u)$ should be a neighbor of $i$.

  * •

The set $S^{\prime}:=S\setminus\\{v\\}$ should be $\Pi$-prefix: as $S$ is
$\Pi$-prefix, the only way for $S^{\prime}$ to lose this property is if there
is a $u\in S^{\prime}$ with $v<u$ that is in the same class of $\Pi$ as $v$,
which in particular means that $u\in\beta(t)\setminus(g(t)\cup\lambda(t))$.
But then the $\Pi$-ordered embedding
$\phi\in\overline{\mathcal{W}}_{t,\overline{f},S,i}$ should map
$u\in\beta(t)\setminus g(t)$ to a vertex greater than $i$, which is not
possible by the definition of $\overline{\mathcal{W}}_{t,\overline{f},S,i}$.

We claim that if $v$ satisfies these three conditions, then any embedding of
$\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i-1}$ can be extended to an
embedding of $\overline{\mathcal{W}}_{t,\overline{f},S,i}$ by mapping $v$ to
$i$. The only subtle point here is that we need to argue that the embeddings
in $\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i-1}$ cannot already use
$i$: this is because every vertex of $H$ with same color as $i$ and $v$
appears in $\beta(t)$ (Lemma 6.5(2)), we assumed that $\overline{f}$ maps no
vertex of $g(t)$ to $i$, and an embedding in
$\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i-1}$ cannot map a vertex
of $\beta(t)\setminus g(t)$ to $i$ by definition. Thus we can conclude that if
the three conditions hold, the number of embeddings in
$\overline{\mathcal{W}}_{t,\overline{f},S,i}$ that map $v$ to $i$ is exactly
$\\#\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i-1}$.

Case 2. $v\in\lambda(t)$. Again, we have two obvious conditions:

  * •

Vertex $i$ needs to have the same color as $v$.

  * •

For very neighbor $u$ of $v$ in $H$ with $u\in g(t)$ (note that now $v$ can
have neighbors not in $g(t)$), vertex $\overline{f}(u)$ should be a neighbor
of $i$.

The set $S^{\prime}:=S\setminus\\{v\\}$ is always $\Pi$-prefix:
$v\in\lambda(t)$ implies that $v$ is in a singleton class of $\Pi$. Again, we
can argue that no embedding in
$\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i-1}$ can use vertex $i$ of
$G$. This means that any embedding $\psi:V_{t,S^{\prime}}\to V(G)$ appearing
in $\overline{\mathcal{W}}_{t,\overline{f},S,i}$ can be extended to an
embedding $\psi^{+}:V_{t,S^{\prime}}\cup\\{v\\}\to V(G)$ by setting
$\psi^{+}(v)=i$. However, $V_{t,S}$ contains more than just
$V_{t,S^{\prime}}\cup\\{v\\}$: it contains $\alpha(t^{\prime})$ for every
$t^{\prime}\in h_{t}(v)$. For any $t^{\prime}\in h_{t}(v)$, let
$f_{t^{\prime}}$ be the restriction of $\psi^{+}$ to $\sigma(t^{\prime})$. As
$\sigma(t^{\prime})\subseteq g(t)\cup\\{v\\}$ (by definition of $t^{\prime}\in
h_{t}(v)$), the function $f_{t^{\prime}}$ depends only on $\overline{f}$ and
on $i$. We have already computed the value
$\\#\mathcal{W}_{t^{\prime},f_{t^{\prime}}}$, which is the number of
extensions of $f_{t^{\prime}}$ to a embedding of $H_{t}$ to $G$. The crucial
observation is that an embedding
$\psi_{t^{\prime}}\in\mathcal{W}_{t^{\prime},f_{t^{\prime}}}$ cannot conflict
with $\psi^{+}$ in the sense that it is not possible that there is a vertex
$w\in V_{t,S^{\prime}}\cup\\{v\\}$ and a vertex
$w^{\prime}\in\alpha(t^{\prime})$ with
$\psi^{+}(w)=\psi_{t^{\prime}}(w^{\prime})$. This would be possible only if
$w$ and $w^{\prime}$ have the same color, that is, they are adjacent in
$H^{\textup{\textbullet}}$. But then $w^{\prime}\in\alpha(t^{\prime})$ would
imply $w\in\gamma(t^{\prime})$, which is only possible if
$w\in\sigma(t^{\prime})$. Mappings $\psi^{+}$ and $\psi_{t^{\prime}}$ agree on
$\sigma(t^{\prime})$ (as $f_{t^{\prime}}$ is the restriction of $\psi^{+}$ to
$\sigma(t^{\prime})$, while $\psi_{t^{\prime}}$ extends $f_{t^{\prime}}$),
hence $w\in\sigma(t^{\prime})$ cannot conflict with $w^{\prime}$. Thus any
$\psi_{t^{\prime}}\in\mathcal{W}_{t^{\prime},f_{t^{\prime}}}$ can be used to
extend $\psi^{+}$ to an embedding from
$H_{t,S^{\prime}}\cup\\{v\\}\cup\alpha(t^{\prime})$. Moreover, by the same
reasoning, if $t^{\prime},t^{\prime\prime}\in h_{t}(v)$ are two distinct
children of $t$, then two embeddings
$\psi_{t^{\prime}}\in\mathcal{W}_{t^{\prime},f_{t^{\prime}}}$ and
$\psi_{t^{\prime\prime}}\in\mathcal{W}_{t^{\prime\prime},f_{t^{\prime\prime}}}$
cannot conflict either: a vertex of $\alpha(t^{\prime})$ cannot have the same
color as a vertex of $\alpha(t^{\prime\prime})$. Therefore, if we pick any
combination of embeddings
$\psi_{t^{\prime}}\in\mathcal{W}_{t^{\prime},f_{t^{\prime}}}$ for each
$t^{\prime}\in h_{t}(v)$, then together they can be used to extend $\psi^{+}$
to an embedding of $H_{t,S}$. We can conclude that if the two conditions hold,
then the number of embeddings in $\overline{\mathcal{W}}_{t,\overline{f},S,i}$
that map $v$ to $i$ is exactly
$\\#\overline{\mathcal{W}}_{t,\overline{f},S,i-1}$ times the product of the
value $\\#\mathcal{W}_{t^{\prime},f_{t^{\prime}}}$ for every $t^{\prime}\in
h_{t}(v)$.

We have shown that $\\#\overline{\mathcal{W}}_{t,\overline{f},S,i}$ can be
computed in polynomial time, assuming we have already computed
$\\#\overline{\mathcal{W}}_{t,\overline{f},S^{\prime},i-1}$ for every
$S^{\prime}\in\mathcal{S}_{t}$, and $\\#\mathcal{W}_{t^{\prime},f^{\prime}}$
for every child $t^{\prime}$ of $t$ and mapping
$f^{\prime}\in\mathcal{F}_{\sigma(t^{\prime})}$. For a given $t$ and
$\overline{f}$, there are $2^{d}\cdot|V(G)|^{2^{O(c)}}$ values
$\\#\overline{\mathcal{W}}_{t,\overline{f}}$ compute (Claim 6.20) and solving
these subproblems allows us to compute
$\\#\overline{\mathcal{W}}_{t,\overline{f}}$, hence we can conclude that
$\\#\overline{\mathcal{W}}_{t,\overline{f}}$ can be computed in time
$2^{d}\cdot|V(G)|^{2^{O(c)}}$. For a given $t\in V(T)$, the number of
possibilities for $\overline{f}\in\mathcal{F}_{g(t)}$ is at most
$|V(G)|^{g(t)}\leq|V(G)|^{c}$, which means that the at most
$|V(H)|\cdot|V(G)|^{c}$ subproblems
$\\#\overline{\mathcal{W}}_{t,\overline{f}}$ can be all solved in total time
$2^{d}\cdot|V(G)|^{2^{O(c)}}$.

###  6.4 Putting it together

Finally, we are ready to prove the main result of the section, classifying
which of the FPT cases of counting colored patterns is polynomial-time
solvable. The result is under assuming the Nonuniform Counting Exponential
Time Hypothesis, which states that there is an $\epsilon>0$ such that there is
no infinite collection of algorithms $\\{A_{n}\mid n\in N\\}$ for some
infinite set $N\subseteq\mathbb{Z}^{+}$ such that algorihm $A_{n}$ solves
$n$-variable #3-SAT in time $2^{\epsilon n}$. By known reductions, we can
replace #3-SAT with counting perfect matchings in an $n+n$ vertex bipartite
graph [16].

######  Theorem 6.21.

Let $\mathcal{H}$ be a class of colored graph where, for every
$H\in\mathcal{H}$, the graphs in $\mathrm{Spasm}\left\lparen H\right\rparen$
have treewidth at most $c$.

  1. 1.

If there is a constant $h$ such that the largest half-colorful matching in
every $H\in\mathcal{H}$ is at most $h\log|V(H)|$, then
$\mathsf{\\#Sub}(\mathcal{H})$ is polynomial-time solvable.

  2. 2.

Otherwise, $\mathsf{\\#Sub}(\mathcal{H})$ is not polynomial-time solvable,
unless the Nonuniform Counting Exponential Time Hypothesis.

###### Proof.

Suppose that the first statement holds. Consider an instance of
$\mathsf{\\#Sub}(()\mathcal{H})$ with inputs $H$ and $G$. By Theorem 6.2,
there is a constant $c^{\prime}$ such that $\widehat{H}$ has treewidth at most
$c^{\prime}$ and there is no $c^{\prime}$-flower centered at any color class
of $H$. Thus by Theorem 6.3, there is a constant $c^{\prime\prime}$ such that
we can obtain in polynomial time a guarded cutvertex decomposition with guard
size $c^{\prime\prime}$ and at most $c^{\prime\prime}$ colors in each bag. If
$\lambda(t)=k$ for some node $t$ of the decomposition, then Lemma 6.16 implies
that there is a half-colorful matching of size $k/(c^{\prime\prime})^{2}-1$ in
$H$. Thus the assumption that there is no such matching larger than
$h\log|V(H)|$ implies that $\lambda(t)=O(h(c^{\prime\prime})^{2}\log|V(H)|)$.
It follows that the running time of the algorithm of Lemma 6.4 is
$|V(H)|^{h(c^{\prime\prime})^{2}}|V(H)|^{2^{O(c^{\prime\prime})}}$, which is
polynomial time for fixed constants $h$ and $c^{\prime\prime}$.

For the second statement, suppose that there is no such $h$. From the
assumption that $\mathrm{Spasm}\left\lparen H\right\rparen$ has treewidth at
most $c$ and Theorem 6.2, there is a constant $c^{\prime}$ such that there is
no $c^{\prime}$-flower in $H$. Let us fix any $\epsilon>0$. By assumption,
there are infinitely many graphs $H\in\mathcal{H}$ where the size of the
largest half-colorful matching is at least $(1/\epsilon)\log|V(H)|$. For every
$n\geq 1$, if there is such a graph where the size of the largest half-
colorful matching is exactly $n+3c^{\prime}$, then let us fix such a graph
$H_{n}$. Note that $n\geq(1/\epsilon)\log|V(H)|$ means $|V(H)|\leq 2^{\epsilon
n}$. Lemma 6.17 shows that there is a half-colorful matching of size $n$
satisfying certain conditions and then Lemma 6.18 can be used to reduce
counting perfect matchings in an $n+n$ vertex bipartite graph to
$\mathsf{\\#Sub}(\mathcal{H})$ and use the assumed polynomial-time algorithm.
This way, $A_{n}$ solves the problem of counting perfect matchings in time
$(2^{\epsilon n})^{O(1)}$. As we can construct such an infinite sequence of
algorithms for any $\epsilon>0$, our complexity assumption fails.

##  7 Open Problems

We have defined the space of graph motif parameters and explored three useful
bases thereof, namely, $\operatorname{Hom}$, $\operatorname{Sub}$, and
$\operatorname{IndSub}$. These bases capture well-studied classes of counting
problems, and we could use basis changes to transfer results between these
classes. Are there other computationally interesting bases? Moreover, are
there other interesting subspaces of the space of all graph parameters other
than the graph motif parameters?

## Acknowledgments

Thanks a lot to Édouard Bonnet for pointing out [52] and [22].

## References

  * [1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams.  If the current clique algorithms are optimal, so is Valiant’s parser.  In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 98–117, 2015.  doi:10.1109/FOCS.2015.16.
  * [2] Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp.  Biomolecular network motif counting and discovery by color coding.  Bioinformatics, 24(13):i241–i249, 2008.  doi:10.1093/bioinformatics/btn163.
  * [3] Noga Alon, Raphael Yuster, and Uri Zwick.  Finding and counting given length cycles.  Algorithmica, 17(3):209–223, 1997.  doi:10.1007/BFb0049422.
  * [4] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.  Counting paths and packings in halves.  In Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pages 578–586, 2009.  doi:10.1007/978-3-642-04128-0_52.
  * [5] Andreas Björklund, Petteri Kaski, and Lukasz Kowalik.  Counting thin subgraphs via packings faster than meet-in-the-middle time.  In Proceedings of the 25th Annual Symposium on Discrete Algorithms (SODA), pages 594–603, 2014.  doi:10.1137/1.9781611973402.45.
  * [6] Markus Bläser and Radu Curticapean.  Weighted counting of k-matchings is #W[1]-hard.  In Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC), pages 171–181, 2012.  doi:10.1007/978-3-642-33293-7_17.
  * [7] Hans L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM Journal on Computing, 25(6):1305–1317, 1996.  doi:10.1137/S0097539793251219.
  * [8] Christian Borgs, Jennifer Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi.  Counting graph homomorphisms.  In Topics in discrete mathematics, pages 315–371. Springer, 2006\.  doi:10.1007/3-540-33700-8_18.
  * [9] Cornelius Brand and Marc Roth.  Parameterized counting of trees, forests and matroid bases.  In Proceedings of the 12th International Computer Science Symposium in Russia (CSR), 2017 (to appear).  URL: https://arxiv.org/abs/1611.01823.
  * [10] Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia.  Tight lower bounds for certain parameterized NP-hard problems.  Information and Computation, 201(2):216–231, 2005.  doi:10.1016/j.ic.2005.05.001.
  * [11] Jin Chen, Wynne Hsu, Mong Li Lee, and See-Kiong Ng.  Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 106–115. ACM, 2006.  doi:10.1145/1150402.1150418.
  * [12] Yijia Chen, Martin Grohe, and Bingkai Lin.  The hardness of embedding grids and walls.  arXiv preprint arXiv:1703.06423, 2017.  URL: http://arxiv.org/abs/1703.06423.
  * [13] Yijia Chen, Marc Thurley, and Mark Weyer.  Understanding the complexity of induced subgraph isomorphisms.  In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pages 587–596, 2008.  doi:10.1007/978-3-540-70575-8_48.
  * [14] Stephen A. Cook.  The complexity of theorem-proving procedures.  In Proceedings of the 3rd Annual Symposium on Theory of Computing (STOC), pages 151–158, 1971.  doi:10.1145/800157.805047.
  * [15] Radu Curticapean.  Counting matchings of size k is W[1]-hard.  In Proceedings of the 40th International Conference on Automata, Languages, and Programming (ICALP), pages 352–363, 2013.  doi:10.1007/978-3-642-39206-1_30.
  * [16] Radu Curticapean.  Block interpolation: A framework for tight exponential-time counting complexity.  In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 380–392, 2015.  doi:10.1007/978-3-662-47672-7_31.
  * [17] Radu Curticapean and Dániel Marx.  Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts.  In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 130–139, 2014.  doi:10.1109/FOCS.2014.22.
  * [18] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [19] Víctor Dalmau and Peter Jonsson.  The complexity of counting homomorphisms seen from the other side.  Theoretical Computer Science, 329(1):315–323, 2004.  doi:10.1016/j.tcs.2004.08.008.
  * [20] Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén.  Exponential time complexity of the permanent and the Tutte polynomial.  ACM Transactions on Algorithms, 10(4):21:1–21:32, 2014.  doi:10.1145/2635812.
  * [21] Josep Díaz, Maria J. Serna, and Dimitrios M. Thilikos.  Counting H-colorings of partial k-trees.  Theoretical Computer Science, 281(1-2):291–309, 2002.  doi:10.1016/S0304-3975(02)00017-8.
  * [22] Zdeněk Dvořák and Sergey Norin.  Strongly sublinear separators and polynomial expansion.  SIAM Journal on Discrete Mathematics, 30(2):1095–1101, 2016.  doi:10.1137/15M1017569.
  * [23] Friedrich Eisenbrand and Fabrizio Grandoni.  On the complexity of fixed parameter clique and dominating set.  Theoretical Computer Science, 326(1):57–67, 2004.  doi:10.1016/j.tcs.2004.05.009.
  * [24] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006.
  * [25] Fedor V. Fomin and Yngve Villanger.  Treewidth computation and extremal combinatorics.  Combinatorica, 32(3):289–308, 2012.  doi:10.1007/s00493-012-2536-z.
  * [26] François Le Gall.  Powers of tensors and fast matrix multiplication.  In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296–303, 2014.  doi:10.1145/2608628.2608664.
  * [27] Joshua A Grochow and Manolis Kellis.  Network motif discovery using subgraph enumeration and symmetry-breaking.  In Annual International Conference on Research in Computational Molecular Biology, pages 92–106. Springer, 2007.  doi:10.1007/978-3-540-71681-5_7.
  * [28] Martin Grohe.  Descriptive complexity, canonisation, and definable graph structure theory.  Manuscript.  URL: http://www.lii.rwth-aachen.de/de/mitarbeiter/13-mitarbeiter/professoren/39-book-descriptive-complexity.html.
  * [29] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  Journal of the ACM, 54(1):1:1–1:24, 2007.  doi:10.1145/1206035.1206036.
  * [30] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of $k$-SAT.  Journal of Computer and System Sciences, 62(2):367–375, 2001.  doi:10.1006/jcss.2000.1727.
  * [31] Alon Itai and Michael Rodeh.  Finding a minimum circuit in a graph.  SIAM Journal on Computing, 7(4):413–423, 1978.  doi:10.1137/0207033.
  * [32] Bart M. P. Jansen and Dániel Marx.  Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels.  In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 616–629, 2015.  doi:10.1137/1.9781611973730.42.
  * [33] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting connected subgraphs and graph motifs.  Journal of Computer and System Sciences, 81(4):702–716, 2015.  doi:10.1016/j.jcss.2014.11.015.
  * [34] Mark Jerrum and Kitty Meeks.  Some hard families of parameterized counting problems.  ACM Transactions on Computation Theory, 7(3):11, 2015.  doi:10.1145/2786017.
  * [35] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting even and odd induced subgraphs.  Combinatorica, pages 1–26, 2016.  doi:10.1007/s00493-016-3338-5.
  * [36] Zahra Razaghi Moghadam Kashani, Hayedeh Ahrabian, Elahe Elahi, Abbas Nowzari-Dalini, Elnaz Saberi Ansari, Sahar Asadi, Shahin Mohammadi, Falk Schreiber, and Ali Masoudi-Nejad.  Kavosh: A new algorithm for finding network motifs.  BMC bioinformatics, 10(1):318, 2009.  doi:10.1186/1471-2105-10-318.
  * [37] Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon.  Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs.  Bioinformatics, 20(11):1746–1758, 2004.  doi:10.1093/bioinformatics/bth163.
  * [38] Ton Kloks, Dieter Kratsch, and Haiko Müller.  Finding and counting small induced subgraphs efficiently.  Information Processing Letters, 74(3):115–121, 2000.  doi:10.1016/S0020-0190(00)00047-8.
  * [39] Ioannis Koutis and Ryan Williams.  LIMITS and applications of group algebras for parameterized problems.  ACM Transactions on Algorithms, 12(3):31:1–31:18, 2016.  doi:10.1145/2885499.
  * [40] Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell.  Counting and detecting small subgraphs via equations.  SIAM Journal on Discrete Mathematics, 27(2):892–909, 2013.  doi:10.1137/110859798.
  * [41] Bingkai Lin.  The parameterized complexity of _k_ -biclique.  In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 605–615, 2015.  doi:10.1137/1.9781611973730.41.
  * [42] László Lovász.  Operations with structures.  Acta Mathematica Hungarica, 18(3-4):321–328, 1967.
  * [43] László Lovász.  Large networks and graph limits, volume 60.  American Mathematical Society Providence, 2012.
  * [44] Dániel Marx.  Can you beat treewidth?  Theory of Computing, 6(1):85–112, 2010.  doi:10.4086/toc.2010.v006a005.
  * [45] Kitty Meeks.  The challenges of unbounded treewidth in parameterised subgraph counting problems.  Discrete Applied Mathematics, 198:170–194, 2016.  doi:10.1016/j.dam.2015.06.019.
  * [46] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon.  Network motifs: Simple building blocks of complex networks.  Science, 298(5594):824–827, 2002.  arXiv:http://science.sciencemag.org/content/298/5594/824.full.pdf, doi:10.1126/science.298.5594.824.
  * [47] Jaroslav Nešetřil and Svatopluk Poljak.  On the complexity of the subgraph problem.  Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.
  * [48] Rolf Niedermeier.  Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications.  Oxford University Press, Oxford, 2006.
  * [49] Saeed Omidi, Falk Schreiber, and Ali Masoudi-Nejad.  MODA: An efficient algorithm for network motif discovery in biological networks.  Genes & genetic systems, 84(5):385–395, 2009.  doi:10.1266/ggs.84.385.
  * [50] Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe.  Stream - A stream-based algorithm for counting motifs in dynamic graphs.  In Proceedings of the 2nd International Conference on Algorithms for Computational Biology (AlCoB), pages 53–67, 2015.  doi:10.1007/978-3-319-21233-3_5.
  * [51] Falk Schreiber and Henning Schwöbbermeyer.  Frequency concepts and pattern detection for the analysis of motifs in networks.  In Transactions on computational systems biology III, pages 89–104. Springer, 2005.  doi:10.1007/11599128_7.
  * [52] Alexander D. Scott and Gregory B. Sorkin.  Linear-programming design and analysis of fast algorithms for Max 2-CSP.  Discrete Optimization, 4(3-4):260–287, 2007.  doi:10.1016/j.disopt.2007.08.001.
  * [53] Julian R. Ullmann.  An algorithm for subgraph isomorphism.  Journal of the ACM, 23(1):31–42, 1976.  doi:10.1145/321921.321925.
  * [54] Leslie G. Valiant.  The complexity of computing the permanent.  Theoretical Computer Science, 8(2):189–201, 1979.  doi:10.1016/0304-3975(79)90044-6.
  * [55] Sebastian Wernicke.  Efficient detection of network motifs.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4), 2006.  doi:10.1109/TCBB.2006.51.
  * [56] Virginia Vassilevska Williams.  Multiplying matrices faster than Coppersmith-Winograd.  In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), pages 887–898, 2012.  doi:10.1145/2213977.2214056.
  * [57] Virginia Vassilevska Williams and Ryan Williams.  Subcubic equivalences between path, matrix and triangle problems.  In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 645–654, 2010.  doi:10.1109/FOCS.2010.67.
  * [58] Virginia Vassilevska Williams and Ryan Williams.  Finding, minimizing, and counting weighted subgraphs.  SIAM Journal on Computing, 42(3):831–854, 2013.  doi:10.1137/09076619X.

##  Appendix A Appendix

In this section, we provide those proofs that we chose not to include in the
main text.

###### Proof of Proposition 1.6.

We begin by computing an optimal tree decomposition $(T,\beta)$ of $H$, for
example via the $O(1.7549^{\lvert V(F)\rvert})$ time exact algorithm by Fomin
and Villanger [25]. Without loss of generality, we assume it to be a _nice_
tree decomposition, in which each node has at most two children; the leaves
satisfy $\beta(v)=\emptyset$, the nodes with two children $w,w^{\prime}$
satisfy $\beta(v)=\beta(w)=\beta(w^{\prime})$ and called _join_ nodes, the
nodes with one child $w$ satisfy $\beta(v)=\beta(w)\cup\\{x\\}$ and called
_introduce_ nodes, or $\beta(v)\cup\\{x\\}=\beta(w)$ and called _forget_
nodes.

Recall that $\alpha(v)$ be the union of all bags at or below vertex $v$ in the
tree $T$. The goal of the dynamic programming algorithm is to build up the
following information $I_{v}$ at each vertex $v$ of $T$: For each
$h\in\mathrm{Hom}(H[\beta(v)]\to G)$, we let $I_{v}(h)$ be the number of
homomorphisms $\bar{h}\in\mathrm{Hom}(H[\alpha(v)]\to G)$ such that $\bar{h}$
extends $h$. We observe some properties of $I_{v}$.

Let $v$ be a leaf of $T$. Then $\beta(v)=\emptyset$ and we define $I_{v}(h)=1$
for the empty function $h$. For each leaf $v$, we can set up the dynamic
programming table entry $I_{v}$ in constant time.

Let $v$ be an _introduce_ vertex of $T$. Let $w$ be its unique child in the
tree. Suppose the vertex $x\in V(G)$ is introduced at this node, that is,
$\beta(w)\cup\\{x\\}=\beta(v)$. Let $h\in\mathrm{Hom}(H[\beta(v)]\to G)$, and
let $h^{\prime}$ be $h$ with $x$ removed from its domain. Then
$I_{v}(h)=I_{w}(h^{\prime})$ holds because
$N_{H}(x)\cap\alpha(v)=N_{H}(x)\cap\beta(v)$. Thus at introduce vertices, we
can compute $I_{v}$ from the table $I_{w}$ by going over all table entries $h$
(there are at most $|V(G)|^{|\beta(v)|}\leq|V(G)|^{\mathrm{tw}(H)+1}$ of them)
and writing the value $I_{w}(h^{\prime})$ to $I_{v}(h)$.

Let $v$ be a _forget_ vertex of $T$. Let $w$ be its unique child in the tree.
Suppose the vertex $x\in V(G)$ is forgotten at this node, that is,
$\beta(w)\setminus\\{x\\}=\beta(v)$. Then the neighborhood of $x$ is contained
in $\alpha(w)$. Let $h\in\mathrm{Hom}(H[\beta(v)]\to G)$. For each $z\in
V(G)$, let $h_{z}:\beta(w)\to V(G)$ be the unique function that is consistent
with $h$ and satisfies $h(x)=z$. Then we have

$I_{v}(h)=\sum_{z\in V(G)}\Big{[}h_{z}\in\mathrm{Hom}(H[\beta(w)]\to
G)\Big{]}\cdot I_{w}(h_{z})\,.$

For each of the at most
$|V(G)|^{|\beta(v)|}=|V(G)|^{|\beta(w)|-1}\leq|V(G)|^{\mathrm{tw}(H)}$
functions $h$, we compute $I_{v}(h)$ as follows: first we determine the set
$Z$ of all $z$ for which $h_{z}$ is a homomorphisms, and then we sum up the
corresponding entries $I_{w}(h_{z})$. Let $N(x)$ be the open neighborhood of
$x$ in $H$, and let $N^{\prime}$ be the image of $N(x)\cap\beta(v)$ under $h$.
Then the set $Z$ is the set of all vertices $z$ that are adjacent to all
vertices in $N^{\prime}$. Clearly $N^{\prime}$ has at most
$|\beta(v)|\leq\mathrm{tw}(H)$ elements. Thus $Z=\bigcap_{y\in
N^{\prime}}N_{G}(y)$ holds, and we can compute this intersection in time
$\tilde{O}(\mathrm{tw}(H)\cdot|V(G)|)$. The running time for forget vertices
is therefore $\tilde{O}(\mathrm{tw}(H)\cdot|V(G)|^{\mathrm{tw}(H)+1})$

Let $v$ be a _join_ vertex of $T$, that is, it has exactly two children $w$
and $w^{\prime}$ with $\beta(v)=\beta(w)=\beta(w^{\prime})$. Let
$h\in\mathrm{Hom}(H[\beta(v)]\to G)$. Then $I_{v}(h)=I_{w}(h)\cdot
I_{w^{\prime}}(h)$. This operation can be computed in time
$|V(G)|^{|\beta(v)|}\leq|V(G)|^{\mathrm{tw}(H)+1}$.

To prove Proposition 1.9, we state a vertex-colorful version of the subgraph
counting problem. For two graphs $F$ and $G$, we say that $G$ is $F$-colored
graph if there is a homomorphism $f\in\mathrm{Hom}(G\to F)$ from $G$ to $F$.
Let $\mathrm{PartitionedSub}(F\to G)$ be the set of all subgraphs $H$ of $G$
that are isomorphic to $F$ and _vertex-colorful_ , that is, these subgraphs
$H$ satisfy $\lvert f^{-1}(v)\cap V(H)\rvert=1$ for all $v\in V(F)$. In the
problem $\mathsf{\\#PartitionedSub}(\mathcal{F})$ for a fixed graph class
$\mathcal{F}$, we are given a graph $F\in\mathcal{F}$ and an $F$-colored graph
$G$, and we are asked to compute the number $\\#\mathrm{PartitionedSub}(F\to
G)$. A full dichotomy for this class of problems is known, and it establishes
treewidth as the tractability criterion, together with near-tight lower bounds
under $\mathsf{\\#ETH}$.

######  Theorem A.1 (Corollary 6.2 and 6.3 of [44]).

Let $\mathcal{F}$ be a recursively enumerable family of graphs such that the
treewidth of graphs in $\mathcal{F}$ is unbounded. If $\mathsf{\\#ETH}$ is
true, the problem $\mathsf{\\#PartitionedSub}(\mathcal{F})$ cannot be solved
in time $f(H)\cdot n^{o(\mathrm{tw}(H)/\log\mathrm{tw}(H))}$ for patterns
$H\in\mathcal{F}$ of treewidth $\mathrm{tw}(H)$.

We are ready to prove the following proposition.

###### Proposition 1.9, restated..

Let $\mathcal{F}$ be a recursively enumerable class of graphs of unbounded
treewidth. If $\mathsf{\\#ETH}$ holds, there is no $f(H)\cdot\lvert
V(G)\rvert^{o(\mathrm{tw}(H)/\log\mathrm{tw}(H))}$ time algorithm to compute
$\mathsf{\\#Hom}(\mathcal{F})$ for given graphs $H\in\mathcal{F}$ and $G$.

###### Proof.

We reduce from $\mathsf{\\#PartitionedSub}(\mathcal{F})$ to
$\mathsf{\\#Hom}(\mathcal{F})$. Given an instance $(H,G,f)$ with graphs
$H\in\mathcal{F}$ and $G$ and a given homomorphism $f\in\mathrm{Hom}(G\to F)$,
the reduction wants to compute $\mathrm{PartitionedSub}(H\to G)$. The
reduction uses a straightforward inclusion–exclusion argument. For a set
$A\subseteq V(H)$, let $G_{-A}$ be the graph obtained from $G$ by deleting all
vertices $v\in V(G)$ with $f(v)\in A$. Then the set $\mathrm{Hom}(H\to
G)\setminus\bigcup_{\emptyset\neq A\subseteq V(H)}\mathrm{Hom}(H\to G_{-A})$
contains all homomorphisms $h\in\mathrm{Hom}(H\to G)$ that are color-
preserving, that is, they map each vertex $v\in V(H)$ to a vertex $h(v)\in
V(G)$ with the property that $f(h(v))=v$. In particular, these homomorphisms
are injective. By the principle of inclusion and exclusion, their number is
equal to

$\sum_{\emptyset\neq A\subseteq V(H)}(-1)^{\lvert
A\rvert}\cdot\\#\mathrm{Hom}(H\to G_{-A})\,.$

Dividing by $\\#\mathrm{Aut}(H)$ yields the number of vertex-colorful
$H$-copies in $G$ as required.