We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms.

Multiwinner voting captures a wide variety of settings, from parliamentary elections in democratic systems to product placement in online shopping platforms. There is a large body of work dealing with axiomatic characterizations, computational complexity, and algorithmic analysis of multiwinner voting rules. Although many challenges remain, significant progress has been made in showing existence of fair and representative outcomes as well as efficient algorithmic solutions for many commonly studied settings. However, much of this work focuses on single-shot elections, even though in numerous real-world settings elections are held periodically and repeatedly. Hence, it is imperative to extend the study of multiwinner voting to temporal settings. Recently, there have been several efforts to address this challenge. However, these works are difficult to compare, as they model multi-period voting in very different ways. We propose a unified framework for studying temporal fairness in this domain, drawing connections with various existing bodies of work, and consolidating them within a general framework. We also identify gaps in existing literature, outline multiple opportunities for future work, and put forward a vision for the future of multiwinner voting in temporal settings.

Restricted domains over voter preferences have been extensively studied within the area of computational social choice, initially for preferences that are total orders over the set of alternatives and subsequently for preferences that are dichotomous—i.e., that correspond to approved and disapproved alternatives. This paper contributes to the latter stream of work in a twofold manner. First, we obtain forbidden subprofile characterisations for various important dichotomous domains. Then, we are concerned with incomplete profiles that may arise in many real-world scenarios, where we have partial information about the voters’ preferences. We tackle the problem of determining whether an incomplete profile admits a completion within a certain restricted domain and design constructive, polynomial algorithms to that effect.

Current value-based multi-agent reinforcement learning methods optimize individual Q values to guide individuals' behaviours via centralized training with decentralized execution (CTDE). However, such expected, i.e., risk-neutral, Q value is not sufficient even with CTDE due to the randomness of rewards and the uncertainty in environments, which causes the failure of these methods to train coordinating agents in complex environments. To address these issues, we propose RMIX, a novel cooperative MARL method with the Conditional Value at Risk (CVaR) measure over the learned distributions of individuals' Q values. Specifically, we first learn the return distributions of individuals to analytically calculate CVaR for decentralized execution. Then, to handle the temporal nature of the stochastic outcomes during executions, we propose a dynamic risk level predictor for risk level tuning. Finally, we optimize the CVaR policies with CVaR values used to estimate the target in TD error during centralized training and the CVaR values are used as auxiliary local rewards to update the local distribution via Quantile Regression loss. Empirically, we show that our method outperforms many state-of-the-art methods on various multi-agent risk-sensitive navigation scenarios and challenging StarCraft II cooperative tasks, demonstrating enhanced coordination and revealing improved sample efficiency.

Complexity of voting manipulation is a prominent topic in computational social choice. In this work, we consider a two-stage voting manipulation scenario. First, a malicious party (an attacker) attempts to manipulate the election outcome in favor of a preferred candidate by changing the vote counts in some of the voting districts. Afterwards, another party (a defender), which cares about the voters' wishes, demands a recount in a subset of the manipulated districts, restoring their vote counts to their original values. We investigate the resulting Stackelberg game for the case where votes are aggregated using two variants of the Plurality rule, and obtain an almost complete picture of the complexity landscape, both from the attacker's and from the defender's perspective.

Obraztsova et al. (2013) have recently proposed an intriguing convexity axiom for voting rules. This axiom imposes conditions on the shape of the sets of elections with a given candidate as a winner. However, this new axiom is both too weak and too strong: it is too weak because it defines a set to be convex if for any two elements of the set some shortest path between them lies within the set, whereas the standard definition of convexity requires all shortest paths between two elements to lie within the set, and it is too strong because common voting rules do not satisfy this axiom. In this paper, we (1) propose several families of voting rules that are convex in the sense of Obraztsova et al.; (2) put forward a weaker notion of convexity that is satisfied by most common voting rules; (3) prove impossibility results for a variant of this definition that considers all, rather than some shortest paths.

We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height.

Decision making under uncertainty is a key component of many AI settings, and in particular of voting scenarios where strategic agents are trying to reach a joint decision. The common approach to handle uncertainty is by maximizing expected utility, which requires a cardinal utility function as well as detailed probabilistic information. However, often such probabilities are not easy to estimate or apply.To this end, we present a framework that allows for “shades of gray” of likelihood without probabilities. Specifically, we create a hierarchy of sets of world states based on a prospective poll, with inner sets contain more likely outcomes. This hierarchy of likelihoods allows us to define what we term ordinally-dominated strategies. We use this approach to justify various known voting heuristics as bounded-rational strategies.

Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is being used in order to decide upon the exact time of the meeting. Decisions are to be taken during the meeting, therefore each team would like to maximize its relative attendance (i.e. the proportional number of its team members attending the meeting). We introduce a corresponding game, where each team can declare a lower total availability in the scheduling poll in order to improve its relative attendance—the pay-off. We are especially interested in situations where teams can form coalitions. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in a coalition to improve its pay-off. In contrast, we show that deciding whether such a coalition exists is NP-hard. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is coNP-hard if the coalition size is unbounded.

Voting is a common way to reach a group decision. When possible, voters will attempt to vote strategically, in order to optimize their satisfaction from the outcome. Previous research has modelled how rational voter agents (bots) vote to maximize their personal utility in an iterative voting process that has a deadline (a timeout). However, it remains an open question whether human beings behave rationally when faced with the same settings. The focus of this paper is therefore to examine how the deadline factor affects manipulative behavior in real-world scenarios were humans are required to reach a decision before a deadline. An On-line platform was built to enable voting games by all types of users: agents (bots), humans, and mixed games with both humans and agents. We compare the results of human behavior and bot behavior and conclude that it might be wise to allow bots to make (certain) decisions on our behalf.

In this paper we expand the standard Hotelling-Downs model of spatial competition to a setting where clients do not necessarily choose their closest candidate (retail product or political). Specifically, we consider a setting where clients may disavow all candidates if there is no candidate that is sufficiently close to the client preferences. Moreover, if there are multiple candidates that are sufficiently close, the client may choose amongst them at random. We show the existence of Nash Equilibria for some such models, and study the price of anarchy and stability in such scenarios.

We study the complexity of deciding if a given profile of incomplete votes (i.e., a profile of partial orders over a given set of alternatives) can be extended to a single-crossing profile of complete votes (total orders). This problem models settings where we have partial knowledge regarding voters' preferences and we would like to understand whether the given preference profile may be single-crossing. We show that this problem admits a polynomial-time algorithm when the order of votes is fixed and the input profile consists of top orders, but becomes NP-complete if we are allowed to permute the votes and the input profile consists of weak orders or independent-pairs orders. Also, we identify a number of practical special cases of both problems that admit polynomial-time algorithms.

We study convergence properties of iterative voting procedures. Such procedures are defined by a voting rule and a (restricted) iterative process, where at each step one agent can modify his vote towards a better outcome for himself. It is already known that if the iteration dynamics (the manner in which voters are allowed to modify their votes) are unrestricted, then the voting process may not converge. For most common voting rules this may be observed even under the best response dynamics limitation. It is therefore important to investigate whether and which natural restrictions on the dynamics of iterative voting procedures can guarantee convergence. To this end, we provide two general conditions on the dynamics based on iterative myopic improvements, each of which is sufficient for convergence. We then identify several classes of voting rules (including Positional Scoring Rules, Maximin, Copeland and Bucklin), along with their corresponding iterative processes, for which at least one of these conditions hold.

Following recent studies of iterative voting and its effects on plurality vote outcomes, we provide characterisations and complexity results for three models of iterative voting under the plurality rule. Our focus is on providing a better understanding regarding the set of equilibria attainable by iterative voting processes. We start with the basic model of plurality voting. We first establish some useful properties of equilibria, reachable by iterative voting, which enable us to show that deciding whether a given profile is an iteratively reachable equilibrium is NP-complete. We then proceed to combine iterative voting with the concept of truth bias, a model where voters prefer to be truthful when they cannot affect the outcome. We fully characterise the set of attainable truth-biased equilibria, and show that it is possible to determine all such equilibria in polynomial time. Finally, we also examine the model of lazy voters, in which a voter may choose to abstain from the election. We establish convergence of the iterative process, albeit not necessarily to a Nash equilibrium. As in the case with truth bias, we also provide a polynomial time algorithm to find all the attainable equilibria.

Recently Bai and Lagunoff [1] have studied the question of Faustian Dynamics (FD) of policy and political power using a formal game theoretic framework. Specifically, they studied the conflict between implementing a (personally) optimal policy and maintaining political power. However, these works assumed that the policy makers come from the same population that empowers them. In contrast, in this paper we study a society that has a political class, hence policy makers are detached from the general population. Specifically, we study a society where members of the political class compete via pre-election propaganda campaigns – a competition form characteristic to modern democracies. We assume that the society is characterised by an inherent cyclical Faustian dynamics, such as the Sarkar Cycle, and concentrate on the strategic behaviour of the political class members. We show that their propaganda over time tends to become extreme (single issue oriented). In addition, the equilibrium behaviour of the political class members precludes them from adopting a persistent agenda. Rather, to optimise their political gain over time, they must lack any permanent agenda or views.

Complexity of voting manipulation is a prominent research topic in computational social choice. The voting manipulation literature usually assumes that the manipulator is only concerned with improving the outcome of the election from her perspective. However, in practice, the manipulator may also be reluctant to lie, i.e., she may have a preference for submitting a vote that does not deviate too much from her true ranking of the candidates. In this paper, we study the complexity of finding a manipulative vote that achieves the manipulator's goal yet is as close as possible to her true preference order. We analyze this problem for three natural notions of closeness, namely, swap distance, footrule distance, and maximum displacement distance, and a variety of voting rules, such as scoring rules, Bucklin, Copeland, and Maximin. For all three distances, we obtain polynomial-time algorithms for all scoring rules and Bucklin and hardness results for Copeland and Maximin.

Computational complexity of voting manipulation is one of the most actively studied topics in the area of computational social choice, starting with the groundbreaking work of [Bartholdi et al., 1989]. Most of the existing work in this area, including that of [Bartholdi et al., 1989], implicitly assumes that whenever several candidates receive the top score with respect to the given voting rule, the resulting tie is broken according to a lexicographic ordering over the candidates. However, till recently, an equally appealing method of tiebreaking, namely, selecting the winner uniformly at random among all tied candidates, has not been considered in the computational social choice literature. The first paper to analyze the complexity of voting manipulation under randomized tiebreaking is [Obraztsova et al., 2011], where the authors provide polynomial-time algorithms for this problem under scoring rules and—under an additional assumption on the manipulator’s utilities— for Maximin. In this paper, we extend the results of [Obraztsova et al., 2011] by showing that finding an optimal vote under randomized tie-breaking is computationally hard for Copeland and Maximin (with general utilities), as well as for STV and Ranked Pairs, but easy for the Bucklin rule and Plurality with Runoff.

In their groundbreaking paper, Bartholdi, Tovey and Trick [1989] argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important assumption made in that paper is that the manipulator's goal is to ensure that his preferred candidate is among the candidates with the maximum score, or, equivalently, that ties are broken in favor of the manipulator's preferred candidate. In this paper, we examine the role of this assumption in the easiness results of [Bartholdi et al., 1989]. We observe that the algorithm presented in [Bartholdi et al., 1989] extends to all rules that break ties according to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator's utility function that is inspired by the original model of [Bartholdi et al., 1989]. In contrast, we show that manipulation becomes hard when arbitrary polynomial-time tie-breaking rules are allowed, both for the rules considered in [Bartholdi et al., 1989], and for a large class of scoring rules.