Lirong Xia

AAAI Conference 2026 Conference Paper

On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting

• Ratip Emin Berker
• Emanuel Tewolde
• Vincent Conitzer
• Mingyu Guo
• Marijn Heule
• Lirong Xia

Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear programming for deciding whether and when core-stable committees are guaranteed to exist. In contrast to SAT-based approaches popular in computational social choice, our method can produce proofs for a specific number of candidates independent of the number of voters. In addition to these computational gains, our program lends itself to a novel duality-based reformulation of the core stability problem, from which we obtain new existence results in special cases. Further, we use our framework to reveal previously unknown relationships between core stability and other desirable properties, such as notions of priceability.

AAMAS Conference 2025 Conference Paper

Group Fairness in Multi-period Mobile Facility Location Problems

• Haris Aziz
• Hau Chan
• Xingchen Sha
• Toby Walsh
• Lirong Xia

We study the group-fair multi-period mobile facility location problems, where agents from different groups are located on a real line and arrive in different periods. Our goal is to locate 𝑘 mobile facilities at each period to serve the arriving agents in order to minimize the maximum total group-fair cost and the maximum average group-fair cost objectives that measure the costs or distances of groups of agents to their corresponding facilities across all periods. We first consider the problems from the algorithmic perspective for both group-fair cost objectives. We then consider the problems from the mechanism design perspective, where the agents’ locations and arrival periods are private. For both objectives, we design deterministic strategyproof mechanisms to elicit the agents’ locations and arrival periods truthfully while optimizing the group-fair cost objectives and show that our mechanisms have almost tight bounds on the approximation ratios for certain periods and settings. Finally, we discuss the extensions of our results to the online setting where agent arrival information is only known at each period.

UAI Conference 2025 Conference Paper

How Likely Are Two Voting Rules Different?

• Ziqi Yu
• Lirong Xia
• Qishen Han
• Chengkai Zhang

We characterize the maximum likelihood that two voting rule outcomes are different and that the winner of one voting rule is the loser of another (implying that they are {\em drastically different}) on positional scoring rules, Condorcet winner/loser, Copeland, Ranked Pairs, and STV (Single Transferable Vote) under any fixed number of alternatives. The most famous problem in this scope is strong Borda’s paradox, in which the winner of the plurality rule is the Condorcet loser. Under mild assumptions, we show that the maximum likelihood that different rules are drastically different is $\Theta(1)$ except for a few special cases, demonstrating the difference between these rules. We also prove that two scoring rules with linear independent scoring vectors have different winners with probability $\Theta(1)$, no matter how similar they are. Our analysis adopts the {\em smoothed social choice framework} \cite{xia2020smoothed} and can be applied to a variety of statistical models, including the standard impartial culture (IC).

UAI Conference 2025 Conference Paper

Trading Off Voting Axioms for Privacy

• Zhechen Li
• Ao Liu 0001
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

In this paper, we investigate tradeoffs among differential privacy (DP) and several important voting axioms: Pareto efficiency, SD-efficiency, PC-efficiency, Condorcet criterion, and Condorcet loser criterion. We provide upper and lower bounds on the two-way tradeoffs between DP and each axiom. We also provide upper and lower bounds on three-way tradeoffs among DP and every pairwise combination of all the axioms, showing that, while the axioms are compatible without DP, their upper bounds cannot be achieved simultaneously under DP. Our results illustrate the effect of DP on the satisfaction and compatibility of voting axioms.

IJCAI Conference 2024 Conference Paper

Computational Complexity of Verifying the Group No-show Paradox

• Farhad Mohsin
• Qishen Han
• Sikai Ruan
• Pin-Yu Chen
• Francesca Rossi
• Lirong Xia

The (group) no-show paradox refers to the undesirable situation where a group of agents have incentive to abstain from voting to make the winner more favorable to them. To understand whether it is a critical concern in practice, in this paper, we take a computational approach by examining the computational complexity of verifying whether the group no-show paradox exists given agents' preferences and the voting rule. We prove that, unfortunately, the verification problem is NP-hard to compute for some commonly studied voting rules, i. e. , Copeland, maximin, single transferable vote, and all Condorcetified positional scoring rules such as Black's rule. We propose integer linear programming-based algorithms and a search-based algorithm for the verification problem for different voting rules. Experimental results on synthetic data illustrate that the former is efficient when the number of unique rankings in a profile is not too high, and the latter is efficient for a small number of agents. With the help of these algorithms, we observe that group no-show paradoxes rarely occur in real-world data.

IJCAI Conference 2024 Conference Paper

Determining Winners in Elections with Absent Votes

• Qishen Han
• Amelie Marian
• Lirong Xia

An important question in elections is determining whether a candidate can be a winner when some votes are absent. We study this determining winner with absent votes (WAV) problem with elections that take top-truncated ballots. We show that the WAV problem is NP-complete for single transferable vote, Maximin, and Copeland, and propose a special case of positional scoring rule such that the problem can be computed in polynomial time. Our results for top-truncated rankings differ from the results in full rankings as their hardness results still hold when the number of candidates or the number of missing votes are bounded, while we show that the problem can be solved in polynomial time in either case.

AAMAS Conference 2024 Conference Paper

Distribution of Chores with Information Asymmetry

• Hadi Hosseini
• Joshua Kavner
• Tomas Wąs
• Lirong Xia

One well-regarded fairness notion in dividing indivisible chores is envy-freeness up to one item (EF1), which requires that pairwise envy can be eliminated by the removal of a single item. While an EF1 and Pareto optimal (PO) allocation of goods can always be found via well-known algorithms, even the existence of such solutions for chores remains open, to date. We take an epistemic approach to identify such allocations utilizing information asymmetry by introducing dubious chores – items that inflict no cost on receiving agents but are perceived to be costly by others. On a technical level, dubious chores provide a more fine-grained approximation of envyfreeness than EF1. We show that finding allocations with minimal number of dubious chores is computationally hard. Nonetheless, we prove the existence of envy-free and fractional PO allocations for 𝑛 agents with only 2𝑛 − 2 dubious chores and strengthen it to 𝑛 − 1 dubious chores in four special classes of valuations.

ECAI Conference 2024 Conference Paper

Distribution of Chores with Information Asymmetry

• Hadi Hosseini
• Joshua Kavner
• Tomasz Was
• Lirong Xia

A well-regarded fairness notion when dividing indivisible chores is envy-freeness up to one item (EF1), which requires that pairwise envy can be eliminated by the removal of a single item. While an EF1 and Pareto optimal (PO) allocation of goods can always be found via well-known algorithms, even the existence of such solutions for chores remains open, to date. We take an epistemic approach utilizing information asymmetry by introducing dubious chores–items that inflict no cost on receiving agents but are perceived costly by others. On a technical level, dubious chores provide a more fine-grained approximation of envy-freeness than EF1. We show that finding allocations with minimal number of dubious chores is computationally hard. Nonetheless, we prove the existence of envy-free and fractional PO allocations for n agents with only 2n−2 dubious chores and strengthen it to n−1 dubious chores in four special classes of valuations. Our experimental analysis demonstrates that often only a few dubious chores are needed to achieve envy-freeness.

UAI Conference 2023 Conference Paper

Accelerating Voting by Quantum Computation

• Ao Liu 0001
• Qishen Han
• Lirong Xia
• Nengkun Yu

Studying the computational complexity and designing fast algorithms for determining winners under voting rules are classical and fundamental questions in computational social choice. In this paper, we accelerate voting by leveraging quantum computation: we propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. We show that our algorithm can be quadratically faster than any classical algorithm (based on sampling with replacement) under a wide range of common voting rules, including positional scoring rules, Copeland, and single transferable voting (STV). Precisely, our quantum-accelerated voting algorithm outputs the correct winner with high probability in $\Theta\left(\frac{n}{\text{MOV}}\right)$ time, where $n$ is the number of votes and $\text{MOV}$ is margin of victory, the smallest number of voters to change the winner. In contrast, any classical voting algorithm based on sampling with replacement requires $\Omega\left(\frac{n^2}{\text{MOV}^2}\right)$ time under a large class of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.

AAMAS Conference 2023 Conference Paper

Computational Complexity of Verifying the Group No-show Paradox

• Farhad Mohsin
• Qishen Han
• Sikai Ruan
• Pin-Yu Chen
• Francesca Rossi
• Lirong Xia

The (group) no-show paradox refers to the undesirable situation where a group of agents has the incentive to abstain from voting to get a more favorable winner. We examine the computational complexity of verifying whether the group no-show paradox exists given agents’ preferences and the voting rule. We prove that the verification problem is NP-hard to compute for commonly studied voting rules such as Copeland, maximin, single transferable vote, and Black’s rule. We propose integer linear programming-based algorithms and a breadth-first search algorithm for the verification problem. Experimental results illustrate that the former work better for a small number of alternatives, and the latter work better for a small number of agents. Using these algorithms, we observe that the group no-show paradoxes rarely occur in real-world data.

IJCAI Conference 2023 Conference Paper

Convergence in Multi-Issue Iterative Voting under Uncertainty

• Joshua Kavner
• Reshef Meir
• Francesca Rossi
• Lirong Xia

We study strategic behavior in iterative plurality voting for multiple issues under uncertainty. We introduce a model synthesizing simultaneous multi-issue voting with local dominance theory, in which agents repeatedly update their votes based on sets of vote profiles they deem possible, and determine its convergence properties. After demonstrating that local dominance improvement dynamics may fail to converge, we present two sufficient model refinements that guarantee convergence from any initial vote profile for binary issues: constraining agents to have O-legal preferences, where issues are ordered by importance, and endowing agents with less uncertainty about issues they are modifying than others. Our empirical studies demonstrate that while cycles are common for agents without uncertainty, introducing uncertainty makes convergence almost guaranteed in practice.

AAAI Conference 2023 Conference Paper

Differentially Private Condorcet Voting

• Zhechen Li
• Ao Liu
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the well-known Condorcet method, and focus on three classes of voting rules in this family: Laplacian Condorcet method (CMLAP), exponential Condorcet method (CMEXP), and randomized response Condorcet method (CMRR), where λ represents the level of noise. We prove that all of our rules satisfy absolute monotonicity, lexi-participation, probabilistic Pareto efficiency, approximate probabilistic Condorcet criterion, and approximate SD-strategyproofness. In addition, CMRR satisfies (non-approximate) probabilistic Condorcet criterion, while CMLAP and CMEXP satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.

AAMAS Conference 2023 Conference Paper

Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences

• Hadi Hosseini
• Sujoy Sikdar
• Rohit Vaish
• Lirong Xia

We study fair allocation of indivisible goods and chores among agents with lexicographic preferences—a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying envy-freeness up to any item (EFX) could fail to exist for a mixture of objective goods and chores. To our knowledge, this negative result provides the first counterexample for EFX over (any subdomain of) additive valuations. To complement this non-existence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to maximin share (MMS), we show positive existence and computation for any mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as chores-only instances, and highlights the additional difficulty of these problems vis-à-vis their goods-only counterparts.

JAIR Journal 2023 Journal Article

Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms

• Xiaoxi Guo
• Sujoy Sikdar
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.

IJCAI Conference 2023 Conference Paper

First-Choice Maximality Meets Ex-ante and Ex-post Fairness

• Xiaoxi Guo
• Sujoy Sikdar
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i. e. , maximizing the number of agents assigned their first choices, together with Pareto efficiency (PE). Our mechanisms also provide guarantees of ex-ante and ex-post fairness. The generalized eager Boston mechanism is ex-ante envy-free, and ex-post envy-free up to one item (EF1). The generalized probabilistic Boston mechanism is also ex-post EF1, and satisfies ex-ante efficiency instead of fairness. We also show that no strategyproof mechanism satisfies ex-post PE, EF1, and FCM simultaneously. In doing so, we expand the frontiers of simultaneously providing efficiency and both ex-ante and ex-post fairness guarantees for the assignment problem.

AAAI Conference 2023 Conference Paper

Frustratingly Easy Truth Discovery

• Reshef Meir
• Ofra Amir
• Omer Ben-Porat
• Tsviel Ben Shabat
• Gal Cohensius
• Lirong Xia

Truth discovery is a general name for a broad range of statistical methods aimed to extract the correct answers to questions, based on multiple answers coming from noisy sources. For example, workers in a crowdsourcing platform. In this paper, we consider an extremely simple heuristic for estimating workers' competence using average proximity to other workers. We prove that this estimates well the actual competence level and enables separating high and low quality workers in a wide spectrum of domains and statistical models. Under Gaussian noise, this simple estimate is the unique solution to the MLE with a constant regularization factor. Finally, weighing workers according to their average proximity in a crowdsourcing setting, results in substantial improvement over unweighted aggregation and other truth discovery algorithms in practice.

IJCAI Conference 2023 Conference Paper

Learning to Design Fair and Private Voting Rules (Extended Abstract)

• Farhad Mohsin
• Ao Liu
• Pin-Yu Chen
• Francesca Rossi
• Lirong Xia

Voting is used widely to aggregate preferences to make a collective decision. In this paper, we focus on evaluating and designing voting rules that support both the privacy of the voting agents and a notion of fairness over such agents. First, we introduce a novel notion of group fairness and adopt the existing notion of local differential privacy. We then evaluate the level of group fairness in several existing voting rules, as well as the trade-offs between fairness and privacy, showing that it is not possible to always obtain maximal economic efficiency with high fairness. Then, we present both a machine learning and a constrained optimization approach to design new voting rules that are fair while maintaining a high level of economic efficiency. Finally, we empirically examine the effect of adding noise to create local differentially private voting rules and discuss the three-way trade-off between economic efficiency, fairness, and privacy.

AAMAS Conference 2023 Conference Paper

Learning to Explain Voting Rules

• Inwon Kang
• Qishen Han
• Lirong Xia

Explaining the outcome of an election is a crucial task to address, especially in the case of complex voting rules. For those without a background in social choice, understanding the result of an election with a complex voting rule can be difficult. One possible way of explaining a voting rule is by using a decision tree structure, allowing the reader to follow the reasoning behind the outcome. This work proposes a methodology for explaining voting rules using decision-tree-based classifiers. Using simple features, the classifiers can be trained to a high accuracy while maintaining a human-readable size. We test this framework with well-established voting rules – Copeland, Kemeny-Young, Ranked Pairs and Schulze – to generate explanations for each election’s outcome. We experiment with different decision tree algorithms on a synthetic dataset to generate explanations for the election outcome. We find that Copeland and Schulze under three candidates can be learned perfectly using an optimized decision tree algorithm, while cases of other rules have high accuracy experimentally.

AIJ Journal 2023 Journal Article

Multi resource allocation with partial preferences

• Haibin Wang
• Sujoy Sikdar
• Xiaoxi Guo
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

We provide efficient, fair, and non-manipulable mechanisms for the multi-type resource allocation problems (MTRAs) and multiple assignment problems where agents have partial preferences over bundles consisting of multiple divisible items. We uncover a natural reduction from multiple assignment problems to MTRAs, which preserves the properties of MTRA mechanisms. We extend the well-known random priority (RP) and probabilistic serial (PS) mechanisms to MTRAs with partial preferences as multi-type PS (MPS) and multi-type RP (MRP) and propose a new mechanism, multi-type general dictatorship (MGD), which combines the ideas of MPS and MRP. We show that for the unrestricted domain of partial order preferences, unfortunately, no mechanism satisfies both sd-efficiency and sd-envy-freeness, even as they each satisfy different weaker notions of the desirable properties of efficiency, fairness, and non-manipulability we consider. Notwithstanding this impossibility result, our main message is positive: When agents' preferences are represented by acyclic CP-nets, MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance, while MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, recovering the properties of RP and PS; the MGD satisfies sd-efficiency, equal treatment of equals, and decomposability under the unrestricted domain of partial preferences. We introduce a natural domain of bundle net preferences, which generalizes previously studied domain restrictions of partial preferences for multiple assignment problems and is incomparable to the domain of acyclic CP-nets. We show that MRP and MPS satisfy all properties of the RP and PS under bundle net preferences as well.

AAAI Conference 2023 Conference Paper

Semi-random Impossibilities of Condorcet Criterion

• Lirong Xia

The Condorcet criterion (CC) is a classical and well-accepted criterion for voting. Unfortunately, it is incompatible with many other desiderata including participation (PAR), half-way monotonicity (HM), Maskin monotonicity (MM), and strategy-proofness (SP). Such incompatibilities are often known as impossibility theorems, and are proved by worst-case analysis. Previous work has investigated the likelihood for these impossibilities to occur under certain models, which are often criticized of being unrealistic. We strengthen previous work by proving the first set of semi-random impossibilities for voting rules to satisfy CC and the more general, group versions of the four desiderata: for any sufficiently large number of voters n, any size of the group 1<= B<= \sqrt n, any voting rule r, and under a large class of semi-random models that include Impartial Culture, the likelihood for r to satisfy CC and PAR, CC and HM, CC and MM, or CC and SP is 1-\Omega(B/\sqrt n). This matches existing lower bounds for CC&PAR (B=1) and CC&SP and CC&HM (B<=\sqrt n), showing that many commonly-studied voting rules are already asymptotically optimal in such cases.

TMLR Journal 2023 Journal Article

Smoothed Differential Privacy

• Ao Liu
• Yu-Xiang Wang
• Lirong Xia

Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. Often, DP classifies most mechanisms without additive noise as non-private (Dwork et al., 2014). Thus, additive noises are added to improve privacy (to achieve DP). However, in many real-world applications, adding additive noise is undesirable (Bagdasaryan et al., 2019) and sometimes prohibited (Liu et al., 2020). In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis (Spielman & Teng, May 2004). Our notion, smoothed DP, can effectively measure the privacy leakage of mechanisms without additive noises under realistic settings. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP. In addition, we prove several desirable properties of smoothed DP, including composition, robustness to post-processing, and distribution reduction. Based on those properties, we propose an efficient algorithm to calculate the privacy parameters for smoothed DP. Experimentally, we verify that, according to smoothed DP, the discrete sampling mechanisms are private in real-world elections, and some discrete neural networks can be private without adding any additive noise. We believe that these results contribute to the theoretical foundation of realistic privacy measures beyond worst-case analysis.

AAMAS Conference 2022 Conference Paper

Anti-Malware Sandbox Games

• Sujoy Sikdar
• Sikai Ruan
• Qishen Han
• Paween Pitimanaaree
• Jeremy Blackthorne
• Bulent Yener
• Lirong Xia

We develop a game theoretic model of malware protection using the state-of-the-art sandbox method, to characterize and compute optimal defense strategies for anti-malware. We model the strategic interaction between developers of malware (M) and anti-malware (AM) as a two player game, where AM commits to a strategy of generating sandbox environments, and M responds by choosing to either attack or hide malicious activity based on the environment it senses. We characterize the condition for AM to protect all its machines, and identify conditions under which an optimal AM strategy can be computed efficiently. For other cases, we provide a quadratically constrained quadratic program (QCQP)-based optimization framework to compute the optimal AM strategy. In addition, we identify a natural and easy to compute strategy for AM, which as we show empirically, achieves AM utility that is close to the optimal AM utility, in equilibrium.

AIJ Journal 2022 Journal Article

Certifiably robust interpretation via Rényi differential privacy

• Ao Liu
• Xiaoyu Chen
• Sijia Liu
• Lirong Xia
• Chuang Gan

Motivated by the recent discovery that the interpretation maps of CNNs could easily be manipulated by adversarial attacks against network interpretability, we study the problem of interpretation robustness from a new perspective of Rényi differential privacy (RDP). The advantages of our Rényi-Robust-Smooth (RDP-based interpretation method) are three-folds. First, it can offer provable and certifiable top-k robustness. That is, the top-k important attributions of the interpretation map are provably robust under any input perturbation with bounded ℓ d -norm (for any d ≥ 1, including d = ∞ ). Second, our proposed method offers ∼12% better experimental robustness than existing approaches in terms of the top-k attributions. Remarkably, the accuracy of Rényi-Robust-Smooth also outperforms existing approaches. Third, our method can provide a smooth tradeoff between robustness and computational efficiency. Experimentally, its top-k attributions are twice more robust than existing approaches when the computational resources are highly constrained.

AAMAS Conference 2022 Conference Paper

Designing Efficient and Fair Mechanisms for Multi-Type Resource Allocation

• Xiaoxi Guo
• Sujoy Sikdar
• Haibin Wang
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

In the multi-type resource allocation problem (MTRA), there are 𝑑 ≥ 2 types of items, and 𝑛 agents who each demand one unit of items of each type and have strict linear preferences over bundles consisting of one item of each type. For MTRAs with indivisible items, we first present an impossibility result that no mechanism can satisfy both sd-efficiency and sd-envy-freeness. We show that this impossibility result is circumvented under the natural assumption of lexicographic preferences by providing lexicographic probabilistic serial (LexiPS) as an extension of the probabilistic serial (PS) mechanism. We also prove that LexiPS satisfies sd-efficiency and sd-envy-freeness. Moreover, LexiPS satisfies sd-weak-strategy proofness when agents are not allowed to misreport their importance orders. The multi-type probabilistic serial cannot deal with indivisible items, but provides a stronger efficiency guarantee under the unrestricted domain of strict linear preferences for divisible items, while also retaining desirable fairness guarantees.

IJCAI Conference 2022 Conference Paper

Learning Mixtures of Random Utility Models with Features from Incomplete Preferences

• Zhibing Zhao
• Ao Liu
• Lirong Xia

Random Utility Models (RUMs), which subsume Plackett-Luce model (PL) as a special case, are among the most popular models for preference learning. In this paper, we consider RUMs with features and their mixtures, where each alternative has a vector of features, possibly different across agents. Such models significantly generalize the standard PL and RUMs, but are not as well investigated in the literature. We extend mixtures of RUMs with features to models that generate incomplete preferences and characterize their identifiability. For PL, we prove that when PL with features is identifiable, its MLE is consistent with a strictly concave objective function under mild assumptions, by characterizing a bound on root-mean-square-error (RMSE), which naturally leads to a sample complexity bound. We also characterize identifiability of more general RUMs with features and propose a generalized RBCML to learn them. Our experiments on synthetic data demonstrate the effectiveness of MLE on PL with features with tradeoffs between statistical efficiency and computational efficiency. Our experiments on real-world data show the prediction power of PL with features and its mixtures.

JAIR Journal 2022 Journal Article

Learning to Design Fair and Private Voting Rules

• Farhad Mohsin
• Ao Liu
• Pin-Yu Chen
• Francesca Rossi
• Lirong Xia

Voting is used widely to identify a collective decision for a group of agents, based on their preferences. In this paper, we focus on evaluating and designing voting rules that support both the privacy of the voting agents and a notion of fairness over such agents. To do this, we introduce a novel notion of group fairness and adopt the existing notion of local differential privacy. We then evaluate the level of group fairness in several existing voting rules, as well as the trade-offs between fairness and privacy, showing that it is not possible to always obtain maximal economic efficiency with high fairness or high privacy levels. Then, we present both a machine learning and a constrained optimization approach to design new voting rules that are fair while maintaining a high level of economic efficiency. Finally, we empirically examine the effect of adding noise to create local differentially private voting rules and discuss the three-way trade-off between economic efficiency, fairness, and privacy. This paper appears in the special track on AI & Society.

AAAI Conference 2022 Conference Paper

The Semi-random Likelihood of Doctrinal Paradoxes

• Ao Liu
• Lirong Xia

When aggregating logically interconnected judgements from n agents, the result might be logically inconsistent. This phenomenon is known as the doctrinal paradox, which plays a central role in the field of judgement aggregation. Previous work has mostly focused on the worst-case analysis of the doctrinal paradox, leading to many impossibility results. Little is known about its likelihood of occurrence in practical settings, except for the study under certain distributions by List in 2005. In this paper, we characterize the likelihood of the doctrinal paradox under a general and realistic model called semi-random social choice framework (proposed by Xia in 2020). In the framework, agents’ ground truth judgements can be arbitrarily correlated, while the noises are independent. Our main theorem states that under mild conditions, the semi-random likelihood of the doctrinal paradox is either 0, exp(-Θ(n)), Θ(nˆ (-0. 5)) or Θ(1). This not only answers open questions by List in 2005, but also draws clear lines between situations with frequent paradoxes and with vanishing paradoxes.

AAAI Conference 2021 Conference Paper

Fair and Efficient Allocations under Lexicographic Preferences

• Hadi Hosseini
• Sujoy Sikdar
• Rohit Vaish
• Lirong Xia

Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efficiently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences–a well-studied preference model in artificial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efficiency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).

AAAI Conference 2021 System Paper

OPRA: An Open-Source Online Preference Reporting and Aggregation System

• Yiwei Chen
• Jingwen Qian
• Junming Wang
• Lirong Xia
• Gavriel Zahavi

We introduce the Online Preference Reporting and Aggregation (OPRA) system, an open-source online system that aims at providing support for group decision-making. We illustrate OPRA’s distinctive features: UI for reporting rankings with ties, comprehensive analytics of preferences, and group decision-making in combinatorial domains. We also discuss our work in an automatic mentor matching system. We hope that the open-source nature of OPRA will foster development of computerized group decision support systems.

AAAI Conference 2021 Conference Paper

Representative Proxy Voting

• Elliot Anshelevich
• Zack Fitzsimmons
• Rohit Vaish
• Lirong Xia

We study a model of proxy voting where the candidates, voters, and proxies are all located on the real line, and instead of voting directly, each voter delegates its vote to the closest proxy. The goal is to find a set of proxies that is θrepresentative, which entails that for any voter located anywhere on the line, its favorite candidate is within a distance θ of the favorite candidate of its closest proxy. This property guarantees a strong form of representation as the set of voters is not required to be fixed in advance, or even be finite. We show that for candidates located on a line, an optimal proxy arrangement can be computed in polynomial time. Moreover, we provide upper and lower bounds on the number of proxies required to form a θ-representative set, thus showing that a relatively small number of proxies is enough to capture the preferences of any set of voters. An additional beneficial property of a θ-representative proxy arrangement is that for strict-Condorcet voting rules, the outcome of proxy voting is similarly close to the outcome of direct voting.

AAMAS Conference 2021 Conference Paper

Sequential Mechanisms for Multi-type Resource Allocation

• Sujoy Sikdar
• Xiaoxi Guo
• Haibin Wang
• Lirong Xia
• Yongzhi Cao

Several resource allocation problems involve multiple types of resources, with a different agency being responsible for “locally” allocating the resources of each type, while a central planner wishes to provide a guarantee on the properties of the final allocation given agents’ preferences. We study the relationship between properties of the local mechanisms, each responsible for assigning all of the resources of a designated type, and the properties of a sequential mechanism which is composed of these local mechanisms, one for each type, applied sequentially, under lexicographic preferences, a well studied model of preferences over multiple types of resources in artificial intelligence and economics. We show that when preferences are 𝑂-legal, meaning that agents share a common importance order on the types, sequential mechanisms satisfy the desirable properties of anonymity, neutrality, non-bossiness, or Pareto-optimality if and only if every local mechanism also satisfies the same property, and they are applied sequentially according to the order 𝑂. Our main results are that under 𝑂-legal lexicographic preferences, every mechanism satisfying strategyproofness and a combination of these properties must be a sequential composition of local mechanisms that are also strategyproof, and satisfy the same combinations of properties.

NeurIPS Conference 2021 Conference Paper

Strategic Behavior is Bliss: Iterative Voting Improves Social Welfare

• Joshua Kavner
• Lirong Xia

Recent work in iterative voting has defined the additive dynamic price of anarchy (ADPoA) as the difference in social welfare between the truthful and worst-case equilibrium profiles resulting from repeated strategic manipulations. While iterative plurality has been shown to only return alternatives with at most one less initial votes than the truthful winner, it is less understood how agents' welfare changes in equilibrium. To this end, we differentiate agents' utility from their manipulation mechanism and determine iterative plurality's ADPoA in the worst- and average-cases. We first prove that the worst-case ADPoA is linear in the number of agents. To overcome this negative result, we study the average-case ADPoA and prove that equilibrium winners have a constant order welfare advantage over the truthful winner in expectation. Our positive results illustrate the prospect for social welfare to increase due to strategic manipulation.

NeurIPS Conference 2021 Conference Paper

The Semi-Random Satisfaction of Voting Axioms

• Lirong Xia

We initiate the work towards a comprehensive picture of the worst average-case satisfaction of voting axioms in semi-random models, to provide a finer and more realistic foundation for comparing voting rules. We adopt the semi-random model and formulation in [Xia 2020], where an adversary chooses arbitrarily correlated ``ground truth'' preferences for the agents, on top of which random noises are added. We focus on characterizing the semi-random satisfaction of two well-studied voting axioms: Condorcet criterion and participation. We prove that for any fixed number of alternatives, when the number of voters $n$ is sufficiently large, the semi-random satisfaction of the Condorcet criterion under a wide range of voting rules is $1$, $1-\exp(-\Theta(n))$, $\Theta(n^{-0. 5})$, $ \exp(-\Theta(n))$, or being $\Theta(1)$ and $1-\Theta(1)$ at the same time; and the semi-random satisfaction of participation is $1-\Theta(n^{-0. 5})$. Our results address open questions by Berg and Lepelley in 1994, and also confirm the following high-level message: the Condorcet criterion is a bigger concern than participation under realistic models.

AAAI Conference 2021 Conference Paper

The Smoothed Complexity of Computing Kemeny and Slater Rankings

• Lirong Xia
• Weiqiang Zheng

The computational complexity of winner determination under common voting rules is a classical and fundamental topic in the field of computational social choice. Previous work has established the NP-hardness of winner determination under some commonly-studied voting rules, such as the Kemeny rule and the Slater rule. In a recent position paper, Baumeister, Hogrebe, and Rothe (2020) questioned the relevance of the worst-case nature of NP-hardness in social choice and proposed to conduct smoothed complexity analysis (Spielman and Teng 2009) under Bläser and Manthey’s (2015) framework. In this paper, we develop the first smoothed complexity results for winner determination in voting. We prove the smoothed hardness of Kemeny and Slater using the classical smoothed runtime analysis, and prove a parameterized typical-case smoothed easiness result for Kemeny. We also make an attempt of applying Bläser and Manthey’s (2015) smoothed complexity framework in social choice contexts by proving that the framework categorizes an always-exponential-time brute force search algorithm as being smoothed poly-time, under a natural noise model based on the well-studied Mallows model in social choice and statistics. Overall, our results show that smoothed complexity analysis in computational social choice is a challenging and fruitful topic.

AAAI Conference 2020 Conference Paper

Fair Division Through Information Withholding

• Hadi Hosseini
• Sujoy Sikdar
• Rohit Vaish
• Hejun Wang
• Lirong Xia

Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate, and define a novel fairness notion based on information withholding. Under this notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envyfreeness can be achieved by withholding only a small number of goods overall. We show that finding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. In contrast to the worst-case results, our experiments on synthetic and realworld preference data show that existing algorithms for finding EF1 allocations withhold a close-to-optimal amount of information.

UAI Conference 2020 Conference Paper

How Private Are Commonly-Used Voting Rules?

• Ao Liu 0001
• Yun Lu 0001
• Lirong Xia
• Vassilis Zikas

Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question: “How private are commonly-used voting rules? " Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.

AAAI Conference 2020 Conference Paper

Multi-Type Resource Allocation with Partial Preferences

• Haibin Wang
• Sujoy Sikdar
• Xiaoxi Guo
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

We propose multi-type probabilistic serial (MPS) and multitype random priority (MRP) as extensions of the well-known PS and RP mechanisms to the multi-type resource allocation problems (MTRAs) with partial preferences. In our setting, there are multiple types of divisible items, and a group of agents who have partial order preferences over bundles consisting of one item of each type. We show that for the unrestricted domain of partial order preferences, no mechanism satisfies both sd-efficiency and sd-envy-freeness. Notwithstanding this impossibility result, our main message is positive: When agents’ preferences are represented by acyclic CPnets, MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, while MRP satisfies ex-postefficiency, sd-strategyproofness, and upper invariance, recovering the properties of PS and RP. Besides, we propose a hybrid mechanism, multi-type general dictatorship (MGD), combining the ideas of MPS and MRP, which satisfies sd-efficiency, equal treatment of equals and decomposability under the unrestricted domain of partial order preferences.

UAI Conference 2020 Conference Paper

Optimal Statistical Hypothesis Testing for Social Choice

• Lirong Xia

We address the following question in this paper: “What are the most robust statistical methods for social choice? ” By leveraging the theory of uniformly least favorable distributions in the Neyman-Pearson framework to finite models and randomized tests, we characterize uniformly most powerful (UMP) tests, which is a well-accepted statistical optimality w. r. t. robustness, for testing whether a given alternative is the winner under Mallows’ model and under Condorcet’s model, respectively.

NeurIPS Conference 2020 Conference Paper

The Smoothed Possibility of Social Choice

• Lirong Xia

We develop a framework that leverages the smoothed complexity analysis by Spielman and Teng to circumvent paradoxes and impossibility theorems in social choice, motivated by modern applications of social choice powered by AI and ML. For Condrocet’s paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate as the number of agents increases, or does not vanish at all. For the ANR impossibility on the non-existence of voting rules that simultaneously satisfy anonymity, neutrality, and resolvability, we characterize the rate for the impossibility to vanish, to be either polynomially fast or exponentially fast. We also propose a novel easy-to-compute tie-breaking mechanism that optimally preserves anonymity and neutrality for even number of alternatives in natural settings. Our results illustrate the smoothed possibility of social choice—even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice.

IJCAI Conference 2019 Conference Paper

Equitable Allocations of Indivisible Goods

• Rupert Freeman
• Sujoy Sikdar
• Rohit Vaish
• Lirong Xia

In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efficiency. We show that the Leximin algorithm produces an allocation that satisfies equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.

NeurIPS Conference 2019 Conference Paper

Learning Mixtures of Plackett-Luce Models from Structured Partial Orders

• Zhibing Zhao
• Lirong Xia

Mixtures of ranking models have been widely used for heterogeneous preferences. However, learning a mixture model is highly nontrivial, especially when the dataset consists of partial orders. In such cases, the parameter of the model may not be even identifiable. In this paper, we focus on three popular structures of partial orders: ranked top-$l_1$, $l_2$-way, and choice data over a subset of alternatives. We prove that when the dataset consists of combinations of ranked top-$l_1$ and $l_2$-way (or choice data over up to $l_2$ alternatives), mixture of $k$ Plackett-Luce models is not identifiable when $l_1+l_2\le 2k-1$ ($l_2$ is set to $1$ when there are no $l_2$-way orders). We also prove that under some combinations, including ranked top-$3$, ranked top-$2$ plus $2$-way, and choice data over up to $4$ alternatives, mixtures of two Plackett-Luce models are identifiable. Guided by our theoretical results, we propose efficient generalized method of moments (GMM) algorithms to learn mixtures of two Plackett-Luce models, which are proven consistent. Our experiments demonstrate the efficacy of our algorithms. Moreover, we show that when full rankings are available, learning from different marginal events (partial orders) provides tradeoffs between statistical efficiency and computational efficiency.

AAAI Conference 2019 Conference Paper

Learning Plackett-Luce Mixtures from Partial Preferences

• Ao Liu
• Zhibing Zhao
• Chao Liao
• Pinyan Lu
• Lirong Xia

We propose an EM-based framework for learning Plackett- Luce model and its mixtures from partial orders. The core of our framework is the efficient sampling of linear extensions of partial orders under Plackett-Luce model. We propose two Markov Chain Monte Carlo (MCMC) samplers: Gibbs sampler and the generalized repeated insertion method tuned by MCMC (GRIM-MCMC), and prove the efficiency of GRIM- MCMC for a large class of preferences. Experiments on synthetic data show that the algorithm with Gibbs sampler outperforms that with GRIM-MCMC. Experiments on real-world data show that the likelihood of test dataset increases when (i) partial orders provide more information; or (ii) the number of components in mixtures of Plackett- Luce model increases.

AAAI Conference 2019 Conference Paper

Mechanism Design for Multi-Type Housing Markets with Acceptable Bundles

• Sujoy Sikdar
• Sibel Adalı
• Lirong Xia

We extend the Top-Trading-Cycles (TTC) mechanism to select strict core allocations for housing markets with multiple types of items, where each agent may be endowed and allocated with multiple items of each type. In doing so, we advance the state of the art in mechanism design for housing markets along two dimensions: First, our setting is more general than multi-type housing markets (Moulin 1995; Sikdar, Adali, and Xia 2017) and the setting of Fujita et al. (2015). Further, we introduce housing markets with acceptable bundles (HMABs) as a more general setting where each agent may have arbitrary sets of acceptable bundles. Second, our extension of TTC is strict core selecting under the weaker restriction on preferences of CMI-trees, which we introduce as a new domain restriction on preferences that generalizes commonly-studied languages in previous works.

IJCAI Conference 2019 Conference Paper

Minimizing Time-to-Rank: A Learning and Recommendation Approach

• Haoming Li
• Sujoy Sikdar
• Rohit Vaish
• Junming Wang
• Lirong Xia
• Chaonan Ye

Consider the following problem faced by an online voting platform: A user is provided with a list of alternatives, and is asked to rank them in order of preference using only drag-and-drop operations. The platform's goal is to recommend an initial ranking that minimizes the time spent by the user in arriving at her desired ranking. We develop the first optimization framework to address this problem, and make theoretical as well as practical contributions. On the practical side, our experiments on the Amazon Mechanical Turk platform provide two interesting insights about user behavior: First, that users' ranking strategies closely resemble selection or insertion sort, and second, that the time taken for a drag-and-drop operation depends linearly on the number of positions moved. These insights directly motivate our theoretical model of the optimization problem. We show that computing an optimal recommendation is NP-hard, and provide exact and approximation algorithms for a variety of special cases of the problem. Experimental evaluation on MTurk shows that, compared to a random recommendation strategy, the proposed approach reduces the (average) time-to-rank by up to 50%.

AAAI Conference 2019 Conference Paper

Near-Neighbor Methods in Random Preference Completion

• Ao Liu
• Qiong Wu
• Zhenming Liu
• Lirong Xia

This paper studies a stylized, yet natural, learning-to-rank problem and points out the critical incorrectness of a widely used nearest neighbor algorithm. We consider a model with n agents (users) {xi}i∈[n] and m alternatives (items) {yl}l∈[m], each of which is associated with a latent feature vector. Agents rank items nondeterministically according to the Plackett-Luce model, where the higher the utility of an item to the agent, the more likely this item will be ranked high by the agent. Our goal is to identify near neighbors of an arbitrary agent in the latent space for prediction. We first show that the Kendall-tau distance based kNN produces incorrect results in our model. Next, we propose a new anchor-based algorithm to find neighbors of an agent. A salient feature of our algorithm is that it leverages the rankings of many other agents (the so-called “anchors”) to determine the closeness/similarities of two agents. We provide a rigorous analysis for one-dimensional latent space, and complement the theoretical results with experiments on synthetic and real datasets. The experiments confirm that the new algorithm is robust and practical.

AAAI Conference 2019 Conference Paper

Practical Algorithms for Multi-Stage Voting Rules with Parallel Universes Tiebreaking

• Jun Wang
• Sujoy Sikdar
• Tyler Shepherd
• Zhibing Zhao
• Chunheng Jiang
• Lirong Xia

STV and ranked pairs (RP) are two well-studied voting rules for group decision-making. They proceed in multiple rounds, and are affected by how ties are broken in each round. However, the literature is surprisingly vague about how ties should be broken. We propose the first algorithms for computing the set of alternatives that are winners under some tiebreaking mechanism under STV and RP, which is also known as parallel-universes tiebreaking (PUT). Unfortunately, PUTwinners are NP-complete to compute under STV and RP, and standard search algorithms from AI do not apply. We propose multiple DFS-based algorithms along with pruning strategies, heuristics, sampling and machine learning to prioritize search direction to significantly improve the performance. We also propose novel ILP formulations for PUT-winners under STV and RP, respectively. Experiments on synthetic and realworld data show that our algorithms are overall faster than ILP.

UAI Conference 2018 Conference Paper

A Cost-Effective Framework for Preference Elicitation and Aggregation

• Zhibing Zhao
• Haoming Li 0002
• Junming Wang
• Jeffrey O. Kephart
• Nicholas Mattei
• Hui Su
• Lirong Xia

We propose a cost-effective framework for preference elicitation and aggregation under the Plackett-Luce model with features. Given a budget, our framework iteratively computes the most cost-effective elicitation questions in order to help the agents make a better group decision. We illustrate the viability of the framework with experiments on Amazon Mechanical Turk, which we use to estimate the cost of answering different types of elicitation questions. We compare the prediction accuracy of our framework when adopting various information criteria that evaluate the expected information gain from a question. Our experiments show carefully designed information criteria are much more efficient, i. e. , they arrive at the correct answer using fewer queries, than randomly asking questions given the budget constraint.

NeurIPS Conference 2018 Conference Paper

A Mathematical Model For Optimal Decisions In A Representative Democracy

• Malik Magdon-Ismail
• Lirong Xia

Direct democracy, where each voter casts one vote, fails when the average voter competence falls below 50%. This happens in noisy settings when voters have limited information. Representative democracy, where voters choose representatives to vote, can be an elixir in both these situations. We introduce a mathematical model for studying representative democracy, in particular understanding the parameters of a representative democracy that gives maximum decision making capability. Our main result states that under general and natural conditions, for fixed voting cost, the optimal number of representatives is linear; for polynomial cost, the optimal number of representatives is logarithmic.

ICML Conference 2018 Conference Paper

Composite Marginal Likelihood Methods for Random Utility Models

• Zhibing Zhao
• Lirong Xia

We propose a novel and flexible rank-breaking-then-composite-marginal-likelihood (RBCML) framework for learning random utility models (RUMs), which include the Plackett-Luce model. We characterize conditions for the objective function of RBCML to be strictly log-concave by proving that strict log-concavity is preserved under convolution and marginalization. We characterize necessary and sufficient conditions for RBCML to satisfy consistency and asymptotic normality. Experiments on synthetic data show that RBCML for Gaussian RUMs achieves better statistical efficiency and computation efficiency than the state-of-the-art algorithm and our RBCML for the Plackett-Luce model provides flexible tradeoffs between running time and statistical efficiency.

AAAI Conference 2018 Conference Paper

Learning Mixtures of Random Utility Models

• Zhibing Zhao
• Tristan Villamil
• Lirong Xia

We tackle the problem of identifiability and efficient learning of mixtures of Random Utility Models (RUMs). We show that when the PDFs of utility distributions are symmetric, the mixture of k RUMs (denoted by k-RUM) is not identi- fiable when the number of alternatives m is no more than 2k − 1. On the other hand, when m ≥ max{4k − 2, 6}, any k-RUM is generically identifiable. We then propose three algorithms for learning mixtures of RUMs: an EM-based algorithm, which we call E-GMM, a direct generalized-methodof-moments (GMM) algorithm, and a sandwich (GMM-E- GMM) algorithm that combines the other two. Experiments on synthetic data show that the sandwich algorithm achieves the highest statistical efficiency and GMM is the most computationally efficient. Experiments on real-world data at Preflib show that Gaussian k-RUMs provide better fitness than a single Gaussian RUM, the Plackett-Luce model, and mixtures of Plackett-Luce models w. r. t. commonly-used model fitness criteria. To the best of our knowledge, this is the first work on learning mixtures of general RUMs.

AIJ Journal 2018 Journal Article

Voting on multi-issue domains with conditionally lexicographic preferences

• Jérôme Lang
• Jérôme Mengin
• Lirong Xia

One approach to voting on several interrelated issues consists in using a language for compact preference representation, from which the voters' preferences are elicited and aggregated. Such a language can usually be seen as a domain restriction. We consider a well-known restriction, namely, conditionally lexicographic preferences, where both the relative importance between issues and the preference between the values of an issue may depend on the values taken by more important issues. The naturally associated language consists in describing conditional importance and conditional preference by trees together with conditional preference tables. In this paper, we study the aggregation of conditionally lexicographic preferences for several common voting rules and several classes of lexicographic preferences. We address the computation of the winning alternative for some important rules, both by identifying the computational complexity of the relevant problems and by showing that for several of them, computing the winner reduces in a very natural way to a maxsat problem.

AAMAS Conference 2017 Conference Paper

Condorcet Consistent Bundling with Social Choice

• Shreyas Sekar
• Sujoy Sikdar
• Lirong Xia

IJCAI Conference 2017 Conference Paper

Improving Group Decision-Making by Artificial Intelligence

• Lirong Xia

We summarize some of our recent work on using AI to improve group decision-making by taking a unified approach from statistics, economics, and computation. We then discuss a few ongoing and future directions.

AAAI Conference 2017 Conference Paper

Mechanism Design for Multi-Type Housing Markets

• Sujoy Sikdar
• Sibel Adali
• Lirong Xia

We study multi-type housing markets, where there are p ≥ 2 types of items, each agent is initially endowed one item of each type, and the goal is to design mechanisms without monetary transfer to (re)allocate items to the agents based on their preferences over bundles of items, such that each agent gets one item of each type. In sharp contrast to classical housing markets, previous studies in multi-type housing markets have been hindered by the lack of natural solution concepts, because the strict core might be empty. We break the barrier in the literature by leveraging AI techniques and making natural assumptions on agents’ preferences. We show that when agents’ preferences are lexicographic, even with different importance orders, the classical top-trading-cycles mechanism can be extended while preserving most of its nice properties. We also investigate computational complexity of checking whether an allocation is in the strict core and checking whether the strict core is empty. Our results convey an encouragingly positive message: it is possible to design good mechanisms for multi-type housing markets under natural assumptions on preferences.

AAMAS Conference 2017 Conference Paper

Optimal Decision Making with CP-nets and PCP-nets

• Sujoy Sikdar
• Sibel Adali
• Lirong Xia

AAMAS Conference 2017 Conference Paper

Thwarting Vote Buying Through Decoy Ballots

• David C. Parkes
• Paul Tylkin
• Lirong Xia

IJCAI Conference 2017 Conference Paper

Thwarting Vote Buying Through Decoy Ballots

• David C. Parkes
• Paul Tylkin
• Lirong Xia

There is increasing interest in promoting participatory democracy, in particular by allowing voting by mail or internet and through random-sample elections. A pernicious concern, though, is that of vote buying, which occurs when a bad actor seeks to buy ballots, paying someone to vote against their own intent. This becomes possible whenever a voter is able to sell evidence of which way she voted. We show how to thwart vote buying through decoy ballots, which are not counted but are indistinguishable from real ballots to a buyer. We show that an Election Authority can significantly reduce the power of vote buying through a small number of optimally distributed decoys, and model societal processes by which decoys could be distributed.

AAAI Conference 2017 Conference Paper

Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity

• Stephen Gross
• Elliot Anshelevich
• Lirong Xia

To design social choice mechanisms with desirable utility properties, normative properties, and low sample complexity, we propose a new randomized mechanism called 2-Agree. This mechanism asks random voters for their top alternatives until at least two voters agree, at which point it selects that alternative as the winner. We prove that, despite its simplicity and low sample complexity, 2-Agree achieves almost optimal distortion on a metric space when the number of alternatives is not large, and satisfies anonymity, neutrality, ex-post Pareto efficiency, very strong SD-participation, and is approximately truthful. We further show that 2-Agree works well for larger number of alternatives with decisive agents.

IS Journal 2016 Journal Article

AI's 10 to Watch

• Haris Aziz
• Elias Bareinboim
• Yejin Choi
• Daniel Hsu
• Shivaram Kalyanakrishnan
• Reshef Meir
• Suchi Saria
• Gerardo I. Simari

IEEE Intelligent Systems once again selected 10 young AI scientists as " AI's 10 to Watch. " This acknowledgment and celebration not only recognizes these young scientists and makes a positive impact in their academic career but also promotes the community and cutting-edge AI research among next-generation AI researchers, the industry, and the general public alike. The contributions are "Collective Decision Making in Multi-Agent Systems, " by Haris Aziz, "From Causal Inference and Data Fusion to an Automated Scientist, " by Elias Bareinboim, "Language, Vision, and Social AI, " by Yejin Choi, "Algorithms for Machine Learning, " by Daniel Hsu, "Learning Agents, " by Shivaram Kalyanakrishnan, "Strategy and Bounded Rationality, " by Reshef Meir, "; A Reasoning Engine for Tailoring Healthcare to the Individual, " by Suchi Saria, "Pushing the Limits of Knowledge Representation and Reasoning, " by Gerardo I. Simari, "Better Group Decision Making, " by Lirong Xia, and "Distributed Constraint Optimization, " by William Yeoh.

IJCAI Conference 2016 Conference Paper

Allocating Indivisible Items in Categorized Domains

• Erika Mackin
• Lirong Xia

We initiate a research agenda of mechanism design for categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent gets at least one item per category. We focus on basic CDAPs, where each agent gets exactly one item per category. We first characterize serial dictatorships by a minimal set of three axiomatic properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we propose a natural extension of serial dictatorships called categorial sequential allocation mechanisms (CSAMs), which allocate the items in multiple rounds: in each round, the designated agent chooses an item from a designated category. We fully characterize the worst-case rank efficiency of CSAMs for optimistic and pessimistic agents.

UAI Conference 2016 Conference Paper

Bayesian Estimators As Voting Rules

• Lirong Xia

We investigate the fairness of Bayesian estimators (BEs) by viewing them as (irresolute) voting rules and evaluating them by satisfaction of desirable social choice axioms. We characterize the class of BEs that satisfy neutrality by the class of BEs with neutral structures. We prove that a BE with a neutral structure is a minimax rule if it further satisfies parameter connectivity. We prove that no BE satisfies strict Condorcet criterion. We also propose three new BEs of natural frameworks and investigate their computational complexity and satisfaction of monotonicity and Condorcet criterion.

TIST Journal 2016 Journal Article

Incentive Mechanism Design for Crowdsourcing

• Tie Luo
• Sajal K. Das
• Hwee Pink Tan
• Lirong Xia

Crowdsourcing can be modeled as a principal-agent problem in which the principal (crowdsourcer) desires to solicit a maximal contribution from a group of agents (participants) while agents are only motivated to act according to their own respective advantages. To reconcile this tension, we propose an all-pay auction approach to incentivize agents to act in the principal’s interest, i.e., maximizing profit, while allowing agents to reap strictly positive utility. Our rationale for advocating all-pay auctions is based on two merits that we identify, namely all-pay auctions (i) compress the common, two-stage “bid-contribute” crowdsourcing process into a single “bid-cum-contribute” stage, and (ii) eliminate the risk of task nonfulfillment. In our proposed approach, we enhance all-pay auctions with two additional features: an adaptive prize and a general crowdsourcing environment. The prize or reward adapts itself as per a function of the unknown winning agent’s contribution, and the environment or setting generally accommodates incomplete and asymmetric information, risk-averse (and risk-neutral) agents, and a stochastic (and deterministic) population. We analytically derive this all-pay auction-based mechanism and extensively evaluate it in comparison to classic and optimized mechanisms. The results demonstrate that our proposed approach remarkably outperforms its counterparts in terms of the principal’s profit, agent’s utility, and social welfare.

ICML Conference 2016 Conference Paper

Learning Mixtures of Plackett-Luce Models

• Zhibing Zhao
• Peter Piech
• Lirong Xia

In this paper we address the identifiability and efficient learning problems of finite mixtures of Plackett-Luce models for rank data. We prove that for any k≥2, the mixture of k Plackett-Luce models for no more than 2k-1 alternatives is non-identifiable and this bound is tight for k=2. For generic identifiability, we prove that the mixture of k Plackett-Luce models over m alternatives is \em generically identifiable if k≤⌊\frac m-2 2⌋! . We also propose an efficient generalized method of moments (GMM) algorithm to learn the mixture of two Plackett-Luce models and show that the algorithm is consistent. Our experiments show that our GMM algorithm is significantly faster than the EMM algorithm by Gormley & Murphy (2008), while achieving competitive statistical efficiency.

AAAI Conference 2016 Conference Paper

Quantitative Extensions of the Condorcet Jury Theorem with Strategic Agents

• Lirong Xia

The Condorcet Jury Theorem justifies the wisdom of crowds and lays the foundations of the ideology of the democratic regime. However, the Jury Theorem and most of its extensions focus on two alternatives and none of them quantitatively evaluate the effect of agents’ strategic behavior on the mechanism’s truth-revealing power. We initiate a research agenda of quantitatively extending the Jury Theorem with strategic agents by characterizing the price of anarchy (PoA) and the price of stability (PoS) of the common interest Bayesian voting games for three classes of mechanisms: plurality, MAPs, and the mechanisms that satisfy anonymity, neutrality, and strategy-proofness (w. r. t. a set of natural probability models). We show that while plurality and MAPs have better best-case truth-revealing power (lower PoS), the third class of mechanisms are more robust against agents’ strategic behavior (lower PoA).

ECAI Conference 2016 Conference Paper

Welfare of Sequential Allocation Mechanisms for Indivisible Goods

• Haris Aziz 0001
• Thomas Kalinowski
• Toby Walsh
• Lirong Xia

Sequential allocation is a simple and attractive mechanism for the allocation of indivisible goods used in a number of real world settings. In sequential allocation, agents pick items according to a policy, the order in which agents take turns. Sequential allocation will return an allocation which is Pareto efficient - no agent can do better without others doing worse. However, sequential allocation may not return the outcome that optimizes the social welfare. We consider therefore the relationship between the welfare and the efficiency of the allocations returned by sequential allocation mechanisms. We then study some simple computational questions about what welfare is possible or necessary depending on the choice of policy. Over half the problems we study turn out to be tractable, and we give polynomial time algorithms to compute them. We also consider a novel control problem in which the Chair chooses a policy to improve social welfare. Again, many of the control problems we study turn out to be tractable, and our results give polynomial time algorithms. In this case, tractability is a good thing so that the Chair can improve the social welfare of the allocation.

UAI Conference 2015 Conference Paper

Computing Optimal Bayesian Decisions for Rank Aggregation via MCMC Sampling

• David Hughes
• Kevin Hwang
• Lirong Xia

statistical decision-theoretic framework for social choice by Azari Soufiani et al. (2014). We propose two efficient and general MCMC algorithms to compute optimal Bayesian decisions for Mallows’ model and Condorcet’s model w. r. t. any loss function and prior. We show that the mixing time of our Markov chain for Mallows’ model is polynomial in ϕ−kmax, dmax, and the input size, where ϕ is the dispersion of the model, kmax measures agents’ largest total bias in bipartitions of alternatives, and dmax is the maximum ratio between prior probabilities. We also show that in some cases the mixing time is at least Θ(ϕ−kmax /2 ). For Condorcet’s model, our Markov chain is rapid mixing for moderate prior distributions. Efficiency of our algorithms are illustrated by experiments on real-world datasets. A major challenge in previous research, especially in the Bayesian approaches, is the high computational complexity of decision making. For example, the maximum likelihood estimator (MLE) of a popular ranking model called Mallows’ model (Mallows, 1957) is NP-hard to compute (Bartholdi et al. , 1989). Computing optimal Bayesian decisions for rank aggregation is a hard combinatorial optimization problem because the parameter space is often discrete and its size is often exponential. Most previous work focused on designing efficient case-by-case algorithms for computing MLEs and MAPs of popular ranking models. However, the following question is left unanswered:

IJCAI Conference 2015 Conference Paper

Possible and Necessary Allocations via Sequential Mechanisms

• Haris Aziz
• Toby Walsh
• Lirong Xia

A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternation, and strict alternation. We present characterizations of the allocations that result respectively from the classes, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.

NeurIPS Conference 2014 Conference Paper

A Statistical Decision-Theoretic Framework for Social Choice

• Hossein Azari Soufiani
• David Parkes
• Lirong Xia

In this paper, we take a statistical decision-theoretic viewpoint on social choice, putting a focus on the decision to be made on behalf of a system of agents. In our framework, we are given a statistical ranking model, a decision space, and a loss function defined on (parameter, decision) pairs, and formulate social choice mechanisms as decision rules that minimize expected loss. This suggests a general framework for the design and analysis of new social choice mechanisms. We compare Bayesian estimators, which minimize Bayesian expected loss, for the Mallows model and the Condorcet model respectively, and the Kemeny rule. We consider various normative properties, in addition to computational complexity and asymptotic behavior. In particular, we show that the Bayesian estimator for the Condorcet model satisfies some desired properties such as anonymity, neutrality, and monotonicity, can be computed in polynomial time, and is asymptotically different from the other two rules when the data are generated from the Condorcet model for some ground truth parameter.

AIJ Journal 2014 Journal Article

Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules

• Jessica Davies
• George Katsirelos
• Nina Narodytska
• Toby Walsh
• Lirong Xia

We investigate manipulation of the Borda voting rule, as well as two elimination style voting rules, Nanson's and Baldwin's voting rules, which are based on Borda voting. We argue that these rules have a number of desirable computational properties. For unweighted Borda voting, we prove that it is NP-hard for a coalition of two manipulators to compute a manipulation. This resolves a long-standing open problem in the computational complexity of manipulating common voting rules. We prove that manipulation of Baldwin's and Nanson's rules is computationally more difficult than manipulation of Borda, as it is NP-hard for a single manipulator to compute a manipulation. In addition, for Baldwin's and Nanson's rules with weighted votes, we prove that it is NP-hard for a coalition of manipulators to compute a manipulation with a small number of candidates. Because of these NP-hardness results, we compute manipulations using heuristic algorithms that attempt to minimise the number of manipulators. We propose several new heuristic methods. Experiments show that these methods significantly outperform the previously best known heuristic method for the Borda rule. Our results suggest that, whilst computing a manipulation of the Borda rule is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice. In contrast to the Borda rule, our experiments with Baldwin's and Nanson's rules demonstrate that both of them are often more difficult to manipulate in practice. These results suggest that elimination style voting rules deserve further study.

ICML Conference 2014 Conference Paper

Computing Parametric Ranking Models via Rank-Breaking

• Hossein Azari Soufiani
• David C. Parkes
• Lirong Xia

Rank breaking is a methodology introduced by Azari Soufiani et al. (2013a) for applying a Generalized Method of Moments (GMM) algorithm to the estimation of parametric ranking models. Breaking takes full rankings and breaks, or splits them up, into counts for pairs of alternatives that occur in particular positions (e. g. , first place and second place, second place and third place). GMMs are of interest because they can achieve significant speed-up relative to maximum likelihood approaches and comparable statistical efficiency. We characterize the breakings for which the estimator is consistent for random utility models (RUMs) including Plackett-Luce and Normal-RUM, develop a general sufficient condition for a full breaking to be the only consistent breaking, and provide a trichotomy theorem in regard to single-edge breakings. Experimental results are presented to show the computational efficiency along with statistical performance of the proposed method.

NeurIPS Conference 2013 Conference Paper

Generalized Method-of-Moments for Rank Aggregation

• Hossein Azari Soufiani
• William Chen
• David Parkes
• Lirong Xia

In this paper we propose a class of efficient Generalized Method-of-Moments(GMM) algorithms for computing parameters of the Plackett-Luce model, where the data consists of full rankings over alternatives. Our technique is based on breaking the full rankings into pairwise comparisons, and then computing parameters that satisfy a set of generalized moment conditions. We identify conditions for the output of GMM to be unique, and identify a general class of consistent and inconsistent breakings. We then show by theory and experiments that our algorithms run significantly faster than the classical Minorize-Maximization (MM) algorithm, while achieving competitive statistical efficiency.

UAI Conference 2013 Conference Paper

Preference Elicitation For General Random Utility Models

• Hossein Azari Soufiani
• David C. Parkes
• Lirong Xia

This paper discusses General Random Utility Models (GRUMs). These are a class of parametric models that generate partial ranks over alternatives given attributes of agents and alternatives. We propose two preference elicitation scheme for GRUMs developed from principles in Bayesian experimental design, one for social choice and the other for personalized choice. We couple this with a general Monte-Carlo- Expectation-Maximization (MC-EM) based algorithm for MAP inference under GRUMs. We also prove uni-modality of the likelihood functions for a class of GRUMs. We examine the performance of various criteria by experimental studies, which show that the proposed elicitation scheme increases the precision of estimation.

AAAI Conference 2013 Conference Paper

Strategic Behavior when Allocating Indivisible Goods Sequentially

• Thomas Kalinowski
• Nina Narodytska
• Toby Walsh
• Lirong Xia

We study a simple sequential allocation mechanism for allocating indivisible goods between agents in which agents take turns to pick items. We focus on agents behaving strategically. We view the allocation procedure as a finite repeated game with perfect information. We show that with just two agents, we can compute the unique subgame perfect Nash equilibrium in linear time. With more agents, computing the subgame perfect Nash equilibria is more difficult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard. We identify a special case, when agents value many of the items identically, where we can efficiently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modifications to the mechanism that make it strategy proof.

AAAI Conference 2012 Conference Paper

A Complexity-of-Strategic-Behavior Comparison between Schulze’s Rule and Ranked Pairs

• David Parkes
• Lirong Xia

Schulze’s rule and ranked pairs are two Condorcet methods that both satisfy many natural axiomatic properties. Schulze’s rule is used in the elections of many organizations, including the Wikimedia Foundation, the Pirate Party of Sweden and Germany, the Debian project, and the Gento Project. Both rules are immune to control by cloning alternatives, but little is otherwise known about their strategic robustness, including resistance to manipulation by one or more voters, control by adding or deleting alternatives, adding or deleting votes, and bribery. Considering computational barriers, we show that these types of strategic behavior are NP-hard for ranked pairs (both constructive, in making an alternative a winner, and destructive, in precluding an alternative from being a winner). Schulze’s rule, in comparison, remains vulnerable at least to constructive manipulation by a single voter and destructive manipulation by a coalition. As the first such polynomialtime rule known to resist all such manipulations, and considering also the broad axiomatic support, ranked pairs seems worthwhile to consider for practical applications.

ECAI Conference 2012 Conference Paper

Combining Voting Rules Together

• Nina Narodytska
• Toby Walsh
• Lirong Xia

We propose a simple method for combining together voting rules that performs a run-off between the different winners of each voting rule. We prove that this combinator has several good properties. For instance, even if just one of the base voting rules has a desirable property like Condorcet consistency, the combination inherits this property. On the other hand, some important properties can be lost by the introduction of a run-off, including monotonicity and consistency. In addition, we prove that combining voting rules together in this way can make finding a manipulation more computationally difficult.

AAAI Conference 2012 Conference Paper

Evaluating Resistance to False-Name Manipulations in Elections

• Bo Waggoner
• Lirong Xia
• Vincent Conitzer

In many mechanisms (especially online mechanisms), a strategic agent can influence the outcome by creating multiple false identities. We consider voting settings where the mechanism designer cannot completely prevent false-name manipulation, but may use false-name-limiting methods such as CAPTCHAs to influence the amount and characteristics of such manipulation. Such a designer would prefer, first, a high probability of obtaining the “correct” outcome, and second, a statistical method for evaluating the correctness of the outcome. In this paper, we focus on settings with two alternatives. We model voters as independently drawing a number of identities from a distribution that may be influenced by the choice of the false-name-limiting method. We give a criterion for the evaluation and comparison of these distributions. Then, given the results of an election in which false-name manipulation may have occurred, we propose and justify a statistical test for evaluating the outcome.

AAMAS Conference 2012 Conference Paper

Lot-based Voting Rules

• Toby Walsh
• Lirong Xia

The Internet Engineering Task Force develops and promotes Internet standards like TCP/IP. The chair of the Task Force is chosen by an election which starts with a set of voters being selected at random from the electorate of volunteers. Selecting decision makers by lottery like this has a long and venerable history, having been used in Athenian democracy over two millennia ago, as well as for over 500 years from the 13th Century to elect the Doge of Venice. In this paper, we consider using such lotteries in multi-agent decision making. We study a family of voting rules called lot-based voting rules. Such rules have two steps: in the first step, $k$ votes are selected by a lottery, then in the second round (the runoff), a voting rule is applied to select the winner based on these $k$ votes. We study some normative properties of such lot-based rules. We also investigate the computational complexity of computing the winner with weighted and unweighted votes, and of computing manipulations. We show that for most lot-based voting rules winner determination and manipulation are computationally hard. Our results suggest that this general technique (using lotteries to selecting some voters randomly) may help to prevent strategic behavior of the voters from a computational point of view.

KR Conference 2012 Conference Paper

Paradoxes of Multiple Elections: An Approximation Approach

• Vincent Conitzer
• Lirong Xia

When agents need to make decisions on multiple issues, applying common voting rules becomes computationally hard due to the exponentially large number of alternatives. One computationally efficient solution is to vote on the issues sequentially. In this paper, we investigate how well the winner under the sequential voting process approximates the winners under some common voting rules that admit natural scoring functions that can serve as a basis for approximation results. We focus on multi-issue domains where each issue is binary and the agents’ preferences are O-legal, separable, represented by LP-trees, or lexicographic. We show some generalized paradoxes of multiple elections: Sequential voting does not approximate many common voting rules well even when the preferences are O-legal or separable. However, these paradoxes are much alleviated or even completely avoided when the preferences are lexicographic or represented by LP-trees. Our results thus draw a border for conditions under which sequential voting rules, which have extremely low computational and communicational cost, are good approximations of some common voting rules w. r. t. their corresponding scoring functions.

NeurIPS Conference 2012 Conference Paper

Random Utility Theory for Social Choice

• Hossein Azari
• David Parks
• Lirong Xia

Random utility theory models an agents preferences on alternatives by drawing a real-valued score on each alternative (typically independently) from a parameterized distribution, and then ranking the alternatives according to scores. A special case that has received signicant attention is the Plackett-Luce model, for which fast inference methods for maximum likelihood estimators are available. This paper develops conditions on general random utility models that enable fast inference within a Bayesian framework through MC-EM, providing concave loglikelihood functions and bounded sets of global maxima solutions. Results on both real-world and simulated data provide support for the scalability of the approach and capability for model selection among general random utility models including Plackett-Luce.

ECAI Conference 2012 Conference Paper

The Possible Winner Problem with Uncertain Weights

• Dorothea Baumeister
• Magnus Roos
• Jörg Rothe
• Lena Schend
• Lirong Xia

The original possible winner problem is: Given an unweighted election with partial preferences and a distinguished candidate c, can the preferences be extended to total ones such that c wins? We introduce a novel variant of this problem in which not some of the voters' preferences are uncertain but some of their weights. Not much has been known previously about the weighted possible winner problem. We present a general framework to study this problem, both for integer and rational weights, with and without upper bounds on the total weight to be distributed, and with and without ranges to choose the weights from. We study the complexity of these problems for important voting systems such as scoring rules, Copeland, ranked pairs, plurality with runoff, and (simplified) Bucklin and fall-back voting.

IJCAI Conference 2011 Conference Paper

A Maximum Likelihood Approach towards Aggregating Partial Orders

• Lirong Xia
• Vincent Conitzer

In many of the possible applications as well as the theoretical models of computational social choice, the agents' preferences are represented as partialorders. In this paper, we extend the maximum likelihood approach for defining "optimal" voting rules to this setting. We consider distributions in which the pairwise comparisons / incomparabilities between alternatives are drawn i. i. d. We call suchmodels pairwise-independentmodels and show that they correspond to a class of voting rules that we call pairwise scoring rules. This generalizes rulessuch as Kemeny and Borda. Moreover, we show that Borda is the only pairwise scoring rule that satisfies neutrality, when the outcome space is the set of all alternatives. We then study which voting rules defined for linear orders can be extended to partial orders via our MLE model. We show that any weakly neutral outcome scoring rule (includingany ranking/candidate scoring rule) based onthe weighted majority graph can be represented as the MLE of a weakly neutral pairwise-independent model. Therefore, all such rules admit natural extensionsto profiles of partial orders. Finally, we propose a specific MLE model &pi; k for generating a set of k winning alternatives, and study the computational complexity of winner determination for the MLE of &pi; k.

IJCAI Conference 2011 Conference Paper

An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments

• Lirong Xia
• David M. Pennock

Computing the market maker price of a security in a combinatorial prediction market is #P-hard. We devise a fully polynomial randomized approximation scheme (FPRAS) that computes the price of any security in disjunctive normal form (DNF) within an &epsilon; multiplicative error factor in time polynomial in 1&epsilon; and the size of the input, with high probability and under reasonable assumptions. Our algorithm is a Monte-Carlo technique based on importance sampling. The algorithm can also approximately price securities represented in conjunctive normal form (CNF) with additive error bounds. To illustrate the applicability of our algorithm, we show that many securities in Yahoo! 's popular combinatorial prediction market game called Predictalot can be represented by DNF formulas of polynomial size.

AAAI Conference 2011 Conference Paper

Dominating Manipulations in Voting with Partial Information

• Vincent Conitzer
• Toby Walsh
• Lirong Xia

We consider manipulation problems when the manipulator only has partial information about the votes of the nonmanipulators. Such partial information is described by an information set, which is the set of profiles of the nonmanipulators that are indistinguishable to the manipulator. Given such an information set, a dominating manipulation is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator’s information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.

IJCAI Conference 2011 Conference Paper

Hypercubewise Preference Aggregation in Multi-Issue Domains

• Vincent Conitzer
• J
• eacute; r
• ocirc; me Lang
• Lirong Xia

We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of each edge of the hypercube is decided according to the majority rule. First we focus on hypercube Condorcet winners (HCWs); in particular, we show that, assuming a uniform distribution for the CP-nets, the probability that there exists at least one HCW is at least 1-1/e, and the expected number of HCWs is 1. Our experimental results confirm these results. We also show experimental results under the Impartial Culture assumption. We then generalize a few tournament solutions to select winners from (weighted) majoritarian CP-nets, namely Copeland, maximin, and Kemeny. For each of these, we address some social choice theoretic and computational issues.

AAAI Conference 2011 Conference Paper

Manipulation of Nanson’s and Baldwin’s Rules

• Nina Narodytska
• Toby Walsh
• Lirong Xia

Nanson’s and Baldwin’s voting rules select a winner by successively eliminating candidates with low Borda scores. We show that these rules have a number of desirable computational properties. In particular, with unweighted votes, it is NP-hard to manipulate either rule with one manipulator, whilst with weighted votes, it is NP-hard to manipulate either rule with a small number of candidates and a coalition of manipulators. As only a couple of other voting rules are known to be NP-hard to manipulate with a single manipulator, Nanson’s and Baldwin’s rules appear to be particularly resistant to manipulation from a theoretical perspective. We also propose a number of approximation methods for manipulating these two rules. Experiments demonstrate that both rules are often difficult to manipulate in practice. These results suggest that elimination style voting rules deserve further study.

AAMAS Conference 2011 Conference Paper

Possible Winners When New Alternatives Join: New Results Coming Up!

• Lirong Xia
• ocirc; me Lang
• J
• eacute; r
• ocirc; me Monnot

In a voting system, sometimes multiple new alternatives will join the election after the voters' preferences over the initial alternatives have been revealed. Computing whether a given alternative can be a co-winner when multiple new alternatives join the election is called the possible co-winner with new alternatives (PcWNA) problem and was introduced by (Chevaleyre et al. , 2010). In this paper, we show that the PcWNA problems are NP-complete for the Bucklin, Copeland _0, and maximin (a. k. a. Simpson) rule, even when the number of new alternatives is no more than a constant. We also show that the PcWNA problem can be solved in polynomial time for plurality with runoff. For the approval rule, we examine three different ways to extend a linear order with new alternatives, and characterize the computational complexity of the PcWNA problem for each of them.

UAI Conference 2011 Conference Paper

Price Updating in Combinatorial Prediction Markets with Bayesian Networks

• David M. Pennock
• Lirong Xia

To overcome the #P-hardness of computing/updating prices in logarithm market scoring rule-based (LMSR-based) combinatorial prediction markets, Chen et al. [5] recently used a simple Bayesian network to represent the prices of securities in combinatorial predictionmarkets for tournaments, and showed that two types of popular securities are structure preserving. In this paper, we significantly extend this idea by employing Bayesian networks in general combinatorial prediction markets. We reveal a very natural connection between LMSR-based combinatorial prediction markets and probabilistic belief aggregation,which leads to a complete characterization of all structure preserving securities for decomposable network structures. Notably, the main results by Chen et al. [5] are corollaries of our characterization. We then prove that in order for a very basic set of securities to be structure preserving, the graph of the Bayesian network must be decomposable. We also discuss some approximation techniques for securities that are not structure preserving.

AAMAS Conference 2010 Conference Paper

Aggregating Preferences in Multi-Issue Domains by Using Maximum Likelihood Estimators

• Lirong Xia
• Vincent Conitzer
• Jerome Lang

In this paper, we study a maximum likelihood estimation (MLE)approach to voting when the set of alternatives has a multi-issuestructure, and the voters' preferences are represented by CP-nets. We first consider general multi-issue domains, and study whetherand how issue-by-issue voting rules and sequential voting rulescan be represented by MLEs. We first show that issue-by-issuevoting rules in which each local rule is itself an MLE (resp. acandidate scoring rule) can be represented by MLEs with a weak(resp. strong) decomposability property. Then, we prove two theorems that state that if the noise model satisfies a very weak decomposability property, then no sequential voting rule that satisfiesunanimity can be represented by an MLE, unless the number ofvoters is bounded. We then consider multi-issue domains in which each issue isbinary; for these, we propose a general family of distance-basednoise models, of which give an axiomatic characterization. Wethen propose a more specific family of natural distance-based noisemodels that are parameterized by a threshold. We identify the complexity of winner determination for the corresponding MLE votingrule in the two most important subcases of this framework.

AAAI Conference 2010 Conference Paper

Compilation Complexity of Common Voting Rules

• Lirong Xia
• Vincent Conitzer

In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as the votes of voters outside the subelectorate, we can conclude which of the m alternatives wins. This corresponds to the notion of compilation complexity, the minimum number of bits required to summarize the votes for a particular rule, which was introduced by Chevaleyre et al. [IJCAI- 09]. We study three different types of compilation complexity. The first, studied by Chevaleyre et al. , depends on the size of the subelectorate but not on the size of the complement (the voters outside the subelectorate). The second depends on the size of the complement but not on the size of the subelectorate. The third depends on both. We first investigate the relations among the three types of compilation complexity. Then, we give upper and lower bounds on all three types of compilation complexity for the most prominent voting rules. We show that for l-approval (when l ≤ m/2), Borda, and Bucklin, the bounds for all three types are asymptotically tight, up to a multiplicative constant; for l-approval (when l > m/2), plurality with runoff, all Condorcet consistent rules that are based on unweighted majority graphs (including Copeland and voting trees), and all Condorcet consistent rules that are based on the order of pairwise elections (including ranked pairs and maximin), the bounds for all three types are asymptotically tight up to a multiplicative constant when the sizes of the subelectorate and its complement are both larger than m1+ for some > 0.

SODA Conference 2010 Conference Paper

Incentive Compatible Budget Elicitation in Multi-unit Auctions

• Sayan Bhattacharya
• Vincent Conitzer
• Kamesh Munagala
• Lirong Xia

AAAI Conference 2010 Conference Paper

Stackelberg Voting Games: Computational Aspects and Paradoxes

• Lirong Xia
• Vincent Conitzer

We consider settings in which voters vote in sequence, each voter knows the votes of the earlier voters and the preferences of the later voters, and voters are strategic. This can be modeled as an extensive-form game of perfect information, which we call a Stackelberg voting game. We first propose a dynamic-programming algorithm for finding the backward-induction outcome for any Stackelberg voting game when the rule is anonymous; this algorithm is efficient if the number of alternatives is no more than a constant. We show how to use compilation functions to further reduce the time and space requirements. Our main theoretical results are paradoxes for the backwardinduction outcomes of Stackelberg voting games. We show that for any n ≥ 5 and any voting rule that satisfies nonimposition and with a low domination index, there exists a profile consisting of n voters, such that the backwardinduction outcome is ranked somewhere in the bottom two positions in almost every voter’s preferences. Moreover, this outcome loses all but one of its pairwise elections. Furthermore, we show that many common voting rules have a very low (= 1) domination index, including all majorityconsistent voting rules. For the plurality and nomination rules, we show even stronger paradoxes. Finally, using our dynamic-programming algorithm, we run simulations to compare the backward-induction outcome of the Stackelberg voting game to the winner when voters vote truthfully, for the plurality and veto rules. Surprisingly, our experimental results suggest that on average, more voters prefer the backward-induction outcome.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Jérôme Lang

Sequential voting rules and correspondences provide a way for agents to make group decisions when the set of available options has a multi-issue structure. One important question about sequential voting rules (correspondences) is whether they satisfy two crucial criteria, namely neutrality and ef- ficiency. Recently, Benoit and Kornhauser established an important result about seat-by-seat voting rules (which are a special case of sequential voting rules): they proved that if the multi-issue domain satisfies some properties, then the only seat-by-seat rules being either efficient or neutral are dictatorships. However, there are still some cases not covered by their results, including a very important and interesting case—voting correspondences. In this paper, we extend the impossibility theorems by Benoit and Kornhauser to voting correspondences, and obtain a dichotomy theorem on the existence of efficient or neutral sequential (seat-by-seat) voting rules and correspondences. Therefore, the question of whether sequential (seat-by-seat) voting rules (correspondences) can be efficient or neutral is now completely answered.

IJCAI Conference 2009 Conference Paper

• Vincent Conitzer
• Matthew Rognlie
• Lirong Xia

In social choice, a preference function (PF) takes a set of votes (linear orders over a set of alternatives) as input, and produces one or more rankings (also linear orders over the alternatives) as output. Such functions have many applications, for example, aggregating the preferences of multiple agents, or merging rankings (of, say, webpages) into a single ranking. The key issue is choosing a PF to use. One natural and previously studied approach is to assume that there is an unobserved “correct” ranking, and the votes are noisy estimates of this. Then, we can use the PF that always chooses the maximum likelihood estimate (MLE) of the correct ranking. In this paper, we define simple ranking scoring functions (SRSFs) and show that the class of neutral SRSFs is exactly the class of neutral PFs that are MLEs for some noise model. We also de- fine composite ranking scoring functions (CRSFs) and show a condition under which these coincide with SRSFs. We study key properties such as consistency and continuity, and consider some example PFs. In particular, we study Single Transferable Vote (STV), a commonly used PF, showing that it is a CRSF but not an SRSF, thereby clarifying the extent to which it is an MLE function. This also gives a new perspective on how ties should be broken under STV. We leave some open questions.

IJCAI Conference 2009 Conference Paper

• Vincent Conitzer
• Jérôme Lang
• Lirong Xia

Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach is to vote on the issues one at a time, in sequence; however, a drawback is that the outcome may depend on the order in which the issues are voted upon and decided, which gives the chairperson some control over the outcome of the election because she can strategically determine the order. While this is undeniably a negative feature of sequential voting, in this paper we temper this judgment by showing that the chairperson’s control problem is, in most cases, computationally hard.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Vincent Conitzer

An important problem in computational social choice concerns whether it is possible to prevent manipulation of voting rules by making it computationally intractable. To answer this, a key question is how frequently voting rules are manipulable. We [Xia and Conitzer, 2008] recently defined the class of generalized scoring rules (GSRs) and characterized the frequency of manipulability for such rules. We showed, by examples, that most common rules seem to fall into this class. However, no natural axiomatic characterization of the class was given, leaving the possibility that there are natural rules to which these results do not apply. In this paper, we characterize the class of GSRs based on two natural properties: it is equal to the class of rules that are anonymous and finitely locally consistent. Generalized scoring rules also have other uses in computational social choice. For these uses, the order of the GSR (the dimension of its score vector) is important. Our characterization result implies that the order of a GSR is related to the minimum number of locally consistent components of the rule. We proceed to bound the minimum number of locally consistent components for some common rules.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Michael Zuckerman
• Ariel D. Procaccia
• Vincent Conitzer
• Jeffrey S. Rosenschein

Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.

AAAI Conference 2008 Conference Paper

Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders

• Lirong Xia

Usually a voting rule or correspondence requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a profile of partial orders and a candidate c, two important questions arise: first, is c guaranteed to win, and second, is it still possible for c to win? These are the necessary winner and possible winner problems, respectively. We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We prove that for Copeland, maximin, Bucklin, and ranked pairs, the possible winner problem is NP-complete; also, we give a sufficient condition on scoring rules for the possible winner problem to be NP-complete (Borda satisfies this condition). We also prove that for Copeland and ranked pairs, the necessary winner problem is coNP-complete. All the hardness results hold even when the number of undetermined pairs in each vote is no more than a constant. We also present polynomial-time algorithms for the necessary winner problem for scoring rules, maximin, and Bucklin.

AAAI Conference 2008 Conference Paper

Voting on Multiattribute Domains with Cyclic Preferential Dependencies

• Lirong Xia

In group decision making, often the agents need to decide on multiple attributes at the same time, so that there are exponentially many alternatives. In this case, it is unrealistic to ask agents to communicate a full ranking of all the alternatives. To address this, earlier work has proposed decomposing such voting processes by using local voting rules on the individual attributes. Unfortunately, the existing methods work only with rather severe domain restrictions, as they require the voters’ preferences to extend acyclic CP-nets compatible with a common order on the attributes. We first show that this requirement is very restrictive, by proving that the number of linear orders extending an acyclic CP-net is exponentially smaller than the number of all linear orders. Then, we introduce a very general methodology that allows us to aggregate preferences when voters express CP-nets that can be cyclic. There does not need to be any common structure among the submitted CP-nets. Our methodology generalizes the earlier, more restrictive methodology. We study whether properties of the local rules transfer to the global rule, and vice versa. We also address how to compute the winning alternatives.

SODA Conference 2007 Conference Paper

Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree

• Jing Xiao
• Lan Liu 0001
• Lirong Xia
• Tao Jiang 0001

TARK Conference 2007 Conference Paper

Sequential voting rules and multiple elections paradoxes

• Lirong Xia
• Jérôme Lang
• Mingsheng Ying

Multiple election paradoxes arise when voting separately on each issue from a set of related issues results in an obviously undesirable outcome. Several authors have argued that a sufficient condition for avoiding multiple election paradoxes is the assumption that voters have separable preferences. We show that this extremely demanding restriction can be relaxed into the much more reasonable one: there exists a linear order x1 >. .. > xp on the set of issues such that for each voter, every issue xi is preferentially independent of xi+1, .. ., xp given x1, .. ., xi−1. This leads us to define a family of sequential voting rules, defined as the sequential composition of local voting rules. These rules relate to the setting of conditional preference networks (CP-nets) recently developed in the Artificial Intelligence literature. We study in detail how these sequential rules inherit, or do not inherit, the properties of their local components. We focus on the case of multiple referenda, corresponding to multiple elections with binary issues.

AAAI Conference 2007 Conference Paper

Strongly Decomposable Voting Rules on Multiattribute Domains

• Lirong Xia

Sequential composition of voting rules, by making use of structural properties of the voters’ preferences, provide computationally economical ways for making a common decision over a Cartesian product of finite local domains. A sequential composition is usually defined on a set of legal profiles following a fixed order. In this paper, we generalize this by order-independent sequential composition and strong decomposability, which are independent of the chosen order. We study to which extent some usual properties of voting rules transfer from the local rules to their order-independent sequential composition. Then, to capture the idea that a voting rule is neutral or decomposable on a slightly smaller domain, we define nearly neutral, nearly decomposable rules for both sequential composition and order-independent sequential composition, which leads us to defining and studying decomposable permutations. We prove that any sequential composition of neutral local rules and any order-independent sequential composition of neutral local rules satisfying a necessary condition are nearly neutral.