Dear all,
The next Computational Social Choice Seminar at the ILLC will take place
on Monday at 15:00. It will be delivered by Lefteris Kirousis (Athens),
who is going to be visiting for the day. He will speak about possibility
results in judgment aggregation. I'm including the abstract below.
As always, for more information on the COMSOC Seminar please consult
http://www.illc.uva.nl/~ulle/seminar/.
All the best,
Ulle
-------------------------------------------------------------------------
Speaker: Lefteris Kirousis (Athens)
Title: Abstract Possibility Domains: Algorithms and Characterizations
Date: Monday 1 July 2019
Time: 15:00
Location: ILLC Room F1.15, Science Park 107, Amsterdam
Abstract
Let V be a set of possible evaluations on an issue, with cardinality two
or possibly greater. An abstract domain (or just domain) is an arbitrary
subset D of a Cartesian power V^m. The elements of a domain are
considered to represent the rational, or permissible, evaluation vectors
on m issues, in some abstract sense of rationality. Given an integer
k>1, a k-ary aggregator for D is a function F defined for all elements
of D^k and taking values in D. We assume that aggregators are defined
independently on each issue and that they are supportive. An aggregator
F is called non-dictatorial if it differs from all projection functions
on any d in 1..k. A domain D is called a possibility domain if it admits
a non-dictatorial aggregator of some arity k. I will first give
necessary and sufficient conditions for D to be a possibility domain in
terms of existence of binary or ternary aggregators. Using this
characterization as a stepping stone, I will give efficient (polynomial
time in the size of the domain) algorithms that decide whether an input
domain is a possibility one. Finally in the case the cardinality of V is
exactly two (Boolean case), I will define a class of Conjunctive Normal
Form formulas of Propositional Logic that describe the domains that are
possibility ones. I will also prove that such formulas are recognizable
in linear time in the size of the input formula.
--
Ulle Endriss
ILLC, University of Amsterdam
http://www.illc.uva.nl/~ulle/
Dear all,
Unfortunately, we had to cancel the talk by Frank Feys in the COMSOC
Seminar at the ILLC planned for this Tuesday, because Frank got sick. I
hope that we will be able to reschedule his talk sometime soon.
http://www.illc.uva.nl/~ulle/seminar/
All the best,
Ulle
--
Ulle Endriss
ILLC, University of Amsterdam
http://www.illc.uva.nl/~ulle/
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/
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/
