{"id":920,"date":"2009-10-28T10:26:26","date_gmt":"2009-10-28T14:26:26","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=920"},"modified":"2009-10-28T10:26:26","modified_gmt":"2009-10-28T14:26:26","slug":"algorithmic-voting-theory-venice-and-a-talk-on-oldnew-papers","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2009\/10\/28\/algorithmic-voting-theory-venice-and-a-talk-on-oldnew-papers\/","title":{"rendered":"Algorithmic Voting Theory, Venice, and a Talk on Old\/New Papers"},"content":{"rendered":"

I just got back from Venice, where I attended a conference on Algorithmic Decision Theory<\/a>.\u00a0 This is a new conference series (optimistically numbered the first conference, implying at least a second) revolving around issues in uncertainty in decision making, preference solicitation, learning and other issues.\u00a0 From the conference web page:<\/p>\n

A new unique event aiming to put together researchers and practitioners coming from different fields such as Decision Theory, Discrete Mathematics, Theoretical Computer Science and Artificial Intelligence in order to improve decision support in the presence of massive data bases, combinatorial structures, partial and\/or uncertain information and distributed, possibly inter-operating decision makers. Such problems arise in several real-world decision making problems such as humanitarian logistics, epidemiology, risk assessment and management, e-government, electronic commerce, and the implementation of recommender systems.<\/p><\/blockquote>\n

This area has been very active, particularly in computer science where there are\u00a0 a host of applications.<\/p>\n

I was asked to give one of the invited talks, and spoke on “An Operations Research Look at Voting”.\u00a0 I was a little worried about giving this talk, since my main qualifications come from papers published twenty years ago.\u00a0 When I was a doctoral student at Georgia Tech, I worked with John Bartholdi and Craig Tovey on computational issues in voting.\u00a0 Being the first to look at those issues, we got to prove some of the basic results in the area.\u00a0 These include<\/p>\n

    \n
  1. For some natural voting rules, it is NP-hard to determine who the winner is.<\/li>\n
  2. For some natural voting rules, it is NP-hard to determine how to manipulate the rule (where manipulation means misrepresenting your preferences so as to get a preferred outcome).<\/li>\n
  3. For some natural voting rules, optimally using the powers of a chair to form subcommittees or otherwise manipulate the voting process is NP-hard.<\/li>\n<\/ol>\n

    We published this work in Social Choice and Welfare<\/em> (after getting it rejected from more mainstream economics journals) where … it was soundly ignored for 15 years.\u00a0 No one referred to the papers; no one followed up on the papers;\u00a0 no one cared about the papers at all!<\/p>\n

    This work was my job talk in 1987\/88, and it got me a wonderful job here at the Tepper School (then GSIA), Carnegie Mellon.\u00a0 And, without Google Scholar, it was not obvious that the papers were being ignored, so they added to my vita, and made it a bit easier to pass through the various steps.<\/p>\n

    But I did like the work a lot, and regretted (and still regret) that my economist colleagues did not take computational limits more seriously in their models.<\/p>\n

    \"votingcites\"But then something amazing happened about 5 years ago:\u00a0 people started referring to the papers!\u00a0 The references were mainly in computer science, but at least the papers were being recognized. The counts of these papers in the Web of Science<\/a> (formerly Science Citation Index) are particularly striking.\u00a0 In the associated graph, the x-axis is years since publication;\u00a0 the y-axis is the number of references in Web of Science in that year (Google scholar numbers are higher of course, but there is a bias towards more recent papers there).\u00a0 In my talk, I compare that graph to my “normal” papers, which reach a peak after 4 or 5 years then decrease. \u00a0 It is really gratifying to see the interest in these papers along with all the really cool new results people are getting.<\/p>\n

    I closed off the talk with some work I have done recently on creating voting trees.\u00a0 Suppose there are three candidates, “a”, “b”, and “c”, and you really like candidate “a”.\u00a0 Many voting systems proceed as a series of comparisons between two alternatives (think of standard parliamentary procedure).\u00a0 If you are the chairperson, you might try to bring the candidates forward so as to increase the chances of “a” winning.\u00a0 In fact, if you set the agenda to be “b” against “c” and the winner against “a”, then “a” will win as long as “a” beats someone<\/em> (and no one beats everyone).\u00a0 In this problem, the goal is to do the manipulation without knowing other voters’ preferences.<\/p>\n

    \"lextree4\"Can you do this for four candidates?\u00a0 If you want “a” to win, “a” must be in the top cycle: the group of candidates (perhaps the entire set of candidates) who all beat all the other candidates.\u00a0 The “Condorcet winner” is the minimal top cycle:\u00a0 if some candidate beats all the other candidates one-on-one, then that candidate must win any voting tree it occurs in.\u00a0 So, assuming “a” is in the top cycle, can you create a voting\u00a0 tree so that “a” wins with four candidates?\u00a0 The answer is yes, but it is a bit complicated:\u00a0 first “a” goes against “c” with the winner against “d” then the winner against “b” who plays the winner of (“a” goes against “b” with the winner against “d” …) ….\u00a0 actually, the minimum tree has 14 leaves!\u00a0 I am biased, but I think the tree is beautiful, but it goes to show how hard it is to manipulate agendas without knowledge of others’ preferences.\u00a0 I am in the process of generating the trees on 4 candidates:\u00a0 there is a very natural rule (“Copeland winner with Copeland loser tie break”:\u00a0 see the presentation for definitions) that requires more than 32 leaves (if an implementation tree for it exists).<\/p>\n

    Sanjay Srivastava and I made a conjecture almost 15 years ago that would imply that this sort of manipulation would be possible no matter how many candidates.\u00a0 Little progress has been made but I think it is still a great problem (the economists know this as implementation by backwards induction and characterizing rules implementable on trees is an important problem in social choice\/mechanism design).<\/p>\n

    If you want more details on all this, here are my slides<\/a>.\u00a0 The references are<\/p>\n