Monday, November 21, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
We study "Condorcet domains," that is, subdomains of preference orders
on which majority voting is acyclic. Prominent examples are the
single-peaked and the single-crossing domains. We provide novel and
simple "global" characterizations of both these domains. The
characterization of the single-crossing domains is based on a
fundamental correspondence between Condorcet domains and median graphs.
The characterization of the single-peaked domain uses a richness
property which requires that every alternative be the top element of
some preference order in the domain. Finally, we derive a structural
property of maximal Condorcet domains, namely that the (median) graphs
associated with them are either chains, or admit at least one 4-cycle
(i.e. trees different from chains can never occur under maximality).
Colloquium - 16:00
Abstract:
Consider an important meeting to be held in a team-based organization.
Taking availability constraints into account, an online scheduling poll
is used to decide upon the exact time of the meeting.
Decisions are to be taken during the meeting, therefore each team wants
to maximize its relative attendance in the meeting (that is, the
proportional number of its participating team members).
We introduce a corresponding game, where each team can declare (in the
scheduling poll) a lower total availability, in order to improve its
relative attendance---the pay-off. We are especially interested in
situations where teams can form coalitions:
1. We provide an efficient algorithm that, given a coalition, finds an
optimal way for each team in the coalition to improve its pay-off.
2. In contrast, we show that deciding whether a coalition with
improvement exists is NP-hard.
3. We also study the existence of Nash equilibria: Finding Nash
equilibria for various small sizes of teams and coalitions can be done
in polynomial time while it is coNP-hard if the coalition size is unbounded.
* This is a joint work with Robert Bredereck, Rolf Niedermeier,
Svetlana Obraztsova, and Nimrod Talmon.