Arrow Research search

Author name cluster

Nicholas Mattei

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

53 papers
2 author rows

Possible papers

53

AAMAS Conference 2026 Conference Paper

Computational Social Choice: Research & Development

  • Dorothea Baumeister
  • Ratip Emin Berker
  • Niclas Boehmer
  • Sylvain Bouveret
  • Andreas Darmann
  • Piotr Faliszewski
  • Martin Lackner
  • Jérôme Lang

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. We articulate the defining features of COMSOC-R&D, argue for its value, and discuss various roadblocks and possible solutions.

PDF

AAAI Conference 2026 Conference Paper

Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits

  • Tianyi Xu
  • Jiaxin Liu
  • Nicholas Mattei
  • Zizhan Zheng

We propose a multi-agent multi-armed bandit (MA-MAB) framework to ensure fair outcomes across agents while maximizing overall system performance. For example, in a ridesharing setting where a central dispatcher assigns drivers to distinct geographic regions, utilitarian welfare (the sum of driver earnings) can be highly skewed—some drivers may receive no rides. We instead measure fairness by Nash social welfare, i.e., the product of individual rewards. A key challenge in this setting is decision-making under limited information about arm rewards (geographic regions). To address this, we introduce a novel probing mechanism that strategically gathers information about selected arms before assignment. In the offline setting, where reward distributions are known, we exploit submodularity to design a greedy probing algorithm with a constant-factor approximation guarantee. In the online setting, we develop a probing-based algorithm that achieves sublinear regret while preserving Nash social welfare. Extensive experiments on synthetic and real-world datasets demonstrate that our approach outperforms baseline methods in both fairness and efficiency.

PDF Details DOI

AAMAS Conference 2026 Conference Paper

Optimizing Voting Rules for Social Welfare and Beyond

  • Ben Armstrong
  • Hrishi Kabra
  • Nicholas Mattei

We present a website and Python package, optimal_voting, that provides tools for finding the positional scoring rule (PSR) that optimizes for a user-selected target function over a (set of) profiles. The web interface provides an intuitive interface for creating profiles, analyzing them, and exploring various PSRs; while the library provides extensive functionality for researchers and system implementers. By formulating finding the optimal PSR within a larger optimization system, the target of the optimization can be any of a number of widely studied functions including classical social welfare functions (utilitarian, egalitarian, Nash), distortion, or axiom violation rate. By restricting optimization to positional scoring rules we ensure that our results are intuitively explainable. Our library has already been used to generate significant results for two papers and can be directly applied to several further settings.

PDF

AAAI Conference 2026 Conference Paper

The Illusion of Fairness: Auditing Fairness Interventions in Algorithmic Hiring with Audit Studies

  • Disa Sariola
  • Patrick Button
  • Aron Culotta
  • Nicholas Mattei

Classifiers trained on historical data are deployed in the real world to automate decisions from hiring to loan issuance. Judging the fairness and efficiency of these systems, and their human counterparts, is a complex and important topic studied across both computational and social sciences. One common way to address bias in classifiers is to resample the training data to offset distributional disparities. In the hiring domain, where results may vary by a protected class, many interventions from the literature equalize the hiring rate within the training set to alleviate bias. While simple and seemingly effective, these methods have typically only been evaluated using data obtained through convenience samples, e.g., data from a real-world hiring process, introducing selection and label bias. In the social and health sciences, audit studies, in which fictitious "testers" (resumes) are sent to subjects (job openings) in a randomized control trial, provide high-quality data that support rigorous estimates of discrimination by controlling for confounding factors. We investigate how data from audit studies can be used to improve our ability to both train and evaluate automated hiring algorithms. Specifically, we use data from a large audit study of age discrimination in hiring to test common resampling methods from the fair machine learning literature. We find that audit data of real-world hiring reveals cases where equalizing base rates across classes appears to achieve parity using traditional measures, but in fact has an absolute ~10% disparity when measured appropriately. We also show that corrections based on individual treatment effect estimation methods combined with audit study data can overcome these issues, underscoring the need for rigorous data collection in fairness research.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

When Is It Acceptable to Break the Rules? Knowledge Representation of Moral Judgements Based on Empirical Data (Extended Abstract)

  • Edmond Awad
  • Sydney Levine
  • Andrea Loreggia
  • Nicholas Mattei
  • Iyad Rahwan
  • Francesca Rossi
  • Kartik Talamadupula
  • Joshua Tenenbaum

This paper explores how humans make contextual moral judgments to inform the development of AI systems capable of balancing rulefollowing with flexibility. We investigate the limitations of rigid constraints in AI, which can hinder morally acceptable actions in specific contexts, unlike humans who can override rules when appropriate. We propose a preference-based graphical model inspired by dual-process theories of moral judgment and conduct a study on human decisions about breaking the social norm of "no cutting in line. " Our model outperforms standard machine learning methods in predicting human judgments and offers a generalizable framework for modeling moral decision-making across various contexts. This short paper summarizes the main findings of our paper published in the journal Autonomous Agents and Multi-Agent Systems. [2]

PDF

AAMAS Conference 2025 Conference Paper

Who Reviews The Reviewers? A Multi-Level Jury Problem

  • Ben Abramowitz
  • Omer Lev
  • Nicholas Mattei

We consider the problem of determining a binary ground truth using advice from a group of independent reviewers (experts) who express their guess about a ground truth correctly with some independent probability (competence) 𝑝𝑖. In this setting, when all reviewers are competent with 𝑝 ≥ 0. 5, the Condorcet Jury Theorem tells us that adding more reviewers increases the overall accuracy, and if all 𝑝𝑖’s are known, then there exists an optimal weighting of the reviewers. However, in practical settings, reviewers may be noisy or incompetent, i. e. , 𝑝𝑖 ≤ 0. 5, and the number of experts may be small, so the asymptotic Condorcet Jury Theorem is not practically relevant. In such cases we explore appointing one or more chairs (judges) who determine the weight of each reviewer for aggregation, creating multiple levels. However, these chairs may be unable to correctly identify the competence of the reviewers they oversee, and therefore unable to compute the optimal weighting. We give conditions on when a set of chairs is able to weight the reviewers optimally, and depending on the competence distribution of the agents, give results about when it is better to have more chairs or more reviewers. Through simulations we show that in some cases it is better to have more chairs, but in many cases it is better to have more reviewers.

PDF

AAMAS Conference 2023 Conference Paper

Does Delegating Votes Protect Against Pandering Candidates?

  • Xiaolin Sun
  • Jacob Masur
  • Ben Abramowitz
  • Nicholas Mattei
  • Zizhan Zheng

The election of representatives in regular election cycles ostensibly prevents misbehavior by elected officials and keeps them accountable in service of the “will of the people. " This democratic ideal can be undermined if candidates campaign dishonestly when seeking office over one or more election cycles or ‘rounds’. We introduce a novel formal model of pandering, or strategic preference reporting by electoral candidates, and examine the resilience of two democratic voting systems to such pandering. The two voting systems we compare are Representative Democracy (RD) and Flexible Representative Democracy (FRD). For each voting system, our analysis centers on the types of strategies candidates employ and how voters update their views of candidates across rounds based on how the candidates have pandered in the past. We provide theoretical results on the complexity of pandering for a single round, formulate our problem for multiple rounds as a Markov Decision Process, and use reinforcement learning to study the effects of pandering by sets of candidates across a number of rounds.

PDF

AAMAS Conference 2023 Conference Paper

Mitigating Skewed Bidding for Conference Paper Assignment

  • Inbal Rozenzweig
  • Reshef Meir
  • Nicholas Mattei
  • Ofra Amir

The explosion of conference paper submissions in AI and related fields has underscored the need to improve many aspects of the peer review process, especially the matching of papers and reviewers. Recent work argues that the key to improve this matching is to modify aspects of the bidding phase itself, to ensure that the set of bids over papers is balanced, and in particular to avoid orphan papers, i. e. , those papers that receive no bids. In an attempt to understand and mitigate this problem, we have developed a flexible bidding platform to test adaptations to the bidding process. Using this platform, we performed a field experiment during the bidding phase of a medium-size international workshop that compared two bidding methods. We further examined via controlled experiments on Amazon Mechanical Turk various factors that affect bidding, in particular the order in which papers are presented [11, 17]; and information on paper demand [33]. Our results suggest that several simple adaptations, that can be added to any existing platform, may significantly reduce the skew in bids, thereby improving the allocation for both reviewers and conference organizers.

PDF

UAI Conference 2023 Conference Paper

Pandering in a (flexible) representative democracy

  • Xiaolin Sun 0002
  • Jacob Masur
  • Ben Abramowitz
  • Nicholas Mattei
  • Zizhan Zheng

In representative democracies, regular election cycles are supposed to prevent misbehavior by elected officials, hold them accountable, and subject them to the “will of the people. " Pandering, or dishonest preference reporting by candidates campaigning for election, undermines this democratic idea. Much of the work on Computational Social Choice to date has investigated strategic actions in only a single election. We introduce a novel formal model of pandering and examine the resilience of two voting systems, Representative Democracy (RD) and Flexible Representative Democracy (FRD), to pandering within a single election and across multiple rounds of elections. For both voting systems, our analysis centers on the types of strategies candidates employ and how voters update their views of candidates based on how the candidates have pandered in the past. We provide theoretical results on the complexity of pandering in our setting for a single election, formulate our problem for multiple cycles as a Markov Decision Process, and use reinforcement learning to study the effects of pandering by single candidates and groups of candidates over many rounds.

Details

AIJ Journal 2023 Journal Article

PeerNomination: A novel peer selection algorithm to handle strategic and noisy assessments

  • Omer Lev
  • Nicholas Mattei
  • Paolo Turrini
  • Stanislav Zhydkov

In peer selection a group of agents must choose a subset of themselves, as winners for, e. g. , peer-reviewed grants or prizes. We take a Condorcet view of this aggregation problem, assuming that there is an objective ground-truth ordering over the agents. We study agents that have a noisy perception of this ground truth and give assessments that, even when truthful, can be inaccurate. Our goal is to select the best set of agents according to the underlying ground truth by looking at the potentially unreliable assessments of the peers. Besides being potentially unreliable, we also allow agents to be self-interested, attempting to influence the outcome of the decision in their favour. Hence, we are focused on tackling the problem of impartial (or strategyproof) peer selection – how do we prevent agents from manipulating their reviews while still selecting the most deserving individuals, all in the presence of noisy evaluations? We propose a novel impartial peer selection algorithm, PeerNomination, that aims to fulfil the above desiderata. We provide a comprehensive theoretical analysis of the recall of PeerNomination and prove various properties, including impartiality and monotonicity. We also provide empirical results based on computer simulations to show its effectiveness compared to the state-of-the-art impartial peer selection algorithms. We then investigate the robustness of PeerNomination to various levels of noise in the reviews. In order to maintain good performance under such conditions, we extend PeerNomination by using weights for reviewers which, informally, capture some notion of reliability of the reviewer. We show, theoretically, that the new algorithm preserves strategyproofness and, empirically, that the weights help identify the noisy reviewers and hence to increase selection performance. 1

Details DOI

AAMAS Conference 2023 Conference Paper

Social Mechanism Design: A Low-Level Introduction

  • Ben Abramowitz
  • Nicholas Mattei

When it comes to collective decisions, we have to deal with the fact that agents have preferences over both decision outcomes and how decisions are made. If we create rules for aggregating preferences over rules, and rules for preferences over rules for preferences over rules, and so on, it would appear that we run into infinite regress with preferences and rules at successively higher “levels. ” The starting point of our analysis is the claim that such regress should not be a problem in practice, as any such preferences will necessarily be bounded in complexity and structured coherently in accordance with some (possibly latent) normative principles. Our core contributions are (1) the identification of simple, intuitive preference structures at low levels that can be generalized to form the building blocks of preferences at higher levels, and (2) the development of algorithms for maximizing the number of agents with such low-level preferences who will “accept” a decision. We analyze algorithms for acceptance maximization in two different domains: asymmetric dichotomous choice and constitutional amendment. In both settings we study the worst-case performance of the appropriate algorithms, and reveal circumstances under which universal acceptance is possible. In particular, we show that constitutional amendment procedures proposed recently by Abramowitz et al. [2] can achieve universal acceptance.

PDF

NeSy Conference 2022 Conference Paper

Combining Fast and Slow Thinking for Human-like and Efficient Decisions in Constrained Environments

  • Marianna Bergamaschi Ganapini
  • Murray Campbell
  • Francesco Fabiano
  • Lior Horesh
  • Jonathan Lenchner
  • Andrea Loreggia
  • Nicholas Mattei
  • Francesca Rossi 0001

Current AI systems lack several important human capabilities, such as adaptability, generalizability, selfcontrol, consistency, common sense, and causal reasoning. We believe that existing cognitive theories of human decision making, such as the thinking fast and slow theory, can provide insights on how to advance AI systems towards some of these capabilities. In this paper, we propose a general architecture that is based on fast/slow solvers and a metacognitive component. We then present experimental results on the behavior of an instance of this architecture, for AI systems that make decisions about navigating in a constrained environment. We show how combining the fast and slow decision modalities, which can be implemented by learning and reasoning components respectively, allows the system to evolve over time and gradually pass from slow to fast thinking with enough experience, and that this greatly helps in decision quality, resource consumption, and efficiency.

Details

AAMAS Conference 2022 Conference Paper

Group Fairness in Bandits with Biased Feedback

  • Candice Schumann
  • Zhi Lang
  • Nicholas Mattei
  • John P. Dickerson

We propose a novel formulation of group fairness with biased feedback in the contextual multi-armed bandit (CMAB) setting. In the CMAB setting, a sequential decision maker must, at each time step, choose an arm to pull from a finite set of arms after observing some context for each of the potential arm pulls. In our model, arms are partitioned into two or more sensitive groups based on some protected feature(s) (e. g. , age, race, or socio-economic status). Initial rewards received from pulling an arm may be distorted due to some unknown societal or measurement bias. We assume that in reality these groups are equal despite the biased feedback received by the agent. To alleviate this, we learn a societal bias term which can be used to both find the source of bias and to potentially fix the problem outside of the algorithm. We provide a novel algorithm that can accommodate this notion of fairness for an arbitrary number of groups, and provide a theoretical bound on the regret for our algorithm. We validate our algorithm using synthetic data and two real-world datasets for intervention settings wherein we want to allocate resources fairly across groups.

PDF

TCS Journal 2022 Journal Article

Stable matching with uncertain pairwise preferences

  • Haris Aziz
  • Péter Biró
  • Tamás Fleiner
  • Serge Gaspers
  • Ronald de Haan
  • Nicholas Mattei
  • Baharak Rastegari

We study a two-sided matching problem under preferences, where the agents have independent pairwise comparisons on their possible partners and these preferences may be uncertain. Preferences may be intransitive and agents may even have cycles in their preferences; e. g. an agent a may prefer b to c, c to d, and d to b, all with probability one. If an instance has such a cycle, then there may not exist any matching that is stable with positive probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i. e. , matchings whose probability of being stable is positive or one, respectively. We show that finding possibly stable matchings is NP-hard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences.

Details DOI

AAAI Conference 2021 Conference Paper

A Market-Inspired Bidding Scheme for Peer Review Paper Assignment

  • Reshef Meir
  • Jérôme Lang
  • Julien Lesca
  • Nicholas Mattei
  • Natan Kaminsky

We propose a market-inspired bidding scheme for the assignment of paper reviews in large academic conferences. We provide an analysis of the incentives of reviewers during the bidding phase, when reviewers have both private costs and some information about the demand for each paper; and their goal is to obtain the best possible k papers for a predetermined k. We show that by assigning ‘budgets’ to reviewers and a ‘price’ for every paper that is (roughly) proportional to its demand, the best response of a reviewer is to bid sincerely, i. e. , on her most favorite papers, and match the budget even when it is not enforced. This game-theoretic analysis is based on a simple, prototypical assignment algorithm. We show via extensive simulations on bidding data from real conferences, that our bidding scheme would substantially improve both the bid distribution and the resulting assignment.

PDF Details

NeurIPS Conference 2021 Conference Paper

Causal Inference for Event Pairs in Multivariate Point Processes

  • Tian Gao
  • Dharmashankar Subramanian
  • Debarun Bhattacharjya
  • Xiao Shou
  • Nicholas Mattei
  • Kristin P Bennett

Causal inference and discovery from observational data has been extensively studied across multiple fields. However, most prior work has focused on independent and identically distributed (i. i. d. ) data. In this paper, we propose a formalization for causal inference between pairs of event variables in multivariate recurrent event streams by extending Rubin's framework for the average treatment effect (ATE) and propensity scores to multivariate point processes. Analogous to a joint probability distribution representing i. i. d. data, a multivariate point process represents data involving asynchronous and irregularly spaced occurrences of various types of events over a common timeline. We theoretically justify our point process causal framework and show how to obtain unbiased estimates of the proposed measure. We conduct an experimental investigation using synthetic and real-world event datasets, where our proposed causal inference framework is shown to exhibit superior performance against a set of baseline pairwise causal association scores.

PDF Details

AAAI Conference 2021 Conference Paper

Modeling Voters in Multi-Winner Approval Voting

  • Jaelle Scheuerman
  • Jason Harman
  • Nicholas Mattei
  • K. Brent Venable

In many real world situations, collective decisions are made using voting and, in scenarios such as committee or board elections, employing voting rules that return multiple winners. In multi-winner approval voting (AV), an agent submits a ballot consisting of approvals for as many candidates as they wish, and winners are chosen by tallying up the votes and choosing the top-k candidates receiving the most approvals. In many scenarios, an agent may manipulate the ballot they submit in order to achieve a better outcome by voting in a way that does not reflect their true preferences. In complex and uncertain situations, agents may use heuristics instead of incurring the additional effort required to compute the manipulation which most favors them. In this paper, we examine voting behavior in single-winner and multi-winner approval voting scenarios with varying degrees of uncertainty using behavioral data obtained from Mechanical Turk. We find that people generally manipulate their vote to obtain a better outcome, but often do not identify the optimal manipulation. There are a number of predictive models of agent behavior in the social choice and psychology literature that are based on cognitively plausible heuristic strategies. We show that the existing approaches do not adequately model our real-world data. We propose a novel model that takes into account the size of the winning set and human cognitive constraints; and demonstrate that this model is more effective at capturing real-world behaviors in multi-winner approval voting scenarios.

PDF Details

JAIR Journal 2021 Journal Article

Reasoning with PCP-Nets

  • Cristina Cornelio
  • Judy Goldsmith
  • Umberto Grandi
  • Nicholas Mattei
  • Francesca Rossi
  • K. Brent Venable

We introduce PCP-nets, a formalism to model qualitative conditional preferences with probabilistic uncertainty. PCP-nets generalise CP-nets by allowing for uncertainty over the preference orderings. We define and study both optimality and dominance queries in PCP-nets, and we propose a tractable approximation of dominance which we show to be very accurate in our experimental setting. Since PCP-nets can be seen as a way to model a collection of weighted CP-nets, we also explore the use of PCP-nets in a multi-agent context, where individual agents submit CP-nets which are then aggregated into a single PCP-net. We consider various ways to perform such aggregation and we compare them via two notions of scores, based on well known voting theory concepts. Experimental results allow us to identify the aggregation method that better represents the given set of CP-nets and the most efficient dominance procedure to be used in the multi-agent context.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Thinking Fast and Slow in AI

  • Grady Booch
  • Francesco Fabiano
  • Lior Horesh
  • Kiran Kate
  • Jonathan Lenchner
  • Nick Linck
  • Andreas Loreggia
  • Keerthiram Murgesan

This paper proposes a research direction to advance AI which draws inspiration from cognitive theories of human decision making. The premise is that if we gain insights about the causes of some human capabilities that are still lacking in AI (for instance, adaptability, generalizability, common sense, and causal reasoning), we may obtain similar capabilities in an AI system by embedding these causal components. We hope that the high-level description of our vision included in this paper, as well as the several research questions that we propose to consider, can stimulate the AI research community to define, try and evaluate new methodologies, frameworks, and evaluation metrics, in the spirit of achieving a better understanding of both human and machine intelligence.

PDF Details

AAAI Conference 2020 Conference Paper

A Multi-Channel Neural Graphical Event Model with Negative Evidence

  • Tian Gao
  • Dharmashankar Subramanian
  • Karthikeyan Shanmugam
  • Debarun Bhattacharjya
  • Nicholas Mattei

Event datasets are sequences of events of various types occurring irregularly over the time-line, and they are increasingly prevalent in numerous domains. Existing work for modeling events using conditional intensities rely on either using some underlying parametric form to capture historical dependencies, or on non-parametric models that focus primarily on tasks such as prediction. We propose a non-parametric deep neural network approach in order to estimate the underlying intensity functions. We use a novel multi-channel RNN that optimally reinforces the negative evidence of no observable events with the introduction of fake event epochs within each consecutive inter-event interval. We evaluate our method against state-of-the-art baselines on model fitting tasks as gauged by log-likelihood. Through experiments on both synthetic and real-world datasets, we find that our proposed approach outperforms existing baselines on most of the datasets studied.

PDF Details

IJCAI Conference 2020 Conference Paper

Cause-Effect Association between Event Pairs in Event Datasets

  • Debarun Bhattacharjya
  • Tian Gao
  • Nicholas Mattei
  • Dharmashankar Subramanian

Causal discovery from observational data has been intensely studied across fields of study. In this paper, we consider datasets involving irregular occurrences of various types of events over the timeline. We propose a suite of scores and related algorithms for estimating the cause-effect association between pairs of events from such large event datasets. In particular, we introduce a general framework and the use of conditional intensity rates to characterize pairwise associations between events. Discovering such potential causal relationships is critical in several domains, including health, politics and financial analysis. We conduct an experimental investigation with synthetic data and two real-world event datasets, where we evaluate and compare our proposed scores using assessments from human raters as ground truth. For a political event dataset involving interaction between actors, we show how performance could be enhanced by enforcing additional knowledge pertaining to actor identities.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Closing the Loop: Bringing Humans into Empirical Computational Social Choice and Preference Reasoning

  • Nicholas Mattei

Research in both computational social choice and preference reasoning uses tools and techniques from computer science, generally algorithms and complexity analysis, to examine topics in group decision making. This has brought tremendous progress in the last decades, creating new avenues for research and results in areas including voting and resource allocation. I argue that of equal importance to the theoretical results are impacts in research and development from the empirical part of the computer scientists toolkit: data, system building, and human interaction. I highlight work by myself and others to establish data driven, application driven research in the computational social choice and preference reasoning areas. Along the way, I highlight interesting application domains and important results from the community in driving this area to make concrete, real-world impact.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Event-Driven Continuous Time Bayesian Networks

  • Debarun Bhattacharjya
  • Karthikeyan Shanmugam
  • Tian Gao
  • Nicholas Mattei
  • Kush Varshney
  • Dharmashankar Subramanian

We introduce a novel event-driven continuous time Bayesian network (ECTBN) representation to model situations where a system’s state variables could be influenced by occurrences of events of various types. In this way, the model parameters and graphical structure capture not only potential “causal” dynamics of system evolution but also the influence of event occurrences that may be interventions. We propose a greedy search procedure for structure learning based on the BIC score for a special class of ECTBNs, showing that it is asymptotically consistent and also effective for limited data. We demonstrate the power of the representation by applying it to model paths out of poverty for clients of CityLink Center, an integrated social service provider in Cincinnati, USA. Here the ECTBN formulation captures the effect of classes/counseling sessions on an individual’s life outcome areas such as education, transportation, employment and financial education.

PDF Details

AAAI Conference 2020 Conference Paper

Infusing Knowledge into the Textual Entailment Task Using Graph Convolutional Networks

  • Pavan Kapanipathi
  • Veronika Thost
  • Siva Sankalp Patel
  • Spencer Whitehead
  • Ibrahim Abdelaziz
  • Avinash Balakrishnan
  • Maria Chang
  • Kshitij Fadnis

Textual entailment is a fundamental task in natural language processing. Most approaches for solving this problem use only the textual content present in training data. A few approaches have shown that information from external knowledge sources like knowledge graphs (KGs) can add value, in addition to the textual content, by providing background knowledge that may be critical for a task. However, the proposed models do not fully exploit the information in the usually large and noisy KGs, and it is not clear how it can be effectively encoded to be useful for entailment. We present an approach that complements text-based entailment models with information from KGs by (1) using Personalized PageRank to generate contextual subgraphs with reduced noise and (2) encoding these subgraphs using graph convolutional networks to capture the structural and semantic information in KGs. We evaluate our approach on multiple textual entailment datasets and show that the use of external knowledge helps the model to be robust and improves prediction accuracy. This is particularly evident in the challenging BreakingNLI dataset, where we see an absolute improvement of 5-20% over multiple text-based entailment models.

PDF Details

IJCAI Conference 2020 Conference Paper

PeerNomination: Relaxing Exactness for Increased Accuracy in Peer Selection

  • Nicholas Mattei
  • Paolo Turrini
  • Stanislav Zhydkov

In peer selection agents must choose a subset of themselves for an award or a prize. As agents are self-interested, we want to design algorithms that are impartial, so that an individual agent cannot affect their own chance of being selected. This problem has broad application in resource allocation and mechanism design and has received substantial attention in the artificial intelligence literature. Here, we present a novel algorithm for impartial peer selection, PeerNomination, and provide a theoretical analysis of its accuracy. Our algorithm possesses various desirable features. In particular, it does not require an explicit partitioning of the agents, as previous algorithms in the literature. We show empirically that it achieves higher accuracy than the exiting algorithms over several metrics.

PDF Details DOI

AAAI Conference 2019 Conference Paper

Building Ethically Bounded AI

  • Francesca Rossi
  • Nicholas Mattei

The more AI agents are deployed in scenarios with possibly unexpected situations, the more they need to be flexible, adaptive, and creative in achieving the goal we have given them. Thus, a certain level of freedom to choose the best path to the goal is inherent in making AI robust and flexible enough. At the same time, however, the pervasive deployment of AI in our life, whether AI is autonomous or collaborating with humans, raises several ethical challenges. AI agents should be aware and follow appropriate ethical principles and should thus exhibit properties such as fairness or other virtues. These ethical principles should define the boundaries of AI’s freedom and creativity. However, it is still a challenge to understand how to specify and reason with ethical boundaries in AI agents and how to combine them appropriately with subjective preferences and goal specifications. Some initial attempts employ either a data-driven examplebased approach for both, or a symbolic rule-based approach for both. We envision a modular approach where any AI technique can be used for any of these essential ingredients in decision making or decision support systems, paired with a contextual approach to define their combination and relative weight. In a world where neither humans nor AI systems work in isolation, but are tightly interconnected, e.g., the Internet of Things, we also envision a compositional approach to building ethically bounded AI, where the ethical properties of each component can be fruitfully exploited to derive those of the overall system. In this paper we define and motivate the notion of ethically-bounded AI, we describe two concrete examples, and we outline some outstanding challenges.

PDF Details

AAMAS Conference 2019 Conference Paper

DeepAggregation: A New Approach for Aggregating Incomplete Ranked Lists using Multi-Layer Graph Embedding

  • Rohith Dwarakanath Vallam
  • Ramasuri Narayanam
  • Srikanth G. Tamilselvam
  • Nicholas Mattei
  • Sudhanshu S. Singh
  • Shweta Garg
  • Gyana R. Parija

Preference aggregation, and specifically rank aggregation, is a well known problem in the fields of computational social choice and preference handling with broad application including web search and recommendation systems. Inspired by the recent advances in the area of deep neural representation learning, for the first time in the literature, in this paper we leverage unsupervised deep learning techniques - especially graph embeddings - for aggregating a collection of incomplete rank lists and accordingly we develop an algorithm called DeepAggregation. It takes as input a set of incomplete rank lists and constructs a multi-layer graph wherein the nodes are the alternatives that are ranked and the edges capture information contained in the incomplete rank lists. We then compute deep neural representation vectors (i. e. embeddings) for the nodes and then derive the aggregated order using these representation vectors. Our proposed algorithm can handle incomplete rank lists with or without ties. We conduct thorough empirical analysis of the proposed DeepAggregation algorithm using various real life data sets such as TripAdvisor reviews data. We empirically observe that DeepAggregation generates impressive results in comparison with a number of well-known state-of-the-art preference aggregation methods.

PDF

IJCAI Conference 2019 Conference Paper

Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging

  • Enrico H. Gerding
  • Alvaro Perez-Diaz
  • Haris Aziz
  • Serge Gaspers
  • Antonia Marcu
  • Nicholas Mattei
  • Toby Walsh

We consider mechanisms for the online allocation of perishable resources such as energy or computational power. A main application is electric vehicle charging where agents arrive and leave over time. Unlike previous work, we consider mechanisms without money, and a range of objectives including fairness and efficiency. In doing so, we extend the concept of envy-freeness to online settings. Furthermore, we explore the trade-offs between different objectives and analyse their theoretical properties both in online and offline settings. We then introduce novel online scheduling algorithms and compare them in terms of both their theoretical properties and empirical performance.

PDF Details

IJCAI Conference 2019 Conference Paper

Flexible Representative Democracy: An Introduction with Binary Issues

  • Ben Abramowitz
  • Nicholas Mattei

We introduce Flexible Representative Democracy (FRD), a novel hybrid of Representative Democracy (RD) and Direct Democracy (DD), in which voters can alter the issue-dependent weights of a set of elected representatives. In line with the literature on Interactive Democracy, our model allows the voters to actively determine the degree to which the system is direct versus representative. However, unlike Liquid Democracy, FRD uses strictly non-transitive delegations, making delegation cycles impossible, preserving privacy and anonymity, and maintaining a fixed set of accountable elected representatives. We present FRD and analyze it using a computational approach with issues that are independent, binary, and symmetric; we compare the outcomes of various democratic systems using Direct Democracy with majority voting and full participation as an ideal baseline. We find through theoretical and empirical analysis that FRD can yield significant improvements over RD for emulating DD with full participation.

PDF Details

AAAI Conference 2019 Conference Paper

Improving Natural Language Inference Using External Knowledge in the Science Questions Domain

  • Xiaoyan Wang
  • Pavan Kapanipathi
  • Ryan Musa
  • Mo Yu
  • Kartik Talamadupula
  • Ibrahim Abdelaziz
  • Maria Chang
  • Achille Fokoue

Natural Language Inference (NLI) is fundamental to many Natural Language Processing (NLP) applications including semantic search and question answering. The NLI problem has gained significant attention due to the release of large scale, challenging datasets. Present approaches to the problem largely focus on learning-based methods that use only textual information in order to classify whether a given premise entails, contradicts, or is neutral with respect to a given hypothesis. Surprisingly, the use of methods based on structured knowledge – a central topic in artificial intelligence – has not received much attention vis-a-vis the NLI problem. While there are many open knowledge bases that contain various types of reasoning information, their use for NLI has not been well explored. To address this, we present a combination of techniques that harness external knowledge to improve performance on the NLI problem in the science questions domain. We present the results of applying our techniques on text, graph, and text-and-graph based models; and discuss the implications of using external knowledge to solve the NLI problem. Our model achieves close to state-of-the-art performance for NLI on the SciTail science questions dataset.

PDF Details

AAAI Conference 2019 Conference Paper

Incorporating Behavioral Constraints in Online AI Systems

  • Avinash Balakrishnan
  • Djallel Bouneffouf
  • Nicholas Mattei
  • Francesca Rossi

AI systems that learn through reward feedback about the actions they take are increasingly deployed in domains that have significant impact on our daily life. However, in many cases the online rewards should not be the only guiding criteria, as there are additional constraints and/or priorities imposed by regulations, values, preferences, or ethical principles. We detail a novel online agent that learns a set of behavioral constraints by observation and uses these learned constraints as a guide when making decisions in an online setting while still being reactive to reward feedback. To define this agent, we propose to adopt a novel extension to the classical contextual multi-armed bandit setting and we provide a new algorithm called Behavior Constrained Thompson Sampling (BCTS) that allows for online learning while obeying exogenous constraints. Our agent learns a constrained policy that implements the observed behavioral constraints demonstrated by a teacher agent, and then uses this constrained policy to guide the reward-based online exploration and exploitation. We characterize the upper bound on the expected regret of the contextual bandit algorithm that underlies our agent and provide a case study with real world data in two application domains. Our experiments show that the designed agent is able to act within the set of behavior constraints without significantly degrading its overall reward performance.

PDF Details

AIJ Journal 2019 Journal Article

Strategyproof peer selection using randomization, partitioning, and apportionment

  • Haris Aziz
  • Omer Lev
  • Nicholas Mattei
  • Jeffrey S. Rosenschein
  • Toby Walsh

Peer reviews, evaluations, and selections are a fundamental aspect of modern science. Funding bodies the world over employ experts to review and select the best proposals from those submitted for funding. The problem of peer selection, however, is much more general: a professional society may want to give a subset of its members awards based on the opinions of all members; an instructor for a Massive Open Online Course (MOOC) or an online course may want to crowdsource grading; or a marketing company may select ideas from group brainstorming sessions based on peer evaluation. We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, economics, and political science. First, we propose a novel mechanism that is strategyproof, i. e. , agents cannot benefit by reporting insincere valuations. Second, we demonstrate the effectiveness of our mechanism by a comprehensive simulation-based comparison with a suite of mechanisms found in the literature. Finally, our mechanism employs a randomized rounding technique that is of independent interest, as it solves the apportionment problem that arises in various settings where discrete resources such as parliamentary representation slots need to be divided proportionally.

Details DOI

IJCAI Conference 2019 Conference Paper

Teaching AI Agents Ethical Values Using Reinforcement Learning and Policy Orchestration

  • Ritesh Noothigattu
  • Djallel Bouneffouf
  • Nicholas Mattei
  • Rachita Chandra
  • Piyush Madan
  • Kush R. Varshney
  • Murray Campbell
  • Moninder Singh

Autonomous cyber-physical agents play an increasingly large role in our lives. To ensure that they behave in ways aligned with the values of society, we must develop techniques that allow these agents to not only maximize their reward in an environment, but also to learn and follow the implicit constraints of society. We detail a novel approach that uses inverse reinforcement learning to learn a set of unspecified constraints from demonstrations and reinforcement learning to learn to maximize environmental rewards. A contextual bandit-based orchestrator then picks between the two policies: constraint-based and environment reward-based. The contextual bandit orchestrator allows the agent to mix policies in novel ways, taking the best actions from either a reward-maximizing or constrained policy. In addition, the orchestrator is transparent on which policy is being employed at each time step. We test our algorithms using Pac-Man and show that the agent is able to learn to act optimally, act within the demonstrated constraints, and mix these two functions in complex ways.

PDF Details

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.

Details

AIJ Journal 2018 Journal Article

Fixing balanced knockout and double elimination tournaments

  • Haris Aziz
  • Serge Gaspers
  • Simon Mackenzie
  • Nicholas Mattei
  • Paul Stursberg
  • Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.

Details DOI

AAMAS Conference 2018 Conference Paper

On the Distance Between CP-nets

  • Andrea Loreggia
  • Nicholas Mattei
  • Francesca Rossi
  • K. Brent Venable

Preferences play a key role in decision making by both single individuals and/or groups. In a multi-agent context, it is also important to know how to aggregate preferences to reach a collective decision. Moreover, being able to measure the distance between the preference of two individuals is important to identify the amount of disagreement and possibly reach consensus. In this paper we define a notion of distance between CP-nets, a formalism that can compactly encode conditional qualitative preferences. We consider the Kendall-tau distance between the partial orders induced by CPnets, and we define two tractable approximations of that distance, which can be computed in time polynomial in the number of features of the CP-nets. We then perform experiments to demonstrate the quality of these approximations compared to the Kendall-tau distance. We also relate our two notions of distance to the distance rationalizability of sequential plurality voting for CP-nets.

PDF

AAAI Conference 2018 Conference Paper

The Conference Paper Assignment Problem: Using Order Weighted Averages to Assign Indivisible Goods

  • Jing Wu Lian
  • Nicholas Mattei
  • Renee Noble
  • Toby Walsh

We propose a novel mechanism for solving the assignment problem when we have a two sided matching problem with preferences from one side (the agents/reviewers) over the other side (the objects/papers) and both sides have capacity constraints. The assignment problem is a fundamental in both computer science and economics with application in many areas including task and resource allocation. Drawing inspiration from work in multi-criteria decision making and social choice theory we use order weighted averages (OWAs), a parameterized class of mean aggregators, to propose a novel and flexible class of algorithms for the assignment problem. We show an algorithm for finding an Σ-OWA assignment in polynomial time, in contrast to the NP-hardness of finding an egalitarian assignment. We demonstrate through empirical experiments that using Σ-OWA assignments can lead to high quality and more fair assignments.

PDF Details

IJCAI Conference 2018 Conference Paper

Using Contextual Bandits with Behavioral Constraints for Constrained Online Movie Recommendation

  • Avinash Balakrishnan
  • Djallel Bouneffouf
  • Nicholas Mattei
  • Francesca Rossi

AI systems that learn through reward feedback about the actions they take are increasingly deployed in domains that have significant impact on our daily life. In many cases the rewards should not be the only guiding criteria, as there are additional constraints and/or priorities imposed by regulations, values, preferences, or ethical principles. We detail a novel online system, based on an extension of the contextual bandits framework, that learns a set of behavioral constraints by observation and uses these constraints as a guide when making decisions in an online setting while still being reactive to reward feedback. In addition, our system can highlight features of the context which are more predicted to be more rewarding and/or are in line with the behavioral constraints. Â We demonstrate the system by building an interactive interface for an online movie recommendation agent and show that our system is able to act within a set of behavior constraints without significantly degrading overall performance.

PDF Details

IJCAI Conference 2017 Conference Paper

Mechanisms for Online Organ Matching

  • Nicholas Mattei
  • Abdallah Saffidine
  • Toby Walsh

Matching donations from deceased patients to patients on the waiting list account for over 85\% of all kidney transplants performed in Australia. We propose a simple mechanisms to perform this matching and compare this new mechanism with the more complex algorithm currently under consideration by the Organ and Tissue Authority in Australia. We perform a number of experiments using real world data provided by the Organ and Tissue Authority of Australia. We find that our simple mechanism is more efficient and fairer in practice compared to the other mechanism currently under consideration.

PDF Details

AAMAS Conference 2017 Conference Paper

Stable Matching with Uncertain Pairwise Preferences

  • Haris Aziz
  • Pé ter Biró
  • Tamá s Fleiner
  • Serge Gaspers
  • Ronald de Haan
  • Nicholas Mattei
  • Baharak Rastegari

We study a two-sided matching problem where the agents have independent pairwise preferences on their possible partners and these preferences may be uncertain. In this case, the certainly preferred part of an agent’s preferences may admit a cycle and there may not even exist a matching that is stable with non-zero probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i. e. , matchings whose probability of being stable is positive or one, respectively. We show that finding a possibly stable matching is NP-hard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences. The latter complexity result also implies the hardness of finding a kernel in a special class of directed graphs. CCS Concepts •Theory of computation! Design and analysis of algorithms; •Computing methodologies! Multi-agent systems; •Applied computing! Economics;

PDF

JAIR Journal 2017 Journal Article

Uniform Random Generation and Dominance Testing for CP-Nets

  • Thomas E. Allen
  • Judy Goldsmith
  • Hayden Elizabeth Justice
  • Nicholas Mattei
  • Kayla Raines

The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o and o', of a minimal proof that o is preferred to o'. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.

PDF Details DOI

JAIR Journal 2016 Journal Article

A Study of Proxies for Shapley Allocations of Transport Costs

  • Haris Aziz
  • Casey Cahan
  • Charles Gretton
  • Philip Kilby
  • Nicholas Mattei
  • Toby Walsh

We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.

PDF Details DOI

AAMAS Conference 2016 Conference Paper

Egalitarianism of Random Assignment Mechanisms (Extended Abstract)

  • Haris Aziz
  • Aris Filos-Ratsikas
  • Jiashu Chen
  • Simon Mackenzie
  • Nicholas Mattei

We consider the egalitarian welfare of random assignment mechanisms when agents have unrestricted cardinal utilities over the objects. We define and give bounds on how well different random assignment mechanisms approximate the optimal egalitarian value (OEV) and investigate the effect that different well-known properties like ordinality, envyfreeness, and truthfulness have on the achievable egalitarian value. Finally, we conduct detailed experiments analyzing the tradeoffs between efficiency with envy-freeness or truthfulness using two prominent random assignment mechanisms — random serial dictatorship and the probabilistic serial mechanism — for different classes of utility functions and distributions.

PDF

AAAI Conference 2016 Conference Paper

Generating CP-Nets Uniformly at Random

  • Thomas Allen
  • Judy Goldsmith
  • Hayden Justice
  • Nicholas Mattei
  • Kayla Raines

Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with naı̈ve generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

PDF Details

IJCAI Conference 2016 Conference Paper

Interdependent Scheduling Games

  • Andres Abeliuk
  • Haris Aziz
  • Gerardo Berbeglia
  • Serge Gaspers
  • Petr Kalina
  • Nicholas Mattei
  • Dominik Peters
  • Paul Stursberg

We propose a model of interdependent scheduling games in which each player controls a set of services that they schedule independently. A player is free to schedule his own services at any time; however, each of these services only begins to accrue reward for the player when all predecessor services, which may or may not be controlled by the same player, have been activated. This model, where players have interdependent services, is motivated by the problems faced in planning and coordinating large-scale infrastructures, e. g. , restoring electricity and gas to residents after a natural disaster or providing medical care in a crisis when different agencies are responsible for the delivery of staff, equipment, and medicine. We undertake a game-theoretic analysis of this setting and in particular consider the issues of welfare maximization, computing best responses, Nash dynamics, and existence and computation of Nash equilibria.

PDF Details

AAAI Conference 2016 Conference Paper

Strategyproof Peer Selection: Mechanisms, Analyses, and Experiments

  • Haris Aziz
  • Omer Lev
  • Nicholas Mattei
  • Jeffrey Rosenschein
  • Toby Walsh

We study an important crowdsourcing setting where agents evaluate one another and, based on these evaluations, a subset of agents are selected. This setting is ubiquitous when peer review is used for distributing awards in a team, allocating funding to scientists, and selecting publications for conferences. The fundamental challenge when applying crowdsourcing in these settings is that agents may misreport their reviews of others to increase their chances of being selected. We propose a new strategyproof (impartial) mechanism called Dollar Partition that satisfies desirable axiomatic properties. We then show, using a detailed experiment with parameter values derived from target real world domains, that our mechanism performs better on average, and in the worst case, than other strategyproof mechanisms in the literature.

PDF Details

IJCAI Conference 2015 Conference Paper

Equilibria Under the Probabilistic Serial Rule

  • Haris Aziz
  • Serge Gaspers
  • Simon Mackenzie
  • Nicholas Mattei
  • Nina Narodytska
  • Toby Walsh

The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.

PDF Details

AAAI Conference 2014 Conference Paper

Fixing a Balanced Knockout Tournament

  • Haris Aziz
  • Serge Gaspers
  • Simon Mackenzie
  • Nicholas Mattei
  • Paul Stursberg
  • Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner.

PDF Details

ECAI Conference 2014 Conference Paper

How Hard Is It to Control an Election by Breaking Ties?

  • Nicholas Mattei
  • Nina Narodytska
  • Toby Walsh

We study the computational complexity of controlling the result of an election by breaking ties strategically. This problem is equivalent to the problem of deciding the winner of an election under parallel universes tie-breaking. When the chair of the election is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Additionally, we show that the form of the tie-breaking function can increase the opportunities for control.

Details

AAAI Conference 2014 Conference Paper

Voting with Rank Dependent Scoring Rules

  • Judy Goldsmith
  • Jérôme Lang
  • Nicholas Mattei
  • Patrice Perny

Positional scoring rules in voting compute the score of an alternative by summing the scores for the alternative induced by every vote. This summation principle ensures that all votes contribute equally to the score of an alternative. We relax this assumption and, instead, aggregate scores by taking into account the rank of a score in the ordered list of scores obtained from the votes. This defines a new family of voting rules, rank-dependent scoring rules (RDSRs), based on ordered weighted average (OWA) operators, which, include all scoring rules, and many others, most of which of new. We study some properties of these rules, and show, empirically, that certain RDSRs are less manipulable than Borda voting, across a variety of statistical cultures.

PDF Details

AAAI Conference 2013 Conference Paper

Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote

  • Haris Aziz
  • Serge Gaspers
  • Nicholas Mattei
  • Nina Narodytska
  • Toby Walsh

We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non-deterministic tie-breaking rule where we simply choose candidate uniformly at random. In general, we demonstrate that there is no connection between the computational complexity of computing a manipulating vote with the two different types of tie-breaking. However, we prove that for some scoring rules, the computational complexity of computing a manipulation can increase from polynomial to NP-hard. We also discuss the relationship with the computational complexity of computing a manipulating vote when we ask for a candidate to be the unique winner, or to be among the set of co-winners.

PDF Details

AAMAS Conference 2012 Conference Paper

Bribery in Voting Over Combinatorial Domains is Easy

  • Nicholas Mattei
  • Maria Silvia Pini
  • Francesca Rossi
  • Kristen Brent Venable

We investigate the computational complexity of finding optimal bribery schemes in voting domains where the candidate set is the Cartesian product of a set of variables and agents’ preferences are represented as CP-nets. We show that, in most cases, the bribery problem is easy. This also holds for some cases of k-approval, where bribery is difficult in traditional domains.

PDF

IJCAI Conference 2011 Conference Paper

Decision Making under Uncertainty: Social Choice and Manipulation

  • Nicholas Mattei

My research seeks insight into the complexity of computationalreasoning under uncertain information. I focus onpreference aggregation and social choice. Insights in theseareas have broader impacts in the areas of complexity theory, autonomous agents, and uncertainty in artificial intelligence.

PDF Details DOI
v2026.09.13