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.