A UNSW computer scientist who solved a long-standing computational problem relating to the way software agents make voting selections has cracked a prestigious list of up-and-coming artificial intelligence (AI) researchers.
Dr Nina Narodytska, an adjunct researcher from UNSW and NICTA, is the first Australian to be featured on AI’s 10 to Watch – a list of top early career researchers compiled by the Institute of Electrical and Electronics Engineers (IEEE).
Narodytska, who undertook PhD and postdoctoral study at UNSW before moving to the University of Toronto in Canada in May, has been investigating optimisation theory for things like transport networks, personnel rostering and logistical management of supplychains.
She has also been exploring ways that AI can be used for resource allocation and other problems in the areas of social welfare. This is a rapidly evolving field that lies at the boundary between computer science and economics.
“One famous application of the theory is the kidney exchange problem where a transplant donor and a transplant recipient are paired. Some of these pairs are incompatible, so the goal is to compose a new set of compatible pairings in the most socially fair way,” says Narodytska.
In examining the problem of how to divide limited resources amongst agents that have preferences over those resources, Narodytska and her colleagues proved the best method is to let those agents alternate picking items in turn.
It’s one of the oldest and most well known methods of sharing employed by humans, and as it turns out, it’s also computationally efficient, she says. “It’s a mechanism used in school playgrounds all over the world and for the first time we’ve provided justification for its use.”
At a leading AI conference in 2011 hosted by the Association for the Advancement of Artificial Intelligence, Narodytska also won best paper for solving an ongoing problem relating to the way software agents vote.
In computing, voting is an important way to aggregate preferences of different agents with competing priorities to determine a consensus action.
For example, agents that control different traffic lights along a major roadway vote to determine the length of green light cycles. Each agent wants to optimise traffic at its respective intersection, but must ultimately vote on an action that will lead to the best outcome for the entire roadway.
And just like humans, who don’t always vote according to their true preference (e.g. a Greens supporter who votes Labor to prevent a Liberal candidate from winning office) software agents also vote strategically.
It was held that successive elimination of candidates (or voting options) made this strategising more difficult. Narodytska, however, helped prove that “elimination style voting” doesn’t necessarily increase the computational complexity of agents’ rule manipulation. In other words, agents are just as likely to vote strategically regardless of the options available to them.
This work was done while she was a researcher at the Algorithmic Decision Theory group at NICTA and UNSW.
“She asked me for an unsolved problem,” recalls Professor Toby Walsh, her PhD supervisor and the group Director. “I pointed her toward this one and I didn’t expect her to be able to solve it. I was quite pleased and amazed… She proved there’s no point in searching for a more exotic, efficient algorithm.”
The AI 10 to Watch list is published by IEEE Intelligent Systems – the artificial intelligence publication of IEEE. It has been publishing the list every two years since 2006. View the full list.