Dominik Peters
Interests
[From July 2019, I have moved to Carnegie Mellon University to do a postdoc hosted by Ariel Procaccia.]
My interests lie in algorithmic game theory (studying strategic behaviour) and computational social choice (studying voting).
My recent research has focussed on restricted preference domains, such as the notion of single-peaked preferences. Here, I work on designing algorithms that can uncover underlying structure in the preferences of a group of agents -- once we understand these preferences better, we can then use this structure to more efficiently solve optimisation problems that would otherwise be computationally intractable. In particular, I have worked on multidimensional Euclidean preferences, preferences single-peaked on a tree or on a circle, and a short survey.
I am also interested in hedonic games, sometimes called coalition formation games, where a group of agents needs to be assigned into different teams or coalitions. One might think of these coalitions as friendship groups, and agents have preferences over which group they are part of: Some players might prefer large groups, others small groups. Some players might like each other, others hate each other. Our aim is to find some assignment to groups that is stable: no agent, or no group of agents, can profitably deviate from the way the groups are assigned. Can we write a computer program that finds such a stable outcome in a relatively short time? The answer is no, since this problem is NP-complete or even harder. But I try to find special cases where finding stable outcomes is easy after all. Examples of work in this area study cases of bounded treewidth, dichotomous preferences, or preferences obtained by lifting preferences over agents to preferences over groups of agents. I also enjoy proving hardness results for trickier complexity classes.
Some other interests lie in the theory of voting, and here I work on figuring out under what circumstances certain paradoxes (like the no-show paradox) arise, how to make complex group decisions with the help of a computer (for example using linear programming), and when people's preferences are nicely structured.
Biography
I did my DPhil (2015-19) at Balliol College supervised by Edith Elkind. Before that, I studied for a Master of Mathematics & Computer Science (2011-15) at St John's College, Oxford, where I focussed on Foundations of Mathematics and Probability. Originally, I am from Hamburg in Germany. Also see my personal website for more on me and my research.
Selected Publications
-
Optimal Bounds for the No−Show Paradox via SAT Solving
Felix Brandt‚ Christian Geist and Dominik Peters
In Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems‚ AAMAS 2016. Pages 314–322. 2016.
Details about Optimal Bounds for the No−Show Paradox via SAT Solving | BibTeX data for Optimal Bounds for the No−Show Paradox via SAT Solving | Download (pdf) of Optimal Bounds for the No−Show Paradox via SAT Solving
-
Preferences Single−Peaked on Nice Trees
Dominik Peters and Edith Elkind
In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence‚ AAAI 2016. Pages 594–600. 2016.
Details about Preferences Single−Peaked on Nice Trees | BibTeX data for Preferences Single−Peaked on Nice Trees | Download (pdf) of Preferences Single−Peaked on Nice Trees
-
Graphical Hedonic Games of Bounded Treewidth
Dominik Peters
In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence‚ AAAI 2016. Pages 586–593. 2016.
Details about Graphical Hedonic Games of Bounded Treewidth | BibTeX data for Graphical Hedonic Games of Bounded Treewidth | Download (pdf) of Graphical Hedonic Games of Bounded Treewidth