On the Robustness of Mechanism Design under Total Variation Distance
Authors: Anuran Makur
Marios Mertzanidis
Alexandros Psomas
Athina Terzoglou
Venue: NeurIPS 2023 poster (2023)
Keywords: mechanism design
revenue maximization
correlated distributions
total variation distance

Abstract: We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distribution $D$, and we are interested in designing a (truthful) mechanism that has good performance for all "true distributions" that are close to $D$ in Total Variation (TV) distance. We show that DSIC and BIC mechanisms in this setting are strongly robust with respect to TV distance, for any bounded objective function $\mathcal{O}$, extending a recent result of Brustle et al. ([BCD20], EC 2020). At the heart of our result is a fundamental duality property of total variation distance. As direct applications of our result, we (i) demonstrate how to find approximately revenue-optimal and approximately BIC mechanisms for weakly dependent prior distributions; (ii) show how to find correlation-robust mechanisms when only ``noisy'' versions of marginals are accessible, extending recent results of Bei et. al. ([BGLT19], SODA 2019); (iii) prove that prophet-inequality type guarantees are preserved for correlated priors, recovering a variant of a result of D{\"u}tting and Kesselheim ([DK19], EC 2019) as a special case; (iv) give a new necessary condition for a correlated distribution to witness an infinite separation in revenue between simple and optimal mechanisms, complementing recent results of Psomas et al. ([PSCW22], NeurIPS 2022); (v) give a new condition for simple mechanisms to approximate revenue-optimal mechanisms for the case of a single agent whose type is drawn from a correlated distribution that can be captured by a Markov Random Field, complementing recent results of Cai and Oikonomou ([CO21], EC 2021).

On the Robustness of Mechanism Design under Total Variation Distance
Anuran Makur Purdue University
Marios Mertzanidis
Alexandros Psomas Purduc University apsomas9cs purdue. edu
Purdue University
amakur@purdue edu
umertzan@purduee edu
Athina Terzoglou
Purdue University aterzogl@purduut @purdue-...... edu
Abstract
We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distribution D, and we are interested designing a (truthful) mechanism that has good performance for all "true distributions" that are close to in Total Variation (TV) distance. We show that DSIC and BIC mechanisms in this setting strongly robust with respect to TV distance, for any bounded objective function O, extending a recent result Brustle et al. ([BCD20), EC 2020). At the heart of our result is fundamental duality property of total variation distance. As direct applications approximately revenue-optimal and approximately BIC mechanisms for weakly dependent prior distributions; (ii) show how to find correlation-robus mechanisms when only "noisy" versions of marginals are accessible, extending recent results of Bei et. al. ([BGLT19), SODA 2019); (iii) prove that prophet-inequality type guarantees are preserved for correlated priors, recovering variant of result of Dütting and Kesselheim ([DK19], EC 2019); (iv) give new necessary condition for correlated distribution to witness an infinite separation revenue between simple and optimal mechanisms, complementing recent results of Psomas et al. (PPSCW22), NeurIPS 2022): (v) give a new condition for simple mechanisms approximate revenue-optimal mechanisms for the case of single agent whose type is drawn from correlated distribution that can captured by Markov Random Field, complementing recent results of Cai and Oikonomou ([CO21], EC 2021).
our result, we (i) demonstrate how to find
Introduction
Mechanism design studies optimization in strategic settings. The designer's task is create mechanism that interacts with strategic agents, each with their own, private preferences over the mechanism's 's output. The inability to provide meaningful guarantees for important objectives such as revenue when studying mechanism design problems through the lens of worst-case analysis, has motivated the study of Bayesian mechanisms. In the Bayesian setting, there probability distribution, typically known to the designer, from which agents' private information their rypes drawn, and the designer seeks to maximize an objective function expectation over the randomness of the types, and, at the same time, incentivize the agents to report their type truthfully.
While we have greatly deepened our understanding of mechanism design under the Bayesian setting, when taking this approach to practice, it is natural to ask what happens if the designer has only partial information about the agents' type distributions. In recent years, a growing literature studies
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the robustness of mechanisms with respect to inaccurate priors. The term "robustness" can mean many things in this context, such as mechanism design using only sampling access from the under- lying prior [CR14, HMR15, DHP16, MR16, CD17, GHZ19, GW21], or mechanism design using only parametric knowledge of the underlying prior [AMDW13, Car17, GL.18 BGLT19, GPTD23]. Arguably, the most ambitious line of work in this thread strives to, given a prior distribution D. design mechanism that provides good guarantees simultaneously for all "true distributions" D that are close to D under some notion of statistical distance. Recent, compelling positive re- sults [BS11, CD17, DK19, LLY19, BCD20] show that this endeavor is, in fact, possible.
In this work, we demonstrate that large class of such robustness results can be obtained from a fundamental duality property of total variation distance. We distill this key property into various forms that are directly applicable to mechanism design, and then illustrate how they imply a variety of robustness results for both Dominant Strategy Incentive Compatible (DSIC) and Bayesian Incentive Compatible (BIC) mechanisms. In particular, we recover a litany of known results, such as the revenue robustness of BIC mechanisms of [BCD20] and robustness of prophet inequalities of [DK19], as well as prove several new results, such as a new necessary condition for a prior distribution to exhibit a large gap between simple and optimal mechanisms (complementing recent results of [PSCW22J).
Our Contributions. We consider the problem of a designer that wants to design a mechanism that maximizes a bounded objective function O when allocating items to n strategic agents. Agent i has a private type t; E Tú, drawn from a probability distribution Di, which specifies her value for every subset of items S C [m]. We write D for the joint distribution over agents' types.
We start in Section by proving a simple, but crucial lemma, Lemma 2, about non-truthful mecha- nisms in this setting. Lemma 2 states that the expected performance, with respect to the objective O, of a (possibly non-truthful) mechanism M is stable with respect to small changes in total varia- tion (TV) distance to the underlying prior distribution. This lemma follows from the argument for Kantorovich- Rubinssteinn duality of TV distance [LPW09, Vi109].
Appropriate applications of Lemma 2 allow us to prove our first robustness result: DSIC mechanisms are strongly robust. Specifically, given a mechanism M that is ex ex-post individually rational (ex-post IR), DSIC, and an a approximation to the optimal mechanism for a distribution D (w.r.t. the objective O), we construct ex-post IR and DSIC mechanism M that is agnostic to D and approximates, under distribution D. the performance of the optimal mechanism for D (w.r.t. O) minus a small error which depends on the TV distance, dtv (D, D) of DD and D (Theorem 1). Notably, D and D need not be product distributions, and if they have the same support, M is the same mechanism as M.
We proceed to study the robustness of BIC mechanisms. As opposed to the DSIC case, the BIC property is not maintained under small perturbations of a prior, or even by small changes in the support of a distribution. Rather surprisingly, however, in Lemma 4 we show that a mechanism
M that is BIC w.r.t. distribution D, is also approximately BIC w.r.t. distribution D, where the approximation depends on the distance between D and D. Combined with Lemma 2, we show our main robustness result for BIC mechanisms (Theorem 2): mechanism M that is BIC w.r.t D is approximately BIC w.r.f. D. and its performance for an objective function O is similar under D and D, as long D and D have the same support. Compared to the corresponding robustness result of [BCD20], Theorem only holds if D and D have the same support. Furthermore, M is not E-BIC (as in [BCD20D, but (e, -BC (see Section 2). On the other hand, our robustness results hold for arbitrary objectives, not just revenue, and arbitrary distributions, not just product distributions.
In Section 4 we show numerous applications of our robustness framework. Specifically, we give five applications. First, in Section 4. we extend our strong DSIC robustness to BIC mechanisms, albeit only for the revenue objective and product distributions. That is, we show that given a distribution D that is close to a product distribution DP, approximately optimal (w.r.t. revenue) and BIC mechanisms for DP can be transformed into approximately optimal and approximately- -BC mechanisms for D (Theorem 3). En route, we prove self- that constructs e' BIC mechanism w.r.t. D, given an (E, 9) -BC mechanism w.r.t. D, that might be of independent interest.
In Section 4.2 we study the correlation-robust framework of [BGLT19] (first introduced in [Carl I7D. At a high level, we are given the marginals of n dependent agents for single item. The goal is to design mechanism that maximizes (among all feasible mechanisms) the minimum, over all possible

---

joint distributions consistent with the given marginals, expected revenue. We extend our robustness results to this setting (Theorem 4), and get implications for the max-min revenue performance of sequential posted prices and the Lookahead auction when the given marginals are inaccurate.
In Section 4.3 consider prophet inequalities. In the simplest version of this problem, we are shown n non-negative numbers, t tn. one at a time, and upon arrival we need to decide (immediately and irrevocably) whether we should accept t,, or keep going. f,5 are drawn independently from known distributions D;. A celebrated result, known as the prophet inequality, states that simple threshold policy T ("pick the first z; bigger than r") has expected reward at least half of a prophet, who knows the values of all 2,5 in advance (and can therefore get reward max; t.). Prophet inequalities have numerous applications in mechanism design, and are the main tool in the analysis of posted price mechanisms. Observing that prophet inequalities correspond to sequential posted prices, which are DSIC mechanisms, and applying Lemma 2 for the welfare objective, we get robustness of prophet inequalities (Corollary 1); as a special case of our application we recover a variant of a result of Dütting and Kesselheim [DK19] on the TV robustness of prophet inequalities.
Finally, in Section 4.4 we apply our robustness framework to study revenue gaps between simple and optimal mechanisms. Here, [BCKW15, HN19] construct correlated distributions whose revenue is infinite, but such that simple mechanisms (e.g.. those with finite menus) cannot extract a lot of revenue. Recently, Psomas et al. [PSCW22] provide (arguably, complex) conditions that distribution DD should satisfy in order to witness such large gaps; our framework readily provides new, simple, and necessary conditions (Corollary 2), complementing the results of [PSCW22]. On similar note, Cai and Oikonomou [CO21] escape the negative results of [BCKW15 15, HN19] by considering distributions described by a Markov Random Field (MRF). Their revenue guarantees for simple mechanisms are controlled by A, parameter of the MRF, that is determined by how much the value of an item can be influenced by values of other items. We show that bound on the TV distance to product distribution also suffices to provide guarantees on the revenue of simple mechanisms (Proposition 2). Furthermore, under conditions on the MRF, bounds on A imply bounds on this distance (Proposition 4). but the other direction is not necessarily true (Proposition 3); thus, getting bounds on the TV distance of an MRF to a product distribution is a meaningful endeavor.
Related Work. A number of recent works study robustness in mechanism design; see [Carl7] for a survey. The paper (thematically and technically) closest to ours is [BCD20], which proves the robustness of the revenue objective for BIC mechanisms under various notions of statistical distance, including TV and Prokhorov, as well as Lévy and Kolmogorov for single parameter settings. Specifically, given a distribution D. [BCD20] show how to construct a mechanism that is (approximately) BIC, and performs well, when executed on any distribution D that is close to D. Here, focus on TV distance, and recover their result for this case, slightly extending it for the case of revenue, and significantly extending it under some minor assumptions. Dütting and Kesselheim [DK19] study prophet inequalities with inaccurate priors. Specifically, given product distribution X SEjmm] D, [DK19] study policies that perform well when executed on a product
distribution [m] D.. such that D, is close D. for all E [n], under various statistical distances. As an application of our robustness for DSIC mechanisms, we recover and extend to non-pro non-product distributions their result for TV distance, for the special case of sequential posted prices.
A related, but different, approach is to assume sample access to the underlying distribution [CR14, HMR15, DHP16, MR16. CD17, GHZ19, GW21J. In this line of work, the goal is bound the number of samples necessary to design a near-optimal mechanism, or, given a fixed number of samples, design the best mechanism possible Robustness results of the former style, i.e., the current paper or [BCD20], sometimes imply sample complexity results, e.g., by arguing that using the samples, one can learn a distribution that is close to the real distribution, and then applying robustness results [BCD20]. We conjecture that similar results can be shown using our robustness framework, combined with estimation in TV distance [HJW15, DG85J, Another line of work [AMDW 13, Carl 17, GL18, BGLT19, GPTD23] assumes partial knowledge of the true prior distribution, e.g., its mean or the marginals of correlated distribution. The goal to find the mechanism that (approximately) maximizes the worst-case performance with respect to the missing details (e.g., the CDF consistent with the mean or the joint distribution that respects the given marginals). Our results have implications for such settings as well. Finally, certain works consider the robustness of pathological examples in mechanism design, e.g., constructions of distributions that have infinite revenue gaps between simple and optimal mechanisms [BCKW15, HN19]. For example, [PSW 19] uses the lens of smoothed
3

---

analysis ([ST04)) to reason about the robustness of the [HN19] constructions. Our framework has implications about these constructions; specifically,, we give a new necessary condition for a distribution to be "pathological," complementing a recent result of [PSCW22).
From a probability theory perspective, heavily use coupling techniques. Couplings are general proof technique in probability theory with several historically notable uses [Doe38, Sko56, Kan60, Str65, Dud68, Wic70, Dob70] (also see [Vi109, Ka12IJ). Given two marginal distributions, the basic idea of coupling is to construct a consistent joint distribution on a common probability space in order to deduce certain relationships between the marginals. The key coupling used in this work Dobrushin's 's optimal coupling minimizes the probability that two random variables with given marginal distributions are different, and has been historically utilized to develop sharper results on Markov chain ergodicity, cf. [Dob70, Dob71, 1, Gri75]. It turns out that this optimal coupling also defines total variation distance, cf. [L.PW99, Vi109]. Such distances exhibit Kantorovich-R Rubintteen duality and are characterized by the maximal difference of expected values with respect to the given marginal distributions [Kan60, LPW09, Vi109]. In this work, we distill how optimal couplings and duality for total variation can be used in yet another setting: mechanism design.
2 Preliminaries
We examine the problem of a central designer who seeks to create a mechanism that maximizes an objective function given some prior knowledge of the universe. Consider a set [x] _ (1.....7) n) of selfish agents and finite set [m]] ê {l..... m) of items. Each agent i [n]] has a type &, belonging to a set Ti of possible types. We assume that, for all i E [ra]. there exists special type - E T. interpreted as the option of not participating in the designer's 's mechanism. Let 7 = Ti x ... x Tn. We use X' to denote the set of all possible allocations of the items. (In particular, the sets X' and T; are typically standard Borel spaces, e.g., finite-dimensee dimensional Euclidean spaces. Hence, our analysis with couplings and total variation distance in the sequel do not require measure theoretic arguments.)
The goal of the designer is to construct mechanism M (ar, p) which consists of (1) an allocation rule x: T + (AY), which maps reported types (41,...,4,) E T to a distribution over allocations, and (2) a payment function p: T > [-H, H, H]" which maps reported types to (bounded) payments for each agent, for some fixed constant H > O. We say that mechanism M = (x, p) is defined on types T if the domain of x and p is T. We write M(t) = (xt)) for the outcome, i.e., the allocation and payments, of mechanism M on input & E T.
Each agent i has a valuation function U; : T, X X + [0. H). which specifies their value for an allocation, given their type. We assume that agents are quasi-linear i.e., the utility of agent i, with type t,, for an allocation A and a payment ps is equal 8s (t, A) - Pi. We overload notation and write 4, (M((s,
for the utility of agent with type 4 E To for the outcome of the mechanism M on input (4z, t)) We use F for the set of possible outcomes of a mechanism M. We assume that there exists probability distribution DD supported on T from which agents' types are drawn.
Mechanism Design Considerations. When faced with a mechanism M, each agent reports a type by E Ti to the mechanism. We aim to design mechanisms that (approximately) incentivize agents to report their true types, so we typically have that b, = t,, for all i E [n]. Given a mechanism f,, for the difference in utility of agent i when she reports t E Ti
M, we write uz a,MMt, (t, instead of her true type t, E Tr and all other agents report according to t. E T_ That is, (M(4, (-)) 1, (M(G,
uiM(: - (,,,,,
We consider four, increasingly weaker, notions of incentive compatibility. First, we say that a mechanism M is Dominant Strategy Incentive Compatible (henceforth, DSIC) if an agent is better off reporting her true type, no matter what other agents report, i.c., for all i E [n]], every type t, E T. possible misreport E E T, and types t_: E T_; for the remaining agents, it holds that Mt - t t..) 2 O. Second, mechanism M is Bayesian Incentive Compatible (henceforth BIC) with respect to a distribution D. if an agent better off reporting her true type in expectation over the other agents' reports, i.e. if for all i E [r)), every type I, E T; and possible misreport I E T, it holds that E, ED [MgM(t < 1, :)) 2 0. Third, mechanism M is E-BIC w.r.t. D if for all i [n). and all t,, f E Te, it holds that E, g~D :lt; [u.M(,, (t, t, t-] 2 -E. Fourth, mechanism M is (E.g)-BIC w.r.t. D if it is e- E-BIC with probability at least 1 q, i.c., if for all i e [n)], and all

---

t,,t, E Tú, PII,ND, E, cnD :ls [uf (t: t t. -E] 21-q. An (s, O)-BIC mechanism is simply E-BIC, and a O-BiC is simply BIC.
Finally, mechanism_ M is ex-post Individually Rational (henceforth ex ex-post IR) if for every agent i E [n]. every type Ti and types L-; E T-, for the remaining agents, it holds that 1, (M(t,, (-))) O.
The Designer's Objective. The designer has an objective function O(..)) x F [a. b] that takes as input agents' (reported) types / E T and mechanism outcomes M(() E J (noting that the mechanism's outcome might be a randomized allocation) and outputs real number the interval (a, bj. Let V = b a. The task of the designer is to find an ex-post IR and truthful mechanism (under one of the aforementioned notions of truthfulness) that maximizes this objective function in expectation over the randomness of D. We denote the optimal value of the objective O under distribution D by OPo (D). We specify in context whether this is with respect to DSIC, or BIC, or e-BIC mechanisms. A mechanism MG is a approximation to the optimal mechanism under D, with respect to O, if ELnD [O(t, Mt))] 2 (OPTo(D).
Some of our results hold for arbitrary, bounded objectives O. Two objectives of specific interest to us will be welfare and revenue. The welfare objective, denoted by V.l(.), is simply the sum of agents' valuations of an outcome, i.e. Val((, = Eie(n) oz(12,z;(1)) where xx(() is the allocation of agent in the outcome M(t). The revenue objective, denoted by Rev(.), the sum of agents' payments, i.e. Rev(t, M(()) = Eie(m) P: (t),,, where p; is the payment of agent i in the outcome M(t). We often overload notation and write (ev(M, D) for the expected revenue of mechanism M under distribution D, i.c. Rev(M, D) = ELED [Re
To maintain consistency with the (vast) literature on mechanism design we further denote the optimal revenue (ev(D). and the optimal welfare as V (D), under distribution D.
Statistical Distance. Throughout the paper, we are interested in how mechanisms behave under different distributions that are not "too far" from each other. Our notion of distance in this paper is total variation distance.
Definition 1 (Total Variation Distance). The total variation (TV) distance between any two probability distributions P and Q on a sample space Q2 is defined as
dtv (P, Q) A sup IP(E) - Q(E), RCQ
where the supremum is over all Borel measurable subsets E C S2 and P(E) (resp. Q(E)) denotes the probability of the event E with respect to the distribution P (resp. Q).
We note that Z is either diserete our analysis, and hence, it is always a standard Borel space. For any probability distributions P and Q on Ω2 let [[P, Q) be the (non-empty) set of all couplings of P and Q, i.e., all joint probability distributions ? = Px,y of two random variables X, Y E Ω such that the marginal distributions are Px P and P = Q. respectively. The following definition will be of utility in the sequel [Dob70, LPW09].
measurable subset of minite-dmeessinall Euclidean space in
Definition 2 (Optimal Coupling). For any two probability distributions P and Q on P, we define the optimal coupling of P and Q as the joint distribution 7 = arg min, Ex [1{X + YJ of two random variables (X, Y) that has marginal distributions P and Q of X and Y, respectively, and minimizes the probability that X is different to Y.
We note that such an optimal coupling always exists [Dob70, Vi109]. The next lemma presents several useful characterizations of TV distance including an optimal coupling representation (which demonstrates how TV distance is Wasserstein distance with respect to the discrete metric [Vil09]); see [Mak19, Section 2.2.1] and [PW22, Theorem 7.7] for a compilation of other characterizations. Lemma 1 (Equivalent Characterizations of TV Distance [Str65, Dob70, LPW09, Vi109]). For any two probability distributions P and Q on Ω we have
drv (P,Q) = 2 P QQ111
min
Pr(XyVI~ [X [Y
(EI((P.))
Ex-p [((X) - Ey (S(Y),,
max
/00---2
2.21
5

---

where -P- is the L' --isstance between P and Q, the second equality is the optimal coupling characterization which minimizes yr [X + YJ E y [1 & Y over all couplings
y of P and Q, and the third equality is the Kantorovich- Rubinstenn dual characterization which takes the maximum over all (measurable) functions f + R bounded by supten (f()) S
Robustness of Mechanisms Under Total Variation Distance
In this section, we prove our robustness results for DSIC and BIC mechanisms. Missing proofs throughout the section are deferred to Appendix A.
At the heart of our approach lies the following lemma, which shows that, even for correlated prior distributions, assuming truthful bidding, a mechanism's 's performance with respect to an arbitrary objective function O is stable under small perturbations to the prior.
Lemma 2. Let P and Q be two arbitrary probability distributions supported on T and let M be any mechanism. Assuming truthful bidding, for all objective functions ( [a, bj. letting V = b
holds that Evp M(t)) Exrq ((tt', S V dPv
We note that M in the statement of Lemma 2 may not be DSIC BIC, for neither P nor Q.
Proof of Lemma 2. The objective function is lower bounded by a and upper bounded by b; thus, we have that for any 1, T, (())) O M((') s V 1 * ('). Since this inequality holds for all t, E TT it also holds after taking an expectation with respect to any coupling of P and Q and specifically for the optimal coupling 7 between P and Q (see Definition 2):
Bawrr (O(,, O(t', M(()) S V Eagyr [1te + (')..
(I)
Using the second form of Lemma 1, the RHS (1) is equal to V drv (P,Q). For the LHS of (1), using linearity of expectation, the fact that (t,, does not depend on E', and the fact that Ott,, ((t))( does not depend on we have that (') (O(t, Ex~q [O M(t)) Putting everything together, we get the desired inequality.
O(t', MM('))] E.-p [O M(t))
In the remainder of this section, we show that this lemma can be used to prove strong robustness results for DSIC and BIC mechanisms.
3.1 DSIC Mechanisms
Our main robustness result for DSIC mechanisms is stated as follows.
Theorem 1 (Robustness for DSIC), Let 'D and D be two arbitrary distributions supported on T, respectively, such that drv (D.D) s 5, and let ((..-) [a, b) be objective function. Let MG be an ex-post IR, DSIC, and a-approximate mechanism (under DD, with respect to the optimal (under D) ex-post IR and DSIC mechanism for O, Then, letting V a, it holds that
En (O(t, 2 OPTo (1+
where OPTo(D) is the performance of the optimal (for O) DSIC mechanism.
Proof. We apply Lemma 2 twice. First, choosing P D, Q = D, and M -Mg, Lemma implies END (O(t, (t) Eyra (O MS (t))) < V dTv (D.)) < V.
Now, let M be the optimal (under D) ex post IR and DSIC mechanism for O. Using the definition of Mg. and re-arranging we have
BynD MO''',
> EnD
V
2 a Er (t) 1 V5
> a B.ND 0 ((..M)(1)) V8,

---

where the last inequality is because M is feasible (i.e. ex-post IR and DSIC) for D. Sec- ond, choosing P D Q = D, and M = MM. by Lemma 2, plus re-arranging, we have that V Combining these inequalities we have: B (Ott, Mb((M) 2 a L [5(L.M)(0)) - -1+
BU'DD BAND [O 2 ELD (²,
Intuitively. Theorem states that, if mechanism is approximately optimal for D, then it is also approximately optimal for all DD that are close in total variation distance, paying small additive error. Note that neither 'D nor D needs to be product distribution. That is, if D and D have the same support, DSIC mechanism M performs pagroximateel-opimmalll under D. Finally, notice that in the above theorem, we assume that the D and share the same support; in Appendix A. we relax this assumption, and show how to modify the mechanism MD in a way that is agnostic to D, and provide exactly the same guarantee.
3.2 Bayesian Incentive Robustness
In this section, we study BIC mechanisms. As opposed to DSIC mechanisms, arguing about whether BIC mechanism remains BIC after perturbing the prior distribution is a lot more involved. Our goal in this section to prove that the BIC property degrades gracefully as a function of the TV distance, even for arbitrary objectives, albeit, with two small technical caveats (compared to the
DSIC robustness): (1) D and D must share the same support, and (2) the incentive guarantees of our mechanisms also degrade. The second requirement is necessary; in Section 4.1 we show how to bypass the first requirement for the revenue objective, recovering a slightly stronger version of TV robustness result of Brustle et al. [BCD20].
First, we need the following Markov-like technical lemma that when two joint distributions Px,Y, Qx,y are close in TV distance, then, with high probability, the conditional distributions Py|x= Qyxx== are also close in TV distance.
Lemma 3. Let Px.y, Qx.y be two probability distributions for the (possibly multivariate) random variables X and Y. Let Py]x== (resp. Qy(x=z) be the probability distribution of Px,x (resp. Qx.Y) conditioned on X = I and let Qx be the marginal probability distribution of X as dictated
by Qx... Then, for all E [0, Przwex dTv (Pylx=r: Qx(x==) 2d xxxx)) S.
Next, we prove that a BIC mechanism for D is (e, g)-BIC for D, assuming that D and DD have the same support and small TV distance.
Lemma 4. Let D and D be two probability distributions supported on T, with drv (D.D) S
If M is an ex- ex-post IR and BIC mechanism w.r.t. 'D then it is also an ex-post IR and (886 mechanism w.E.t D, for all E 1).
9 -BC
To prove the above lemma we leverage Lemma 3. We know that with high probability the perception of each agent over the distributions of the rest of the agents is very close under D and D. That is why, if agent cannot gain by misreporting under D, then with high probability, she cannot significantly increase her utility by misreporting under D.
As direct implication of Lemma 2 and Lemma 4 get our main robustness result for BIC.
Theorem 2 (Robustness for BIC). Let D and D be two arbitrary distributions supported on T, such that dTv (D.D) < 8, and let ((.,.) E [a, b] be an objective function. Let MD be a mechanism
9 .9) .) -BIC w.r.t. D. for all that is ex ex-post IR and BIC w.r.t. D. Then Mp is also ex-post IR and SHE E [0. 1). Also, letting V = b - it holds that E,5 (1,,, (OL,,MD())) > END (O(,, (1)) - V8.
Comparing to the corresponding result of Brustle et al. [BCD20], Theorem 2 only holds if D and D have the same support. Also, the guarantee incentives is weaker: MD is not e-BIC (as in (BCD20]), but (E, BBCC. However, our robustness results holds for arbitrary objectives, not just revenue, and arbitrary distributions, not just product distributions.
7

---

On Tightness of Robustness Results. Regarding Lemma 2, it is known that Ex-p [f())
Ex-qlf(X) S drv Q) for all functions f bounded by 1/2 (see Lemma 1), and equality holds for the function (*(())) = 1/2 if P(x) 2 Qxx) and (*(x) -1/2 otherwise. We can use this to show that equality holds for Lemma when the objective function and the mechanism, combined, look like this function, i.e., (*) = (z, M(x)) (with appropriate re-scaling when V is not 1).
This yields a sufficient condition for tightness of Lemma 2.
Regarding Theorem 1, it is straightforward to construct tight example for the case of revenue and welfare. For instance, for the case of single agent, letting T [0. V1. consider the case that the distribution P is a point mass at V, and distribution Q takes the value V with probability 1 - 6, and zero otherwise. The TV distance between P and Q is 6. Consider the simple mechanism M that posts a price of V. Its revenue/welfarr under P is V. and its revenue/welfare under Q is (1 -1-6 -... The main issue with generalizing to arbitrary objectives that worst-case arbitrary objective can do something uninteresting, e.g., take the value no matter what, where naturally our result is not tight.
Regarding Theorem 2, tightness of the revenue objective follows from the aforementioned tightness of Theorem 1 for revenue. Tightness for the BIC guarantee follows from the following example. Consider the single item case where two identical bidders have valuation I with probability 0.5 and valuation 2 with probability 0.5 independently from each other. Now consider the mechanism where the first bidder always takes the item if he bids 2 and pays 1.5. When he bids and the second bidder bids 1, he again takes the item and and now pays 1. Finally, if the first bidder bids 1 and the second bidder bids 2, then the second bidder takes the item and pays 2. For the specific distribution we selected, it is easy to check that this mechanism is BIC. Now assume that the second bidder's s distribution changes to having valuation with probability 0.5++ and with probability 0.5 e. The TV distance between the two distributions is exactly e. However our mechanism is no longer BIC. Whenever the first bidder's valuation 2. if he reports truthfully, he will always get 0.5 utility. If he instead reports 1, he will make 0.5 + e utility (on expectation). Taking into account this observation, we can see that our mechanism is now E-BIC.
Applications
In this section, we show a number of applications of Lemma 2, and Theorems I and 2.
4.1 BIC Mechanisms
We start by showing applications of our robustness results for the revenue objective of BIC mecha- nisms. Our goal is to extend our DSIC robustness result (Theorem 1) to BIC mechanisms. That is, we'd like, given an approximately optimal BIC mechanism for a distribution D, to get an approxi- mately optimal and approximately BIC mechanism for distribution D. We will achieve this goal for the revenue objective and product distributions; missing proof' can be found in Appendix B.
Towards our main result for this section, we prove the following lemma, which might be of inde- pendent interest. Intuitively, the lemma shows that one can turn an gBBIC mechanism into O(E + )) mechanism, paying a small loss in revenue.
Lemma 5. For any product distribution D Xie(m] Dr given a mechanism M that is ex-post IR and (e, BIC w.r.t. DD we can design mechanism M that is ex-post IR and O(e + =nHH) w.r.t. D, such that (ev(M, D) Rev(M, D) ngV.
Our main theorem for this stage is stated as follows.
Theorem Let D be a probability distribution supported on T, and let DP be a product distribution such that dtv (D, DP) < ò. Let M be an ex-post IR, BIC, and a-approximate mechanism (under DP), with respect to the revenue optimal (under DP) ex-post IR and BIC mechanism. Then, MG. is ex-post IR and 18H6 -q-BIC with respect to D. for all q E (0, 1]. Furthermore, Rev(MBp. D) Z
OPT(D)) - (11 V Vnvō).
In order to get the full benefits of Theorem 3, one needs the product distribution DP that is the closest (in TVV distance) to the original distribution D. Let be this optimal distance. The following proposition shows that, for every distribution D. the distance of to the product of its marginals is bounded by (n + 1)e, and therefore, Theorem 3 holds for every distribution D for 5 (n + 1)s.
8

---

D; be product distribution supported on Xie(n Tú and let D be joint distribution supported on Xse[m] Te. whose marginal over T; exactly D, Then, if there exists product distribution DP such that drv (D.D*) E. it holds that dTv (D,D) $ (n+1) 1)E.
Proposition 1. Let D
4.2 Marginal Robustness
As a second application, we consider the setting of Bei et al. [BGLT19). In this problem, we want to sell one item n dependent agents, and we only know the marginal distribution of each agent i. Overloading notation, let I E T, S R be the valuation of agent i for the item. There distribution D, supported on Xie[n] Ti, from which agents' valuations are sampled from. For the sake of simplicity, we only argue about discrete distributions; however, our re- sults easily extend to the continuous case. Let D; be the marginal distribution of agent i, i.e., Pre,D, [t, = u;] Ee_.ET_ Pr [t (v,, u-s)]. The designer knows marginal distributions D; for each i but not D. Given set of marginal distributions (D,. D.) II(), ,D,) be the set of all distributions consistent with such marginals, i.e. [T(,,, Dx) -D''Prr, (4 my] Ev_eT_, Pre- [t = (e%, u-=)] Vi [n], Vt, E Ti). Our goal is to find mechanism M such that M = arg max My ming'em(P)
.D.) ELND (O(I, where M is taken over possible ex-post IR and DSIC mechanisms. We can prove the following theorem.
Theorem 4. Given a set of marginals (D).... Da) and DSIC and ex-post IR mechanism M such that minpen(P...- .D.) BEND (I,, 2 a max minpeunDD.... .D.) EL-D [Ott, ([)]]
then any set of marginals (D,,... , D', such that for all i E [nl,, dtv (D,, D() I E, it holds that m "",,,, (D,) ELND OO,t, M (t)) max min P.)) BLWDY [O M' (1 + a)n=V.
The input to our problem is set of marginals; however, we do not sample from these marginals to compute our objective. Instead, these marginals are used in order to derive a new distribution from which we will sample. Therefore, we cannot immediately "black box" the results we have shown until now. To prove Theorem we first relate, and bound the "distance" between IT, ... .D,) and II(",,.. ................... D.)). Then, we need re-prove arguments equivalent to the ones used for our robustness results so far, while taking into consideration the min max nature of the problem. We postpone the formal proof of Theorem 4 to Appendix C.
[BGLT19] show that Sequential Posted Prices Mechanisms are a 4. ap78xapprox and there exists a Lookahead Auction that is a 2-approximation with respect to revenue for the above problem. Using Theorem 4, we can readily get implications for the robustness of those two auctions.
4.3 Prophet Inequalities
Here, we study the prophet inequality problem. Recall that in this problem, agents arrive over time; in the i-th step, we need (immediately and irrevocably) decide on the allocation of agent whose type 4 is drawn from a marginal distribution D. Our goal is to design a prophet inequality: a policy that competes with the optimal in hindsight welfare maximizing allocation. It is known that, in fairly general domains, one can achieve this goal using posted prices, i.e.. set price Pj for each item j. and let users pick their utility- utility-maximine maximizing subset of items [SC84, FGL14, RS17, KW 19, ANSS19, DKL20, DFKL20]: see [Luc17] 7] for survey. Using Lemma 2 for the welfare objective we prove robustness for prophet incqualities, noting that posted price mechanisms are ex-post IR and DSIC.
Corollary 1. For posted price mechanism M, and distributions D, D such that dTv (D.D) S 8. holds that V Val(M,)) D) 2 Val(M, V
Using Corollary for D = Xie(n] Dj and D Xie (x) that are product distributions, we can get the TV robustness result of Dütting and Kesselheim [DK19] ] for sequential posted prices as special case,
noting that (1) if drv (D.. D.) s E, then drv (D. D) < ne, and (2) if valuations are normalized to n.
[0, 1] (as in [DK19]),
4.4 Gaps between Simple and Optimal Mechanisms
Here, we show applications of our robustness results to the study of simple and approximately optimal mechanisms. Missing proofs are deferred to Appendix D.

---

Motivated by numerous negative results for revenue optimal auctions (see [Das15] for a sur- vey), a major research thread in mechanism design studies the performance of simple mecha- nisms [CHK07, CHMS10, CMS15, 15 RW15, CM16, CDW16, 16, C7.17, KW19, BILW20J. Two canonical mechanisms that are considered simple in this literature are: (1) the mechanism that sells each item separately (and optimally), and (2) the mechanism that optimally sells all items as grand bundle; let SRev(D) and (e) be the expected revenue of these mechanisms, respectively, under prior D. On the flip side, product distributions are known to witness simple mechanisms that are approximately optimal. For instance, Babaioff et. al. [BILW20] prove that for a single agent and product distribution D", max(SReu((D)) (ee((D)) 2 Rev(DD), even though the individual approximation factors for SRev(Di) (D)) and B (D)) are O(1/ lo)(m)) and 1 1/m, respectively [HN13, LY13J. Note that in the single-agent context, by product distribution, we mean with respect to items. The following observation is an immediate implication of Theorem 1.
Observation 1. Let SM be family of mechanisms, such that E [Ott,S S.. (t)) > a (D") for some objective O, where SM a mechanism in SM parameterized by the product distribution Dr. Then, for any (possibly non-product) distribution 'D that is close aOPTo(D) have that to some product distributions DP, and specifically, drv (D, S 2[1+a]V EY-D (Mrt,))) 2 @OPTo(D)
construction of Hart and Nisan [HN13] shows that there exists a non-product distribution D such that SRev(D) 2m, B Ree((D) I 2m but RD)(D) + Recently, [PSCW22] show necessary and sufficient conditions for a distribution D to exhibit such infinite gaps between the revenue of rather complex (namely, they
simple and optimal mechanisms. Unfortunately, these conditions conditions on the existence of infinite sequences of points with certain properties). Here, leveraging Observation 1 for the revenue objective, we complement results of [PSCW22] by giving a new, simple necessary condition that a "pathological" construction must satisfy:
Rev(D) Corollary 2. For a single agent and any distribution 'D such that (R) 2 2m it must be the case
Rev(D) E {((log(m)) that for any product distribution DD, drv (D, Z Rev(D) Furthermore, if SRev(D)
it must be the case that for any product distribution DD, drv (D, Z Ree(D)
As final application of our framework, we give new positive results simple mechanisms. Proposition 2. Let D be distribution supported on T, and let DP be a product distribution such that drv (D, DP) < 8. Then, we have max (D). (r) 2 1/ Rev(D) - - H...
Proposition 2 implies that the better of bundling and selling each item separately for a distribution D is a good approximation to (Dv( as long as D is close product distribution. Cai and Oikonomou [CO21] prove that the same mechanism is good approximation for dependent distribu- tions that can be captured by a Markov Random Field (MRF); see Appendix D for basic definitions regarding MRFs. The approximation ratio of [CO21] is controlled by A, parameter of the MRF that determined by how much the value of an item can be influenced by the values of the other items. Specifically, [CO21] prove that max ( Ree (D), B (R)) 2 12 Rev(D). In Proposition 3, we prove that there exist distributions such that the object of interest for Proposition 2, i.e., the distance to product distribution, is arbitrarily small, while the objective of interest for [CO21], the parameter A, is arbitrarily large. At the same time, in Proposition 4 we show that when the MRF parameter A is bounded, we can bound the distance of a distribution D to product distribution, for distributions that can be represented by MRFs that only have pairwise edges.
Proposition 3. For any O < k < 1/2, there exists a distribution 'D produced by an MRF with parameter A and a product distribution DD such that drv (D, DP) & 212 and A 2 4 log (2) Proposition 4. Let 'D be a distribution produced by an MRF with only pairwise edges. Then, there exists a product distribution DD such that dTv (D, DP) < min{ / vI - e -ma/2), where m the number of items.
Acknowledgments
Alexandros Psomas is supported in part by an NSF CAREER award CCF-2144208. Google Research Scholar Award, and Google AI for Social Good award. Athina Terzoglou is supported in part by an NSF CAREER award CCF-2144208. Marios Mertzanidis is supported in part by DOE award SC0022085, and NSF awards CCF-181404) CCF-2209509, and
10


Reviews:
[{"review_id": "0a35yBgbr0", "reviewer": "Reviewer_acoM", "summary": "This paper considers the design and performance guarantees of various mechanisms under prior distributions, and aims to provide a general account of what happens to these mechanisms and their guarantees when these (joint) prior distributions are perturbed. They use the definition of TV distance in terms of the largest difference in probabilities over all events and combine it with the assumption that the mechanisms in question have bounded values and payments in order to argue that expected values, rewards, and incentives are only incrementally affected by small perturbations in TV distance. This observation allows for the 'robustificaton' of a number of prior results. The authors present some more technically involved claims for settings involving product prior distributions and Markov random fields.", "questions": "Where is the crux of your invocation of duality, and how are you using the connection between these characterizations of TV distance?\n\nWhich of your robustness claims readily admit lower (upper?) bounds?\n\n\nPossible corrections:\nL195-196: Should Omega additionally be a measurable subset in order to be a standard Borel space?\nL213: is the supremum necessary?\nL244: \"inequality is because\"\nL310: epsilon used before it is introduced\nL376: \"distributions\"\nL384: is the Omega here intended to mean that there is some constant for which the claim holds?", "limitations": "Some of the theorem statements seem to be missing quantifiers and conditions, as well as informal overviews of their methods of proof.\n\nIt would be helpful to have more discussion of which dependences are necessary.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work considers a natural question, and aims to provide a systematic answer. \n\nThe applications and results are a combination of recovering prior robustness results and extending prior non-robust mechanisms and results to nearby joint prior distributions.", "weaknesses": "Upon some reflection it makes sense that the robustness guarantees the authors consider should contribute additive terms which depend on the maximum payment or reward in a mechanism. But for the bounds presented there are frequently other factors in the additive terms. This paper would benefit from discussion of lower bounds, and more generally from arguments that the forms of these guarantees make sense.\n\nMany of the claims are not stated along with all of the relevant conditions and caveats, for instance restrictions on boundedness and on the supports of distributions.\n\nThe proofs of some central claims are intuitive and straightforward, and at the same time many claims are lacking outlines of their proofs. The authors herald their usage of a \"fundamental duality property of total variation distance,\" but it is unclear in which proofs this duality is being used, or the sense in which it is being employed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions. We will update our theorems and lemmas, whenever applicable, to state the relevant conditions/restrictions necessary.\n\nBelow we answer your questions.\n\n- Where is the crux of your invocation of duality, and how are you using the connection between these characterizations of TV distance?\n\nThe key duality property of TV distance refers to the fact that it has two equivalent characterizations: 1) the maximum over bounded functions of the difference of expectations, and 2) the minimum over couplings of the probability that the two associated random variables are different. This property is presented in Lemma 1, and it is distilled in Lemma 2 in the context of mechanism design. Specifically, the result in Lemma 2 is really a form of (weak) duality that tells us that the difference between expected objective functions is bounded by TV distance. Its proof illustrates how we use the minimum coupling characterization of TV distance from Lemma 1. \n\nThis means that we are invoking duality of TV distance anywhere we are using Lemma 2. Lemma 2 is crucially used in both Theorem 1 (DSIC robustness) and in Theorem 2 (BIC robustness). Moreover, in the applications, we use it in Corollary 1 (Prophet inequality) and marginal robustness (Lemma 10, towards proving Theorem 4), in Lemma 7 in order to prove Lemma 5 ($(\\epsilon,q)$-BIC to $(\\epsilon + nqH)$-BIC reduction), and in the proof of Theorem 3 (application for BIC mechanisms).\n\nNote also that although the duality property of TV distance is related to notions like linear programming duality, we do not use any such form of duality to prove Lemma 2. Rather, Lemma 2 itself is proving a form of duality. We hope this clarifies our use of “duality”, and we are also happy to clarify this in the paper. \n\t\t\n- Which of your robustness claims readily admit lower (upper?) bounds?\n\nSee the “global” response for an answer to this question.\n\n- L195-196: Should Omega additionally be a measurable subset in order to be a standard Borel space? \n\nYes, $\\Omega$ must be measurable. This will be clarified in the paper.\n\n- L213: is the supremum necessary?\n\nThe supremum used in the dual characterization of TV distance could be replaced by a maximum, i.e., the maximizing function exists under our assumptions. This will be changed in the paper. (The supremum used to define the bound of 1/2 on the functions is necessary.)\n \n- L244: \"inequality is because\". L310: epsilon used before it is introduced. L376: \"distributions\". \n\nThank you for catching these; we fixed them.\n\n- L384: is the Omega here intended to mean that there is some constant for which the claim holds?\n\nCorrect."}, {"review_id": "PJ1DKY5ffV", "reviewer": "Reviewer_XhLk", "summary": "The paper studies a robust auction design problem for multiple items. In the model, the authors assume that they can access a (predicted) valuation distribution over all agents, and the total variance between the predicted distribution and the actual distribution is bounded. The goal is to design a truthful mechanism such that given any objective, the expected performance is robust with respect to the total variance bound. \n\nBoth DSIC and BIC mechanisms are considered in the paper. For the DISC setting, the paper shows that when the total variance is at most $\\delta$ and the length of the range of the objective function is at most $V$, if there exists a $\\alpha$-approximate mechanism (for the special case that $\\delta=0$), using the mechanism directly can return an expected objective at least $\\alpha OPT- (1+\\alpha) V \\delta$. For the BIC setting, the authors prove a similar theorem. They show that the difference between the objective obtained by a mechanism on two close valuation distributions is at most $V\\delta$. Several applications are mentioned in the paper. The authors illustrate how their ideas can be applied to these concrete applications. ", "questions": "Is there any negative result for the model? For example, could you give a concrete hard instance such that the difference is at least $V\\delta$? ", "limitations": "See weakness.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper extends the previous result on robust auction design and shows that for any objective function, once the range is bounded, we can obtain a robust mechanism with respect to the total variance easily. This result is interesting, and the basic idea might be useful in many other mechanism design settings.", "weaknesses": "One shortcoming of the proposed result is that the mechanism still does not have a performance guaranteed when the total variance is large. Maybe the authors could borrow some ideas from the learning-augmented algorithms and find an efficient way to combine the predicted mechanism and the traditional worst-case mechanism, such that the mechanism is still competitive even if the total variance is large.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for the thoughtful review and question. Indeed, when the total variation is large, our results don’t have any bite, which, of course, does not imply that some sort of robustness is impossible to show. The approach of using learning-augmented algorithms that the reviewer suggests is a great direction for future work.\n\nRegarding your question, “Is there any negative result for the model? For example, could you give a concrete hard instance such that the difference is at least $V \\delta$?”, see the “global” response.\n"}, {"review_id": "2DCbOoyDoV", "reviewer": "Reviewer_yCAy", "summary": "This paper studies the robust design of mechanisms for a designer with general bounded objective, when the true distribution of the agent types (possibly correlated) is not the actual distribution. More precisely, the main idea is that the optimal incentive compatible mechanism designed for the a priori distribution approximates well the optimal mechanism for the true distribution as a function of the TV distance between the two distributions, as well as guarantees approximate incentive compatibility. In this way, it generalizes results from the existing literature which were focused on specific objectives such as welfare or revenue, and under product distribution. This work is decomposed in 2 main different parts, first results relating how the various metrics (objective and incentive compatibility) degrade in the TV distance for both DSIC and BIC mechanisms are presented, then these approximation results are used for applications such as approximations in the prophet inequality setting when the distributions may be correlated, or for approximation results on simple mechanisms. ", "questions": "- l638 : Does 'single agent' described in this context mean that $n=1$? In this case what would the product distribution $\\mathcal{D}^p$ signify? \n- The proof of Lemma $2$ uses a coupling argument to bound the difference between objectives under different distributions in terms of TV distance. Can similar coupling arguments be used to derive similar robustness results, but this time for Wasserstein distance? More generally, does it look possible to extend those results to more general distances (or f-divergences like the Kullback-Leibler) or are these results stemming from the specific properties of the TV distance? \n- Is there an example when some of the proposed approximation bounds are tight, for instance in Theorem $1$? ", "limitations": "The authors have correctly addressed some of the limitations of their work, such as discussing when some assumptions may be less general than previous works (common support of distributions necessary for Theorem 2, and weaker BIC guarantees).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper study the important setting of mechanisms robust to small perturbations of the agents types distribution. It generalizes some previous results, and presents a variety of tools that can be useful for a mechanism designer. Multiple applications are given. Moreover the various applications, beyond their own interest, also serve as an example on how to apply these tools. \n- The paper is clearly written, and the existing literature well presented. The link between previous results and how they are being generalized is transparent.\n- I have went through the proofs in the main paper, as well as some in the appendix, and found no issues. ", "weaknesses": "- Compared to other works, such as `Posted Pricing and Prophet Inequalities with Inaccurate Priors' (Dutting et al 2019), this paper only studies the TV distance.\n- The approximation results are not related to any upper bound, which makes it difficult to evaluate the tightness of these results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and questions. Below we provide answers to your questions.\n\n- \"l638 : Does 'single agent' described in this context mean that n=1? In this case what would the product distribution signify?\"\n\nIndeed this is the case of a single agent. The product distribution here is referring to the items. That is, the values for the items are drawn from independent distributions. We will clarify this.\n\n- \"The proof of Lemma 2 uses.. the TV distance?\"\n\nFor the KL divergence (as well as many other f-divergences, such as $\\chi^2$-divergence), we can readily use our results since a bound on KL implies a bound on TV (e.g., using Pinsker's inequality). Note that f-divergences also exhibit supremum characterizations like TV distance (using convex conjugation ideas), but these characterizations do not have the simple structure that TV exhibits. So, it's difficult to obtain crisp robustness results from these characterizations for general f-divergences. The easier approach is to bound TV using different f-divergences and use our results for TV distance as mentioned above.\n\nFor Prokhorov distance, consider the following situation, noting that a bound on Prokhorov implies a bound on Wasserstein distance. Distribution $D$ is a point mass at $H$ (i.e. $H$ happens with probability 1). Distribution $D'$ is a point mass at $H-\\delta$. The two distributions have a Prokhorov distance of $\\delta$ but TV distance of 1. Now consider the single-item mechanism $M$ that posts a price of $H$. If the bidder that participates in $M$ draws her value for the item from $D$ she will always buy the item; thus the mechanism has expected revenue $H$. If the bidder draws her value from $D'$, $M$ has expected revenue equal to 0.\n\nThis example demonstrates that our results cannot be immediately transferred to other Prokhorov or Wasserstein-type distances (despite the existence of coupling and/or duality characterizations), and “robustifying” a mechanism, as Brustle et al. do, seems necessary.\n\n- \"Is there an example when some of the proposed approximation bounds are tight, for instance in Theorem 1?\"\n\nYes. See the “global” response.\n"}, {"review_id": "2mSUBbMZ0Z", "reviewer": "Reviewer_K563", "summary": "This paper studies the robust mechanism design. In this problem, there is a set of items and a set of agents whose valuation functions are drawn from a batch of unknown distributions. These distributions are correlated, i.e., they are close to a known distribution under the total variance distance. The agents' valuation functions are private information, and the goal is to design a truthful mechanism that maximizes some objective functions in expectation. The two main objectives are considered in this paper: social welfare maximization and revenue maximization.\n\nThe main contribution of this paper is: they prove dominant strategy incentive-compatible mechanisms are robust, namely alpha-approximate mechanisms under the classical setting can be converted into a mechanism under the robust setting without losing any factor on approximation ratio. A similar result holds for Beyseian incentive-compatible mechanisms, but a small factor has to be loss on the approximation ratio. Finally, the authors also list a batch of applications of the proposed framework.", "questions": "I don't have any specific questions.", "limitations": "This is a theoretical paper, there is no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I appreciated that the submission is carefully written and structured, so reads well given the technicality of the material. Especially, the flow of the paper is well-designed. The presentation of the algorithmic idea is also clear.\n\n2. The studied problem is interesting and well-motivated.\n\n3. The proposed framework works for a large number of applications, although the fundamental technical results are simple. ", "weaknesses": "From my perspective, there are no major weaknesses, but there seems to be no big surprise in the used techniques. However, I am not in a good position on judging the technique novelty of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review. "}, {"review_id": "xvexkz9pf7", "reviewer": "Reviewer_JheU", "summary": "The paper studies the following question: in what way can approximation guarantees of (approximately) IC mechanisms be preserved when the prior distribution is perturbed by a small amount in the total variation distance?  The main technical lemmas state that the guarantees of DSIC and BIC mechanisms are in fact preserved in ways that can be useful.  Based on these lemmas, the authors reproduce a number of previously known results, and also prove some new ones, in various subareas of algorithmic mechanism design.", "questions": "(also including detailed comments here)\n\nLine 263, \"two conditional P_{X, Y}, Q_{X, Y}\": do you mean \"joint\"?\n\nLemma 3: could mention this is essentially a Markov-like bound (right?)\n\nLemma 5: some intuition might be helpful\n\nLine 316: \"Bei et. al.\" => \"Bei et al.\" (consider using \\citet or \\citeauthor?)\n\nCorollary 1: why do you need the mechanism to be posted pricing?", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The general question the paper aims to answer is very natural and important.  The main technical lemmas turn out to be quite powerful, although they are fairly simple and intuitive (which I think is good).  I like the way the various implications are derived in the paper, i.e., the right technical observations (in the case of this paper, the main technical lemmas in Section 3) can make things much easier.", "weaknesses": "One might complain that the main technical lemmas are not all that surprising, but I think the way the authors make use of these lemmas outweighs such criticism.  Another minor thing is the applications are relatively loosely organized, and I'd be more excited if there is a key application that irrefutably shows the power of the framework proposed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and questions. Below we answer your questions.\n\n- \"Line 263, \"two conditional P_{X, Y}, Q_{X, Y}\": do you mean \"joint\"?\"\n- \"Line 316: \"Bei et. al.\" => \"Bei et al.\" (consider using \\citet or \\citeauthor?)\"\n\nWe will fix both typos.\n\n- Lemma 3: could mention this is essentially a Markov-like bound (right?)\n\nWe will mention above the lemma that it is a Markov-like result. To clarify, the lemma requires two steps to prove (as shown in the Supplementary Materials): 1) An argument to bound expected TV distance between conditional distributions using the TV distance between joint distributions, which is the main calculation, and 2) Markov’s inequality (as you correctly point out). \n\n\n- \"Lemma 5: some intuition might be helpful\"\n\nIntuitively, one can focus on the subset of “good” types such that reporting truthfully on M is within $\\epsilon$ of the optimal report; a type will be “good” with probability $1-q$, which implies a bound on the TV distance between the original distribution and the distribution “restricted” to “good” types. Our construction alters the behavior of $M$ on the “bad” types, and uses the aforementioned TV bound and Lemma 2 to bound the additional loss in the BIC constraint, as well as the revenue loss. We’d be happy to include this intuition, as well as further expand/clarify if the reviewer believes it would improve the quality of the paper.\n\n- \"Corollary 1: why do you need the mechanism to be posted pricing?\"\n\nThe corollary holds for all DSIC and ex-post IR mechanisms. We refer to posted prices here because they are the main family of policies studied in the literature on prophet inequalities. Specifically, the optimal policy and, to the best of our knowledge, every simple and approximately optimal policy in the literature are posted prices.\n"}]

Author rebuttal:
We thank all reviewers for the thorough reviews and helpful comments. We will incorporate the valuable suggestions from all reviewers in the final version of this paper.

A common question that reviewers acoM, XhLk, and yCAy ask is whether our various bounds are tight. One can construct trivial tight examples for Lemma 2 and Theorem 1, at least for the case of revenue and welfare. For instance, for the case of a single agent, letting $\mathcal{T} = [0,V]$, consider the case that the distribution P is a point mass at V, and distribution Q takes the value V with probability $1-\delta$, and zero otherwise. The TV distance between P and Q is exactly $\delta$. Now, consider the simple mechanism M that posts a price of V. Its revenue/welfare under P is V, and its revenue under Q is $(1-\delta)V$. One can construct such simple examples to show tightness for Lemma 2 and Theorem 1 in general. For BIC (e.g. Thm 2) it seems slightly trickier to construct tight examples (where one loses both in the BIC constraint and the revenue). 

We’d be happy to include such lower-bound examples in the final version of the paper.

Meta-review: The reviewers agreed that this paper studies a natural question and found it interesting.
Decision: Accept (poster)