- comsoc-seminar - list.uva.nl

[COMOSC Seminar] Frank Feys on Tuesday at 16:00
by Ulle Endriss 20 Jun '19

20 Jun '19

Dear all, The next Computational Social Choice Seminar at the ILLC will take place next week on Tuesday at 16:00 and will be delivered by Frank Feys (TU Delft), who will talk about a new proof of Arrow's Theorem based on a fixed-point argument. I'm including the abstract below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Frank Feys (Delft) Title: Arrow's Theorem through a Fixpoint Argument Date: Tuesday 25 June 2019 Time: 16:00 Location: Room F2.19, Science Park 107, Amsterdam Abstract: Social choice theory studies mathematically the processes involved when groups of people make choices. The classical result that has inspired much of the research in this area is Arrow's impossibility theorem about the non-existence of ideal election systems. Arrow's original proof proceeded by showing the existence of a "decisive" voter. In this talk, we present a proof of Arrow’s theorem that uses a fixpoint argument. Specifically, we use Banach’s fixpoint theorem, which states that a contractive map on a complete metric space has a unique fixpoint. To this end, we first define a metric parametrized by a probability distribution on profiles: we let the distance between two voting rules be the probability under the given distribution that the outcome of the election is different. The use of a distribution has the benefit that it allows for profiles to be considered concurrently. Inspired by the technical notion of influence from Boolean analysis, we then define a notion that we call "force" of a voter, which is the probability that the outcome of the election coincides with that voter’s preference. We use this notion to define a map (a process that transforms voting rules) which is shown to be a contraction with the set of dictators as unique fixpoint. Our proof does not require us to manipulate specific profiles, like most other previous proofs of Arrow’s theorem, but offers an analytic perspective in terms of fixpoints and convergence rather than a combinatoric one. Conceptually, our approach shows that dictatorships can be seen as "stable points" (fixpoints) of a certain process. This talk is based on joint work with Helle Hvid Hansen. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Hossein Khani on Tuesday at 16:00
by Ulle Endriss 10 Jun '19

10 Jun '19

Dear all, The next Computational Social Choice Seminar at the ILLC will take place tomorrow, Tuesday, at 16:00. Hossein Khani is visiting from Paris-Dauphine University for the week and will be presenting his ideas on ordinal power indices. I'm including the abstract below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Hossein Khani (Paris) Title: Ordinal Power Indices Date: Tuesday 11 June 2019 Time: 16:00 Location: Room F0.22, Science Park 107, Amsterdam Abstract: The problem of evaluating the influence of individuals in a society when the ranking of teams formed by them is given is of great relevance in the context of decision theory, social choice theory, and game theory. Consider, for instance, the problem of estimating the "power" of countries in the process of collective decision making in an international parliament, or the ranking of researchers in a department based on the relative performance of research teams. In many such situations it is not possible to evaluate the worth (value) of teams (or coalitions) precisely due to several factors: uncertain data, the complexity of the analysis, missing information, or difficulties in the update. Therefore, the main objective in this talk is to answer the general question of how to obtain an ordinal ranking over a finite set of individuals (called social ranking solution), given an ordinal ranking over coalitions of individuals (called power relation). We answer this question using two approaches: First, using classical social choice theory and based on the "Ceteris Paribus principle", we define a social ranking solution that ranks any two individuals according to their performance when they join the same coalition. By defining a restriction of the structure of the power relation called "social single-peakedness" we guarantee the transitivity of the resulting ranking on individuals. Second, in the context of cooperative game theory, we introduce a social ranking solution by extending the classical notion of the Banzhaf index to our ordinal framework. We investigate both of these social ranking solutions using a property-driven approach, and we characterize them by a set of well-defined axioms. Finally we emphasize the similarity of the two proposed solutions by indicating that they belong to a larger family of solutions. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Suzanne Bloks on Friday at 16:00
by Ulle Endriss 29 Apr '19

29 Apr '19

Dear all, The next Computational Social Choice Seminar at the ILLC will take place this Friday. Suzanne Bloks will speak about the work she did for her Master's thesis on Condorcet winning sets at the London School of Economics, before joining the ILLC a month ago. The abstract is included below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Suzanne Bloks (ILLC) Title: Minimum-sized Condorcet Winning Sets in Preference Profiles Date: Friday 3 May 2019 Time: 16:00 Location: Room F1.15, Science Park 107, Amsterdam Abstract This talk approaches an open question in Computational Social Choice Theory, posed by Elkind, Lang and Saffidine in 2015: Do there exist preference profiles in which the minimum size of a Condorcet winning set is bigger than 3? A Condorcet winning set is a generalization of the Condorcet winner. A set Y is a Condorcet winning set if for every candidate z not in Y a majority of voters prefer some candidate in Y to z. Elkind, Lang and Saffidine have constructed a preference profile in which the minimum size of a Condorcet winning set is 3. That is, there is no Condorcet winner or a Condorcet winning set of size 2 in the constructed profile. It remains an open question whether preference profiles can be constructed with minimum Condorcet winning sets of size 4 or higher. In this talk, we will explore this question by relating Condorcet winning sets in preference profiles to dominating sets in tournaments. The concept of dominating sets in tournaments is related to but stronger than the concept of Condorcet winning sets in preference profiles. We will use this relation to make advancements towards constructing preference profiles with Condorcet dimension 4 or higher. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Daan Bloembergen on Friday at 16:00
by Ulle Endriss 02 Apr '19

02 Apr '19

Dear all, The next the Computational Social Choice Seminar at the ILLC will take place this Friday. Our speaker is Daan Bloembergen from the CWI and he will talk about recent work on liquid democracy. Full abstract below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Daan Bloembergen (CWI) Title: On Rational Delegations in Liquid Democracy Date: Friday 5 April 2019 Time: 16:00 Location: Room F1.15, Science Park 107, Amsterdam Abstract: This talk consists of two parts. In the first part, I will present our recent paper that was published at AAAI'19, titled "On Rational Delegations in Liquid Democracy". Liquid democracy is a proxy voting method where proxies are delegable. In the paper we propose and study a game-theoretic model of liquid democracy to address the following question: when is it rational for a voter to delegate her vote? We study the existence of pure-strategy Nash equilibria in this model, and how group accuracy is affected by them. We complement these results by means of simulations to study the effect of network structures on group's accuracy, and various aspects of the patterns of delegations that emerge in this type of interaction. In the second part, I will sketch a brief and high-level overview of my main area of research, which focuses on multi-agent reinforcement learning. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Dominik Peters on Wednesday at 16:00
by Ulle Endriss 25 Mar '19

25 Mar '19

Dear all, The next talk in the Computational Social Choice Seminar at the ILLC will be given by Dominik Peters (Oxford) this Wednesday at 16:00. Dominik will be speaking about participatory budgeting. The abstract is included below. I hope to see you at the seminar. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Dominik Peters (Oxford) Title: Truthful Aggregation of Budget Proposals Date: Wednesday 27 March 2019 Time: 16:00 Location: Room F3.20, Science Park 107, Amsterdam Abstract: We consider a participatory budgeting problem in which each voter submits a proposal for how to divide a single divisible resource (such as money or time) among several possible alternatives (such as public projects or activities) and these proposals must be aggregated into a single consensus division. Under ℓ_1 preferences---for which a voter's disutility is given by the ℓ_1 distance between the consensus division and the division he or she most prefers---the social welfare-maximizing mechanism, which minimizes the average ℓ_1 distance between the outcome and each voter's proposal, is incentive compatible [Goel et al. 2016]. However, it fails to satisfy a natural fairness notion of proportionality, placing too much weight on majority preferences. Leveraging a connection between market prices and the generalized median rules of Moulin [1980], we introduce the independent markets mechanism, which is both incentive compatible and proportional. We unify the social welfare-maximizing mechanism and the independent markets mechanism by defining a broad class of moving phantom mechanisms that includes both. We show that every moving phantom mechanism is incentive compatible. Finally, we characterize the social welfare-maximizing mechanism as the unique Pareto-optimal mechanism in this class, suggesting an inherent tradeoff between Pareto optimality and proportionality. (This is joint work with Rupert Freeman, David Pennock, and Jenn Wortman Vaughan.) -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Emel Öztürk on Friday at 16:00
by Ulle Endriss 18 Mar '19

18 Mar '19

Dear all, The next talk in the Computational Social Choice Seminar at the ILLC is scheduled for this Friday already. Emel Öztürk from the UvA's Faculty of Economics and Business will present her work on the axiomatic analysis of the problem of finding a fair and stable allocation of water extracted from a river to a group of stake-holders with different entitlements. The talk will start at 16:00. I'm including the abstract below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Z. Emel Öztürk (UvA) Title: An Efficient, Fair and Stable Solution to the River Sharing Problem Date: Friday 22 March 2019 Time: 16:00 Location: Room F1.15, Science Park 107, Amsterdam Abstract A group of agents is ordered along a linear river. Each agent has quasilinear preferences over water and money. A vector of property rights, referred to as the reference vector, specifies how much water each agent is entitled to. The key concept in this study is an allocation's distance-to-reference vector. At an allocation, this vector specifies, for each agent, the amount of money that needs to be subtracted from the bundle the agent receives in order for the agent to be indifferent between the reference vector and the allocation. First, we characterize a social ordering, called the reference-welfare equivalent Lorenz ordering, which prefers an allocation to another if the distance-to-reference vector of the former is more equal than the distance-to-reference vector of the latter. Second, we show that maximizing the reference-welfare equivalent Lorenz ordering over the set of acceptable allocations (defined in the sense of the core) leads to a unique allocation which meets the three key objectives of international river management: efficiency, fairness and stability. Moreover, we show that this allocation coincides with the egalitarian solution of Dutta and Ray (Econometrica, 1989) and the downstream incremental solution of Ambec and Sprumont (Journal of Economic Theory, 2002) for particular conceptions of property rights. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Jérôme Lang on Monday at 15:00
by Ulle Endriss 12 Mar '19

12 Mar '19

Dear all, The next talk in the Computational Social Choice Seminar at the ILLC will take place next Monday. Jérôme Lang (Paris) will speak about communication issues for the rule of single transferable vote. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Jérôme Lang (Paris) Title: Single Transferable Vote: Incomplete Knowledge and Communication Issues Date: Monday 18 March 2019 Time: 15:00 Location: Room F0.20, Science Park 107, Amsterdam Abstract: Single Transferable Vote (STV) is used in large political elections around the world. It is easy to understand and has desirable normative properties, such as clone-proofness. However, voters need to report full rankings, which can make it less practical than plurality voting. We study ways to minimize the amount of communication required to use single-winner STV. In the first part of the talk, voters are assumed to report their top-k alternatives in a single shot. We empirically evaluate the extent to which STV with truncated ballots approximates STV with full information. We also study the computational complexity of the possible winner problem for top-k ballots. For k = 1, it can be solved in polynomial time, but it is NP-complete when k > 1. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm in 2005, we show how we can reduce the amount of communication required in practice. We then study empirically the average communication complexity of these protocols, based on randomly generated profiles, and on real-world election data. Our conclusion is that STV needs, in practice, much less information than in the worst case. (This is joint work with Manel Ayadi, Nahla Ben Amor, and Dominik Peters.) -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Adrian Haret on Monday at 15:00
by Ulle Endriss 01 Mar '19

01 Mar '19

Dear all, The next talk in the Computational Social Choice Seminar at the ILLC is this coming Monday already. Adrian Haret (Vienna) will talk about the aggregation of CP-nets at 15:00. I include the abstract below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Adrian Haret (Vienna) Title: Preference Aggregation with Incomplete CP-nets Date: Monday 4 March 2019 Time: 15:00 Location: Room F1.15, Science Park 107, Amsterdam Abstract: Generalized CP-nets (gCP-nets) extend standard CP-nets by allowing conditional preference tables to be incomplete. Such generality is desirable, as in practice users may want to express preferences over the values of a variable that depend only on partial assignments for other variables. In this paper we study aggregation of gCP-nets, under the name of multiple gCP-nets (mgCP-nets). Inspired by existing research on mCP-nets, we define different semantics for mgCP-nets and study the complexity of prominent reasoning tasks such as dominance, consistency and various notions of optimality. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Marija Slavkovik on Thursday and Arianna Novaro on Friday
by Ulle Endriss 25 Feb '19

25 Feb '19

Dear all, This week we are going to have two talks in the Computational Social Choice Seminar at the ILLC, both of them related to judgment aggregation, but deviating from the standard model in different ways. On Thursday at 15:00 Marija Slavkovik (Bergen) will speak about aggregating likelihood judgments, and on Friday at 16:00 Arianna Novaro (Toulouse) will speak about goal-based voting. I include both abstracts below. As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. All the best, Ulle ------------------------------------------------------------------------- Speaker: Marija Slavkovik (Bergen) Title: Aggregation of Likelihood Judgments Date: Thursday 28 February 2019 Time: 15:00 Location: Room F1.15, Science Park 107, The Netherlands Abstract: Judgment aggregation studies methods for aggregating individual opinions on logically related issues. So far, concrete aggregators have been proposed only for aggregating binary, or Boolean, judgments. However, opinion sources do not always provide binary judgments. Sometimes we have judgments expressing likelihood, not certainty, of whether a proposition is true. We here propose a framework and a first set of specific aggregation methods for aggregating likelihood judgments. Our aggregation methods are mainly obtained by generalizing known classic judgment aggregation methods that satisfy some essential desirable properties. ------------------------------------------------------------------------- Speaker: Arianna Novaro (Toulouse) Title: Collective Decisions with Logic-based Goals Date: Friday 1 March 2019 Time: 16:00 Location: Room F1.15, Science Park 107, Amsterdam Abstract: In this talk I will present the framework of goal-based voting, where agents express their individual goals as formulas of propositional logic, with the common objective of reaching a collective decision (e.g., which points of interest to visit together when exploring a new city). I will present some voting rules for this setting, adapted from the literature on Social Choice Theory, which will then be studied from both an axiomatic and a computational perspective. In the final part, I will focus on agents acting strategically, i.e., agents reporting a goal that differs from their truthful one if by doing so they can get a better outcome. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 0

[COMOSC Seminar] Femke Bekius this Friday at 16:00
by Ulle Endriss 06 Feb '19

06 Feb '19

Dear all, This is your reminder for the next edition of the Computational Social Choice Seminar at the ILLC. Femke Bekius (TU Delft) will speak about the use of concepts from game theory to model complex decision making scenarios. I hope to see you at the seminar this Friday! All the best, Ulle ------------------------------------------------------------------------- Speaker: Femke Bekius (Delft) Title: Game Concepts to Understand Collective Decision-Making on Complex Systems Date: Friday 8 February 2019 Time: 16:00 Location: Room F1.15, Science Park 107, Amsterdam Abstract: Real-world decision-making on complex systems is complex due to the technical uncertainties of the system: multiple actors with different incentives are involved and the environment in which the decision-making takes place is dynamic. To understand the process of such collective decision-making we look for patterns and mechanisms that characterize these processes. These patterns and mechanisms, so-called game concepts, origin from game theory and public administration. In this talk, I will present the approach of applying game concepts to real-world decision-making processes, both in a descriptive and in a prescriptive way. This means that we are not only interested in the theoretical insights, but also how the approach can enable decision-makers in their daily work. The application area of this research is the Dutch railway sector, hence examples from this area will be used. The talk will be broadly accessible and no prior knowledge of either the theoretical concepts or the application domain will be assumed. For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/. -- Ulle Endriss ILLC, University of Amsterdam http://www.illc.uva.nl/~ulle/

1 1

2024

2023

2022

2021

2020

2019

comsoc-seminar