Lirong Xia made a decision: he would study mathematics in college, for which he had a natural affinity. But his father had other ideas. Mr. Xia brought a computer scientist home to meet his son, and both urged the young man to try computing instead. “At the time, I didn’t know which was better, but I decided to follow their advice,” says Xia, now a CS PhD candidate at Duke. He remains pleased with his decision, “but I still prefer theoretical problems to programming,” he laughs.
Xia completed his undergraduate degree in CS at Tsinghua University, the MIT of China, and stayed on for graduate work until 2007. But he first set his sights on Duke in 2006. One day while browsing through conference papers, Xia came across a study on voting theory by the Department’s own Vincent Conitzer. Voting theory, the design and analysis of rules applied to group decisions, appealed to Xia’s interests in both CS and math. “I realized I could apply a lot of mathematics to voting problems,” he recalls.
Xia received a James B. Duke fellowship to attend Duke, a competitive campus-wide merit scholarship, and joined Conitzer’s lab in the fall of 2007. Once on campus, Xia decided to study computational social choice, the computational aspects of voting when overwhelming amounts of information are involved. “He’s very independent, driven, and motivated,” says Conitzer. “We’re very lucky to have him here.”
Xia’s research spans two major topics: manipulation of voting systems and multiissue domains. During any type of voting, participants may try and manipulate the system, lying about their real preferences in the hopes of strategically altering the result. Xia studies how to prevent such manipulation by adding computational complexity to voting rules, so even if it is possible to manipulate a system, it will be impossibly difficult (NP hard) to do so. For most CS researchers, unsolvable problems are bad news. For Xia, they are the ideal solution.
In a second line of research, Xia studies voting in multi-issue situations, in which parties make a variety of decisions, each conditional on the one before it. For example, if a group of people are going out for dinner, a person’s vote for a restaurant may change depending on the day and time the group chooses to eat. With many choices, multi-issue voting rapidly becomes computationally complex. Xia is working to find solutions that speed up the process, hoping that an efficient system for multiissue voting will make the procedure more useful in real life situations.
This year, Xia co-authored an unprecedented five papers at the prestigious 21st International Joint Conference on Artificial Intelligence (IJCAI-09). “He’s had an extremely successful year,” says Conitzer. Xia, who is also pursuing a Master’s degree in economics, attributes that success to Department support, especially from his advisor. “Vince gives me a lot of freedom to develop my research,” says Xia. “I owe him thanks for his help and support.”