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

Nawal Benabbou and Cassandre Leroy and Thibaut Lust 1Abstract. 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.

INTRODUCTION

Multi-Objective Combinatorial Optimization (MOCO) is concerned with problems involving alternatives that are evaluated with respect to several conflicting viewpoints/objectives to be optimized simultaneously (e.g., cost, time, profit), with various applications in Artificial Intelligence (AI) such as investments planning, resource allocation, group configuration, recommendation systems and electronic commerce. To model the preferences of the Decision Maker (DM) over feasible solutions, an aggregation function is often used to synthesize the different evaluations into scalar values representing the overall performances of alternatives. Recently there has been a growing interest in rank-dependent aggregators such as Choquet integrals [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF], which enable to model complex decision behaviors by considering possible (positive and negative) synergies between the objectives. They also make it possible to model preferences for "well-balanced" efficient solutions that cannot be obtained by optimizing a weighted sum. While most contributions focus on the elaboration of algorithms allowing the fast determination of the optimal solutions given a preference model, a key question is how to assess the preference parameters of such sophisticated models to best fit the DM's preferences. In this paper, we address both issues simultaneously by studying the integration of preference elicitation into the resolution of MOCO problems with rank-dependent aggregators.

Preference elicitation on combinatorial domains is an active topic studied within the AI community that has motivated several contributions in various contexts, e.g., in multi-objective state space search [START_REF] Benabbou | Incremental weight elicitation for multiobjective state space search[END_REF], in multi-agents systems [START_REF] Benabbou | Solving multi-agent knapsack problems using incremental approval voting[END_REF][START_REF] Bourdache | Active preference elicitation based on generalized Gini functions: Application to the multiagent knapsack problem[END_REF], in stable matching problems [START_REF] Drummond | Preference elicitation and interview minimization in stable matchings[END_REF], in constraint satisfaction problems [START_REF] Boutilier | Constraintbased optimization and utility elicitation using the minimax decision criterion[END_REF], in Markov Decision Processes [START_REF] Regan | Eliciting additive reward functions for markov decision processes[END_REF][START_REF] Weng | Interactive value iteration for markov decision processes with unknown rewards[END_REF] and in MOCO problems [START_REF] Benabbou | Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights[END_REF]. Here we focus on regret-based incremental preference elicitation, an approach recently designed by AI researchers, as it was proved to be very effective in practice [START_REF] Benabbou | Combining preference elicitation and search in multiobjective state-space graphs[END_REF][START_REF] Boutilier | Constraintbased optimization and utility elicitation using the minimax decision criterion[END_REF][START_REF] Wang | Incremental Utility Elicitation with the Minimax Regret Decision Criterion[END_REF]. The idea is to use the minimax regret decision criterion to select informative preference queries at each step of the elicitation process, so as to progressively reduce the set of admissible parameters until a robust recommendation can be made. This elicitation approach has been mainly studied with linear models and/or explicit sets of solutions. In this paper, we show how to efficiently extend this approach to MOCO problems with imprecise preferences represented by rank-dependent aggregation functions; the proposed approach is illustrated on the multi-objective knapsack problem.

The paper is organized as follows: first we introduce the formal framework (Section 2) and present some related works (Section 3). Then, we introduce two regret-based interactive procedures for the multi-objective knapsack problem with unknown preferences: a local search method and a greedy algorithm. We prove that both procedures run in polynomial time and ask no more than a polynomial number of preference queries to the DM (Section 3). Finally, we provide numerical tests that demonstrate the practical efficiency of the proposed methods, comparing our results to those obtained by two existing methods: a two-phase method and the state-of-the-art regretbased solving method for general MOCO problems (Section 4).

THE GENERAL FRAMEWORK

The Multi-Objective Knapsack Problem

We consider a decision problem where the DM has to select a set of items (e.g., candidates, projects, objects) in a set I = {1, . . . , p}. In this problem, any subset of items can be represented by a solution vector x = (x1, . . . , xp) ∈ {0, 1} p where xi = 1 if item i is in the subset and xi = 0 otherwise. In the standard knapsack problem, the set X of admissible solutions is defined by linear constraints of the form p i=1 wixi ≤ W where wi ≥ 0 is the weight of item i and W ≥ 0 is the maximum total weight. For instance, in committee election problems, cardinality constraints are usually imposed to control the size of the elected committee or to ensure gender parity. For the simplicity of the presentation, we will only consider one cardinality constraint in this paper but the proposed algorithm can be easily adapted to problems with additional feasibility constraints.

In the multi-objective knapsack problem, we consider a finite set of objectives yj : I → R+, with j ∈ N = {1, . . . , n}, to be maximized. Thus any item i ∈ I is associated with a performance vector y(i) = (y1(i), . . . , yn(i)) ∈ R n + where yj(i) is the evaluation of item i on the j-th objective; for instance, yj(i) can be the utility of voter j for candidate i in committee election problems. Any solution x ∈ X is then characterized by a performance vector y(x) = (y1(x), . . . , yj(x)) defined by yj(x) = p i=1 xiyj(i) for all j ∈ N = {1, . . . , n}. In this framework, solutions are usually compared through their images in the objective space using the Pareto dominance relation: we say that performance vector a = (a1, . . . , an) ∈ R n Pareto dominates performance vector b = (b1, . . . , bn) ∈ R n (denoted by a P b) if and only if aj ≥ bj for all j ∈ N , with at least one strict inequality. Then a solution is said to be Pareto-optimal if and only its performance vector is not Pareto-dominated by that of any other admissible solution.

A standard way to model preferences over vectors consists in using an aggregation function fω : R n + → R+ that maps performance vectors to scalar values: given two solutions x, x representing two subsets of items, x is at least as good as x for the DM whenever fω(y(x)) ≥ fω(y(x )). In this paper, we focus on rank-dependent aggregation functions.

Rank-Dependent Aggregation Functions

Rank-dependent aggregation functions are scalarizing functions that sort the performance values by increasing order before mapping the performance vector into a scalar value, thus enabling to assign weighting coefficients to ranks rather than to objectives. To specify such aggregation functions, we will often denote by (•) a permutation defined on {1, . . . , n} such that y (1) (x) ≤ ... ≤ y (n) (x), sorting the performance values of a given solution x from the smallest to the largest. Here we focus on two families of rank-dependent aggregators, namely ordered weighted averages and Choquet integrals.

Ordered Weighted Averages

Ordered Weighted Averages (OWA) is one of the simplest families of rank-dependent aggregation functions: it is simply defined as the weighted sum applied on the sorted performance vectors [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF]. OWA is specified by a normalized weighting vector ω = (ω1, . . . , ωn) ∈ [0, 1] n where ωj is the weight associated to the performance ranked in the j-th position.

Definition 1 (OWA operator) The OWA value of solution x ∈ X is:

fω(y(x)) = n j=1 ωjy (j) (x)
This family of aggregators includes the minimum, maximum, median and all order statistics as a special case. It is often used in social choice theory with decreasing weights in order to favor wellbalanced Pareto-optimal solutions (see e.g., [START_REF] Korhonen | Choice behavior in interactive multiple-criteria decision making[END_REF][START_REF] Lesca | LP Solvable Models for Multiagent Fair Allocation problems[END_REF][START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF] in fair allocation problems or [START_REF] Goldsmith | Voting with rank dependent scoring rules[END_REF][START_REF] Elkind | OWA-based extensions of the chamberlin courant rule[END_REF] in voting problems).

Choquet Integrals

Choquet Integrals [START_REF] Choquet | Theory of capacities[END_REF][START_REF] Schmeidler | Integral representation without additivity[END_REF][START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF] is a more general family of aggregators which is appealing because it offers a wider flexibility due to a greater number of preference parameters. More precisely, these aggregators are specified by a capacity function ω : 2 N → [0, 1] such that ω(∅) = 0, ω(N ) = 1 and ω(A) ≤ ω(B) for all A ⊂ B ⊆ N , allowing a fine control of interactions between the objectives by assigning weights to coalitions of objectives.

Definition 2 (Choquet integral) The Choquet value of x ∈ X is:

fω(y(x)) = n j=1 y (j) (x) -y (j-1) (x) ω(X (j) ) with y (0) (x) = 0
where X (j) = {(j), . . . , (n)} is the set of objectives with respect to which x has a performance greater or equal to y (j) (x).

For illustration purposes, consider the following capacity function:

∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} ω 0 0.2 0.1 0.3 0.4 0.7 0.6 1
For a solution x with performance vector y(x) = (3, 2, 5), the Cho-

quet integral value is fω(x) = (2 -0) × ω({1, 2, 3}) + (3 -2) × ω({1, 3}) + (5 -3) × ω({3}) = 2 × 1 + 1 × 0.7 + 2 × 0.3 = 3.3.
The family of Choquet integrals includes the weighted sums (when ω is additive), OWA aggregators (when ω is symmetric) and weighted OWA operators [START_REF] Torra | The weighted OWA operator[END_REF] as a special case. Moreover, using a convex capacity (e.g., a belief function [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]) enables to model preferences for well-balanced Pareto-optimal solutions (see e.g., [START_REF] Chateauneuf | Diversification, convex preferences and non-empty core in the Choquet expected utility model[END_REF]).

Regret-Based Preference Elicitation

In this work, we assume that preference parameters ω are not known initially. Instead, we are given a (possibly empty) set Θ of pairs (a, b) ∈ R n + × R n + such that vector a is known to be preferred to vector b; such preference statements can be obtained by asking comparison queries to the DM. Let ΩΘ be the set of all parameters ω that are compatible with Θ, i.e. all parameters ω that satisfy the constraints fω(a) ≥ fω(b) for all (a, b) ∈ Θ.

Minimax regret is a decision criterion that is commonly used within the AI community to make robust recommendations under preference imprecision (e.g., [START_REF] Benabbou | Solving multi-agent knapsack problems using incremental approval voting[END_REF][START_REF] Boutilier | Constraintbased optimization and utility elicitation using the minimax decision criterion[END_REF]). It can be defined as follows:

Definition 3 (Pairwise Max Regret) The Pairwise Max Regret (PMR) of solution x ∈ X with respect to solution x ∈ X is:

P M R(x, x , ΩΘ) = max ω∈Ω Θ fω(y(x )) -fω(y(x))
In other words, P M R(x, x , ΩΘ) is the worst-case loss when recommending solution x instead of solution x to the DM.

Definition 4 (Max Regret) The Max Regret (MR) of x ∈ X is: M R(x, X , ΩΘ) = max x ∈X P M R(x, x , ΩΘ)
Thus M R(x, X , ΩΘ) is the worst-case loss when choosing solution x instead of any other feasible solution x ∈ X .

Definition 5 (Minimax Regret) The MiniMax Regret (MMR) is: M M R(X , ΩΘ) = min x∈X M R(x, X , ΩΘ)
According to the minimax regret criterion, an optimal solution is a solution that achieves the minimax regret (i.e., any solution in arg minx∈X M R(x, X , ΩΘ)). By definition, recommending any of these solutions enables to minimize the worst-case loss.

Note that, depending on Θ the set of available preference statements, the worst-case loss ensured by the minimax regret criterion might be at unacceptable level for the DM. Note also that the inequality P M R(•, •, Ω) ≤ P M R(•, •, Ω ) holds for any two sets Ω ⊆ Ω . Thus this worst-case loss can be decreased by collecting new preference information from the DM (inducing new constraints on ΩΘ the set of admissible parameters). This observation has led to the following elicitation approach: progressively ask preference queries to the DM until the MMR value drops below a given threshold δ ≥ 0 representing the maximum allowable gap to optimality [START_REF] Boutilier | Constraintbased optimization and utility elicitation using the minimax decision criterion[END_REF]; if we set δ = 0, then we obtain the best solution for the DM at the end of the execution. This approach, sometimes referred to as regret-based incremental elicitation, was efficiently used in various contexts, such as multicriteria decision making [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF][START_REF] Perny | Incremental preference elicitation for decision making under risk with the rank-dependent utility model[END_REF] and voting problems [START_REF] Benabbou | Solving multi-agent knapsack problems using incremental approval voting[END_REF][START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF].

RELATED WORKS

Recently it has been proposed to integrate regret-based incremental elicitation into constructive algorithms so as to produce efficient exact solving methods for MOCO problems. The general principle is to construct the optimal solution from optimal sub-solutions using the available preference information, and to ask preference queries only when necessary (see [START_REF] Benabbou | Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights[END_REF] for a synthesis). This approach has been mainly studied with linear aggregators in order to produce exact solving methods. In this paper, we extend this approach to rankdependent aggregators by proposing a very efficient regret-based greedy method for the knapsack problem that is guaranteed to run in polynomial time with no more than a polynomial number of queries.

Local search is a popular heuristic approach for solving hard combinatorial optimization problems [START_REF] Aarts | Local Search in Combinatorial Optimization[END_REF]. It can yield high-quality solutions by iteratively applying small modifications (local moves) to a solution with the goal of generating improving solutions. Thanks to its flexibility, local search has been successfully applied to a wide range of domains, including matching problems [START_REF] Gelain | Local search algorithms on the stable marriage problem: Experimental studies[END_REF][START_REF] Munera | Solving hard stable matching problems via local search and cooperative parallelization[END_REF], multi-agent problems [START_REF] Grubshtein | Partial cooperation in multiagent local search[END_REF] and natural language parsing [START_REF] Daum | Parsing natural language using guided local search[END_REF]. A regret-based local search method called Interactive Local Search (ILS) has been recently proposed for MOCO problems with rank-dependent aggregators, requiring that a (near-)optimal solution can be efficiently determined when the aggregation function is precisely known [START_REF] Benabbou | Combining local search and elicitation for multi-objective combinatorial optimization[END_REF]. In practice, this requirement is quite restrictive since most existing efficient algorithms for rank-dependent aggregators are designed for subclasses representing very specific decision behaviors or for problems involving very few objectives (e.g., [START_REF] Galand | Exact algorithms for owa-optimization in multiobjective spanning tree problems[END_REF][START_REF] Lust | Choquet optimal set in biobjective combinatorial optimization[END_REF]). In this paper, we propose a regret-based local search procedure specially designed for the knapsack problem that does not require existing solving methods.

Another regret-based method has been recently introduced for rank-dependent aggregators [START_REF] Benabbou | A general interactive approach for solving multi-objective combinatorial optimization problems with imprecise preferences[END_REF][START_REF] Bourdache | Active preference elicitation based on generalized Gini functions: Application to the multiagent knapsack problem[END_REF]. The idea is to identify informative queries by exploiting the extreme points of the polyhedron representing the admissible preference parameters; in the following, this exact method will be called IEEP for Incremental Elicitation based on Extreme Points. In [START_REF] Benabbou | A general interactive approach for solving multi-objective combinatorial optimization problems with imprecise preferences[END_REF], it is shown that IEEP outperforms the constructive regret-based algorithm presented in [START_REF] Benabbou | Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights[END_REF] for the multiobjective spanning tree problem with the weighted sum model. However, IEEP requires that (near-)optimal solutions can be determined efficiently when the preferences are known (as ILS). Our methods also differ from IEEP with respect to performance guarantees: IEEP is an exact exponential time method that may generate an exponential number of queries, whereas our heuristic methods run in polynomial time and ask no more than a polynomial number of queries. Our methods and IEEP will be compared in the numerical section.

Committee election (or multi-winner election) is another active topic studied within the AI community. The goal is to select individuals from a pool of candidates to form a committee that is consistent with the voters' preferences (e.g., [START_REF] Elkind | OWA-based extensions of the chamberlin courant rule[END_REF][START_REF] Fluschnik | Fair knapsack[END_REF]). This multi-agent variant of the knapsack problem is mostly studied with multi-winner voting rules (e.g., the Chamberlin-Courant rule [START_REF] Chamberlin | Representative deliberations and representative decisions: Proportional representation and the Borda rule[END_REF]) and social welfare functions (e.g., Nash welfare) from a computational complexity perspective, assuming that voters' preferences are known. There are a few notable exceptions: two regret-based incremental elicitation procedures designed for approval voting [START_REF] Benabbou | Solving multi-agent knapsack problems using incremental approval voting[END_REF] and the Chamberlin-Courant rule [START_REF] Lu | Multi-winner social choice with incomplete preferences[END_REF] respectively. In these papers, the authors assume that the voting rule (i.e. the aggregation function) is known but not individual utilities (i.e., performance vectors); we make the opposite assumption in this paper. More recently, a regret-based branch and bound procedure has been proposed for solving the multi-agent knapsack problem with an OWA operator, but it has been shown that IEEP achieves better results on this problem [START_REF] Bourdache | Active preference elicitation based on generalized Gini functions: Application to the multiagent knapsack problem[END_REF].

NEW INTERACTIVE HEURISTIC METHODS

For MOCO problems, computing M M R(X , ΩΘ) at every step of the elicitation procedure may induce prohibitive computation times due to the possibly large number of Pareto-optimal solutions; this may indeed require to compute the pairwise max regrets for all pairs of distinct Pareto-optimal solutions in X (see Definitions 3,4 and 5). Therefore, we propose instead to combine heuristic search and regret-based incremental elicitation so as to reduce both computation times and number of queries by focusing on promising solutions.

A Regret-Based Local Search

We now introduce an interactive local search procedure that uses regret-based incremental elicitation techniques to select solutions from generated neighborhoods; this algorithm, called RBLS for Regret-Based Local Search, is summarized in Algorithm 1.

Initialization. First, we identify a promising feasible solution by applying the following greedy algorithm: starting from an empty set of items, we iteratively select an item i (among the remaining items) that maximizes the arithmetic mean 1/n n j=1 yj(i) so as to construct a good compromise solution in polynomial time.

Interactive local search. Then, starting from the solution obtained at the initialization step (denoted by x * hereafter), we iteratively move from solution to solution by considering local improvements:

• Firstly, we generate a set X * of feasible solutions from solution

x * using the neighborhood function consisting in removing one item from subset x * and adding one item to x * (all combinations are performed). Then, any solution that is Pareto-dominated by another solution is removed from X * . Note that for OWA operators the most discriminant Lorenz dominance can be used instead [START_REF] Perny | A decision-theoretic approach to robust optimization in multivalued graphs[END_REF]. • Secondly, we select a solution for the next iteration step by applying the standard regret-based incremental elicitation approach on set X * . More precisely, while M M R(X * , ΩΘ) > δ holds, the DM is asked to compare two performance vectors a, b ∈ R n + and then ΩΘ is restricted by inserting the linear constraint fω(a) ≤ fω(b) (or fω(b) ≥ fω(b) depending on her answer). Finally, if M R(x * , X * , ΩΘ) ≤ δ holds at the end of the elicitation process, then we stop by returning x * (no local improvement). Otherwise, for the next iteration step, x * is replaced by a neighbor solution that minimizes the max regret in X * .

Termination. We stop the process by returning solution x * after at most max it number of iteration steps, where max it is polynomial in the problem size.

Θ ← Θ ∪ {(a, b)} ΩΘ ← {ω : ∀(a, b) ∈ Θ, fω(a) ≥ fω(b)} end while --| Move to another solution: if M R(x * , X * , ΩΘ) > δ then x * ← Select(arg minx∈X * M R(x, X * , ΩΘ)) it ← it + 1 else improve ← false end if end while return x *
Example 1 We now present an execution of RBLS. Consider an instance of the 3-objectives knapsack problem with 10 items (denoted by i1, . . . , i10), where X the set of feasible solutions only includes the subsets of size at most 5. The performance vectors are as follows: We assume here that the DM's preferences can be represented by an OWA operator fω * with the hidden decreasing weights ω * = (0.7, 0.2, 0.1). We start the execution of RBLS with an empty set of preference statements (i.e. Θ = ∅) and δ = 0. Hence ΩΘ is initially the set of all weighting vectors ω = (ω1, ω2, ω3) ∈ [0, 1] 3 such that ω1 + ω2 + ω3 = 1 and ω1 ≥ ω2 ≥ ω3. Note that ΩΘ is a convex polyhedron since fω(a) is linear in ω for fixed performance vector a. The extreme points of ΩΘ are (0.5, 0.5, 0), ( 13 , 1 3 , 1 3 ) and (1, 0, 0) initially; in Figure 1, ΩΘ is represented by the triangle ABC in the space (ω1, ω2), ω3 being implicitly defined by ω3 = 1 -ω1 -ω2.

Initialization step: First, we compute the optimal solution for the weighted sum with weights ( 1 3 , 1 3 , 1 3 ) by using our greedy algorithm. We obtain solution x * = (0, 1, 0, 0, 1, 0, 1, 1, 0, 1) whose performance vector is y(x * ) = [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Choquet | Theory of capacities[END_REF][START_REF] Weng | Interactive value iteration for markov decision processes with unknown rewards[END_REF].

Local Search: At the first iteration step, only two neighbors of x * are non-dominated, and the set X * contains three solutions, denoted by x 1 (= x * ), x 2 and x 3 , which are evaluated as follows: y(x 1 ) =

ω 1 ω 2 • • • ω * + B 0.5 + A 0 • C 1 Figure 1. Initial set Ω Θ . ω 1 ω 2 • ω * + • D • E 0 + 0.5 • C + 1 Figure 2. Ω Θ after 1 query. ω 1 ω 2 • ω * + • D • F • G 0 + 0.5 • C + 1 Figure 3
. Ω Θ after 2 queries. [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Choquet | Theory of capacities[END_REF][START_REF] Weng | Interactive value iteration for markov decision processes with unknown rewards[END_REF], y(x 2 ) = (24, 28, 43) and y(x 3 ) = [START_REF] Drummond | Preference elicitation and interview minimization in stable matchings[END_REF][START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF]. Since M M R(X * , ΩΘ) = 1.5 > 0, we ask the DM to compare two solutions in X * , say x 2 and x 3 . We have fω * (y(x 2 )) = 26.7 > fω * (y(x 3 )) = 25.2. Therefore the DM prefers solution x 2 to solution x 3 . Thus we obtain Θ = {((24, 28, 43), [START_REF] Drummond | Preference elicitation and interview minimization in stable matchings[END_REF][START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF])} and ΩΘ is restricted by the linear constraint fω(y(x 2 )) ≥ fω(y(x 3 )), i.e. ω2 ≤ 1 8 + 3 8 ω1 (see Figure 2 where ΩΘ is represented by CDE). Now we have M M R(X * , ΩΘ) = M R(x 2 , X * , ΩΘ) = 0. Therefore we stop asking queries and we move from solution x * = x 1 to solution x 2 for the next step (i.e., we now set x * = x 2 ).

At the second step, X * includes only 5 non-dominated solutions denoted by x 1 (= x * ), x 2 , x 3 , x 4 and x 5 with the following evaluations: y(x 1 ) = (24, 28, 43), y(x 2 ) = [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Choquet | Theory of capacities[END_REF][START_REF] Weng | Interactive value iteration for markov decision processes with unknown rewards[END_REF], y(x 3 ) = [START_REF] Lesca | LP Solvable Models for Multiagent Fair Allocation problems[END_REF][START_REF] Galand | Exact algorithms for owa-optimization in multiobjective spanning tree problems[END_REF][START_REF] Perny | A decision-theoretic approach to robust optimization in multivalued graphs[END_REF], y(x 4 ) = [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Drummond | Preference elicitation and interview minimization in stable matchings[END_REF][START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF] and y(x 5 ) = [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Elkind | OWA-based extensions of the chamberlin courant rule[END_REF][START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF]. Since M M R(X * , ΩΘ) = 7 11 ≥ 0, the DM is asked to compare two solutions, say x * and x 5 . Since fω * (y(x 1 )) = 26.7 > fω * (y(x 5 )) = 25.2, the DM prefers x * to x 5 . Then Θ is set to {((24, 28, 43), [START_REF] Drummond | Preference elicitation and interview minimization in stable matchings[END_REF][START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF]), ((24, 28, 43), [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Elkind | OWA-based extensions of the chamberlin courant rule[END_REF][START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF])} and ΩΘ is restricted by ω2 ≤ 8 15 -1 3 ω1 (see Figure 3 where ΩΘ is represented by CDFG). Now we have M R(x * , X * , ΩΘ) = 0. Therefore x * is a local optimum (variable improve is set to false and the while loop ends). RBLS ends by returning x * = (0, 0, 1, 0, 1, 0, 1, 1, 0, 1) which is the preferred solution. Thus only 2 queries were needed to discriminate between the 27 Pareto-optimal solutions of this instance.

A Regret-Based Greedy Algorithm

In this subsection, we propose a new interactive solving method that consists in integrating regret-based incremental elicitation techniques into a greedy algorithm. Our algorithm, called RBGA for Regret-Based Greedy Algorithm, starts from an empty set of items (denoted by S hereafter) and then iterates as follows:

• First, we compute X * the set of all (partial) solutions obtained by adding one item to set S; formally X * = {S ∪ {i} : i ∈ I\S}.

Then, while M M R(X * , ΩΘ) > δ holds, we ask preference queries to the DM and update the set of admissible preference parameters accordingly. • Once M M R(X * , ΩΘ) ≤ δ holds, we select an item i * from I\S such that S ∪ {i * } minimizes the max regret. Finally, item i * is added to set S for the next iteration step.

Termination. RBGA stops whenever the knapsack capacity is reached, i.e. after exactly W iteration steps (see Algorithm 2).

Algorithm 2 RBGA

IN ↓ P : a multi-objective knapsack problem; fω: a family of rankdependent operators; Θ: a set of statements; δ: a positive threshold.

--| Initialization:

ΩΘ ← {ω : ∀(a, b) ∈ Θ, fω(a) ≥ fω(b)} S ← ∅ it ← 0 --| Greedy Search: while it < W do X * ← {S ∪ {i} : i ∈ I\S} --| Standard Regret-Based Elicitation: while M M R(X * , ΩΘ) > δ do --| Ask the DM to compare two solutions: (a, b) ← Query(X * ) --| Update preference information: Θ ← Θ ∪ {(a, b)} ΩΘ ← {ω : ∀(a, b) ∈ Θ, fω(a) ≥ fω(b)} end while --| Item Selection: i * ← Select(arg min i∈I\S M R(S ∪ {i}, X * , ΩΘ)) S ← S ∪ {i * } it ← it + 1 end while return S
Note that, when the DM's preferences are represented by a weighted sum that is precisely known, an optimal solution can be obtained by a greedy algorithm that simply selects an item maximizing the aggregated value at each iteration step, until the knapsack capacity is reached (here after W steps). When the weighted sum is imprecisely known, one may ask preference queries at each step until identifying an item maximizing the "unknown" aggregated value (i.e., until there is an item with a max regret equal to zero); that is precisely what RBGA does when δ = 0. Thus, RBGA necessarily returns an optimal solution according to the DM's preferences when fω is a weighted sum and δ = 0 (for δ > 0, one can easily prove that the worst-case loss is bounded above by W × δ). Moreover, we observed in practice that it often returns the optimal solution with OWA operators and Choquet integrals (see Section 4), and it constructs the optimal solution when applied to Example 1 with only two queries.

Performance guarantees

This subsection is devoted to the proof of the following result:

Proposition 1 RBLS and RBGA can be implemented in such way that they run in polynomial time and ask no more than a polynomial number of queries for OWA aggregators and Choquet integrals.

We remark first that the number of iteration steps of the outer loop is polynomial (in the problem size) for both procedures, and this is also the case for the size of X * at each iteration step.

OWA operators

On the number of preference queries. Since the number of iteration steps of the outer loop is polynomial for both RBLS and RBGA, the number of generated queries is also polynomial if and only if the minimax regret of X * drops below δ after a polynomial number of comparison queries at each iteration step of the search procedures.

To do so, one can simply apply the Current Solution Strategy (CSS) [START_REF] Boutilier | Constraintbased optimization and utility elicitation using the minimax decision criterion[END_REF] which consists in asking to compare a solution x achieving the minimax regret to one of its adversary's choice (i.e. a solution in arg max x ∈X * P M R(x, x , ΩΘ)) at each iteration step of the elicitation process. By doing so, one can ensure that the minimax regret will be equal to zero after at most |X * | -1 queries since at least one solution is eliminated after every comparison query.

On the computation times. Recall that both the number of steps and the size of X * at each step are polynomial in the problem size. Moreover, we have just proved that, at each step of the outer loop, the number of preference queries (hence the number of steps of the inner loop) is polynomial when applying the CSS strategy. Therefore, we only need to prove that MMR-computations can be performed in polytime. Recall that M M R(X * , ΩΘ) can be obtained by solving at most |X * | 2 pairwise max regrets (see Definitions 4 and 5). Therefore, it is sufficient to show that pairwise max regrets can be computed in polynomial time. For OWA aggregators, even though fω(a) = n j=1 ωja (j) is non-linear in a for fixed parameters ω, it is linear in ω for fixed a. Thus P M R(x, x , ΩΘ) can be obtained in polynomial time by solving the following linear program:

max ω n j=1 ωjy (j) (x ) - n j=1 ωjy (j) (x) s.t. j∈N ωj = 1 ωj ≥ 0, ∀j ∈ N n j=1 ωja (j) - n j=1 ωjb (j) ≥ 0, ∀ (a, b) ∈ Θ
The constraints ωj ≥ ωj+1 for all j ∈ {1, . . . , n -1} can be added so as to favor well-balanced solutions.

Choquet integrals

As regards the number of queries, the same reasoning as for OWA aggregators applies for Choquet integrals. This is not the case for computation times. More precisely, since fω(a) is linear in ω for fixed a with Choquet integrals, P M R(x, x , ΩΘ) can also be obtained by solving the following program: However, in this linear program, the number of variables and constraints is exponential in the number of variables. This linear program can be simplified for some subclasses of Choquet integrals defined using an alternative formulation in terms of Möbius masses m [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF]:

fω(y(x)) = n A⊆N m(A) min j∈A yj(x) max ω n j=1 y (j) (x )-y (j-1) (x ) ω(X (j) )-y (j) (x)-y (j-1) (x) ω(X (j) ) s.t. ω(∅) = 0, ω(N ) = 1 ω(A) ≤ ω(B), ∀A ⊂ B ⊆ N n j=1 a (j) -a (j-1) ω(A (j) )-b (j) -b (j-1) ω(B (j) ) ≥ 0, ∀(a, b) ∈ Θ
where m(A) = B⊆A (-1) |A\B| ω(B) for all A ⊆ N . For instance, for the subclass of convex capacities characterized by positive Möbius masses (a.k.a. belief functions [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]), the monotonicity constraints ω(A) ≤ ω(B), with A ⊂ B ⊆ N , are naturally satisfied due to the non-negativity of Möbius masses. For the subclass of 2-additive capacities (i.e., m(A) = 0 for all |A| > 2 and m(A) = 0 for some set |A| = 2), it has been proposed to use the fact that these particular capacities form a convex polytope with only n2 extreme points (see e.g., [START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF]), yielding a linear formulation involving a quadratic number of variables and constraints; hence for 2-additive capacities, our procedures combined with the CSS strategy run in polynomial time and generate no more than a polynomial number of queries.

For general capacities, it has been shown in [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF] that PMRoptimization problems can be formulated as linear programs with only a linear number of variables and constraints, provided that the DM is only asked to compare binary alternatives to constant utility profiles. In the same paper, the authors propose a query generation strategy that is very efficient in practice but no theoretical guarantee is provided regarding the number of queries. In fact, the proposed query generation strategy can be adapted to ensure a polynomial number of queries by simply selecting the constant utility profile in the middle of the interval representing the possible capacity values, instead of selecting the query that minimizes the worst-case minimax regret (see e.g., [START_REF] Benabbou | Adaptive elicitation of preferences under uncertainty in sequential decision making problems[END_REF]). Thus, our procedures are also polynomial for general Choquet integrals.

EXPERIMENTAL RESULTS

We now provide numerical results showing the practical efficiency of our algorithms in terms of computation times (given in seconds), number of queries and gap to optimality (error) expressed in terms of percentage from the optimal solution. The results are averaged over 30 runs and "/" means that the timeout (30 mins) is exceeded.

Instances. We consider instances of the multi-objective knapsack problem with |I| = 50 and 100 items and we vary n the number of criteria from 2 to 6. Instances are generated as follows: performance vectors y(i), i ∈ I, are uniformly drawn in {1, . . . , 1000} n and W the knapsack capacity is set to 0.5 × |I| so as to obtain difficult instances (i.e., with a large number of Pareto-optimal solutions).

Preferences. The DM's preferences are represented by the following aggregation models:

• OWA: OWA aggregators with decreasing positive weights to model preferences for well-balanced performance vectors. • Choquet: Choquet integrals with 2-additive belief functions (see Section 4.3.2) to model interactions between criteria and favor well-balanced vectors.

We start the executions with an empty set of preference statements; therefore ΩΘ is initially equal to:

• {ω ∈ R n + : ∀j ∈ {1, . . . , n -1}, ωj+1 ≥ ωj; n j=1 ωj = 1} for the OWA model.

• {mA ∈ R+, A ⊆ N, |A| ≤ 2 : ∃A, |A| = 2, mA = 0; A mA = 1}
for Choquet integrals.

During the execution of the methods, the answers to queries are simulated using a weighting vector (ω for OWA, m for Choquet) that is randomly generated before running the methods. The weighting vector is generated using the procedure presented in [START_REF] Rubinstein | Generating random vectors uniformly distributed inside and on the surface of different regions[END_REF] so as to guarantee a uniform distribution of the weights.

Regret-Based Solving Methods. In this section, we compare the results obtained by the following regret-based procedures:

• RBLS: the proposed local search method with max it = 100.

• RBGA: the proposed greedy method.

• Two-Phase δ : a two-phase method which consists in first constructing a "well-represented" Pareto set and then applying the CSS strategy on this set until the minimax regret drops below threshold δ ≥ 0; here we generate sets of size at most 3000. • IEEP δ : the solving method introduced in [START_REF] Benabbou | A general interactive approach for solving multi-objective combinatorial optimization problems with imprecise preferences[END_REF] for general MOCO problems, which is based on the extreme points of ΩΘ. This method is guaranteed to return a solution x ∈ X such that MR(x, X , ΩΘ) ≤ δ holds at the end of the execution. To compute the optimal solutions attached to extreme points, we simply return the solutions that maximize the corresponding aggregated values in the representative Pareto set.

To generate Pareto sets for both Two-Phase δ and IEEP δ , we use dynamic programming [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF] and fast Pareto dominance checking [START_REF] Jaszkiewicz | ND-Tree-based update: A fast algorithm for the dynamic nondominance problem[END_REF] to reduce computation times (e.g., the Pareto set includes about 2 × 10 6 solutions for the instances with 50 items and 6 objectives). For both procedures, the reported computation times do not include the time needed to generate the Pareto set.

Implementation details. Numerical tests were performed on a Intel Core i7-950 @ 3.06 GHz with 11,7 GB of RAM, with a program written in C++, and pairwise max regret optimizations are performed by CPLEX Optimizer 2 .

Results for OWA. First we compare the results obtained by the two proposed procedures (see Table 2). We observe that RBLS is more efficient that RBGA in terms of number of queries and error in all the settings (while achieving comparable computation times); for instance, when using RBLS instead of RBGA for n = 6 with δ = 0.5, the number of queries is divided by 2 and the error is decreased by a factor of 4. Note that the error is very low in all the settings (below 1%) and that varying δ from 0 to 0.5 does not really impact on the performances of both procedures for OWA aggregators. Now we compare RBLS to IEEP δ and Two-Phase δ (see Table 3); here we set δ = 0.01 to allow for the same error as our method (to be as fair as possible). We observe that RBLS is drastically faster than IEEP0.01 and generates far fewer queries in all the settings. To give an example, when using IEEP0.01 instead of RBLS (with δ = 0.5) for n = 6, the computation time is reduced by a factor of 260 and the number of queries is divided by 3. Finally, we see that RBLS is much faster than Two-Phase0.01 but the former asks a few more preference queries than the latter (at most 3 queries with δ = 0.5). Results for Choquet. In Table 2, we see that varying δ from 0 to 0.5 allows to significantly reduce the computation time and the number of preference queries of both RBLS and RBGA without increasing the error too much (at most 2%). For instance, for n = 6, RBLS ends after 16 minutes and 154 queries for δ = 0 against 2 minutes and 32 queries for δ = 0.5. This is mainly due to the fact that more preference information is needed (more preference parameters) and PMR-optimizations are more computationally demanding (a quadratic number of variables) when considering Choquet instead of OWA. Now, when comparing our procedures, we see that RBLS is better than RBGA in terms of number of queries but the latter is much faster than the former on the bigger instances. For example, for n = 6 and δ = 0.5, RBLS generates two times less preference queries than RBGA but RBGA is about 15 times faster than RBLS. Finally, we compare our procedures to IEEP δ and Two-Phase δ (see Table 3) with δ = 0.02 to allow for the same error as our methods. We see that both IEEP0.02 and Two-Phase0.02 induce prohibitive computation times when increasing the number of criteria (even when ignoring the time required to compute the representative Pareto set). For IEEP0.02, the problem is even more dramatic since the timeout is reached as soon as n ≥ 4. This is mainly due to the very large number of extreme points of ΩΘ, which increases exponentially with the number of collected preference statements; for instance, we stopped IEEP0.02 after 3 hours for n = 4 and we observed that only 25 queries were asked and 10 4 extreme points were generated on average. In fact, our procedures can be applied to bigger instances, as shown in Table 4 with 100 items.

CONCLUSION

In this paper, we have proposed two new regret-based interactive procedures to solve multi-objective knapsack problems with unknown preferences: a local search method (called RBLS) and a greedy algorithm (called RBGA). To model the DM's preferences, we have considered the following two families of non-linear aggregators: OWA operators and Choquet integrals. We have proved that both RBLS and RBGA run in polynomial time and ask no more than a polynomial number of queries. Moreover, we have compared the performances achieved by RBLS and RBGA with that of two different regret-based solving methods. In particular, it is shown that the latter two procedures are both outperformed by RBLS and RBGA in all considered instances. We have also observed that RBLS performs better than RBGA for OWA operators, but RBGA is much faster for Choquet integrals (even if RBLS may still be preferred to minimize the number of queries). An interesting direction of research is to compare our methods to a very recent heuristic approach based on genetic algorithms, which may require to adapt the latter approach to efficiently handle rank-dependant aggregators [START_REF] Benabbou | An interactive regret-based genetic algorithm for solving multi-objective combinatorial optimization problems[END_REF].

Algorithm 1 RBLS

 1 IN ↓ P : a multi-objective knapsack problem; fω: a family of rankdependent operators; Θ: a set of statements; δ: a positive threshold. --| Initialization: ΩΘ ← {ω : ∀(a, b) ∈ Θ, fω(a) ≥ fω(b)} x * ← ComputeInitialSolution(P ) it ← 0 improve ← true --| Local Search: while improve and (it < max it) do --| Generation of neighbors: X * ← ComputeAllSwaps(x * ) --| Standard regret-based elicitation: while M M R(X * , ΩΘ) > δ do --| Ask the DM to compare two solutions: (a, b) ← AskQuery(X * ,ΩΘ) --| Update preference information:

Table 1 .

 1 Performance vectors attached to items.

		i 1	i 2	i 3	i 4	i 5	i 6	i 7	i 8	i 9	i 10
	y 1	4	10	3	10	4	4	10	8	1	3
	y 2	4	1	7	2	6	1	3	3	4	5
	y 3	3	9	7	2	9	7	8	9	10	10

Table 2 .

 2 Results obtained by RBLS and RBGA the two proposed procedures for 50 items.

					OWA						Choquet
			RBLS		RBGA			RBLS			RBGA
		n	time queries error	time queries error		time queries error	time queries error
		2	0.07	3.0	0.00	0.08	6.4	0.81		0.42	5.6	0.14	0.44	10.70	0.10
		3	0.20	7.9	0.13	0.16	10.4	0.91		7.99	19.7	0.16	2.31	33.83	0.17
	δ = 0	4	0.02	3.0	0.00	0.19	18.2	0.63		48.04	54.0	0.15	7.27	70.13	0.63
		5	0.27	8.3	0.18	0.25	17.4	0.64	144.67	79.3	0.09	19.5	119.97	0.59
		6	0.65	17.2	0.24	0.29	17.1	0.81	975.96	154.0	0.23	38.9	179.93	0.21
		2	0.08	3.6	0.00	0.08	6.5	0.92		0.43	4.73	0.15	0.36		9.03	0.00
		3	0.15	5.7	0.10	0.13	8.9	0.94		3.76	9.36	1.16	1.60	24.76	0.16
	δ = 0.5	4	0.02	2.0	0.00	0.18	16.1	0.79		20.17	20.13	0.18	4.12	39.90	0.27
		5	0.23	6.4	0.19	0.22	14.8	0.65		43.56	26.40	0.12	7.12	51.83	0.54
		6	0.31	7.3	0.18	0.27	14.6	0.85	129.18	32.83	0.28	8.82	66.27	0.32
				OWA						Choquet
		Two-Phase0.01		IEEP0.01		Two-Phase0.02		IEEP0.02
	n	time queries	error	time queries	error		time	queries error	time	queries error
	2	4.3	2.5	0.02	10.1	4.7	0.00		1.6	4.2	0.04	8.4		3.9	0.01
	3	36.4	3.1	0.05	16.9	8.0	0.03	298.4	12.5	0.13	19.5		9.0	0.17
	4	46.4	2.7	0.46	33.9	15.0	0.00	416.6	30.2	0.32	/		/	/
	5	82.1	4.5	0.68	40.6	18.3	0.00	859.3	55.8	0.52	/		/	/
	6	95.3	4.1	0.96	80.6	26.8	0.00		/	/	/	/		/	/

Table 3 .

 3 Results obtained by IEEP δ and Two-Phase δ for 50 items.

				OWA					Choquet
			RBLS			RBGA			RBLS			RBGA
	n	time queries error	time queries error	time queries error	time queries error
	2	0.1	3.4	0.04	0.2	8.5	1.52	1.9	7.0	0.30	1.2	12.6	0.28
	3	0.3	5.5	0.01	0.7	13.6	1.15	25.8	15.5	0.91	9.1	34.3	0.23
	4	1.1	11.4	0.16	0.7	21.6	0.71	124.4	27.2	0.06	27.3	53.1	0.43
	5	4.1	26.5	0.29	1.1	24.5	0.54	516.4	38.8	0.11	44.5	80.6	0.26
	6	5.2	28.3	0.42	1.0	25.7	0.72	1183.5	47.8	0.10	64.3	107.0	0.23

Table 4 .

 4 Results obtained by RBLS and RBGA the two proposed procedures for 100 items (δ = 0.5).

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France, email: firstname.lastname@lip6.fr

https://www.ibm.com/analytics/cplex-optimizer

Acknowledgements

This work was supported by the Paris Ile-de-France Region, the FMJH Program PGMO and EDF-THALESE-ORANGE.


Nawal Benabbou
email: nawal.benabbou@lip6.fr

Mithun Chakraborty
email: mithun@comp.nus.edu.sg

Edith Elkind
email: elkind@cs.ox.ac.uk

Yair Zick
email: zick@comp.nus.edu.sg

Fairness Towards Groups of Agents in the Allocation of Indivisible Items

Keywords: Fair Allocation of Indivisible Items, Typewise Envy-freeness up to one item, Non-wasteful Allocation

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. We extend multiple desirable properties of an allocation of indivisible goods 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. In particular, we define a new concept of waste for this setting; we 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 polynomialtime algorithm for computing a non-wasteful TEF1 allocation for binary agent-item utilities.

Introduction

Consider an academic department faced with the task of assigning incoming graduate students to advisers. It has computed a score for each potential advisoradvisee pair and cares about the overall score of the matching; but the faculty is divided into research groups and the department might also wish to achieve a fair distribution of students (or, more correctly, student scores) across these groups. A similar trade-off between efficiency/welfare and fairness might be desirable in other planning/allocation scenarios such as public housing allocation, e.g. agents are potential tenant households and items are flats in public housing blocks, individual agents having utilities over flats and a central authority desiring a fair allocation across groups of agents (in the same vein as the ethnicity quotas of the Singapore Housing and Development Board [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF]).

We can model these problems as a variant of the problem of fair allocation of indivisible goods (see e.g. [START_REF] Bouveret | Fair allocation of indivisible goods[END_REF]): here, we have an underlying weighted bipartite matching problem, with the nodes on the two sides being called items and agents for convenience, but the parties we are trying to be fair towards are not individual agents but subsets forming a partition over agents -we call these subsets types of agents. An important aspect of this problem is that all agents in a type do not derive utility from all items in the bundle allocated to that type (unlike the public goods scenario [START_REF] Fain | The core of the participatory budgeting problem[END_REF]): within a type, we assign items to agents under matching constraints with no regard to other types. Hence, the parties under consideration end up violating the additive bundle-valuation assumption present in much of recent work. There are some approaches (e.g. [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF]) that achieve good fairness guarantees but are agnostic to how a party computes its bundle valuation, hence if we use them naïvely, they can result in allocations that are wasteful/inefficient in some way given the structure of our problem. These considerations necessitate novel solution concepts and techniques for our setting.

Our contributions

We describe a new model of typewise fair allocation and define our desirable properties in Section 2 -in particular, non-wastefulness and typewise envyfreeness up to one item (TEF1) as well as a marginal envy-based variant of the latter (TMEF1). In Sections 3 and 4, we explore the problems of determining Pareto optimal, TMEF1 allocations and TEF1 allocations that maximize overall sum of weights respectively. In Section 5, we show experimentally that Lipton et al. [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF]'s classic algorithm equipped with a simple heuristic can produce TEF1 allocations with significantly reduced waste. Section 6 details a polynomial-time algorithm for computing a non-wasteful TEF1 allocation for binary agent-item utilities. We conclude with future research directions in Section 7.

Related work

There is a rich body of work on approaches towards the fair allocation of indivisible goods [START_REF] Bouveret | Fair allocation of indivisible goods[END_REF][START_REF] Markakis | Approximation algorithms and hardness results for fair division with indivisible goods[END_REF]. A popular fairness concept is envy-freeness [START_REF] Foley | Resource allocation in the public sector[END_REF]. A complete envy-free (EF) allocation may not exist but a relaxation that always does is one that is envy-free up to one item (EF1) [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF] where any envy towards an agent can be eliminated by removing an item from its bundle. The bounded-envy, polynomial-time algorithm due to Lipton et al. [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF] also produces an EF1 allocation for general valuation functions [START_REF] Plaut | Almost envy-freeness with general valuations[END_REF].

Extensions of envy-freeness to groups include strict envy-freeness [START_REF] Zhou | Strictly fair allocations in large exchange economies[END_REF]; coalition fairness or group envy-freeness [START_REF] Lahaie | Fair package assignment[END_REF] as well as envy-freeness of an individual/a group towards a group [START_REF] Todo | Generalizing envyfreeness toward group of agents[END_REF], both under monetary transfers; group fairness as defined by Conitzer et al. [START_REF] Conitzer | Group fairness for indivisible good allocation[END_REF]. Barman et al. [START_REF] Barman | Groupwise maximin fair allocation of indivisible goods[END_REF] recently defined a groupwise extension to the maximin share-based fairness concept. A major difference of these contributions with our model is that they deal with a σ-algebra of subsets of agents rather than an exogenously defined partition over agents. Notable papers that define fairness with respect to pre-defined groups of multiple players include those by Suksompong along with Manurangsi and Segal-Halevi [START_REF] Manurangsi | Asymptotic existence of fair divisions for groups[END_REF][START_REF] Suksompong | Approximate maximin shares for groups of agents[END_REF][START_REF] Segal-Halevi | Democratic fair allocation of indivisible goods[END_REF] where the utility structure is significantly different from ours, and Elzayn et al. [START_REF] Elzayn | Fair algorithms for learning in allocation problems[END_REF] whose concepts of utility and fairness are significantly different from ours. Recent work [START_REF] Fain | The core of the participatory budgeting problem[END_REF][START_REF] Fain | Fair allocation of indivisible public goods[END_REF] has also explored non-envy-based fairness criteria in the allocation of public goods under additive valuations.

We must also mention the literature on statistical fairness (also called group fairness) in the fundamentally different problem domain of classification in machine learning: the equalization of some statistical property of the classifier across groups of data instances based on sensitive/protected attributes ( [START_REF] Dwork | Fairness through awareness[END_REF][START_REF] Hardt | Equality of opportunity in supervised learning[END_REF][START_REF] Kearns | Preventing fairness gerrymandering: Auditing and learning for subgroup fairness[END_REF] and references therein); we are interested in fairness notions in terms of subjective valuations of items from the economics/social choice literature.

Model and definitions

Throughout the paper, [r] will denote the set {1, 2, • • • , r} for any positive integer r. Our model, an extension of the classic framework of matching on a weighted bipartite graph [START_REF] Lovász | Matching theory[END_REF], has the following ingredients: (i) a set N of n vertices called agents partitioned into k types N 1 , . . . , N k , (ii) a set M of m vertices called items, (iii) a weight/utility u(i, j) ∈ R + for each agent-item edge (i, j) ∈ N × M , such that for each i ∈ N (resp. at least one j ∈ M ), there is at least one j ∈ M (resp. each i ∈ N ) with u(i, j) > 0.

For any T ⊆ N and any S ⊆ M , a (T, S)-matching is defined as a subset of the edges T × S such that every vertex in T ∪ S is incident on at most one of the edges or, equivalently, as a binary matrix X = (x ij ) i∈T,j∈S such that for each agent i (resp. item j), there is at most one item j (resp. agent i) with x ij = 1, i.e. each item is assigned to at most one agent and each agent is assigned at most one item. The utilitarian social welfare USW(X) (or total weight) of a matching X is defined as the sum of the realized utilities of all agents under that matching:

USW(X)

i∈T j∈S

x ij u(i, j).

An optimal matching is one that maximizes the corresponding utilitarian social welfare. We are interested in a (N, M )-matching that trades off some welfare concept characterizing the entire agent population against some fairness criterion defined with respect to the agent types. More precisely, for every type p ∈ [k], we are given a type-value function v p : 2 M → R + which quantifies some concept of overall welfare derived by N p from some bundle or subset of items S ⊆ M in terms of the weights u(i, j), (i, j) ∈ N p × S. In this paper, we will use the following specific type-value function for every type:

Definition 1 (Utilitarian type-value function) The utilitarian type-value of any type p ∈ [k] for any bundle S ⊆ M is defined as the total weight of an optimal (N p , S)-matching:

v p (S) max X∈X (Np,S) USW(X), if S = ∅; 0, otherwise.
where X (N p , S) is the collection of all (N p , S)-matchings.

We will define the marginal utility ∆ p (S; j) of an item j ∈ M for a type p ∈ [k] and a bundle S ⊆ M as:

∆ p (S; j) v p (S ∪ {j}) -v p (S), if j ∈ S; v p (S) -v p (S\{j}), otherwise.
Given a type p and a bundle S, there can be multiple optimal (N p , S)-matchings with the same type-value but possibly differing in other efficiency and/or fairness properties (see discussion on Figure 1 at the end of this section) -with this in mind, we define an allocation in our setting as follows:

Definition 2 (Allocation) An allocation A is a collection of bundles M A 1 ,• • • , M A k , such that M A 1 ∪. . .∪M A k ⊆ M and M A p ∩M A q = ∅
for all p, q ∈ [k] with p = q, along with an optimal matching between each type N p and the corresponding bundle M A p for all p ∈ [k], thereby inducing a unique (N, M )-matching

X A = (x A ij ) i∈N,j∈M .
We call M A p the allocated bundle of type p under A and

M A 0 = M \ ∪ p∈[k] M A p
the set of withheld items. We will sometimes drop the superscript A when there is no ambiguity. A type p envies a type

q if v p (M A p ) < v p (M A q ); p envies q up to ν items, ν ∈ [|M A q |], if there is a subset C ⊆ M A q of size |C| = ν such that v p (M A p ) ≥ v p (M A q \C) and, for every subset C ⊆ M A q with |C | < ν, v p (M A p ) < v p (M A q \C
). We can analogously define the envy of a type for a bundle (up to any number of items).

With these fundamentals in place, we now define the desiderata of an allocation A that we investigate in this paper. The first three are concerned with efficiency; the rest are extensions of efficiency-agnostic fairness concepts introduced by Budish [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF] and Caragiannis et al. [START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF] respectively.

Definition 3 (Type-completeness) A is type-complete if ∪ p∈[k] M A p = M ; otherwise it is type-incomplete. 4
Definition 4 (Waste and non-wastefulness) An item j ∈ M is said to be wasted by an allocation A if it has a positive marginal utility for some type p ∈ [k] (i.e. ∆ p (M A p ; j) > 0) but is either withheld (i.e. j ∈ M A 0 ) or belongs to the allocated bundle of some type q = p for which it has zero marginal utility (i.e. j ∈ M A q and ∆ q (M A q ; j) = 0). A is called non-wasteful if it has no wasted item, and wasteful otherwise.

Definition 5 (Typewise Pareto optimality)

Allocation A 1 is said to type- wise Pareto dominate another allocation A 2 if v p (M A1 p ) ≥ v p (M A2 p ) for all types p ∈ [k] and v p (M A1 p ) > v p (M A2 p ) for some type p ∈ [k]
. An allocation that is not typewise Pareto dominated by any other allocation is typewise Pareto optimal.

Definition 6 (Typewise envy-freeness up to one item) Allocation A is typewise envy-free up to one item (TEF1) if for any two types p, q ∈ [k], p either does not envy q or envies q up to one item, i.e. there exists an item j

∈ M A q such that v p (M A p ) ≥ v p (M A q \{j}).
Definition 7 (Typewise marginal envy-freeness up to one item) Allocation A is typewise marginally envy-free up to one item (TMEF1) if for any p, q

∈ [k],
there is an item

j ∈ M A q such that v p (M A p ) ≥ v p (M A p ∪ M A q \{j})-v p (M A p ).
We are now ready to formulate and analyze specific problems that approach 'good' allocations in different ways. But first, we will provide a problem instance that we will use as a running example throughout the rest of the paper.

Example 1 Consider the problem depicted in Figure 1 and the bundles

M 1 = {1, 2, 6}, M 2 = M \M 1 :
there is a unique optimal (N 2 , M 2 )-matching with 3, 4, 5 assigned to b 1 , b 2 , b 3 respectively; but there are two optimal (N 1 , M 1 )-matchings in both of which 2 is assigned to a 2 : if 1 is assigned to a 1 and 6 remains unassigned, then we have a wasteful allocation since 6 could be assigned to b 4 so that ∆ 2 (M 2 ; 6) = 1; but if 6 is assigned to a 1 instead, the allocation is non-wasteful since no agent in N 2 has a positive utility for item 1. ; u(i, j) is 1 if there is an edge between agent i and item j, and 0 otherwise.

Typewise Pareto optimal TMEF1 allocation

In this section, we will adapt a result of Caragiannis et al. [START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF] to our setting.

To that end, we first state without proof a property of our type-value function (Definition 1) that is part of the folklore of weighted bipartite matching. Moreover, we define the Nash type-welfare of an allocation A as the product of the type-values, i.e.

k p=1 v p (M A p ).
Theorem 2. Every type-complete allocation that maximizes the Nash type-welfare is typewise Pareto optimal and TMEF1.

Proof. An "allocation", as defined in [START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF] as a partition of the set of items among all agents, translates to a type-complete allocation in our setting; also, since each v p (•) is monotone submodular by Theorem 1, we can use the natural extension of Theorem 3.5 of [START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF] to conclude that every maximum Nash type-welfare, typecomplete allocation is TMEF1 as well as typewise Pareto optimal.

The next result establishes that non-wastefulness is a weakening of typewise Pareto optimality in our setting.

Lemma 1. Any typewise Pareto optimal allocation is non-wasteful but the converse is not true.

Proof. If an allocation A had a wasted item j with positive marginal utility for a type q, then, by the definition of waste, we could augment M A q with j for an improved type-value without reducing any other type-value, resulting in an allocation that Pareto dominates A. For the converse, Example 1 provides a counterexample: Take again the allocation A 1 with bundles

M A1 1 = {1, 2, 6}, M A1 2 = M \M A1
1 , item 1 remaining unassigned and 2, . . . , 6 assigned to a 2 , b 1 , b 2 , b 3 , a 1 respectively. This is non-wasteful (and incidentally also TEF1) but is Pareto dominated by allocation A 2 with bundles

M A2 1 = {1, 2, 3}, M A2 2 = M \M A2 1 since v 1 (M A2 1 ) = 3 > 2 = v 1 (M A1 1 ) and v 2 (M A2 2 ) = v 2 (M A1 2 ) = 3.
This result implies, in conjunction with Theorem 2, that a maximum Nash type-welfare, type-complete allocation is also non-wasteful. In spite of the above existence results, maximizing Nash welfare with indivisible items is known to be hard in general, and the above guarantees may break down for constantfactor approximations [START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF]. Moreover, marginal envy-freeness up to one item is a relatively new fairness concept that is hard to explain and not extensively used as yet. Hence, in subsequent chapters, we will focus on efficient TEF1 allocations.

Assignment under TEF1 constraints

We first study the problem of finding a TEF1 allocation A that maximizes the sum of weights of the induced matching:

USW(X A ) i∈N j∈M x A ij u(i, j) = p∈[k] v p (M A p ).
This is equivalent to the assignment problem [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF] under TEF1 constraints specified in Definition 6. We define the decision version of the problem as follows:

Definition 8 (AssignTEF1) An instance of the Assignment under TEF1 constraints ( AssignTEF1) problem is given by parameters (i) to (iii) of Section 2 as well as a value U ∈ R + ; it is a 'yes'-instance iff it admits a TEF1 allocation A with a utilitarian social welfare at least U .

A TEF1 allocation always exists under our Definition 2 (see Section 5 for further details); we prove next that it is hard to compute one with the maximum USW.

Theorem 3. The AssignTEF1 problem is NP-complete, even with only 3 types.

Proof. The problem is in NP: given an allocation A, we need to evaluate k typevalue function, solving the polynomial-time unconstrained assignment problem (see e.g. [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF]) each time, and can hence verify that A satisfies all requirements in polynomial time.

We will now describe a polynomial-time reduction to AssignTEF1 from the NP-complete partition problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. An instance of the latter is given by a set S = {s j } j∈[l] of l positive integers that sum to σ; it is a 'yes'-instance iff S can be partitioned into two subsets S 1 and S 2 such that both sum to σ/2. Given an instance of the partition problem, we construct an AssignTEF1 instance as follows. We have a set of l + 2 items M = [l + 2] and a set of 2l + 4 agents N partitioned into k = 3 types

N 1 = {a i } i∈[l+1] , N 2 = {b i } i∈[l+1] ,
and

N 3 = {c 1 , c 2 }. The utilities are given by u(a j , j) = u(b j , j) = s j , ∀j ∈ [l]; u(a l+1 , j) = u(b l+1 , j) = σ/2, ∀j ∈ {l + 1, l + 2}; u(c 1 , l + 1) = u(c 2 , l + 2) =
κ for an arbitrarily large constant κ > σ; u(i, j) = 0 for every other (i, j)-pair. Finally, let U = 2κ + σ.

First, we prove that, for any 'yes'-instance of the partition problem, so is the corresponding AssignTEF1 instance we constructed. Given the two parts S 1 and S 2 of S as above, consider the bundles M 1 = {j ∈ M : s j ∈ S 1 }, M 2 = {j ∈ M : s j ∈ S 2 }, and M 3 = {l + 1, l + 2} allocated to N 1 , N 2 , and N 3 respectively, with no withheld items; evidently, assigning item j to agent a j (resp. b j ) for every s j in S 1 (resp. S 2 ), l + 1 to c 1 , and l + 2 to c 2 constitutes the unique optimal matching between each type and its allocated bundle, inducing an allocation A (Definition 2). We want to prove that A is TEF1. Note that for the above utilities, v 3 (M 3 ) = 2κ > 0 = v 3 (M q ) for all q ∈ {1, 2};

v 1 (M 1 ) = v 2 (M 1 ) = sj ∈S1 s j = σ/2 and also v 2 (M 2 ) = v 1 (M 2 ) = sj ∈S2 s j = σ/2 from
the definition of a 'yes'-instance of the partition problem; v 1 (M 3 \{j}) = v 2 (M 3 \{j}) = σ/2 for all j ∈ M 3 . Hence, each type envies any other type up to at most one item under

A. Finally, USW(X A ) = σ/2 + σ/2 + 2κ = 2κ + σ = U .
Next, we prove that, assuming our constructed AssignTEF1 instance to be a 'yes'-instance, so is the partition instance. Let A be an allocation verifying all desiderata. Since κ > σ and the maximum sum of realized utilities that can be achieved from items j ∈ [l] is σ, the only way for USW(X A ) to be at least U = 2κ + σ is to have {l + 1, l + 2} ⊆ M A 3 with c 1 (resp. c 2 ) assigned to l + 1 (resp. l + 2). Moreover, since the other items must contribute a sum of realized utilities at least σ, the utility structure implies that each j ∈ [l] must be assigned to either a j or b j ; hence, M 3 = {l + 1, l + 2}, there are no withheld items, and

v 1 (M A 1 ) + v 2 (M A 2 ) = σ. Now consider the sets S 1 = {s j ∈ S : j ∈ M A 1 } and S 2 =
{s j ∈ S : j ∈ M A 2 }: It is evident that they form a partition of S such that the sum of the values in S 1 (resp. S 2 ) equals v

1 (M A 1 ) (resp. v 2 (M A 2 )). Since A is TEF1, we must have v 1 (M A 1 ) ≥ v 1 (M A 3
\{j}) for some j ∈ M A 3 ; but, from our utility structure, v 1 (M A 3 \{j}) = σ/2 for all j ∈ M A 3 and so the inequality

v 1 (M A 1 ) ≥ σ/2 holds. Arguing similarly, v 2 (M A 2 ) ≥ σ/2. But since v 1 (M A 1 ) + v 2 (M A 1 ) = σ, then sj ∈S1 s j = v 1 (M A 1 ) = sj ∈S2 s j = v 2 (M A 2 ) = σ/2.
Since v p (•) is a particular submodular function, Theorem 3 implies the following result that applies to the traditional indivisible item allocation setting where each agent receives a bundle.

Corollary 1 For submodular agent valuation functions over bundles, it is N Phard to compute the EF1 allocation that maximizes the sum of valuations.

One might conjecture that the maximum-USW TEF1 allocation is non-wasteful. But the following surprising result belies this intuition, and raises the question: Does a non-wasteful, TEF1 allocation always exist? Proposition 1 The TEF1 allocation that maximizes the utilitarian social welfare may waste items, even in a problem instance that admits a non-wasteful TEF1 allocation.

Proof. Consider a problem with items M = {1, 2, 3, 4, 5}, agents N = {1, 2, 3, 4, 5} divided into 2 types N 1 = {1, 2} and N 2 = {3, 4, 5}, and utilities u(i, 1) = u(i, 2) = 2, u(i, 3) = u(i, 4) = 4, u(i, 5) = 1 for every i ∈ N 1 ; u(i, 1) = u(i, 2) = 0, u(i, 3) = u(i, 4) = 8, u(i, 5) = 1 for every i ∈ N 2 . Any allocation with bundles M 1 = {1, 2} and M 2 = {3, 4}, and no other allocation, maximizes USW under TEF1 constraints with USW = 20. But, such an allocation is wasteful since item 5 is withheld although ∆ 2 (M 2 ; 5) = 1. However, any allocation with bundles M 1 = {1, 3} and M 2 = {2, 4, 5} is non-wasteful and TEF1 but has USW = 17.

TEF1 allocation with waste reduction

In our quest for a TEF1 allocation with no (or, at least, low) waste, we note that it is possible to obtain a type-complete TEF1 allocation in polynomial time by a natural extension (called L hereafter) of the algorithm due to Lipton et al. [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF]: Iterate over the items j ∈ M , giving item j to a type, say p, that is currently not envied by any other type for its current bundle M p ; compute an optimal matching with the augmented bundle M p ∪{j}; construct the envy graph where there is a directed edge from a type q to a type r whenever q envies r and eliminate any cycle in this graph by transferring the bundle of every type on this cycle to its predecessor on this cycle (to ensure that there is an unenvied type in each iteration), followed by re-matching within each such type. Although no item is withheld, it is possible for the final allocation to be wasteful: an item may be allocated to a type which has zero marginal utility for it or may become unassigned after a bundle is transferred between types.

One heuristic that could reduce waste is to allocate the item to the unenvied type that has the maximum marginal utility for it, breaking further ties uniformly at random, rather than to an arbitrary unenvied type -we call L, augmented with this heuristic, H. Unfortunately, Example 1 shows that, H can be wasteful in general. Consider the order 1, 2, • • • , 6 over items: 1 and 2 are obviously allocated to N 1 while, depending on how ties are broken, 3, 4, 5 can all be given to N 2 . With this allocation of item 5, envy appears for the first time and N 1 is the only unenvied type. Hence, 6 must go to N 1 although ∆ 1 ({1, 2}; 6) = 0 and is wasted. Notice further that if 6 were allocated to N 2 , it would increase N 2 's own type-value but make N 1 envy N 2 up to 2 items although N 1 does not want 6 in conjunction with its current bundle! This is especially disappointing since Example 1 admits three non-wasteful TEF1 allocations, which are also typewise Pareto optimal and maximize USW, with bundles M * 1 = {1, 2, 3}, {1, 2, 5}, or {1, 2, 3, 5}, and M * 2 = M \M * 1 (each resulting in a unique optimal matching for each type).

Nevertheless, To see how the marginal utility maximization heuristic performs in practice, we experimentally compared procedures L and H using the percentage of items wasted as our performance metric. We simulated two sets of problem instances with n = 100 agents partitioned into k = 3 types: Unequal:

|N 1 | = 74, |N 2 | = 13, |N 3 | = 13 5 ; Equal: |N p | ≈ n/k for all types p ∈ [k].
For each, we used m ∈ {50, 100} items; for each agent, we sampled m numbers uniformly at random from [0, 1] and normalized them to generate utilities for all m items. We report results averaged over 100 runs each.

We find that L wastes 39% (resp. 13%) of the items on average with m = 100 (resp. m = 50) for Unequal, and, for Equal, 0.005% of the items with m = 100 and no item with m = 50; H gives non-wasteful solutions for all instances. Thus, we can conclude that the performance of L the natural extension of [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF] strongly depends on parameters such as type proportions and the number of items, whereas augmenting it with the heuristic under consideration gives surprisingly good results over a variety of input instances.

Binary utilities: non-wasteful TEF1 allocation

In this section, we fill focus on the binary utility model : u(i, j) ∈ {0, 1}, ∀i ∈ N , ∀j ∈ M . This captures scenarios where each agent either approves or disapproves of an item but does not distinguish among its approved items. There exists prior work on fair allocation algorithms producing allocations with binary item utilities [START_REF] Barman | Greedy algorithms for maximizing Nash social welfare[END_REF] but most assume additive bundle valuations. Theorem 4. For any problem instance with a binary utility model, there exists a non-wasteful TEF1 allocation that can be computed in polynomial time.

Our proof is constructive: We provide and analyze an allocation algorithm for the problem (Algorithm 1). Like Lipton et al. [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF], we iterate over the items

Algorithm 1: PMURR({N p } p∈[k] , M, (u(i, j)) i∈N,j∈M ) Withheld set M0 ← M ; Temporary set MT ← ∅; Allocated bundles Mp ← ∅ ∀p ∈ [k]. repeat for j ∈ M0 do if ∆p(Mp; j) = 0 ∀p ∈ [k] then M0 ← M0\{j}; MT ← MT ∪ {j}. else Find a type p such that ∆p(Mp; j) > 0. M0 ← M0\{j}; Mp ← Mp ∪ {j}.
if some type envies p up to more than 1 item then /*Revocation and reallocation*/ repeat Find types q, r such that r envies q up to more than 1 item. Find item j ∈ Mq such that ∆r(Mr; j ) = 1. Mq ← Mq\{j }; Mr ← Mr ∪ {j }. until no type envies another up to more than

1 item. end M0 ← MT ; MT ← ∅. until M0 = ∅ or ∆p(Mp; j) = 0 ∀j ∈ M0, ∀p ∈ [k].
but decide to augment a type's bundle with an item not based on (the absence of) envy towards it but on the marginal utility of the type for the item. Let us call any algorithm that starts with empty bundles and follows the principle of augmenting the current bundle M p of a type p with an item j only if p has positive marginal utility (i.e. ∆ p (M p ; j) > 0) a PMU algorithm. Proof. The first part follows directly from the fact, for binary utilities, that any item can contribute either 1 or 0 to the type-value of any bundle, i.e. ∆ p (S; j) ∈ {0, 1} for any p ∈ [k], S ⊆ M , and j ∈ S. For the second part, note that each type starts with an empty bundle (hence zero type-value) and increases its typevalue by 1 every time it acquires an item under a PMU algorithm; moreover, since all positive utilities are equal, the only way for an item j to improve the type-value of p is to ensure that every item is assigned to an agent in every (N p , M p ∪ {j})-matching -hence, if an item is revoked, both the bundle-size and type-value diminish by 1. If after receiving a new item, a type is still envied by all others up to at most 1 item, no further action is necessary. But a PMU approach by itself cannot ensure that no type will start envying the recipient up to more than 1 item if the latter was already envied up to 1 item. If envy does exceed the acceptable limit, we execute a special revocation and reallocation (RR) subroutine repeatedly until we restore the TEF1 property -hence, we call our algorithm PMURR. The functioning of the RR subroutine depends on the following result: Proposition 3 At any stage of a PMU algorithm, if type p envies type q up to ν or more items, then |M q | ≥ |M p | + ν.

Proof. It follows from the definition of envy up to ν (or more) items: for any subset C ⊆ M q with |C| = ν -1, v p (M p ) < v p (M q \C). But, from Proposition 2 (and since C ⊆ M q ), we must have

v p (M q \C) ≤ |M q \C| = |M q | -|C| = |M q | - ν + 1. Combining this with the fact that v p (M p ) = |M p | (Proposition 2), we get |M p | < |M q | -ν + 1, i.e. |M p | ≤ |M q | -ν.
Corollary 3 Type p can envy another type q only if q has an allocated bundle of a larger size than p which, in turn, implies that there can be no cycles in the envy graph among types for binary utilities under a PMU algorithm.

The following lemma proves that the existence of envy is sufficient for having an item that can be revoked and reallocated. Lemma 2. At any stage of a PMU algorithm, if type p envies type q, then there is an item j ∈ M q which has a positive marginal utility for p, i.e. ∆ p (M p ; j) = 1.

Proof. By Proposition 2 and Corollary 2, if N p is the subset of agents who are assigned items in the current (N p , M p )-matching, then we must have v p (M p ) = |M p | = |N p | < |N p | for p to envy q. Now, if N q p is the subset of agents who would be assigned items in a (N p , M q )-matching, we must have

|N q p | = v p (M q ) > v p (M p ) = |N p |, so that |N q p \N p | ≥ |N q p | -|N p | > 0. Since N q p \N p ⊆ N p \N p , each agent in N q
p \N p is assigned no item under the current matching but has a positive utility for a distinct item in M q .

Evidently, a revocation from q (resp. a reallocation to r) decrements (resp. increments) its type-value. But, it is not immediately obvious how it affects all envy relations (other types that already envied q or r up to 1 or more items, types that q might start envying up to 1 or more items, etc.) and whether we could trigger a never-ending chain reaction. Our final lemma dispels such doubts. Lemma 3. The revocation and reallocation subroutine produces a TEF1 allocation in a polynomial number of steps.

Proof. First note that computing a type-value for any bundle is polynomial-time and so is checking whether r envies q up to more than 1 item (i.e. v r (M r ) < v q (M q \{j}) for some j ∈ M q ). Now, for an iteration of the RR subroutine to occur, we must have a type r envying a type q up to 2 or more items, so that |M q | ≥ |M

Φ(M ) -Φ(M ) = |M q | 2 -|M q | 2 + |M r | 2 -|M r | 2 = 2(1 + |M r | -|M q |) ≤ 2(1 -2) = -2,
i.e. Φ strictly decreases with each RR iteration, and obviously lies between 0 and m 2 (since p∈[k] |M p | ≤ m). Hence, RR terminates after a polynomial number of iterations; by the stop criterion, the final allocation is TEF1.

We are now ready to prove the main result of this section.

Proof (Theorem 4).

Non-wastefulness: By construction, no bundle-augmentation and revocationand-reallocation allow an item in an allocated bundle to remain unassigned; by Corollary 3, no envy cycles are ever formed in the envy graph among types, hence bundles are never passed between types (unlike in the decycling procedure of [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF]) and so no item once assigned can become unassigned (or transferred to the temporary set). However, within the for loop, the revocation(s) might result in an agent becoming unassigned who has a positive utility for a currently withheld item that was put in the temporary set because it previously had zero marginal utility for each type (hence this item now becomes a wasted item). This necessitates the outer repeat loop whose stop criterion ensures that there are no wasted items in the withheld set at the end of the algorithm.

TEF1 property: Lemma 3 ensures that the allocation is TEF1 after every iteration of the for loop, hence upon termination of the algorithm.

Polynomial time-complexity: Computing v p (•) and ∆ p (•), verifying envy up to more than 1 item, and finding an item to revoke and reallocate are all polynomial-time; Lemma 3 ensures that each iteration of the for loop takes polynomial time. With each iteration of the outer repeat loop, the size of the withheld set, which starts at m, strictly decreases (if it does not, it must mean that each withheld item has zero marginal utility for every type -a stop criterion), hence we have a linear number of iterations.

Discussion and future work

We have introduced and investigated new fairness and efficiency concepts for the allocation of indivisible goods to agents of pre-defined types. Evidently, the most important open question is whether a non-wasteful TEF1 allocation exists for every problem instance with arbitrary (non-negative) agent-item utilities. Important properties (such as the equality of bundle size and type-value) do not carry over from binary to arbitrary utilities, hence extensions of our PMURR algorithm to general utility models remain elusive.

It will also be interesting to deduce a theoretical upper bound on the number of wasted items for heuristic approaches such as the one in Section 5.

We considered one type-value function (Definition 1) here, which already posed interesting challenges. A natural alternative, the average utilitarian typevalue vp (S) v p (S)/|N p | is equivalent to v p (S) for all intents and purposes in this paper. More complex functions such as OWA operators [START_REF] Yager | On Ordered Weighted Averaging aggregation operators in multicriteria decision making[END_REF] or those that address fairness within a type (e.g. [START_REF] Bouveret | A general elicitation-free protocol for allocating indivisible goods[END_REF]) merit further analysis.

Other possible directions for future research include non-envy-based fairness concepts (egalitarian type-welfare, proportionality, maximin share etc.) as well as strategic implications of typewise fair allocation algorithms.

Fig. 1 :

 1 Fig.1: Our running example: 2 types N1 = {a1, . . . , a4} and N2 = {b1, . . . , b4}; items M =[START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF]; u(i, j) is 1 if there is an edge between agent i and item j, and 0 otherwise.

Theorem 1 .

 1 The utilitarian type-value function v p (S) is a non-additive, monotone submodular function of S ∈ 2 M .

Proposition 2

 2 Under the binary utility model, we have v p (S) ≤ min{|N p |, |S|}, ∀p ∈ [k], ∀S ⊆ M . In particular, any type's value for its allocated bundle at any stage of a PMU algorithm is equal to the cardinality of the bundle, i.e. v p (M p ) = |M p |, ∀p ∈ [k].

Corollary 2 A

 2 type p ∈ [k] with |M p | = |N p | under a PMU algorithm cannot envy any bundle S ⊆ M since v p (S) ≤ |N p |.

  r | + 2 by Proposition 3. For any collection of bundles M = {M 1 , . . . M 2 }, define the potential function Φ(M ) p∈[k] |M p | 2 , and let M = {M 1 , . . . M 2 } be the collection of bundles after revocation from q and reallocation to r. Hence we have |M q | = |M q | -1 and |M r | = |M r | + 1 (by Proposition 2) but |M p | = |M p | for every other type p. Thus, upon simplification,

Type-completness does not preclude an item j ∈ M A p remaining unassigned in the (Np, M A p )-matching.

These numbers roughly follow the proportions of Chinese, Malay, and Indian/Other residents of Singapore according to the 2010 census report[START_REF]Census: Key Indicators of the Resident Population[END_REF].