The ACM Special Interest Group on Electronic Commerce (ACM SIGecom) has presented Georgia Tech professors John Bartholdi and Craig Tovey with the Test of Time Award for two different papers. Bartholdi is Manhattan Associates/Dabbiere Chair in the Stewart School of Industrial & Systems Engineering (ISyE), and Tovey is a professor and Stewart Faculty Fellow in ISyE.

The Test of Time Award recognizes “papers published between 10 and 25 years ago that have had significant impact on research or applications that exemplify the interplay of economics and computation,” said David Pennock, on behalf of the award committee. The two winning papers, selected by unanimous vote of the award committee, have influenced “a thriving subfield of computational social choice. In many ways, these papers catalyzed an entire field.”

The first winning paper, written by Bartholdi and MIT Sloan School of Management Professor James Orlin, is “Single Transferable Vote Resists Strategic Voting,” which appeared in the journal Social Choice in 1991.

The second winning paper, written by Bartholdi, Tovey, and then-ISyE graduate student Michael Trick (M.S. OR 1984, Ph.D. IE 1987) is “How Hard Is It to Control an Election?”, which appeared in the journal Mathematical and Computer Modelling in 1992.

Tovey and Trick (now associate dean of research and a professor of operations research at Carnegie Mellon University) will travel in July to the 2016 ACM Conference on Economics and Computation in the Netherlands to accept the award and give a presentation on the work.

About the Award-winning Papers

These two papers helped start the now-flourishing field of computational social choice, a blend of voting theory from economics with complexity and algorithmic analysis from operations research and computer science.

“Single Transferable Vote Resists Strategic Voting” discusses how a “strategic vote” is a vote cast to tilt an election by voting other than one’s true preferences. This is troubling because it seems contrary to the purpose of voting, which is to elicit the true opinion of the electorate. The Gibbard-Satterthwaite-Gärdenfors theorems famously proved that every minimally fair voting system is susceptible to manipulation by strategic voting. Bartholdi and Orlin proved that the system of voting known as “single transferrable vote” (STV) is resistant to manipulation, even though susceptible in theory. That is, when votes are to be tabulated by STV, it can be computationally difficult – and therefore impractical – to devise a strategic vote that will advance one’s true objectives. Furthermore, STV seems to be unique in this regard among voting schemes in common use.

In “How Hard Is It to Control an Election?”, Bartholdi, Tovey, and Trick proposed the search for voting systems that are computationally resistant to attacks by the addition or disqualification of candidates or voters.  They proved that of two popular systems, one is resistant to attacks on voters, and the other is resistant to attacks on candidates. 

About John Bartholdi

Bartholdi, as well as being an ISyE professor, serves as Co-Executive Director of the Georgia Tech - Panama Logistics Innovation and Research Center. He teaches supply chain issues, primarily warehousing, at both the undergraduate and graduate levels and in SCL's professional education program. His research centers on problems in warehousing and distribution, but he reserves some time to pursue wider-ranging interests, including mechanics, politics, computer science, geography, biology, and, more recently, public transit (he is the co-creator of the software that coordinates buses on the Georgia Tech campus).

He was named a Presidential Young Investigator by the National Science Foundation (NSF) for 1984-1989 and received the IIE Innovation Award in 1999. His research has been supported by the Defense Logistics Agency, the Office of Naval Research, and the Air Force Office of Scientific Research, among others.

Bartholdi graduated in 1968 with a B.S. degree in mathematics from the University of Florida and then served two tours of duty in Southeast Asia as a paratrooper in a Naval Special Warfare unit. He returned to the University of Florida to complete the Ph.D. program in operations research in 1977 and later served on the faculties at the University of Michigan, the Shanghai Institute of Mechanical Engineering, the National University of Singapore, and Stellenbosch University.

About Craig Tovey

In addition to serving as an ISyE professor, Tovey also co-directs CBID, the Georgia Tech Center for Biologically Inspired Design.

His principal research and teaching activities are in operations research and its interdisciplinary applications to social and natural systems, with emphasis on sustainability, the environment, and energy. His current research concerns inverse optimization for electric grid management, classical and biomimetic algorithms for robots and webhosting, the behavior of animal groups, sustainability measurement, and political polarization.

Tovey received a Presidential Young Investigator Award from the NSF in 1985 and the 1989 Jacob Wolfowitz Prize for research in heuristics. He was granted a Senior Research Associateship from the National Research Council in 1990, was named an Institute Fellow at Georgia Tech in 1994, and received the Class of 1934 Outstanding Interdisciplinary Activity Award in 2011.

He received an A.B. in applied mathematics from Harvard College in 1977 and both an M.S. in computer science and a Ph.D. in operations research from Stanford University in 1981.