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/
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/
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/
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/
