Author name cluster

Nawal Benabbou

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.

15 papers

2 author rows

ECAI Conference 2023 Conference Paper

On the Notion of Envy Among Groups of Agents in House Allocation Problems

Nathanaël Gross-Humbert
Nawal Benabbou
Aurélie Beynier
Nicolas Maudet

Envy-freeness is one of the prominent fairness notions in multiagent resource allocation but it has been mainly studied from an individual point of view. When the agents are partitioned into groups, fairness between groups is desirable. Several notions of group envy-freeness have been proposed over the last few years in the domain of fair division. In this paper we show that when groups may have different sizes and each agent gets at most one item, existing group envy-freeness notions fail to satisfy some desirable axioms. This motivates us to propose an original notion of degree of envy-freeness among groups, based on the counterfactual comparison of subgroups of the same size. While this notion is computationally demanding, we show that it can be efficiently approximated thanks to an adapted sampling method, showing that our approach is of practical relevance.

Details

AAAI Conference 2021 Conference Paper

Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization

Nawal Benabbou
Cassandre Leroy
Thibaut Lust
Patrice Perny

We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or nearoptimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.

PDF Details

AAMAS Conference 2021 Conference Paper

Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-Based Utilities

Nathanaël Gross-Humbert
Nawal Benabbou
Aurélie Beynier
Nicolas Maudet

We consider the problem of allocating indivisible items to agents where both agents and items are partitioned into disjoint groups. Following previous works on public housing allocation, each item (or house) belongs to a block and each agent is assigned a type. The allocation problem consists in assigning at most one item to each agent in a good way while respecting diversity constraints. Based on Schelling’s seminal work, we introduce a generic individual utility function where the welfare of an agent not only relies on her preferences over the items but also takes into account the fraction of agents of her own type in her own block. In this context, we investigate the issue of stability, and study two existing allocation mechanisms: a sequential mechanism used in Singapore and a distributed procedure based on mutually improving swaps of items.

PDF

AAAI Conference 2020 Conference Paper

An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems

Nawal Benabbou
Cassandre Leroy
Thibaut Lust

We propose a new approach consisting in combining genetic algorithms and regret-based incremental preference elicitation for solving multi-objective combinatorial optimization problems with unknown preferences. For the purpose of elicitation, we assume that the decision maker’s preferences can be represented by a parameterized scalarizing function but the parameters are initially not known. Instead, the parameter imprecision is progressively reduced by asking preference queries to the decision maker during the search to help identify the best solutions within a population. Our algorithm, called RIGA, can be applied to any multi-objective combinatorial optimization problem provided that the scalarizing function is linear in its parameters and that a (near-)optimal solution can be efﬁciently determined when preferences are known. Moreover, RIGA runs in polynomial time while asking no more than a polynomial number of queries. For the multi-objective traveling salesman problem, we provide numerical results showing its practical efﬁciency in terms of number of queries, computation time and gap to optimality.

PDF Details

ECAI Conference 2020 Conference Paper

Regret-Based Elicitation for Solving Multi-Objective Knapsack Problems with Rank-Dependent Aggregators

Nawal Benabbou
Cassandre Leroy
Thibaut Lust

In this paper, we consider multi-objective knapsack problems where the decision maker’s preferences are represented by a non-linear aggregation function whose parameters are initially not known. More precisely, we focus on rank-dependent aggregators such as ordered weighted averages (OWA) and Choquet integrals which are non-linear scalarizing functions that assign weights to ranks rather than to objectives in the aggregation process, so as to control the importance attached to the bottom performance or to any other order statistics; for instance, an OWA operator with decreasing weights helps promoting balanced solutions while ensuring overall efficiency. In this setting, we propose new interactive heuristic methods consisting in combining regret-based preference elicitation and heuristic search so as to quickly focus the search on the most promising solutions. For OWA operators and Choquet integrals, the proposed methods run in polynomial time and are guaranteed to generate no more than a polynomial number of queries. We perform numerical tests comparing our methods to different interactive solving methods in order to show the practical efficiency of our approach in terms of number of queries, computation time and gap to optimality.

Details

SoCS Conference 2019 Conference Paper

A General Interactive Approach for Solving Multi-Objective Combinatorial Optimization Problems with Imprecise Preferences

Nawal Benabbou
Thibaut Lust

In this paper, we develop a general interactive method to solve multi-objective combinatorial optimization problems with imprecise preferences. Assuming that preferences can be represented by a parameterized scalarizing function, we iteratively ask preferences queries to the decision maker in order to reduce the uncertainty over the preference parameters until being able to determine her preferred solution. To produce informative preference queries at each step, we generate promising solutions using the extreme points of the polyhedron representing the admissible preference parameters and then we ask the decision maker to compare two of these solutions (we propose different selection strategies). These extreme points are also used to provide a stopping criterion guaranteeing that the returned solution is optimal (or near-optimal) according to the decision maker

Details

IJCAI Conference 2019 Conference Paper

Fairness Towards Groups of Agents in the Allocation of Indivisible Items

Nawal Benabbou
Mithun Chakraborty
Edith Elkind
Yair Zick

In this paper, we study the problem of matching a set of items to a set of agents partitioned into types so as to balance fairness towards the types against overall utility/efficiency. We extend multiple desirable properties of indivisible goods allocation to our model and investigate the possibility and hardness of achieving combinations of these properties, e. g. we prove that maximizing utilitarian social welfare under constraints of typewise envy-freeness up to one item (TEF1) is computationally intractable. We also define a new concept of waste for this setting, show experimentally that augmenting an existing algorithm with a marginal utility maximization heuristic can produce a TEF1 solution with reduced waste, and also provide a polynomial-time algorithm for computing a non-wasteful TEF1 allocation for binary agent-item utilities.

PDF Details

AAMAS Conference 2018 Conference Paper

Diversity Constraints in Public Housing Allocation

Nawal Benabbou
Mithun Chakraborty
Xuan-Vinh Ho
Jakub Sliwinski
Yair Zick

The state of Singapore operates a national public housing program, accounting for over 70% of its residential real estate. Singapore uses its housing allocation program to promote ethnic diversity in its neighborhoods; it does so by imposing ethnic quotas: every ethnic group must not own more than a certain percentage in a housing project, thus ensuring that every neighborhood contains members from each ethnic group. However, imposing diversity constraints naturally results in some welfare loss. Our work studies the tradeoff between diversity and (utilitarian) social welfare from the perspective of computational economics. We model the problem as an extension of the classic assignment problem, with additional diversity constraints. While the classic assignment program is polytime computable, we show that adding diversity constraints makes the problem computationally intractable; however, we identify a 1 2 approximation algorithm, as well as reasonable agent utility models which admit poly-time algorithms. In addition, we study the price of diversity: this is the loss in welfare incurred by imposing diversity constraints; we provide upper bounds on the price of diversity as functions of natural problem parameters. Finally, we use recent, public demographic and real-estate data from Singapore to create a simulated framework testing the welfare loss due to diversity constraints in realistic large-scale scenarios.

PDF

IJCAI Conference 2017 Conference Paper

Adaptive Elicitation of Preferences under Uncertainty in Sequential Decision Making Problems

Nawal Benabbou
Patrice Perny

This paper aims to introduce an adaptive preference elicitation method for interactive decision support in sequential decision problems. The Decision Maker's preferences are assumed to be representable by an additive utility, initially unknown or imperfectly known. We first study the determination of possibly optimal policies when admissible utilities are imprecisely defined by some linear constraints derived from observed preferences. Then, we introduce a new approach interleaving elicitation of utilities and backward induction to incrementally determine an optimal or near-optimal policy. We propose an interactive algorithm with performance guarantees and describe numerical experiments demonstrating the practical efficiency of our approach.

PDF Details

IJCAI Conference 2017 Conference Paper

Incremental Decision Making Under Risk with the Weighted Expected Utility Model

Hugo Gilbert
Nawal Benabbou
Patrice Perny
Olivier Spanjaard
Paolo Viappiani

This paper deals with decision making under risk with the Weighted Expected Utility (WEU) model, which is a model generalizing expected utility and providing stronger descriptive possibilities. We address the problem of identifying, within a given set of lotteries, a (near-)optimal solution for a given decision maker consistent with the WEU theory. The WEU model is parameterized by two real-valued functions. We propose here a new incremental elicitation procedure to progressively reduce the imprecision about these functions until a robust decision can be made. We also give experimental results showing the practical efficiency of our method.

PDF Details

AIJ Journal 2017 Journal Article

Incremental elicitation of Choquet capacities for multicriteria choice, ranking and sorting problems

Nawal Benabbou
Patrice Perny
Paolo Viappiani

This paper proposes incremental preference elicitation methods for multicriteria decision making with a Choquet integral. The Choquet integral is an evaluation function that performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among them and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries (questions) selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until the regret (the worst-case “loss” due to reasoning with only partially specified capacities) is low enough. We propose a new approach designed to efficiently compute minimax regret for the Choquet model and we show how this approach can be used in different settings: 1) the problem of recommending a single alternative, 2) the problem of ranking alternatives from best to worst, and 3) sorting several alternatives into ordered categories. Numerical experiments are provided to demonstrate the practical efficiency of our approach for each of these situations.

Details DOI

ECAI Conference 2016 Conference Paper

Solving Multi-Agent Knapsack Problems Using Incremental Approval Voting

Nawal Benabbou
Patrice Perny

In this paper, we study approval voting for multi-agent knapsack problems under incomplete preference information. The agents consider the same set of feasible knapsacks, implicitly defined by a budget constraint, but they possibly diverge in the utilities they attach to items. Individual utilities being difficult to assess precisely and to compare, we collect approval statements on knapsacks from the agents with the aim of determining the optimal solutions by approval voting. We first propose a search procedure based on mixed-integer programming to explore the space of utilities compatible with the known part of preferences in order to determine or approximate the set of possible approval winners. Then, we propose an incremental procedure combining preference elicitation and search in order to determine the set of approval winners without requiring the full elicitation of the agents' preferences. Finally, the practical efficiency of these procedures is illustrated by various numerical tests.

Details

IJCAI Conference 2015 Conference Paper

Combining Preference Elicitation and Search in Multiobjective State-Space Graphs

Nawal Benabbou
Patrice Perny

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e. g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.

PDF Details

AAAI Conference 2015 Conference Paper

Incremental Weight Elicitation for Multiobjective State Space Search

Nawal Benabbou
Patrice Perny

This paper proposes incremental preference elicitation methods for multiobjective state space search. Our approach consists in integrating weight elicitation and search to determine, in a vector-valued state-space graph, a solution path that best fits the Decision Maker’s preferences. We first assume that the objective weights are imprecisely known and propose a state space search procedure to determine the set of possibly optimal solutions. Then, we introduce incremental elicitation strategies during the search that use queries to progressively reduce the set of admissible weights until a nearlyoptimal path can be identified. The validity of our algorithms is established and numerical tests are provided to test their efficiency both in terms of number of queries and solution times.

PDF Details

ECAI Conference 2014 Conference Paper

Incremental Elicitation of Choquet Capacities for Multicriteria Decision Making

Nawal Benabbou
Patrice Perny
Paolo Viappiani

The Choquet integral is one of the most sophisticated and expressive preference models used in decision theory for multicriteria decision making. It performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among criteria and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until a decision can be made. We propose a new approach designed to efficiently compute minimax regret for the Choquet model. Numerical experiments are provided to demonstrate the practical efficiency of our approach.

Details