# graphical_onesided_markets__23209e8f.pdf

Graphical One-Sided Markets

Sagar Massand and Sunil Simon Department of CSE, IIT Kanpur, Kanpur, India {smassand, simon}@cse.iitk.ac.in,

We study the problem of allocating indivisible objects to a set of rational agents where each agent s ﬁnal utility depends on the intrinsic valuation of the allocated item as well as the allocation within the agent s local neighbourhood. We specify agents local neighbourhood in terms of a weighted graph. This extends the model of one-sided markets to incorporate neighbourhood externalities. We consider the solution concept of stability and show that, unlike in the case of one-sided markets, stable allocations may not always exist. When the underlying local neighbourhood graph is symmetric, a 2stable allocation is guaranteed to exist and any decentralised mechanism where pairs of rational players agree to exchange objects terminates in such an allocation. We show that computing a 2-stable allocation is PLS-complete and further identify subclasses which are tractable. In the case of asymmetric neighbourhood structures, we show that it is NP-complete to check if a 2-stable allocation exists. We then identify structural restrictions where stable allocations always exist and can be computed efﬁciently. Finally, we study the notion of envyfreeness in this framework.

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 inﬂuential 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 [Gusﬁeld 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 Shapley Scarf 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 ﬁnite sequence of exchanges can converge to such an allocation. It was shown that using a simple and efﬁcient procedure often termed as Gale s Top Trading Cycle, one can always ﬁnd an allocation that is stable. The allocation constructed in this manner also satisﬁes 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 ﬁnal 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 inﬂuence that neighbours have on the agent. In our model, this inﬂuence is also item speciﬁc. 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 inﬂuence 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 ﬁnal utility associated with an allocation depends on both the valu-

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

ation 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 inﬂuenced 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 speciﬁes the inﬂuence 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 inﬂuence 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 ﬁnal 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 ﬁnding 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 speciﬁc 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 ﬁnal 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 inﬂuence 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 inﬂuences a player s utility. The presence of externalities has been studied in the literature, mainly in the context of fair and efﬁcient 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 efﬁcient 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 ﬁnite set of agents (or players) and A be a ﬁnite 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 speciﬁed 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 speciﬁes 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 ex-

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

actly 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 deﬁned 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 speciﬁed 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 ﬁnite 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 deﬁned 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 ﬁnite sets X and Y

Figure 1: An item graph

where |X| = |Y |. Each x X has a valuation function zx : Y R which speciﬁes 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 deﬁned earlier; we view the valuation function zx as specifying the ﬁnal 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 signiﬁcantly 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 sufﬁcient to divide players into groups of 3, assign them to any of the 3-cliques. It can be veriﬁed 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 efﬁciently.

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

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

Corollary 1. In a symmetric graphical matching problem with uniform valuation where the underlying player graph is

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 deﬁned in the proof of Theorem 1 essentially reduces to the social welfare, i.e., φ(π) = Σi Nui(π) = SW (π). It can be veriﬁed 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 cut Weight(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 satisﬁes 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

0 if x = umin i 1 if x = umin i + ci,2(ci,2 ci,1) 2 if x = umin i + ci,1 and ci,1 > ci,2 3 if x = umin i + ci,1 + ci,2 and ci,2 > 0 It can be shown that P(π) = 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 efﬁcient 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 ﬁnding a local max-cut with a FLIP neighbourhood is PLScomplete even for graphs with degree at most ﬁve. 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 veriﬁed 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).

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Figure 2: A gadget

Proof sketch. Let NU = {i | π(i) U} and NV = {i | π(i) V }. Then the potential function reduces to φ(π) = P i NU 2ui(π) + P i NV 2vi(π). Assume |U| |V |. For each assignment π, we can ﬁnd the maximum value of P i NV 2vi(π) by ﬁnding the maximum weight matching of the bipartite graph Q = (V, NV , V NV ) with the weight of an edge (i, a) being vi(a) (in O(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 ﬂat 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 efﬁciently.

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 sufﬁces 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

p S1 S2 p C1 p C2 p C3 p C4 t AS1 b 0 0 0 0 t AS2 b 0 0 0 0 t AC1 0 b + 4e f b 6d b b 6d t AC2 0 b 6d b b 6d b f t AC3 0 b f b 6d b b 6d t AC4 0 b 6d b f b 6d b

|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 satisﬁable. We set up the following constants to aid our explanation: b = (2q + 3m + 20)d = (2q + 3m + 20)2e = (2q + 3m + 20)3f 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 efﬁciently. A natural restriction to consider is a hierarchical inﬂuence 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 problem with uniform valuation. If M

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Figure 3: An item graph and an allocation

satisﬁes 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 problem with 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 speciﬁed 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 veriﬁed 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 veriﬁed that starting at π there is a unique sequence of improvement steps resolving blocking coalitions which results in an inﬁnite 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 deﬁned 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 modiﬁed notion of envy-freeness, which is deﬁned 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 deﬁned in [Branzei et al., 2013]. Note that, in a graphical matching problem, every allocation is complete by deﬁnition. 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 difﬁcult 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 speciﬁc 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 ﬁnd 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 efﬁciently computed.

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

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

[Abebe et al., 2017] R. Abebe, J. Kleinberg, and D.C. Parkes. Fair division via social comparison. In AAMAS 17, pages 281 289, 2017.

[Alon, 1987] N. Alon. Splitting necklaces. Advances in Mathematics, 63(3):247 253, 1987.

[Anshelevich et al., 2013] E. Anshelevich, O. Bhardwaj, and M. Hoefer. Friendship and stable matching. In ESA 13, page 49 60, 2013.

[Arcaute and Vassilvitskii, 2009] E. Arcaute and S. Vassilvitskii. Social networks and stable matchings in the job market. In WINE 09, pages 220 231, 2009.

[Beynier et al., 2018] A. Beynier, Y. Chevaleyre, L. Gourv es, J. Lesca, N. Maudet, and A. Wilczynski. Local envy-freeness in house allocation problems. In AAMAS 18, pages 292 300, 2018.

[Bil o et al., 2018] V. Bil o, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters, C. Vinci, and W. S. Zwicker. Almost envy-free allocations with connected bundles. In Proceedings of the 10th ITCS, volume 124 of LIPIcs, pages 14:1 14:21, 2018.

[Bouveret and Lang, 2008] S. Bouveret and J. Lang. Efﬁciency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. JAIR, 32:525 564, 2008.

[Bouveret et al., 2016] S. Bouveret, Y. Chevaleyre, and N. Maudet. Fair Allocation of Indivisible Goods, chapter 12. Handbook of Computational Social Choice. Cambridge University Press, 2016.

[Bouveret et al., 2017] S. Bouveret, K. Cechl arov a, E. Elkind, A. Igarashi, and D. Peters. Fair division of a graph. In IJCAI 17, pages 135 141, 2017.

[Branzei et al., 2013] S. Branzei, A.D. Procaccia, and J. Zhang. Externalities in cake cutting. In IJCAI 13, pages 55 61, 2013.

[Budish, 2011] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011.

[Cai and Daskalakis, 2011] Y. Cai and C. Daskalakis. On minmax theorems for multiplayer games. In Proceedings of the SODA 11, pages 217 234. SIAM, 2011.

[Chevaleyre et al., 2017] Y. Chevaleyre, U. Endriss, and N. Maudet. Distributed fair allocation of indivisible goods. Artiﬁcial Intelligence, 242:1 22, 2017.

[Damamme et al., 2015] A. Damamme, A. Beynier, Y. Chevaleyre, and N. Maudet. The power of swap deals in distributed resource allocation. In AAMAS 15, pages 625 633, 2015.

[Deligkas et al., 2014] A. Deligkas, J. Fearnley, R. Savani, and P. Spirakis. Computing approximate nash equilibria in polymatrix games. In WINE 14, pages 58 71, 2014.

[Els asser and Tscheuschner, 2011] R. Els asser and T. Tscheuschner. Settling the complexity of local max-cut (almost) completely. In ICALP 11, pages 171 182. Springer, 2011. [Fujita et al., 2015] E. Fujita, J. Lesca, A. Sonoda, T. Todo, and M. Yokoo. A complexity approach for core-selecting exchange with multiple indivisible goods under lexicographic preferences. In AAAI 15, pages 907 913, 2015. [Ghodsi et al., 2018] M. Ghodsi, H. Saleh, and M. Seddighin. Fair allocation of indivisible items with externalities. Co RR, abs/1805.06191, 2018. [Gottlob et al., 2005] G. Gottlob, G. Greco, and F. Scarcello. Pure Nash equilibria: Hard and easy games. JAIR, 24:357 406, 2005. [Gourves et al., 2017] L. Gourves, J. Lesca, and A. Wilczynski. Object allocation via swaps along a social network. In IJCAI 17, pages 213 219, 2017. [Gusﬁeld and Irvin, 1989] D. Gusﬁeld and R. Irvin. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989. [Hoefer, 2013] M. Hoefer. Local matching dynamics in social networks. Information and Computation, 222:20 35, 2013. [Janovskaya, 1968] E.B. Janovskaya. Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik, 8:381 384, 1968. [Kearns et al., 2001] M. Kearns, M. Littman, and S. Singh. Graphical models for game theory. In UAI 01, pages 253 260, 2001. [Lesca and Todo, 2018] J. Lesca and T. Todo. Service exchange problem. In IJCAI 18, pages 354 360, 2018. [Lonc and Truszczynski, 2018] Z. Lonc and M. Truszczynski. Maximin share allocations on cycles. In IJCAI 18, pages 410 416. AAAI Press, 2018. [Poljak, 1995] S. Poljak. Integer linear programs and local search for max-cut. SIAM Journal of Computing, 24(4):822 839, 1995. [Rahn and Sch afer, 2015] M. Rahn and G. Sch afer. Efﬁcient equilibria in polymatrix coordination games. In Proceedings of the 40th MFCS, pages 529 541, 2015. [Roth and Vate, 1990] A.E. Roth and John H Vande Vate. Random paths to stability in two-sided matching. Econometrica: Journal of the Econometric Society, pages 1475 1480, 1990. [Sch affer and Yannakakis, 1991] A.A. Sch affer and M. Yannakakis. Simple local search problems that are hard to solve. SIAM journal on Computing, 20(1):56 87, 1991. [Shapley and Scarf, 1974] L. S. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1(1):23 37, 1974. [Sun et al., 2015] Z. Sun, H. Hata, T. Todo, and M. Yokoo. Exchange of indivisible objects with asymmetry. In IJCAI 15, pages 97 103, 2015.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)