Phokion G. Kolaitis

(University of California Santa Cruz and IBM Research)
hosted by Distinguished Lecture Series, the Max Planck Institute for Software Systems

"Computational Social Choice and Incomplete Information"

( MPI-SWS talk in Kooperation mit dem Fachbereich Informatik)

Computational social choice is an interdisciplinary field that studies collective decision making from an algorithmic perspective. Determining the winners under various voting rules is a mainstream area of research in computational social choice. Many such rules assume that the voters provide complete information about their preferences, an assumption that is often unrealistic because typically only partial preference information is available. This state of affairs has motivated the study of the notions of the necessary winners and the possible winners with respect to a variety of voting rules.
The main aim of this talk is to present an overview of winner determination under incomplete information and to highlight some recent advances in this area, including the development of a framework that aims to create bridges between computational social choice and data management. This framework infuses relational database context into social choice and allows for the formulation of sophisticated queries about voting rules, candidates, winners, issues, and positions on issues. We will introduce the necessary answer semantics and the possible answer semantics to queries and will explore the computational complexity of query evaluation under these semantics.

Bio: Phokion Kolaitis is a Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity.
Kolaitis is a Fellow of the American Association for the Advancement of Science (AAAS), a Fellow of the Association for Computing Machinery (ACM), a Foreign Member of the Finnish Academy of Science and Letters, a Foreign Member of Academia Europaea, and the recipient of a 1993 Guggenheim Fellowship. He is also the recipient of two IBM Research Division Outstanding Innovation Awards, an IBM Research Division Outstanding Technical Achievement Award, a co-winner of both the 2008 and the 2014 ACM PODS Alberto O. Mendelzon Test-of-Time Award, a co-winner of the 2013 International Conference on Database Theory Test-of-Time Award, and a co-winner of the 2020 Alonzo Church Award for Outstanding Contributions to Logic and Computation. In 2014, Kolaitis was awarded an Honorary Doctorate Degree (Doctor Honoris Causa) from the National and Kapodistrian University of Athens, Greece.

Time:	Wednesday, 28.04.2021, 16:00
Place:
Video:

Termin als Datei downloaden und in den Kalender importieren.