Skip to main content

Detecting structure in voters' preferences

Supervisors

Suitable for

MSc in Computer Science
Mathematics and Computer Science, Part C
Computer Science and Philosophy, Part C
Computer Science, Part C

Abstract

A large international community of researchers is trying to use computers to allow groups of people (or groups of automated agents) make better joint decisions. This is a hard problem, since the preferences that agents report might contradict each other, and this leads to so-called voting paradoxes. Also, it can be computationally hard to calculate what decisions to make.

A promising way to tackle this problem is by exploiting structure in the reported preferences. For this purpose, Australian researchers have collected an impressive amount of real-world preference data (PrefLib http://www.preflib.org/) comprising over 3,000 data sets coming from user preferences taken from places as diverse as rating systems at Netflix and TripAdvisor, and real political election data, with the aim of figuring out how we might use properties of preferences that actually occur in the real world.

This project is about analysing this data to reveal how much structure is contained in these preferences. Technically, we are interested in figuring out how close the preferences reported are to what are known as single-peaked and/or single-crossing preferences (see, e.g., https://en.wikipedia.org/wiki/Single_peaked_preferences). There are different measures of closeness, and for many of them the associated decision problem is NP-hard; for others, the computational complexity is not known.

Prerequisites: There are several ways in which this project can be pursued. On the one hand, one can consider the notions of closeness for which the complexity of the associated problem is not known, and try to develop an efficient algorithm or prove NP-hardness. On the other hand, one can try to develop practical algorithms for detecting profiles that are almost single-peaked/single-crossing, by encoding the associated problem as an instance of SAT or an integer linear program and running a respective solver; such algorithms could then be applied to PrefLib data.