On the Robustness of Mechanism Design under Total Variation Distance

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.

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.

Questions

(also including detailed comments here) Line 263, "two conditional P_{X, Y}, Q_{X, Y}": do you mean "joint"? Lemma 3: could mention this is essentially a Markov-like bound (right?) Lemma 5: some intuition might be helpful Line 316: "Bei et. al." => "Bei et al." (consider using \citet or \citeauthor?) Corollary 1: why do you need the mechanism to be posted pricing?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

n/a

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. The 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.

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. 2. The studied problem is interesting and well-motivated. 3. 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.

Questions

I don't have any specific questions.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This is a theoretical paper, there is no potential negative societal impact.

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.

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. - The paper is clearly written, and the existing literature well presented. The link between previous results and how they are being generalized is transparent. - 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. - The approximation results are not related to any upper bound, which makes it difficult to evaluate the tightness of these results.

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? - 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? - Is there an example when some of the proposed approximation bounds are tight, for instance in Theorem $1$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

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).

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. Both 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.

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.

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$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weakness.

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.

Strengths

This work considers a natural question, and aims to provide a systematic answer. The 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. Many 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. The 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.

Questions

Where is the crux of your invocation of duality, and how are you using the connection between these characterizations of TV distance? Which of your robustness claims readily admit lower (upper?) bounds? Possible corrections: L195-196: Should Omega additionally be a measurable subset in order to be a standard Borel space? L213: is the supremum necessary? L244: "inequality is because" L310: epsilon used before it is introduced L376: "distributions" L384: is the Omega here intended to mean that there is some constant for which the claim holds?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Some of the theorem statements seem to be missing quantifiers and conditions, as well as informal overviews of their methods of proof. It would be helpful to have more discussion of which dependences are necessary.