Combining Fairness and Optimality when Selecting and Allocating Projects

1 Introduction

When allocating indivisible resources to a group of agents, optimality and fairness are key considerations in order to satisfy the agents with their assigned resources [Bouveret et al., 2016]. However, when not all resources are to be assigned, the choice of the assigned resources may be particularly important. Many real-world situations can illustrate this issue.

A first context concerns a University course where students must be assigned to projects they have to work on, and present to their peers at the end of the course. Usually, an allocation that takes into account the preferences of the students is desirable in order to motivate them to work. An optimal allocation of projects to the students should maximize the global satisfaction of the students. This allocation must also be fair otherwise students could complain about the assignment. However, the choice of selected projects can also be fundamental for pedagogical reasons: not all students should present similar projects since it is expected that even attendants will learn from the presentations. Therefore, some diversity constraints according to the topics of the projects must be considered.

Another example concerns the organization of a conference with invited speakers. Suppose each of the speakers must be assigned a one hour time slot from Monday to Wednesday (9:00-19:00). In such a context, speakers can express preferences over time slots (e.g. preferably in the morning or early in the conference). The decisions to make involve selecting time slots for presentations, and the allocation of a time slot for each speaker. Solving such selection/allocation should account for the preferences of speakers both for the conference timetable, and for the time of their presentation.

The two preceding examples involve agents and many resources (more than the number of agents), referred to as projects, to be assigned to agents by a central authority. The assignment must be optimal and fair for the agents, and at the same time the set of assigned projects should be selected regarding balance constraints with respect to groups of projects (topics, days) or preferences of the agents. Hence it can be seen as a combination of multiwinner voting [Elkind et al., 2017; Faliszewski et al., 2017] (we want a good selection of projects) and resource allocation problems (we want a fair and optimal assignment of projects to agents).

In this paper, we focus on house allocation problems [Hylland and Zeckhauser, 1979; Abdulkadiroˇglu and S¨onmez, 1998], where each agent must be assigned exactly one project. Optimality questions have been widely investigated, especially with respect to Pareto-optimality [Abraham et al., 2004] and its refinements, such as rank-maximality [Irving, 2003; Irving et al., 2006] and popularity [Abraham et al., 2007; Cseh, 2017]. Concerning fairness, the most classical criterion, envy-freeness [Foley, 1967; Varian, 1974], requires that no agent prefers the project assigned to another agent to her own assigned project. This criterion is too demanding if the number of projects equals the number of agents. Hence, some relaxations of envy-freeness have been proposed [Beynier et al., 2019]. However, envy-freeness is more interesting when there are more projects than agents [Gan et al., 2019].

We focus in this article on a relaxation of envy-freeness, called rank-envy-freeness, which requires that no agent prefers the project assigned to another agent whereas she ranked this project in a better position in her preference ranking. This notion is present in the favoring higher ranks concept introduced by Ramezanian and Feizi [2020], was implicitly used by Kojima and ¨Unver [2014], and is equivalent to no envy by rank in random assignment [Harless, 2018]. We propose a generalization of rank-envy-freeness and introduce another concept, frustration-freeness, which relates both allocation and selection issues. Frustration-freeness imposes that no agent prefers an unassigned project to her assigned project. Focusing on the personal satisfaction of an agent, it can be viewed as a fairness concept, but also as an optimality concept because it asks for no project waste. Whereas optimality and fairness are often incompatible [Bouveret and Lang, 2008], we show that rank-envy-freeness and frustration-freeness are necessary to characterize rank-maximality and popularity.

For choosing an adequate set of selected projects at the same time as a good allocation of projects to agents, we investigate two ways: considering hard diversity constraints represented by lower and upper quotas over categories, or considering the preferences of the agents over the selected projects.

Diversity constraints are relevant in multiwinner voting when a committee with particular attributes is sought [Brams, 1990; Bredereck et al., 2018]. In resource allocation, it has been investigated, e.g., in public housing allocation [Benabbou et al., 2018], and in course allocation [Cechl´arov´a and Fleiner, 2017] where courses have capacities and open only if a lower quota of participants is reached.

When preferences of the agents are taken into account for selecting the projects to assign, a naive strategy is to first select the projects via a multiwinner voting rule and then allocate the projects. Nevertheless, this approach may lead to select projects that do not fit any agent personally, like in the conference example. Conversely, by only considering allocation purposes, one could impose conference days where only a few attendants can be present. Our model can be seen as a particular case of house allocation with externalities where agents care about their assignment and the set of selected projects (but not about the identity of the owners). In the notion of envy-freeness conditioned to the approval of the majority of agents [Shams et al., 2020], agents can also give their opinion about the assignment of other agents, but there is no concern of the set of selected projects. The goal of our article is to find a reasonable way to combine both allocation and selection goals, by focusing on fairness and optimality issues.

2 Allocation of Projects

We consider a set of agents N = [n] := {1, . . . , n} and a set of projects P = {p1, . . . , pm} with m ≥ n. Each agent i has ordinal preferences over projects, represented by a linear order ≻i over P. A feasible allocation σ : N → P is a matching, perfect w.r.t. the agents, where every agent is assigned to exactly one project and no two agents share the same project, i.e., σ(i) ̸= σ(j) for every agents i ̸= j and σ(i) ∈ P denotes the project assigned to agent i in allocation σ. Typically, some projects may not be assigned. Let Pσ denote the set of assigned projects in allocation σ, i.e., Pσ := {p ∈ P : ∃i ∈ N such that σ(i) = p}. An instance of the selection-allocation (SA) problem is I = (N, P, (≻i)i∈N). 1

2.1 Finding an Optimal and Fair Allocation

An allocation σ is Pareto-optimal (PO) if there is no feasible allocation σ′ such that σ′ (i) ⪰i σ(i) for every agent i and there exists an agent j such that σ′ (j) ≻j σ(j). In an ordinal setting, PO can be refined with rank-maximality (RM). The signature ρσ of allocation σ is the m-vector giving the number of agents ρσ(k) assigned to their kth most preferred project in σ, for all k ∈ [m]. Signature ρσ is lexicographically strictly greater than signature ρσ′ , denoted by ρσ >lex ρσ′ , if there exists an index i ∈ [m] such that ρσ(i′ ) = ρσ′(i′ ) for all i′ < i and ρσ(i) > ρσ′(i). An RM allocation can be computed in polynomial time [Irving et al., 2006].

1 The problem is similar to house allocation but we use a different name to emphasize the combined goal of selection and allocation.

Definition 1 (Rank-maximality (RM)). An allocation σ is RM if there is no feasible allocation σ′ such that ρσ′ >lex ρσ.

Popularity is another optimality measure that refines PO. Agent i prefers allocation σ to allocation σ′ if σ(i) ≻i σ′ (i). An allocation σ is then more popular than another allocation σ′ if the number of agents who prefer σ to σ′ is strictly greater than the number of agents who prefer σ′ to σ.

Definition 2 (Popularity (Pop)). An allocation σ is popular if there is no feasible allocation σ′ more popular than σ.

A Pop allocation may not exist but existence can be efficiently checked and, in the positive case, a Pop allocation can be computed in polynomial time, thanks to the following characterization due to Abraham et al. [2007]: An allocation σ is Pop iff (1) every first-ranked project is assigned in σ, and (2) σ assigns to every agent either her first-ranked project or the most preferred project that is not ranked first by an agent.

Fairness issues can also be considered. We relax envyfreeness with rank-envy-freeness, where an agent i is envious towards an agent j only if agent i ranks the envied project in a better position in her preference ranking than agent j. Let ri : P → [m] be the function giving the rank of a project in ≻i, i.e., ri(x) = |{y ∈ P : y ⪰i x}|, for project x ∈ P.

Definition 3 (Rank-envy-freeness (r-EF)). Allocation σ is rEF if σ(i) ≻i σ(j) or rj(σ(j)) ≤ ri(σ(j)) for every i, j ∈ N.

A rank-maximal or popular allocation is also r-EF.

Proposition 1. RM⇒ r-EF and Pop⇒ r-EF.

Proof. Suppose that an RM allocation σ is not r-EF. There exist agents i and j such that σ(j) ≻i σ(i) and ri(σ(j)) < rj(σ(j)). Hence, both ri(σ(j)) < rj(σ(j)) and ri(σ(j)) < ri(σ(i)) hold. Thus, by swapping the projects of i and j, we get an allocation σ′ such that ρσ′ >lex ρσ, a contradiction.

Suppose that a Pop allocation σ is not r-EF. There exist agents i and j such that σ(j) ≻i σ(i) and ri(σ(j)) < rj(σ(j)). By rank-envy, neither agent i nor agent j is assigned her first-ranked project in σ so, by Abraham et al. [2007]'s characterization, they are both assigned her most preferred project that is not ranked first by an agent. Since i prefers σ(j) to σ(i), project σ(j) must be ranked first by some agent, contradicting the fact that agent j is assigned her most preferred project that is not ranked first by any agent.

The reverse of both implications is not true, since r-EF does not even imply PO. Moreover, although both RM and Pop imply r-EF, it is not true for their weaker requirement PO.

Example 1. For r-EF ̸⇒ PO, simply consider an instance with two agents and three projects with the following preferences: p1 ≻1 p2 ≻1 p3 and p1 ≻2 p3 ≻2 p2. Allocation assigning p2 to agent 1 and p3 to agent 2 is r-EF but not PO.

For PO ̸⇒ r-EF, consider an instance with three agents and three projects. The preferences are given below.

The encircled allocation is PO but not r-EF: agent 1 is envious towards agent 2 who owns her second ranked project p1 which is the first-ranked project of agent 1.

For rank 0 ≤ k < m, we define a generalization of r-EF.

Definition 4 (Rankk-envy-freeness (rk-EF)). An allocation σ is rankk-envy-free if for every agents i and j, σ(i) ≻i σ(j) or rj (σ(j)) ≤ min{ri(σ(j)), k} holds.

Note that rk-EF ⇒ rk′ -EF for every k′ > k. Moreover, rm-1-EF ⇔ r-EF and r0-EF ⇔ envy-freeness (EF). By the fact that RM ⇒ r-EF, an rm-1-EF allocation always exists. However, starting from k = m- 2, an rk-EF allocation may not exist, as shown in the basic example with three agents and three projects where every agent has the same preferences.

2.2 Towards a Good Selection

We introduce a simple requirement imposing that no agent prefers a project that has not even been assigned.

Definition 5 (Frustration-freeness (FF)). An allocation σ is FF if σ(i) ≻i p for every agent i and every project p ∈ P \Pσ.

When m = n, all projects are selected so every allocation is FF. Frustration is defined according to selected projects, so it does not say anything about global optimality. In particular, it is clear that an FF allocation may not be PO. However, conversely, in every SA instance, a PO allocation (and thus an RM or a Pop allocation) is FF: otherwise by assigning the preferred unassigned project to the agent who prefers it over her current assigned project, we get an allocation that Paretodominates it. Therefore, an FF allocation always exists.

The issues forbidding r-EF or FF to imply Paretooptimality can be fixed by combining the two properties.

Proof. Consider an allocation σ that is r-EF and FF. Take an allocation σ′ that Pareto-dominates σ. For every agent i, either σ′ (i) = σ(i), or σ′ (i) ≻i σ(i). So, by FF, we have Pσ = Pσ′ . Consider an ameliorating cycle (i0, i1, . . . , ic-1) ⊆ N from σ to σ′ , i.e., σ′ (ij-1) = σ(ij mod c) for every j ∈ [c]. Since σ′ (ij-1) = σ(ij mod c) ≻ij-1 σ(ij-1), by r-EF we must have rij mod c (σ(ij mod c)) ≤ rij-1 (σ(ij mod c)) < rij-1 (σ(ij-1)), for every j ∈ [c], a contradiction.

Combining FF with r1-EF provides an alternative characterization of Pop. An agent i is r1-envious towards an agent j only if the envied project is not ranked first by agent j.

Theorem 1. For every SA instance, Pop ⇔ r1-EF + FF.

3 Hard Constraints over the Selected Projects

In this section, we assume that the set of projects is partitioned into q groups, i.e., P = P1∪· · ·∪Pq, and that a feasible allocation must satisfy some quotas on the selected projects within groups. Let ℓj and uj denote the respective lower and upper quotas for group Pj for j ∈ [q]; trivially we assume that ℓj ≤ uj ≤ |Pj| for every j ∈ [q]. An allocation σ is feasible if ℓj ≤ |Pσ ∩ Pj| ≤ uj for every j ∈ [q]. We suppose that ∑j∈[q] ℓj ≤ n ≤ ∑j∈[q] uj , otherwise there is no feasible allocation. An instance of this constrained selection-allocation (CSA) problem is (N, P, (≻i)i∈N , (Pj )j∈[q], (ℓj , uj )j∈[q]).

An SA instance is a CSA instance where ℓj = 0 and uj = |Pj | for every j ∈ [q]. An instance is said with no trivial group upper quota if uj < |Pj| for every j ∈ [q]. Let ≻Pj i be the preference ranking of agent i within group Pj. Preferences are group-oriented if every agent i's preferences can be decomposed w.r.t. project groups, i.e., there is a permutation τi : [q] → [q] such that for every projects p ∈ Pj and p′ ∈ Pj ′ , p ≻i p′ iff p ≻Pj i p′ if j = j ′ or τi(j) < τi(j ′ ) otherwise.

Contrary to the SA setting, even an RM and Pop allocation may not be FF in a CSA instance, because of the constraints on project groups, even if an FF allocation exists.

Example 2. Let us consider a CSA instance with four agents and five projects where P1 = {p1, p3, p4}, P2 = {p2, p5}, and u1 = 2. The preferences are given below.

The framed allocation is RM with signature (3, 0, 0, 0, 1) and Pop. However, it is not FF since agent 1 is frustrated: she prefers the unassigned project p4. Nevertheless, the encircled allocation, with signature (1, 2, 1, 0, 0), is both PO and FF.

It follows that the characterization obtained in Theorem 1 does not hold in a CSA instance. By replacing FF by PO, we can nevertheless keep the validity of necessary conditions.

Proposition 3. In every CSA instance, Pop⇒ r1-EF + PO.

Proof. A Pop allocation σ is trivially PO. Suppose that σ is not r1-EF. There exist agents i and j such that σ(j) ≻i σ(i) and rj(σ(j)) > 1. Thus, j does not rank σ(j) first. If there exists a project p ∈ Pσ assigned to an agent k such that p ≻j σ(j) then, by assigning project σ(j) to i, project p to j and project σ(i) to k, we reach an allocation more popular than σ (i and j are better off and k may be worse off), a contradiction. Otherwise, there exists a project p ∈ P \ Pσ such that p ≻j σ(j). If p cannot be assigned, it means that it belongs to a group Pℓ whose upper quota uℓ is reached. By removing from Pσ an arbitrary project belonging to Pℓ \{σ(j)} that was assigned to an agent k, we can assign p to j, σ(j) to i and an arbitrary project respecting the constraints to k. This new allocation is more popular than σ (i and j are better off and k may be worse off), a contradiction. If there is no assigned project belonging to Pℓ different from σ(j), then uℓ = 1 and Pσ ∩ Pℓ = {σ(j)}. Hence, σ(i) /∈ Pℓ and reassigning project p to j instead of σ(j) is feasible and construct an allocation more popular than σ, a contradiction.

However, r1-EF + PO ̸⇒ Pop, as illustrated below.

Example 3. Let us consider a CSA instance with three agents and four projects where P1 = {p1, p4}, P2 = {p2, p3} and u1 = 1. The preferences are given below.

The encircled allocation is PO and r1-EF but not popular. The framed allocation is both rank-maximal and popular.

In Example 2, the intersection between the set of RM or Pop allocations and the set of FF allocations is empty. However, this does not hold for the weaker requirement PO. If an FF allocation exists, then an allocation that is both PO and FF exists: it suffices to start a top-trading cycle algorithm [Shapley and Scarf, 1974] from an FF allocation. In general, an FF allocation may not exist: consider an instance with two agents where their first-ranked projects are p1 and p2, respectively, which belong to the same group with upper quota one. Moreover, deciding the existence of FF allocations is hard.

Theorem 2. It is NP-complete to decide whether there exists an FF allocation in a CSA instance, even either under grouporiented preferences or with no trivial group upper quota.

In Theorem 2's reduction, preferences are group-oriented or there is no trivial group upper quota, but not both simultaneously. Indeed, under both restrictions, one can decide in polynomial time about the existence of an FF allocation.

Proposition 4. The existence of an FF allocation can be decided in polynomial time in every CSA instance with no trivial group upper quota under group-oriented preferences. If existence is guaranteed, one can then construct an FF and RM (or Pop if exists) allocation in polynomial time.

Sketch of proof. Let Nj denote the set of agents who prefer the most the projects in Pj. One can show that, under group-oriented preferences when uj < |Pj | for every j ∈ [q], there exists an FF allocation iff ℓj ≤ |Nj| ≤ uj for every j ∈ [q]. Under such conditions, each FF allocation or each PO allocation assigns to each agent in Nj a project in Pj. Thus, each PO allocation is FF and is the concatenation of PO allocations in all SA sub-instances (Nj, Pj, (≻i)i∈Nj )j∈[q]. Recall that in each SA sub-instance, an RM allocation or Pop allocation (if exists) can be found in polynomial time.

4 Selecting Socially Good Projects

In this section, we aim to assign projects to the agents such that the whole set of selected projects is "good" according to the preferences of the agents. We evaluate the quality of projects w.r.t. pairwise comparisons. Let N(p, p′ ) denote the set of agents preferring project p to project p′ . A project p is said to dominate another project p′ if |N(p, p′ )| > n/2. The set of projects that dominate project p is denoted by D(p). In a voting setting, when focusing on pairwise comparisons, it is highly desirable to select a Condorcet winner alternative which dominates all the others, and to not select a Condorcet loser alternative which is dominated by all the others. We adapt these requirements to the context of allocation.

Definition 6 (Condorcet {winner / loser} criterion ({CWC / CLC})). Allocation σ satisfies CWC if, when there exists a Condorcet winner project p then project p is assigned in σ. Allocation σ satisfies CLC if, when m > n and there exists a Condorcet loser project p then project p is not assigned in σ.

There is already a conflict between selection and allocation desiderata since the two Condorcet axioms for selection can be incompatible with FF (and thus PO, RM and Pop).

Proposition 5. CWC or CLC is incompatible with FF.

Proof. Let us consider an instance with n > 2 agents where the preferences are given below.

. . .

FF imposes to select all n first-ranked projects, and thus Condorcet loser pCL but not Condorcet winner pCW.

Preferences ≻ over single projects can be extended to sets of projects by using a preference extension ≻ext . A preference extension ≻ext satisfies responsiveness [Roth, 1985; Barber`a et al., 2004] if ∀x ∈ X ⊂ P and ∀y ∈ P \ X, (X\{x})∪{y} ≻ext X holds iff y ≻ x holds. The responsive set extension ≻RS is the minimal partial order that satisfies responsiveness. We also consider extension ≻RS- , a weaker version of ≻RS where transitivity is dropped. Although the latter notion may appear unnatural for modelling preferences, in the context of an SA instance, it means that if two sets of selected projects are too different then only the quality of the allocation matters. When referring to a given preference extension ≻ext , we assume that each agent i uses ≻ext i .

We derive a variant of popularity for taking into account the preferences of the agents over selected projects. Let n1(σ′ , σ) denote the number of agents who get a better assignment in σ′ than in σ, and n≻ext 2 (σ′ , σ) the number of agents who get the same assignment but prefer set Pσ′ to Pσ w.r.t. ≻ext . Let nPop ≻ext(σ′ , σ) denote the number of agents who prefer allocation σ′ to σ in the sense that they prefer to get a better assigned project and if they keep the same project, they consider the selected projects, i.e., nPop ≻ext (σ′ , σ) = n1(σ′ , σ) + n≻ext 2 (σ′ , σ). Allocation σ is more popular w.r.t. ≻ext than allocation σ′ if nPop ≻ext(σ′ , σ) > nPop ≻ext(σ, σ′ ). This notion generalizes standard popularity to an SA instance with externalities where agents care about the other assigned projects.

Definition 7 (Popularity w.r.t. ≻ext (Pop≻ext )). An allocation σ is Pop≻ext if there is no other feasible allocation σ′ that is more popular w.r.t. preference extension ≻ext .

A Pop≻ext allocation may not be Pop and vice versa, as shown in Example 4. However, when n = m the two notions coincide, showing that a Pop≻ext allocation may not exist.

An allocation σ satisfies dominion selection (DS) if ⋃p∈Pσ D(p) ⊆ Pσ. We show that, for any responsive ≻ext , Pop≻ext satisfies both dominion selection and r1-EF restricted to the set of selected projects, called rPσ 1 -EF, where there is no pair of agents i and j such that i prefers the project allocated to j but this project is not ranked first by j within Pσ.

Proof. Consider a Pop≻ext allocation σ. Suppose that σ does not satisfy DS. Then, there exists a project p ∈ Pσ dominated by p′ ∈ P \ Pσ. Consider the allocation σ′ constructed from σ where agent i who was assigned p in σ is assigned p′ . By definition of dominance, at least ⌈ n+1 2 ⌉ agents prefer σ′ to σ, a contradiction. Suppose now that σ is not rPσ 1 -EF. There exist agents i and j and project p ∈ Pσ such that σ(j) ≻i σ(i)

and p ≻j σ(j). Consider the allocation σ′ constructed from σ where agent i is assigned σ(j), agent j is assigned p and agent k who was possessing p is assigned σ(i). Since Pσ = Pσ′ , we only need to consider the satisfaction of agents i, j and k, and two of them (i and j) are better off in σ′ , a contradiction.

From the satisfaction of DS, when m > n, a Pop≻ext allocation cannot select a Condorcet loser p, for a responsive ≻ext , since p is dominated by at least n other projects. Moreover, a project that dominates at least m- n other projects must be selected since at least one of its dominated projects is selected. Hence, the Condorcet winner is selected.

Contrary to standard popularity, as expected from Proposition 5, if ≻ext is responsive, then Pop≻ext fails FF. However, from Proposition 6, it satisfies a mild relaxation of FF, imposing to an allocation σ that if there exists a project p ∈ P \ Pσ and an agent i such that p ≻i σ(i), then p cannot dominate any project in Pσ. Nevertheless, even Pop≻RS may fail r-EF.

The underlined and encircled allocations are Pop≻RS but the latter is not r-EF. The only Pop allocation is framed.

In case of r-EF failure, r-EF swaps can be performed: agents i and j can swap their projects if i is rank-envious towards j. We show that r-EF swaps preserve Pop≻ext .

Proposition 7. For every ≻ext , if a Pop≻ext allocation σ exists, then an allocation that is both Pop≻ext and r-EF can be reached in polynomial time via r-EF swaps starting from σ.

Proof. Consider a Pop≻ext allocation σ that is not r-EF. There exist two agents i and j such that i is rank-envious towards j. Let σ′ denote the allocation resulting from an r-EF swap between i and j in σ. We have Pσ = Pσ′ , so n≻ext 2 (σ′ , σ) = n≻ext 2 (σ, σ′ ) = 0. By rank-envy, σ′ (i) ≻i σ(i). Thus, σ(j) ≻j σ(i), otherwise i and j would be rPσ 1 -envious in σ. Hence, σ′ is as popular w.r.t. ≻ext as σ. By rPσ 1 -EF and DS, if an allocation is more popular w.r.t. ≻ext than σ′ , then it is also true for σ, a contradiction. Hence, σ′ is also Pop≻ext .

A Pop≻ext allocation σ is Pop when P = Pσ and the number of Pop allocations is polynomial [McDermid and Irving, 2011]. Since r-EF swaps transform a Pop≻ext allocation σ to another Pop≻ext allocation σ′ where Pσ′ = Pσ but with a strictly greater signature w.r.t. >lex, the dynamics of r-EF swaps starting from σ converges in polynomial time.

However, although Pop≻RS is attractive and despite the fact that a popular allocation can be computed in polynomial time, even the verification of a Pop≻RS allocation is hard.

Theorem 3. Checking popularity w.r.t. ≻RS is co-NP-hard.

The complexity proof mostly relies on set comparisons induced by ≻RS . However, an allocation is not Pop≻RS if there exists an unselected project p that is preferred to a selected project p′ by a "blocking" subset of agents and the remaining subset of agents can be reassigned such that there are more, or as many, better off agents than worse off agents. Hence, we conjecture that checking Pop≻RS- is also hard.

To circumvent the problem of a blocking subset of agents, we derive another variant of popularity that takes into account the preferences of all agents over selected projects. For preference extension ≻ext , we denote by n≻ext 3 (σ′ , σ) the number of agents who prefer Pσ′ to Pσ, and define n2Pop ≻ext (σ′ , σ) := n1(σ′ , σ) + n≻ext 3 (σ′ , σ). Allocation σ′ is more 2popular w.r.t. ≻ext than allocation σ if n2Pop ≻ext (σ′ , σ) > n2Pop ≻ext (σ, σ′ ).

Definition 8 (2Pop≻ext). Allocation σ is (strictly) 2popular w.r.t. ≻ext if there is no other allocation that is more 2popular (at least as 2popular) w.r.t. ≻ext .

2Pop≻ext allocations always select a Condorcet winner and strictly 2Pop≻ext allocations never select a Condorcet loser.

Proposition 8. If ≻ext is responsive, 2Pop≻ext ⇒CWC and strict 2Pop≻ext ⇒CLC.

Moreover, by the same proof idea as Proposition 7, for every ≻ext , if a 2Pop≻ext exists then r-EF swaps can reach in polynomial time an allocation that is both 2Pop≻ext and r-EF.

By slightly adapting the proof of Theorem 3, even the verification of 2Pop≻RS is co-NP-hard. We consequently focus on the weaker version of ≻RS where transitivity is dropped. Note that 2Pop≻RS- can be characterized based on rPσ 1 -EF, a refinement of FF and dominance conditions w.r.t. unassigned projects. These conditions can be verified in polynomial time.

Theorem 4. 2Pop≻RS- can be verified in polynomial time.

The question of computation for 2Pop≻RS- remains open.

5 Empirical Evaluation of Allocations

In this section, we empirically evaluate the quality of different procedures for assigning projects to agents, both according to selection and allocation considerations. We generate 100 SA instances with n = 5 agents and m = 15 projects. Correlated preferences are studied via the single-peaked preference domain. A preference ranking ≻i is single-peaked if there exists a linear order > over P such that for all projects x, y, z with x > y > z or z > y > x, x ≻i y implies y ≻i z. We consider three types of preference generation: impartial culture (IC) where each preference ranking is uniformly drawn from the set of all possible preference rankings, single-peaked uniform peak (SP-UP) where each single-peaked preference ranking is generated by first uniformly selecting the peak project then uniformly choosing the next ranked project either on the left of the peak in axis > or on the right and so on [Conitzer, 2009], and single-peaked uniform (SP-U) where each preference ranking is uniformly drawn from the set of all possible single-peaked rankings [Walsh, 2015]. Under SP-U and SP-UP, preferences are correlated w.r.t. a common axis > along projects. Under SP-UP, a preference ranking with, as a first-ranked project, an extreme point of the axis has the same probability to occur as one with a middle point of the axis. Hence, the generated preferences are more diverse under SPUP than under SP-U, where the occurrence of a project at a certain preference rank depends on a binomial coefficient.

For evaluating the quality of the set of selected projects (selection goal), we compute the satisfaction of an agent by considering the average rank in her preference ranking over all selected projects. The global rank satisfaction is then computed by averaging all individual average rank satisfactions. For evaluating the quality of the allocation (allocation goal), we consider the average over all agents of the rank given to their allocated project. Our results are given in Figure 1.

All possible allocations are generated and the measures are given in average for different types of allocations:

• Optimal allocations: Pop allocations or RM allocations;
• Selection-based optimal (Sel-opt) allocations: a multiwinner voting rule (MWR) is used for selecting n projects, and then a Pop or an RM allocation is computed on an SA instance where projects are restricted to this set. We use the following excellence-based MWRs: Bloc, k-Borda, k-Maximin, and kCopeland (see Faliszewski et al. [2017] for definitions).
• Selection & allocation (SA)-based allocations: 2Pop≻RSallocations (2PopRS), 2Pop≻RS- allocations that are r-EF, and allocations (r-EF+FF dyn.) which are the result of the dynamics of r-EF swaps and FF-agreement moves (an agent i can get a more preferred unassigned project p if the majority of agents prefers p to i's project) from a random allocation.

As expected, optimal allocations behave significantly better under an allocation goal than Sel-opt allocations and reversely under a selection goal. Our variant of Pop, 2Pop≻RS- , is not satisfactory under IC where the average rank satisfactions are always superior than those of Pop or RM. However, it performs a bit better with a selection goal when preferences are correlated. Indeed, under single-peaked distributions, the satisfaction of Condorcet criteria should help to choose a better set of selected projects. Surprisingly, the stable allocation arising from the dynamics associated with r-EF swaps and FF-agreement moves appears to be very good for combining both goals of selection and allocation. It has an intermediate behavior with an average rank satisfaction closer to those of Sel-opt allocations than optimal allocations with a selection goal, and closer to optimal allocations than Sel-opt allocations with an allocation goal. In average, ten steps are sufficient to reach a stable allocation so we are far from the exponential theoretical bound for r-EF swaps.

So far, we have evaluated the quality of an allocation (allocation goal) via the optimality measure of average rank satisfaction. For fairness, we compute the average minimum k such that an allocation is rk-EF. Our experiments show that optimal allocations and SA-based allocations are very fair. However, Sel-opt allocations are very unfair in comparison, showing the need of combining allocation and selection goals. In general, a slight tendency confirms the intuition under which correlated preferences favor consensus in selection whereas diverse preferences favor consensus in allocation.

6 Conclusion

We investigated a variant of resource allocation where both selection and allocation are important. We focused on popularity (Pop) and rank-maximality (RM) optimality concepts and showed that they are compatible with two notions of fairness that we have introduced or refined, namely frustrationfreeness (FF) and rank-envy-freeness (r-EF). In an ordinal context, r-EF appears as a very natural and flexible fairness requirement that could easily be used as an argument for explaining a decision. The selection goal has been combined with the allocation goal in two ways: via hard constraints represented by quotas on project groups or via the preferences of the agents themselves. Under hard constraints, RM and Pop lose their link with FF and this latter basic requirement even becomes difficult to satisfy. However, we identified natural restrictions under which the compatibility remains. When the selection goal is conditioned by the preferences of the agents, we derive variants of Pop that can be connected with r-EF and that are Condorcet-consistent. However the most natural extension of Pop in such a context suffers from a computational burden. In practice, variants of Pop slightly improve Pop towards the selection goal. Nevertheless, the most interesting notion empirically is the outcome of the dynamics associated with r-EF swaps and FF-agreement moves which turns out to satisfy the goal of combining both selection and allocation.

Many interesting directions can be explored. Technically, some algorithmic questions remain open for our variants of Pop. Moreover, we have focused on pairwise comparisonsbased refinements of Pop but one could think about other types of refinements. To further understand how selection and allocation can be combined, an extensive study deserves to be initiated on the dynamics associated with r-EF swaps and FF moves. Concerning optimality, one could also consider minimizing the rank of the least happy agent and examine it under the lens of r-EF. Intuitively, r-EF seems to be very sensitive to strategic manipulation. This point deserves to be formally investigated. Finally, the extension to more than one project per agent or more than one agent per project is natural.

Acknowledgements

This work has been partially supported by the CNRS, via the project INS2I - 2021 - DeSIRe.