Francesca Rossi

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]

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.

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.

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.

IJCAI Conference 2023 Conference Paper

Plansformer Tool: Demonstrating Generation of Symbolic Plans Using Transformers

• Vishal Pallagani
• Bharath Muppasani
• Biplav Srivastava
• Francesca Rossi
• Lior Horesh
• Keerthiram Murugesan
• Andrea Loreggia
• Francesco Fabiano

Plansformer is a novel tool that utilizes a fine-tuned language model based on transformer architecture to generate symbolic plans. Transformers are a type of neural network architecture that have been shown to be highly effective in a range of natural language processing tasks. Unlike traditional planning systems that use heuristic-based search strategies, Plansformer is fine-tuned on specific classical planning domains to generate high-quality plans that are both fluent and feasible. Plansformer takes the domain and problem files as input (in PDDL) and outputs a sequence of actions that can be executed to solve the problem. We demonstrate the effectiveness of Plansformer on a variety of benchmark problems and provide both qualitative and quantitative results obtained during our evaluation, including its limitations. Plansformer has the potential to significantly improve the efficiency and effectiveness of planning in various domains, from logistics and scheduling to natural language processing and human-computer interaction. In addition, we provide public access to Plansformer via a website as well as an API endpoint; this enables other researchers to utilize our tool for planning and execution. The demo video is available at https: //youtu. be/_1rlctCGsrk

AIJ Journal 2022 Journal Article

Atlas of AI – Book review

• Francesca Rossi

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.

AAMAS Conference 2022 Conference Paper

Voting with Random Classifiers (VORACE): Theoretical and Experimental Analysis

• Cristina Cornelio
• Michele Donini
• Andrea Loreggia
• Maria Silvia Pini
• Francesca Rossi

Ensemble methods are built by training many different models and aggregating their outputs to output the prediction of the whole system. In this work, we study the behavior of an ensemble method where voting rules are used to aggregate the output of a set of randomly-generated classifiers. We provide both a theoretical and an empirical analysis of this method, showing that it performs comparably with other state-of-the-art ensemble methods, while not requiring any domain expertise to fine-tune the individual classifiers.

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.

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.

AAAI Conference 2021 System Paper

VEGA: a Virtual Environment for Exploring Gender Bias vs. Accuracy Trade-offs in AI Translation Services

• Mariana Bernagozzi
• Biplav Srivastava
• Francesca Rossi
• Sheema Usmani

Machine translation services are a very popular class of Artificial Intelligence (AI) services nowadays but public’s trust in these services is not guaranteed since they have been shown to have issues like bias. In this work, we focus on the behavior of machine translators with respect to gender bias as well as their accuracy. We have created the first-of-its-kind virtual environment, called VEGA, where the user can interactively explore translations services and compare their trust ratings using different visuals.

JAAMAS Journal 2021 Journal Article

Voting with random classifiers (VORACE): theoretical and experimental analysis

• Cristina Cornelio
• Michele Donini
• Francesca Rossi

Abstract In many machine learning scenarios, looking for the best classifier that fits a particular dataset can be very costly in terms of time and resources. Moreover, it can require deep knowledge of the specific domain. We propose a new technique which does not require profound expertise in the domain and avoids the commonly used strategy of hyper-parameter tuning and model selection. Our method is an innovative ensemble technique that uses voting rules over a set of randomly-generated classifiers. Given a new input sample, we interpret the output of each classifier as a ranking over the set of possible classes. We then aggregate these output rankings using a voting rule, which treats them as preferences over the classes. We show that our approach obtains good results compared to the state-of-the-art, both providing a theoretical analysis and an empirical evaluation of the approach on several datasets.

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.

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.

AAMAS Conference 2019 Conference Paper

Preferences and Ethical Priorities: Thinking Fast and Slow in AI

• Francesca Rossi
• Andrea Loreggia

In AI, the ability to model and reason with preferences allows for more personalized services. Ethical priorities are also essential, if we want AI systems to make decisions that are ethically acceptable. Both data-driven and symbolic methods can be used to model preferences and ethical priorities, and to combine them in the same system, as two agents that need to cooperate. We describe two approaches to design AI systems that can reason with both preferences and ethical priorities. We then generalize this setting to follow Kahneman’s theory of thinking fast and slow in the human’s mind. According to this theory, we make decision by employing and combining two very different systems: one accounts for intuition and immediate but imprecise actions, while the other one models correct and complex logical reasoning. We discuss how such two systems could possibly be exploited and adapted to design machines that allow for both data-driven and logical reasoning, and exhibit degrees of personalized and ethically acceptable behavior.

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.

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.

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.

AAAI Conference 2016 Conference Paper

Embedding Ethical Principles in Collective Decision Support Systems

• Joshua Greene
• Francesca Rossi
• John Tasioulas
• Kristen Venable
• Brian Williams

The future will see autonomous machines acting in the same environment as humans, in areas as diverse as driving, assistive technology, and health care. Think of self-driving cars, companion robots, and medical diagnosis support systems. We also believe that humans and machines will often need to work together and agree on common decisions. Thus hybrid collective decision making systems will be in great need. In this scenario, both machines and collective decision making systems should follow some form of moral values and ethical principles (appropriate to where they will act but always aligned to humans’), as well as safety constraints. In fact, humans would accept and trust more machines that behave as ethically as other humans in the same environment. Also, these principles would make it easier for machines to determine their actions and explain their behavior in terms understandable by humans. Moreover, often machines and humans will need to make decisions together, either through consensus or by reaching a compromise. This would be facilitated by shared moral values and ethical principles.

IJCAI Conference 2015 Conference Paper

Gibbard-Satterthwaite Games

• Edith Elkind
• Umberto Grandi
• Francesca Rossi
• Arkadii Slinko

The Gibbard-Satterthwaite theorem implies the ubiquity of manipulators–voters who could change the election outcome in their favor by unilaterally modifying their vote. In this paper, we ask what happens if a given profile admits several such voters. We model strategic interactions among Gibbard–Satterthwaite manipulators as a normal-form game. We classify the 2-by-2 games that can arise in this setting for two simple voting rules, namely Plurality and Borda, and study the complexity of determining whether a given manipulative vote weakly dominates truth-telling, as well as existence of Nash equilibria.

AAAI Conference 2015 Conference Paper

Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization

• Danny Munera
• Daniel Diaz
• Salvador Abreu
• Francesca Rossi
• Vijay Saraswat
• Philippe Codognet

Stable matching problems have several practical applications. If preference lists are truncated and contain ties, finding a stable matching with maximal size is computationally difficult. We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parallel versions (particularly versions with communication) improve performance so much that very large and hard instances can be solved quickly.

AAAI Conference 2013 Conference Paper

A Framework for Aggregating Influenced CP-Nets and its Resistance to Bribery

• Alberto Maran
• Nicolas Maudet
• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable

AAAI Conference 2013 Conference Paper

Bribery in Voting With Soft Constraints

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable

We consider a multi-agent scenario where a collection of agents needs to select a common decision from a large set of decisions over which they express their preferences. This decision set has a combinatorial structure, that is, each decision is an element of the Cartesian product of the domains of some variables. Agents express their preferences over the decisions via soft constraints. We consider both sequential preference aggregation methods (they aggregate the preferences over one variable at a time) and one-step methods and we study the computational complexity of influencing them through bribery. We prove that bribery is NPcomplete for the sequential aggregation methods (based on Plurality, Approval, and Borda) for most of the cost schemes we defined, while it is polynomial for one-step Plurality.

AAMAS Conference 2013 Conference Paper

Resistance to Bribery when Aggregating Soft Constraints

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable

We investigate a multi-agent scenario where agents express their preferences over a large set of decisions via soft constraints. We consider sequential procedures (based on Plurality, Approval, and Borda) to aggregate agents’ preferences and we study their resistance to bribery attempts to influence the result of the aggregation.

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.

AAMAS Conference 2012 Conference Paper

Influence and aggregation of preferences over combinatorial domains

• Nicolas Maudet
• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable

In a multi-agent context where a set of agents declares their preferences over a common set of candidates, it is often the case that agents may influence each others. Recent work has modelled the influence phenomenon in the case of voting over a single issue. Here we generalize this model to account for preferences over combinatorially structured domains including several issues. When agents express their preferences as CP-nets, we show how to model influence functions and how to aggregate preferences by interleaving voting and influence convergence.

IJCAI Conference 2011 Conference Paper

Multi-Agent Soft Constraint Aggregation via Sequential Voting

• Giorgio Dalla Pozza
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable

We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via soft constraints. We consider a sequential procedure that chooses one candidate by asking the agents to vote on one variable at a time. While some properties of this procedure have been already studied, here we focus on independence of irrelevant alternatives, non-dictatorship, and strategy-proofness. Also, we perform an experimental study that shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering and of the presence of coalitions of agents.

AAMAS Conference 2011 Conference Paper

Possible And Necessary Winners In Voting Trees: Majority Graphs Vs. Profiles

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

Given the preferences of several agents over a common set of candidates, voting trees can be used to select a candidate (the winner) by a sequence of pairwise competitions modelled by a binary tree (the agenda). The majority graph compactly represents the preferences of the agents and provides enough information to compute the winner. When some preferences are missing, there are various notions of winners, such as the possible winners (that is, winners in at least one completion) or the necessary winners (that is, winners in all completions). In this generalized scenario, we show that using the majority graph to compute winners is not correct, since it may declare as winners candidates that are not so. Nonetheless, the majority graph can be used to compute efficiently an upper or lower approximation of the correct set of winners.

AAMAS Conference 2011 Conference Paper

Procedural Fairness in Stable Marriage Problems

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. It has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. Given a stable marriage problem, it is possible to find a male-optimal (resp. , female-optimal) stable marriage in polynomial time. However, it is sometimes desirable to find stable marriages without favoring one group at the expenses of the other one. To achieve this goal, we consider a local search approach to find stable marriages with the aim of exploiting the nondeterminism of local search to give a fair procedure. We test our algorithm on classes of stable marriage problems, showing both its efficiency and its sampling capability over the set of all stable marriages, and we compare it to a Markov chain approach.

AAAI Conference 2011 Conference Paper

The Next Best Solution

• Ronen Brafman
• Enrico Pilotto
• Francesca Rossi
• Domenico Salvagnin
• Kristen Venable
• Toby Walsh

We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

AIJ Journal 2010 Journal Article

Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

We consider soft constraint problems where some of the preferences may be unspecified. This models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define algorithms, that interleave search and preference elicitation, to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. We define a combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm, which we compare experimentally. We compute both the number of elicited preferences and the user effort, which may be larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate as little information as possible, the user effort measures also the hidden work the user has to do to be able to communicate the elicited preferences. Our experimental results on classical, fuzzy, weighted and temporal incomplete CSPs show that some of our algorithms are very good at finding a necessarily optimal solution while asking the user for only a very small fraction of the missing preferences. The user effort is also very small for the best algorithms.

KR Conference 2010 Conference Paper

Finding the next solution in constraint- and preference-based knowledge representation formalisms

• Ronen Brafman
• Francesca Rossi
• Domenico Salvagnin
• Kristen Brent Venable
• Toby Walsh

In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preference-based representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in tree-shaped CSPs and tree-shaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CP-nets, showing that the problem is easy in acyclic CP-nets, as well as in constrained acyclic CP-nets where the (soft) constraints are tree-shaped and topologically compatible with the CP-net.

AAMAS Conference 2010 Conference Paper

Male optimality and uniqueness in stable marriage problems with partial orders

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

In this paper, we study the concepts of male optimality anduniqueness of stable marriages for partially ordered preferences. We give an algorithm to find a stable marriage that ismale optimal, and a sufficient condition on the preferences, which guarantees the uniqueness of stable marriages.

JAAMAS Journal 2010 Journal Article

Manipulation complexity and gender neutrality in stable marriage procedures

• Maria Silvia Pini
• Francesca Rossi
• Toby Walsh

Abstract The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors, to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale–Shapley algorithm, which runs in quadratic time in the number of men/women. It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale–Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale–Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral.

KER Journal 2010 Journal Article

New trends in constraint satisfaction, planning, and scheduling: a survey

• Roman Barták
• Miguel A. Salido
• Francesca Rossi

Abstract During recent years, the development of new techniques for constraint satisfaction, planning, and scheduling has received increased attention, and substantial effort has been invested in trying to exploit such techniques to find solutions to real-life problems. In this paper, we present a survey on constraint satisfaction, planning, and scheduling from the Artificial Intelligence point of view. In particular, we present the main definitions and techniques, and discuss possible ways of integrating such techniques. We also analyze the role of constraint satisfaction in planning and scheduling, and hint at some open research issues related to planning, scheduling, and constraint satisfaction.

IJCAI Conference 2009 Conference Paper

• Ulle Endriss
• Maria Silvia Pini
• Francesca Rossi
• Brent Venable

Voting theory can provide useful insights for multiagent preference aggregation. However, the standard setting assumes voters with preferences that are total orders, as well as a ballot language that coincides with the preference language. In typical AI scenarios, these assumptions do not hold: certain alternatives may be incomparable for some agents, and others may have their preferences encoded in a format that is different from how the preference aggregation mechanism wants them. We study the consequences of dropping these assumptions. In particular, we investigate the consequences for the important notion of strategy-proofness. While strategy-proofness cannot be guaranteed in the classical setting, we are able to show that there are situations in our more general framework where this is possible. We also consider computational aspects of the problem.

AAMAS Conference 2009 Conference Paper

Manipulation and Gender Neutrality in Stable Marriage Procedures

• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

KR Conference 2008 Conference Paper

Dealing with Incomplete Agents' Preferences and an Uncertain Agenda in Group Decision Making via Sequential Majority Voting

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

EAAI Journal 2008 Journal Article

Fuzzy conditional temporal problems: Strong and weak consistency

• Marco Falda
• Francesca Rossi
• K. Brent Venable

In real life scenarios there is often the need for modeling conditional plans where external events determine the actual execution sequence. Conditional temporal problems (CTPs) have addressed such a need by extending the classical temporal constraint models with conditions on the occurrence of some events. Preferences are also a key aspect in many temporal reasoning tasks, since they allow for modeling in a natural way desires and different satisfaction levels. In this paper, we generalize CTPs to CTPPs by adding fuzzy preferences to the temporal constraints and by allowing fuzzy thresholds for the occurrence of some events. This allows us to generalize the conditions: events are allowed to determine not only which variables are executed, but also the preferences associated to their execution time. We consider two consistency notions (that is, strong and weak) and we provide their corresponding testing algorithms. We show that the complexity of these algorithms is not larger than their classical counterparts for CTPs. We also compare CTPPs with STPPUs, another temporal framework with uncertainty and preferences, by providing a polynomial mapping from STPPUs to CTPPs which allows to identify a strong theoretical connection among the two formalisms. Finally, we describe a tool to define CTPPs and to test if they are strongly or weakly consistent.

IJCAI Conference 2007 Conference Paper

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

We consider how to combine the preferences of multiple agents despite the presence of incompleteness and incomparability in their preference orderings. An agent's preference ordering may be incomplete because, for example, there is an ongoing preference elicitation process. It may also contain incomparability as this is useful, for example, in multi-criteria scenarios. We focus on the problem of computing the possible and necessary winners, that is, those outcomes which can be or always are the most preferred for the agents. Possible and necessary winners are useful in many scenarios including preference elicitation. First we show that computing the sets of possible and necessary winners is in general a difficult problem as is providing a good approximation of such sets. Then we identify general properties of the preference aggregation function which are sufficient for such sets to be computed in polynomial time. Finally, we show how possible and necessary winners can be used to focus preference elicitation.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

Preferences can be aggregated using voting rules. We consider here the family of rules which perform a sequence of pairwise majority comparisons between two candidates. The winner thus depends on the chosen sequence of comparisons, which can be represented by a binary tree. We address the difficulty of computing candidates that win for some trees, and then introduce and study the notion of fair winner, i. e. candidates who win in a balanced tree. We then consider the situation where we lack complete informations about preferences, and determine the computational complexity of computing winners in this case.

AAMAS Conference 2006 Conference Paper

Strategic voting when aggregating partially ordered preferences

• Francesca Rossi
• Maria Silvia Pini
• Kristen Brent Venable
• Toby Walsh

AIJ Journal 2002 Journal Article

Abstracting soft constraints: Framework, properties, examples

• Stefano Bistarelli
• Philippe Codognet
• Francesca Rossi

Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster. In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier. We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.

TCS Journal 1997 Journal Article

Preface

• Ugo Montanari
• Francesca Rossi

IJCAI Conference 1997 Conference Paper

Semiring-based Constraint Logic Programming

• Stefano Bistarelli
• Ugo Montanari
• Francesca Rossi

We extend the Constraint Logic Programming (CLP) formalism in order to handle semiringbased constraint systems. This allows us to perform in the same language both constraint solving and optimization. In fact, constraint systems based on semirings are able to model both classical constraint solving and more sophisticated features like uncertainty, probability, fuzzyness, and optimization. We then provide this class of languages with three equivalent semantics: model-theoretic, fixpoint, and proof-theoretic, in the style of CLP programs.

IJCAI Conference 1995 Conference Paper

Constraint Solving over Semirings

• Stefano Bistarelli
• Ugo Montanari
• Francesca Rossi

We introduce a general framework for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated to each tuple of values of the variable domain, and the two semiring operations (+ and x) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that some conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving schemes, thus allowing one both to formally justify many informally taken choices in existing schemes, and to prove that the local consistency techniques can be used also in newly defined schemes.

TCS Journal 1994 Journal Article

An abstract machine for concurrent modular systems: CHARM

• Andrea Corradini
• Ugo Montanari
• Francesca Rossi

CHARM (for concurrency and hiding in an abstract rewriting machine) is an abstract machine which allows one to model naturally the behavior of distributed systems consisting of a collection of processes-sharing variables. CHARM is equipped with a clean operational semantics based on term rewriting over a suitable algebra, and it exhibits a sophisticated treatment of concurrency and modularity, which is obtained through the partition of each state into a global and a local part. To show the expressiveness and generality of this abstract machine, three relevant computational formalisms are mapped onto the CHARM framework: graph grammars, concurrent constraint programming, and place/transition Petri nets.

TCS Journal 1993 Journal Article

Graph rewriting for a partial ordering semantics of concurrent constraint programming

• Ugo Montanari
• Francesca Rossi

The concurrent constraint logic programming framework extends both logic programming and concurrent logic programming in that a program consists of the concurrent execution of agents which add (i. e. , “tell”) and check (i. e. , “ask”) constraints on a shared set of variables, and whose behaviour is described by a set of clauses. This formulation is very general and can be seen as a concurrent logic programming shell which is parametrized w. r. t. the underlying constraint system. Graphs and graph grammars can be conveniently used to describe such a framework, and the modelling is so elegant and expressive that they provide what we believe is the most natural abstract machine for concurrent constraint programming. In fact, basic notions like the possibility of asking or telling a constraint into the shared store are very easy to express in the algebraic approach to graph rewriting. More precisely, the shared store is represented as a (hyper)graph, where nodes are variables and arcs are constraints or agents. Then, both the entailment relation of the underlying constraint system and the local behaviour of agents is expressed by suitable sets of graph productions, which transform the current global state of the system into a new one. Finally, each computation is represented by a graph derivation. In our setting the shared store is not seen as one constraint, but as a set of constraints which possibly share variables. This is in contrast with all the operational and denotational semantics already proposed for the concurrent constraint paradigm, which treat the shared store as a monolith and, thus, are not useful for deriving any information about the causal dependencies among the agents or the maximal degree of parallelism. On the contrary, our approach can easily express such information in the form of a partial ordering associated to each graph derivation. This can be regarded as the first attempt to give a true-concurrency semantics to concurrent constraint programming and, more generally, to graph grammars.

TCS Journal 1993 Journal Article

Hyperedge replacement jungle rewriting for term-rewriting systems and logic programming

• Andrea Corradini
• Francesca Rossi

We introduce hyperedge replacement jungle rewriting, a graph-rewriting formalism suitable for modeling the manipulation of terms and similar structures, and investigate its expressive power by showing that it can model both term-rewriting systems and logic programming in a faithful way. For term-rewriting systems we prove the soundness of their jungle representation, and a result of completeness w. r. t. applicability which is stronger than similar results in the related literature, since it works also for non-left-linear rules. For logic programming both soundness and completeness hold.

AIJ Journal 1991 Journal Article

Constraint relaxation may be perfect

• Ugo Montanari
• Francesca Rossi

Networks of constraints are a simple knowledge representation method, useful for describing those problems whose solution is required to satisfy several simultaneous constraints. The problem of solving a network of constraints with finite domains is NP-complete. The standard solution technique for such networks of constraints is the backtrack search, but many relaxation algorithms, to be applied before backtracking, have been developed: they transform a network in an equivalent but more explicit one. The idea is to make the backtrack search have a better average time complexity. In fact, if the network elaborated by the backtrack algorithm is more explicit, the algorithm backtracks less. In this paper we describe relaxation algorithms as sequences of applications of relaxation rules. Moreover, we define perfect relaxation algorithms as relaxation algorithms which not only return a more explicit network, but also exactly solve the given network of constraints by applying every relaxation rule only once. Finally, we characterize a family of classes of networks on which certain perfect relaxation algorithms are very efficient: the exact solution of each network in a class is found in linear time.