# EC'23 Rebuttal - Best of Both Distortion Worlds

We thank all the reviewers for the detailed and constructive reviews. We will incorporate all your minor remarks and suggestions in our revision. Please find below our answers to your major comments and questions.

## Review #536A

> Do the results by the authors reveal novel conceptual similarities between metric and utilitarian distortion?

**Response:** That's a great question. We believe that our work uncovers surprising flexibility that the metric distortion framework offers when the goal is to achieve a small constant distortion. This is exemplified by Lemma 2 for deterministic rules, and Lemmas 3 and 4 for randomized rules. Our Pruned Plurality Veto and Truncated Harmonic rules exploit this flexibility to achieve asymptotically (near-)optimal distortion while staying within the boundary of a small constant metric distortion.

> Concerning Lemma 2: Is there a restriction on $\tau$? How do the two upper bounds relate?

**Response:** The only bound we prove is the one from the proof, $1+\frac{2}{1-\tau m}$. The bound of $1+\frac{2}{\tau}$ from the statement of Lemma 2 is simply a typo that we unfortunately forgot to correct when we revised notation to make the proof easier to understand. The bound in the statement should also be $1+\frac{2}{1-\tau m}$, and as you say, this is the bound we use later.** Also, the statement of this lemma is meaningful only when $0 \leq \tau < 1/m$. This is, indeed, the range of $\tau$ values that we use later on, in the following theorem, so this does not affect the correctness of our arguments. We thank the reviewer for catching this typo and we will make sure to update our Lemma 2 statement accordingly!**

> In the proof of Corollary 1 (Theorem 4), I could not verify the value (upper bound) of $p(I,Y)$ ($p(Y)$). Could you please elaborate on that?

**Response:** The definition of $p(i,Y)$ is provided as Definition 2. If we compare its value to $\hat{w}(i, Y)$, we can see that for $Y \neq X$, we have $p(i, Y) = \frac{\varepsilon}{6} \hat{w}(i, Y)$.

> In the proof of Theorem 12, I do not understand the estimate with $n/2$ in the second line.

**Response:** We believe that the reviewer may be referring to the second line of Page 22 instead of the second line of the proof of Theorem 12. If so, then yes, this should be $n$ instead of $n/2$; we apologize for this typo. This does not affect the correctness of the proof or the statement of the theorem (since we only care about the asymptotic bound). Also, note that we only included this argument for completeness; Theorem 12 is not one of the contributions of this work, but rather a result from a separate paper as we discuss at the beginning of the section.

## Review #536B

> Better motivation for the focus on two distortion world

We actually believe that in many important applications we do not know in advance whether the metric structure applies or not.

For example, the primary motivating application for the metric structure is facility location. If we assume that each agent’s top priority is to minimize her distance to the facility and her cost grows linearly in this distance, then the metric structure is natural given the geometric nature of the problem. However, this heavily depends on the aforementioned assumptions. If the agent cares about other features of possible locations (e.g., proximity to some other facility or shop that the agent often visits, or whether it is on their way to work), or if the agent's cost grows non-linearly in the distance to the facility, the metric structure might break down. In practice, this can be difficult to detect in advance.

Another common application motivating the metric structure is voting, when each voter’s preferences over different candidates are determined by their distance on different issues (which, e.g., can be captured as different dimensions). Once again, the metric structure holds in this case, but can easily break down if other factors can significantly affect the voters' preferences, e.g., who their parents or friends vote for, or whether they trust some candidate more than another.

If one were to use rules for minimizing metric distortion and the metric structure breaks down, these rules could perform poorly. Our proposed rules add a safety net by ensuring that even when the metric assumption does not hold, approximately optimal welfare will be achieved with respect to all possible utility functions consistent with the voters' ordinal preferences (since distortion is a worst-case notion).

That said, we agree with the reviewer that this motivation should be laid out more thoroughly in the paper, which we will do in the next revision.

> Leaving out the definitions of plurality matchings, stable lotteries and harmonic rule

We chose to leave out definitions that our work does not crucially rely on and provided citations instead as we felt that providing these definitions would be distracting to the reader. However, this is a subjective choice. For example, Reviewer #536A lists precisely this as one of the strengths of the paper! That said, if the reviewers come to a consensus that we should add some of these definitions, we would be happy to oblige!