Toby Walsh is a professor of artificial intelligence at NICTA and the University of New South Wales. He has served as Scientific Director of NICTA, Australia’s centre of excellence for ICT research. He has also held research positions in England, Scotland, Ireland, France, Italy, Sweden and Australia. He has been Editor-in-Chief of the Journal of Artificial Intelligence Research, and of AI Communications. He is Editor of the Handbook of Constraint Programming, and of the Handbook of Satisfiability.
Luke Muehlhauser: In Rossi et al. (2011), you and your co-authors quickly survey a variety of methods in computational social choice, including methods for preference aggregation, e.g. voting rules. In Narodytska et al. (2012), you and your co-authors examine the issue of combining voting rules to perform a run-off between the different winners of each voting rule. What do you think are some plausible practical applications of this work — either soon or after further theoretical development?
Toby Walsh: As humans, we’re all used to voting: voting for our politicians, or voting for where to go out. In the near future, we’ll hand over some of that responsibility to computational agents that will help organize our lives. Think Siri on steroids. In such situations, we often have many choices as there can be a combinatorial number of options. This means we need to consider computational questions: How do we get computer(s) to work with such rich decision spaces? How do we efficiently collect and represent users’ preferences?
I should note that computer systems are already voting. The SCATS system for controlling traffic lights has the controllers of different intersections vote for what should be the common cycle time for the lights. Similarly, the Space Shuttle had 5 control computers which voted on whose actions to follow.
Computational social choice is, however, more than just voting. It covers many other uses of preferences. Preferences are used to allocate scarce resources. I prefer, for example, a viewing slot on this expensive telescope when the moon is high from the horizon. Preferences are also used to allocate people to positions. I prefer, for example, to be matched to a hospital with a good pediatrics depts. Lloyd Shapley won the Nobel Prize in Economics recently for looking at such allocation problems. There are many appealing applications in areas like kidney transplant, and school choice.
One interesting thing we’ve learnt from machine learning is that you often make better decisions when you combine the opinions of several methods. It’s therefore likely that we’ll get better results by combining together voting methods. For this reason, we’ve been looking at how voting rules combine together.
Luke: Which methods from social computational choice might be relevant to a situation like the following, adapted from Bostrom (2009)?
Suppose you want to learn agent A’s preferences, and suppose that you begin with a set of mutually exclusive preference orderings, and that you assign each of these some probability of representing A’s preferences. Now imagine that each of these preference orderings gets to send some number of delegates to Parliament. The number of delegates each preference ordering gets to send is proportional to the probability of that preference ordering. Then the delegates bargain with one another for support on various issues; and the Parliament reaches a decision by the delegates voting.
Toby: In computational social choice, we’d be interested in computational aspects of such voting situations. The first problem in this setting is that the number of preference orderings is exponential. So, is the number of delegates also exponential which will make it computationally difficult to deal with such a large number of delegates? Or is it polynomial in which case, we need to consider which polynomial subset and how “representative” this is of the whole? Having solved such problems, we’ll then consider computational questions like how do the delegates compute their (possibly strategic) votes. We know from fundamental axiomatic results in social choice that any reasonable voting system is likely to be manipulable and subject to strategic voting.
Luke: In some of your work (e.g. 2011a, 2011b), you explore the computational complexity of manipulation. Are there cases where an agent can efficiently engage in truthful voting, but can’t efficiently engage in various forms of manipulation, including strategic voting?
Toby: Well, hopefully an agent can always efficiently engage in truthful voting as we want participation. But surprisingly, even this can be sometime challenging. A nice example goes back to the Victorian mathematician and writer Charles Dodgson, or to go by his more familiar pen name, Lewis Carroll. He proposed an interesting voting rule, known as Dodgson’s method which elects any candidate that is preferred by a majority of voters to any other candidate when such a candidate exists. When such a candidate does not exist (for instance, when votes are split three ways), it elects the closest candidate in the sense that we have to make the fewest number of pairwise swaps in the votes to get to a candidate that is preferred by a majority. It’s worth noting that many popular rules, even plurality voting, do not necessarily elect a candidate that is pairwise preferred to all others by a majority when such a candidate exists. Anyway, back to Dodgson’s rule. Somewhat to the surprise of many, even working out who wins an election run under Dodgson’s rule is computationally intractable in the worst case (formally, it is NP-hard).
Fortunately, most voting rules are easy to compute, typically even linear time. On the other hand, there are many deep impossibility results showing that voters may profit from strategic voting and mis-reporting their preferences. An interesting escape from this problem was put forwards by Bartholdi, Tovey and Trick. Perhaps strategic voting is possible but too computationally difficult to actually work out?
Since they, I and others have explored which voting rules have this property. For example, we recently settled a long standing open question that Borda voting (which many people will have seen as a variant of Borda voting is used in the Eurovision song contest) is computationally difficult to manipulate. These are worst case results so we’ve also looked at how difficult strategic voting is to compute in practice (not just in the worst case).
Luke: What are some of the most interesting questions in computational social choice that you think have a decent chance of being essentially resolved in the next 20 years?
Toby: We’ll definitely have a good idea of the computational properties of the many different voting rules proposed throughout history, from ancient ones like Borda to recent ones like Schulz’e rule. And we’ll understand the computational resistance of these rules to manipulation not just in the worst case but in average and in practice on real world elections. More practically, we’ll also have a good understanding of computational aspects of other problems in social choice like fair division. For instance, we’ll have developed a rich range of mechanisms for fair division that cover the spectrum of cases (divisible/indivisible goods, centralized/decentralized, etc) and for which we understand their properties (fairness, efficiency, etc) and agents behaviour (e.g. how agents can compute a best response, Nash dynamics, etc).
Luke: Thanks, Toby!
Did you like this post? You may enjoy our other Conversations posts, including:
