Author name cluster

Nahla Ben Amor

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.

11 papers

2 author rows

JAAMAS Journal 2022 Journal Article

Approximating voting rules from truncated ballots

Manel Ayadi
Nahla Ben Amor
Jérôme Lang

Abstract Classical voting rules assume that ballots are complete preference orders over candidates. However, when the number of candidates is large enough, it is too costly to ask the voters to rank all candidates. We suggest to fix a rank k, to ask all voters to specify their best k candidates, and then to consider “top- k approximations” of rules, which take only into account the top - k candidates of each ballot. The questions are then: Are these k-truncated approximations good predictors of the approximated rule? For which values of k and under which assumptions can we expect to output the correct winner with high probability? For different voting rules, we study these questions theoretically, by giving tight approximation ratios, and empirically, based on randomly generated profiles and on real data. We consider two measures of the quality of the approximation: the probability of selecting the same winner as the original rule, and the score ratio. We do a worst-case study (for the latter measure only), and for both measures, an average-case study and a study from real data sets.

Details DOI

EUMAS Conference 2020 Conference Paper

Approximating Voting Rules from Truncated Ballots

Manel Ayadi 0002
Nahla Ben Amor
Jérôme Lang

Details DOI

KR Conference 2020 Conference Paper

Ordinal Polymatrix Games with Incomplete Information

Nahla Ben Amor
Hélène Fargier
Régis Sabbadin
Meriem Trabelsi

Possibilistic games with incomplete information (Π-games) constitute a suitable framework for the representation of ordinal games under incomplete knowledge. However, representing a Π-game in standard normal form requires an extensive expression of the utility functions and the possibility distribution, namely, on the product spaces of actions and types. In the present work, we propose a less costly view of Π-games, namely min-based polymatrix Π-games, which allows to concisely specify Π-games with local interactions. This framework allows, for instance, the compact representation of coordination games under uncertainty where the satisfaction of an agent is high if and only if her strategy is coherent with all of her neighbors, the game being possibly only incompletely known to the agents. Then, an important result of this paper is to show that a min-based polymatrix Π-game can be transformed, in polynomial time, into a (complete information) min-based polymatrix game with identical pure Nash equilibria. Finally, we show that the latter family of games can be solved through a MILP formulation. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Possibilistic Games with Incomplete Information

Nahla Ben Amor
Helene Fargier
Régis Sabbadin
Meriem Trabelsi

Bayesian games offer a suitable framework for games where the utility degrees are additive in essence. This approach does nevertheless not apply to ordinal games, where the utility degrees do not capture more than a ranking, nor to situations of decision under qualitative uncertainty. This paper proposes a representation framework for ordinal games under possibilistic incomplete information (π-games) and extends the fundamental notion of Nash equilibrium (NE) to this framework. We show that deciding whether a NE exists is a difficult problem (NP-hard) and propose a Mixed Integer Linear Programming (MILP) encoding. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.

PDF Details

AAMAS Conference 2019 Conference Paper

Single Transferable Vote: Incomplete Knowledge and Communication Issues

Manel Ayadi
Nahla Ben Amor
Jérôme Lang
Dominik Peters

Single Transferable Vote (STV) is used in large political elections around the world. It is easy to understand and has desirable normative properties such as clone-proofness. However, voters need to report full rankings, which can make it less practical than plurality voting. We study ways to minimize the amount of communication required to use single-winner STV. In the first part of the paper, voters are assumed to report their top-k alternatives in a single shot. We empirically evaluate the extent to which STV with truncated ballots approximates STV with full information. We also study the computational complexity of the possible winner problem for top-k ballots. For k = 1, it can be solved in polynomial time, but is NPcomplete when k ⩾ 2. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm (2005), we show how we can reduce the amount of communication required in practice. We then study empirically the average communication complexity of these protocols, based on randomly generated profiles, and on real-world election data. Our conclusion is that STV needs, in practice, much less information than in the worst case.

PDF

IJCAI Conference 2017 Conference Paper

Equilibria in Ordinal Games: A Framework based on Possibility Theory.

Nahla Ben Amor
Helene Fargier
Régis Sabbadin

The present paper proposes the first definition of mixed equilibrium for ordinal games. This definition naturally extends possibilistic (single agent) decision theory. This allows us to provide a unifying view of single and multi-agent qualitative decision theory. Our first contribution is to show that ordinal games always admit a possibilistic mixed equilibrium, which can be seen as a qualitative counterpart to mixed (probabilistic) equilibrium. Then, we show that a possibilistic mixed equilibrium can be computed in polynomial time (wrt the size of the game), which contrasts with pure Nash or mixed probabilistic equilibrium computation in cardinal game theory. The definition we propose is thus operational in two ways: (i) it tackles the case when no pure Nash equilibrium exists in an ordinal game; and (ii) it allows an efficient computation of a mixed equilibrium.

PDF Details

ECAI Conference 2016 Conference Paper

Lexicographic Refinements in Possibilistic Decision Trees

Nahla Ben Amor
Zeineb El Khalfi
Hélène Fargier
Régis Sabbadin

Possibilistic decision theory has been proposed twenty years ago and has had several extensions since then. Because of the lack of decision power of possibilistic decision theory, several refinements have then been proposed. Unfortunately, these refinements do not allow to circumvent the difficulty when the decision problem is sequential. In this article, we propose to extend lexicographic refinements to possibilistic decision trees. We show, in particular, that they still benefit from an Expected Utility (EU) grounding. We also provide qualitative dynamic programming algorithms to compute lexicographic optimal strategies. The paper is completed with an experimental study that shows the feasibility and the interest of the approach.

Details

ECAI Conference 2016 Conference Paper

Preference Modeling with Possibilistic Networks and Symbolic Weights: A Theoretical Study

Nahla Ben Amor
Didier Dubois
Héla Gouider
Henri Prade

The use of possibilistic networks for representing conditional preference statements on discrete variables has been proposed only recently. The approach uses non-instantiated possibility weights to define conditional preference tables. Moreover, additional information about the relative strengths of these symbolic weights can be taken into account. The fact that at best we have some information about the relative values of these weights acknowledges the qualitative nature of preference specification. These conditional preference tables give birth to vectors of symbolic weights that reflect the preferences that are satisfied and those that are violated in a considered situation. The comparison of such vectors may rely on different orderings: the ones induced by the product-based, or the minimum-based chain rule underlying the possibilistic network, the discrimin, or leximin refinements of the minimum-based ordering, as well as Pareto ordering, and the symmetric Pareto ordering that refines it. A thorough study of the relations between these orderings in presence of vector components that are symbolic rather numerical is presented. In particular, we establish that the product-based ordering and the symmetric Pareto ordering coincide in presence of constraints comparing pairs of symbolic weights. This ordering agrees in the Boolean case with the inclusion between the sets of preference statements that are violated. The symmetric Pareto ordering may be itself refined by the leximin ordering. The paper highlights the merits of product-based possibilistic networks for representing preferences and provides a comparative discussion with CP-nets and OCF-networks.

Details

AAAI Conference 2015 Conference Paper

Egalitarian Collective Decision Making under Qualitative Possibilistic Uncertainty: Principles and Characterization

Nahla Ben Amor
Fatma Essghaier
Helene Fargier

This paper raises the question of collective decision making under possibilistic uncertainty; We study four egalitarian decision rules and show that in the context of a possibilistic representation of uncertainty, the use of an egalitarian collective utility function allows to get rid of the Timing Effect. Making a step further, we prove that if both the agents’ preferences and the collective ranking of the decisions satisfy Dubois and Prade’s axioms (1995), and particularly risk aversion, and Pareto Unanimity, then the egalitarian collective aggregation is compulsory. This result can be seen as an ordinal counterpart of Harsanyi’s theorem (1955).

PDF Details

UAI Conference 2011 Conference Paper

On the Complexity of Decision Making in Possibilistic Decision Trees

Hélène Fargier
Nahla Ben Amor
Wided Guezguez

When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to a series of possibilistic criteria, e.g pessimistic possibilistic qualitative utility, possibilistic likely dominance , binary possibilistic utility and possibilistic Choquet integrals. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a complexity study of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria which allows the application of dynamic programming that offers a polytime reduction of the decision problem. It also shows that possibilistic Choquet integrals do not satisfy this property, and that in this case the optimization problem is NP − hard.

Details

UAI Conference 2010 Conference Paper

Compiling Possibilistic Networks: Alternative Approaches to Possibilistic Inference

Raouia Ayachi
Nahla Ben Amor
Salem Benferhat
Rolf Haenni

Qualitative possibilistic networks, also known as min-based possibilistic networks, are important tools for handling uncertain information in the possibility theory framework. Despite their importance, only the junction tree adaptation has been proposed for exact reasoning with such networks. This paper explores alternative algorithms using compilation techniques. We first propose possibilistic adaptations of standard compilation-based probabilistic methods. Then, we develop a new, purely possibilistic, method based on the transformation of the initial network into a possibilistic base. A comparative study shows that this latter performs better than the possibilistic adaptations of probabilistic methods. This result is also confirmed by experimental results.

Details