# voting_with_preference_intensities__3faa31a5.pdf

Voting with Preference Intensities

Anson Kahng1, Mohamad Latifian2, Nisarg Shah2

1 University of Rochester 2 University of Toronto akahng2@cs.rochester.edu, latifian@cs.toronto.edu, nisarg@cs.toronto.edu

When an agent votes, she typically ranks the set of available alternatives. Occasionally, she may also wish to report the intensity of her preferences by indicating adjacent pairs of alternatives in her ranking between which her preference is acutely decisive; for instance, she may suggest that she likes alternative a more than b, but b much more than c. We design near-optimal voting rules which aggregate such preference rankings with intensities using the recently-popular distortion framework. We also show that traditional voting rules, which aggregate preference rankings while ignoring (or not eliciting) intensities, can incur significant welfare loss.

Introduction

Professor X wants to take her students out for a group lunch. Being a computational social choice researcher, she realizes that this is the perfect opportunity to conduct real-life voting, so she offers them the choice between four popular restaurants (a, b, c, and d) and asks the ambiguously worded though, perhaps intentionally so question: Tell me your preferences over these restaurants . One of her students, Sam, responds with the preference ranking a ą b ą c ą d, which means he likes a the most and d the least. Meera has a slightly different preference ranking, b ą d ą c ą a. Additionally, she also wants to convey that she likes b and d much more than a or c (she is vegetarian and the latter two lack good vegetarian options). Thus, she responds with a preference ranking with intensities, b ą d ąą c ą a; the ąą between d and c indicates that her preference intensity drops sharply from d to c.1

Professor X was planning to use the Borda count, a wellestablished voting rule for aggregating preference rankings that would give each restaurant 3, 2, 1, and 0 points each time it is ranked first, second, third, and fourth, respectively, and pick the restaurant with the most points as the winner. But now, she begins to wonder how she should aggregate preference rankings with intensities indicated by ąą signs. A natural approach would be to modify Borda count so that there is a steeper drop in points awarded when encountering a ąą sign. But exactly how steep should it be? In Meera s

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1We use intensity and decisiveness interchangeably.

case (b ą d ąą c ą a), perhaps the four restaurants should be awarded 3, 2.5, 0.5, and 0 points in order. Or should it be 3, 2.1, 0.9, and 0 points? Professor X is not satisfied with this, and for a more systematic approach, she looks towards the distortion framework. Introduced by Procaccia and Rosenschein (2006), the distortion framework posits that ordinal preferences reported by the agents stem from their underlying numerical utility functions over the set A of m alternatives. That is, when agent i reports that she prefers alternative a to b (denoted a ą b), it must be the case that uipaq ě uipbq according to her underlying utility function ui : A Ñ Rě0. The goal of the distortion framework is to seek voting rules which, subject to the available partial information about agents utility functions, minimize the worst-case approximation ratio between the highest possible utilitarian social welfare (sum of agent utilities) and that of the outcome picked by the rule; this quantity is termed distortion. For aggregating preference rankings (without intensities), the best possible distortion for deterministic and randomized voting rules is known to be Θpm2q (Caragiannis and Procaccia 2011; Caragiannis et al. 2017) and Θp?mq (Boutilier et al. 2015; Ebadian et al. 2022), respectively. The distortion framework is extremely versatile. It can be used not only to analyze how to aggregate ranked preferences, but also to analyze how to aggregate other ballot formats such as top-t preferences (Borodin et al. 2022), threshold approval votes (Benade et al. 2021), and ranked preferences coupled with additional queries (Amanatidis et al. 2021; Brams and Sanver 2009); compare different ballot formats (Benade et al. 2021); and even design optimal ballot formats (Mandal et al. 2019; Mandal, Shah, and Woodruff 2020). We argue that this framework also provides a systematic approach to aggregating preference rankings with intensities. Let α P r0, 1s be a parameter that governs how decisive an agent must be for her to use a ąą sign. When agent i reports a ą b, we still assume that uipaq ě uipbq. But when agent i reports aąąb, we assume that the agent has an αdecisive preference for a over b given by α uipaq ě uipbq. Thus, when α 0, ąą signs provide significant additional information since the agent s utility must drop to 0 starting with the alternative after the first ąą sign (if it exists). In contrast, when α 1, ąą signs provide little additional in-

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

formation and are essentially equivalent to ą signs. Given a value of α, the distortion framework allows us to identify an alternative (or a distribution over alternatives) with the the minimum distortion, when agents (voluntarily) use ąą signs to reveal α-decisive preferences. Alternatively, the designer may choose a value of α and mandate all agents to use ąą signs whenever they have α-decisive preferences; in this case, agent i reporting a ą b would translate to a stronger condition of uipaq ě uipbq ą α uipaq because we know the agent s preference for a over b is decidedly not decisive (no pun intended). In both these cases of voluntary and mandatory intensity revelation, one can not only study optimal voting rules, but also the social welfare loss that traditional voting rules can incur by either not eliciting or ignoring the intensity information. This leads to our main research questions:

How should one aggregate preference rankings with intensities? Can a better distortion be guaranteed if all agents have decisive preferences or if the designer mandates revealing decisive preferences whenever they exist? What welfare loss might the designer incur when using a traditional voting rule that simply aggregates preference rankings without intensities?

Our Contribution

A key conceptual contribution of our work is to introduce a formal model in which agents can report α-decisive preferences using the ąą sign and the impact of this on the distortion of voting rules can be analyzed. We begin our analysis with the top decisiveness setting, in which every agent is assumed to be α-decisive between their top two choices. For this setting, which has been considered in the literature under a different model, we identify asymptotically optimal distortion bounds for both deterministic and randomized voting rules. We also extend this to uniform decisiveness, in which every agent is assumed to be α-decisive between every pair of adjacent alternatives in her preference ranking, and provide tight distortion bounds for deterministic rules. In general when agents can have α-decisive preferences at arbitrary locations in their preference rankings, we introduce and study the price of ignoring the intensities (POII), which captures the efficiency loss of traditional voting rules that do not elicit preference intensities. When agents can voluntarily report their α-decisive preferences (but are not required to do so), we show that both deterministic and randomized rules can suffer from a significant POII. When agents must mandatorily report their α-decisive preferences, the POII can be even higher, and we prove a better lower bound for deterministic rules. In case of mandatory reporting, by proving non-trivial lower bounds, we raise the interesting open question of whether one can establish better distortion bounds for deterministic rules by carefully choosing the value of α, but show that this cannot be done for randomized rules.

Related Work

Our work builds on the distortion framework, specifically the utilitarian distortion framework in which agents have normalized utilities for alternatives (Procaccia and Rosenschein 2006). There is a closely related framework of metric distortion (Anshelevich et al. 2018; Anshelevich and Postl 2017; Abramowitz, Anshelevich, and Zhu 2019), in which agents and alternatives are embedded in an underlying metric space, agents have costs for the alternatives measured by the distance between them, and agents rank the alternatives by these costs. While constant distortion of 3 can already be guaranteed in this framework by aggregating ranked preferences using a deterministic rule (Gkatzelis, Halpern, and Shah 2020; Kizilkaya and Kempe 2022), Anshelevich and Postl (2017) introduced the idea of deriving improved distortion bounds when the underlying metric space is α-decisive, that is, when each agent s distance to her closest alternative is at most α times her distance to her next-closest alternative. This has induced a significant body of follow-up work (Gross, Anshelevich, and Xia 2017; Ghodsi, Latifian, and Seddighin 2019; Gkatzelis, Halpern, and Shah 2020; Anagnostides, Fotakis, and Patsilinakos 2022). The top-decisiveness setting from our paper is precisely the counterpart of this in the utilitarian distortion framework, where each agent s utility for her second-best alternative is assumed to be at most α times her utility for her best alternative. Our uniform decisiveness setting takes this one step further, where the agent is decisive between every adjacent pair of alternatives in her preference ranking, not only between her top two alternatives. For our setting in which agents voluntarily reveal their decisiveness, improved distortion bounds cannot be guaranteed because in the worst case, none of the agents may reveal any decisiveness. For this setting, we study the price of ignoring the intensities, which is the maximum factor by which the distortion can increase due to not taking into account the voluntarily revealed decisiveness information; here, the worst case is when agents do reveal substantial useful information. This is similar to the concept of competitive ratio from online algorithms (Borodin and El-Yaniv 2005), except the ignorance in our case is rectifiable. Our setting in which the designer chooses a value of α and forces agents to reveal whenever they have α-decisive preferences is equivalent to querying agents for additional information beyond their ranked preferences, which has been studied by Amanatidis et al. (2021). Specifically, our setting is a special case of their framework, in which m 1 comparison queries are made to each agent, one for every adjacent pair of alternatives in her preference ranking. While we show a lower bound of Ωpmq for our setting (and leave open the exciting question of whether this is tight), they show that constant distortion can be achieved by using Oplog2 mq arbitrary comparison queries per agent. Mandal et al. (2019) and Mandal, Shah, and Woodruff (2020) extend this idea to allow arbitrary queries and search over the space of all possible ballot formats to find ones that provide the optimal tradeoff between distortion and the number of bits of information elicited from each agent. We refer the interested reader to

the survey by Anshelevich et al. (2021) for further related work on distortion.

Preliminaries For t P N, define rts t1, 2, . . . , tu, and for a set X, define p Xq to be the set of all distributions over X. Let N rns be a set of n agents, and A ta1, a2, . . . , amu be a set of m alternatives.

Preference rankings with intensities. Each agent i has ordinal preferences over the alternatives given by a preference ranking with intensities, denoted σi pπi, iq, where πi : rms Ñ A is a one-to-one function that determines a ranking over the alternatives, and i: rm 1s Ñ t ą , ąą u is a function that determines the intensities: i pjq ą indicates a preference for πipjq over πipj 1q, whereas i pjq ąą indicates a strong preference for πipjq over πipj 1q. Let σ pσ1, . . . , σnq denote the ordinal preference profile, and Sp Aq be the set of all total orderings with intensities over A.

Voting rule. A (randomized) voting rule f : Sp Aqn Ñ p Aq maps an ordinal preference profile to a distribution over the alternatives. We say that f is deterministic if it always outputs a distribution with singleton support; in this case, we use fp σq to directly denote the single alternative in the support of the distribution chosen by f on σ.

Utilitarian framework. We assume that the ordinal preferences of the agents stem from underlying cardinal preferences. Specifically, each agent i has an underlying utility function ui : A Ñ Rě0, where uipaq denotes the utility of agent i for alternative a. For a distribution x P p Aq, we write uipxq Ea x uipaq. Following the literature (Aziz 2020), we work with unit-sum utilities, where ř a PA uipaq 1 for each i P N. Let u pu1, . . . , unq be the utility profile. Let α P r0, 1s be a parameter which may be chosen either by the designer or implicitly by the agents. We say that utility profile u is αconsistent with preference profile σ, denoted u α σ, if, for all i P N and j P rm 1s, we have uipπipjqq ě uipπipj 1qq if i pjq ą and α uipπipjqq ě uipπipj 1qq if i pjq ąą . Given a utility profile u, the social welfare of distribution x P p Aq is swpx, uq ř i PN uipxq. The distortion of x over u is defined as

distpx, uq maxa PA swpa, uq

and the α-distortion of x on a preference profile σ is defined as distαpx, σq sup u α σ distpx, uq.Throughout the paper we might use candidate a when a distribution x P p Aq is expected. In this case by a we mean a distribution that gives probability 1 to a and zero to the rest of the candidates. Intuitively, distortion quantifies the efficiency of a distribution x for a preference profile σ by taking the worst-case ratio between the social welfare of the optimal alternative and the (expected) social welfare of x over all utility profiles that are α-consistent with the preference profile, which, in this case, includes preferences intensities.

We also define the α-distortion of a voting rule f as

distαpfq max σPSp Aqn distαpfp σq, σq,

or as the worst case α-distortion of the output of f over all preference profiles.

Top Decisiveness Without assuming that agents have at least somewhat decisive preferences, one cannot hope to improve distortion bounds (Opm2q for deterministic rules and Op?mq for randomized rules (Ebadian et al. 2022)) because, in the worst case, none of the agents may use the ąą sign. Hence, in the related literature on metric distortion, a number of papers have analyzed distortion bounds subject to a natural restriction on agent preferences: all agents are assumed to be α-decisive in their preference for their best alternative over their second-best alternative, for a fixed α (Anshelevich and Postl 2017; Gross, Anshelevich, and Xia 2017; Ghodsi, Latifian, and Seddighin 2019; Gkatzelis, Halpern, and Shah 2020; Anagnostides, Fotakis, and Patsilinakos 2022). We study such preferences in the utilitarian framework, and rename them as top α-decisive to indicate that the decisiveness is at the top of the preference ranking. While identifying asymptotically optimal distortion bounds for top αdecisive preferences is still an open question in the metric distortion framework (Gkatzelis, Halpern, and Shah 2020), we are able to obtain tight distortion bounds for this in the utilitarian framework. Definition 1 (Top α-Decisiveness). Let α P r0, 1s. We say that agent i with utility function ui is top α-decisive if there exists an alternative a such that uipaq ď α uipa q for all a a . To restate this, define top to be a function where topp1q ąą and toppjq ą for 1 ă j ă m, and Sdp Aq Ă Sp Aq to be the set of preference rankings with intensities containing σ pπ, topq for all preference rankings π. Then, agent i is top α-decisive if there exists σi P Sdp Aq such that ui α σi. A preference profile σ is top α-decisive if σ P Sdp Aqn, and a utility profile u is top α-decisive if u α σ for some σ P Sdp Aqn. Definition 2 (Top α-decisive distortion of rule f). The distortion of a voting rule f with respect to top α-decisive preferences is defined as

disttop α pfq max σPSdp Aqn distα pfp σq, σq .

First, we show matching lower (Theorem 1) and upper (Theorem 2) bounds on the best possible distortion of deterministic rules with respect to top α-decisive preferences. Theorem 1. For any α P r0, 1s, the distortion of every deterministic voting rule with respect to top α-decisive utilitarian spaces is Ωpα2m2 1q. The proof of this result and all other missing proofs are available in the full version. 2 Next, we show that the simple plurality rule provides a matching upper bound for all α, despite ignoring preference

2Full version: https://www.cs.toronto.edu/ nisarg/papers/ intensities.pdf

intensities and being oblivious to the value of α. This is perhaps not so surprising: plurality is known to provide asymptotically the best distortion for aggregating (not necessarily decisive) ranked preferences (Caragiannis and Procaccia 2011; Caragiannis et al. 2017), and assuming top decisiveness only increases the importance of focusing on the top choices of the agents, which plurality does. Theorem 2. For any α P r0, 1s, the distortion of plurality with respect to top α-decisive preferences is O α2m2 1 .

Proof. Let fplu denote the plurality rule. Consider a top αdecisive preference profile σ and a utility profile u such that u α σ. Let ap be the plurality winner and a P arg maxa PA swpa, uq be an optimal alternative. Let N ap and N a denote the sets of agents who have ap and a as their top choices in σ, respectively. Then, due to the utility functions being unit-sum and top α-decisive, we have

swpap, uq ě |N ap| 1 αpm 1q 1,

swpa , uq ď |N a | 1 pn |N a |q α α 1.

Using the fact that |N ap| ě maxp|N a |, n{mq, we have

distpfplup σq, uq swpa , uq

ď αpm 1q 1 αpm 1q

α 1 pαpm 1q 1q

Note that the best distortion bound of deterministic rules drops from Θpm2q at α 1 (which is the traditional setting) to Θp1q at α Θp1{mq, and then stays Θp1q. As is often the case with distortion-based analysis, randomized rules offer significantly better guarantees. We next present matching lower (Theorem 3) and upper (Theorem 4) bounds for the distortion of randomized voting rules with respect to top α-decisive preferences, with some minor results along the way. Theorem 3. The distortion of every randomized voting rule with respect to top α-decisive utilitarian spaces is Ωp αm 1

Given our results for deterministic rules, one may wonder whether randomized rules that are known to be (near-)optimal for aggregating ranked preferences (α 1) may also happen to be (near-)optimal for aggregating top αdecisive preferences for all α P r0, 1s, despite being oblivious to preference intensities and the value of α. For aggregating ranked preferences, the harmonic rule (Boutilier et al. 2015) provides Op?m log mq distortion while the stable lottery rule (Ebadian et al. 2022) provides the optimal Op?mq distortion. While these distortion upper bounds trivially hold for aggregating top α-decisive preferences, unfortunately the distortion of these rules does not seem to improve when α ă 1. Fortunately, we are able to modify the stable lottery rule to design a new randomized voting rule, which pays

increased attention to agents top choices and provably achieves asymptotically optimal distortion with respect to top α-decisive preferences, while still being oblivious to preference intensities as well as the value of α. Definition 3. We define fdec to be a randomized voting rule that, with probability 1

2, runs the stable lottery rule (fslr); with probability 1

4, selects an alternative uniformly at random from the set of alternatives which are the top choice of at least one agent; and with the remaining probability 1

4, selects an alternative with the maximum plurality score (i.e., is the top-choice of the most agents).

Theorem 4. For every α P r0, 1s, the distortion of the (randomized) rule fdec with respect to top α-decisive preferences is Op αm 1

Proof. Consider any top α-decisive preference profile σ p π, q, and let u α σ be the underlying utility profile. Let a P arg maxa PA swpa, uq be an optimal alternative. Define N a to be the set of agents who have alternative a as their top choice, N a Nz N a, and T to be the set of the alternatives that are the top choice of at least one agent. For each i P N a we have uipπip1qq ě uipa q

α , so we have ÿ

a PT swpa, uq ě ÿ

i PN uipπip1qq ě ÿ

i PN a uipπip1qq

The plurality winner ap must be the top choice of at least |N a | agents, each of whom must have utility at least 1 αpm 1q 1 ě 1 αm 1 due to having a unit-sum and top αdecisive utility function. Thus, we have

swpap, uq ě |N a |

Putting Equations (1) and (2) together with the fact that the distortion of fslr is at most 2?m (Ebadian et al. 2022), we have: Erswpfdecp σq, uqs

αm 1 swpa , uq ?m

uipa q αm 1 |N a |

αm 1 swpa , uq ?m

αm 1 swpa , uq ?m

ě swpa , uq

αm?m ?m ě swpa , uq α?m 1

distpfdecp σq, uq swpa , uq Erswpfdecp σq, uqs

α?m 1 O ˆ αm 1

Note that the distortion stays Θp?mq from α 1 to α Θp1{?mq, then drops to Θp1q by α Θp1{mq, and then stays Θp1q as α drops further.

Uniform Decisiveness In some applications, it may be natural for agents to be αdecisive not only between their top two choices, but between every pair of adjacent alternatives in their ranking. We initiate the study of this natural restriction on agent preferences. We say that agent i is uniform α-decisive if i pąą, . . . , ąąq in her ordinal preferences σi pπi, iq. We then define uniform α-decisive preference profiles and utility profiles, as well as the distortion of a voting rule with respect to uniform α-decisive preferences similarly to the case of top α-decisiveness. While any distortion upper bounds with respect to top αdecisive preferences continue to hold with respect to uniform α-decisive preferences, one may hope to find improved distortion bounds now that the agents are more decisive. Indeed, we are able to provide improved matching lower (Theorem 5) and upper (Theorem 6) bounds for deterministic rules. For randomized rules, we present a lower bound (Theorem 7), but leave open the question of whether an upper bound better than the one in Theorem 4 can be derived. Theorem 5. For every α P r0, 1s, the distortion of every deterministic voting rule with respect to uniform α-decisive preferences is Ω pmα 1qp1 αmq

Theorem 6. For every α P r0, 1s, the distortion of the (deterministic) plurality rule with respect to uniform α-decisive preferences is O pmα 1qp1 αmq

Theorem 7. For every α P r0, 1s, the distortion of every randomized voting rule with respect to uniform α-decisive preferences is Ω min ?m, 1 αm

Voluntary Reporting of Intensities We now relax the assumption that all agents have similarly decisive preferences. Instead, we study a setting in which agents may have decisive preferences at arbitrary positions in their preference rankings, and even when they do, they may choose to not reveal them and use the ą sign instead of the ąą sign. As argued before, one cannot hope to derive improved distortion bounds in this case because it is possible that none of the agents use ąą sign anywhere in the preference profile.3 Instead, we focus on the loss of efficiency that a traditional voting rule can incur in the worst case, measured by increased α-distortion, due to aggregating only preference rankings and not preference rankings with intensities. This is meaningful as the worst case now occurs when the agents

3One can still seek to computationally find the distortionoptimal distribution on any given (not necessarily worst-case) preference profile. It is easy to see that this requires only a slight modification in the linear program Boutilier et al. (2015), where uipaq ě uipbq is replaced by α uipaq ě uipbq whenever agent i reports aąąb (in adjacent positions in her preference ranking).

could have revealed α-decisive preferences by using the ąą sign, but the traditional voting rule either did not elicit such intensities or chose to ignore them. We initiate the study of this efficiency loss, which we term the price of ignoring the intensities.

Definition 4 (Intensity-aware optimal). Let optaw α p σq be a distribution x over A that minimizes the worst-case distortion over the utility profiles that are α-consistent with σ, i.e.,

optaw α p σq arg min x P p Aq distαpx, σq.

Definition 5 (Price of ignoring the intensities (POII)). We define the price of ignoring the intensities (POII) of a distribution x P p Aq on a preference profile σ as the ratio between the α-distortion of x and that of the intensity-aware optimal distribution:

Po IIpx, σ, αq distαpx, σq distαpoptaw α p σq, σq.

When x is chosen based only on the ranked preference profile (without intensities) π, its POII on π is defined as Po IIpx, π, αq max σ π Po IIpx, σ, αq,where we use σ π to denote that σ p π, q for some . This allows us to define both the intensity-oblivious optimal distribution on π as optob α p πq arg minx P p Aq Po IIpx, π, αq and the POII on π as Po IIp π, αq Po IIpoptob α p πq, π, αq. We are interested in the worst case of this over all π, termed the POII for αdecisive preferences: Po IIpαq max π Po IIp π, αq.

We observe the following lemma, which provides a way to derive a lower bound on the price of ignorance.

Lemma 1. For any ranked preference profile (without intensities) π, preference profile σ π, and distribution x P p Aq, we have:

Po IIp π, αq ě distαpoptob α p πq, σq distαpx, σq .

Proof. By the definitions,

Po IIp π, αq ě Po IIpoptob α p πq, σ, αq distαpoptob α p πq, σq distαpoptaw α p σq, σq

ě distαpoptob α p πq, σq distαpx, σq .

Theorem 8. For any α P r0, 1s, the price of ignoring the intensities for α-decisive preferences is Po IIpαq Ω ?mp1 αq

Proof. For ease of exposition, assume ?m divides n. Partition the agents into ?m equal-sized subsets N1, . . . , N?m, and consider ranked preference profile (without intensities) π, where members of Nj rank aj first and the rest of the alternatives in a cyclic order.4

4All we need is that for j ą 1, each alternative appears in the j-th position in the preference rankings of at most n{m agents.

Fix an intensity-oblivious optimal distribution optob α p πq. Without loss of generality, assume that optob α p πq places the lowest probability on a1 among the alternatives a1, . . . , a?m (thus, this probability is at most 1{?m). Now, define intensities in a way that for i P N1, we have i pąą, . . . , ąąq, whereas for all other agents i1 R N1, we have i1 pą, . . . , ąq. Consider the preference profile σ p π, q. We show that optob α p πq has a significant POII on σ. We use Lemma 1 to derive this in two steps: proving a lower bound on distαpoptob α p πq, σq and proving an upper bound on distαpx, σq for some distribution x P p Aq. Step 1. For proving a lower bound on distαpoptob α p πq, σq, consider the utility profile u in which all members of N1 have utility 1 for a1 and zero for all other alternatives, and all other agents have utility 1{m for every alternative. Since u α σ, we can see that

distαpoptob α p πq, σq ě distαpoptob α p πq, u q ě ?m

We omit the detailed calculation as it is identical to the one given in Boutilier et al. (2015) for proving a distortion lower bound on randomized voting rules for aggregating ranked preferences (without intensities).5 Step 2. On the other hand, consider the distribution x that places probability 1 on a1. To prove an upper bound on distαpx, σq distαpa1, σq, consider any utility profile u such that u α σ. For each i P N1, we can see that uipa1q ě 1 α 1 αm due to unit-sum and uniform α-decisive utility function ui. Hence,

swpa1, uq ě n ?m 1 α

Also, every other alternative a appears as the top choice of at most n{?m agents (who each have utility at most 1 for it), and for 1 ă j ď m, it appears in the j-th position in the preference rankings of at most n{m of the agents (who each have utility at most 1{j for it due to their utility functions being unit-sum). Hence, we have

swpa, uq ď n ?m 1 n

m Hm ď 2n ?m, (5)

where Hm řm i 1 1{i is the m-th harmonic number. From Equations (4) and (5), we have that

distαpa1, σq ď 2p1 αmq

Using Lemma 1 and Equation (3), we have

Po IIpαq ě Po IIp π, αq ě distαpoptob α p πq, σq distαpa1, σq

4p1 αmq Ω ˆp1 αq?m

The last step follows because the POII is always at least 1.

5While they derive a lower bound of ?m{3, it is not difficult to see that a careful calculation in their analysis yields ?m{2.

You can see that when α is a constant less than 1, Po IIpαq Θp?mq. Note that we can not hope for a higher POII since the stable lottery rule (Ebadian et al. 2022) already guarantees Op?mq distortion while being intensity oblivious. That means we have a rule that could not suffer from a multiplicative increase in distortion by an ωp?mq factor compared to the intensity-aware optimal distribution in hindsight. That said, for other regimes of α, it remains to be seen whether the bound from Theorem 8 is tight. The POII can similarly be defined when restricting to deterministic choices. Here, we prove the following lower bound, which is not necessarily tight even when α is a constant less than 1, resulting in another open question. Theorem 9. For any α P r0, 1s, the price of ignoring the intensities of deterministic rules for α-decisive preferences is Ω mp1 αq

Mandatory Reporting of Intensities To this point, we have studied the setting where agents may choose to report decisive preferences. Crucially, they are not required to report all (or indeed any) α-decisive preferences. One natural question is whether a designer can do significantly better by choosing a value of α and requiring all agents to report all locations in their preference ranking where their preference between adjacent alternatives is αdecisive. In this case, when agent i reports a ą b for adjacent alternatives a and b in her preference ranking, we know not only that uipaq ě uipbq (agent i prefers a to b), but also that α uipaq ď uipbq (the preference is not α-decisive). We say that utility function u is strictly α-consistent with preference ordering σ pπ, q, and denote it with u α σ, if u is α-consistent with σ, and for each j P rm 1s where pjq ą , we have α upπpjqq ď upπpj 1qq. A utility profile u is strictly α-consistent with a preference profile σ if ui α σi for each agent i. In this section, we assume that agents utility functions are strictly α-consistent with the preference ordering they submit to the voting rule. Our goal is to see if we can get improved distortion bounds in this case. Definition 6 (Strict Distortion). The strict α-distortion of distribution x P p Aq on preference profile σ is defined as:

dist S αpx, σq sup u α σ distpx, uq.

We prove a lower bound on the best possible strict distortion of any deterministic rule as a function of α. Our bound is Ωpm2q at α Θp1q and α Op1{mq, showing that mandatory reporting of intensities cannot help reduce distortion in these regimes. However, our bound is the weakest (Ωpm5{4q) at α Θp1{ 4?mq, raising the interesting possibility of significantly improving upon the Opm2q distortion by choosing the right value of α and mandating agents to report α-decisive preferences. Theorem 10. For any α P r0, 1s, the strict α-distortion of every deterministic voting rule f satisfies:

dist S αpfq Ω ˆ max ˆ m2α3, m2

1{m 1{?m 1{ 4?m 1

Lower bound on dist S αpfq

Figure 1: A conceptual plot of the bounds in Theorem 10.

The bound achieves its weakest value of Ωpm 5 4 q at m Θp1{ 4?mq (see Figure 1).

Proof sketch. We give two bounds that complement each other as shown in Figure 1. For the first bound (the gray line in Figure 1) consider a profile in which agents all have the same alternative as their second choice but are split evenly among favorite alternatives. All agents are decisive only between the first and second, and second and third positions, i.e., i pąą, ąą, ą , . . . , ąq. For the second bound (the black line in Figure 1), consider a profile in which agents are divided into groups. All the agents have am as their second choice, each group of agents ranks a particular subset of alternatives first, and the rest in an arbitrary order. For any deterministic voting rule f, we can case on whether f chooses am or not.

While it may be possible to improve the distortion of deterministic rules via mandatory reporting of intensities, we prove that this is decidedly not the case for randomized rules: regardless of the value of α P r0, 1s, every randomized rule has strict distortion Ωp?mq, meaning that the stable lottery rule of Ebadian et al. (2022) achieves the optimal strict distortion of Op?mq for all α P r0, 1s. The result is proved by deriving two separate lower bounds, which establish the desired implication in complementary regions of α, as depicted in Figure 2.

Theorem 11. For every α P r0, 1s, every (randomized) voting rule f has strict α-distortion dist S αpfq Ωp?mq.

Proof sketch. We consider the classic lower bound instance from Boutilier et al. (2015), where ?m of the alternatives appear as the top choices of n{?m agents each. We bound the strict distortion of this instance with respect to two different intensity profiles: in the first profile, each agent i reports i pą, . . . , ąq, and in the second profile, each agent i reports i pąą, ą, . . . , ąq.

POII with Mandatory Reporting of Intensities

One can define the price of ignoring the intensities in this case like in the case of voluntary reporting of intensities. However, in the case of mandatory reporting of intensities, an intensity-oblivious rule has potentially more to lose: had

Lower bound on dist S αpfq

Figure 2: A conceptual plot of the bounds in Theorem 11.

it elicited intensities, it could have obtained additional information not only when a voter used the ąą sign (which indicates the preference is decisive), but also when the voter used the ą sign (which indicates the preference is not decisive). We are in fact able to improve upon our lower bound from Theorem 9. While that lower bound started at Ωpmq at α 0 and decreased to the trivial bound of Ωp1q as α Ñ 1, our new bound starts at Ωpmq at α 0, but increases to Ωpm2q as α Ñ 1. Note that Ωpm2q is the highest possible POII because plurality achieves Opm2q distortion in an intensityoblivious manner, so it cannot suffer from a multiplicative increase in distortion by an ωpm2q factor due to the lack of intensity elicitation.

Theorem 12. For every α P r0, 1s, the price of ignoring the intensities of deterministic rules with mandatory reporting of α-decisive preferences is Ωp mp1 αmq

Our work uncovers several exciting open questions. Perhaps the most compelling of them is whether one can improve the distortion of deterministic rules to Opmq by choosing a value of α P r0, 1s and mandating all agents to reveal whenever their preferences are α-decisive. A compelling candidate is α Θp1{?mq because this is where our lower bound from Theorem 10 achieves its weakest value of Ωpmq. Other open questions include settling the optimal distortion of randomized rules subject to uniform decisiveness (see Theorem 7 for our lower bound), the POII when agents reveal their α-decisive preferences voluntarily (see Theorems 8 and 9 for our lower bounds), and the POII when agents reveal their α-decisive preferences mandatorily (see Theorem 12). In the related literature on metric distortion, top decisiveness (i.e., decisiveness between the best and second-best alternatives) has been explored extensively, but assuming other forms of decisiveness (such as uniform decisiveness) and eliciting decisive preferences deserves further exploration. Exploring the impact of decisive agent preferences on other important desiderata such as fairness (e.g., proportional fairness (Ebadian et al. 2022)) and strategyproofness is also an exciting direction for the future.

Acknowledgments Latifian and Shah were partially supported by an NSERC Discovery Grant.

References Abramowitz, B.; Anshelevich, E.; and Zhu, W. 2019. Awareness of voter passion greatly improves the distortion of metric social choice. In International Conference on Web and Internet Economics, 3 16. Springer. Amanatidis, G.; Birmpas, G.; Filos-Ratsikas, A.; and Voudouris, A. A. 2021. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artificial Intelligence, 296: 103488. Anagnostides, I.; Fotakis, D.; and Patsilinakos, P. 2022. Metric-distortion bounds under limited information. Journal of Artificial Intelligence Research, 74: 1449 1483. Anshelevich, E.; Bhardwaj, O.; Elkind, E.; Postl, J.; and Skowron, P. 2018. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264: 27 51. Anshelevich, E.; Filos-Ratsikas, A.; Shah, N.; and Voudouris, A. A. 2021. Distortion in Social Choice Problems: The First 15 Years and Beyond. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 4294 4301. Survey Track. Anshelevich, E.; and Postl, J. 2017. Randomized social choice functions under metric preferences. Journal of Artificial Intelligence Research, 58: 797 827. Aziz, H. 2020. Justifications of welfare guarantees under normalized utilities. ACM SIGecom Exchanges, 17(2): 71 75. Benade, G.; Nath, S.; Procaccia, A. D.; and Shah, N. 2021. Preference elicitation for participatory budgeting. Management Science, 67(5): 2813 2827. Borodin, A.; and El-Yaniv, R. 2005. Online computation and competitive analysis. Cambridge University Press. Borodin, A.; Halpern, D.; Latifian, M.; and Shah, N. 2022. Distortion in voting with top-t preferences. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 116 122. Boutilier, C.; Caragiannis, I.; Haber, S.; Lu, T.; Procaccia, A. D.; and Sheffet, O. 2015. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227: 190 213. Brams, S. J.; and Sanver, M. R. 2009. Voting systems that combine approval and preference. In The mathematics of preference, choice and order, 215 237. Springer. Caragiannis, I.; Nath, S.; Procaccia, A. D.; and Shah, N. 2017. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58: 123 152. Caragiannis, I.; and Procaccia, A. D. 2011. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(9-10): 1655 1671. Ebadian, S.; Kahng, A.; Peters, D.; and Shah, N. 2022. Optimized Distortion and Proportional Fairness in Voting. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 563 600.

Ghodsi, M.; Latifian, M.; and Seddighin, M. 2019. On the distortion value of the elections with abstention. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), volume 33, 1981 1988. Gkatzelis, V.; Halpern, D.; and Shah, N. 2020. Resolving the optimal metric distortion conjecture. In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS), 1427 1438. Gross, S.; Anshelevich, E.; and Xia, L. 2017. Vote until two of you agree: Mechanisms with small distortion and sample complexity. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 544 -550. Kizilkaya, F. E.; and Kempe, D. 2022. Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 349 355. Mandal, D.; Procaccia, A. D.; Shah, N.; and Woodruff, D. P. 2019. Efficient and thrifty voting by any means necessary. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (Neur IPS), 7180 7191. Mandal, D.; Shah, N.; and Woodruff, D. P. 2020. Optimal communication-distortion tradeoff in voting. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), 795 813. Procaccia, A. D.; and Rosenschein, J. S. 2006. The distortion of cardinal preferences in voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA), 317 331.