Convergence of Multi-Issue Iterative Voting under Uncertainty

Joshua Kavner Reshef Meir Rensselaer Polytechnic Institute
{[email protected],[email protected]} Francesca Rossi Technion Israel Institute of Technology
[email protected] Lirong Xia

Abstract

We study the effect of strategic behavior in iterative voting for multiple issues under uncertainty. We introduce a model synthesizing simultaneous multi-issue voting with Meir et al. (2014)’s local dominance theory 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 $\mathcal{O}$ -legal preferences and endowing agents with less uncertainty about issues they are modifying than others. Our empirical studies demonstrate that although cycles are common when agents have no 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. Suppose they have three issues: the main course (chicken, beef, or salmon), the paired wine (red or white), and the dessert cake’s flavor (chocolate or vanilla). How should the planner proceed? On the one hand, the planner could request each attendee’s (agent’s) full preference ranking over the $d^{p}$ possibilities (alternatives), for $p$ issues with $d$ candidates each. However, this is computationally prohibitive and imposes a high cognitive cost for agents.

On the other hand, the planner could only request agents’ most preferred alternatives 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 three binary issues and all prefer $(1,1,1)$ last Lacy and Niou (2000). Then the agents select $(1,1,1$ ) by majority rule on each issue independently.

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 Lang and Xia (2009); Xia et al. (2011). 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. For example, agents may be fully aware of each other’s votes, such as in online Doodle polls Zou et al. (2015), and update to the myopic best response of all others. Alternatively, agents may only have partial information, such as from imprecise opinion polls Reijngoud and Endriss (2012) or latency if they can only periodically retrieve vote counts on a networked system. We then take a strict uncertainty approach in which agents assume that any vote profile in a set is possible without assigning probabilities to them. Agents update to votes that locally dominate their prior reports 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?

The conclusion from previous research regarding convergence in single-issue IV is mixed, as the plurality and veto voting rules have strong guarantees, yet many other rules admit cycles Meir et al. (2017). This leaves us with mixed hope that multi-issue IV can converge, and if so, that it can solve other problems like multiple election paradoxes Xia et al. (2011). Furthermore, in contrast to the single-issue setting Meir (2015), uncertainty for multiple issues plays a double role. First, like the single-issue 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 regarding their own preferences on a particular issue, as this may depend on the outcomes of other uncertain issues.

1.1 Our Contribution

On the conceptual side, we introduce a model that synthesizes prior work in local dominance strategic behavior, iterative 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 for either best response, without uncertainty, or local dominance improvement dynamics, with uncertainty, may not converge. We then present two model refinements that prove sufficient to guarantee convergence for binary issues: restricting agent preferences to be $\mathcal{O}$ -legal converges because agents’ preferences on issues are not interdependent; alternating uncertainty, in which agents are more certain about the current issue than others, converges because fewer preference rankings yield improvement steps in this case. These convergence results do not extend to the multi-candidate issues setting, as LDI plurality dynamics may cycle if agents have partial order preference information.

Our convergence results for binary issues also hold for a nonatomic variant of IV, in which agents are part of a very large population and arbitrary subsets of agents may change their vote simultaneously, establishing more general convergence results (see 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. Multi-issue 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), 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), Meir (2015). Their research finds broad conditions for voting equilibrium to exist and guaranteed convergence for iterative plurality. In particular, Meir (2015) studies 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. (2020) empirically show 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.

A related line of research studies 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), Van Ditmarsch et al. (2013) each study 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), Elkind et al. (2020). Other forms of IV include work from Airiau and Endriss (2009), Desmedt and Elkind (2010), Xia and Conitzer (2010).

2 Preliminaries

Basic model.

Let $\mathcal{P}=\{1,2,\ldots,p\}$ be the set of $p$ issues over the joint domain $\mathcal{D}=\times_{i=1}^{p}D_{i}$ , where $D_{i}$ is the finite value domain of candidates for issue $i$ . We call the issues binary if $D_{i}=\{0,1\}$ for each $i\in\mathcal{P}$ or multi-candidate otherwise. Each of $n$ agents is endowed with a preference ranking $R_{j}\in\mathcal{L}(\mathcal{D})$ , the set of strict linear orders over the $\times_{i=1}^{p}|D_{i}|$ alternatives. We call the collection of agents’ preferences $P=(R_{1},\ldots,R_{n})$ a preference profile and each agent’s most preferred alternative their truthful vote. A vote profile $a=(a_{1},\ldots,a_{n})\in\mathcal{D}^{n}$ is a collection of votes, where $a_{j}=(a^{1}_{j},\ldots,a^{p}_{j})\in\mathcal{D}$ collects agent $j$ ’s single-candidate vote per issue. A resolute voting rule $f:\mathcal{D}^{n}\rightarrow\mathcal{D}$ maps vote profiles to a unique outcome. We call $a\in\mathcal{D}$ and $a^{i}\in D_{i}$ for $i\in\mathcal{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 $\mathcal{O}=\{o_{1},\ldots,o_{p}\}$ if outcomes of each issue $o_{i}$ are revealed to agents prior to voting on the next issue $o_{i+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 thus take the score of a candidate $c\in D_{i}$ as $s^{i}(c;a)=|\{j\leq n~{}:~{}a^{i}_{j}=c\}|$ and define the score tuple $s(a)=(s^{i}(a))_{i\in\mathcal{P}}$ as a collection of score vectors $s^{i}(a)=(s^{i}(c;a))_{c\in D_{i}}$ . We use the plurality rule $f(a)=(f^{i}(a))_{i\in\mathcal{P}}\in\mathcal{D}$ , where $f^{i}(a)=\operatorname*{arg\,max}_{c\in D_{i}}s^{i}(c;a)$ , breaking ties lexicographically on each issue. We often use $s$ , $s(a)$ , and $a$ interchangeably for ease of notation.

Let $a_{-j}$ denote the vote profile without agent $j$ and $(a_{-j},\hat{a}_{j})$ the profile $a$ by replacing $j$ ’s vote with the prospective vote $\hat{a}_{j}$ . Then $s_{-j}$ and $s_{-j}+\hat{a}_{j}$ denote the corresponding adjusted score tuples.

Preferential dependence.

A preference ranking is called separable if its relative ordering of candidates in $D_{i}$ , for each issue $i\in\mathcal{P}$ , are consistent across all outcomes of the other issues. This has the advantage that such agents may express their preferences for any issue without knowing other issues’ outcomes and avoid multiple-election paradoxes (see e.g., Xia et al. (2011)), but it is a very demanding assumption Hodge (2002). Relaxing agents preferences to be $\mathcal{O}$ -legal maintains representation compactness without permitting arbitrary preferential dependencies Lang and Xia (2009).

Formally, for some order $\mathcal{O}=\{o_{1},\ldots,o_{p}\}$ over the issues, the preference ranking $R$ is called $\mathcal{O}$ -legal if, given the outcomes of the prior issues $\{f^{o_{1}},f^{o_{2}},\ldots,f^{o_{i-1}}\}$ , the relative ordering of candidates in $D_{o_{i}}$ is constant for any combination of outcomes of the later issues $\{f^{o_{i+1}},\ldots,f^{o_{p}}\}$ . Hence, the ranking of candidates $D_{o_{i}}$ in $R$ depends only, if at all, on the outcomes of issues prior to it in $\mathcal{O}$ .

The preference profile $P$ is called $\mathcal{O}$ -legal if every ranking is $\mathcal{O}$ -legal for the same order $\mathcal{O}$ . Thus, the ranking $R$ is separable if it is $\mathcal{O}$ -legal for any order $\mathcal{O}$ .

Example 1.

Let there be $p=2$ binary issues and $n=3$ agents with preferences $P=(R_{1},R_{2},R_{3})$ such that:

$R_{1}:(1,0)\succ_{1}(0,0)\succ_{1}(0,1)\succ_{1}(1,1)$ ,

$R_{2}:(1,1)\succ_{2}(0,0)\succ_{2}(0,1)\succ_{2}(1,0)$ , and

$R_{3}:(0,0)\succ_{3}(0,1)\succ_{3}(1,0)\succ_{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 $R_{1}$ is $\mathcal{O}$ -legal for $\mathcal{O}=\{2,1\}$ : the agent always prefers $0\succ 1$ on the second issue, yet their preference for the first issue depends on $f^{2}$ . $R_{3}$ is separable, as the agent prefers $0\succ 1$ on each issue independent of the other issue’s outcome. $R_{2}$ is neither separable nor $\mathcal{O}$ -legal for any $\mathcal{O}$ .

Finally, agent $2$ can improve the outcome for themselves by voting for $\hat{a}_{2}=(0,1)$ instead of $a_{2}=(1,1)$ . The adjusted score tuple is $s_{-2}=\{(1,1),(2,0)\}$ , so $s_{-2}+\hat{a}_{2}=\{(2,1),(2,1)\}$ and $f(s_{-2}+\hat{a}_{2})=(0,0)\succ_{2}(1,0)=f(a)$ .

Improvement dynamics.

We implement the iterative voting (IV) model introduced by Meir et al. (2010) and refined for uncertainty by Meir et al. (2014), Meir (2015). Given agents’ truthful preferences $P$ and an initial vote profile $a(0)$ , we consider an iterative process of vote profiles $a(t)=(a_{1}(t),\ldots,a_{n}(t))$ that describe agents’ reported votes over time $t\geq 0$ . For each round $t$ , a scheduler $\phi$ chooses an agent $j$ to make an improvement step over their prior vote $a_{j}(t)$ by applying a specified response function $g_{j}:\mathcal{D}^{n}\rightarrow\mathcal{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., $g_{j}(a)=a_{j}~{}\forall j\leq 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)). This means that there are multiple levels in which a voting rule may guarantee convergence to an equilibrium Meir et al. (2017). 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\in\mathcal{P}$ per round, as determined by the scheduler $\phi$ . We therefore have the following form of convergence, as described by Kukushkin (2011), Monderer and Shapley (1996), 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$ , $g_{j}(a):=\hat{a}_{j}$ which yields agent $j$ ’s most preferred outcome of the set $\{f(a_{-j},\tilde{a}_{j}):\tilde{a}^{i}_{j}\in D_{i},\tilde{a}^{k}_{j}=a^{k}_{j}~{}\forall k\neq i\}$ , defaulting as $a_{j}$ if the best outcome is the same.

LDI dynamics are based on the notions of strict uncertainty and local dominance Conitzer et al. (2011); Reijngoud and Endriss (2012). Let $S\subseteq\times_{i=1}^{p}\mathbb{N}^{|D_{i}|}$ 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 $\hat{a}_{j}$ is (1) weakly better off than their original $a_{j}$ for every $v\in S$ , (2) strictly better off for some tuple in $v\in S$ , and (3) not worse off for any $v\in S$ . This is formally defined as follows.

Definition 3.

The vote $\hat{a}_{j}$ $S$ -beats $a_{j}$ if there is at least one score tuple $v\in S$ such that $f(v+\hat{a}_{j})\succ_{j}f(v+a_{j})$ . The vote $\hat{a}_{j}$ $S$ -dominates $a_{j}$ if both (I) $\hat{a}_{j}$ $S$ -beats $a_{j}$ ; and (II) $a_{j}$ does not $S$ -beat $\hat{a}_{j}$ .

Definition 4 (Local dominance improvement).

Given the vote profile $a$ and agent $j$ , let $LD^{i}_{j}$ be the set of votes that $S$ -dominate $a_{j}$ , only differ from $a_{j}$ on the $i^{th}$ issue, and are not themselves $S$ -dominated by votes differing from $a_{j}$ only on the $i^{th}$ issue. Then $g_{j}(a)=a_{j}$ if $LD^{i}_{j}=\emptyset$ and $\hat{a}_{j}\in LD^{i}_{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 constructed 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\in\mathcal{P}$ , let $\delta(s^{i}(a),\tilde{s}^{i}(a))$ be a distance measure for score vectors for any vote profile $a$ . This measure is candidate-wise if it can be written as $\delta(s^{i}(a),\tilde{s}^{i}(a))=\max_{c\in D_{i}}\hat{\delta}(s^{i}(c;a),\tilde{s}^{i}(c;a))$ for some monotone function $\hat{\delta}$ . For example, the multiplicative distance (where $\hat{\delta}(s,\tilde{s})=\max\{\tilde{s}/s,s/\tilde{s}\}-1$ ) and the $\ell_{\infty}$ metric (where $\hat{\delta}(s,\tilde{s})=|s-\tilde{s}|$ ) are candidate-wise.

Given the vote profile $a$ and issue $i\in\mathcal{P}$ , we model agent $j$ ’s uncertainty about the adjusted score vector $s^{i}_{-j}$ by the uncertainty score set $\tilde{S}^{i}_{-j}(s;r^{i}_{j}):=\left\{v^{i}:\delta(v^{i},s^{i}_{-j})\leq r^{i}_{j}\right\}$ with an uncertainty parameter $r^{i}_{j}$ . That is, given all other agents’ votes $a_{-j}^{i}$ , agent $j$ is not sure what the real score vector is $v^{i}\in\tilde{S}_{-j}^{i}(s;r^{i}_{j})$ . We take $\tilde{S}_{-j}(s,r_{j}):=\times_{i=1}^{p}\tilde{S}^{i}_{-j}(s;r^{i}_{j})$ for $r_{j}=(r_{j}^{i})_{i\in\mathcal{P}}$ , and drop the parameters if the context is clear.

Example 2.

Let there be $p=2$ binary issues and $n=13$ agents. Define the vote profile $a$ such that $s(a)=\{(8,5),(9,4)\}$ and $a_{j}=(0,1)$ for some agent $j$ . Suppose $j$ uses the $\ell_{\infty}$ uncertainty metric with $(r^{1}_{j},r^{2}_{j})=(1,1)$ . Then the uncertainty score set without $j$ ’s vote is:

$\tilde{S}_{-j}=\{(6,7,8)\times(4,5,6)\}\times\{(8,9,10)\times(2,3,4)\}$

Consider the prospective vote $\hat{a}_{j}=(1,1)$ . Then the set of possible outcomes is $\{f(v+\hat{a}_{j})~{}:~{}v\in\tilde{S}_{-j}\}=\{0,1\}\times\{0\}.$

Remark.

Notice that in any vote profile reachable via BR or LDI dynamics from the truthful vote profile, no agent with fully separable preferences will have an improvements step. This follows from the definitions of BR and LDI.

3 Best-Response Dynamics

Given the vote profile $a$ , consider agent $j$ changing their vote $a_{j}$ on issue $i$ to the prospective vote $\hat{a}_{j}$ . 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 $R_{j}$ . This happens under two conditions. First, $j$ must be pivotal on the $i^{th}$ issue, meaning that changing their vote will necessarily change the outcome. Second, $j$ must be preferential to change $i$ by voting for $\hat{a}^{i}_{j}$ over $a^{i}_{j}$ given the outcomes of the other issues $\mathcal{P}\backslash\{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:

$R_{1}:(0,1)\succ_{1}(1,1)\succ_{1}(1,0)\succ_{1}(0,0)$ ,

$R_{2}:(0,0)\succ_{2}(0,1)\succ_{2}(1,1)\succ_{2}(1,0)$ , and

$R_{3}:(1,0)\succ_{3}(1,1)\succ_{3}(0,0)\succ_{3}(0,1)$ .

Agent $j$	$a_{j}(0)$	$a_{j}(1)$	$a_{j}(2)$	$a_{j}(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)

Table 1 demonstrates a cycle generated by 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, demonstrating that no agent scheduler can lead to convergence. Notice that agent $3$ never changes their vote since their ranking is fully separable.

4 Local Dominance Improvement Dynamics

4.1 Non-Convergence

LDI dynamics broadens best-response, but it is initially unclear how increasing agents’ uncertainty parameters will affect their improvement steps and whether this eliminates the possibility of cycles. Under LDI dynamics, with uncertainty, agent $j$ changes their vote $a_{j}$ on issue $i$ to the prospective vote $\hat{a}_{j}$ from vote profile $a$ with two conditions similar to BR dynamics: if they (I) believe they may be pivotal and (II) can improve the outcome with respect to $R_{j}$ (corresponding to $S$ -dominance). First, intuitively, it would seem that uncertainty over $j$ ’s current issue $i$ affects whether they believe they can change $i$ ’s outcome. Notice that if issue $i$ has a unique winning candidate and no runner-up, then $j$ has no best-response but may have an LDI step only if their uncertainty parameter is large enough. Second, unlike BR dynamics and the single-issue setting Meir et al. (2014); Meir (2015), $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.

Despite these two apparent parallels, we observe for multi-candidate issues that the relationship between uncertainty parameter and existence of LDI steps is not monotonic. Example 5 in Appendix B demonstrates that different sets of prospective votes $LD^{i}_{j}$ in the same vote profile $a$ are non-comparable for the same agent with different uncertainty parameters. On the other hand, LDI dynamics have the aforementioned structure with binary issues, as we prove in Theorem 1. Still, this relationship has counter-acting forces: increasing uncertainty on issue $i$ may only add LDI steps over issue $i$ but may only eliminate steps on all other issues.

Theorem 1.

Given binary issues, consider agent $j$ changing their vote on issue $i$ in vote profile $a$ with one of three uncertainty parameters: $r_{j}$ , $q_{j}$ , or $\hat{q}_{j}$ . The parameters $r_{j}$ and $q_{j}$ only differ on issue $k\neq i$ such that $r_{j}^{k}<q_{j}^{k}$ ; $r_{j}$ and $\hat{q}_{j}$ only differ on issue $i$ such that $r_{j}^{i}<\hat{q}_{j}^{i}$ . Let $LD^{i}_{j}$ , $LQ^{i}_{j}$ , and $\hat{LQ}^{i}_{j}$ denote $j$ ’s possible LDI steps according to each of the parameters. Then $LQ_{j}^{i}\subseteq LD_{j}^{i}\subseteq\hat{LQ}^{i}_{j}$ .

We prove the theorem in two parts by demonstrating that if a vote $\hat{a}_{j}~{}\tilde{S}_{-j}(a;q_{j})$ -dominates $a_{j}$ , then it must $\hat{a}_{j}~{}\tilde{S}_{-j}(a;r_{j})$ -dominates $a_{j}$ ; likewise, this implies that $\hat{a}_{j}~{}\tilde{S}_{-j}(a;\hat{q}_{j})$ -dominates $a_{j}$ . Each of these relationships arise as a result of $\tilde{S}_{-j}(a;r_{j})\subseteq\tilde{S}_{-j}(a;q_{j})$ and $\tilde{S}_{-j}(a;r_{j})\subseteq\tilde{S}_{-j}(a;\hat{q}_{j})$ . For binary issues, this is sufficient and we do not need to show that $\hat{a}_{j}$ is not $\tilde{S}_{-j}(a;r_{j})$ - or $\tilde{S}_{-j}(a;\hat{q}_{j})$ -dominated. This may not be the case for multi-candidate issues, as previously stated in Example 5. The full proof may be found in Appendix A.

In sum, we find that enabling agents to have uncertainty over issues does not eliminate the possibility of a cycle, unlike the single-issue setting, as declared in the following proposition and proved with Example 6 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.

4.2 Strategic responses and $\mathcal{O}$ -legal preferences

We next present two model refinements that prove sufficient to guarantee convergence for binary issues: $\mathcal{O}$ -legal preferences and a specific form of dynamic uncertainty.

We are motivated by observing in Examples 3 and 6 that cycles appear due to agents’ interdependent preferences among the issues. For simplicity, consider two issues $i$ and $k$ in which no agent has an LDI step on issue $i$ . LDI steps on issue $k$ may change the set of possible winning candidates (see Definition 5), thus transforming agents’ preferences over the candidates in $i$ . This enables agents to have LDI steps over issue $i$ , even if they may no longer have improvement steps over $k$ . It stands to reason that eliminating interdependent preferences by restricting agents to have $\mathcal{O}$ -legal preference rankings would guarantee convergence.

We prove this is the case in Theorem 2. 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. Formally,

$W^{i}_{j}(a)=\{c\in D_{i}~{}:~{}\exists v\in\tilde{S}_{-j}(a;r_{j})~{}\text{s.t.}~{}f^{i}(v+a_{j})=c\}$ .

In contrast, $j$ calls $c$ a potential winner if there is some score vector in which they can vote to make $c$ win:

$H^{i}_{j}(a)=\{c\in D_{i}~{}:~{}\exists v\in\tilde{S}_{-j}(a;r_{j})~{}\text{and}~{}\hat{a}_{j}~{}\text{s.t.}~{}\hat{a}^{i}_{j}=c,\hat{a}^{k}_{j}=a^{k}_{j}~{}\forall k\neq i,~{}\text{s.t.}~{}f^{i}(v+\hat{a}_{j})=c\}$ .

The set of real potential winners is denoted: $H^{i}_{0}(a)=\{c\in D_{i}~{}:~{}f^{i}(s_{-j}+\hat{a}_{j})=c~{}\text{where}~{}\hat{a}^{i}_{j}=c,\hat{a}^{k}_{j}=a^{k}_{j}~{}\forall k\neq i\}$ .

By this definition, $W^{i}_{j}(a)\subseteq H^{i}_{j}(a)$ . ¹¹1 Without uncertainty, $H^{i}_{j}(a)$ (or $H^{i}_{j}(a)\cup\{a^{i}_{j}\}$ if adding a vote to $a^{i}_{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$ . $H^{i}_{j}(a)$ coincides with Meir et al. (2014) and Meir (2015)’s definition of a possible winner “ $W_{j}(s)$ .” Denote by $\mathcal{W}^{-i}(a;r_{j})=\times_{k\in\mathcal{P}\backslash\{i\}}W^{k}_{j}(a)$ the set of possible winning candidates on all issues besides $i$ , from agent $j$ ’s perspective with uncertainty parameter $r_{j}$ .

Lemma 1.

Consider an LDI step $a_{j}\xrightarrow{j}\hat{a}_{j}$ over issue $i$ from vote profile $a$ by agent $j$ with uncertainty parameter $r_{j}$ . Then either (1) $a^{i}_{j}\notin H^{i}_{j}(a)$ ; or for every combination of possible winners in $\mathcal{W}^{-i}(a;r_{j})$ , either (2) $a^{i}_{j}\prec_{j}b$ for all $b\in H^{i}_{j}(a)$ ; or (3) $r^{i}_{j}=0$ , $\{a^{i}_{j},\hat{a}^{i}_{j}\}\subseteq H_{0}(a)$ and $\hat{a}^{i}_{j}\succ_{j}a^{i}_{j}$ .

The proof of this lemma directly follows that of Lemma 3 in Meir (2015); see Appendix A.

Theorem 2.

Suppose all agents have $\mathcal{O}$ -legal preferences for the common order $\mathcal{O}$ over binary issues. Then LDI dynamics converge.

Proof.

Fix an initial vote profile $a(0)$ . Suppose for contradiction that there is a cycle among the vote profiles $\mathcal{C}=\{a(t_{1}),\ldots,a(t_{T})\}$ , where $a(t_{T}+1)=a(t_{1})$ and $a(t_{1})$ is reachable from $a(0)$ via LDI dynamics. Let $i$ be the highest order issue in $\mathcal{O}$ for which any agent changes their vote in $\mathcal{C}$ .

Let $t^{*}\in[t_{1},t_{T})$ be the first round that some agent $j$ takes an LDI step on issue $i$ , where $a_{j}\xrightarrow{j}\hat{a}_{j}$ from vote profile $a(t^{*})$ ; let $t^{**}\in(t^{*},t_{T}]$ be the last round that $j$ switches their vote on $i$ back to $a^{i}_{j}$ . It must be the case that $a^{i}_{j}\in H^{i}_{j}(a(t^{*}))$ , since issues are binary and otherwise, $|H^{i}_{j}(a(t^{*}))|=1$ and $j$ would not have an improvement step. Hence by Lemma 1, $\hat{a}^{i}_{j}\succ_{j}a^{i}_{j}$ for every combination of possible winners in $\mathcal{W}^{-i}(a(t^{*});r_{j})$ . Likewise, on round $t^{**}$ , $a^{i}_{j}\succ_{j}\hat{a}^{i}_{j}$ for every combination of possible winners in $\mathcal{W}^{-i}(a(t^{**});r_{j})$ . Thus for some issue $k$ and outcomes $x,y\in\{0,1\}$ , $x\neq y$ , we have $W^{k}_{j}(a(t^{*}))=\{x\}$ and $W^{k}_{j}(a(t^{**}))=\{y\}$ .

Since $j$ has $\mathcal{O}$ -legal preferences, $k$ must be prior to issue $i$ in the order $\mathcal{O}$ . However, no agent changed their vote on issue $k$ between rounds $t^{*}$ and $t^{**}$ so it must be that $x\in 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 2 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 $\mathcal{O}$ . Agents’ relative preferences for the candidates in $i$ are fixed because their preferences are $\mathcal{O}$ -legal: score vectors for issues prior to $i$ in $\mathcal{O}$ do not change 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 $\mathcal{O}$ -legality is not necessary for convergence, as BR dynamics induced from the truthful vote profile in Example 1 converge. Although $\mathcal{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 $\mathcal{O}$ -legal ranking but orders differ between agents.

Furthermore, the theorem describes that LDI steps over the issue $i$ eventually terminate, thus enabling each subsequent issue in $\mathcal{O}$ to converge. This seems to suggest that IV under $\mathcal{O}$ -legal preferences is the same as truthful sequential voting, where agents vote for their preferred alternative on each issue $o_{i}$ given the known previous outcomes of $\{o_{1},\ldots,o_{i-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 with a single possible winning candidate that differs from the truthful sequential outcome; then no agent has an improvement step on that issue. Second, based on the scheduler, there may be a round with multiple possible winning candidates but no subsequent improvement steps on an issue. This may terminate IV with outcomes different than the truthful sequential vote.

This convergence result does not extend to the multi-candidate case, as declared in the following proposition and proved with the subsequent example.

Proposition 3.

LDI dynamics may not converge for multiple issues, even if agents have the same constant uncertainty parameters and $\mathcal{O}$ -legal preferences for the common order $\mathcal{O}$ .

Example 4.

Let there be $p=2$ issues and $n=15$ agents who each use the $\ell_{\infty}$ uncertainty metric with common fixed uncertainty parameters $(r^{1}_{j},r^{2}_{j})=(2,1)~{}\forall j\leq n$ . Label the candidates $\{0,1\}$ and $\{a,b,c,d\}$ respectively. Agent $j$ has preferences: if $f^{1}=0$ then $b\succ_{j}c\succ_{j}a\succ_{j}d$ on the second issue; otherwise $c\succ_{j}b\succ_{j}a\succ_{j}d$ . Agent $k$ always prefers $a\succ_{k}d\succ_{k}b\succ_{k}c$ on the second issue. These preferences are $\mathcal{O}$ -legal for $\mathcal{O}=\{1,2\}$ .

Define $a(0)$ so $s(a(0))=\{(7,8),(3,5,5,2)\}$ and $a_{j}(0)=a_{k}(0)=(0,a)$ . There are four LDI steps involved in this cycle: (i) $(0,a)\xrightarrow{j}(0,d)$ , (ii) $(0,a)\xrightarrow{k}(0,d)$ , (iii) $(0,d)\xrightarrow{j}(0,a)$ , and (iv) $(0,d)\xrightarrow{k}(0,a)$ . We prove these steps are valid in Appendix B.

Note that $H^{2}_{j}(a(0))=\{a,b,c\}$ and $H^{2}_{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 Theorem 1 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 $r^{c}_{j}$ , $r^{o}_{j}$ for each agent $j$ such that $r^{c}_{j}<r^{o}_{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 $r^{c}_{j}$ and for each other issue $k\neq i$ is $r^{o}_{j}$ .

Theorem 3.

Given binary issues, LDI dynamics converges for agents with alternating uncertainty.

Proof.

Fix an initial vote profile $a(0)$ and uncertainty parameters $r^{c}_{j},r^{o}_{j}$ for each agent $j\leq n$ . Suppose for contradiction that there is a cycle among the vote profiles $\mathcal{C}=\{a(t_{1}),\ldots,a(t_{T})\}$ , where $a(t_{T}+1)=a(t_{1})$ and $a(t_{1})$ 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 $r^{o}_{j}=\max_{u\leq n}r^{o}_{u}$ . Let $t^{*}\in[t_{1},t_{T})$ be the first round that $j$ takes an LDI step on issue $i$ , where $a_{j}\xrightarrow{j}\hat{a}_{j}$ from vote profile $a(t^{*})$ ; let $t^{**}\in(t^{*},t_{T}]$ be the last round that $j$ switches their vote on $i$ back to $a^{i}_{j}$ . It must be the case that $a^{i}_{j}\in H^{i}_{j}(a(t^{*}))$ , since issues are binary and otherwise, $|H^{i}_{j}(a(t^{*}))|=1$ and $j$ would not have an improvement step. Hence by Lemma 1, $\hat{a}^{i}_{j}\succ_{j}a^{i}_{j}$ for every combination of possible winners in $\mathcal{W}^{-i}(a(t^{*});r_{j})$ . Likewise, on round $t^{**}$ , $a^{i}_{j}\succ_{j}\hat{a}^{i}_{j}$ for every combination of possible winners in $\mathcal{W}^{-i}(a(t^{**});r_{j})$ . Thus for some issue $k$ and outcomes $x,y\in\{0,1\}$ , $x\neq y$ , we have $W^{k}_{j}(a(t^{*}))=\{x\}$ and $W^{k}_{j}(a(t^{**}))=\{y\}$ .

Let $t^{\prime}\in(t^{*},t^{**})$ be the first round since $t^{*}$ that some agent $h$ changes their vote on issue $k$ . Then $H^{k}_{h}(a(t^{\prime}))=\{0,1\}$ . Since $W^{k}_{j}(a(t^{\prime}))=W^{k}_{j}(a(t^{*}))=\{x\}\subsetneq\{0,1\}$ and distance functions are candidate-wise, $r^{c}_{h}\geq r^{o}_{j}$ . This entails $r^{o}_{h}>r^{o}_{j}$ by definition of alternating uncertainty, which contradicts the assertion that $j$ is the agent $u$ with the largest $r^{o}_{u}$ .

∎

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

5 Experiments

Refer to caption — Figure 1: Percentage of non-equilibrium profiles as $n$
increases.

Our computational experiments investigate the effects of uncertainty, number of issues, and number of agents on LDI dynamics. Specifically, we ask how often truthful vote profiles are themselves in equilibrium, how often LDI dynamics does not converge, and the path length to equilibrium when it converges. Our inquiry focuses on whether cycles are commonplace in practice even as convergence is not guaranteed.

We answer these questions for a broad cross-section of inputs, with $n\in\{7,11,15,19\}$ agents, $p\in\{2,3,4,5\}$ binary issues, and $r\in\{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 from 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 4 – 4 with respect to $n$ and $r$ for $p=5$ . We find that as uncertainty is introduced and $r$ increases, the availability of LDI steps diminishes significantly (Figure 4) to the point of eliminating (almost) all cycles and shortening the path length to convergence (Figure 4). Figure 4 presents the number of profiles whose LDI sequence cycles for no uncertainty, while only $5$ of our sampled $r\geq 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.²²2Measured by the percent change in Borda welfare. The Borda utility of outcome $a$ for ranking $R$ is $2^{p}$ minus the index of $a$ ’s position in $R$ ; the Borda welfare is the sum of utilities across agents. 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), Grandi et al. (2020), suggesting that IV may reduce multiple-election 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), Koolyk et al. (2017).

6 Discussion and Open Questions

We have introduced a novel model of strategic behavior in 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 when their preference for $i$ changes. This occurs when the set of possible winning candidates of other issues, that affect $j$ ’s preference for $i$ , have changed.

Without this interdependence, agents’ preference over issues change a finite number of times, so LDI dynamics converge (Theorem 2). As uncertainty increases over issues other than the one agents are changing, fewer preference rankings admit LDI steps which eliminates cycles (Theorem 3). Convergence does not extend to multi-candidate issues, as LDI plurality 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 their truthful vote outcome.

There are several open directions for future work. First, our empirical study was limited by assuming agents’ preferences were sampled from the impartial culture preference distribution and had 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 dynamic price of anarchy work of Brânzei et al. (2013), Kavner and Xia (2021) and smoothed analysis techniques of Xia (2020).

Second, IV is useful, in part, for protecting agents’ privacy, as they do not explicitly reveal their truthful preferences. However, agents that make improvement steps implicitly reveal partial preference information. Studying IV when agents account for others’ preferences based on current information is an interesting open direction. A third direction is to detail the properties, such as anonymity and Condorcet-consistency, of multi-issue IV rules that may be inherited by the decision rule used locally on each issue, as studied for sequential voting rules by Xia et al. (2011).

References

Airiau and Endriss [2009] Stéphane 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 no-regret 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ânzei et al. [2013] Simina Brânzei, 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érôme 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. [2020] Umberto Grandi, Jérôme Lang, Ali Ozkes, and Stéphane Airiau. Voting behavior in one-shot and iterative multiple referenda. Available at SSRN, 2020.
Hodge [2002] Jonathan K Hodge. Separable preference orders. Western Michigan University, 2002.
Kavner and Xia [2021] Joshua Kavner and Lirong Xia. Strategic behavior is bliss: Iterative voting improves social welfare. In Proceedings of NeurIPS, 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 [2007] Jérôme 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.
Lang and Xia [2009] Jérôme 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érôme Lang and Lirong Xia. Voting in Combinatorial Domains. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel Procaccia, editors, Handbook of Computational Social Choice, chapter 9. Cambridge University Press, 2016.
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ürdal Arslan, and Jeff S. Shamma. Regret based dynamics: Convergence in 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. ISBN 9788190426275. doi: 10.1145/1329125.1329175. URL https://doi.org/10.1145/1329125.1329175.
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.
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.
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érôme Lang, and Abdallah Saffidine. Strategic voting and the logic of knowledge. arXiv preprint arXiv:1310.6436, 2013.
Xia [2020] Lirong Xia. The Smoothed Possibility of Social Choice. In Proceedings of NeurIPS, 2020.
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érôme 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.
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.

Appendix

Appendix A Deferred Proofs

Theorem 1.

Proof.

We prove the theorem by proving a weaker claim that holds for the more general multi-candidate issues setting. Specifically, let $D^{i}_{j}$ , $Q^{i}_{j}$ , and $\hat{Q}^{i}_{j}$ denote the set of votes that $S$ -dominate $a_{j}$ and only differ on the $i^{th}$ issue, corresponding to $S=\tilde{S}_{-j}(a;r_{j})$ , $S=\tilde{S}_{-j}(a;q_{j})$ , or $S=\tilde{S}_{-j}(a;\hat{q}_{j})$ respectively. We show that $Q^{i}_{j}\subseteq D^{i}_{j}\subseteq\hat{Q}^{i}_{j}$ . The theorem follows because $LD^{i}_{j}=D^{i}_{j}$ (respectively, $LQ^{i}_{j}=Q^{i}_{j}$ and $\hat{LQ}^{i}_{j}=\hat{Q}^{i}_{j}$ ) for binary issues.

(Part 1: $Q^{i}_{j}\subseteq D^{i}_{j}$ .) Without loss of generality let $D^{i}_{j}\neq\emptyset$ . Suppose $\hat{a}_{j}\in Q^{i}_{j}$ . Then $\hat{a}_{j}$ $\tilde{S}_{-j}(a;q_{j})$ -dominates $a_{j}$ , entailing:

1.

$\exists\tilde{s}\in\tilde{S}_{-j}(a;q_{j})$ such that $f(\tilde{s}+\hat{a}_{j})\succ_{j}f(\tilde{s}+a_{j})$ , and
2.

$\nexists\tilde{s}^{\prime}\in\tilde{S}_{-j}(a;q_{j})$ such that $f(\tilde{s}^{\prime}+\hat{a}_{j})\prec_{j}f(\tilde{s}^{\prime}+a_{j})$ .

First, by construction of the uncertainty sets, $\tilde{S}^{k}_{-j}(a;r_{j})\subseteq\tilde{S}^{k}_{-j}(a;q_{j})$ and $\tilde{S}^{h}_{-j}(a;r_{j})=\tilde{S}^{h}_{-j}(a;q_{j})$ for all $h\neq k$ ; therefore $\tilde{S}_{-j}(a;r_{j})\subseteq\tilde{S}_{-j}(a;q_{j})$ . It follows that $\nexists\tilde{s}^{\prime}\in\tilde{S}_{-j}(a;r_{j})$ such that $f(\tilde{s}^{\prime}+\hat{a}_{j})\prec_{j}f(\tilde{s}^{\prime}+a_{j})$ by point (2) above. Hence, $a_{j}$ does not $\tilde{S}_{-j}(a;r_{j})$ -beat $\hat{a}_{j}$ .

Second, define a score tuple $\tilde{v}$ such that $\tilde{v}^{h}=\tilde{s}^{h}$ for each $h\neq k$ and $\tilde{v}^{k}\in\tilde{S}^{k}(a;r_{j})$ arbitrarily. It is the case that $\tilde{v}\in\tilde{S}(a;r_{j})$ since $\tilde{S}^{h}_{-j}(a;r_{j})=\tilde{S}^{h}_{-j}(a;q_{j})$ for all $h\neq k$ . Since $f^{i}(\tilde{s}+\hat{a}_{j})\neq f^{i}(\tilde{s}+a_{j})$ and $f^{h}(\tilde{s}+\hat{a}_{j})=f^{h}(\tilde{s}+a_{j})$ for all $h\neq i$ , we have $f(\tilde{v}+\hat{a}_{j})\neq f(\tilde{v}+a_{j})$ . It follows from the above argument that $f(\tilde{v}+\hat{a}_{j})\succ_{j}f(\tilde{v}+a_{j})$ . Therefore $a_{j}~{}\tilde{S}_{-j}(a;r_{j})$ -beats $\hat{a}_{j}$ and $\hat{a}_{j}\in D^{i}_{j}$ .

(Part 2: $D^{i}_{j}\subseteq\hat{Q}^{i}_{j}$ .) Without loss of generality let $\hat{Q}^{i}_{j}\neq\emptyset$ . Suppose $\hat{a}_{j}\in D^{i}_{j}$ . Then $\hat{a}_{j}$ $\tilde{S}_{-j}(a;r_{j})$ -dominates $a_{j}$ , entailing:

1.

$\exists\tilde{s}\in\tilde{S}_{-j}(a;r_{j})$ such that $f(\tilde{s}+\hat{a}_{j})\succ_{j}f(\tilde{s}+a_{j})$ , and
2.

$\nexists\tilde{s}^{\prime}\in\tilde{S}_{-j}(a;r_{j})$ such that $f(\tilde{s}^{\prime}+\hat{a}_{j})\prec_{j}f(\tilde{s}^{\prime}+a_{j})$ .

By construction of the uncertainty sets, $\tilde{S}^{i}_{-j}(a;r_{j})\subseteq\tilde{S}^{i}_{-j}(a;\hat{q}_{j})$ and $\tilde{S}^{h}_{-j}(a;r_{j})=\tilde{S}^{h}_{-j}(a;\hat{q}_{j})$ for all $h\neq i$ ; therefore $\tilde{S}_{-j}(a;r_{j})\subseteq\tilde{S}_{-j}(a;\hat{q}_{j})$ . It immediately follows that $\tilde{s}\in\tilde{S}_{-j}(a;\hat{q}_{j})$ , so $\hat{a}_{j}$ $\tilde{S}_{-j}(a;r_{j})$ -beats $a_{j}$ . Furthermore, $\nexists\tilde{s}^{\prime}\in\tilde{S}_{-j}(a;\hat{q}_{j})$ such that $f(\tilde{s}^{\prime}+\hat{a}_{j})\prec_{j}f(\tilde{s}^{\prime}+a_{j})$ by point (2) above. Hence, $a_{j}$ does not $\tilde{S}_{-j}(a;r_{j})$ -beat $\hat{a}_{j}$ . Therefore $\hat{a}_{j}\in\hat{Q}^{i}_{j}$ , concluding our proof.

∎

Lemma 1.

Proof.

The proof follows that of Lemma 3 in Meir [2015]. Suppose that $a^{i}_{j},b\in H^{i}_{j}(a)$ and $a^{i}_{j}\succ_{j}b$ whenever some combination of possible winners $(c^{1},c^{2},\ldots,c^{i-1},c^{i+1},\ldots,c^{p})\in\mathcal{W}^{-i}(a;r_{j})$ wins (i.e., (1) and (2) are violated). Assume first that $\hat{a}^{i}_{j}\notin H_{0}(a)$ . By Lemma 2 of Meir [2015], $\exists\tilde{s}\in\tilde{S}_{-j}(a;r_{j})$ such that:

•

$a^{i}_{j},b$ have maximal score (possibly with other candidates), strictly above $\hat{a}^{i}_{j}$ , in $\tilde{s}^{i}$ ;
•

for each $k\neq i$ , $\tilde{s}^{k}$ is such that $f^{k}(\tilde{s}+a_{j})=c^{k}$ wins.

W.l.o.g. assume $b$ is prior to $a^{i}_{j}$ in tie-breaking (otherwise adjust $\tilde{s}$ so that $f^{i}(\tilde{s})=b$ ). Thus $f^{i}(\tilde{s}+a_{j})=a^{i}_{j}$ while $f^{i}(\tilde{s}+\hat{a}_{j})=b$ . Since $a^{i}_{j}\succ_{j}b$ given $\tilde{s}$ , this implies $a_{j}~{}\tilde{S}_{-j}(a;r_{j})$ -beats $\hat{a}_{j}$ .

The remaining case is where $\hat{a}^{i}_{j}\in H_{0}(a)$ and $a^{i}_{j}\succ_{j}\hat{a}^{i}_{j}$ whenever some $(c^{1},c^{2},\ldots,c^{i-1},c^{i+1},\ldots,c^{p})\in\mathcal{W}^{-i}(a;r_{j})$ wins. Then in $\tilde{s}$ where $a^{i}_{j},\hat{a}^{i}_{j}$ are tied and $(c^{k})_{k\in\mathcal{P}\backslash\{i\}}$ wins, it is better for $j$ to vote for $a_{i}$ .

In both cases we get $\hat{a}_{j}\notin LD^{i}_{j}$ , which is a contradiction. ∎

Appendix B Supplementary Examples

Example 4.

(Cont’d.) Recall the agents $j$ and $k$ with the following preferences:

•

If $f^{1}=0$ then $j$ prefers $b\succ c\succ a\succ d$ on the second issue;
•

if $f^{1}=1$ then $j$ prefers $c\succ b\succ a\succ d$ on the second issue;
•

agent $k$ prefers $a\succ d\succ b\succ c$ on the second issue regardless of the first issue’s outcome.

Initialize the vote profile $a(0)$ such that $s(a(0))=\{(7,8),(3,5,5,2)\}$ and $a_{j}(0)=a_{k}(0)=(0,a)$ . There are four LDI steps involved in this cycle: (i) $(0,a)\xrightarrow{j}(0,d)$ , (ii) $(0,a)\xrightarrow{k}(0,d)$ , (iii) $(0,d)\xrightarrow{j}(0,a)$ , and (iv) $(0,d)\xrightarrow{k}(0,a)$ . We will prove that these are valid LDI steps in turn, demonstrating that (i) the new vote $S$ -beats the old vote, (ii) the old vote does not $S$ -beat the new vote, and (iii) the new vote is not $S$ -dominated. For any candidate $e\in\{a,b,c,d\}$ , denote the vote switching the second candidate to $e$ by $\hat{e}=(0,e)$ . Recall that ties are broken in lexicographical order.

(Step 1: $s^{2}(a(0))=(3,5,5,2)$ .) Since $r^{2}_{j}=1$ and $a^{2}_{j}=a$ , we have $H^{2}_{j}(a(0))=\{a,b,c\}$ .

(i) Let $\tilde{s}=\{(6,8),(3,4,4,2)\}\in\tilde{S}_{-j}(a(0);r_{j})$ . Then $f(\tilde{s}+\hat{d})=(1,b)\succ_{j}(1,a)=f(\tilde{s}+\hat{a})$ , so $\hat{d}~{}\tilde{S}_{-j}$ -beats $\hat{a}$ .

(ii) For any $\tilde{s}\in\tilde{S}_{-j}(a(0);r_{j})$ , we have that if $f^{2}(\tilde{s}+\hat{d})=a$ then $f^{2}(\tilde{s}+\hat{a})=a$ ; otherwise, if $f^{2}(\tilde{s}+\hat{a})\in\{b,c\}$ then $f^{2}(\tilde{s}+\hat{d})=f^{2}(\tilde{s}+\hat{a})$ . Hence, it is never preferable for $j$ to vote for $\hat{a}$ than $\hat{d}$ .

(iii) Neither $\hat{b}$ nor $\hat{c}$ $\tilde{S}_{-j}$ -dominate $\hat{d}$ since for $\tilde{s}^{\prime}=\{(6,8),(2,4,5,2)\}$ and $\tilde{s}^{\prime\prime}=\{(7,7),(2,4,4,2)\}$ it is preferable for $j$ to vote for $\hat{d}$ than $\hat{b}$ and $\hat{c}$ , respectively.

(Step 2: $s^{2}(a(1))=(2,5,5,3)$ .) Since $r^{2}_{k}=1$ and $a^{2}_{j}=a$ , we have $H^{2}_{k}(a(1))=\{b,c,d\}$ .

(i) Let $\tilde{s}=\{(6,8),(2,4,4,4)\}\in\tilde{S}_{-k}(a(1);r_{k})$ . Then $f(\tilde{s}+\hat{d})=(1,d)\succ_{k}(1,b)=f(\tilde{s}+\hat{a})$ , so $\hat{d}~{}\tilde{S}_{-k}$ -beats $\hat{a}$ .

(ii) For any $\tilde{s}\in\tilde{S}_{-k}(a(1);r_{k})$ , we have that if $f^{2}(\tilde{s}+\hat{d})=d$ then $f^{2}(\tilde{s}+\hat{a})=b$ ; otherwise $f^{2}(\tilde{s}+\hat{d})=f^{2}(\tilde{s}+\hat{a})$ . Hence, it is never preferable for $k$ to vote for $\hat{a}$ than $\hat{d}$ .

(iii) Neither $\hat{b}$ nor $\hat{c}$ $\tilde{S}_{-k}$ -dominate $\hat{d}$ since for $\tilde{s}=\{(6,8),(2,4,4,4)\}$ (the same as in (i)), it is preferable for $j$ to vote for $\hat{d}$ than either $\hat{b}$ or $\hat{c}$ .

(Step 3: $s^{2}(a(2))=(1,5,5,4)$ .) Since $r^{2}_{j}=1$ and $a^{2}_{j}=d$ , we have $H^{2}_{j}(a(2))=\{b,c,d\}$ .

(i) Let $\tilde{s}=\{(6,8),(1,4,4,4)\}\in\tilde{S}_{-j}(a(2);r_{j})$ . Then $f(\tilde{s}+\hat{a})=(1,b)\succ_{j}(1,d)=f(\tilde{s}+\hat{d})$ , so $\hat{a}~{}\tilde{S}_{-j}$ -beats $\hat{d}$ .

(ii) For any $\tilde{s}\in\tilde{S}_{-j}(a(2);r_{j})$ , we have that if $f^{2}(\tilde{s}+\hat{a})=d$ then $f^{2}(\tilde{s}+\hat{d})=d$ ; otherwise, if $f^{2}(\tilde{s}+\hat{d})\in\{b,c\}$ then $f^{2}(\tilde{s}+\hat{a})=f^{2}(\tilde{s}+\hat{d})$ . Hence, it is never preferable for $j$ to vote for $\hat{d}$ than $\hat{a}$ .

(iii) Neither $\hat{b}$ nor $\hat{c}$ $\tilde{S}_{-j}$ -dominate $\hat{a}$ since for $\tilde{s}^{\prime}=\{(6,8),(2,4,5,3)\}$ and $\tilde{s}^{\prime\prime}=\{(7,7),(2,4,4,3)\}$ it is preferable for $j$ to vote for $\hat{a}$ than $\hat{b}$ and $\hat{c}$ , respectively.

(Step 4: $s^{2}(a(3))=(2,5,5,3)$ .) Since $r^{2}_{k}=1$ and $a^{2}_{j}=d$ , we have $H^{2}_{k}(a(3))=\{a,b,c\}$ .

(i) Let $\tilde{s}=\{(6,8),(3,4,4,2)\}\in\tilde{S}_{-k}(a(3);r_{k})$ . Then $f(\tilde{s}+\hat{a})=(1,a)\succ_{k}(1,b)=f(\tilde{s}+\hat{d})$ , so $\hat{a}~{}\tilde{S}_{-k}$ -beats $\hat{d}$ .

(ii) For any $\tilde{s}\in\tilde{S}_{-k}(a(3);r_{k})$ , we have that if $f^{2}(\tilde{s}+\hat{a})=a$ then $f^{2}(\tilde{s}+\hat{d})=b$ ; otherwise $f^{2}(\tilde{s}+\hat{a})=f^{2}(\tilde{s}+\hat{d})$ . Hence, it is never preferable for $k$ to vote for $\hat{d}$ than $\hat{a}$ .

(iii) Neither $\hat{b}$ nor $\hat{c}$ $\tilde{S}_{-k}$ -dominate $\hat{a}$ since for $\tilde{s}=\{(6,8),(3,4,4,2)\}$ (the same as in (i)), it is preferable for $j$ to vote for $\hat{a}$ than either $\hat{b}$ or $\hat{c}$ .

Example 5.

Consider $p=2$ issues with three candidates each, labeled $\{A^{i},B^{i},C^{i},D^{i}\}$ for $i\leq 2$ . Let agent $j$ have $\ell_{\infty}$ uncertainty metric and $\mathcal{O}=(2,1)$ -legal preferences that satisfy:

•

If $f^{2}=C^{2}$ , then over issue $1$ : $A^{1}\succ_{j}B^{1}\succ_{j}D^{1}\succ_{j}C^{1}$
•

If $f^{2}=B^{2}$ , then over issue $1$ : $B^{1}\succ_{j}A^{1}\succ_{j}D^{1}\succ_{j}C^{1}$
•

If $f^{2}=A^{2}$ , then over issue $1$ : $C^{1}\succ_{j}A^{1}\succ_{j}B^{1}\succ_{j}D^{1}$

Suppose $a_{j}=(D^{1},C^{2})$ in vote profile $a$ with score tuple $s(a)=\{(6,6,3,5),(2,4,6,0)\}$ .

(Part 1: increasing $r^{1}_{j}$ .) This part of the example is motivated by Lemma 3b of Meir [2015].

If $r_{j}=(0,0)$ then it is easy to see that $j$ has no BR steps: the unique winner is $f(a)=(A^{1},C^{2})$ and, although $j$ can make $B^{1}$ win, they prefer $A^{1}\succ B^{1}$ when $f^{2}(a)=C^{2}$ . Hence $LD^{1}_{j}=\emptyset$ .

If $r_{j}=(1,0)$ then

\tilde{S}^{1}_{-j}=\{(5,6,7)\times(5,6,7)\times(2,3,4)\times(3,4,5)\}

First, when $\tilde{s}=\{(5,5,4,5),(2,4,6,0)\}\in\tilde{S}_{-j}$ , it is preferable for $j$ to vote for either $\hat{a}_{j}=(A^{1},C^{2})$ or $\hat{a}^{\prime}_{j}=(B^{1},C^{2})$ instead of $a_{j}$ . Recall that ties are broken by lexicographical order. Hence both $\hat{a}_{j}$ and $\hat{a}^{\prime}_{j}~{}\tilde{S}_{-j}$ -beat $a_{j}$ . Second, it is easy to see that there is no $\tilde{s}^{\prime}\in\tilde{S}_{-j}$ where it is preferable for $j$ to vote for $a_{j}$ instead of either $\hat{a}_{j}$ or $\hat{a}^{\prime}_{j}$ . Thus, $a_{j}$ does not $\tilde{S}_{-j}$ -beat either $\hat{a}_{j}$ or $\hat{a}^{\prime}_{j}$ . Third, we notice that $\hat{a}_{j}~{}\tilde{S}$ -dominates $\hat{a}^{\prime}_{j}$ , which which follows from $A^{1}\succ_{j}B^{1}$ whenever $f^{2}(a)=C^{2}$ . It is easy to see that $\hat{a}_{j}$ is not $\tilde{S}$ -dominated. Thus $LD^{1}_{j}=\{(A^{1},C^{2})\}$ .

Now consider $r_{j}=(2,0)$ . Then

	$\displaystyle\tilde{S}^{1}_{-j}=\{$	$\displaystyle(4,5,6,7,8)\times(4,5,6,7,8)$
	$\displaystyle\times$	$\displaystyle(1,2,3,4,5)\times(2,3,4,5,6)\}$

Since $\tilde{s}=\{(5,5,3,5),(2,4,6,0)\}\in\tilde{S}_{-j}$ , both $\hat{a}_{j}$ and $\hat{a}^{\prime}_{j}$ still $\tilde{S}_{-j}$ -beat $a_{j}$ . However, as $\tilde{s}=\{(4,4,5,5),(2,4,6,0)\}\in\tilde{S}_{-j}$ we have $f^{1}(\tilde{s}+a_{j})=(D^{1},C^{2})\succ_{j}(C^{1},C^{2})=f^{1}(\tilde{s}+\hat{a}_{j})=f^{1}(\tilde{s}+\hat{a}^{\prime}_{j})$ , so $a_{j}~{}\tilde{S}_{-j}$ -beats both $\hat{a}_{j}$ and $\hat{a}^{\prime}_{j}$ . Hence, $LD^{1}_{j}=\emptyset$ .

(Part 2: increasing $r^{2}_{j}$ .) Recall that when $r_{j}=(1,0)$ , we found that $\hat{a}_{j}=(A^{1},C^{2})~{}\tilde{S}_{-j}$ -dominated $a_{j}=(D^{1},C^{2})$ , while $\hat{a}^{\prime}_{j}=(B^{1},C^{2})~{}\tilde{S}_{-j}$ -dominated $a_{j}$ and $\hat{a}_{j}~{}\tilde{S}_{-j}$ -dominated $\hat{a}^{\prime}_{j}$ ; thus $LD^{1}_{j}=\{(A^{1},C^{2})\}$ .

If $r_{j}=(1,1)$ , then

\tilde{S}^{2}_{-j}=\{(1,2,3)\times(3,4,5)\times(4,5,6)\times(0,1)\}

For $\tilde{s}=\{(5,5,4,5),(2,4,5,0)\}\in\tilde{S}_{-j}$ it is preferable for $j$ to vote for $\hat{a}_{j}$ rather than $\hat{a}^{\prime}_{j}$ , whereas for $\tilde{s}=\{(5,5,4,5),(2,5,4,0)\}\in\tilde{S}_{-j}$ it is preferable for $j$ to vote for $\hat{a}^{\prime}_{j}$ rather than $\hat{a}_{j}$ . Then both $\hat{a}_{j}$ and $\hat{a}^{\prime}_{j}$ $\tilde{S}_{-j}$ -dominate $a_{j}$ but neither are $\tilde{S}_{-j}$ -dominated. Therefore $LD^{1}_{j}=\{(A^{1},C^{2}),(B^{1},C^{2})\}$ .

If $r_{j}=(1,2)$ , then

	$\displaystyle\tilde{S}^{2}_{-j}=\{$	$\displaystyle(0,1,2,3,4)\times(2,3,4,5,6)$
	$\displaystyle\times$	$\displaystyle(3,4,5,6,7)\times(0,1,2)\}$

Then there are score vectors $\tilde{s}\in\tilde{S}_{-j}$ where $f^{2}(\tilde{s}+a_{j})=f^{2}(\tilde{s}+\hat{a}_{j})=f^{2}(\tilde{s}+\hat{a}^{\prime}_{j})=C^{2}$ , so that neither $\hat{a}_{j}$ nor $\hat{a}^{\prime}_{j}~{}\tilde{S}_{-j}$ -dominate $a_{j}$ . Thus $LD^{1}_{j}=\emptyset$ .

Example 6.

Let there be $p=2$ binary issues and $n=13$ agents who each use the $\ell_{\infty}$ uncertainty metric with common fixed uncertainty parameters $(r^{1}_{j},r^{2}_{j})=(1,2)~{}\forall j\leq n$ . Suppose that agents’ preferences abide by the following four types:

•

(Type 1) three agents have rankings: $(0,1)\succ(1,1)\succ(1,0)\succ(0,0)$ ;
•

(Type 2) five agents have rankings: $(0,0)\succ(0,1)\succ(1,1)\succ(1,0)$ ;
•

(Type 3) four agents have rankings: $(1,0)\succ(1,1)\succ(0,0)\succ(0,1)$ ; and
•

(Type 4) one agent has ranking: $(1,1)\succ(1,0)\succ(0,1)\succ(0,0)$ .

There is a cycle passing through the four vote profiles $a(0)$ (which is truthful), $a(3)$ , $a(8)$ , and $a(11)$ listed in Table 2, in which every agent of the same type has the same vote. There are four parts of the cycle between these profiles:

•

between $a(0)$ and $a(3)$ , all agents of Type 1 make LDI steps on the first issue $(0,1)\xrightarrow{1}(1,1)$ ;
•

between $a(3)$ and $a(8)$ , all agents of Type 2 make LDI steps on the second issue $(0,0)\xrightarrow{2}(0,1)$ ;
•

between $a(8)$ and $a(11)$ , all agents of Type 1 make LDI steps on the first issue $(1,1)\xrightarrow{1}(0,1)$ ;
•

between $a(11)$ and $a(16)=a(0)$ , all agents of Type 2 make LDI steps on the second issue $(0,1)\xrightarrow{2}(0,0)$ .

Notice that no agent of Types 3 and 4 make LDI steps since they are voting truthfully and have separable preferences.

Agent Type $j$	$a_{j}(0)$	$a_{j}(3)$	$a_{j}(8)$	$a_{j}(11)$
$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)$
$4$	$(1,1)$	$(1,1)$	$(1,1)$	$(1,1)$

Table 2: Agents’ votes for

a(0)

(truthful),

a(3)

a(8)

, and

a(11)

We claim these are valid LDI steps as follows. For any vote profile in $\{a(0),a(1),a(2)\}$ , let $t$ be the number of Type 1 agents who have made LDI steps. Then $s(a(t))=\{(8-t,5+t),(9,4)\}$ and for any Type 1 agent $j$ who has not made their first LDI step yet,

$\tilde{S}^{1}_{-j}=\{(6-t,7-t,8-t)\times(4+t,5+t,6+t)\}$

$\tilde{S}^{2}_{-j}=\{(7,8,9,10,11)\times(2,3,4,5,6)\}$

Define $\hat{a}_{j}=(1,1)$ . Then $\tilde{s}=\{(6,6),(9,4)\in\tilde{S}_{-j}(a(t);r_{j})~{}\forall t\in\{0,1,2\}$ , so $f(\tilde{s}+\hat{a}_{j})=(1,0)\succ_{j}(0,0)=f(\tilde{s}+a_{j})$ and $\hat{a}_{j}~{}\tilde{S}_{-j}$ -beats $a_{j}$ . It is easy to see that $a_{j}$ does not $\tilde{S}_{-j}$ -beat $\hat{a}$ and that $\hat{a}$ is not $\tilde{S}_{-j}$ -dominated since issues are binary. Thus $LD^{1}_{j}=\{\hat{a}_{j}\}$ .

The other LDI steps follow similar reasoning, yielding the cycle presented in the table. It can be verified that this represents all possible LDI sequences from the truthful vote profile.

Appendix C Nonatomic model

Each of the results presented for binary issues and atomic agents, where each agent contributes one unit of influence to the population of $n$ votes, also generalize to a nonatomic variant of IV, in which agents are part of a very large population and have negligible influence over the outcome. Our model extends Meir [2015]’s iterative plurality voting for nonatomic agents to the multi-issue setting. Like this setting, our convergence results permit arbitrary subsets of agents to change their vote simultaneously. This differs from the finite case which may not converge if multiple agents change their votes simultaneously Meir et al. [2010].

In this section, we provide the necessary definitions for the nonatomic model, using our existing notation wherever possible. There are two major differences: (i) with the identify of an agent, and (ii) with the uncertainty score set. First, rather than treating each agent $j\leq n$ individually, there are groups of identical agents with $\epsilon$ mass; “an agent of type $j$ ” then refers to a representative agent in this group. Second, as agents have negligible influence, type $j$ agents consider any score tuple in $\tilde{S}(a;r_{j})$ possible; all agents agree of the same type agree what real score tuples are possible. Lemma 1 and Theorems 1, 2, and 3 are each upheld after applying this model redefinition. Similar non-convergence results also apply for the nonatomic variant of IV.

Basic notations.

We do not have a finite set of agents. Rather, a preference profile $Q\in\Delta(\mathcal{L}(D))$ is a distribution over rankings that specifies the fraction of agents $Q(R)$ for each $R\in\mathcal{L}(D)$ . We only consider moves by subsets of agents since each agent has negligible influence. To avoid infinite improvement sequence paths of sequentially smaller subsets of agents, we assume there is a minimum resolution $\epsilon$ , such that sets of agents of the same type with mass $\epsilon$ always move together (although in an uncoordinated manner; see Appendix IX of Meir [2015]). We denote the collection of these $1/\epsilon$ sets by $J$ . Since all agents in set $j\in J$ are indistinguishable, we refer to “agent $j$ ” as an arbitrary agent in the set $j$ . Then $R_{j}\in\mathcal{L}(D)$ is the preference, $r_{j}$ is the uncertainty parameter, and $a_{j}$ is the vote of an arbitrary agent in the set of vote profile $a$ .

Winner determination.

For any issue $i\in\mathcal{P}$ , we define the score vector $s^{i}(a)=(s^{i}(c;a))_{c\in D_{i}}$ induced by the vote profile $a$ such that $s^{i}(c;a)=|\{f:a^{i}_{j}=c\}|\epsilon\in[0,1]$ . Winner determination is exactly as in the atomic model with lexicographical tie-breaking.

Uncertainty and local dominance.

We assume agents utilize the same candidate-wise distance uncertainty as the atomic model. Like the atomic model, each agent of type $j\in J$ selected by the scheduler to change their vote has uncertainty parameters $r_{j}=(r^{i}_{j})_{i\in\mathcal{P}}$ . Unlike the atomic model, agents have negligible influence in the score vector. Hence, they take their uncertainty score sets with respect to the real score tuple: $\tilde{S}^{i}(a;r^{i}_{j})=\{v^{i}:\delta(v^{i},s^{i}(a))\leq r^{i}_{j}\}$ . As before, $\tilde{S}(a;r_{j})=\times_{i\in\mathcal{P}}\tilde{S}^{i}(a;r^{i}_{j})$ .

Given $v\in\tilde{S}(a;r_{j})$ , we define $f(v+a_{j})$ to be the outcome an agent of type $j$ expects by voting for $a_{j}$ according to score vector $s$ . That is, for each issue $i$ , the extra vote $a^{i}_{j}$ decides the winner if several candidates are tied with maximal score in $s$ , overriding the default tie-breaker (see Appendix X of Meir [2015]).

The definition of a local dominance improvement (LDI) step for a nonatomic agent of type $j\in J$ from vote $a_{j}$ to $\hat{a}_{j}$ on issue $i$ then is the same as in the atomic model of Definitions 3 and 4, applying this redefinition and using $\tilde{S}(a;r_{j})$ in lieu of $\tilde{S}_{-j}(a;r_{j})$ . The response function $g_{j}$ is also the same, except that its domain (all possible profiles) is now $\mathcal{D}^{|J|}$ rather than $\mathcal{D}^{n}$ . The definition of equilibrium does not change.

Convergence of Multi-Issue Iterative Voting under Uncertainty

Abstract

1 Introduction

1.1 Our Contribution

1.2 Related Work

2 Preliminaries

Basic model.

Simultaneous plurality voting.

Preferential dependence.

Example 1.

Improvement dynamics.

Definition 1.

Definition 2 (Best response).

Definition 3.

Definition 4 (Local dominance improvement).

Distance-based uncertainty.

Example 2.

Remark.

3 Best-Response Dynamics

Proposition 1.

Example 3.

4 Local Dominance Improvement Dynamics

4.1 Non-Convergence

Theorem 1.

Proposition 2.

4.2 Strategic responses and 𝒪\mathcal{O}-legal preferences

Definition 5.

Lemma 1.

Theorem 2.

Proof.

Proposition 3.

Example 4.

Corollary 1.

4.3 Alternating Uncertainty

Definition 6.

Theorem 3.

Proof.

5 Experiments

6 Discussion and Open Questions

References

Appendix

Appendix A Deferred Proofs

Theorem 1.

Proof.

Lemma 1.

Proof.

Appendix B Supplementary Examples

Example 4.

Example 5.

Example 6.

Appendix C Nonatomic model

Basic notations.

Winner determination.

Uncertainty and local dominance.

4.2 Strategic responses and $\mathcal{O}$ -legal preferences