Convergence in Multi-Issue Iterative Voting under Uncertainty

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

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

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.

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 reducingmultiple election paradoxes. Increasing uncertainty yields faster convergence but degrades this welfare improvement.

1.2 RelatedWork

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 GibbardSatterthwaite 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 = ×pi=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 ∏pi=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 = (a1j , . . . , apj ) ∈ 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 : aij = c}|. We use the plurality rule f(a) = (f i (a))i∈P ∈ D, where f i (a) = argmaxc∈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 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 convergence 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) : ˜aij ∈ Di, ˜akj = akj ∀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 ⊆ ×pi=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 LDij 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 LDij = ∅ and ˆaj ∈ LDij 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.

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; rij ) := {vi : δ(vi , si-j ) ≤ rij } with an uncertainty parameter rij . That is, given other votes ai-j , agent j is not sure what the real score vector is within ˜ Si-j (s; rij ). We define ˜ S-j(s, rj) := ×pi=1 ˜ Si-j (s; rij ) for rj = (rij )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

which is a bandwidth of rij = 1 around each real score si-j . Finally, consider the prospective vote ˆaj = (1, 1). Then

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 ˆaij over aij 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.

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 rij , it is pivotal with respect to all larger parameters ˜ rj : ˜ rij > rij 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 rij < βi j . Let LDij (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 uncertainty parameters - αj, rj, or βj - as defined above. Then LDij (αj ) ⊆ LDij (rj ) ⊆ LDij (β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 LDij 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. ˆaij = c, ˆakj = akj ∀k ̸= i, s.t. f i (v + ˆaj) = c}. The set of real potential winners is denoted: Hi0 (a) = {c ∈ Di : f i (s-j + ˆaj) = c where ˆaij = c, ˆakj = akj ∀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) aij /∈ Hi j (a); or for every combination of possible winners in W-i (a; rj), either (2) aij ≺j b for all b ∈ Hi j (a) or (3) rij = 0, {aij , ˆaij } ⊆ Hi0 (a) and ˆaij ≻j aij .

The proof of this lemma directly follows that of Lemma 3 in Meir [2015]; see Appendix A for the full proof.

2 Without uncertainty, Hi j (a) (or Hi j (a)∪{aij} if adding a vote to aij 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(tT )}, where a(tT + 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, tT ) 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∗ , tT ] be the last round that j switches their vote on i back to aij . It must be the case that aij ∈ 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, ˆaij ≻j aij for every combination of possible winners in W-i (a(t∗ ); rj). Likewise, on round t∗∗ , aij ≻j ˆaij 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.

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(tT )}, where a(tT + 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 rou . Let t∗ ∈ [t1, tT ) 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∗ , tT ] be the last round that j switches their vote on i back to aij . It must be the case that aij ∈ 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, ˆaij ≻j aij for every combination of possible winners in W-i (a(t∗ ); rj ). Likewise, on round t∗∗ , aij ≻j ˆaij 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, rch ≥ ro j . This entails roh > ro j by definition of alternating uncertainty, which contradicts the assertion that j is the agent u with the largest rou .

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 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 IVmay 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 individual 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.

3 Measured 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 4: Average percent change in Borda welfare as n increases; 95%CI (too small to show).

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

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