Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Clemens Puppe - Karlsruher Institut für Technologie

Towards a Classification of Condorcet Domains

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

Jiehua Chen - TU Berlin

Teams in Online Scheduling Polls: Game-Theoretic Aspects

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.

Letzte Aktualisierung: 15.11.2016