Lirong Xia

Ph.D. student supervised by Dr. Vincent Conitzer Duke University, Dept. of Computer Science, Box 90129    Durham, NC 27708-0129, USA Office: D343 LSRC Office Phone: +1-(919) 660-6564 E-mail:  or      My Curriculum Vitae

Research Interests

• Social choice (voting) theory, game theory, artificial intelligence, algorithms. Here is a more detailed research statement.

Publications

Working papers

• Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders. [pdf]
  This is the extended journal version of the paper under the same title published in AAAI-08.
  All proofs can be found here, as well as the study of two more common voting rules: voting trees and plurality with runoff.
  Lirong Xia and Vincent Conitzer.
• A Scheduling Approach to Coalitional Manipulation. [pdf]
  Lirong Xia, Vincent Conitzer, and Ariel D. Procaccia.

• Aggregating Preferences in Multi-Issue Domains by Using Maximum Likelihood Estimators.  [pdf]
  Lirong Xia, Vincent Conitzer, and Jerome Lang.

• Strategy-proof Voting Rules over Multi-issue Domains with Restricted Preferences. [pdf]
  Lirong Xia and Vincent Conitzer.

• Probabilistic automata for computing with words. [arxiv link]
  Submitted to Journal of Computer and System Sciences.
  Yongzhi Cao, Lirong Xia, and Mingsheng Ying.

2010

• Incentive Compatible Budget Elicitation in Multi-unit Auctions. [arxiv link]
  To appear in Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA-10), 2010.
  Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia.

2009

• How Hard Is It to Control Sequential Elections Via the Agenda? [pdf]
  In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp 103-108, Pasadena, CA, USA, 2009.
  Vincent Conitzer, Jerome Lang, and Lirong Xia.

• Preference Functions That Score Rankings and Maximum Likelihood Estimation. [pdf]
  In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp 109-115, Pasadena, CA, USA, 2009.
  Earlier version appeared in COMSOC-08.
  Vincent Conitzer, Matthew Rognlie, and Lirong Xia.

• Finite Local Consistency Characterizes Generalized Scoring Rules.. [pdf]
  In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp 336-341, Pasadena, CA, USA, 2009.
  Lirong Xia and Vincent Conitzer.

• A Dichotomy Theorem on the Existence of Efficient or Neutral Sequential Voting Correspondences. [pdf]
  In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp 342-347, Pasadena, CA, USA, 2009.
  Earlier version appeared in SCW-08.
  Lirong Xia and Jerome Lang.

• Complexity of Unweighted Coalitional Manipulation Under Some Common Voting Rules. [pdf]
  In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp 348-353, Pasadena, CA, USA, 2009.
  Earlier version appeared in COMSOC-08.
  Lirong Xia, Michael Zuckerman, Ariel D. Procaccia, Vincent Conitzer, and Jeffrey S. Rosenschein.

• Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations. [link]
  SIAM Journal on Computing 38(6): 2198-2219, 2009.
  Earlier version appeared in Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA-07), pp 655-664, 2007.
  Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang.

• Sequential composition of voting rules in multi-issue domains. [link]
  Mathematical Social Sciences 57(3): 304-324, 2009. 
  Earlier version appeared in IJCAI-07 and TARK-07.
  Jerome Lang and Lirong Xia.

2008

• Generalized Scoring Rules and the Frequency of Coalitional Manipulability. [pdf]
  In Proceedings of the 9th ACM Conference on Electronic Commerce (EC-08), pp 109-118, 2008.
  Lirong Xia and Vincent Conitzer.

• A Sufficient Condition for Voting Rules to Be Frequently Manipulable. [pdf]
  In Proceedings of the 9th ACM Conference on Electronic Commerce (EC-08), pp 99-108, 2008.
  Lirong Xia and Vincent Conitzer.

• Voting on Multiattribute Domains with Cyclic Preferential Dependencies. [pdf]
  In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI-08), pp 202-207, 2008.
  Lirong Xia, Vincent Conitzer, and Jerome Lang.

• Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders. [pdf]
  In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI-08), pp 196-201, 2008.
  Lirong Xia and Vincent Conitzer.

2007

• Strongly decomposable voting rules on multiattribute domains. [pdf]
  In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07), pp 776-781, 2007.
  Lirong Xia, Jerome Lang, and Mingsheng Ying.

• Sequential voting rules and multiple elections paradoxes. [pdf]
  In Proceedings of the Eleventh Conference on Theoretical Aspects of Rationality and Knowledge (TARK-07), pp 279-288, 2007.
  Lirong Xia, Jerome Lang, and Mingsheng Ying.

• Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree. [pdf]
  In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA-07), pp 655-664, 2007.
  Superceded by the journal version above.
  Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang.

2006

• On minimal models of the Region Connection Calculus. [pdf]
  Fundamenta Informaticae 69(4): 427-446, 2006.
  Lirong Xia and Sanjiang Li.

2003

• Image orientation detection with integrated human perception cues (or which way is up). [pdf]
  In Proceedings of IEEE International Conference on Image Processing (ICIP-03) vol 2: 539-542, 2003.
  Lei Wang, Xu Liu, Lirong Xia, Guangyou Xu, and Alfred M. Bruckstein.

Workshop presentations

• Complexity of unweighted coalitional manipulation under some common voting rules.
  Presented at Second International Workshop on Computational Social Choice (COMSOC-08).
  Lirong Xia, Vincent Conitzer, Ariel Procaccia, and Jeffrey Rosenschein.
• Social Welfare Functions That Score Rankings and Maximum Likelihood Estimation.
  Presented at Second International Workshop on Computational Social Choice (COMSOC-08).
  Vincent Conitzer, Matthew Rognlie, and Lirong Xia.
• On the neutrality and efficiency of seat-by-seat voting rules and correspondences.
  Presented at 9th International Meeting of the Society of Social Choice and Welfare (SCW-08).
  Lirong Xia and Jerome Lang.

Unpublished

• A logical approach to modelling Boolean Bayesian networks through qualitative information.
  Lirong Xia, Yongzhi Cao, and Mingsheng Ying.
• A topological approach to the compactness of many-valued propositional logic and first-order logic.
  Lirong Xia and Mingsheng Ying.

Last Updated: Nov. 1, 2009