Speaker:
Stéphane Airiau (LAMSADE, Univ. Paris-Dauphine)
Title:
Generating and Testing Multi-issue Elections
Abstract: Some collective decision problems involve deciding about multiple issues. Due to the combinatorial aspect of the problem, it may not be feasible to use a single election for deciding all the issues at once. Many approaches have been proposed, one of which is to organize a sequence of elections about a few issues at a time. This solution is appealing as in each election the voters have to provide their preferences on a small number of alternatives. However, if the size of the election is kept small, the preferential dependencies of some voters may be violated and a voter may not know how to vote. When some agents cannot vote, we want to know how to choose the sequence of elections so that the elected winner is a good candidate. We ran computer simulations using artificial data and we show that agendas that minimize the number of violations often elect a legitimate winner, which indicates that this method could be used in practice.
Speaker:
Reyhan Aydogan (Department of Intelligent Systems, TU Delft)
Title:
Multilateral Mediated Negotiation Protocols with Feedback
Abstract: When more than two participants have a conflict of interest, finding a mutual agreement may entail a time consuming process, especially when the number of participants is high. Automated negotiation tools can play a key role in providing effective solutions. We present two variants of a feedback based multilateral negotiation protocol in which a mediator agent generates bids and negotiating agents provide their feedback about those bids. We investigate different types of feedback to model each agent's preferences , which accordingly generates well-targeted bids over time rather than arbitrary bids. We study the performance of those protocols in an experimental setting. This is joint work with Koen Hindriks and Catholijn Jonker.
Speaker:
Dorothea Baumeister (Institute for Informatics, University of Düsseldorf)
Title:
Interference in Judgment Aggregation
Abstract: The aim of a judgment aggregation process is to aggregate individual judgment sets of judges over possibly interconnected propositions to reach a collective outcome. In computational social choice, the complexity of changing the outcome of elections via manipulation, bribery, and various control actions, such as adding or deleting candidates or voters, has been studied intensely. The complexity-theoretic study of problems associated to judgment aggregation was initiated recently by the analysis of the winner determination and manipulation problem in judgment aggregation. We pursue this direction and study the complexity of manipulation for premise-based quota rules, a whole class of judgment aggregation procedures. A judgment aggregation scenario is said to be manipulable if one judge has an incentive to report an untruthful judgment set as this yields a more favorable outcome for him, where the distance between the preferences of the manipulator can be measured by the Hamming distance. We show not only NP-hardness but also study the parameterized complexity (W[2]-hardness) of this problem. Furthermore we show strategyproofness for certain restrictions on the agenda. Besides the manipulation problem, we also investigate different forms of bribery in judgment aggregation, where an external actor seeks to change the outcome by bribing some of the judges. This work is inspired by different bribery problems in voting theory. In addition to classical complexity (NP-hardness) results we also obtain W[2]-hardness with respect to one natural parameter, and membership in P for restricted problem instances. Furthermore, we introduce three different types of control specific to judgment aggregation. Here the set of participating judges may be changed, and these problems are again inspired by the corresponding problems from voting theory. NP-hardness is shown for all three types of control considered here. This is joint work with Gabor Erdélyi, Olivia Erdélyi, and Jörg Rothe.
Speaker:
Olivier Caillloux (ILLC, University of Amsterdam)
Title:
Building a Common Sorting Function for a Group of Decision Makers
Abstract: Multiple criteria sorting aims at assigning alternatives evaluated on several criteria to predefined ordered categories. We will consider a well-known multiple criteria sorting method, Electre TRI, which involves three types of preference parameters: (1) category limits defining the frontiers between consecutive categories, (2) weights and a majority level specifying which coalitions form a majority, and (3) veto thresholds characterizing discordance effects. We propose an elicitation procedure to infer category limits from assignment examples provided by multiple decision makers. The procedure computes a set of category limits and vetoes common to all decision makers, with variable weights for each decision maker. Hence, the method helps reaching a consensus among decision makers on the category limits and veto thresholds. Existing procedures permit to find a consensus on the weights and can thus be fruitfully combined with our proposal.
Speaker:
Burak Can (School of Business and Economics, Maastricht University)
Title:
A Re-characterization of the Kemeny Distance
Abstract: The well-known swap distance (Kemeny (1959); Kendall (1938); Hamming (1950)) is analyzed. On weak preferences, this function was characterized by Kemeny (1959) with five conditions: metric, betweenness, neutrality, reducibility, and normalization. We show that the same result can be achieved without the reducibility condition, therefore, the original five conditions are not logically independent. We provide a new and logically independent characterization of the Kemeny distance and provide some insight to further analyze distance functions on preferences.
Speaker:
Umberto Grandi (Department of Mathematics, University of Padova)
Title:
Restricted Manipulation in Iterative Voting
Abstract: In collective decision making, where a voting rule is used to take a collective decision among a group of agents, manipulation by one or more agents is usually considered a negative behaviour to be avoided, or at least to be made computationally difficult for the agents to perform. However, there are scenarios in which a restricted form of manipulation can instead be beneficial. In this paper we consider the iterative version of several voting rules, where at each step one agent is allowed to manipulate by modifying his ballot according to a set of restricted manipulation moves which are computationally easy and require little information to be performed. We prove convergence of iterative voting rules when restricted manipulation is allowed, and we present experiments showing that most iterative voting rules have a higher Condorcet efficiency and a higher average position of the winner than their non-iterative version. (Joint work with Andrea Loreggia, Francesca Rossi, Kristen Brent Venable and Toby Walsh.)
Speaker:
Martin van Hees (Department of Political Science, University of Amsterdam)
Title:
Constructing a Formula of Universal Law
Abstract: This paper provides a methodologically original construction of Kant's "Formula of Universal Law" (FUL). A formal structure consisting of possible worlds and games--a "game frame"--is used to implement Kant's concept of a maxim and to define versions of the two tests FUL comprises: the "contradiction in conception" and "contradiction in the will" tests. The analysis reinforces existing doubts that Kant's famous defence of the duty of beneficence cannot be sustained. Furthermore, we show that certain agent-neutral forms of consequentialism satisfy FUL. We conclude by suggesting that the problems can be circumvented if we focus on what we call "comprehensive" Kantianism, which is the application of FUL to systems of maxims rather than to isolated maxims. This is joint work with Matthew Braham.
Speaker:
Ines Lindner (Department of Econometrics & OR, VU Amsterdam)
Title:
Cascade Dynamics in Social Networks
Abstract: Collective action sometimes seems to appear from nowhere, e.g., large protests against a particular regime suddenly bring onto the streets thousands and thousands of people as happened in the Arabic Spring which started in December 2010 in Tunisia. Although the synchronization of action and the outburst as such might come as a surprise, it is not uncommon in such situations that a "sentiment" against the regime has already been building up under the surface for quite some time. Following models of biological synchronization, we study volatility of crowd behavior and the orchestrating role of social networks. (Joint work with Jia-Ping Huang and Maurice Koster.)
Speaker:
Nicolas Maudet (LIP6, Univ. Pierre et Marie Curie, Paris)
Title:
Voting Rules and Strategic Candidacy: Some Recent Results
Abstract: We consider a voting setting where candidates have preferences about the outcome of the election and are free to join or leave the election. The corresponding candidacy game, where candidates choose strategically to participate or not, has been studied in very few papers, mainly by Dutta et al., who showed that no non-dictatorial voting procedure satisfying unanimity is candidacy-strategyproof, or equivalently, is such that the joint action where all candidates enter the election is always a pure strategy Nash equilibrium. They also showed that for voting trees, there are candidacy games with no pure strategy Nash equilibria. However, no results were known about other voting rules. Here we prove several such results. Some are positive (a pure strategy Nash equilibrium is guaranteed for Copeland and the uncovered set, whichever the number of candidates, and for all Condorcet-consistent rules, for 4 candidates). Some are negative, namely for plurality and maximin. We also study the existence of strong equilibria. (This is joint work with Jérôme Lang and Maria Polukarov.)
Speaker:
Daniele Porello (Institute of Cognitive Science and Technology, CNR Trento)
Title:
A Proof-Theoretical View of Collective Rationality
Abstract: The impossibility results in judgement aggregation show the tension between our definitions of fair aggregation procedures and our view of rational collective outcomes. In this work, we present an analysis of the notion of rational outcome by proposing a proof-theoretical understanding of rationality. In particular, we use the analysis of proofs and inferences provided by linear logic in order to study collective rationality with respect to a number of logics. We analyse the well-known paradoxes in judgement aggregation and we pinpoint the reasoning steps that trigger the inconsistencies. In particular, we show that there exist fragments of linear logic for which general possibility results can be obtained.
Speaker:
Guido Schäfer (CWI & VU Amsterdam)
Title:
Altruism and Spite in Games
Abstract: In most game-theoretical studies it is assumed that the decision makers base their decisions on purely selfish grounds. This assumption is in stark contrast with a large body of research in experimental economics and the social sciences, which suggest that decision makers are often motivated by other-regarding preferences such as altruism, spite or fairness. Very little attention has been given to the analysis of the impact of such alternative behaviors. In this talk, we review some recent advances in the study of the inefficiency of equilibria when players are (partially) altruistic or spiteful and highlight a few counter-intuitive results.