Arrow Research search

Author name cluster

Maria Silvia Pini

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.

25 papers
2 author rows

Possible papers

25

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.

PDF

JAAMAS Journal 2019 Journal Article

Multi-agent soft constraint aggregation via sequential voting: theoretical and experimental results

  • Cristina Cornelio
  • Maria Silvia Pini
  • Kristen Brent Venable

Abstract 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 (i. e. , features). These scenarios are very common when candidates are described by feature vectors, such as cars, or houses, or any complex product. We assume agents to compactly express their preferences over the candidates via soft constraints. This is a compact way to model preferences which naturally models variables domains, and relationship among variables. To aggregate the preferences of the agents, we consider a sequential procedure that asks the agents to vote on one variable at a time. At each step, all agents express their preferences over the domain of a variable; based on such preferences, a voting rule is used to select one value for that variable. When all variables have been considered, the selected values constitute the returned variable assignment, that is, the elected candidate. We study several properties of this procedure (such as Condorcet consistency, anonymity, neutrality, monotonicity, consistency, efficiency, participation, independence of irrelevant alternatives, non dictatorship, and strategy-proofness), by relating them to corresponding properties of the adopted voting rules used for each variable. Moreover, we perform an experimental study on a special kind of soft constraints, namely fuzzy constraints. The experimental study 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.

Details DOI

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.

PDF Details

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.

PDF

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

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.

PDF

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.

PDF Details DOI

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.

PDF

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.

PDF

TARK Conference 2011 Conference Paper

Weights in stable marriage problems increase manipulation opportunities

  • Maria Silvia Pini
  • Francesca Rossi 0001
  • 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. Such a problem 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. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here we consider stable marriage problems with weighted preferences: each man (resp. , woman) provides a score for each woman (resp. , man). In this context, we consider the manipulability properties of the procedures that return stable marriages. While we know that all procedures are manipulable by modifying the preference lists or by truncating them, here we consider if manipulation can occur also by just modifying the weights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, we indeed increase the possibility of manipulating and this cannot be avoided by any reasonable restriction on the weights.

Details

JAAMAS Journal 2011 Journal Article

Winner determination in voting trees with incomplete preferences and weighted votes

  • Jérôme Lang
  • Maria Silvia Pini
  • Toby Walsh

Abstract In multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.

Details DOI

ECAI Conference 2010 Conference Paper

Local search algorithms on the Stable Marriage Problem: Experimental Studies

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

The stable marriage problem (SM) 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. In the classical formulation, n men and n women express their preferences over the members of the other sex. Solving an SM means finding a stable marriage: a matching of men to women with no blocking pair. A blocking pair consists of a man and a woman who are not married to each other but both prefer each other to their partners. 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 a group at the expenses of the other one. In this paper we present a local search approach to find stable marriages. Our experiments show that the number of steps grows as little as O(nlog(n)). We also show empirically that the proposed algorithm samples very well the set of all stable marriages of a given SM, thus providing a fair and efficient approach to generate stable marriages.

Details

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.

PDF

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.

Details DOI

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.

PDF Details

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.

PDF Details

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.

PDF Details