# convergence_in_multiissue_iterative_voting_under_uncertainty__0d60f551.pdf

Convergence of Multi-Issue Iterative Voting under Uncertainty

Joshua Kavner1 , Reshef Meir2 , Francesca Rossi3 and Lirong Xia1

1Rensselaer Polytechnic Institute 2Technion Israel Institute of Technology 3IBM T.J. Watson Research Center kavnej@rpi.edu, reshefm@ie.technion.ac.il, Francesca.Rossi2@ibm.com, xialirong@gmail.com

We study strategic behavior in iterative plurality voting for multiple issues under uncertainty. We introduce a model synthesizing simultaneous multiissue voting with local dominance theory, in which agents repeatedly update their votes based on sets of vote profiles they deem possible, and determine its convergence properties. After demonstrating that local dominance improvement dynamics may fail to converge, we present two sufficient model refinements that guarantee convergence from any initial vote profile for binary issues: constraining agents to have O-legal preferences, where issues are ordered by importance, and endowing agents with less uncertainty about issues they are modifying than others. Our empirical studies demonstrate that while cycles are common for agents without uncertainty, introducing uncertainty makes convergence almost guaranteed in practice.

1 Introduction

Consider a wedding planner who is deciding a wedding s banquet and wants to accommodate the party invitees preferences. 1 There are three issues with two candidates each: the main course (chicken or beef), the paired wine (red or white), and the cake flavor (chocolate or vanilla). How should the planner proceed? On the one hand, they could request each attendee s (agent s) full preference ranking over the 2p alternatives, for p binary issues. However, this is computationally prohibitive and imposes a high cognitive cost for agents. On the other hand, the planner could solicit only agents votes and decide each issue simultaneously. Although simpler, this option admits multiple election paradoxes whereby agents can collectively select each of their least favored outcomes. For example, suppose three agents prefer (1, 1, 0), (1, 0, 1), and (0, 1, 1) first, respectively on the issues, and all prefer (1, 1, 1) last. Then the agents select (1, 1, 1) by majority rule on each issue independently [Lacy and Niou, 2000]. A third approach is to decide the issues in sequence and have agents vote for their preferred alternative on the current

1The full version of the paper may be found on the archive at: https://arxiv.org/abs/2301.08873

issue given the previously chosen outcomes. Still, the joint outcome may depend on the voting agenda and agents may be uneasy voting on the current issue if their preference depends on the outcomes of later issues [Conitzer et al., 2009]. In this work, we study iterative voting (IV) as a different yet natural method for deciding multiple issues [Meir et al., 2010]. We elicit agents most preferred alternatives and, given information about others votes, allow agents to update their reports before finalizing the group decision. This approach combines the efficiency of simultaneous voting with the dynamics of sequential voting, thus incorporating information about agents lower-ranked preferences without directly eliciting them. Like the former approach, agents only report their most preferred alternative. Like the latter approach, agents only update one issue at a time but are unrestricted in the order of improvements. IV is an effective framework for its adaptability to various information and behavioral schemes. First, we consider agents with full information about the real vote profile, such as in online Doodle polls [Zou et al., 2015], who update their votes to the best response of all others. Second, we consider agents with access only to a noisy signal about the real vote profile, such as from imprecise opinion polls [Reijngoud and Endriss, 2012] or latency in a networked system if they can only periodically retrieve accurate vote counts. These agents update their votes to those that locally dominate their prior reports votes that achieve weakly better outcomes for all possible vote profiles and strictly better outcomes for some possible vote profile [Meir et al., 2014]. We ask two primary questions: (1) Under what conditions does multi-issue IV converge? (2) How does introducing and increasing uncertainty affect the rate of convergence? Prior work in single-issue IV offers mixed answers, as iterative plurality and veto have strong convergence guarantees but many other rules do not [Meir et al., 2017]. This leaves us with mixed hope in the multi-issue plurality case, and if so, that it can solve other problems like multiple election paradoxes. Furthermore, in contrast to prior work, uncertainty for multiple issues plays a double role. First, like the singleissue case, agents consider themselves as possibly pivotal on any issue that is sufficiently close to a tie. Second and this part is new agents may be uncertain whether changing their vote on an issue would improve or degrade the outcome, as this may depend on the outcomes of other uncertain issues.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

1.1 Our Contribution On the conceptual side, we introduce a novel model that synthesizes prior work in local dominance strategic behavior, iterative plurality voting, and simultaneous voting over multiple issues. This generalized model naturally captures both types of uncertainty discussed above. On the technical side, we first show that IV with or without uncertainty may not converge. We then present two model refinements that prove sufficient to guarantee convergence for binary issues: restricting agent preferences to have O-legal preferences and alternating uncertainty, in which agents are more certain about the current issue than others. The former converges because agents preferences on issues are not interdependent; the latter because fewer preference rankings yield valid improvement steps. These convergence results do not extend to the multi-candidate issues setting, as IV may cycle if agents have partial order preference information. Our convergence results for binary issues also hold for a nonatomic variant of plurality IV in which agents are part of a large population and arbitrary subsets of agents may change their vote simultaneously, establishing more general convergence results. This is discussed separately in Appendix C. We conclude with empirical evidence corroborating our findings that introducing uncertainty eliminates almost all cycles in IV for multiple binary issues. Our experiments further suggest IV improves the quality of equilibrium vote profiles relative to their respective truthful profiles, thus reducing multiple election paradoxes. Increasing uncertainty yields faster convergence but degrades this welfare improvement.

1.2 Related Work Our model pulls insights from research across multi-issue voting, IV, and local dominance strategic behavior. Multiissue voting is an extensively studied problem in economics and computer science with applications in direct democracy referendums, group planning and committee elections (see e.g., [Lang and Xia, 2016] for a survey). Our work follows research in agent strategic behavior by Lang [2007], Lang and Xia [2009], Conitzer et al. [2009], and Xia et al. [2011]. Single-issue IV was initially studied by Meir et al. [2010] for best response dynamics and the plurality social choice rule, whose authors bounded its guaranteed convergence rate. Subsequent work demonstrated that iterative veto converges [Reyhani and Wilson, 2012; Lev and Rosenschein, 2012], although many other voting rules do not [Koolyk et al., 2017] unless agents are additionally restricted in their behavior [Reijngoud and Endriss, 2012; Grandi et al., 2013; Obraztsova et al., 2015; Endriss et al., 2016]. This review already narrows down the possibility of convergence in the multi-issue setting. We therefore restrict our attention to plurality, extending the models of Meir et al. [2014] and Meir [2015]. Their research found broad conditions for voting equilibrium to exist and guaranteed convergence for iterative plurality. In particular, Meir [2015] studied a nonatomic model variation where agents have negligible impact on the outcome but multiple agents update their votes simultaneously, greatly simplifying the dynamics. Bowman et al. [2014] and Grandi et al. [2022] empirically demonstrated for multiple binary issues that IV improves the

social welfare of voting outcomes using computer simulations and human experiments respectively. Our work augments this research by characterizing convergence in settings where agents do not have complete information. Related research studied strategic behavior in epistemic voting games when agents have uncertainty about the preferences or votes of others (see e.g., [Meir, 2018] for a survey). Notably, Chopra et al. [2004], Conitzer et al. [2011], Reijngoud and Endriss [2012], and Van Ditmarsch et al. [2013] focused on the susceptibility and computational complexity of voting rules to local dominance improvement steps. Game-theoretic properties of strategic behavior for Gibbard Satterthwaite games were studied by Myerson and Weber [1993], Grandi et al. [2019], and Elkind et al. [2020]. Other forms of IV include work from Airiau and Endriss [2009], Desmedt and Elkind [2010], and Xia and Conitzer [2010].

2 Preliminaries Basic model. Let P = {1, 2, . . . , p} be the set of p issues over the joint domain D = p i=1Di, where Di is the finite value domain of candidates for issue i. We call the issues binary if Di = {0, 1} for each i P or multi-candidate otherwise. Each of n agents is endowed with a preference ranking Rj L(D), the set of strict linear orders over the Qp i=1 |Di| alternatives. We call the collection of agents preferences P = (R1, . . . , Rn) a preference profile and each agent s most preferred alternative their truthful vote. A vote profile a = (a1, . . . , an) Dn is a collection of votes, where aj = (a1 j, . . . , ap j) D collects agent j s single-candidate vote per issue. A resolute voting rule f : Dn D maps vote profiles to a unique outcome. We call a D and ai Di for i P an alternative or outcome synonymously. Simultaneous plurality voting. A local voting rule, applied to each issue independently, is simultaneous if issues outcomes are revealed to agents at the same time. It is sequential according to the order O = {o1, . . . , op} if outcomes of each issue oi are revealed to agents prior to voting on the next issue oi+1 [Lacy and Niou, 2000]. We focus on simultaneous plurality voting and adapt the framework of Xia et al. [2011]. The plurality rule f i(a) applied to vote profile a on issue i only depends on the total number of votes for each of its candidates. We define the score tuple s(a) := (si(a))i P as a collection of score vectors si(a) = (si(c; a))c Di, which compose the score of a candidate c Di as si(c; a) = |{j n : ai j = c}|. We use the plurality rule f(a) = (f i(a))i P D, where f i(a) = arg maxc Di si(c; a), breaking ties lexicographically on each issue. Let a j denote the vote profile without agent j and (a j, ˆaj) the profile a by replacing j s vote with the prospective vote ˆaj. Then s j and s j + ˆaj denote corresponding adjusted score tuples without j and upon replacing j s vote. We may interchange s, s(a), and a for ease of notation. Preferential dependence. A preference ranking is called separable if the relative ordering of candidates in each issue s domain Di is consistent across all outcomes of the other issues. That is, an agent prefers one outcome over another if they prefer the former s candidates on each issue independently. Such rankings have the advantage that agents

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

may express their preferences on individual issues and avoid multiple-election paradoxes, but it is a very demanding assumption [Xia et al., 2011; Hodge, 2002]. Relaxing rankings to be O-legal maintains representation compactness without permitting arbitrary preferential dependencies. Then agents may declare their preferences over an issue s candidates once given the previous outcomes. Formally, for some order O = {o1, . . . , op} over the issues, the preference ranking R is called O-legal if, given the outcomes of the prior issues {f o1, f o2, . . . , f oi 1}, the relative ordering of candidates in Doi is constant for any combination of outcomes of the later issues {f oi+1, . . . , f op} [Lang and Xia, 2009]. Hence, the ranking of candidates Doi in R depends only, if at all, on outcomes of issues prior to it in O. The preference profile P is called O-legal if every ranking is O-legal for the same order O; the ranking R is separable if it is O-legal for any order O.

Example 1. Consider p = 2 binary issues and n = 3 agents with preference profile P = (R1, R2, R3) such that: R1 : (1, 0) 1 (0, 0) 1 (0, 1) 1 (1, 1), R2 : (1, 1) 2 (0, 0) 2 (0, 1) 2 (1, 0), and R3 : (0, 0) 3 (0, 1) 3 (1, 0) 3 (1, 1). The truthful vote profile a = ((1, 0), (1, 1), (0, 0)) consists of each agent s most preferred alternative. The score tuple is then s(a) = {(1, 2), (2, 1)}, so with plurality f(a) = (1, 0). Note that R1 is O-legal for O = {2, 1}: the agent always prefers 0 1 on the second issue, yet their preference for the first issue depends on f 2. R3 is separable, as the agent prefers 0 1 on each issue independent of the other issue s outcome. R2 is neither separable nor O-legal for any O. Furthermore, agent 2 can improve the outcome for themselves by voting for ˆa2 = (0, 1) instead of a2 = (1, 1). The adjusted score tuple is s 2 = {(1, 1), (2, 0)}, so s 2 + ˆa2 = {(2, 1), (2, 1)} and f(s 2 + ˆa2) = (0, 0) 2 (1, 0) = f(a).

Improvement dynamics. We implement iterative voting (IV) as introduced by Meir et al. [2010] and refined for uncertainty by Meir et al. [2014] and Meir [2015]. Given agents truthful preferences P and an initial vote profile a(0), we consider an iterative process of vote profiles a(t) = (a1(t), . . . , an(t)) that describe agents reported votes over time t 0. For each round t, a scheduler ϕ chooses an agent j to make an improvement step over their prior vote aj(t) by applying a specified response function gj : Dn D. Each agent s response implicitly depends on their preferences and belief about the current real vote profile, but they are not aware of others private preferences. All other votes besides j s remain unchanged. A scheduler is broadly defined as a mapping from sequences of vote profiles to an agent with an improvement step in the latest vote profile [Apt and Simon, 2015]. An improvement step must be selected if one exists, and a vote profile where no improvement step exists (i.e., gj(a) = aj j n) is called an equilibrium. The literature on game dynamics considers different types of response functions, schedulers, initial profiles, and other assumptions (see e.g., Fudenberg and Levine [2009], Marden et al. [2007], Bowling [2005], Young [1993], and Meir et al. [2017]). This means that there are multiple levels in which a voting rule may guarantee con-

vergence to an equilibrium. In this work, we study two response functions: best response (BR), without uncertainty, and local dominance improvements (LDI), with uncertainty. For both dynamics, we restrict agents to only changing their vote on a single current issue i P per round, as determined by the scheduler ϕ. We therefore have the following form of convergence, as described by Kukushkin [2011], Monderer and Shapley [1996], and Milchtaich [1996]:

Definition 1. An IV dynamic has the restricted-finite improvement property if every improvement sequence is finite from any initial vote profile for a given response function.

Under BR dynamics, agents know the real score tuple s(a).

Definition 2 (Best response). Given the vote profile a, gj(a) := ˆaj which yields agent j s most preferred outcome of the set {f(a j, aj) : ai j Di, ak j = ak j k = i} unless there is no change in the outcome; then gj(a) := aj.

LDI dynamics are based on the notions of strict uncertainty and local dominance [Conitzer et al., 2011; Reijngoud and Endriss, 2012]. Let S p i=1N|Di| be a set of score tuples that, informally, describes agent j s uncertainty about the real score tuple s(a). An LDI step to a prospective vote ˆaj is one that is weakly better off than their original aj for every v S and strictly better off for some v S, as follows.

Definition 3. The vote ˆaj S-beats aj if there is at least one score tuple v S such that f(v + ˆaj) j f(v + aj). The vote ˆaj S-dominates aj if both (I) ˆaj S-beats aj; and (II) aj does not S-beat ˆaj.

Definition 4 (Local dominance improvement). Given the vote profile a and agent j, let LDi j be the set of votes that S-dominate aj, only differ from aj on the ith issue, and are not themselves S-dominated by any other vote differing from aj only on the ith issue. Then gj(a) = aj if LDi j = and ˆaj LDi j otherwise.

This definition distinguishes from (weak) LDI in Meir [2015] in that agents may change their votes consecutively but only on different issues. Note that S-dominance is transitive and antisymmetric, but not complete, so an agent j may not have an improvement step. To fully define the model, we need to specify S for every a. For example, if S = {s(a j)} and each j has no uncertainty about the real score tuple, then LDI coincides with BR and an equilibrium coincides with Nash equilibrium. Therefore, LDI broadens BR dynamics.

Distance-based uncertainty. Agents in the single-issue model construed their uncertainty sets using distance-based uncertainty, in which all score vectors close enough to the current profile were believed possible [Meir et al., 2014; Meir, 2015]. We adapt this to the multi-issue setting by assuming agents uphold candidate-wise distance-based uncertainty over score vectors for each issue independently. For any issue i P, let δ(si(a), si(a)) be a distance measure for score vectors for any vote profile a. This measure is candidate-wise if it can be written as δ(si(a), si(a)) = maxc Di ˆδ(si(c; a), si(c; a)) for some monotone function ˆδ. For example, the ℓ metric, where ˆδ(s, s) = |s s|, is candidate-wise.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Given the vote profile a and issue i P, we model agent j s uncertainty about the adjusted score vector si j by the uncertainty score set Si j(s; ri j) := vi : δ(vi, si j) ri j

with an uncertainty parameter ri j. That is, given other votes ai j, agent j is not sure what the real score vector is within Si j(s; ri j). We define S j(s, rj) := p i=1 Si j(s; ri j) for rj = (ri j)i P, and drop the parameters if the context is clear. Example 2. Consider p = 2 binary issues and n = 13 agents with the vote profile a defined such that seven agents vote (0, 0), three agents vote (1, 1), two agents vote (1, 0), and the last agent, which we label j, votes aj = (0, 1). The score tuple is then s(a) = {(8, 5), (9, 4)}, so f(a) = (0, 0). Under BR dynamics, j has complete information about s(a) and can compute s j(a) = {(7, 5), (9, 3)}. Clearly, no prospective vote ˆaj can change the outcome f(a j, ˆaj). Under LDI dynamics, agent j has incomplete information about s(a). Suppose that j uses the ℓ uncertainty metric with uncertainty parameters (r1 j, r2 j) = (1, 1). By the above definitions, the uncertainty score set for issue i {1, 2} is Si j(s; ri j) = {vi : |vi si j| ri j}

= {(6, 7, 8) (4, 5, 6)} {(8, 9, 10) (2, 3, 4)}

which is a bandwidth of ri j = 1 around each real score si j. Finally, consider the prospective vote ˆaj = (1, 1). Then S j + ˆaj = {(6, 7, 8) (5, 6, 7)} {(8, 9, 10) (3, 4, 5)} so that {f(v + ˆaj) : v S j} = {(0, 0), (1, 0)}.

3 Best-Response Dynamics Given the vote profile a, consider agent j changing their vote aj on issue i to the prospective vote ˆaj. Under BR dynamics, without uncertainty, j changes their vote only if they can feasibly improve the outcome f(a) to one more favorable with respect to Rj. This happens under two conditions. First, j must be pivotal on the ith issue, meaning that changing their vote will necessarily change the outcome. Second, j must be preferential to change i by voting for ˆai j over ai j given the outcomes of the other issues P\{i}. Agent j s preferences are always well-defined since they know every issue s real outcome. Thus BR dynamics behave similar to the single-issue setting, which we recall converges [Meir et al., 2010]. However, in the multi-issue setting, agents preferences on each issue may change as other issues outcomes change. This entails the possibility of a cycle, as declared in the following proposition and proved with the subsequent example. Proposition 1. BR dynamics for multiple issues may not converge, even if issues are binary. Example 3. Let there be p = 2 binary issues and n = 3 agents without uncertainty and the following preferences: R1 : (0, 1) 1 (1, 1) 1 (1, 0) 1 (0, 0), R2 : (0, 0) 2 (0, 1) 2 (1, 1) 2 (1, 0), and R3 : (1, 0) 3 (1, 1) 3 (0, 0) 3 (0, 1). Table 1 demonstrates a cycle via BR dynamics from the truthful vote profile a(0). The order of improvement steps is j = (1, 2, 1, 2). No other BR step is possible from any profile in the cycle, so no agent scheduler can lead to convergence.

Agent j aj(0) aj(1) aj(2) aj(3)

1 (0, 1) (1, 1) (1, 1) (0, 1) 2 (0, 0) (0, 0) (0, 1) (0, 1) 3 (1, 0) (1, 0) (1, 0) (1, 0)

f(a) (0, 0) (1, 0) (1, 1) (0, 1)

Table 1: Agents votes for a(0) (truthful), a(1), a(2), and a(3).

4 Local Dominance Improvement Dynamics LDI dynamics broadens best-response since agents uncertainty score sets contain the true score tuple, by definition, but it is initially unclear how uncertainty affects the possibility of cycles. Seemingly, greater uncertainty over an agent s current issue increases the possibility of having LDI steps over that issue, whereas greater uncertainty over other issues decreases this possibility. We demonstrate in Section 4.1 below that this relationship holds only for binary issues, but it does not eliminate the possibility of cycles, as declared in the following proposition and proved with Example 5 in Appendix B. Proposition 2. LDI dynamics with multiple issues may not converge, even if agents have the same constant uncertainty parameters and issues are binary. This finding contrasts convergence guaranteed in the single-issue setting with uncertainty [Meir, 2015]. After explaining the effect of uncertainty on LDI steps, we conclude the section with two model refinements that prove sufficient to guarantee convergence for binary issues: O-legal preferences and a form of dynamic uncertainty.

4.1 Effect of Uncertainty on LDI Steps Given the vote profile a among binary issues, consider agent j changing their vote aj on issue i to the prospective vote ˆaj. Under LDI dynamics, j changes their vote only if two conditions hold, similar to BR dynamics: if (I) they believe they may be pivotal on issue i and (II) they can improve the outcome with respect to Rj. Notice that if the agent is pivotal on the binary issue i with respect to an uncertainty parameter ri j, it is pivotal with respect to all larger parameters rj : ri j > ri j over i. Furthermore, recall that j s preference over candidates of issue i may depend on the outcomes of other issues, which j may be uncertain about. It stands to reason that the more uncertainty j has over other issues, the less clarity the agent has over their own preference for issue i s candidates. We realize the following monotonic relationship between the magnitude of agents uncertainty parameters and whether they have an LDI step over an issue: increasing uncertainty on issue i may only add LDI steps over issue i but may only eliminate LDI steps over each other issue. This is stated technically in the following proposition. First, we define three uncertainty parameters αj, rj, and βj such that: rj and αj only differ on issue k = i such that rk j < αk j ; rj and βj only differ on issue i such that ri j < βi j. Let LDi j(rj) denote agent j s possible LDI steps as in Definition 4 with respect to the uncertainty parameter rj. Proposition 3. Given binary issues, consider agent j changing their vote on issue i in vote profile a with one of three

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

uncertainty parameters αj, rj, or βj as defined above. Then LDi j(αj) LDi j(rj) LDi j(βj). The theorem is proved in two parts by demonstrating that if a vote ˆaj S j(a; αj)-dominates aj, then it must hold that ˆaj S j(a; rj)-dominates aj; likewise, this implies that ˆaj S j(a; βj)-dominates aj. Each of these relationships arise as a result of S j(a; rj) S j(a; αj) and S j(a; rj) S j(a; βj). This is sufficient to prove since issues are binary. The full proof may be found in Appendix A. We find that this relationship between agents uncertainty parameters and their LDI steps is not monotonic in the generalized case of multi-candidate issues, as Example 6 in Appendix B demonstrates that different sets of prospective votes LDi j may not be comparable for an agent j with different uncertainty parameters even from the same vote profile a.

4.2 Strategic Responses and O-legal Preferences We are motivated by observing in Examples 3 and 5 that cycles appear due to agents interdependent preferences among the issues. Specifically, in Table 1, a cycle is formed as agents 1 and 2 switch their preferences among candidates for one issue when the other issue changes outcomes, and this holds for opposite issues. It therefore stands to reason that eliminating interdependent preferences by fixing agents with a O-legal preference profile would guarantee convergence. We prove that this is the case in Theorem 1. To state this result technically, we first introduce a characterization about agents strategic responses, extending a lemma from Meir [2015] to the multi-issue setting. Definition 5. Agent j believes a candidate c on issue i is a possible winner if there is some score vector where c wins: W i j(a) := {c Di : v S j(a; rj) s.t. f i(v+aj) = c} In contrast, j calls c a potential winner if there is some score vector in which they can vote to make c win: Hi j(a) = {c Di : v S j(a; rj) and ˆaj s.t. ˆai j = c, ˆak j = ak j k = i, s.t. f i(v + ˆaj) = c}. The set of real potential winners is denoted: Hi 0(a) = {c Di : f i(s j + ˆaj) = c where ˆai j = c, ˆak j = ak j k = i}.

By this definition, W i j(a) Hi j(a). 2 Denote by W i(a; rj) = k P\{i}W k j (a) the set of possible winning candidates on all issues besides i, from agent j s perspective with uncertainty parameter rj.

Lemma 1. Consider an LDI step aj j ˆaj over issue i from vote profile a by agent j with uncertainty parameter rj. Then either (1) ai j / Hi j(a); or for every combination of possible winners in W i(a; rj), either (2) ai j j b for all b Hi j(a) or (3) ri j = 0, {ai j, ˆai j} Hi 0(a) and ˆai j j ai j. The proof of this lemma directly follows that of Lemma 3 in Meir [2015]; see Appendix A for the full proof.

2Without uncertainty, Hi j(a) (or Hi j(a) {ai j} if adding a vote to ai j makes it win) is also known as the chasing set (excluding f(a)) [Rabinovich et al., 2015] or potential winner set (including f(a)) [Kavner and Xia, 2021] on issue i. Hi j(a) coincides with Meir et al. [2014] and Meir [2015] s definition of a possible winner Wj(s).

Theorem 1. LDI dynamics converge over binary issues when all agents have O-legal preferences for the common order O.

Proof. Fix an initial vote profile a(0). Suppose for contradiction that there is a cycle among the vote profiles C = {a(t1), . . . , a(t T )}, where a(t T + 1) = a(t1) and a(t1) is reachable from a(0) via LDI dynamics. Let i be the highest order issue in O for which any agent changes their vote in C. Let t [t1, t T ) be the first round that some agent j takes

an LDI step on issue i, where aj j ˆaj from vote profile a(t ); let t (t , t T ] be the last round that j switches their vote on i back to ai j. It must be the case that ai j Hi j(a(t )), since issues are binary and otherwise, |Hi j(a(t ))| = 1 and j would not have an improvement step. Hence by Lemma 1, ˆai j j ai j for every combination of possible winners in W i(a(t ); rj). Likewise, on round t , ai j j ˆai j for every combination of possible winners in W i(a(t ); rj). Thus for some issue k and outcomes x, y {0, 1}, x = y, we have W k j (a(t )) = {x} and W k j (a(t )) = {y}. Since j has O-legal preferences, k must be prior to issue i in the order O. However, no agent changed their vote on issue k between rounds t and t so it must be that x W k j (a(t )), even if j s uncertainty parameters changed. This forms a contradiction, so no such cycle can exist.

The intuition behind Theorem 1 is that as an LDI sequence develops, there is some foremost issue i in which no LDI step takes place on any issue prior to i in the order O. Agents relative preferences for the candidates in i are fixed because their preferences are O-legal: score vectors for issues prior to i in O do not change, while scores of issues afterward do not affect agents preferences for i. Hence, agents improvement steps over the issue i converge, whereas any cycle must have a sub-sequence of vote profile whose votes for issue i cycles. Note that O-legality is not necessary for convergence, as BR dynamics induced from the truthful vote profile in Example 1 converge. Although O-legality is a strict assumption, loosening this even slightly may lead to cycles. Example 3 demonstrates a cycle in which each agent has an O-legal ranking but orders differ between agents. Separately, the theorem describes that LDI steps over the issue i eventually terminate, thus enabling each subsequent issue in O to converge. This seems to suggest that IV under O-legal preferences is the same as truthful sequential voting, where agents vote for their preferred alternative on each issue oi given the known previous outcomes of {o1, . . . , oi 1} [Lang and Xia, 2009]. Although the procedures outcomes could be the same, there are two notable differences. First, the initial vote profile could have an issue whose outcome differs from the truthful sequential outcome and no agent has an improvement step on that issue. Second, depending on the scheduler, agents may not have further improvement steps over an issue intermediately before IV reaches the same outcome as in truthful sequential voting. This convergence result does not extend to the multicandidate case, as declared in the following proposition and proved with the subsequent example.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Proposition 4. LDI dynamics may not converge for multiple issues, even if agents have the same constant uncertainty parameters and O-legal preferences for the common order O. Example 4. Consider p = 2 issues and n = 15 agents who each use the ℓ uncertainty metric with common fixed uncertainty parameters (r1 j, r2 j) = (2, 1) j n. Label the candidates {0, 1} and {a, b, c, d} respectively. Agent j has preferences: if f 1 = 0 then b j c j a j d on the second issue; otherwise c j b j a j d. Agent k always prefers a k d k b k c on the second issue. These preferences are O-legal for O = {1, 2}. Define a(0) so s(a(0)) = {(7, 8), (3, 5, 5, 2)} and aj(0) = ak(0) = (0, a). There are four LDI steps involved in this

cycle: (i) (0, a) j (0, d), (ii) (0, a) k (0, d), (iii) (0, d) j

(0, a), and (iv) (0, d) k (0, a). We prove these steps are valid in Appendix B. Note that H2 j (a(0)) = {a, b, c} and H2 j (a(2)) = {b, c, d}. In contrast to the single-issue setting (see Lemma 4 of Meir [2015]), agent j takes LDI steps to candidates not in the potential winning set. This results from j s uncertainty over whether b or c is most-preferred, even as both are preferable to a and d. Hence, we get the following corollary: Corollary 1. LDI dynamics may not converge for plurality over a single issue for agents with partial order preferences.

4.3 Alternating Uncertainty In Proposition 3 we found that for binary issues, agents may have fewer LDI steps over an issue i if that issue has less uncertainty and other issues have more. This suggests that LDI steps occur from a relative lack of information about the current issue s score vector than for other issues. If agents can gather more information about the current issue before changing their vote, thereby decreasing its uncertainty relative to other issues, then they may not have an LDI step. We therefore consider a specific form of dynamics over agents uncertainty parameters where agents can gather this information and consider themselves pivotal only with respect to the lowered uncertainty. Agents are assumed to subsequently forget this relative information since it may be outdated by the time they change their vote again. We show in the following theorem that this eliminates cycles. Definition 6. (Alternating Uncertainty.) Fix two parameters rc j, ro j for each agent j such that rc j < ro j. Define each agent j s uncertainty parameters such that whenever they are scheduled to change their vote on issue i, j s uncertainty for i is rc j and for each other issue k = i the uncertainty is ro j. Theorem 2. Given binary issues, LDI dynamics converges for agents with alternating uncertainty.

Proof. Fix an initial vote profile a(0) and uncertainty parameters rc j, ro j for each agent j n. Suppose for contradiction that there is a cycle among the vote profiles C = {a(t1), . . . , a(t T )}, where a(t T + 1) = a(t1) and a(t1) is reachable from a(0) via LDI dynamics. Without loss of generality, suppose all issues and agents are involved in the cycle. Consider the agent j with the largest ro j = maxu n ro u. Let t [t1, t T ) be the first round that j takes an LDI step

on issue i, where aj j ˆaj from vote profile a(t ); let t (t , t T ] be the last round that j switches their vote on i back to ai j. It must be the case that ai j Hi j(a(t )), since issues are binary and otherwise, |Hi j(a(t ))| = 1 and j would not have an improvement step. Hence by Lemma 1, ˆai j j ai j for every combination of possible winners in W i(a(t ); rj). Likewise, on round t , ai j j ˆai j for every combination of possible winners in W i(a(t ); rj). Thus for some issue k and outcomes x, y {0, 1}, x = y, we have W k j (a(t )) = {x} and W k j (a(t )) = {y}. Let t (t , t ) be the first round since t that some agent h changes their vote on issue k. Then Hk h(a(t )) = {0, 1}. Since W k j (a(t )) = W k j (a(t )) = {x} {0, 1} and distance functions are candidate-wise, rc h ro j. This entails ro h > ro j by definition of alternating uncertainty, which contradicts the assertion that j is the agent u with the largest ro u.

This convergence result does not extend to the multicandidate case, as Example 4 also covers this setting.

5 Experiments

Our computational experiments investigate the effects of uncertainty and numbers of binary issues and agents on LDI dynamics. Specifically, we ask how often truthful vote profiles are themselves in equilibrium, how often LDI dynamics do not converge, and the path length to equilibrium given that LDI dynamics do converge. Our inquiry focuses on whether cycles are commonplace in practice even though convergence is not guaranteed. We answer these questions for a broad cross-section of inputs, with n {7, 11, 15, 19} agents, p {2, 3, 4, 5} binary issues, and r {0, 1, 2, 3} uncertainty that is constant for all agents, issues, and rounds. We generate 10, 000 preference profiles for each combination by sampling agents preferences uniformly and independently at random. We simulate LDI dynamics from the truthful vote profile using a scheduler that selects profiles uniformly at random from the set of valid LDI steps among all agents and issues. If there are no such steps, we say the sequence has converged. Otherwise, we take 50, 000 rounds as a sufficiently large stopping condition to declare the sequence has cycled. Our results are presented in Figures 1 3 with respect to n. As uncertainty is introduced and r increases, given p = 5, the availability of LDI steps diminishes significantly from the initial vote profile (Figure 1) and throughout the dynamics to eliminate (almost) all cycles and shorten the path length to convergence (Figure 3). Figure 2 presents the number of initial vote profiles whose LDI sequence cycles for r = 0, given that they are not themselves in equilibrium; only five of the sampled r 1 profiles sequences cycle. Therefore, cycles with uncertainty are the exception rather than the norm. These findings corroborate our theoretical analysis. As uncertainty increases, more issues are perceived by agents to have more than one possible winner. Since issues are interdependent for many preference rankings, fewer agents have LDI steps. On the other hand, as n increases, more agents

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Figure 1: Percentage of truthful vote profiles not in equilibrium as n increases.

Figure 2: Number of truthful vote profiles whose LDI sequences cycle as n increases.

have rankings without these interdependencies, thus increasing the availability of LDI steps. As an additional inquiry, we studied how IV affects the quality of outcomes by comparing the social welfare of equilibrium to truthful vote profiles.3 We find in Figure 4 that IV improves average welfare, but at a rate decreasing in r. This finding agrees with experiments by Bowman et al. [2014] and Grandi et al. [2022], suggesting that IV may reduce multipleelection paradoxes by helping agents choose better outcomes. However, further work will be needed to generalize this conclusion, as it contrasts experiments of single-issue IV by Meir et al. [2020] and Koolyk et al. [2017].

6 Discussion and Open Questions

We have introduced a novel model of strategic behavior in iterative voting (IV) for multiple issues under uncertainty. We find that for binary issues, the existence of cycles hinges on the interdependence of issues in agents preference rankings. Specifically, once an agent j takes an LDI step on an issue i, they only subsequently revert their vote if their preference for i changes. This occurs if the possible winning candidates among other issues that affect j s preference for i change. Without this interdependence, agents preference over indi-

3Measured by the percent change in Borda welfare. The Borda utility of outcome a for ranking R is 2p minus the index of a s position in R; the Borda welfare is the sum of utilities across agents.

Figure 3: Average number steps for LDI sequences to converge as n increases; log scale; 95% CI (too small to show).

Figure 4: Average percent change in Borda welfare as n increases; 95% CI (too small to show).

vidual issues change only finite times, so LDI dynamics converge (Theorem 1). We also find that as uncertainty increases over issues other than the one agents are changing, fewer preference rankings admit LDI steps, eliminating cycles (Theorem 2). Convergence does not extend to multi-candidate issues since LDI dynamics may cycle if agents only have partial order preference information (Corollary 1). Our experiments confirm that convergence is practically guaranteed with uncertainty, despite its possibility, and suggests IV improves agents social welfare over truthful outcomes. There are several open directions for future work. First, our empirical study was limited by sampling agents preferences from the impartial culture preference distribution and measuring additive social welfare (see e.g., [Tsetlin et al., 2003; Sen, 1999]). Proving IV s welfare properties for more realistic preference distributions and welfare functions may follow the research in dynamic price of anarchy of Brˆanzei et al. [2013] and Kavner and Xia [2021] and in smoothed analysis of Xia [2020]. Second, IV is useful for protecting agents privacy, in part, as it does not explicitly reveal agents truthful preferences. However, agents implicitly reveal partial information through their improvement steps. Studying IV when agents account for others preferences based on current information is an interesting open direction. A third direction is detailing the axiomatic properties of multi-issue IV rules that may be inherited by the decision rule used locally on each issue, as studied for sequential voting by Xia et al. [2011].

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Acknowledgments

Lirong Xia acknowledges NSF #1453542, #2007994, and #2106983, and a Google Research Award for support. Reshef Meir is supported by the Israel Science Foundation (ISF; Grant No. 2539/20).

[Airiau and Endriss, 2009] St ephane Airiau and Ulle Endriss. Iterated majority voting. In International Conference on Algorithmic Decision Theory, pages 38 49. Springer, 2009.

[Apt and Simon, 2015] Krzysztof R Apt and Sunil Simon. A classification of weakly acyclic games. Theory and Decision, 78(4):501 524, 2015.

[Bowling, 2005] Michael Bowling. Convergence and noregret in multiagent learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), pages 209 216, Vancouver, Canada, 2005.

[Bowman et al., 2014] Clark Bowman, Jonathan K Hodge, and Ada Yu. The potential of iterative voting to solve the separability problem in referendum elections. Theory and Decision, 77(1):111 124, 2014.

[Brˆanzei et al., 2013] Simina Brˆanzei, Ioannis Caragiannis, Jamie Morgenstern, and Ariel D. Procaccia. How bad is selfish voting? In Proceedings of the 27th AAAI Conference on Artificial Intelligence, pages 138 144, 2013.

[Chopra et al., 2004] Samir Chopra, Eric Pacuit, and Rohit Parikh. Knowledge-theoretic properties of strategic voting. In European Workshop on Logics in Artificial Intelligence, pages 18 30. Springer, 2004.

[Conitzer et al., 2009] Vincent Conitzer, J erˆome Lang, and Lirong Xia. How hard is it to control sequential elections via the agenda? In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI), pages 103 108, Pasadena, CA, USA, 2009.

[Conitzer et al., 2011] Vincent Conitzer, Toby Walsh, and Lirong Xia. Dominating manipulations in voting with partial information. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 638 643, San Francisco, CA, USA, 2011.

[Desmedt and Elkind, 2010] Yvo Desmedt and Edith Elkind. Equilibria of plurality voting with abstentions. In Proceedings of the 11th ACM conference on Electronic Commerce, pages 347 356, 2010.

[Elkind et al., 2020] Edith Elkind, Umberto Grandi, Francesca Rossi, and Arkadii Slinko. Cognitive hierarchy and voting manipulation in k-approval voting. Mathematical Social Sciences, 108:193 205, 2020.

[Endriss et al., 2016] Ulle Endriss, Svetlana Obraztsova, Maria Polukarov, and Jeffrey S. Rosenschein. Strategic voting with incomplete information. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 16, page 236 242. AAAI Press, 2016.

[Fudenberg and Levine, 2009] Drew Fudenberg and David K Levine. Learning and equilibrium. Annu. Rev. Econ., 1(1):385 420, 2009. [Grandi et al., 2013] Umberto Grandi, Andrea Loreggia, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Restricted manipulation in iterative voting: Condorcet efficiency and Borda score. In International Conference on Algorithmic Decision Theory, pages 181 192. Springer, 2013. [Grandi et al., 2019] Umberto Grandi, Daniel Hughes, Francesca Rossi, and Arkadii Slinko. Gibbard Satterthwaite games for k-approval voting rules. Mathematical Social Sciences, 99:24 35, 2019. [Grandi et al., 2022] Umberto Grandi, J erˆome Lang, Ali I Ozkes, and St ephane Airiau. Voting behavior in one-shot and iterative multiple referenda. Social Choice and Welfare, pages 1 35, 2022. [Hodge, 2002] Jonathan K Hodge. Separable preference orders. Ph D thesis, Western Michigan University, 2002. [Kavner and Xia, 2021] Joshua Kavner and Lirong Xia. Strategic behavior is bliss: iterative voting improves social welfare. Advances in Neural Information Processing Systems, 34:19021 19032, 2021. [Koolyk et al., 2017] Aaron Koolyk, Tyrone Strangway, Omer Lev, and Jeffrey S. Rosenschein. Convergence and quality of iterative voting under non-scoring rules. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 273 279, 2017. [Kukushkin, 2011] Nikolai S Kukushkin. Acyclicity of improvements in finite game forms. International Journal of Game Theory, 40(1):147 177, 2011. [Lacy and Niou, 2000] D. Lacy and E. Niou. A problem with referenda. Journal of Theoretical Politics, 12(1):5 31, 2000. [Lang and Xia, 2009] J erˆome Lang and Lirong Xia. Sequential composition of voting rules in multi-issue domains. Mathematical Social Sciences, 57(3):304 324, 2009. [Lang and Xia, 2016] J erˆome Lang and Lirong Xia. Voting in Combinatorial Domains. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel Procaccia, editors, Handbook of Computational Social Choice, chapter 9. Cambridge University Press, 2016. [Lang, 2007] J erˆome Lang. Vote and aggregation in combinatorial domains with structured preferences. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI), pages 1366 1371, Hyderabad, India, 2007. [Lev and Rosenschein, 2012] Omer Lev and Jeffrey S Rosenschein. Convergence of iterative voting. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pages 611 618, 2012. [Marden et al., 2007] Jason R. Marden, G urdal Arslan, and Jeff S. Shamma. Regret based dynamics: Convergence in

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

weakly acyclic games. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 07, New York, NY, USA, 2007. Association for Computing Machinery.

[Meir et al., 2010] Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R. Jennings. Convergence to Equilibria of Plurality Voting. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 823 828, Atlanta, GA, USA, 2010.

[Meir et al., 2014] Reshef Meir, Omer Lev, and Jeffrey S. Rosenschein. A Local-Dominance Theory of Voting Equilibria. In Proceedings of the 15th ACM Conference on Electronic Commerce, pages 313 330, Palo Alto, CA, USA, 2014.

[Meir et al., 2017] Reshef Meir, Maria Polukarov, Jeffrey S Rosenschein, and Nicholas R Jennings. Iterative voting and acyclic games. Artificial Intelligence, 252:100 122, 2017.

[Meir et al., 2020] Reshef Meir, Kobi Gal, and Maor Tal. Strategic voting in the lab: compromise and leader bias behavior. Autonomous Agents and Multi-Agent Systems, 34(1):1 37, 2020.

[Meir, 2015] Reshef Meir. Plurality Voting under Uncertainty. In Proceedings of the 29th AAAI on Artificial Intelligence, 2015.

[Meir, 2018] Reshef Meir. Strategic Voting. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool, 2018.

[Milchtaich, 1996] Igal Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111 124, 1996.

[Monderer and Shapley, 1996] Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124 143, 1996.

[Myerson and Weber, 1993] Roger B Myerson and Robert J Weber. A theory of voting equilibria. American Political Science Review, 87(1):102 114, 1993.

[Obraztsova et al., 2015] Svetlana Obraztsova, Evangelos Markakis, Maria Polukarov, Zinovi Rabinovich, and Nicholas R. Jennings. On the convergence of iterative voting: How restrictive should restricted dynamics be? In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI 15, page 993 999, 2015.

[Rabinovich et al., 2015] Zinovi Rabinovich, Svetlana Obraztsova, Omer Lev, Evangelos Markakis, and Jeffrey Rosenschein. Analysis of equilibria in iterative voting schemes. In Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 2015.

[Reijngoud and Endriss, 2012] Annemieke Reijngoud and Ulle Endriss. Voter response to iterated poll information. In Proceedings of the Eleventh International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), volume 1, pages 635 644, 06 2012.

[Reyhani and Wilson, 2012] Reyhaneh Reyhani and Mark C. Wilson. Best reply dynamics for scoring rules. In Proceedings of the 20th European Conference on Artificial Intelligence, ECAI 12, page 672 677, NLD, 2012. IOS Press. [Sen, 1999] Amartya Sen. The Possibility of Social Choice. American Economic Review, 89(3):349 378, 1999. [Tsetlin et al., 2003] Ilia Tsetlin, Michel Regenwetter, and Bernard Grofman. The impartial culture maximizes the probability of majority cycles. Social Choice and Welfare, 21(3):387 398, 2003. [Van Ditmarsch et al., 2013] Hans Van Ditmarsch, J erˆome Lang, and Abdallah Saffidine. Strategic voting and the logic of knowledge. ar Xiv preprint ar Xiv:1310.6436, 2013. [Xia and Conitzer, 2010] Lirong Xia and Vincent Conitzer. Stackelberg voting games: Computational aspects and paradoxes. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 921 926, Atlanta, GA, USA, 2010. [Xia et al., 2011] Lirong Xia, Vincent Conitzer, and J erˆome Lang. Strategic sequential voting in multi-issue domains and multiple-election paradoxes. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 179 188, San Jose, CA, USA, 2011. [Xia, 2020] Lirong Xia. The smoothed possibility of social choice. Advances in Neural Information Processing Systems, 33:11044 11055, 2020. [Young, 1993] H Peyton Young. The Evolution of Conventions. Econometrica, 61(1):57 84, January 1993. [Zou et al., 2015] James Zou, Reshef Meir, and David Parkes. Strategic voting behavior in doodle polls. In Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing, CSCW 15, page 464 472, New York, NY, USA, 2015.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)