# Auctioning Multiple Goods without Priors

Wanchang Zhang Department of Economics, University of California, San Diego.
Email<EMAIL_ADDRESS>I am indebted to Songzi Du and Joel Sobel for
stimulating discussions. I thank Denis Shishkin and Emanuel Vespa for helpful
comments.

(Current Draft: April 2022
First Draft: October 2021)

###### Abstract

I consider a mechanism design problem of selling multiple goods to multiple
bidders when the designer has minimal amount of information. I assume that the
designer only knows the upper bounds of bidders’ values for each good and has
no additional distributional information. The designer takes a minimax regret
approach. The expected regret from a mechanism given a joint distribution over
value profiles and an equilibrium is defined as the difference between the
full surplus and the expected revenue. The designer seeks a mechanism,
referred to as a minimax regret mechanism, that minimizes her worst-case
expected regret across all possible joint distributions over value profiles
and all equilibria. I find that a separate second-price auction with random
reserves is a minimax regret mechanism for general upper bounds. Under this
mechanism, the designer holds a separate auction for each good; the formats of
these auctions are second-price auctions with random reserves.
Keywords: Minimax regret, robust mechanism design, multiple goods, separate
second-price auctions, random reserves.
JEL Codes: C72, D44, D82.

##  1 Introduction

The standard auction literature focuses on the single-good environment and
assumes that bidders’ value profile follows a commonly known joint
distribution. It is assumed that the designer seeks a mechanism that maximizes
the expected revenue. Myerson, (1981) characterizes optimal mechanisms for
selling a single good when bidders’ values are independent; Crémer and McLean,
(1988) characterize optimal mechanisms for selling a single good given generic
correlation structures of bidders’ values. However, optimal mechanisms vary
widely with the model of correlation structure and relatively little is known
about how optimal mechanisms would perform once the correlation structure is
misspecified. In addition, it is not clear how the designer should form a
prior in the first place.
In this paper, I am going to extend the analysis in two ways. First, I
consider the multiple-good environment, in which little is known about the
optimal mechanisms. Even for the special case where there is only one bidder,
the optimal mechanism is hard to characterize or to describe (Daskalakis et
al., (2014) and Manelli and Vincent, (2007)). Second, I consider a robust
version of the analysis. Specifically, I consider a (correlated) private value
model where the designer auctioning multiple different goods knows no
distributional information except for the upper bounds of bidders’ values for
each good. In contrast, bidders agree on a joint distribution over their value
profiles111In the Appendix, I show that the main result still holds when
bidders can acquire additional information.. The designer considers any joint
distribution consistent with the known upper bounds to be possible. I consider
general mechanisms with the only requirement that the mechanism “secures”
bidders’ participation: there exists a message for each payoff type of each
bidder that guarantees a non-negative ex-post payoff regardless of the other
bidders’ messages. I assume that the designer takes the minimax regret
approach. Precisely, the expected regret from a mechanism given a joint
distribution over value profiles and a Bayesian equilibrium is defined as the
difference between the full surplus222The full surplus under a joint
distribution over value profiles is the expected revenue attainable were the
designer able to sell the goods with full information about bidders’ value
profile. and the expected revenue. The designer evaluates a mechanism by its
highest expected regret across all possible joint distributions and all
Bayesian equilibria, which is referred to as its regret cap. The designer aims
to find a mechanism, referred to as a minimax regret mechanism, that minimizes
the regret cap.
The assumption that the designer only knows the upper bounds is appropriate
for situations where little information is known about the bidders and it is
costly and time-consuming to collect information. For example, in an auction
of initial public offerings, there is no distributional information about the
bidders’ values. Note that in this example, bidders’ budgets, which can be
viewed as (reasonable approximations of) the upper bounds of bidders’ values,
are typically known by the designer, as bidders for initial public offerings
are often institutional investors, whose financial resources are publicly
known, or can be estimated fairly precisely from their financial reports. On
the contrary, the assumption may be too conservative for situations in which
data about bidders are abundant, e.g., online advertising in which auctions
are held repeatedly and frequently. In addition, the assumption is formally
necessary to obtain non-trivial results because if there is no known upper
bound, then minimax regret will be infinite 333See Remark 5 for the formal
proof.. Thus, this model can be viewed as a theoretical benchmark that
provides a first step toward a broad study of robust auction design problems
in the multiple-good environment.
The minimax regret approach can be traced back to Wald, (1950) and Savage,
(1951). It captures the idea that a decision maker is concerned about missing
out opportunities. A decision theoretical axiomatization of regret can be
found in Milnor, (1951) and Stoye, (2011). It is adapted to multiple priors by
Hayashi, (2008) and Stoye, (2011). Another leading approach is the maxmin
utility approach, which is adopted by most of the robust mechanism design
literature. However, in the setting of this paper, under the maxmin utility
approach, it is optimal for the designer to keep all goods to herself because
it is possible that all bidders have zero values towards all goods. Note that
in this extreme case, there is no surplus to extract even under complete
information. Thus, the maxmin utility approach is too conservative to be
useful, whereas the minimax regret approach protects the surplus when there is
some surplus to extract and will be shown to lead to a non-trivial answer.
The main result is that a separate second-price auction with random reserves
is a minimax regret mechanism. This mechanism can be described as follows. For
each good, the designer holds a separate auction; the formats of these
auctions are second-price auctions with bidder-specific random reserves that
depend on the upper bounds of values444The distributions of these random
reserves are given in the Section 4.1. . It is remarkable that a simple
mechanism arises as a robustly optimal mechanism for auctioning multiple
goods, across all participation-securing mechanisms that include highly
complicated mechanisms, e.g., combinatorial auctions555In a combinatorial
auction, bidders can place bids on combinations of discrete heterogeneous
goods..
Importantly, I allow for general upper bounds of values for the main result.
In particular, the upper bounds of the values for a given good can be
different across bidders. This captures the widely observed asymmetries in
many real-life auction environments. For example, in art auctions, there are
obvious asymmetries associated with differing budget constraints across
bidders. Asymmetric auctions have been studied in Maskin and Riley, (2000),
Hafalir and Krishna, (2008),Güth et al., (2005) and Athey et al., (2013) among
others.
The main result provides a possible explanation why separate second-price
auctions - or their more practical equivalents in the private value
environment, separate English auctions - are widely used in practice for
auctioning multiple goods. For example, at the popular online auction site
eBay, each good is typically auctioned separately via an English auction
(Krishna, (2009), Anwar et al., (2006) and Feldman et al., (2020)); Sotheby’s
and Christie’s (two major auction houses of art) typically sell works of art
separately via an English auction (Ashenfelter and Graddy, (2003)).666In
practice, there are other mechanisms used for auctioning multiple goods. While
most of spectrum auctions in US do not allow for “package bidding” due to its
complexities (Cramton et al., (2002) and Filiz-Ozbay et al., (2015)), the
Federal Communications Commission (FCC) has used a “package bidding auction”
to sell spectrum licenses in rare cases. In such an auction, a bidder is
allowed to select a group of licenses to bid on as a package. In an early 2008
FCC auction (Auction 73), AT&T and Verizon both bought geographically diverse
packages of 700MHz spectrum. The principal rationale to consider a package
bidding auction is that there may be complementarity between different
licenses (Goeree and Holt, (2005)). Complementarity is ruled out in my model.
It is an interesting open question what the minimax regret mechanism would be
like when there is complementarity between goods. The main result justifies
this empirical rule of thumb by an optimal performance guarantee: a separate
second-price auction (albeit with random reserves) minimizes the worst-case
expected regret. This may be one reason why complicated mechanisms that
require the full information of the joint distribution over bidders’ value
profiles, to my knowledge, are not used in practice for auctioning multiple
goods.
The role of randomized reserves can be seen considering the one-good one-
bidder case, in which they are reduced to randomized pricing. The designer
suffers from a large regret if she charges a high price when the value of the
bidder is low or if she charges a low price when the value of the bidder is
high. She can lower her regret by randomizing. Bergemann and Schlag, (2008)
characterize the solution for the one-good one-bidder case. Indeed, the well-
crafted distribution of the randomized pricing renders the designer
indifferent across values over a range. The second-price auction with random
reserves extends the robust property to the one-good multiple-bidder case. In
this case, the regret from a value profile is the difference between the
highest value and the collected revenue. When the second highest value is low
enough (e.g., 0), it boils down to the one-good one-bidder case and the regret
remains the same; when the second highest value is high enough (e.g., above
the lower bound of the random reserve for the highest bidder), then the
revenue is even higher and the regret is thus lower. To see the intuition
behind separation, it is instructive to consider another mechanism of
auctioning the grand bundle (only the bundle of all goods is auctioned). I
argue that this mechanism may result in a high regret. Consider a three-good
three-bidder example and an extremely asymmetric value profile in which each
bidder values a different good (assuming that the upper bound on each bidder’s
values for each good is 1) :
$(v_{1}^{1},v_{1}^{2},v_{1}^{3})=(1,0,0),(v_{2}^{1},v_{2}^{2},v_{2}^{3})=(0,1,0),(v_{3}^{1},v_{3}^{2},v_{3}^{3})=(0,0,1)$.777The
superscript represents the good, and the subscript represents the bidder. The
designer will lose all but one good if auctioning the grand bundle: she can at
most obtain a revenue of 1 from one of the goods but will suffer a regret of 2
from losing the other goods. In contrast, separation can guarantee a good
regret performance for each good. It can be shown that for this example, the
separate second-price auction with random reserves yields a regret
cap888Indeed, it can be shown that the regret cap is $\frac{3}{e}$ by simple
calculation. lower than 2. Intuitively, auctioning the grand bundle performs
just like selling one good at this value profile, while selling separately
allows the designer to earn more. Furthermore, the same argument implies that
partial bundling (a mechanism in which a bundle of some goods are auctioned)
may perform worse than separate selling.
I show that the separate second-price auction with random reserves is a
minimax regret mechanism by constructing a joint distribution over value
profiles, referred to as a worst-case distribution, such that the lower bound
of the expected regret for any mechanism and any equilibrium under this joint
distribution is equal to the upper bound of the expected regret for any joint
distribution and any equilibrium under the separate second-price auction with
random reserves. One can imagine that adversarial nature is constructing a
worst-case distribution to let the designer suffer from a high expected
regret.
The worst-case distribution admits a simple description as follows999Its
formal definition is given in Section 4.2. . For each good, adversarial nature
selects one bidder whose upper bound of the values of the good is the highest
among the bidders (breaking ties arbitrarily). For each bidder, the marginal
distributions of the values of the goods for which the bidder is selected are
equal-revenue distributions, 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 is the same; the values for these goods are comonotonic
(maximal positive correlation); the values for the other goods are all
zeros101010Note that if a bidder is not selected for any good, then his values
for all goods are zeros.. For the goods across the bidders, the values are
independent.
Under this distribution, each selected bidder values a totally different set
of goods; for each good, exactly one bidder values it; each selected bidder’s
values for the goods he values are comonotonic; the values of the goods across
the selected bidders are independent.
Now I illustrate the idea behind this distribution. First, to understand the
part of equal-revenue distributions, consider the one-good one-bidder case in
which the mechanism collapses to randomized pricing over a range. As the
designer is indifferent between these prices, the marginal revenue must be
zero over these prices, from which an equal-revenue distribution
arises111111See Bergemann and Schlag, (2008) for details about the
derivation.. Second, the intuition for the part of selection can be summarized
by a scale effect: because the minimax regret in the one-good one-bidder case
is proportional to the upper bound of the values, by selecting a bidder whose
upper bound of the values is the highest for each good, the potential regret
is made the highest for each good. Third, the intuition for the part of
comonotonicity can be summarized by a screening effect: consider the multiple-
good one-bidder case, the comonotonicity between goods limits the ability of
the designer to screen different goods by reducing the multi-dimensional
screening to the single-dimensional screening. Fourth, the intuition for the
part of zeros can be summarized by a competition effect: it eliminates the
competition among bidders for each good by letting only one bidder have a
positive value for each good. Fifth, the intuition for the part of
independence can be summarized by an information effect: one bidder’s values
for goods do not provide any information about any other bidder’s values for
other goods, which prevents the designer from extracting surplus from one
bidder based on information about other bidders.
The main result incorporates multi-dimensional screening and single-good
auction as two special cases. For the multi-dimensional screening, a separate
randomized posted-price mechanism is a minimax regret mechanism, and a
distribution in which the values across the goods are comonotonic is a worst-
case distribution.121212The solution for the multi-dimensional screening has
been found by Koçyiğit et al., (2021). I offer an alternative proof using a
quantile-version of virtual values. Carroll, (2017) also uses quantiles to
parameterize the single buyer’s values for the multi-dimensional screening.
For the single-good auction, a second-price auction with random reserves is a
minimax regret mechanism, and a distribution in which only one bidder has a
positive value for the good is a worst-case distribution.
The remainder of the introduction discusses related work. Section 2 presents
the model. Section 3 illustrates the methodology. Section 4 characterizes the
main result. Section 5 presents the solutions to two special cases. Section 6
is a discussion. Section 7 is a conclusion. The Appendix extends the result to
an environment where bidders can acquire any additional information.

###  1.1 Related Work

The closest related work is Koçyiğit et al., (2020), who consider the same
environment and find a (different) separate second-price auction with random
reserves has good robust properties. There are, however, several critical
differences. First, they restrict attention to dominant-strategy
mechanisms131313See Definition 1 for the formal definition of dominant-
strategy mechanisms., whereas I allow for general mechanisms with essentially
the only requirement that there is a message that secures bidders’
participation. That is, I search for a minimax regret mechanism from a much
wider class of mechanisms. Second, they show that their proposed mechanism is
a minimax regret mechanism for the symmetric case where the upper bounds of
the values for a given good are the same across bidders, whereas I establish
that my proposed mechanism is a minimax regret mechanism for general upper
bounds. That is, I place no restrictions on the upper bounds of the values for
a given good across bidders. It is important and interesting to understand the
minimax regret mechanism in asymmetric environments considered in this paper,
as the symmetric case is a knife-edge case. In this sense, this paper
complements their work. The key factor that drives these differences is that I
construct a different joint distribution over value profiles that yields a
higher lower bound of the expected regret in general. In addition, there is a
Pareto ranking between my proposed mechanism and theirs: in the truth-telling
equilibrium, the ex-post regret is always weakly lower and sometimes strictly
lower under my proposed mechanism than that under theirs (Remark 2). Besides,
technically, they take the duality approach for their result, whereas I adopt
an adaptation of the classic Myerson’s approach to identify a lower bound of
the expected regret under my constructed joint distribution.
Bergemann and Schlag, (2008, 2011) consider the problem of monopoly pricing
where the monopolist is faced with uncertainty about the demand curve and
characterize randomized posted price mechanisms as minimax regret mechanisms.
My result is reduced to that of Bergemann and Schlag, (2008) in the one-good
one-bidder case. Koçyiğit et al., (2021) consider the problem of multi-
dimensional screening without priors and characterize randomized separate
posted price mechanisms as minimax regret mechanisms. My result is reduced to
theirs in the multiple-good one-bidder case. Moreover, I offer another minimax
regret mechanism: a randomized grand bundling (Remark 7).
There are other mechanism design papers where the designer aims to minimize
the worst-case regret. Guo and Shmaya, (2019) study the classic problem of
monopoly regulation (Baron and Myerson, (1982)) using the minimax regret
approach; Guo and Shmaya, (2021) study a project choice problem (Armstrong and
Vickers, (2010)) using the minimax regret approach; Caldentey et al., (2017)
characterize the deterministic dynamic pricing rule that minimizes the
seller’s worst-case regret; Renou and Schlag, (2011) study the problem of
implementing social choice correspondences using $\epsilon-$minimax regret
criterion.
More broadly, this paper is related to the robust mechanism design literature
and the information design literature. Carrasco et al., (2018) characterize
maxmin selling mechanisms when the seller faced with a single buyer only knows
the first $N$ moments of distribution ($N$ is an arbitrary positive integer).
Che, (2019), He and Li, (2022) and Zhang, 2021a  study the robust auction
design problem when the designer has limited distributional information.
Zhang, 2021b  studies the profit-maximizing bilateral trade problem and
characterize maxmin trade mechanisms when the designer knows only the
expectations of the values. Similar to mine, these papers all assume that the
values are private and all characterize some randomized mechanism as a maxmin
mechanism. Carroll, (2017) studies the multi-dimensional screening problem
when the designer only knows the marginal distributions. Similar to the
multiple-good one-bidder case in my paper, a separate selling mechanism turns
out to be a maxmin solution. Different from the multiple-good one-bidder case
in my paper, his maxmin solution does not require randomization. Chung and
Ely, (2007) and Chen and Li, (2018) study maxmin foundations for dominant-
strategy mechanisms. Similar to my model, they study the private value
environment. In contrast to my model, beliefs are not required to be
consistent with a common prior; in addition, they select for the designer’s
most preferred equilibrium. Roesler and Szentes, (2017) and Condorelli and
Szentes, (2020) derive optimal information structures for maximizing buyer’s
surplus. My worst-case distribution is reduced to theirs in the one-good one-
bidder case. Du, (2018) derives the optimal informationally robust mechanism
for the one-good one-bidder case and constructs a mechanism that
asymptotically extracts full surplus for the single-good auction. Brooks and
Du, (2021) derive the optimal informationally robust mechanism for the single-
good auction. In contrast to my model, they study the common value
environment. However, our solution concepts are similar. My solution is indeed
a strong minimax solution: holding the joint distribution fixed, the mechanism
and equilibrium minimize regret, and holding the mechanism fixed, the joint
distribution and equilibrium maximize regret; in addition, there is an
equilibrium (the truth-telling equilibrium) under which the regret cap is hit.

##  2 Model

I consider a (correlated) private value environment where a designer sells $J$
different indivisible goods to $I$ risk-neutral bidders. I denote by
$\mathcal{I}=\\{1,2,\cdots,I\\}$ the set of bidders and by
$\mathcal{J}=\\{1,2,\cdots,J\\}$ the set of goods. Bidder $i$’s value of the
good $j$ is denoted by $v_{i}^{j}$, and bidder $i$’s value vector for all
goods is denoted by $\mathbf{v_{i}}=(v_{i}^{1},v_{i}^{2},\cdots,v_{i}^{J})$.
The value profile across bidders is denoted by
$\mathbf{v}=\mathbf{(v_{1},v_{2},\cdots,v_{I})}$. Each bidder’s value vector
is his private information, which the designer perceives as uncertain. I
assume that the designer only knows an upper bound $\bar{v_{i}}^{j}$ on the
value $v_{i}^{j}$ for all $i\in\mathcal{I}$ and all $j\in\mathcal{J}$. Then I
denote by $V_{i}=\times_{j\in\mathcal{J}}[0,\bar{v_{i}}^{j}]$ the set of all
possible value vectors of bidder $i$, by $V=\times_{i\in\mathcal{I}}V_{i}$ the
set of all possible value profiles across bidders and by $\Delta V$ the set of
all possible joint distributions on $V$. In contrast, bidders share a common
prior $\pi\in\Delta(V)$. For exposition, I assume that the supply cost for
each good is zero141414All results can be easily extended to the case where
the supply cost can be positive and different for each good. Formal statement
and proofs are omitted but available upon request..
A mechanism $\mathcal{M}$ consists of measurable sets of messages $M_{i}$ for
each $i$ and measurable allocation rules
$\mathbf{q_{i}}=(q_{i}^{j})_{j\in\mathcal{J}}:M\to[0,1]^{J}$ and measurable
payment rules: $t_{i}:M\to\mathbb{R}$ for each $i$, where
$M=\times_{i=1}^{I}M_{i}$ is the set of message profiles, such that
$\sum_{i=1}^{I}q_{i}^{j}(\mathbf{m})\leq 1$ for each $j$. Given a mechanism
$\mathcal{M}$ and a simultaneously submitted message profile $\mathbf{m}$,
bidder $i$ with a value vector of $\mathbf{v_{i}}$ has an ex-post payoff

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

Bidders’ preferences are quasilinear and additively separable across the
goods. I require the mechanism to satisfy a participation security constraint:
For each $i$, there exists $\mathbf{0}\in M_{i}$ such that for each
$\mathbf{v_{i}}\in V_{i}$ and each $\mathbf{m_{-i}}\in M_{-i}$,

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

Bidder $i$ with a value vector $\mathbf{v_{i}}$ can guarantee a nonnegative
ex-post payoff by sending this message, regardless of messages sent by the
other bidders.
Given a mechanism $\mathcal{M}$ and a joint distribution (common prior among
bidders) $\pi$, I have a game of incomplete information. A Bayes Nash
Equilibrium (BNE) of the game is a strategy profile $\sigma=(\sigma_{i})$,
$\sigma_{i}:V_{i}\to\Delta(M_{i})$, such that $\sigma_{i}$ is best response to
$\sigma_{-i}$: Let
$U_{i}(\mathbf{v_{i}},\mathcal{M},\mathbf{\pi},\sigma)=\int_{\mathbf{v_{-i}}}U_{i}(\mathbf{v_{i}},(\sigma_{i}(\mathbf{v_{i}}),\sigma_{-i}(\mathbf{v_{-i}})))d\mathbf{\pi(v_{-i}|v_{i})}$
where
$U_{i}(\mathbf{v_{i}},(\sigma_{i}(\mathbf{v_{i}}),\sigma_{-i}(\mathbf{v_{-i}})))$
is the multilinear extension of $U_{i}$ in Equation (2), then for any
$i,\mathbf{v_{i}},\sigma_{i}^{\prime}$,

$U_{i}(\mathbf{v_{i}},\mathcal{M},\pi,\sigma)\geq
U_{i}(\mathbf{v_{i}},\mathcal{M},\pi,(\sigma_{i}^{\prime},\sigma_{-i})).$

The set of all Bayes Nash Equilibria for a given mechanism $\mathcal{M}$ and a
given joint distribution $\mathbf{\pi}$ is denoted by
$\Sigma(\mathcal{M},\mathbf{\pi})$.
The designer’s expected regret is defined as the difference between the full
surplus given a joint distribution and the expected revenue under a mechanism
and an equilibrium. Given a joint distribution $\mathbf{\pi}$, the full
surplus is
$\int_{\mathbf{v}}\\{\sum_{j=1}^{J}\max_{i\in\mathcal{I}}v_{i}^{j}\\}d\mathbf{\pi(v)}$,
and the expected revenue given a mechanism $\mathcal{M}$ and an equilibrium
$\sigma$ is
$\int_{\mathbf{v}}\\{\sum_{i=1}^{I}t_{i}(\sigma(\mathbf{v}))\\}d\mathbf{\pi(v)}$.
The expected regret thus is
$ER(\mathcal{M},\mathbf{\pi},\sigma)=\int_{\mathbf{v}}\\{\sum_{j=1}^{J}\max_{i\in\mathcal{I}}v_{i}^{j}-\sum_{i=1}^{I}t_{i}(\sigma(\mathbf{v}))\\}d\mathbf{\pi(v)}$.
The integrand is defined as the ex-post regret from $\mathbf{v}$ under the
equilibrium $\sigma$. The designer evaluates a mechanism by its worst-case
expected regret across all possible joint distributions and equilibria.
Formally, the designer evaluates a mechanism $\mathcal{M}$ by
$GER(\mathcal{M})=\sup_{\mathbf{\pi}\in\Delta(V)}\sup_{\sigma\in\Sigma(\mathcal{M},\mathbf{\pi})}ER(\mathcal{M},\mathbf{\pi},\sigma)$,
referred to as the regret cap. I say $\bar{R}$ is an upper bound of the
expected regret under a mechanism $\mathcal{M}$ if
$GER(\mathcal{M})\leq\bar{R}$. I say $\underline{R}$ is a lower bound of the
expected regret given a joint distribution $\mathbf{\pi}$ if
$\inf_{\mathcal{M}}\inf_{\sigma\in\Sigma(\mathcal{M},\mathbf{\pi})}ER(\mathcal{M},\mathbf{\pi},\sigma)\geq\underline{R}$.
The designer’s goal is to find a mechanism with the minimal regret cap. I
refer to the minimal regret cap as the minimax regret. Formally, the designer
aims to find a mechanism $\mathcal{M^{*}}$, referred to as a minimax regret
mechanism, that solves the following problem:

$\inf_{\mathcal{M}}GER(\mathcal{M}).$

##  3 Methodology

The problem (2) can be interpreted as a two-player sequential game. The two
players are the designer and adversarial nature. The designer first chooses a
mechanism $\mathcal{M}$. After observing the designer’s choice of the
mechanism, adversarial nature chooses a joint distribution over value profiles
$\mathbf{\pi}\in\Delta(V)$ as well as an equilibrium
$\sigma\in\Sigma(\mathcal{M},\mathbf{\pi})$ to maximize the expected regret.
The designer’s payoff is $-ER(\mathcal{M},\mathbf{\pi},\sigma)$, and nature’s
payoff is $ER(\mathcal{M},\mathbf{\pi},\sigma)$ if
$\Sigma(\mathcal{M},\mathbf{\pi})\neq\emptyset$; otherwise, both players’
payoffs are minus infinity. One can also consider a game in which nature moves
first by choosing a joint distribution and the designer moves next by choosing
a mechanism and an equilibrium. Although it is not obvious that these two
problems are payoff equivalent because the equilibrium correspondence is not
lower-hemicontinuous, I will construct a mechanism $\mathcal{M^{*}}$ and a
joint distribution $\mathbf{\pi^{*}}$ that form (a version of) a saddle point
and therefore (a version of) the minimax theorem holds. Precisely, I will (i)
find an upper bound $R^{*}$ of the expected regret under the mechanism
$\mathcal{M^{*}}$ and (ii) show that $R^{*}$ is also a lower bound of the
expected regret given the joint distribution $\mathbf{\pi^{*}}$. Note that
(ii) implies that no mechanism can achieve a regret cap strictly lower than
$R^{*}$, and (i) says that the regret cap of $\mathcal{M^{*}}$ is weakly lower
than $R^{*}$. Therefore, (i) and (ii) together imply that $\mathcal{M^{*}}$ is
a minimax regret mechanism. I refer to $\mathbf{\pi^{*}}$ as a worst-case
distribution.

##  4 Main Result

In this section, I first formally define the separate second-price auction
with random reserves $(M^{*},\mathbf{q^{*},t^{*}})$ (Section 4.1) and the
joint distribution over value profiles $\mathbf{\pi^{*}}$ (Section 4.2), then
I present the formal statement of the result (Section 4.3) that the proposed
mechanism (resp, the proposed distribution) is a minimax regret mechanism
(resp, a worst-case distribution). Finally, I prove the formal statement
(Section 4.4).

###  4.1 Separate Second-price Auction with Random Reserves

The separate second-price auction with random reserves,
$(M^{*},\mathbf{q^{*},t^{*}})$, is defined as follows. First, it is a direct
mechanism, i.e., $M^{*}=V$. With slight abuse of notations, I use
$\mathbf{v}=(v^{j}_{i})_{i\in\mathcal{I},j\in\mathcal{J}}$ to also denote the
reported message. Let $v_{(2)}^{j}$ be the second highest reported value for
the good $j$ whenever well-defined.
If there are no ties,
$\mathbf{q^{*}(v)}=(q_{i}^{j*}(\mathbf{v}))_{i\in\mathcal{I},j\in\mathcal{J}}$
where

$q_{i}^{j*}(\mathbf{v})=\left\\{\begin{array}[]{lll}1+\ln{\frac{v_{i}^{j}}{\bar{v_{i}}^{j}}}&&{\text{if
$\forall k\neq i,v_{i}^{j}>v^{j}_{k}$ and $\frac{\bar{v_{i}}^{j}}{e}\leq
v_{i}^{j}\leq\bar{v_{i}}^{j}$};}\\\ 0&&{\text{if $\exists k\neq i$ s.t.
$v_{i}^{j}<v_{k}^{j}$ or $0\leq
v_{i}^{j}<\frac{\bar{v_{i}}^{j}}{e}$}.}\end{array}\right.$

$\mathbf{t^{*}(v)}=(t_{i}^{*}(\mathbf{v}))_{i\in\mathcal{I}}$ in which
$t_{i}^{*}(\mathbf{v})=\sum_{j\in\mathcal{J}}t_{i}^{j*}(\mathbf{v})$151515$t_{i}^{j*}$
can be interpreted as the payment from bidder $i$ for good $j$ under the
mechanism $(M^{*},\mathbf{q^{*},t^{*}})$.  where

$t_{i}^{j*}(\mathbf{v})=\left\\{\begin{array}[]{lll}v_{i}^{j}-\frac{\bar{v_{i}}^{j}}{e}&&{\text{if
$\forall k\neq i$, $v_{i}^{j}>v^{j}_{k}$ and
$v^{j}_{(2)}<\frac{\bar{v_{i}}^{j}}{e}\leq v_{i}^{j}\leq\bar{v_{i}}^{j}$};}\\\
v_{i}^{j}+v^{j}_{(2)}\ln{\frac{v^{j}_{(2)}}{\bar{v_{i}}^{j}}}&&{\text{if
$\forall k\neq i$, $v_{i}^{j}>v^{j}_{k}$ and $\frac{\bar{v_{i}}^{j}}{e}\leq
v^{j}_{(2)}<v_{i}^{j}\leq\bar{v_{i}}^{j}$};}\\\ 0&&{\text{if $\exists k\neq i$
s.t. $v_{i}^{j}<v_{k}^{j}$ or $0\leq
v_{i}^{j}<\frac{\bar{v_{i}}^{j}}{e}$}.}\end{array}\right.$

Now I specify the tie breaking rule when there are ties. Given a value profile
$\mathbf{v}$ in which there are ties in the auction of good $j$, let
$\mathcal{I}(\mathbf{v^{j}}):=\\{s\in\mathcal{I}|v_{s}^{j}\geq
v_{i}^{j}\quad\forall i\in\mathcal{I}\quad\text{and}\quad
v_{s}\geq\frac{\bar{v_{s}}^{j}}{e}\\}$. If $\mathcal{I}(\mathbf{v^{j}})$ is
empty, then $q_{i}^{j*}(\mathbf{v})=t_{i}^{j*}(\mathbf{v})=0$ for any
$i\in\mathcal{I}$; otherwise, pick a bidder
$i\in\operatorname*{arg\,min}_{s\in\mathcal{I}(\mathbf{v^{j}})}\bar{v_{s}}^{j}$,
let
$q_{i}^{j*}(\mathbf{v})=1+\ln\frac{v_{i}^{j}}{\bar{v_{i}}^{j}},t_{i}^{j*}(\mathbf{v})=v_{i}^{j}+v_{i}^{j}\ln{\frac{v_{i}^{j}}{\bar{v_{i}}^{j}}}$,
and $q_{s}^{j*}(\mathbf{v})=t_{s}^{j*}(\mathbf{v})=0$ for any $s\neq i$. In
words, among the bidders whose values are weakly higher than their lower
bounds of the random reserves respectively, pick a bidder whose upper bound of
the values is the lowest and allocate good $j$ to this bidder when his bid is
higher than the random reserve.
Note that the allocation probabilities for each good $j$ are independent of
the bidders’ values for the other goods. The payment rule is characterized by
the envelope theorem. Then clearly the above mechanism is equivalent to
holding a separate second-price auction with bidder-specific random reserves
for each good.

###  4.2 Joint Distribution

The joint distribution over value profiles $\mathbf{\pi^{*}}$ is defined via
the following five steps.
Step 1: Selection. For each good $j$, pick (breaking ties arbitrarily) a
bidder $i\in\operatorname*{arg\,max}_{s\in\mathcal{I}}\bar{v_{s}}^{j}$. Let
$\mathcal{J}(i)$ denote the set of goods for which $i$ is picked. Note that
$\mathcal{J}(i)$ (could be empty) is disjoint and
$\cup_{i\in\mathcal{I}}\mathcal{J}(i)=\mathcal{J}$. If a bidder is not picked
for any good, then his values for all goods are zeros.
Step 2: Equal-revenue Distributions. For each bidder $i$ and
$j\in\mathcal{J}(i)$ (this part is irrelevant if $\mathcal{J}(i)$ is empty),
the marginal distribution of $v_{i}^{j}$ is an equal-revenue distribution
whose cumulative distribution function is

$\pi_{i}^{j*}(v_{i}^{j})=\left\\{\begin{array}[]{lll}1-\frac{\bar{v_{i}}^{j}}{ev_{i}^{j}}&&{\text{if
$\frac{\bar{v_{i}}^{j}}{e}\leq v_{i}^{j}<\bar{v_{i}}^{j}$};}\\\ 1&&{\text{if
$v_{i}^{j}=\bar{v_{i}}^{j}$}.}\end{array}\right.$

Step 3: Comonotonicity. For each bidder $i$ and cross $j\in\mathcal{J}(i)$
(this part is irrelevant if $\mathcal{J}(i)$ is empty), the dependence
structure is comonotonic. Formally, for good $j\in\mathcal{J}(i)$, define the
inverse quantile function

$v_{i}^{j}(z_{i})=\min\\{\tilde{v_{i}}^{j}|\pi_{i}^{j*}(\tilde{v_{i}}^{j})\geq
z_{i}\\}=\left\\{\begin{array}[]{lll}\frac{\bar{v_{i}}^{j}}{e(1-z_{i})}&&{\text{if
$0\leq z_{i}<1-\frac{1}{e}$};}\\\ \bar{v_{i}}^{j}&&{\text{if $z_{i}\geq
1-\frac{1}{e}$}.}\end{array}\right.$

Then I define the joint distribution across $j\in\mathcal{J}(i)$ by randomly
drawing $z_{i}\sim U[0,1]$ and taking $v_{i}^{j}=v_{i}^{j}(z_{i})$ for each
$j\in\mathcal{J}(i)$.
Step 4: Zeros. For each bidder $i$ and $j\notin\mathcal{J}(i)$ (this part is
irrelevant if $\mathcal{J}(i)=\mathcal{J}$), $v_{i}^{j}=0$.
Step 5: Independence. For goods across bidders (this part is irrelevant if
$\mathcal{J}(i)=\mathcal{J}$ for some $i\in\mathcal{I}$), the values are
independently distributed. Formally, $z_{i}$’s are independently distributed
uniform distributions.

###  4.3 Formal Statement: Theorem 1

######  Theorem 1.

The mechanism $(M^{*},\mathbf{q^{*},t^{*}})$ is a minimax regret mechanism
with the regret cap of
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$. The
joint distribution $\mathbf{\pi^{*}}$ is a worst-case distribution.

###  4.4 Proof of Theorem 1

####  4.4.1 Upper Bound on Regret for $(M^{*},\mathbf{q^{*},t^{*}})$

######  Proposition 1.

An upper bound of the expected regret under the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$ is
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$.

###### Proof.

Consider the auction of good $j$ under the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$. Fix an arbitrary joint distribution
$\mathbf{\pi}\in\Delta V$. First consider the truth-telling equilibrium. Given
any value profile $\mathbf{v}\in supp(\mathbf{\pi})$, suppose $i$ is the
unique highest bidder for good $j$ . If
$v^{j}_{(2)}<\frac{\bar{v_{i}}^{j}}{e}\leq v_{i}^{j}\leq\bar{v_{i}}^{j}$, then
the ex-post regret is
$v_{i}^{1}-t_{i}^{j*}(\mathbf{v})=v_{i}^{j}-(v_{i}^{j}-\frac{\bar{v_{i}}^{j}}{e})=\frac{\bar{v_{i}}^{j}}{e}$;
if $\frac{\bar{v_{i}}^{j}}{e}\leq v^{j}_{(2)}<v_{i}^{j}\leq\bar{v_{i}}^{j}$,
then the ex-post regret is
$v_{i}^{j}-t_{i}^{j*}(\mathbf{v})=v_{i}^{j}-(v_{i}^{j}+v^{j}_{(2)}\ln{\frac{v^{j}_{(2)}}{\bar{v_{i}}^{j}}})=-v^{j}_{(2)}\ln{\frac{v^{j}_{(2)}}{\bar{v_{i}}^{j}}}$,
which is maximized at $v^{j}_{(2)}=\frac{\bar{v_{i}}^{j}}{e}$, yielding an ex-
post regret of $\frac{\bar{v_{i}}^{j}}{e}$; finally, if $0\leq
v_{i}^{j}<\frac{\bar{v_{i}}^{j}}{e}$, then the ex-post regret is less than
$\frac{\bar{v_{i}}^{j}}{e}$ because the maximal revenue is less than
$\frac{\bar{v_{i}}^{j}}{e}$. Suppose now there are ties. Then under the
specified tie breaking rule, if $\mathcal{I}(\mathbf{v^{j}})$ is empty, then
$v^{j}_{i}<\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ for any
$i\in\mathcal{I}$, and so the ex-post regret is less than
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$; if
$\mathcal{I}(\mathbf{v^{j}})$ is not empty, then the ex-post regret is
$v_{i}^{j}\ln{\frac{v_{i}^{j}}{\bar{v_{i}}^{j}}}$ where
$i\in\operatorname*{arg\,min}_{s\in\mathcal{I}(\mathbf{v^{j}})}\bar{v_{s}}^{j}$,
which is maximized at $v_{i}^{j}=\frac{\bar{v_{i}}^{j}}{e}$, yielding an ex-
post regret of
$\frac{\bar{v_{i}}^{j}}{e}\leq\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$.
Thus, in the truth-telling equilibrium, the ex-post regret from good $j$ is at
most $\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ for any value profile.
Next consider any equilibrium $\sigma$. Given any value profile $\mathbf{v}\in
supp(\mathbf{\pi})$, pick a bidder $i$ whose value for good $j$ is the highest
among the bidders, or $i\in\operatorname*{arg\,max}_{i\in I}v_{i}^{j}$. If
$v_{i}^{j}>\frac{\bar{v_{i}}^{j}}{e}$ and there is a positive measure of the
others’ reports under the conditional equilibrium report distribution
$\sigma_{-i}(\mathbf{v_{-i}})$ such that bidder $i$ wins the good by
truthfully reporting $v_{i}^{j}$ provided that $v_{i}^{j}$ is higher than the
random reserve, then bidder $i$ has a strict incentive to truthfully report
his value for good $j$, and thus the argument in the previous paragraph
implies that the ex-post regret must not exceed
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$. Otherwise, there are two
cases to consider. 1) If $v_{i}^{j}\leq\frac{\bar{v_{i}}^{j}}{e}$, then the
most to lose does not exceed $\frac{\bar{v_{i}}^{j}}{e}$ and thus the ex-post
regret must not exceed $\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$. 2)
If $v_{i}^{j}>\frac{\bar{v_{i}}^{j}}{e}$ and there is a zero measure of the
others’ reports under the conditional equilibrium report distribution
$\sigma_{-i}(\mathbf{v_{-i}})$ such that bidder $i$ wins the good by
truthfully reporting $v_{i}^{j}$ provided that $v_{i}^{j}$ is higher than the
random reserve, then (almost surely) the highest report among the other
bidders is (weakly) higher than bidder $i$’s value for good $j$. In this case,
the ex-post regret must not exceed
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ as the difference between
the highest report and the ex-post revenue is weakly less than
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ by the argument in the
previous paragraph. Thus, in any equilibrium, the ex-post regret from good $j$
is at most $\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ for any value
profile. This implies that in any equilibrium, the expected regret from good
$j$ is at most $\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ given the
arbitrary joint distribution $\mathbf{\pi}$.
Finally, because of the separable nature of the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$, an upper bound of the expected regret is
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$. ∎

######  Remark 1.

This upper bound is hit given the joint distribution $\mathbf{\pi^{*}}$ and
the truth-telling equilibrium. To see this, fix any
$\mathbf{v}\in\mathbf{\pi^{*}}$ and consider good $j$. By the definition of
$\mathbf{\pi^{*}}$, there is only one bidder, denoted by $i$, whose value for
good $j$ is positive. In addition, $v_{i}^{j}\geq\frac{\bar{v_{i}}^{j}}{e}$.
Then by the proof of Proposition 1, the ex-post regret from good $j$ is
$\frac{\bar{v_{i}}^{j}}{e}$ in the truth-telling equilibrium. Note that by the
definition of $\mathbf{\pi^{*}}$,
$i\in\operatorname*{arg\,max}_{i\in\mathcal{I}}\bar{v_{i}}^{j}$. Thus the ex-
post regret from good $j$ is equal to
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ in the truth-telling
equilibrium. Because this is true for any $\mathbf{v}\in\mathbf{\pi^{*}}$, the
expected regret from good $j$ is equal to
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ given the joint distribution
$\mathbf{\pi^{*}}$ and the truth-telling equilibrium. Summing up across goods,
the expected regret is
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ given
the joint distribution $\mathbf{\pi^{*}}$ and the truth-telling equilibrium.

######  Remark 2.

Koçyiğit et al., (2020) present a separate second-price auction with anonymous
random reserves in which

$q_{i}^{j}(\mathbf{v})=\left\\{\begin{array}[]{lll}1+\ln{\frac{v_{i}^{j}}{\max_{i\in\mathcal{I}}\bar{v_{i}}^{j}}}&&{\text{if
$\forall k\neq i$, $v_{i}^{j}>v^{j}_{k}$ and
$\frac{\max_{i\in\mathcal{I}}\bar{v_{i}}^{j}}{e}\leq
v_{i}^{j}\leq\bar{v_{i}}^{j}$};}\\\ 0&&{\text{if $\exists k\neq i$ s.t.
$v_{i}^{j}<v_{k}^{j}$ or $0\leq
v_{i}^{j}<\frac{\max_{i\in\mathcal{I}}\bar{v_{i}}^{j}}{e}$}.}\end{array}\right.$

And the payment rule is characterized by the envelope theorem. They show that
given this mechanism,
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ is an
upper bound of the ex-post regret. Although their mechanism has the same
regret cap, the designer may favor $(M^{*},\mathbf{q^{*},t^{*}})$ over their
mechanism for reasons outside the model. Specifically, there exists a Pareto
ranking between the two mechanisms in the following sense: as long as
$\max_{i\in\mathcal{I}}\bar{v_{i}}^{j}>\bar{v_{k}}^{j}$ for some
$k\in\mathcal{I}$ and some $j\in\mathcal{J}$, it is straightforward to show
that in the truth-telling equilibrium, i) the ex-post regret under
$(M^{*},\mathbf{q^{*},t^{*}})$ is weakly lower than that under their mechanism
for any $\mathbf{v}\in V$, and ii) the ex-post regret under
$(M^{*},\mathbf{q^{*},t^{*}})$ is strictly lower than that under their
mechanism for some $\mathbf{v}\in V$. Intuitively, under their mechanism, the
allocation probability is lower for a highest bidder whose upper bound of the
values of the good is not the highest, resulting in a higher ex-post regret
for such a value profile.

Indeed, under the criterion used in Remark 2, no mechanism from the family of
separate second-price auctions161616In a separate second-price auction, there
may be random reserves, deterministic reserves, or no reserves., denoted by
$\mathcal{F}-SSP$, is better than the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$.

######  Definition 1.

I say a direct mechanism $\mathcal{M}=(V,\mathbf{q,t})$ is a dominant-strategy
mechanism if for all $i\in\mathcal{I}$, all $\mathbf{v}\in V$, and all
$\mathbf{v_{i}^{\prime}}\in V_{i}$,

$\mathbf{v_{i}}\cdot\mathbf{q_{i}(v)}-t_{i}(\mathbf{v})\geq\mathbf{v_{i}}\cdot\mathbf{q_{i}(v_{i}^{\prime},v_{-i})}-t_{i}(\mathbf{v_{i}^{\prime},v_{-i}}),$
$\mathbf{v_{i}}\cdot\mathbf{q_{i}(v)}-t_{i}(\mathbf{v})\geq 0.$

######  Definition 2.

I say a dominant-strategy mechanism $\mathcal{M}_{1}$ is undominated by
another dominant-strategy mechanism $\mathcal{M}_{2}$ if in the truth-telling
equilibrium, the ex-post regret under the mechanism $\mathcal{M}_{1}$ is
strictly lower than that under the mechanism $\mathcal{M}_{2}$ for some
$\mathbf{v}\in V$.

######  Corollary 1.

The mechanism $(M^{*},\mathbf{q^{*},t^{*}})$ is undominated by any mechanism
from $\mathcal{F}-SSP$.

###### Proof.

Fix any $i\in\mathcal{I}$ and any $j\in\mathcal{J}$, consider the value
profiles in which $v_{i}^{j}\in[0,\bar{v_{i}}^{j}]$ and all other values are
zeros. Then Proposition 1 in Bergemann and Schlag, (2008) implies that the
random reserve for the bidder $i$ and the good $j$ in the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$ is the unique random reserve that minimizes the
worst-case ex-post regret in the truth-telling equilibrium for these value
profiles. Therefore, if a different (random) reserve were used for the bidder
$i$ and the good $j$, then there would be a value profile with an ex-post
regret strictly higher than that under the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$.
In addition, the specific tie-breaking rule in $(M^{*},\mathbf{q^{*},t^{*}})$
minimizes the worst-case ex-post regret when there are ties across different
tie-breaking rules. To see this, recall that the worst-case ex-post regret is
proportional to the upper bound of values in the one-good one-bidder case and
that under the tie-breaking rule in $(M^{*},\mathbf{q^{*},t^{*}})$, a bidder
with the lowest upper bound of values for a good is picked. This finishes the
proof. ∎

####  4.4.2 Lower Bound on Regret for $\mathbf{\pi^{*}}$

######  Proposition 2.

A lower bound of the expected regret under $\mathbf{\pi^{*}}$ is
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$.

###### Proof.

Note that given a joint distribution, minimizing the expected regret across
mechanisms and equilibria is equivalent to maximizing the expected revenue
across mechanisms and equilibria. Then the revelation principle applies and
thus it is without loss to restrict attention to direct mechanisms.
I parameterize the value profile across bidders by
$\mathbf{z}=(z_{1},z_{2},\cdots,z_{I})\in[0,1]^{I}$. Then for any direct
mechanism
$(\mathbf{q(z),t(z)})=((\mathbf{q_{i}(z)})_{i\in\mathcal{I}},(t_{i}(\mathbf{z}))_{i\in\mathcal{I}})$
where
$\mathbf{q_{i}(z)}=(q_{i}^{j}(\mathbf{z}))_{j\in\mathcal{J}}\in[0,1]^{J}$
represent the allocation probabilities of the goods to bidder $i$ under the
parametrerized value profile $\mathbf{z}$ and $t_{i}(\mathbf{z})\in\mathbb{R}$
represents bidder $i$’s payment under $\mathbf{z}$, (2) together with (2)
imply

$U_{i}(z_{i}):=\sum_{j\in\mathcal{J}(i)}v_{i}^{j}(z_{i})Q_{i}^{j}(z_{i})-T_{i}(z_{i})\geq\sum_{j\in\mathcal{J}(i)}v_{i}^{j}(z_{i})Q_{i}^{j}(z_{i}^{\prime})-T_{i}(z_{i}^{\prime})\quad\text{for}\quad
i\in\mathcal{I},z_{i},z_{i}^{\prime}\in[0,1],$
$\sum_{j\in\mathcal{J}(i)}v_{i}^{j}(z_{i})Q_{i}^{j}(z_{i})-T_{i}(z_{i})\geq
0\quad\text{for}\quad i\in\mathcal{I},z_{i}\in[0,1],$

where
$Q_{i}^{j}(z_{i})=\int_{[0,1]^{I-1}}q_{i}^{j}(z_{i},\mathbf{z_{-i}})d\mathbf{z_{-i}}$
and
$T_{i}(z_{i})=\int_{[0,1]^{I-1}}t_{i}(z_{i},\mathbf{z_{-i}})d\mathbf{z_{-i}}$
are the expected allocation of good $j$ to type $z_{i}$ of bidder $i$ and the
expected payment made by type $z_{i}$ of bidder $i$ respectively, due to the
fact that $z_{i}$’s are independently distributed uniform distributions by the
definition of $\mathbf{\pi^{*}}$. Note that the allocation of good $j$ for
$j\notin\mathcal{J}(i)$ does not appear in either (4.4.2) or (4.4.2) because
the value for such a good (if any) is zero to bidder $i$ under the joint
distribution $\mathbf{\pi^{*}}$.
For $z_{i}^{\prime}\geq z_{i}$, (4.4.2) implies that

$\sum_{j\in\mathcal{J}(i)}(v_{i}^{j}(z_{i}^{\prime})-v_{i}^{j}(z_{i}))Q_{i}^{j}(z_{i}^{\prime})\geq
U_{i}(z_{i}^{\prime})-U_{i}(z_{i})\geq\sum_{j\in\mathcal{J}(i)}(v_{i}^{j}(z_{i}^{\prime})-v_{i}^{j}(z_{i}))Q_{i}^{j}(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
$v_{i}^{j}(z_{i})$ is differentiable for all $z_{i}$ but
$z_{i}=1-\frac{1}{e}$. Then applying the envelope theorem to (4.4.2) at each
point of differentiability, I obtain that

$\frac{\partial U_{i}(z_{i})}{\partial
z_{i}}=\sum_{j\in\mathcal{J}(i)}\frac{\partial v_{i}^{j}(z_{i})}{\partial
z_{i}}Q_{i}^{j}(z_{i})=\left\\{\begin{array}[]{lll}\sum_{j\in\mathcal{J}(i)}\frac{\bar{v_{i}}^{j}}{e(1-z_{i})^{2}}Q_{i}^{j}(z_{i})&&{\text{if
$0\leq z_{i}<1-\frac{1}{e}$};}\\\ 0&&{\text{if
$z_{i}>1-\frac{1}{e}$}.}\end{array}\right.$

Thus,

$U_{i}(z_{i})=\left\\{\begin{array}[]{lll}U_{i}(0)+\int_{0}^{z_{i}}[\sum_{j\in\mathcal{J}(i)}\frac{\bar{v_{i}}^{j}}{e(1-\tilde{z_{i}})^{2}}Q_{i}^{j}(\tilde{z_{i}})]d\tilde{z_{i}}&&{\text{if
$0\leq z_{i}<1-\frac{1}{e}$};}\\\
U_{i}(0)+\int_{0}^{1-\frac{1}{e}}[\sum_{j\in\mathcal{J}(i)}\frac{\bar{v_{i}}^{j}}{e(1-\tilde{z_{i}})^{2}}Q_{i}^{j}(\tilde{z_{i}})]d\tilde{z_{i}}&&{\text{if
$z_{i}\geq 1-\frac{1}{e}$}.}\end{array}\right.$

Therefore, the expected revenue from bidder $i$

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

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

$\begin{split}\sum_{i=1}^{I}\int_{0}^{1}T_{i}(z_{i})dz_{i}&\leq\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}(i)}\frac{\bar{v_{i}}^{j}}{e}\\\
&=\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e},\end{split}$

where the equality holds by the definition of $\mathcal{J}(i)$.
Now, the expected regret

$\begin{split}\sum_{i\in\mathcal{I}}\int_{0}^{1}\sum_{j\in\mathcal{J}(i)}v_{i}^{j}(z_{i})dz_{i}-\sum_{i=1}^{I}\int_{0}^{1}T_{i}(z_{i})dz_{i}&=\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{2\bar{v_{i}}^{j}}{e}-\sum_{i=1}^{I}\int_{0}^{1}T_{i}(z_{i})dz_{i}\\\
&\geq\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e},\end{split}$

where the term
$\sum_{i\in\mathcal{I}}\int_{0}^{1}\sum_{j\in\mathcal{J}(i)}v_{i}^{j}(z_{i})dz_{i}$
is the full surplus given the joint distribution $\mathbf{\pi^{*}}$ and the
equality holds by direct calculation and by the definition of
$\mathcal{J}(i)$. Thus,
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ is a
lower bound of the expected regret under $\mathbf{\pi^{*}}$. ∎

######  Remark 3.

In the Step 1 of the definition of $\mathcal{\pi^{*}}$, it is important that
for each good, only one bidder is selected when there are ties. Otherwise,
there would be competition for some good, resulting in a lower expected
regret.

######  Remark 4.

One may be tempted to consider the following joint distribution over value
profiles as a candidate for a worst-case distribution. There is only one
bidder, bidder $i$, whose values for the goods are non-zero; in addition, the
bidder $i$’s values for the goods follow the comonotonic equal-revenue
distribution. The bidder $i$ is selected such that
$i\in\operatorname*{arg\,max}_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}\frac{\bar{v_{i}}^{j}}{e}$.
Then by an argument similar to the proof of Proposition 2 , a lower bound of
the expected regret under this joint distribution is
$\max_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}\frac{\bar{v_{i}}^{j}}{e}$.
However, this lower bound is lower than
$\sum_{j\in\mathcal{J}}\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{j}}{e}$ in
general. Thus, this joint distribution is not “bad” enough for the designer
and is not a worst-case distribution in general. Intuitively, this joint
distribution may ignore a bidder whose upper bound of the values of a given
good is the highest among the bidders, resulting in an expected regret not
high enough. This motivates the Step 1 of the definition of
$\mathbf{\pi^{*}}$.

######  Remark 5.

What if the designer knows nothing about the joint distribution over bidders’
value profiles? That is, bidders’ values can be unbounded. I argue that the
regret cap for any mechanism that secures bidders’ participation will be
infinity. To see this, consider a joint distribution that puts all probability
masses on a single value profile in which bidder $i$ has a large positive
value of $\theta$ for good $j$, bidder $i$’s values for the other goods are
zeros and the other bidders’ values for all the goods are zeros. Recall that
given a joint distribution over value profiles, the revelation principle
applies and it is without loss to restrict attention to direct mechanisms. In
addition, the expected revenue is generated from selling good $j$ to bidder
$i$ only, as the other values are zeros and the mechanism secures bidders’
participation. Consider a revenue-maximizing (and therefore regret-minimizing)
direct mechanism, let $Q_{i}^{j}(x)$ denote the expected allocation
probability of good $j$ to bidder $i$ given a bidder $i$’s report of $x$ about
his value for good $j$. Note that $Q_{i}^{j}(x)$ is non-decreasing in $x$ by
the incentive compatible constraint. Then the expected revenue is
$T_{i}^{j}(\theta)=\theta Q_{i}^{j}(\theta)-\int_{0}^{\theta}Q(x)dx$. Define
$\lim_{v_{i}^{j}\to\infty}Q_{i}^{j}(v_{i}^{j}):=\kappa$. By definition, for
any $\epsilon>0$, there exists a $t\geq 0$ such that
$Q_{i}^{j}(v_{i}^{j})\geq\kappa-\epsilon$ for any $v_{i}^{j}\geq t$. Then
$\int_{0}^{\theta}Q_{i}^{j}(x)dx=\int_{0}^{t}Q_{i}^{j}(x)dx+\int_{t}^{\theta}Q_{i}^{j}(x)dx\geq(\theta-t)(\kappa-\epsilon)$,
so
$T_{i}^{j}(\theta)\leq\theta\kappa-(\theta-t)(\kappa-\epsilon)=\epsilon\theta+t(\kappa-\epsilon)$,
and the expected regret is $\theta-
T_{i}^{j}(\theta)\geq(1-\epsilon)\theta-t(\kappa-\epsilon)$. As $\epsilon$ can
be chosen to be arbitrarily small, the expected regret goes to infinity as
$\theta$ goes to infinity171717This proof is similar to the proof of
Proposition 1 in Carrasco et al., (2017)..

Theorem 1 follows immediately from Proposition 1 and 2.

##  5 Special Cases

In this section, I present the results for two special cases in which $I=1$
and $J=1$ respectively, which correspond to multi-dimensional screening
(Section 5.1) and single-good auction (Section 5.2).

###  5.1 Multi-Dimensional Screening: $I=1$

Let the mechanism $(M_{1}^{*},\mathbf{q_{1}^{*}},t_{1}^{*})$ (resp, the joint
distribution $\mathbf{\pi_{1}^{*}}$ ) be the specialization of the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$ (resp, the joint distribution
$\mathbf{\pi^{*}}$) to the case in which $I=1$. I omit their descriptions for
brevity. Note that the mechanism $(M_{1}^{*},\mathbf{q_{1}^{*}},t_{1}^{*})$ is
a separate randomized posted-price mechanism: each good is sold separately
with a random posted price. In the joint distribution $\mathbf{\pi_{1}^{*}}$,
the marginal distribution of each good is an equal-revenue distribution and
the values across goods are comonotonic.

######  Corollary 2 (Multi-Dimensional Screening).

If $I=1$, then the mechanism $(M_{1}^{*},\mathbf{q_{1}^{*}},t_{1}^{*})$ is a
minimax regret mechanism with the regret cap of
$\sum_{j\in\mathcal{J}}\frac{\bar{v_{1}}^{j}}{e}$. The joint distribution
$\mathbf{\pi_{1}^{*}}$ is a worst-case distribution.

###### Proof.

The proof is a straightforward adaptation of the proof of Theorem 1 to the
case in which $I=1$. ∎

######  Remark 6.

There are very limited results in multi-dimensional screening for other
correlation structures. McAfee et al., (1989) show that with independent
continuous distributions, separate selling is essentially never optimal.
Therefore an independent joint distribution, where the marginal distributions
remain the same but the values across the goods are independent, is not a
worst-case distribution.

######  Remark 7.

There is another minimax regret mechanism for the multi-dimensional screening:
a randomized grand bundling. It can be described as follows. The designer
sells the bundle of all the goods only. Let $b$ be the bid for the bundle of
all the goods. If $b>\sum_{j\in\mathcal{J}}\frac{\bar{v_{1}}^{j}}{e}$, then
allocate the bundle with a probability of
$1+\ln{\frac{b}{\sum_{j\in\mathcal{J}}\bar{v_{1}}^{j}}}$ and charge a price of
$b-\sum_{j\in\mathcal{J}}\frac{\bar{v_{1}}^{j}}{e}$; otherwise, no goods are
allocated and the buyer (the bidder 1) pays nothing. It is straightforward to
show that the regret cap of this mechanism is
$\sum_{j\in\mathcal{J}}\frac{\bar{v_{1}}^{j}}{e}$.

###  5.2 Single-Good Auction: $J=1$

Let the mechanism $(M^{1*},\mathbf{q^{1*},t^{1*}})$ (resp, the joint
distribution $\mathbf{\pi^{1*}}$ ) be the specialization of the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$ (resp, the joint distribution
$\mathbf{\pi^{*}}$) to the case in which $J=1$. I omit their descriptions for
brevity. Note that the mechanism $(M^{1*},\mathbf{q^{1*},t^{1*}})$ is a
second-price auction with random reserves: the single good is auctioned via a
second-price auction with bidder-specific random reserves. In the joint
distribution $\mathbf{\pi^{1*}}$, only the bidder with the highest upper bound
of the values for the good has a positive value (breaking ties arbitrarily)
and the marginal distribution of this bidder’s value is an equal-revenue
distribution.

######  Corollary 3 (Single-Good Auction).

If $J=1$, then the mechanism $(M^{1*},\mathbf{q^{1*},t^{1*}})$ is a minimax
regret mechanism with the regret cap of
$\max_{i\in\mathcal{I}}\frac{\bar{v_{i}}^{1}}{e}$. The joint distribution
$\mathbf{\pi^{1*}}$ is a worst-case distribution.

###### Proof.

The proof is a straightforward adaptation of the proof of Theorem 1 to the
case in which $J=1$. ∎

##  6 Discussion

###  6.1 Solution Concept

In this paper, I consider the class of all mechanisms that secure bidders’
participation and the worst Bayes Nash Equilibrium for the designer. The
solution concept follows from a recent literature on informationally robust
mechanism design, e.g., Du, (2018) and Brooks and Du, (2021). Several remarks
can be made in sequence. First, if we assume that the class of mechanisms is
the set of dominant-strategy mechanisms and that the truth-telling equilibrium
is played, then the same result will hold by a simple extension of the current
proofs. This is because under the constructed worst-case distribution, the
expected regret under the best dominant-strategy mechanism is the same as that
under the best Bayesian incentive-compatible mechanism. Second, for the main
result, it is not crucial that adversarial nature has to pick the worst
equilibrium. That is, we can allow adversarial nature to pick the best
equilibrium for the designer, and the same result will still hold. So the main
result may be a priori surprising result: the class of the mechanisms is much
wider than the set of dominant-strategy mechanisms, yet, a dominant-strategy
mechanism emerges as a minimax regret mechanism.

###  6.2 Comparative Statics

It is instructive to discuss some comparative statics assuming that there is
no trivial good or bidder, i.e., $\bar{v_{i}}^{j}>0$ for any $i\in\mathcal{I}$
and $j\in\mathcal{J}$. First, the minimax regret is strictly increasing in
$J$. To understand this, note that the comonotonic structure in the worst-case
distribution reduces multi-dimensional screening to single-dimensional
screening, then when adding a new good, the minimax regret will increase by
the amount of the minimax regret when there is only this new good. Second, the
minimax regret is weakly increasing in $I$. To understand this, note that the
zero values in the worst-case distribution eliminate the competition181818The
competition would increase with $I$ for general joint distributions. For
example, consider a joint distribution in which bidders’ values of a given
good follow $i.i.d.$ uniform distributions. It is straightforward to show that
the expected regret under an optimal mechanism would eventually go to 0 as $I$
goes to infinity given this joint distribution. for a given good, then as the
full surplus weakly increases with $I$, the minimax regret also weakly
increases with $I$ (strictly increases with $I$ when the new bidder’s upper
bound of the values of some good is higher than that of any previous bidder).
Third, for the symmetric case where the upper bounds of the values for a given
good are the same across bidders, or $\bar{v_{i}}^{j}=\bar{v_{k}}^{j}$ for any
$i\in\mathcal{I}$, any $k\in\mathcal{I}$ and any $j\in\mathcal{J}$, the
average minimax regret (the minimax regret divided by $I$) is strictly
decreasing in $I$. To understand this, note that when adding a symmetric
bidder, the full surplus does not change given the worst-case distribution,
and, again, there is still no competition for any good. Then, the minimax
regret remains the same and thus the average minimax regret is strictly
decreasing in $I$.

###  6.3 Digital Goods

Consider a related problem in which the designer auctions digital goods191919A
digital goods auction is an auction in which the designer has an unlimited
supply of the same good. to $I$ bidders, e.g., e-books, mobile apps, online
courses, etc. Each bidder demands at most one unit of the good. Bidder $i$ has
a private value $v_{i}\in[0,\bar{v_{i}}]$. The designer aims to minimize the
worst-case expect regret. The formal objective function can be similarly
defined. Indeed, this problem may be interpreted as a special case of the
model: there are $I$ different goods, but each bidder values only one of the
goods and the good each bidder values is different. Under this interpretation,
adversarial nature’s ability is “constrained” in that the set of possible
joint distributions is smaller than the previous one. Note however that the
worst-case distribution in Theorem 1 is not excluded. Then a direct
implication of Theorem 1 is that a separate randomized posted-price mechanism
as follows is a minimax regret mechanism for this problem:

$q_{i}(v_{1},v_{2},\cdots,v_{I})=\left\\{\begin{array}[]{lll}1+\ln{\frac{v_{i}}{\bar{v_{i}}}}&&{\text{if
$\frac{\bar{v_{i}}}{e}\leq v_{i}\leq\bar{v_{i}}$};}\\\ 0&&{\text{if $0\leq
v_{i}<\frac{\bar{v_{i}}}{e}$}.}\end{array}\right.$

And the payment rule is characterized by the envelope theorem. Note that the
allocation to bidder $i$ depends on bidder $i$’s value only. In addition, an
independent equal-revenue distribution as follows is a worst-case
distribution: the marginal distribution of $v_{i}$ follows an equal-revenue
distribution whose cumulative distribution function is

$\pi_{i}(v_{i})=\left\\{\begin{array}[]{lll}1-\frac{\bar{v_{i}}}{ev_{i}}&&{\text{if
$\frac{\bar{v_{i}}}{e}\leq v_{i}<\bar{v_{i}}$};}\\\ 1&&{\text{if
$v_{i}=\bar{v_{i}}$}.}\end{array}\right.$

And the values across bidders are independent.

##  7 Concluding Remarks

In this paper, I characterize a simple minimax regret mechanism for auctioning
multiple goods given general upper bounds of values. It is worth noting that
the proposed mechanism is strategy-proof. Hence, it (essentially202020A
strategy-proof mechanism can be slightly perturbed so that truth-telling is
the unique equilibrium.) remains a minimax regret mechanism even without the
assumption of a common prior among bidders. Critically, I drop the extreme
assumption made by the traditional mechanism design literature that the
designer knows the joint distribution over value profiles, but impose an
equally extreme assumption that the designer has no distributional information
except for the upper bounds of values, on which the result heavily relies. I
believe the truth lies in intermediate cases, which are interesting to further
explore. I further conjecture that separation remains a property in many other
informational environments.

##  Appendix A Additional Information

An additional information structure consists of a measuable set of additional
information $S_{i}$ for each bidder $i$, with $S=\times_{i=1}^{I}S_{i}$, and a
joint distribution $\delta\in\Delta(V\times S)$. An additional information
structure is denoted by $\mathcal{T}=(S,\delta)$. I say $\mathcal{T}$ is $\pi-
consistent$ if the marginal of $\delta$ on $V$ is $\pi$, i.e., for every
measurable $\tilde{V}\subseteq V$, $\delta(\tilde{V}\times S)=\pi(\tilde{V})$.
The set of all $\pi-consistent$ additional information structures is denoted
by $\mathbf{T}(\pi)$. As before, each bidder $i$ knows his private value
vector $\mathbf{v_{i}}\in V_{i}$. And $\pi$ is their common prior. But, before
playing a mechanism, each bidder $i$ may observe a signal $\mathbf{s_{i}}\in
S_{i}$ from an additional information structure
$\mathcal{T}\in\mathbf{T}(\pi)$. And $\mathcal{T}$ is their common knowledge.
The definition of and the requirement for a mechanism are the same as before.
Given a mechanism $\mathcal{M}$ and a common prior $\mathbf{\pi}$ and an
additional information structure $\mathcal{T}\in\mathbf{T}(\pi)$, I have a
game of incomplete information. With slight abuse of notations, a Bayes Nash
Equilibrium (BNE) of the game is a strategy profile $\sigma=(\sigma_{i})$,
$\sigma_{i}:V_{i}\times S_{i}\to\Delta(M_{i})$, such that $\sigma_{i}$ is best
response to $\sigma_{-i}$: Let
$U_{i}(\mathbf{v_{i},s_{i}},\mathcal{M},\mathbf{\pi},\mathcal{T},\sigma)=\int_{\mathbf{v_{-i},s_{-i}}}U_{i}(\mathbf{v_{i}},(\sigma_{i}(\mathbf{v_{i},s_{i}}),\sigma_{-i}(\mathbf{v_{-i},s_{-i}})))d\mathbf{\delta(v_{-i},s_{-i}|v_{i},s_{i})}$
where
$U_{i}(\mathbf{v_{i}},(\sigma_{i}(\mathbf{v_{i},s_{i}}),\sigma_{-i}(\mathbf{v_{-i},s_{-i}})))$
is the multilinear extension of $U_{i}$ in Equation (2), then for any
$i,\mathbf{v_{i},s_{i}},\sigma_{i}^{\prime}$,

$U_{i}(\mathbf{v_{i},s_{i}},\mathcal{M},\mathbf{\pi},\mathcal{T},\sigma)\geq
U_{i}(\mathbf{v_{i},s_{i}},\mathcal{M},\mathbf{\pi},\mathcal{T},(\sigma_{i}^{\prime},\sigma_{-i})).$

The set of all Bayes Nash Equilibria for a given mechanism $\mathcal{M}$ and a
given common prior $\mathbf{\pi}$ and a given additional information structure
$\mathcal{T}\in\mathbf{T(\pi)}$ is denoted by
$\Sigma(\mathcal{M},\mathbf{\pi},\mathcal{T})$.
Given a common prior $\mathbf{\pi}$ and an additional information structure
$\mathcal{T}\in\mathbf{T(\pi)}$, the expected regret is
$ER^{\prime}(\mathcal{M},\mathbf{\pi},\mathcal{T},\sigma)=\int_{\mathbf{v,s}}\\{\sum_{j=1}^{J}\max_{i\in\mathcal{I}}v_{i}^{j}-\sum_{i=1}^{I}t_{i}(\sigma(\mathbf{v,s}))\\}d\mathbf{\delta(v,s)}$.
The designer evaluates a mechanism by its worst-case expected regret across
all possible common priors and consistent additional information structures
and equilibria. Formally, the designer evaluates a mechanism $\mathcal{M}$ by
$GER^{\prime}(\mathcal{M})=\sup_{\mathbf{\pi}\in\Delta(V)}\sup_{\mathcal{T}\in\mathbf{T(\pi)}}\sup_{\Sigma(\mathcal{M},\mathbf{\pi},\mathcal{T})}ER^{\prime}(\mathcal{M},\mathbf{\pi},\mathcal{T},\sigma)$.
The designer’s goal is to find a mechanism with the minimal worst-case
expected regret. Formally, the designer aims to find a mechanism, referred to
as a min-3max regret mechanism, that solves the following problem:

$\inf_{\mathcal{M}}GER^{\prime}(\mathcal{M}).$

######  Theorem 1’.

The mechanism $(M^{*},\mathbf{q^{*},t^{*}})$ is a min-3max regret mechanism.

###### Proof.

For adversarial nature’s strategy, let the common prior be $\mathbf{\pi^{*}}$
and the set of additional information $S$ be a singleton. The proof of Theorem
1 then applies. ∎

Intuitively, adversarial nature cannot generate strictly more expected regret
even though it can use additional information structures because the mechanism
$(M^{*},\mathbf{q^{*},t^{*}})$ is strategy-proof.

## References

  * Anwar et al., (2006) Anwar, S., McMillan, R., and Zheng, M. (2006).  Bidding behavior in competing auctions: Evidence from ebay.  European Economic Review, 50(2):307–322.
  * Armstrong and Vickers, (2010) Armstrong, M. and Vickers, J. (2010).  A model of delegated project choice.  Econometrica, 78(1):213–244.
  * Ashenfelter and Graddy, (2003) Ashenfelter, O. and Graddy, K. (2003).  Auctions and the price of art.  Journal of Economic Literature, 41(3):763–787.
  * Athey et al., (2013) Athey, S., Coey, D., and Levin, J. (2013).  Set-asides and subsidies in auctions.  American Economic Journal: Microeconomics, 5(1):1–27.
  * Baron and Myerson, (1982) Baron, D. P. and Myerson, R. B. (1982).  Regulating a monopolist with unknown costs.  Econometrica, 50(4):911–930.
  * Bergemann and Schlag, (2011) Bergemann, D. and Schlag, K. (2011).  Robust monopoly pricing.  Journal of Economic Theory, 146(6):2527–2543.
  * 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.
  * Brooks and Du, (2021) Brooks, B. and Du, S. (2021).  Optimal auction design with common values: An informationally robust approach.  Econometrica, 89(3):1313–1360.
  * Caldentey et al., (2017) Caldentey, R., Liu, Y., and Lobel, I. (2017).  Intertemporal pricing under minimax regret.  Operations Research, 65(1):104–129.
  * 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.
  * Carrasco et al., (2017) Carrasco, V., Luz, V. F., Kos, N., Messner, M., Monteiro, P., and Moreira, H. A. (2017).  Optimal selling mechanisms under moment conditions.  Available at: https://bibliotecadigital.fgv.br/dspace/handle/10438/27677.
  * 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 Li, (2018) Chen, Y.-C. and Li, J. (2018).  Revisiting the foundations of dominant-strategy mechanisms.  Journal of Economic Theory, 178:294–317.
  * Chung and Ely, (2007) Chung, K.-S. and Ely, J. C. (2007).  Foundations of dominant-strategy mechanisms.  The Review of Economic Studies, 74(2):447–476.
  * Condorelli and Szentes, (2020) Condorelli, D. and Szentes, B. (2020).  Information design in the holdup problem.  Journal of Political Economy, 128(2):681–709.
  * Cramton et al., (2002) Cramton, P. et al. (2002).  Spectrum auctions.  Handbook of telecommunications economics, 1:605–639.
  * 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.
  * Daskalakis et al., (2014) Daskalakis, C., Deckelbaum, A., and Tzamos, C. (2014).  The complexity of optimal mechanism design.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1302–1318. SIAM.
  * Du, (2018) Du, S. (2018).  Robust mechanisms under common valuation.  Econometrica, 86(5):1569–1588.
  * Feldman et al., (2020) Feldman, M., Fu, H., Gravin, N., and Lucier, B. (2020).  Simultaneous auctions without complements are (almost) efficient.  Games and Economic Behavior, 123:327–341.
  * Filiz-Ozbay et al., (2015) Filiz-Ozbay, E., Lopez-Vargas, K., and Ozbay, E. Y. (2015).  Multi-object auctions with resale: Theory and experiment.  Games and Economic Behavior, 89:1–16.
  * Goeree and Holt, (2005) Goeree, J. K. and Holt, C. A. (2005).  Comparing the fcc’s combinatorial and non-combinatorial simultaneous multiple round auctions: Experimental design report.
  * Guo and Shmaya, (2019) Guo, Y. and Shmaya, E. (2019).  Robust monopoly regulation.  arXiv preprint arXiv:1910.04260.
  * Guo and Shmaya, (2021) Guo, Y. and Shmaya, E. (2021).  Project choice from a verifiable proposal.  Technical report.
  * Güth et al., (2005) Güth, W., Ivanova-Stenzel, R., and Wolfstetter, E. (2005).  Bidding behavior in asymmetric auctions: An experimental study.  European Economic Review, 49(7):1891–1913.
  * Hafalir and Krishna, (2008) Hafalir, I. and Krishna, V. (2008).  Asymmetric auctions with resale.  American Economic Review, 98(1):87–112.
  * Hayashi, (2008) Hayashi, T. (2008).  Regret aversion and opportunity dependence.  Journal of Economic Theory, 139(1):242–268.
  * He and Li, (2022) He, W. and Li, J. (2022).  Correlation-robust auction design.  Journal of Economic Theory, 200:105403.
  * Koçyiğit et al., (2020) Koçyiğit, Ç., Kuhn, D., and Rujeerapaiboon, N. (2020).  Regret minimization and separation in multi-bidder multi-item auctions.  Available at SSRN 3636395.
  * Koçyiğit et al., (2021) Koçyiğit, Ç., Rujeerapaiboon, N., and Kuhn, D. (2021).  Robust multidimensional pricing: Separation without regret.  Mathematical Programming, pages 1–34.
  * Krishna, (2009) Krishna, V. (2009).  Auction theory.  Academic press.
  * Manelli and Vincent, (2007) Manelli, A. M. and Vincent, D. R. (2007).  Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly.  Journal of Economic Theory, 137(1):153–185.
  * Maskin and Riley, (2000) Maskin, E. and Riley, J. (2000).  Asymmetric auctions.  The Review of Economic Studies, 67(3):413–438.
  * McAfee et al., (1989) McAfee, R. P., McMillan, J., and Whinston, M. D. (1989).  Multiproduct monopoly, commodity bundling, and correlation of values.  The Quarterly Journal of Economics, 104(2):371–383.
  * Milnor, (1951) Milnor, J. (1951).  Games against nature.  Technical report, RAND PROJECT AIR FORCE SANTA MONICA CA.
  * Myerson, (1981) Myerson, R. B. (1981).  Optimal auction design.  Mathematics of Operations Research, 6(1):58–73.
  * Renou and Schlag, (2011) Renou, L. and Schlag, K. H. (2011).  Implementation in minimax regret equilibrium.  Games and Economic Behavior, 71(2):527–533.
  * Roesler and Szentes, (2017) Roesler, A.-K. and Szentes, B. (2017).  Buyer-optimal learning and monopoly pricing.  American Economic Review, 107(7):2072–80.
  * Savage, (1951) Savage, L. J. (1951).  The theory of statistical decision.  Journal of the American Statistical association, 46(253):55–67.
  * Stoye, (2011) Stoye, J. (2011).  Axioms for minimax regret choice correspondences.  Journal of Economic Theory, 146(6):2226–2251.
  * Wald, (1950) Wald, A. (1950).  Statistical decision functions. Wiley.
  * (43) Zhang, W. (2021a).  Correlation robustly optimal auctions.  arXiv preprint arXiv:2105.04697.
  * (44) Zhang, W. (2021b).  Robust bilateral trade mechanisms with known expectations.  arXiv preprint arXiv:2105.05427.