Counting votes, in the precinct and on the Web

Postdoctoral researcher Lirong Xia uses computational science and insights from election theory to improve ranking systems and preference aggregation across the Web. (Photo by Eliza Grinnell, SEAS Communications.)

Though voters may have tired of the U.S. election season well before November 6, there’s some solace to be found in the fact that the voting itself typically lasts only a day.

One particular kind of voter, however—the computational scientist—might advocate an even lengthier election period, perhaps entailing a single ballot question each day, with voting drawn out over a week or two, or maybe more. Unwelcome though the idea may be to the mind of the weary voter, the theory supports it, if not the practice.

“You can’t say, ‘Today you’ll come in and vote on the first issue, and then we’ll announce the result, and tomorrow you’ll come back again and vote on the second issue.’ That’s too costly,” admits Lirong Xia, a postdoctoral researcher at the Center for Research on Computation and Society at the Harvard School of Engineering and Applied Sciences (SEAS). “But if you can build an online voting system and make it secure enough, then people can stay at home and just log in at the right time. It would reach a better solution and reduce the cost of holding elections.”

Xia is certainly not the first to suggest a sequential approach to elections, but he is a pioneer in the emerging field of computational election theory, which could help to make online voting, and new types of election rules, a reality. A computer scientist whose research intersects with economics and game theory, political science, artificial intelligence, and e-commerce, Xia is among a growing cadre of scholars who recognize that modern computational techniques are changing the ways we can think about the aggregation of human preferences.

To Xia and his colleagues, an 'election' could mean the selection of a president and vice president, or it could mean the rating of an online product listing—four stars or five? To researchers in artificial intelligence (AI), a national election is just another example of a multi-agent system, in which players with different information and objectives all contribute to one outcome. Across these many varied systems, the basic principles are the same.

And, according to Xia, they all stand to benefit from new theories and techniques in computational science.

Consider, for example, a fictional town whose residents must choose whether to fund the construction of a new school, a playground, or a community center. On the ballot, they’re asked to weigh in on each option with a simple yes or no, and a majority vote wins. A parent in the town might prioritize the school, and only support the playground if the school is also built—but the ballot makes no provision for an "if-then" type of choice. With three interrelated ballot questions, the number of possible results and strategies is high enough that the town could end up with an undesirable outcome, such as a bad combination of options, or perhaps none at all.

Xia's point is that sometimes, without the language to express conditional preferences, the whole election system can suffer.

"If you have too many alternatives, it's very hard for voters to express their full preferences," he says. "In an online context or in artificial intelligence, if you're talking about a thousand alternatives, the voters won't even know their full preferences."

The plight of the third-party voter represents another problem that is created by the choice of one election rule over another. In the U.S. presidential election, candidates win by plurality state by state, with a winner-takes-all approach to the electoral college. Rather than voting for a preferred third-party candidate who has little chance of success, therefore, many voters will vote for their second choice, simply to prevent their least-favorite candidate(s) from winning. This type of strategic behavior might achieve a short-term compromise, but it also undermines the candidate who best represents those voters' interests—so the system is self-perpetuating and less than ideal.

“The math and strategic behavior with those decision rules tends to support, in equilibrium, a two-party system," explains David King, Senior Lecturer in Public Policy at Harvard Kennedy School.

Xia suggests that if voters were able to express their first choice, second choice, and so on, right on the ballot, the winner would be more difficult to calculate, but outcome might be more satisfactory.

King agrees, though with some reservation: “There are several techniques that would more accurately translate preference orders into election outcomes, [but] our current system is largely baked into how we’re likely to run elections for many years to come.”

If it were practical, online voting would present an opportunity for election experts to change the rules of the game. But there are several important reasons electronic voting, and specifically online voting, have not yet caught on nationally, according to David Parkes, Harvard College Professor and George F. Colony Professor of Computer Science at SEAS, who co-advises Xia (with Yiling Chen).

“It is absolutely critical to ensure trust and privacy in electoral processes,” says Parkes. “This is an active area of cryptographic research. We need to verify that all votes are counted correctly without revealing the vote of any individual.

“But I think we should also recognize that enabling nationwide online voting would have huge political implications, driving a significant increase in voter turnout and shifting the demographic of the electorate,” Parkes notes. “This would be a big game changer and perhaps cause unease in some political circles.”

Politics aside, the security and secrecy of election data is an ongoing and serious challenge for computer security researchers, such as Ronald Rivest at MIT, a cryptographer who has been studying this problem for years and who offers a voice of caution.

Xia, here at Harvard, believes that solving the issues on the voting side, such as strategy and fraud, is equality important to the success of future election systems, whether digital or analog. A portion of Xia's work involves the use of computational complexity theory to discourage behavior that would undermine the integrity of the election.

“The idea is very much like Dr. Rivest's work in cryptography,” explains Xia. “If you have infinite computational power, then you can crack pretty much every system—but you don’t.”

Therefore, if Xia and his colleagues can determine the threshold at which a manipulation becomes quantifiably "hard" to achieve, they believe they can guarantee the safety of the election.

In the meantime, new computational techniques can combat fraud in a different way. Even in a world of paper ballots, some election fraud is considered normal, and as Xia points out, different states have different thresholds at which they’ll take action. Rather than trying to prevent fraud entirely, the key is really to recognize emerging problems more quickly.

“I’m trying to design a faster way to detect fraud with high statistical confidence,” says Xia. “We don’t know how to fix it, and many people in security are working on that, but maybe, at least, we can detect a fraud faster and then decide what to do next.”

But a robust, secure, and secret online voting system may not be too far away—and it would certainly change the game. From a computational perspective, says Parkes, “It would be astounding. Assuming that the user interface challenges could be addressed, voting online from home would allow voting processes that take a little longer but better reflect the will of the electorate.”

The analysis of election rules is not a new area of research; Nobel laureate Kenneth Arrow laid the foundations for the field in 1951, with his book Social Choice and Individual Values. Arrow’s “impossibility theorem,” as it is known, demonstrates that no electoral system can possibly satisfy all of five fairly basic criteria, so even the most clever election rules can only offer, at best, a compromise. Assessing a range of possible voting rules therefore requires an analysis of constraints and competing objectives—a task extremely well suited to the strengths of computational science.

In some cases, the computational complexity of the system might even be a constraint in itself, if it improves the election's integrity but slows the entire process down.

"With a presidential election you can afford to wait a day or two, or even a week, to find out the winner, as long as it's correct in the end," says Xia. "But for some types of applications, such as online polls, restaurant ratings, or movie rankings, the time between when you close the 'election' and when you announce the winner has a different sensitivity. For those applications it's critical to use a voting rule where computing the winner is faster, as opposed to voting rules that might be better in other aspects."

The correct system to use really depends on the objective.

"The goals of the [U.S.] election system are many," says Stephen Ansolabehere, Professor of Government at Harvard. "If I were to choose the two most important they would be (1) to produce a democratically chosen leader and set of representatives and (2) to have a democratic process that the nation as a whole recognizes as producing legitimate outcomes and that leads to peaceful transitions of government."

Or, as Xia puts it, "You want people to be happy. But in these low-stakes, online applications, you really want to figure out what is the truth."

In e-commerce and AI, at least, researchers still have the opportunity to design the system from scratch.