Service Exchange Problem

1 Introduction

Finding a matching between indivisible items and agents has been widely studied in economics, and recently attracts considerable attention in AI/CS areas. When agents are initially equipped with some items, it is called as exchange problem. Housing market [Shapley and Scarf, 1974] is a special case where each agent is equipped with an item and has a linear priority over items. Various features of exchange problem have been studied, such as the strict core [Ma, 1994], externalities and indifferences [Mumcu and Saglam, 2007; Aziz and de Keijzer, 2012], and multiple endowments [Todo et al., 2014; Sonoda et al., 2014; Sikdar et al., 2017].

In this paper we study an extension of housing market, called service exchange problem, where an agent's preference depends both on the item/service she receives and the person receiving her service. For example, consider a person who wants to study Dutch and can teach French. Assume she has two colleagues who can teach Dutch and want to study French. Whichever colleague she would choose as her Dutch teacher, she should also become her French teacher in return. Her preference then depends also on her student; she would prefer the one who is best for studying French, to minimize her cost. This model can reflect various practical situations, such as short-term house swap where customers prefer lending their houses to those they know well, and studentexchange between laboratories where a laboratory prefers to send its members to its privileged partners.

In our definition of the service exchange problem, the structure of externalities is very restricted; an agent is indifferent to exchanges not involving her. It is easy to see that the necessary condition by S¨onmez (1999) for preference domains to guarantee the existence of truthful, Pareto efficient (PE), and individually rational (IR) matching rule does not hold for the service exchange problem. Therefore, our main focus in this paper is to find PE and IR matchings.

PE and IR matchings obviously exist by definition, not only in the service exchange problem but also in a broad class of exchange problems, and can be trivially found by enumerating and comparing all possible matchings. Therefore, a more precise description of our main focus is to check whether there is a computationally-efficient algorithm that finds a PE and IR matching. Many works have studied such algorithms [Fujita et al., 2015; Aziz et al., 2016; Gourv`es et al., 2017]. To the best of our knowledge, however, no work has focused on the service exchange problem.

Besides Pareto efficiency, there are various criteria for evaluating the matchings, especially when agents preferences are represented by cardinal utilities. One natural objective is to maximize the sum of agents' utilities, which reflects the perspective of utilitarianism. Another well-studied objective is to maximize the utility of the agent who has the minimum utility, which reflects the perspective of egalitarianism and is expected to result in a fair matching. Although both are very familiar in the literature of resource allocation [Chevaleyre et al., 2006; Bouveret et al., 2016], there has been no such discussion for the service exchange problem.

Our contribution is summarized as follows. For finding a PE and IR matching, we provide a poly-time algorithm for a special class of preferences, called set-restricted, and we show that the problem is NP-hard for general preferences. For Sum and Min objectives under cardinal utilities, we showed that maximizing either of them is NP-hard. Note that we do not address agents' incentive for manipulation, including manipulation complexity, i.e., a well-known alternative when truthfulness is not achievable [Bartholdi et al., 1989; Teo et al., 2001; Pini et al., 2011; Fujita et al., 2015]. Nevertheless, we believe that our contribution is critical; finding a desirable matching is likely to be hard even in the simple model where endowments are restricted to singletons and only a special type of externalities is allowed.

2 Preliminaries

Let N = {1, . . . , n} denote the set of agents, and let S = {s1, . . . , sn} denote the set of services, where si is the service offered by agent i. For any N ⊆ N, let SN denote the set of services belonging to the agents of N. A matching M is a bijection fromN to S, such that M(i) is the service assigned to agent i in M. To simplify notations, we denote by M(sj) the agent receiving service sj inM. LetMdenote the set of possible matchings, and for any N ⊆ N, let MN denote the subset of Mwhere each agent of N receives the service of an agent of N i.e., if M ∈ MN then ∀i ∈ N, M(si) ∈ N. Note that MN =MN\N holds for any N ⊆ N.

The preference of an agent depends on both the service that she receives and the agent that receives her service. The ordinal preference of agent i is described through linear order ≻i on N × S, where (ℓ, sj) ≻i (ℓ′ , sj ′) stands for agent i prefers receiving service sj and serving agent ℓ rather than receiving service sj ′ and serving agent ℓ′ . In the following, we call (i, si) the initial endowment of agent i. Preference ≻i is set-restricted (SR) if there exist sets Ni ⊆ N and Si ⊆ S such that (ℓ, sj) ≻i (i, si) if and only if ℓ ∈ Ni and sj ∈ Si. In other words, Ni is the subset of agents that agent i accepts to serve, and Si is the subset of services that agent i accepts to receive in exchange of her own service. Preference ≻i of agent i over matchings extends naturally: M ≻i M ′ if and only if (M(si),M(i)) ≻i (M ′ (si),M ′ (i)). Notation a ≿i b stands for a ≻i b or a = b.

In case of cardinal preferences, utility function ui : N × S → R describes the preference of agent i as follows. For any pairs (ℓ, sj), (ℓ′ , sj ′) ∈ N × S, (ℓ, sj) ≻i (ℓ′ , sj ′) if and only if ui(ℓ, sj) > ui(ℓ′ , sj ′). Utility function ui is additively separable (AS) if exist functions vi : N → R and wi : S → R such that ui(j, sℓ) = vi(j) + wi(sℓ) holds for any (j, sℓ) ∈ N × S. We denote by u(M) := (u1(M), . . . , un(M)) the vector of utility values achieved by matching M, where ui(M) := ui(M(si),M(i)).

For any coalition N ⊆ N, matching M is Pareto dominated over N by matching M ′ if M ′ ≿i M holds for any i ∈ N, and exists j ∈ N such that M ′ ≻j M. Matching M ∗ is Pareto efficient (PE) if no matching Pareto dominates it over N. Matching M is individually rational (IR) if (M(si),M(i)) ≿i (i, si) holds for any i ∈ N. For cardinal preferences, social welfare function f : Rn → R can be used to compare vectors of utilities. Matching M ∗ is foptimal if it maximizes f(u(M)). We consider in this paper two different social welfare functions: Sum (i.e., f(u(M)) = ∑i∈N ui(M)) and Min (i.e., f(u(M)) = mini∈N ui(M)).

Example 1. For n = 3, assume that ordinal preferences are (3, s3) ≻1 (2, s2) ≻1 (2, s3) ≻1 (3, s2), (1, s3) ≻2 (1, s1) and (1, s1) ≻3 (2, s1), where only pairs strictly preferred to the initial endowment are represented. Note that preferences are SR with N1 = {2, 3}, S1 = {s2, s3},N2 = {1}, S2 = {s1, s3},N3 = {1, 2} and S3 = {s1}. Note also that no additively separable utility function can represent the preference of agent 1. Consider matching M1,M2, M3 such that M1(1) = s3, M1(2) = s2, M1(3) = s1, M2(1) = s2, M2(2) = s3, M2(3) = s1 and M3 is the initial endowment. All three are IR but only M1 and M2 are PE since M3 is Pareto dominated over N by M2.

3 PE and IR for Ordinal Preferences

In this section, we study the complexity of computing a PE and IR matching for ordinal preferences. We start our analysis in Section 3.1 by assuming that all preferences are SR, and we provide a polynomial algorithm to compute a PE and IR matching. In section 3.2, we show that computing a PE and IR matching is in the general case NP-hard.

3.1 SR Preferences

We assume in this subsection that all preferences are SR and we describe an algorithm to compute a PE and IR matching. An improving cycle is a sequence of agents 〈a1, . . . , ak〉 such that (ai-1, sai+1 ) ≻ai (ai, sai ) holds for any i ∈ {1, . . . , k}, where a0 and ak+1 stand for ak and a1, respectively. If N ⊆ N is a superset of {a1, . . . , ak} then 〈a1, . . . , ak〉 is an improving cycle restricted to N. Matching M results from improving cycle 〈a1, . . . , ak〉 if M(ai) = sai+1 holds for any i ∈ {1, . . . , k}, where sk+1 stands for s1. Note that each agent visited by an augmenting cycle receives a strictly better outcome than her initial endowment in any matching resulting from this augmenting cycle.

We focus on lexicographic improving cycles which are improving cycles such that no other improving cycle provides a better outcome to the first agent in the sequence, and given that outcome for the first agent there is no other improving cycle providing a better outcome to the second agent, and so on. More formally, improving cycle 〈a1, . . . , ak〉 is a lexicographic improving cycle restricted to N if {a1, . . . , ak} ⊆ N and there is no improving cycle 〈a1, a′2 , a′3 . . . , , a′r 〉 restricted to N such that either (a′r , sa′2 ) ≻a1 (ak, sa2 ), or a′r = ak and there exists ℓ ∈ {1, . . . , k} such that a′i = ai holds for any i < ℓ, and (aℓ-1, sa′ℓ+1 ) ≻aℓ (aℓ-1, saℓ+1 ). Note that the definition relies on the starting point of the lexicographic comparison (denoted a1 above). We assume in the following that the first agent in the sequence is this starting point. Note also that the lexicographic improving cycle starting from a given agent is unique since preferences are strict.

Algorithm 1 computes a PE and IR matching. It constructs step-by-step a matching by iteratively searching a lexicographic improving cycle starting from an arbitrary agent and by computing the matching resulting from this cycle.

Example 2. We use the problem described in Example 1 to illustrate Algorithm 1. Assume that the agent picked during the first iteration is agent 1. There are three improving cycles visiting agent 1: 〈1, 3〉, 〈1, 2〉 and 〈1, 2, 3〉. 〈1, 3〉 is the lexicographic improving cycle when agent 1 is the starting point. Therefore, s3 is assigned to agent 1 and s1 is assigned to agent 3 in M ∗ . During the second iteration, only agent 2 remains in set A and no improving cycle exists. Therefore, agent 2 receives s2 in M ∗ and the algorithm ends.

Note that if agent 2 is picked during the first iteration of Algorithm 1, the improving cycles visiting agent 2 are 〈2, 3, 1〉 and 〈2, 1〉, and 〈2, 3, 1〉 is the lexicographic improving cycle. Therefore, Algorithm 1 returns M ∗ = M2.

Its correctness is shown in the following proposition.

Algorithm 1

Require: Preference profile (≻1, . . . , ≻n) of SR preferences Ensure: A PE and IR matching 1: A←N. 2: M ∗ ← ∅. 3: while A ̸= ∅ do 4: Pick arbitrarily agent a1 fromA. 5: Compute the lexicographic improving cycle 〈a1, . . . , ak〉 restricted to A. 6: if k = 1 then ▷ No improving cycle starts from a1. 7: M ∗ ←M ∗ ∪ {(a1, sa1 )}. 8: else 9: for all j ∈ {1, . . . , k - 1} do 10: M ∗ ← M ∗ ∪ {(aj , saj+1 )}. 11: M ∗ ←M ∗ ∪ {(ak, sa1 )}. 12: A←A \ {a1, . . . , ak}. 13: returnM ∗ .

Proof. First of all, note that M ∗ is IR since either an agent receives her own service (line 7) or M ∗ results from an improving cycle visiting her (line 9-11). Let us show that M ∗ is not Pareto dominated by an IR matching of M. With this in mind, we show by induction that M ∗ is not Pareto dominated over Ai by an IR matching of MAi , where Ai represents set A at the beginning of iteration i of the while loop.

Base case: This case corresponds to the last iteration of the while loop. There are two possibilities: either Ai = {a1} or Ai = {a1, . . . , ak} with k > 1. In the first case, agent a1 receives her own service in any matching of MAi , and therefore none of them Pareto dominates M ∗ over Ai. In the latter case, 〈a1, . . . , ak〉 is a lexicographic improving cycle restricted to Ai and M ∗ results from it. This implies by Lemma 1 that M ∗ is not Pareto dominated over Ai by an IR matching of MAi .

Induction step: Assume that M ∗ is not Pareto dominated over Ai+1 by an IR matching of MAi+1 , and let us show that M ∗ is not Pareto dominated over Ai by an IR matching of MAi . Let N1 denote the set of agents visited by the improving cycle computed in line 5. There are two possibilities: either N1 = {a1} or N1 = {a1, . . . , ak} with k > 1. In the first case, there is no improving cycle restricted to Ai visiting agent a1. Therefore, M ∗ is not Pareto dominated over N1 by an IR matching of MAi since a1 must receive her own service in any IRmatching ofMAi . In the latter case, 〈a1, . . . , ak〉 is a lexicographic improving cycle restricted to Ai and M ∗ results from it. This implies by Lemma 1 that M ∗ is not Pareto dominated over N1 by an IR matching of MAi . In both cases, let N2 denote Ai \ N1. Note that N2 = Ai+1 (line 12), and (N1,N2) forms a partition of Ai. We know that M ∗ is not Pareto dominated over N2 by an IR matching of MN2 (by induction hypothesis), and M ∗ is not Pareto dominated over N1 by an IR matching of MAi . This implies by Lemma 2 that M is not Pareto dominated over Ai by an IR matching of MAi , which concludes the proof by induction.

Algorithm 2

Require: Preference profile (≻1, . . . ,≻n) of SR prefer-

ences, subset of agents A ⊆ N, agent a1 ∈ A Ensure: A lexicographic improving cycle restricted to A 1: N ←A \ {a1} 2: Pa1 ←Pile(N,≻a1 ). 3: (ae, sa2 ) ← pop(Pa1 ). 4: while noPath(a2, ae,GN) and Pa1 ̸= ∅ do 5: (ae, sa2 ) ← pop(Pa1 ). 6: if noPath(a2, ae,GN) then 7: return 〈a1〉 ▷ No improving cycle starts from a1. 8: k ← 2. 9: while ak ̸= ae do 10: N ←N \ {ak} 11: Pak ←Pile(N,≻ak , ak-1). 12: sak+1 ← pop(Pak ). 13: while noPath(ak+1, ae,GN) do 14: sak+1 ← pop(Pak ). 15: k ← k +1. 16: return 〈a1, . . . , ak〉.

For i = 1, this implies that M ∗ is not Pareto dominated over A1 by an IR matching of MA1 . Therefore, M ∗ is not Pareto dominated by any IR matching since A1 = N and MN = M. To conclude, let us show by contradiction that M ∗ is PE. Assume that M ′ is a matching Pareto dominating M ∗ over N. This implies that M ′ is IR since M ∗ is IR and M ′ ≿i M ∗ for any i ∈ N. This leads to a contradiction with M ∗ is not Pareto dominated by any IR matching.

It remains to show that Algorithm 1 can run in polynomial time. The size of A decreases during each while loop (line 12). Therefore, the number of iterations of the while loop is bounded by n. Hence, Algorithm 1 is polynomial if a lexicographic improving cycle restricted to A can be computed in polynomial time. Algorithm 2 performs this task by constructing, agent by agent, the lexicographic improving cycle. In the first while loop, it computes the most preferred pair of agent/service for agent a1 which leads to an improving cycle. To do so, it uses two data structures: pile Pa1 and graph GN.

After its construction by function Pile, Pa1 contains all pairs (i, sj) of N × SN such that (i, sj) ≻a1 (a1, sa1 ) and a1 ∈ Si, ordered from the most preferred to the least preferred according to ≻a1 . Function pop returns the first pair of Pa1 and removes it from Pa1 . Oriented graph GN is used to check the existence of an improving cycle starting from a given agent. Its set of vertices is N and its set of edges is {(i, j) ∈ N 2 : sj ∈ Si, i ∈ Nj}. Note that for any edge (i, j), sj can be assigned to agent i without violating IR. Therefore, if (ae, sa2 ) belongs to Pa1 and exists path a2 → . . . → ae in GN then 〈a1, a2, . . . , ae〉 is an improving cycle restricted to N ∪{a1}. Function noP ath(a, b, GN ) returns true if no path from a to b exists in GN.

At the end of the first while loop, either no improving cycle is founded and 〈a1〉 is returned, or (ae, sa2 ) is the most preferred pair for agent a1 in any improving cycle restricted to A. In the latter case, Algorithm 2 completes the sequence by computing, agent by agent, the most preferred remaining service for the last agent in the sequence when she serves her predecessor in the sequence. Note that N is updated after each step to reflect the set of remaining services. After its construction by function Pile, Pak contains all services si of Sak ∩ N such that ak ∈ Ni, ordered form the most preferred to the least preferred for agent ak when she serves agent ak-1.

Example 3. We use the problem described in Example 1 to illustrate Algorithm 2. Assume that A = {1, 2, 3} and a1 = 2. N is set to {1, 3}, pile Pa1 contains both (1, s3) and (1, s1), and G{1,3} is described in Figure 1. The first pair considered in Pa1 is (1, s3), and ae and a2 are set to 1 and 3, respectively. There is a path from 3 to 1 in G{1,3}, and therefore the algorithm does not enter in the first while loop. Since a2 ̸= ae, the algorithm enter in the second while loop. N is set to {1}, pile Pa2 only contains service s1, and G{1} is a single vertex. Then, a3 is set to 1. There is obviously a path from 1 to 1 and therefore the algorithm does not enter in the inner while loop. The second while loop ends since a3 = ae, and lexicographic improving cycle 〈2, 3, 1〉 is returned.

Algorithm 2 runs in polynomial time since the sizes of piles Pa1 and Pak are bounded above by n2 and the size of N decreases after each iteration of the second while loop. The following proposition shows the correctness of Algorithm 2.

Proposition 2. Algorithm 2 computes a lexicographic improving cycle starting from a1 and restricted to A.

Proof. Algorithm 2 either returns (i) 〈a1〉 or (ii) 〈a1, . . . , ak〉. In case (i), assume by contradiction that exists improving cycle 〈a1, a′2 , . . . , a′r 〉 restricted to A. Since preferences are SR, a1 ∈ Sa′r , (a′r , sa′2 ) ≻a1 (a1, sa1 ), sa′i ∈ Sa′i-1 and a′i-1 ∈ Na′i hold for any i ∈ {3, . . . , r}. Hence, a′2 → . . . → a′r is a path in GN. Therefore, (a′2 , sa′r ) is contained in Pa1 and noPath(a′2 , a′r ,GN) = false, leading to a contradiction with noPath(a2, ae,GN) = true at the end of the first while loop (line 6 in Algorithm 2).

In case (ii), the first while loop stops with noPath(a2, ae,GN) = false. This implies that there exists a path a2 → a′3 → . . . → ae in GN. Furthermore, we know by definition of Pa1 that (ae, sa2 ) ≻a1 (a1, sa1 ) and a1 ∈ Sae . Therefore, there exists at least one improving cycle 〈a1, a2, a′3 , . . . , ae〉. Note that (a1, sa′3 ) ≻a2 (a2, sa2 ) and a2 ∈ Na′3 hold. Hence, during the first iteration of the second while loop, the inner while loop (lines 13-14) stops with a3 such that (a1, sa3 ) ≻a2 (a2, sa2 ). By applying the same reasoning over the sequence, one can check that for any i ∈ {3, . . . , k}, (ai-1, sai+1 ) ≻ai (ai, sai ) holds. Therefore, 〈a1, . . . , ak〉 is an improving cycle.

Assume by contradiction that exists improving cycle 〈a1, a′2 , a′3 . . . , , a′r 〉 restricted to A such that either (a′r , sa′2 ) ≻a1 (ak, sa2 ), or a′r = ak and there exists ℓ ∈ {1, . . . , k} such that a′i = ai holds for any i < ℓ, and (aℓ-1, sa′ℓ+1 ) ≻aℓ (aℓ-1, saℓ+1 ). In the former case, pair (a′r , sa′2 ) belongs to Pa1 and is tested before (ak, sa2 ) in the first while loop. Therefore, noPath(a′2 , a′r ,GN) should be true, a contradiction with 〈a1, a′2 , a′3 . . . , a′r 〉 is an improving cycle. In the latter case, path a′ℓ+1 → . . . → a′r exists in GN

for N = A \ {a1, . . . , aℓ} since 〈a1, . . . , aℓ, a′ℓ+1 . . . , a′r 〉 is an improving cycle. Furthermore, we know that a′r = ak = ae. On the other hand, a′ℓ+1 should be tested before aℓ+1 in the inner while loop and noPath(a′ℓ+1 , ae,GN) necessarily returns true, leading to a contradiction.

Note that the correctness of Algorithm 1 does not rely on the assumption of SR preferences and still holds in the general case. However, the search for a lexicographic improving cycle is NP-hard in the general case whereas it can be computed in polynomial time with the assumption of SR preferences by Algorithm 2.

3.2 General Preferences

Algorithm 1 applies to general preferences whereas Algorithm 2 is restricted to SR preferences. Is it possible to extends Algorithm 2 to general preferences? The following proposition provides a negative answer to this question.

Proposition 3. Computing a PE and IR matching is NP-hard.

Proof. We present a reduction from the NP-complete problem (3,B2)-SAT [Berman and Karpinski, 2003]. An instance of (3,B2)-SAT contains a set of variables X = {x1, . . . , xs} and a set of clauses C = {c1, . . . , ct}. Each clause has three literals, and each variable appears in exactly 4 clauses of C, twice as a positive literal and twice as a negative literal. The problem is to decide whether there exists a truth assignment of X such that all clauses in C are true.

The reduction is as follows. For each variable xi, we introduce 4 literal-agents X1 i , X2 i , ¯X1 i and ¯X2 i . Agents X1 i and X2 i represent occurrences of xi as positive literals, and agents ¯X1 i and ¯X2 i represent occurrences of xi as negative literals. Furthermore, for each clause ci, we introduce clause-agent Ci, and an additional dummy clause-agent C0. For notational convenience, we denote by Lji the literal-agent corresponding to the literal appearing at position j in ci, and we denote by ℓ(i, j) and ¯ ℓ(i, j) the indices of the clauses where appear occurrence j of literals xi and ¬xi, respectively. Furthermore, for any subsets A ⊆ N and B ⊆ S, we denote by [A×B] an arbitrary order over pairs in {(a, b) : a ∈ A, b ∈ B}. Finally, for any 1 < i ≤ s, any 1 ≤ j < t and any 1 ≤ k < t, preferences are as follows. Note that only preferences over the pairs preferred to the initial endowment are provided.

Informally, preferences are designed such that there exists an improving cycle iff C is satisfiable. Any improving cycle can be divided into two parts. The first part is a path alternating between clause-agents and literal-agents, starting from C0 and ending at Ct. In this path, the literal-agent between clause-agents Ck and Ck+1 is a literal of ck. The second part of the cycle is a path which visits for each variable xi, either both X1 i and X2 i or both ¯X1 i and ¯X2 i . The second part of the cycle insure that no two literal-agents visited in the first part of the cycle correspond to a literal and its negation.

We show that there exists a matching Pareto dominating the initial endowment over N iff the instance of C is satisfiable. Assume that there exists truth assignment ϕ of X such that each clause in C is true. We construct from ϕ a matching which Pareto dominates over N the initial endowment. Let Lji i be a literal-agent corresponding to a literal of ci which is true according to ϕ. The services of Lji i and Ci are assigned to agents Ci-1 and Lji i , respectively. For each variable xi, if xi is set to true in ϕ then assign the service of ¯X2 i to agent ¯X1 i , and depending on the truth value of xi-1, assign the service of ¯X1 i either to agent Ct if i = 1, either to agent X2 i-1 if xi-1 = false, or to agent ¯X2 i-1 if xi-1 = true. If xi is set to false in ϕ then assign the service of X2 i to agents X1 i , and depending on the truth value of xi-1, assign the service of X1 i either to agent Ct if i = 1, either to agent X2 i-1 if xi-1 = false, or to agent ¯X2 i-1 if xi-1 = true. The other agents are assigned to their own services. It is easy to check that this assignment is IR and Pareto dominates the initial endowment over N .

The proof of the other implication relies on the structure of the preferences described above. The formal proof of this implication is omitted due to space limitation.

4 Sum andMin for Cardinal Preferences

In this section, we study the complexity of computing Sumoptimal and Min-optimal matchings for cardinal preferences.

4.1 Sum for General and AS Preferences

We first show that the computation of a Sum-optimal matching is hard to solve for general cardinal preferences.

Corollary 1. Computing Sum-optimal matching is NP-hard.

Proof. The reduction is essentially the same than the one provided in the proof of Proposition 3. We only need to give the utility values defining the preferences of the different agents. For each agent in this reduction, assign utility 8t to her initial endowment, and utility 8t + 1 for any pair which is preferred to her initial endowment. Other pairs have utility value 0.

This utility values enforce any matching which maximizes the sum to be IR. Indeed, the utility sum of any matching which provides utility 0 to at least one agent is bounded above by 4t(8t +1) = 32t2 +4t, whereas the utility sum for the initial endowment is (4t+1)(8t) = 32t2 +8t. Therefore, checking the existence of a matching which Pareto dominates the initial endowment over N amounts to decide if there exists a matching of utility sum strictly greater than 32t2 +4t. Note that the utility values implies indifferences since two pairs can have the same utility value. However, it is possible to slightly perturb the utility values by adding very small values in order to remove indifferences.

The remaining of the subsection is devoted to the description of a polynomial algorithm to compute a Sum-optimal matching for AS preferences. This algorithm relies on the well known assignment problem which a restriction of our setting where utility functions only depend on the service assigned to an agent. More formally, the utility function u′i : N × S → R of agent i is such that u′i (j, sℓ) = w′i (sℓ) holds for any j, ℓ ∈ N. The assignment problem aims to find a Sum-optimal matching for utility functions u′ . It is solvable in polynomial time by the Hungarian method [Kuhn, 1955].

We reduce the computation of a Sum-optimal matching, in an instance of the service exchange problem with cardinal AS preferences u, to an assignment problem with utility function u′ . The set of agents and the set of services remain the same. Note that utility function u′i of agent i can be described through w′i . For any agents i, ℓ ∈ N, we define the value of w′i over sℓ as w′i (sℓ) = wi(sℓ) + vℓ(i). To conclude, we show that the utility sum of matching M is the same for utility functions u and u′ = (u′1 , . . . , u′n ). By definition of u′ , we have ∑i∈N u′i (M) = ∑i∈N [wi(M(i)) + vS(i)(i)] = ∑i∈N [wi(M(i))+vi(M(si))] = ∑i∈N ui(M), where S(i) denotes the owner of M(i). Therefore, the optimal matchings for this two problems are the same.

Note that this approach can be applied to the search of a Sum-optimal and IR matching for SR and AS preferences. Indeed, it is possible to consider in an assignment problem that some services are unacceptable to an agent and they cannot be matched. By requiring in the assignment problem that the set of acceptable services for agent i is {sj : i ∈ Nj ∧ sj ∈ Si}, we insure that any complete matching is IR. Therefore, it is possible to compute a Sum-optimal matching among the set of IR matchings. Then, by comparing its value with the value of the Sum-optimal matching among the full set of matchings, one can conclude on the existence of an IR and Sum-optimal matching: these values coincide if and only if a Sum-optimal and IR matching exists.

4.2 Min for AS Preferences

The following proposition shows that even for restricted preferences, computing a Min-optimal matching is hard.

Proposition 4. Computing a Min-optimal matching is NPhard even for AS utility functions.

Proof. We present a reduction from (3,B2)-SAT. This problem is formally described in the proof of Proposition 3.

The reduction is as follows. For each variable xi, we introduce a gadget containing 5 agents X1 i , X2 i , Yi, ¯X1 i and ¯X2 i . Agents X1 i and X2 i represent occurrences of xi as positive literals, and agents ¯X1 i and ¯X2 i represent occurrences of xi as negative literals. Agents X1 i , X2 i , ¯X1 i and ¯X2 i are called literal-agents. Non zero utility values inside the gadget are depicted in Figure 2. Intuitively speaking, this gadget forces agent Yi to exchange her service according to one of the two improving cycles appearing in this figure. Hence, either Yi exchanges her service with literal-agents X1 i and X2 i , or she exchanges her service with literal-agents ¯X1 i and ¯X2 i . For each clause ci we introduce agent Ci. Agent Ci has utility 1 for receiving a service from a literal-agent which corresponds to a literal of ci, and she has utility 2 for serving this literal-agent. Symmetrically, each literal-agent corresponding to a literal of ci has utility 1 for receiving the service of Ci, and utility 2 for serving Ci. Intuitively speaking, agent Ci will perform a one-to-one exchange with a literal-agent corresponding to one of its literals in order to achieve utility 3. Finally, for each i ∈ {1, . . . , 2s - t}, we introduce agent Zi. These agents play the role of garbage collectors for unassigned literal-agents. Agent Zi has utility 1 for receiving a service from a literal-agent, and utility 2 for serving a literal-agent. Symmetrically, each literal agent has utility 1 for receiving a service from Zi, and utility 2 for serving Zi.

Let us show that C is satisfiable if and only if there exists a matching providing an utility of at least 3 to each agent. Assume that there exists a truth assignment ϕ of X that satisfies C. For each variable xi, if xi is true in ϕ then assign services according to improving cycle 〈Yi, ¯X1 i , ¯X2 i 〉, and otherwise assign services according to improving cycle 〈Yi, X1 i ,X2 i 〉. For each clause ci, choose one literal which is true according to ϕ and perform a one-to-one exchange of services between the corresponding literal-agent and Ci. Finally, each literal-agent who did not receive a service so far performs a one-to-one exchange with some agent Zi. It is easy to check that each agent achieves an utility of 3 in this matching.

Assume that there exists a matching M which provides an utility of at least 3 to each agent. We construct from M a truth assignment ϕ of the variables in X. Let us first focus on agent Yi. Her preference are such that she receives the service of either X1 i or ¯X1 i to achieve an utility of 3. Assume that Yi receives the service of X1 i and let us show that M should result from improving cycle 〈Yi,X1 i ,X2 i 〉. If X1 i serves Yi (with utility 1) then she should receive sX2 i because it is the only service providing her utility 2. Then, since X2 i serves X1 i (with utility 1), X2 i should receive sYi because it is the only services providing her utility 2. Following the same line of reasoning, we can conclude that if agent Yi receives s ¯X1 i then agent ¯X1 i should receive s ¯X2 i and agent ¯X2 i should receive sYi . Hence, for each variable xi, M results from either 〈Yi,X1 i ,X2 i 〉 or 〈Yi, ¯X1 i , ¯X2 i 〉. In the former case, set variable xi to false in ϕ and in the latter case, set variable xi to true in ϕ. Furthermore, for achieving an utility of 3 in M, agent Ci must obtain the service of an agent corresponding to a literal of ci. Since this literal-agent was not involve in one of the improving cycles describer above, the truth value of its corresponding variable satisfies ci. Therefore, ϕ satisfies all clauses of C.

5 Conclusion and FutureWorks

We introduced the service exchange problem where each agent can provide and receive a single service, and where preferences are defined over pairs costumer/service. We studied the computational complexity of finding a PE and IR, Sum-optimal and Min-optimal matchings under different preference restrictions. Our main achievement is a polynomial algorithm to compute a PE and IR for SR preferences.

An interesting line of research would be to extend the polynomial algorithm for computing a PE and IR matching to a broader class of preferences. Another direction is the computation of the core. It would be also interesting to study the complexity of computing a Sum-optimal and IR matching for AS cardinal preferences without SR preferences assumption. Finally, even if most of the problems studied in this paper are computationally hard, it would be worthy to consider MIP formulations of these problems able to solve instances of realistic size (e.g., [Lesca and Perny, 2010; Lesca et al., 2013]).

Acknowledgments

Taiki Todo thanks JSPS for support under JSPS KAKENHI Grant Numbers JP17H04695 and JP17H00761. Julien Lesca acknowledges support from the ANR project CoCoRICoCoDec, as well as the JCJC project MAPPOLEON.

A Appendix

The following lemma shows that a matching resulting from a lexicographic improving cycle possesses some guarantees of performance regarding Pareto dominance.

Lemma 1. If matchingM results from lexicographic improving cycle 〈a1, . . . , ak〉 restricted to N then M is not Pareto dominated over {a1, . . . , ak} by an IR matching of MN .

Proof. By contradiction, assume that M ′ is an IR matching of MN which Pareto dominates M over {a1, . . . , ak}. Let ℓ be the smallest integer such that (M ′ (saℓ ),M ′ (aℓ)) ≻aℓ (M(saℓ ),M(aℓ)) holds. Since M ′ belongs toMN and is IR, M ′ results from an improving cycle 〈a1, . . . , aℓ, a′ℓ+1 , . . . , a′r 〉 restricted to N. The existence of this improving cycle is a contradiction with 〈a1, . . . , ak〉 is a lexicographic improving cycle restricted to N.

The following lemma shows that Pareto dominance over two disjoint sets can imply Pareto dominance over its union.

Lemma 2. For any N ⊆ N, any partition (N1,N2) of N, and any matching M of MN1 , if M is both not Pareto dominated over N1 by an IR matching of MN, and not Pareto dominated over N2 by an IR matching of MN2 then M is not Pareto dominated over N by an IR matching of MN .

Proof. Assume by contradiction that M is both not Pareto dominated over N1 by an IR matching of MN , and not Pareto dominated over N2 by an IR matching of MN2 , and M ′ is an IR matching of MN which Pareto dominates M over N. This means that M ′ ≿i M holds for any i ∈ N, and exists j ∈ N such that M ′ ≻j M holds. If exists j ∈ N1 such that M ′ ≻j M then M ′ Pareto dominates M over N1, leading to a contradiction since M ′ is an IR matching of MN. Therefore, M ≿i M ′ holds for any i ∈ N1. This implies that M(i) = M ′ (i) holds for any i ∈ N1 since both M ≿i M ′ and M ′ ≿i M hold and there is no indifference. Therefore, M ′ belongs toMN2 since both M ∈ MN1 and M ′ ∈ MN hold. M ′ cannot Pareto dominate M over N2 since M ′ is an IR matching of MN2 . But in that case, M ′ neither Pareto dominates M over N1 nor N2, leading to a contradiction with M ′ Pareto dominate M over N.