E-mail:  or

Lirong Xia Postdoc at Center for Research on Computation and Society (CRCS), Harvard University, Cambridge, MA, USA. Supported by the Computing Innovation Fellows Program. Host: Prof. David C. Parkes. Also working with Prof. Yiling Chen. Office: MD 110B CRCS, 33 Oxford Street, Cambridge, MA 02138, USA 2007-2011 Ph.D. in CS, Duke university, Durham, NC, USA, under the supervision of Prof. Vincent Conitzer 2007-2010 M.A. in Econ, Duke university, Durham, NC, USA 2000-2004 B.E. in CS, Tsinghua university, Beijing, China My Curriculum Vitae as of Feb. 3, 2012

News: I will give an EC-12 tutorial on Computational Social Choice on Friday June 8, 9:30-1:00 pm. This year EC will be collocated with AAMAS in Valencia, Spain. No background is needed beyond graduate knowledge of computer science, including computational complexity and basic probability theory. The collocation benefit does NOT cover workshops, please register here (early registration by May 15).

Research Interests

• Artificial intelligence, multi-agent systems, decision-making under uncertainty, algorithm design, social choice (voting) theory, game theory, mechanism design, prediction markets.

Publications

Working papers

• By (α-β) Jerome Lang, Jerome Mengin, and Lirong Xia. Aggregating Conditionally Lexicographic Preferences on Multi-Issue Domains.
• By (α-β) David M. Pennock and Lirong Xia. Two New Measurements of Voting Power.
• Lirong Xia. Generalized Weighted Model Counting: An Efficient Monte-Carlo Meta-Algorithm.
• Lirong Xia. How Many Vote Operations Are Needed to Manipulate A Voting System?

2012

• By (α-β) Nina Narodytska, Toby Walsh, and Lirong Xia. Combining Voting Rules Together. In Proceedings of the Twentieth European Conference on Artificial Intelligence (ECAI-12), Montpellier, France.
• By (α-β) Dorothea Baumeister, Magnus Roos, Joerg Rothe, Lena Schend, and Lirong Xia. The Possible Winner Problem with Uncertain Weight. In Proceedings of the Twentieth European Conference on Artificial Intelligence (ECAI-12), Montpellier, France.
• By (α-β) David C. Parkes and Lirong Xia. A Complexity-of-Strategic-Behavior Comparison between Schulze's Rule and Ranked Pairs. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12), Toronto, Canada.
• By (contribution) Bo Waggoner, Lirong Xia, and Vincent Conitzer. Evaluating Resistance to False-Name Manipulations in Elections. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12), Toronto, Canada.
• Lirong Xia. Computing the Margin of Victory for Various Voting Rules. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC-12),Valencia, Spain.
• By (α-β) Vincent Conitzer and Lirong Xia. Paradoxes of Multiple Elections: An Approximation Approach. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR-12), Rome, Italy.
• By (α-β) Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh, and Lirong Xia. Complexity of and Algorithms for the Manipulation of Borda, Nanson and Baldwin's Voting Rules. Accepted to Artificial Intelligence subject to minor changes. Supercedes the AAAI-11 paper below and another AAAI-11 paper by Jessica Davies, George Katsirelos, Nina Narodytska, and Toby Walsh.
• By (α-β) Toby Walsh and Lirong Xia. Lot-based Voting Rules. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-12),Valencia, Spain.
• By (α-β) Yann Chevaleyre, Jerome Lang, Nicolas Maudet, Jerome Monnot, and Lirong Xia. New Candidates Welcome! Possible Winners with respect to the Addition of New Candidates. To appear in Mathematical Social Sciences.

2011

• Lirong Xia. Computational Voting Theory: Game-Theoretic and Combinatorial Aspects. Ph.D. Dissertation. Computer Science Department, Duke University, Durham, NC, August 2011. Duke CS Outstanding Ph.D. Dissertation Award. Abstract, acknowledgements, contents. Chapter 1: Introduction. Chapter 2: Preliminaries. Chapter 3: Introduction to Game-theoretic Aspects of Voting. Chapter 4: Computational Complexity of Unweighted Coalitional Manipulation. Chapter 5: Computing Manipulations is “Usually” Easy. Chapter 6: Preventing Manipulation by Restricting Information. Chapter 7: Stackelberg Voting Games. Chapter 8: Introduction to Combinatorial Voting. Chapter 9: A Framework for Aggregating CP-Nets. Chapter 10: A Maximum-Likelihood Approach. Chapter 11: Strategic Sequential Voting. Chapter 12: Strategy-Proof Voting Rules over Restricted Domains. Chapter 13: Conclusion and Future Directions. Bibliography. Bioraphy.
• By (α-β) David M. Pennock and Lirong Xia. Price Updating in Combinatorial Prediction Markets with Bayesian Networks. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI -11), pp. 581-588, Barcelona, Catalonia, Spain, 2011.
• By (α-β) Vincent Conitzer, Toby Walsh, and Lirong Xia. Dominating Manipulations in Voting with Partial Information. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11), pp. 638-643, San Francisco, California, USA. [proofs]
• By (α-β) Nina Narodytska, Toby Walsh, and Lirong Xia. Manipulation of Nanson's and Baldwin's rule. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11), pp. 713-718, San Francisco, California, USA.
• By (α-β) Vincent Conitzer, Jerome Lang, and Lirong Xia. Hypercubewise Preference Aggregation in Multi-issue Domains. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), pp. 158-163, Barcelona, Catalonia, Spain, 2011.
• By (contribution) Lirong Xia and David M. Pennock. An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), pp. 452-457, Barcelona, Catalonia, Spain, 2011. [preliminary long version]
• By (contribution) Lirong Xia and Vincent Conitzer. A Maximum Likelihood Approach towards Aggregating Partial Orders. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), pp. 446-451, Barcelona, Catalonia, Spain, 2011.
• By (contribution) Lirong Xia, Vincent Conitzer, and Jerome Lang. Strategic Sequential Voting in Multi-Issue Domains and Multiple-Election Paradoxes. In Proceedings of the 12th ACM Conference on Electronic Commerce (EC-11), pp. 179-188, San Jose, CA, USA, 2011.
• By (contribution) Lirong Xia, Jerome Lang and Jerome Monnot. Possible Winners When New Alternatives Join: New Results Coming Up! In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-11), pp. 829-836, Taipei, Taiwan, 2011.
• By (contribution) Lirong Xia and Vincent Conitzer. Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders. Journal of Artificial Intelligence Research (JAIR) 41:25-67, 2011. This is the extended version of the paper under the same title published in AAAI-08.

2010

• By (contribution) Lirong Xia and Vincent Conitzer. Strategy-proof Voting Rules over Multi-issue Domains with Restricted Preferences. In Proceedings of the Sixth Workshop on Internet and Network Economics (WINE-10), pp. 402-414, Stanford, CA, USA, 2010. [long version]
• Lirong Xia. Computational Social Choice: Strategic and Combinatorial Aspects. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10) (Doctoral Consortium), pp. 2000-2001 (the last two pages...), Atlanta, GA, USA, 2010.
• By (contribution) Lirong Xia and Vincent Conitzer. Stackelberg Voting Games: Computational Aspects and Paradoxes. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), pp. 921-926, Atlanta, GA, USA, 2010.
• By (contribution) Lirong Xia and Vincent Conitzer. Compilation Complexity of Common Voting Rules. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), pp. 915-920, Atlanta, GA, USA, 2010.[preliminary long version] There is a typo for Bucklin in the AAAI version. Fixed in the long version. Thanks ILan Frank for pointing it out!
• By (contribution) Lirong Xia, Vincent Conitzer, and Ariel D. Procaccia. A Scheduling Approach to Coalitional Manipulation. In Proceedings of the 11th ACM Conference on Electronic Commerce (EC-10), pp. 275-284, Cambridge, MA, USA, 2010.
• By (contribution) Lirong Xia, Vincent Conitzer, and Jerome Lang. Aggregating Preferences in Multi-Issue Domains by Using Maximum Likelihood Estimators. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-10), pp. 399-408, Toronto, ON, Canada, 2010.
• By (α-β) Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia. Incentive Compatible Budget Elicitation in Multi-unit Auctions. In Proceedings of ACM/SIAM Symposium on Discrete Algorithms (SODA-10), pp. 554-572, Cambridge, MA, USA, 2010.

2009

• By (α-β) Vincent Conitzer, Jerome Lang, and Lirong Xia. How Hard Is It to Control Sequential Elections Via the Agenda? In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp. 103-108, Pasadena, CA, USA, 2009.
• By (α-β) Vincent Conitzer, Matthew Rognlie, and Lirong Xia. Preference Functions That Score Rankings and Maximum Likelihood Estimation. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp. 109-115, Pasadena, CA, USA, 2009.
• By (contribution) Lirong Xia and Vincent Conitzer. Finite Local Consistency Characterizes Generalized Scoring Rules. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp. 336-341, Pasadena, CA, USA, 2009.
• By (contribution) Lirong Xia and Jerome Lang. A Dichotomy Theorem on the Existence of Efficient or Neutral Sequential Voting Correspondences. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp. 342-347, Pasadena, CA, USA, 2009.
• By (contribution) Lirong Xia, Michael Zuckerman, Ariel D. Procaccia, Vincent Conitzer, and Jeffrey S. Rosenschein. Complexity of Unweighted Coalitional Manipulation Under Some Common Voting Rules. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp. 348-353, Pasadena, CA, USA, 2009. [proof for ranked pairs]
• By (contribution) Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang. Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations. SIAM Journal on Computing 38(6): 2198-2219, 2009. Earlier version appeared in SODA-07, pp. 655-664, 2007.
• By (α-β) Jerome Lang and Lirong Xia. Sequential composition of voting rules in multi-issue domains. Mathematical Social Sciences 57(3): 304-324, 2009. Earlier versions appeared in IJCAI-07 and TARK-07.

2008

• By (contribution) Lirong Xia and Vincent Conitzer.  Generalized Scoring Rules and the Frequency of Coalitional Manipulability. In Proceedings of the 9th ACM Conference on Electronic Commerce (EC-08), pp. 109-118, Chicago, IL, USA, 2008.
• By (contribution) Lirong Xia and Vincent Conitzer. A Sufficient Condition for Voting Rules to Be Frequently Manipulable. In Proceedings of the 9th ACM Conference on Electronic Commerce (EC-08), pp. 99-108, Chicago, IL, USA, 2008.
• By (contribution) Lirong Xia, Vincent Conitzer, and Jerome Lang. Voting on Multiattribute Domains with Cyclic Preferential Dependencies. In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI-08), pp. 202-207, Chicago, IL, USA, 2008.
• By (contribution) Lirong Xia and Vincent Conitzer. Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders. In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI-08), pp. 196-201, Chicago, IL, USA, 2008.

2007

• By (contribution) Lirong Xia, Jerome Lang, and Mingsheng Ying. Strongly decomposable voting rules on multiattribute domains. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07), pp. 776-781, Vancouver, BC, Canada, 2007.
• By (contribution) Lirong Xia, Jerome Lang, and Mingsheng Ying. Sequential voting rules and multiple elections paradoxes. In Proceedings of the Eleventh Conference on Theoretical Aspects of Rationality and Knowledge (TARK-07), pp. 279-288, Brussels, Belgium, 2007.
• By (contribution) Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang. Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA-07), pp. 655-664, New Orleans, LA, 2007. Superceded by the journal version above.

2005 and before

• By (contribution) Lirong Xia and Sanjiang Li. On minimal models of the Region Connection Calculus. Fundamenta Informaticae 69(4): 427-446, 2005. (This is my undergrad thesis.)
• By (contribution) Lei Wang, Xu Liu, Lirong Xia, Guangyou Xu, and Alfred M. Bruckstein. Image orientation detection with integrated human perception cues (or which way is up). In Proceedings of IEEE International Conference on Image Processing (ICIP-03) vol 2: 539-542, Barcelona, Spain, 2003.

Professional Service

• Program committee member: IJCAI-11, COMSOC-12, AAMAS-12 (Nominated for the best PC award), AAAI-12, EC-12. Coorganizer of CoopMAS-12.
• Also reviewed papers for ACM Transactions on Algorithms, Artificial Intelligence Journal, Games and Economic Behavior, The Harvard Undergraduate Research Journal, Journal of Artificial Intelligence Research, Journal of Autonomous Agents and Multi-Agent Systems, Journal of Computer and System Sciences, Mathematics of Operations Research, Mathematical Social Sciences, Social Choice and Welfare, Theory of Computing Systems, AISTATS, COCOON, ESA, FOCS, WINE, SAGT, SODA, SOFSEM.