The problem of fairly allocating a set of indivisible items is a well-known challenge in the field of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envy-freeness and proportionality) and economic efficiency (such as Pareto-optimality). However, in the real world, items are not always allocated once and for all, but often repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by this, we initiate the study of the repeated fair division of indivisible goods and chores, and propose a formal model for this scenario. In this paper, we show that, if the number of repetitions is a multiple of the number of agents, there always exists a sequence of allocations that is proportional and Pareto-optimal. On the other hand, irrespective of the number of repetitions, an envy-free and Pareto-optimal sequence of allocations may not exist. For the case of two agents, we show that if the number of repetitions is even, it is always possible to find a sequence of allocations that is overall envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envy-freeness. Finally, in case that the number of repetitions can be chosen freely, we show that envy-free and Pareto-optimal allocations are achievable for any number of agents.

In the context of aggregating intervals reflecting the views of several agents into a single interval, we investigate the impact of the form of representation chosen for the intervals involved. Specifically, we ask whether there are natural rules we can define both as rules that aggregate separately the left and right endpoints of intervals and as rules that aggregate separately the left endpoints and the interval widths. We show that on discrete scales it is essentially impossible to do so, while on continuous scales we can characterise the rules meeting these requirements as those that compute a weighted average of the endpoints of the individual intervals.

Abstract In this paper, we present two models for reasoning about strategic actions in opinion diffusion. In both models, the agents are endowed with goals expressed compactly in a suitably defined language of linear temporal logic and are connected in an influence network which defines the underlying opinion diffusion process. The agents can act by exerting their influence or retain from it: in one case, we assume an initial state of incomplete information about the agents’ opinions, while in the other, we assume that the agents have complete information. We investigate the interplay between simple network structures (e.g. certain acyclic graphs) and the existence of game-theoretic solution concepts for the unanimity aggregator. We also give bounds for the computational complexity of strategic reasoning in both our models on arbitrary networks.

We propose a generalisation of liquid democracy in which a voter can either vote directly on the issues at stake, delegate her vote to another voter, or express complex delegations to a set of trusted voters. By requiring a ranking of desirable delegations and a backup vote from each voter, we are able to put forward and compare four algorithms to solve delegation cycles and obtain a final collective decision.

We study agents expressing propositional goals over a set of binary issues to reach a collective decision. We adapt properties and rules from the literature on Social Choice Theory to our setting, providing an axiomatic characterisation of a majority rule for goal-based voting. We study the computational complexity of finding the outcome of our rules (i.e., winner determination), showing that it ranges from Nondeterministic Polynomial Time (NP) to Probabilistic Polynomial Time (PP).

Judgment aggregation models a group of agents having to collectively decide over a number of logically interconnected issues starting from their individual opinions. In recent years, a growing literature has focused on the design of logical systems for social choice theory, and for judgment aggregation in particular, making use of logical languages designed ad hoc for this purpose. In this paper we deploy the existing formalism of Dynamic Logic of Propositional Assignments (DL-PA), an instance of Propositional Dynamic Logic where atomic programs affect propositional valuations. We show that DL-PA is a well-suited formalism for modeling the aggregation of binary judgments from multiple agents, by providing logical equivalences in DL-PA for some of the best-known aggregation procedures, desirable axioms coming from the literature on judgment aggregation and properties for the safety of the agenda problem.