Graphical One-Sided Markets

1 Introduction

Allocation of indivisible items to rational agents is a central problem which has been studied in economics and computer science. The problem arises in a wide range of applications: including resource allocation in distributed systems, spectrum allocation, kidney exchange programs and so on. Stability and fairness are two influential concepts which are studied in the context of allocation problems. Various notions of fairness such as proportionality, envy-freeness and maximin share guarantee [Budish, 2011] have been studied in the general setting of resource allocation [Bouveret et al., 2016; Beynier et al., 2018]. On the other hand, stability as a solution concept has received greater attention in the context of matchings [Gusfield and Irvin, 1989; Roth and Vate, 1990].

In this paper, we introduce a model which is closely aligned to the one-sided market, also known as the ShapleyScarf housing market [Shapley and Scarf, 1974]. This is a fundamental and well studied framework used to model an exchange economy. It consists of a set of rational agents each owning a house along with a strict preference ordering over all the houses present in the market. A stable allocation corresponds to an assignment of houses to agents such that no coalition of agents can improve by internal redistribution. An important question is whether stable allocations always exist in such markets and whether a finite sequence of exchanges can converge to such an allocation. It was shown that using a simple and efficient procedure often termed as Gale's Top Trading Cycle, one can always find an allocation that is stable. The allocation constructed in this manner also satisfies various desirable properties like it being strategy-proof and Pareto optimal.

In one-sided markets, agents' preferences are typically assumed to be strict and are not dependent on the allocation received by other agents. However, in many practical situations, an agent's utility for an allocation is dependent on both their intrinsic valuation for the allocated item as well as the items which are allocated to the agents within their neighbourhood. We consider a framework to model the allocation problem where agents have cardinal utilities associated with each allocation. The agents are not allowed to make monetary payments to each other, thus the utilities are nontransferable. For each agent i, the final utility depends on two components: the intrinsic value associated with the item assigned to agent i and the items assigned to the agents within the neighbourhood of agent i. We model the agents' neighbourhood structure as a directed weighted graph in which the nodes correspond to agents. For each agent, the incoming edges along with the associated weights denote the quantitative "influence" that neighbours have on the agent. In our model, this influence is also item specific. That is, each item a is associated with a subset of compatible items aλ. The externality for an agent who is allocated an item a depends on the influence from agents in its neighbourhood who are assigned items from aλ.

Such a framework naturally captures various instances of allocation problems that arise in practice. For instance, consider a housing allocation problem, where agents have some intrinsic valuation over the houses. In addition, suppose some of these agents are friends and would prefer to reside in houses near each other. In such a scenario, the final utility associated with an allocation depends on both the valuation of the house as well as the owners of the neighbouring houses. Similarly, consider an organization which needs to decide project allocation for its incoming employees, with each project being mentored by senior employees. An employee's preference for a project would rely on both, the nature of the project and the mentors assigned for the project.

Certain structural aspects are explicated in the model and these choices are influenced by the various frameworks often used to analyse strategic interaction. For instance, graphical dependency structures are known to play an important role in the analysis of strategic interaction in terms of the existence of stable outcomes and their computational properties. In game theory, such structures are studied in graphical games [Kearns et al., 2001]. While we do incorporate neighbourhood externalities in our model, these are required to satisfy a pairwise seperability constraint which specifies the influence of each agent in the neighbourhood. The eventual externality is additive over these pairwise values. In game theory, a similar constraint on the utility functions give rise to a well studied class of games called polymatrix games [Janovskaya, 1968]. Imposing pairwise separability is a natural restriction which typically helps achieve better computational properties and also helps in showing stronger lower bounds [Cai and Daskalakis, 2011; Deligkas et al., 2014; Rahn and Sch¨afer, 2015].

Markets form a fundamental model of exchange economy and allocations of indivisible items in such markets have been studied extensively both in terms of stability and fairness of allocation. In the context of two sided markets, the influence of nieghbourhood relations has been studied in [Arcaute and Vassilvitskii, 2009; Hoefer, 2013].[Hoefer, 2013] proposes a framework where players are modelled as nodes in a social network and explore possible matches only among the players in the current neighbourhood. [Arcaute and Vassilvitskii, 2009] models a job market as a 2-sided matching market and studies the importance of social contacts in terms of stable allocation. [Anshelevich et al., 2013] studies stable matchings in the presence of social contexts where players are positioned in an underlying weighted directed graph and the weights on the edges denote the rewards for being matched to each agent. Each agent's final utility for a matching depends on both the agent's individual reward as well as the rewards received by the neighbours under the matching.

For one-sided markets, [Bouveret et al., 2017] introduces a framework that models constraints based on the dependency relation between items with additive utility functions. The dependency is encoded as a graph on the item set and an allocation is required to satisfy the constraint that the items allocated to each agent forms a sub-graph of the item graph. The paper looks at additive utility functions and investigates the complexity of finding optimal allocations in terms of fairness, envy-freeness and maximin share guarantee. [Lonc and Truszczynski, 2018] further studies the computational properties of this model for maximin share allocations in the specific case when the item graph forms a cycle. Approximations of envy-freeness in terms of EF-1 is considered in [Bil `o et al., 2018]. [Chevaleyre et al., 2017] studies convergence properties for fair allocation of dynamics involving exchange of items by rational agents in the presence of a social network structure on the players. In this line of work listed above, fairness is the main solution concept that is studied. In our model, rather than viewing the social network structure as imposing restrictions on the set of feasible allocations, we interpret the neighbourhood structure as specifying agents' externalities which eventually contributes towards the final utility. In such a setting, the dynamics involving exchange of items are quite natural and therefore, stability of an allocation is an important consideration that we study.

Decentralised swap dynamics where pairs of agents exchange items or services and the optimality of allocations is studied in [Damamme et al., 2015]. [Gourves et al., 2017] examines the influence of a social network structure on players in terms of these exchanges and optimal allocations. [Sun et al., 2015; Fujita et al., 2015] look at unrestricted exchange dynamics in the context of lexicographic preference ordering, with [Sun et al., 2015] focussing on player preferences which have a common structure, implying an asymmetry in the objects. As part of our work, we consider such swap dynamics in the context of a neighbourhood structure which influences a player's utility.

The presence of externalities has been studied in the literature, mainly in the context of fair and efficient allocations. [Branzei et al., 2013] studies the problem of fair division of divisible heterogeneous resources in the presence of externalities; where the agent's utility depends on the allocation to others. A recent paper [Ghodsi et al., 2018] considers a model similar to the one we study in which they analyse fair allocation in terms of the maximin share guarantee. [Lesca and Todo, 2018] incorporates a restricted notion of externality in the context of a service exchange model and analyses the complexity of computing efficient allocation.

2 The Model

We introduce the resource allocation problem that we study in this paper which we call the graphical matching problem. Let N = {1, 2, . . . , n} be a finite set of agents (or players) and A be a finite set of items such that |N| = |A|. The local neighbourhood structure for the set of agents, referred to as the player graph is given by a weighted directed graph G = (N, τ,w) where τ ⊆ N ×N and w is a function that associates with each edge (i, j) ∈ τ , a weight wi,j ∈ R. We say that the player graph G is symmetric if for each pair of players i, j, (i, j) ∈ τ implies (j, i) ∈ τ and wi,j = wj,i. We say that the player graph G is unweighted if for all (i, j) ∈ τ , wi,j = 1.

The dependency structure associated with the items, also referred to as the item graph, is specified by an undirected graph H = (A, λ) where λ ⊆ A × A. We assume that both G and H do not have self loops. For a player i ∈ N, let iτ = {j | (j, i) ∈ τ} denote the set of all neighbours of i in G. For an item a ∈ A, let aλ = {b | (a, b) ∈ λ} denote the set of all items connected to a according to the dependence structure H.

Each player has a valuation function vi : A → R≥0 that specifies the initial utility that the player associates with each item. An allocation π : N → A is a bijection that assigns items to players. In other words, an allocation π assigns exactly one item to each player. Let Π denote the set of all allocations. For a player i ∈ N and an allocation π ∈ Π, let N(i, π) = {j ∈ N | π(j) ∈ (π(i))λ}. For i, j ∈ N, we say that i is connected to j in π if j ∈ N(i, π). Let di(π) = N(i, π) ∩ iτ . The utility of player i for allocation π is then given by: ui(π) = vi(π(i)) + ri(π) where ri(π) = Σj∈di(π)wj,i. In other words, the utility of player i on an allocation π depends on his valuation for π(i) as well as the agents that are assigned items in the local neighbourhood of π(i) (N(i, π)). To simplify notation, we often use vi(π) to denote vi(π(i)). The social welfare for an allocation π is defined as SW(π) = Σi∈Nui(π). We say that the graphical matching problem has uniform valuation if for all i ∈ N and a ∈ A, vi(a) = c for some constant c. In this case, the utilities of players are determined solely by their local neighbourhood structure. An instance of the graphical matching problem is specified by the tuple M = (G,H, (vi)i∈N) where G = (N, τ,w) and H = (A, λ). We say that M = (G, H, (vi)i∈N) has symmetric neighbourhood if G is symmetric. M is unweighted if G is unweighted.

Stability in an allocation captures the property that players do not have any incentive to exchange goods and deviate to a new allocation. Given an allocation π, we call a pair of players i, j ∈ N to be a blocking pair in π, if there exists another allocation π′ where π′ (i) = π(j), π′ (j) = π(i) and π′ (k) = π(k) for all k ∈ N-{i, j} such that ui(π) < ui(π′ ) and uj(π) < uj(π′ ). In other words, the players i, j have an incentive to deviate from the current allocation by exchanging their items. We say an allocation π is 2-stable if there is no blocking pair in π.

Given an allocation π along with a blocking pair (i, j), we say that π′ is a resolution of the blocking pair if π′ (i) = π(j) and π′ (j) = π(i). We denote this by π →i,j π′ . An improvement path is a maximal sequence of allocations π0π1π2 . . . such that for all k ≥ 1, πk-1 →i,j πk for some pair of players i, j ∈ N. It is easy to observe that the existence of a finite improvement path implies the existence of a 2-stable allocation.

For an allocation π, we call X ⊆ N a blocking coalition, if there exists π′ and a bijection µ : X → X such that for all i ∈ X, π′ (i) ̸= π(i), π′ (i) = π(µ(i)) and ui(π′ ) > ui(π). We say an allocation π is core stable if there is no blocking coalition in π.

Example 1. Let the set of players N = {1, . . . , 6} and A = {A,B,C,D,E, F} with vi(a) = 0 for all i ∈ N and a ∈ A. Let G = (N, τ,w) be defined as follows: τ = {(1, 2), (2, 3), (3, 1), (4, 1), (5, 2), (6, 3)} and wi,j = 1 for all (i, j) ∈ τ . Let the item graph be the structure given in Figure 1. Consider the allocation π where π(1) = A, π(2) = B, π(3) = C and π(4) = D, π(5) = E, π(6) = F, then u1(π) = u2(π) = u3(π) = 1 and u4(π) = u5(π) = u6(π) = 0. Now suppose the pair (1, 4) exchanges items and let π′ be the resulting allocation. That is, π′ (4) = A and π′ (1) = D. Then, u1(π′ ) = 0.

The classical one-sided matching market can be viewed as a special case of the model given above. Consider an instance of the one-sided market consisting of two finite sets X and Y

where |X| = |Y |. Each x ∈ X has a valuation function zx : Y → R which specifies the preference ordering over outcomes in Y . An allocation π is a bijection π : X → Y . The notion of a 2-stable and core-stable allocation remains the same as defined earlier; we view the valuation function zx as specifying the final utility of player x ∈ X. Given an instance M of a one-sided market, we can construct an instance M ′ of the graphical matching problem such that the set of stable allocations in M precisely constitutes the set of stable allocations in M ′ . We take N = X, A = Y and vi(π(i)) = zi(π(i)) with the player graph G = (N, τ,w) where τ = ∅.

In one-sided markets, a 2-stable allocation always exists and it can be computed using the Top Trading Cycle procedure. On the other hand, the presence of neighbourhood externalities results in dynamics that is more complex and significantly different in terms of players' behavioural aspects. The example given below shows that in the graphical matching problem, a 2-stable outcome need not always exist even in the simple case when the instance has uniform valuation and when the underlying neighbourhood structure is unweighted.

Example 2. Let the set of players N = {1, . . . , 6} and A = {A,B,C,D,E, F}. Suppose the player graph G = (N, τ, w) forms a cycle on N consisting of the edges (6, 1) ∈ τ and (i, i + 1) ∈ τ for all i : 1 ≤ i ≤ 5. For every edge (i, j) ∈ τ, let wi,j = c for some positive constant c. We also assume uniform valuation vi(a) = 0 for all i ∈ N and a ∈ A. Let the item graph be the structure given in Figure 1. Since the item graph consists of two 3-cliques, it is sufficient to divide players into groups of 3, assign them to any of the 3-cliques. It can be verified that this instance does not have a 2-stable allocation.

3 Stability in Symmetric Neighbourhood

Given Example 2, a natural question is to identify restricted classes of the graphical matching problem where stable outcomes are guaranteed to exist. We show that when the underlying player graph is symmetric, a 2-stable outcome always exists. In general, it is PLS-hard to compute such a stable allocation. We also identify restrictions under which stable allocations can be computed efficiently.

Theorem 1. Every improvement path in a symmetric graphical matching problem is finite. Thus, a 2-stable allocation always exists.

Proof sketch. We can argue that the following function acts as a potential function. φ(π) = ∑i∈N (vi(π) + ui(π)).

Corollary 1. In a symmetric graphical matching problem with uniform valuation where the underlying player graph is unweighted, we can compute a 2-stable allocation in polynomial time.

Proof sketch. Suppose vi(a) = c for all i ∈ N and a ∈ A. Then, φ is bounded above by 2nc + 2|τ | and below by 2nc; in each resolution step the value increases by at least 2.

If we consider the player graph to have weighted edges, then computing a 2-stable outcome is PLS-complete already for the symmetric graphical matching problem with uniform valuation and non-negative edge weights.

Theorem 2. Finding a 2-stable allocation in a symmetric graphical matching problem with uniform valuation in which the edge weights in the underlying player graph are nonnegative is PLS-complete.

Proof sketch. Without loss of generality we assume that vi(a) = 0 for all i ∈ N and a ∈ A. The potential function defined in the proof of Theorem 1 essentially reduces to the social welfare, i.e., φ(π) = Σi∈Nui(π) = SW(π). It can be verified that computing a 2-stable allocation is in PLS. To show PLS-hardness, we give a tight reduction from the max-cut problem with FLIP neighbourhood [Sch¨affer and Yannakakis, 1991].

Let Q = (V,E, {ze}e∈E) be an instance of the max-cut problem where V is the set of vertices, E ⊆ V × V is the set of edges and {ze}e∈E is the set of non-negative edge weights. We construct an instance of the symmetric graphical matching problem in which the underlying player graph has non-negative edge weights as follows. Let the player graph G = (N, τ), where N = {vblue | v ∈ V } ∪ {vred | v ∈ V }. That is, for every vertex v ∈ V , there are two vertices vblue and vred in N. Thus |N| = 2 ∗ |V |. For each edge (u, v) ∈ E we add two edges in τ: (ublue, vblue) ∈ τ and (ured, vred) ∈ τ with wublue,vblue = wured ,vred = z(u,v). Let wmax = |N|2 ∗ (maxe∈E ze -mine∈E ze). For every v ∈ V , we also add the edge (vblue, vred) ∈ τ with wvblue,vred = wmax . The item graph is the complete bipartite graph H = (A, λ) where each partition consists of |V | vertices. In other words, let the two partitions be A1 and A2, with vertices A1(1), A1(2), . . . , A1(|V |) and A2(1), A2(2), . . . , A2(|V |)). For an arbitrary cut (V1, V1), we can construct an allocation π such that SW (π) = 4 ∗ cutWeight (V1, V1) + 2|V | ∗ wmax, that proves the result.

Since Theorem 2 gives a tight PLS reduction from the maxcut problem, we have the following corollary.

Corollary 2. The standard local search algorithm takes exponential time in the worst case for the symmetric graphical matching problem.

The above result shows that in symmetric graphical matching problems with uniform valuations, while a potential function exists, the bound on the function can be exponential in the encoding of the instance. A natural question is to ask if the utilities can be replaced by some bounded integer function for which the local search has the exact same behaviour. We now show that when the degree of the player graph is bounded by two, this is indeed possible, resulting in a polynomial time procedure.

Theorem 3. For the symmetric graphical matching problem with uniform valuation, if the underlying player graph has vertices of degree at most two, a 2-stable allocation can be computed in polynomial time.

Proof sketch. Let ci,1 = maxj∈iτ |wj,i| with ci,2 = minj∈iτ |wj,i| if |iτ | = 2 and ci,2 = 0 otherwise (∀i ∈ N). Let g : N → N denote an ordering of the players (where g(i) denotes the rank of i ∈ N in this ordering) which satisfies the following condition: if g(i) < g(j) then ci,1 ≥ cj,1. For i ∈ N, let umin i = minπ∈Π ui(π) and Yi = {umin i , umin i + ci,2, umin i + ci,1, umin i + ci,1 + ci,2}. Note that, for all π ∈ Π, ui(π) ∈ Yi. For x ∈ Yi, let

It can be shown that P(π) = ∑i∈N (2n-g(i))fi(ui(π)) is a potential function with an upper bound of 6n2 and a step size of at least 1 ensuring computation in polynomial time.

The above result implies efficient computation for various classes of graphs which are often studied, for instance, simple cycles. One natural question is whether the result can be extended to structures with small (logarithmic) neighbourhood. Such a restriction on the neighbourhood graph has interesting consequences in various classes of strategic form games where equilibrium computation is generally known to be hard [Gottlob et al., 2005]. We now show that for bounded degree graphs the problem remains PLS-complete.

Theorem 4. Finding a 2-stable allocation in a symmetric graphical matching problem with uniform valuation in which the underlying player graph has vertices with degree at most six is PLS-complete.

Proof sketch. [Els¨asser and Tscheuschner, 2011] showed that finding a local max-cut with a FLIP neighbourhood is PLScomplete even for graphs with degree at most five. Since our reduction in Theorem 2 increases the degree of each vertex by at most one, the result follows.

While in the analysis above, we consider restrictions on the player graph, it is also natural to study restrictions on the item graph. A starting point would be to consider the case when the item graph is a complete graph. It can be verified that in this situation, the externalities do not play a crucial role and a core stable allocation can be computed using the TTC algorithm. A similar observation holds when the edge set in the item graph is empty (λ = ∅). Another candidate restriction would be the bipartite graph. However, our PLShardness reduction in Theorem 2 constructs a complete bipartite item graph. A careful analysis of the potential function in the context of complete bipartite item graphs provides an upper bound in terms of the size of the partition.

Theorem 5. For the symmetric graphical matching problem, if the underlying item graph is a complete bipartite graph H = (U, V, U × V ) with U and V being the 2 partitions, a 2-stable allocation can be computed in O(nmin(|U|,|V |)+4 ).

-2d

Proof sketch. Let NU = {i | π(i) ∈ U} and NV = {i | π(i) ∈ V }. Then the potential function reduces to φ(π) = ∑i∈NU 2ui(π) + ∑i∈NV 2vi(π). Assume |U| ≤ |V |. For each assignment π, we can find the maximum value of ∑i∈NV 2vi(π) by finding the maximum weight matching of the bipartite graph Q = (V, NV , V ×NV ) with the weight of an edge (i, a) being vi(a) (inO(n4 )). Since there are n! (n-|U |)! ways of assigning players to U, an allocation with the optimal potential value can be computed in O(nmin(|U|,|V |)+4 ).

Corollary 3. For the symmetric graphical matching problem, if the underlying item graph is a complete bipartite graph with a constant number of vertices in one of the partitions, a 2-stable allocation can be computed in polynomial time.

There are various interesting graph structures which satisfy the above restriction, the simplest being the star graph, which is independently important in modelling workplaces with flat hierarchies, such as research labs.

4 Stability in Asymmetric Neighbourhood

When the underlying player graph is not symmetric, Example 2 shows that 2-stable outcomes need not always exists. The negative result already holds for the allocation problem with uniform valuation where the underlying player graph is a cycle and the item graphs consists of two disconnected cliques. This raises the question: What is the complexity of deciding if an instance of the graphical matching problem has a 2-stable outcome? We show that in general, this problem is NP-complete. We then identify restrictions where stable outcomes always exist and can be computed efficiently.

Theorem 6. The problem of deciding if an instance of the graphical matching problem has a 2-stable allocation is NPcomplete.

Proof sketch. Given an allocation π, deciding whether π is a 2-stable allocation can be done in polynomial time. It suffices to check if there is a blocking pair in π. Thus the above problem is in NP. To show hardness, we give a reduction from 3-SAT. Let the 3-SAT instance have q variables ({a1, a2, . . . , aq}) and m clauses ({c1, c2, . . . , cm}). We create an instance of the graphical matching problem with

|N| = 4m + 2q, with the players being differentiated into 6 types with N = C1 ∪ C2 ∪ C3 ∪ C4 ∪ S1 ∪ S2, where ∀i ∈ {1, 2, 3, 4} |Ci| = m and ∀j ∈ {1, 2} |Sj| = q. The key idea is to set up item valuations and the player neighbourhood structure such that a stable allocation can only exist if each player is assigned an item from the item set corresponding to its type(s) and the 3-SAT instance is satisfiable. We set up the following constants to aid our explanation: b = (2q + 3m + 20)d = (2q + 3m + 20)2 e = (2q + 3m+ 20)3 f with f = 1. There are 4 players corresponding to each clause and 2 players corresponding to each variable. For each clause ci, the players corresponding to it (ci,1,ci,2, ci,3 and ci,4) are connected as shown in Figure 2, with wci,2,ci,1 = wci,4,ci,3 = d-e, wci,1,ci,2 = wci,3,ci,4 = d, wci,4,ci,1 = wci,2,ci,3 = d, wci,1,ci,4 = wci,3,ci,2 = d - e and wci,3,ci,1 = wci,1,ci,3 = wci,2,ci,4 = wci,4,ci,2 = -2d. For each variable aj, there are two players sj,1 and sj,2 corresponding to the positive literal aj and the negative literal ¬aj respectively. The edge connecting these two players has a large negative weight (wsj,1,sj,2 = wsj,2,sj,1 = -d). For each clause ci where a positive literal aj appears x times and the corresponding negative literal ¬aj appears y times, wsj,1,ci,1 = (x - y)e and wsj,2,ci,1 = (y - x)e. For example, suppose ci = at ∨ ¬au ∨ av. (t ̸= u ̸= v) Then, wst,1,ci,1 = wsu,2,ci,1 = wsv,1,ci,1 = e and wst,2,ci,1 = wsu,1,ci,1 = wsv,2,ci,1 = -e.

The item graph is A = AC1 ∪AC2 ∪AC3 ∪AC4 ∪AS1 ∪AS2 , with |ACi | = m and |ASj | = q, with each of these six subsets being cliques. Additionally, there is complete connection between AS2 and AC1 , AC1 and AC2 and AC3 and AC4 . The table above contains vp(t), for each player p and item t.

Thus, deciding the existence of a 2-stable allocation in an instance of the graphical matching problem is NP-complete. It is natural to try to identify restricted classes in which stable allocations are guaranteed to exist and classes where such allocations can be computed efficiently. A natural restriction to consider is a hierarchical influence structure, which is present in several organizations. In our framework, such a structure can be modelled by restricting the player graph to a directed acyclic graph (DAG). We now show that when the player graph is a DAG, a core stable allocation is guaranteed to exist and such an allocation can be computed in polynomial time.

Theorem 7. Consider an instance M of the graphical matching problem where the underlying player graph G is a DAG. A core stable allocation is guaranteed to exist in M and it can be computed in polynomial time.

Theorem 8. Consider an instance M = (G,H, (vi)i∈N) of the graphical matching problemwith uniformvaluation. IfM

satisfies the following conditions, then a 2-stable allocation always exists and it can be computed in polynomial time.

• G is a cycle and ∃i, j ∈ N such that (j, i) ∈ τ and wj,i > 0.
• there exists a ∈ A such that for all a′ ∈ A - {a}, (a, a′ ) ∈ λ.

Theorem 9. Consider an instance M = (G,H, (vi)i∈N) of the graphical matching problemwith uniform valuation. If G is a cycle with positive connection weights w and H is connected and has at least 1 node with degree 1, then a core stable allocation always exists and it can be computed in polynomial time.

Note that it is not the case that every 2-stable allocation is also a core stable allocation in this restricted setting (as specified in Theorem 9). Consider an instance of the graphical matching problem with uniform valuation where N = {1, . . . , 6} forms a cycle and the item graph is as shown in Figure 3. The numbers labelling the nodes of the item graph denote the players to which the items are assigned. Consider the allocation π where π(i) = Ai for i ∈ {2, 4, 6} and πi = Bi for i ∈ {1, 3, 5} (also labelled in Figure 3). It can be verified that π is 2-stable but not core stable due to the existence of the blocking coalition X = {1, 3, 5}. In fact, at π there is a unique blocking coalition given by X. The resolution of the blocking coalition generates an allocation π′ where π′ (1) = B5, π′ (3) = B3 and π′ (5) = B5. Now X′ = {2, 4, 6} forms a blocking coalition in π′ . It can also be verified that starting at π there is a unique sequence of improvement steps resolving blocking coalitions which results in an infinite coalition improvement path.

5 Envy-Freeness

Envy-freeness is a natural and well-studied notion of fairness in resource allocation. In the cake-cutting problem, the existence of a complete, envy-free allocation is guaranteed for all agent valuations [Alon, 1987]. In the indivisible goods setting, we have hardness results [Bouveret and Lang, 2008] for computing the existence of a complete, envy-free allocation (Note: An allocation is complete if all of the item(s) available has (have) been assigned to the players). Recent works on resource allocation with a graphical component ([Chevaleyre et al., 2017], [Bouveret et al., 2017], [Abebe et al., 2017] and [Beynier et al., 2018]) have examined envy-freeness and its variants in great detail. Typically, the notion of envy is defined with respect to a bundle of items possessed by some other player. In our model, since a player's utility is dependent on other players' allocations, we adopt a slightly modified notion of envy-freeness, which is defined as follows. An allocation π is envy-free if there does not exist i, j such that ui(π) < ui(π′ ) where π′ (i) = π(j), π′ (j) = π(i) and for all k ∈ N -{i, j}, π(k) = π′ (k). The above notion is very similar to the notion of swap envy-freeness defined in [Branzei et al., 2013]. Note that, in a graphical matching problem, every allocation is complete by definition. A natural question is to ask whether it is possible to decide the existence of an envy-free allocation given an instance of the graphical matching problem. We show that even for a graphical matching problem with uniform valuation, where the underlying player graph is a cycle, this problem is NP-complete.

Theorem 10. For an instance of the graphical matching problem with uniform valuation where the underlying player graph is an unweighted cycle, deciding if there exists an envyfree allocation is NP-complete.

It is not difficult to show that deciding the existence of a complete, envy-free allocation in an instance of the symmetric graphical matching problem is NP-complete. Note that, deciding the existence of a complete, envy-free assignment in an allocation problem is known to be NP-complete [Bouveret and Lang, 2008].

6 Conclusions

In this paper we studied the problem of allocating indivisible items to a set of players where agents have cardinal nontransferable utilities associated with each allocation. We extended the one-sided market model to the network setting where agents' utilities depend on their neighbourhood externalities that are item specific and pairwise separable. We show that unlike in the case of one-sided markets, 2-stable allocations may not always exist. When the underlying neighbourhood structure is symmetric, a 2-stable allocation is guaranteed to exist although computing such an allocation is PLScomplete (already for player graphs of degree 6). We provide a polynomial time procedure to compute a 2-stable allocation when the degree of the player graph is bounded by two. An interesting question is to see if this result can be extended to player graphs of degree three using the technique of local linear programs as done for the local max-cut problem [Poljak, 1995]. Another natural question is the existence of core stable outcomes. While we believe that a core-stable allocation always exists in the symmetric setting, so far, we have been unable to prove this result. In case a core-stable outcome is not guaranteed to exist, it would be useful to find the maximum value of c such that c-stable outcomes exist.

There are several ways to extend the model. Allocations that allow subsets of items to be assigned to players is an obvious choice. We could also consider externalities which are not necessarily pairwise separable. It would be interesting to see whether the existence results continue to hold in these extended settings. It would also be interesting to identify more general classes of neighbourhood structures in which stable allocations are guaranteed to exist and where such an allocation can be efficiently computed.

Acknowledgements

We thank the reviewers for their useful comments. Sunil Simon was partially supported by grant MTR/2018/001244.