On Proportional Allocation in Hedonic Games

Abstract

Proportional allocation is an intuitive and widely applied mechanism to allocate divisible resources. We study proportional allocation for profit sharing in coalition formation games. Here each agent has an impact or reputation value, and each coalition represents a joint project that generates a total profit. This profit is divided among the agents involved in the project based on their reputation. We study existence, computational complexity, and social welfare of core-stable states with proportional sharing.

Core-stable states always exist and can be computed in time $O(m \log m)$, where m is the total number of projects. Moreover, when profits have a natural monotonicity property, there exists a reputation scheme such that the price of anarchy is 1, i.e., every core-stable state is a social optimum. However, these schemes exhibit a strong inequality in reputation of agents and thus imply a lacking fairness condition. Our main results show a tradeoff between reputation imbalance and the price of anarchy. Moreover, we show lower bounds and computational hardness results on the reputation imbalance when prices of anarchy and stability are small.

This work was done while the authors were at Saarland University. Supported by DFG Cluster of Excellence MMCI at Saarland University.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Profit sharing is a central domain in game theory and has attracted a large amount of interest, mostly as cooperative transferable-utility (TU) games. Usually, there are n agents, and a characteristic function specifies the profit for each subset of agents. The goal is to divide the profit of the grand coalition in a fair and stable way. There has been particular interest in TU games resulting from combinatorial optimization problems. For example, in the matching game [20] each agent is a node in an edge-weighted graph, and the profit of a subset of agents is the max-weight matching in the induced subgraph. For these games, there is a large variety of stability and fairness concepts, most prominently variants of the core. In fact, the core of a matching game might be empty, and the (approximate) core enjoys a close connection to the natural integer program of max-weight matching [9].

An underlying assumption is that (deviating) subsets of agents can freely negotiate shares and distribute profit. In many application contexts, however, profit shares are less directly negotiable, e.g., when allocating credit for joint work. For example, in scientific publishing, credit is assigned based on a variety of aspects and rules, such as reputation, visibility, previous achievements, etc. Moreover, collaborative online platforms (recommendation systems, Wikis, etc.) can design and implement centralized rules for credit allocation among the users.

In this paper, we study natural and simple proportional allocation rules to distribute profit or credit among agents that engage in joint projects. Proportional allocation is a central approach in a variety of contexts and has been studied, e.g., for allocating divisible goods in mechanism design [6, 8, 15]. It can be used to express consequences of rich-get-richer-phenomena (also termed Matthew effect), was studied to distribute profits in stable matching [1], or appeared in probabilistic models for allocating scientific credit [16]. Moreover, proportional response dynamics are a successful method to compute market equilibria [4, 22].

We study the properties of the proportional allocation mechanism in matching and coalition formation games. In this scenario, coalitions represent joint projects that agents can engage in. Each project yields a profit value, which is shared among the involved agents in proportion to an agent-specific parameter $r_u$. Intuitively, this parameter specifies the influence of the agent. Depending on the application context, it captures its, e.g., importance, visibility, or reputation. It might result from previous achievements (e.g., by reputation in societies) or be subject to design (e.g., by assignment in collaborative online systems).

Given such a profit sharing scheme, agents strategically choose the projects to engage in. More formally, a given set projects, profit values, and agent reputations constitutes a hedonic coalition formation game [10], where the proportional allocation mechanism yields the agent utilities. Our goal is to shed light on the equilibria of such games, i.e., existence, structure and social welfare of core-stable states. More precisely, we are interested in the structure of reputation values and the resulting prices of anarchy and stability.

Contribution and Overview. In Sect. 2, we observe that in our games, a core-stable state always exists. This is mostly a consequence of earlier work on stable matching [1]. Let k and $k_{\min }$ be the size of the largest and smallest project with non-zero profit in the game, respectively. For equal sharing (all influences the same), prices of anarchy and stability are $\varTheta (k)$. In fact, if profits and influences are misaligned in a worst-case fashion, it is known that prices of anarchy and stability can be unbounded, even for the special case of matching [1].

In Sect. 3, we consider games with a natural monotonicity condition (termed inclusion-monotone), where we find an interesting trade-off between the required difference in influence and price of anarchy. When the ratio of maximum and minimum influence is bounded by $\alpha$, there are reputations such that the price of anarchy is bounded by $\max \{1,k^2/(k-1+\alpha ^{k_{\min }/n})\}$, where $k_{\min }$ is the size of the smallest project with non-zero profit in the game. When $\alpha = (k^2 - k +1)^{n/k_{\min }}$, the price of anarchy drops to – with a suitable assignment of influence, we can eliminate any inefficiency in the game. For environments, in which assigning influence values is possible, we also provide an efficient algorithm that, given an optimum state $S^*$, computes influence values that achieve this bound on the price of anarchy. While finding an optimum solution can be NP-hard, our algorithm can also work with an arbitrary $\rho$-approximative state S, and the price of anarchy bound increases by a factor $\rho$. Note that the natural representation of our games is linear in the number of agents n and the number of projects/coalitions m, since we must specify a possibly arbitrary positive profit value for each possible project. Our algorithm runs in time polynomial in n and m. Consequently, it is strongest if $m=poly(n)$ (which is often the case, e.g., for matching games).

On the downside, when approaching a price of anarchy of 1, the society becomes extremely hierarchical – the maximum difference in influences grow exponentially large. In Sect. 4 we show that for inclusion-monotone games a factor difference of $n-1$ in influences can be required to obtain a price of stability of 1. If the profits of projects in a core-stable optimum should be shared equally, we strengthen this to an exponential lower bound of $(k+1)^{n/k_{\min } - 1}$. Moreover, for games that are not inclusion-monotone, inefficiency of all core-stable states can be unavoidable.

Finally, in Sect. 5 we discuss computational hardness results. For a given optimal state $S^*$ and a given upper bound $\alpha$ on the ratio of influences, it is NP-hard to decide whether we can make $S^*$ stable, even if every project has size $k=2$. Note that this hardness does not stem from computing $S^*$, since $S^*$ is a max-weight matching when $k=2$, which can be computed in polynomial time. We also show lower bounds and hardness results for the case with influence values in $\{1,x\}$ with $x > 1$, where agents have either “low” or “high” influence.

Due to space constraints, further proofs can be found in the appendix of the full version of this paper.

Further Related Work. Computing stability concepts in hedonic coalition formation games is a recent line of research [7, 12, 17,18,19]. Many stability concepts are NP- or PLS-hard to compute. This holds even in the case of additive-separable coalition profits, which can be interpreted by an underlying graph structure with weighted edges, and the profit of a coalition is measured by the total edge weights covered by the coalition [3, 11, 21]. The price of anarchy was studied, e.g., in [5].

Our work is inspired by proportional allocation mechanisms. The model we study was proposed for stable matching in [1] under the name Matthew-effect sharing. We study general hedonic coalition formation games. While the results in [1] bound prices of anarchy and stability for worst-case profit and influence values, our approach here is to study the necessary inherent trade-offs in social welfare in equilibrium and inequality of influence in the population. In this sense, our paper is closely related to [14], who study the trade-offs between social welfare and difference in profit shares. A drawback of [14] is that it allows to design arbitrary profit shares for every coalition and every agent. Thus, it allows a designer an unnatural amount of freedom when assigning credit to stabilize good states. In contrast, our approach with proportional sharing based on influence and reputation represents a more restricted, structured and arguably realistic way of how credit from joint projects might be allocated to agents.

2 Model and Preliminaries

A proportional coalition formation game is a hedonic coalition formation game based on a weighted hypergraph $G=(V,C,w)$. There is a set V of agents (or vertices) and a set of weighted coalitions (or hyperedges) $C \subseteq 2^V$, where $|c| \ge 2$ for every $c \in C$. Let $w : C \rightarrow \mathbb {R}^+$ represent the positive weight or total profit of each coalition $c \in C$. Unless stated otherwise, we use $n=|V|$, $m=|C|$, $k=\max _{c\in C} |c|$ (the maximum size of any coalition in C), and $k_{\min } = \min _{c\in C} |c|$ (the minimum size of any coalition in C).

Each agent $v \in V$ has a reputation $r_v > 0$, which we scale throughout to satisfy $\min _{v \in V} r_v = 1$. When a coalition $c \in C$ is formed, the profit w(c) is shared among the $v \in c$ proportionally to $r_v$. We define a reputation scheme as a vector of reputations for the agents $R = (r_v)_{v \in V}$.

A coalition structure or state $S \subseteq C$ is a collection of pairwise disjoint coalitions c from C, i.e., for each $v \in V$ we have $|\{c \mid c\in S, v \in c\}|\le 1$. For each coalition $c \in S$, the profit of agent $u \in c$ is a proportional share of weight w(c):

$$\begin{aligned} p_u(S) = p_u(c) = \frac{r_u}{\sum _{v \in c} r_v} \cdot w(c) \end{aligned}$$

(1)

Note that $p_{u}(c) > 0$ for all $c \in C$ and $u \in c$ by definition. For every agent $u \in V$ such that S contains no coalition that includes u, we assume $p_u(S) = 0$.

For a coalition structure S, a blocking coalition $c \in C \setminus S$ is a coalition such that, for each $v \in c$, $p_{v}(c) > p_{v}(S)$. Every agent in c gains strictly more profit than he currently obtains in S if they deviate to c instead. In the case of matching and $k=2$, we speak of a blocking pair. A coalition structure S is termed core-stable if there is no blocking coalition in¹ $C \setminus S$.

To assess the quality of reputation schemes, we quantify the social welfare of the resulting core-stable coalition structures. The social welfare of a coalition structure S is . We call the coalition structure $S^*$ with the highest social welfare the optimal coalition structure. We measure the quality of reputation schemes using the prices of anarchy (PoA) and stability (PoS) of core-stable coalition structures. While the core-stable coalition structures depend on reputations, the optimal coalition structures (and hence, optimal social welfare) do not. Consequently, our goal is to measure the quality of reputation schemes based on PoA and PoS. In particular, we strive to design reputations to maximize social welfare of the resulting core-stable coalition structures.

It turns out that we can obtain very small PoA and PoS using a hierarchy of reputations with extremely large differences, which is often undesirable due to reasons of fairness and equality. As a consequence, we try to limit unequal reputations and, in particular, strive to quantify the tension between efficiency and equality. We measure the degree of equality using a parameter as follows. A reputation scheme R is $\alpha$-bounded if $\alpha \ge \frac{\max _{v\in V} r_v}{\min _{v\in V} r_v} = \max _{v \in V} r_v$. Intuitively, a smaller $\alpha$ indicates that reputation is more uniform reputation.

A simple solution to achieve perfect equality is when every agent has the same reputation. This results in equal sharing, and it results in PoA (and PoS) of at most k, where k is the size of the largest coalition. The following result is shown, e.g., in [2, Theorem 2.9, Corollary 8.2]. In the full version of this paper, we include a proof for completeness and discuss an example game.

Proposition 1

The PoA and the PoS in hedonic coalition formation games with equal sharing is exactly k.

Some of our results apply to instances with an additional property. A game $G=(V,C,w)$ is inclusion monotone if for any $c,c' \in C$ with $c' \subsetneq c$, we have $\frac{w(c)}{|c|} > \frac{w(c')}{|c'|}$. Note that, trivially, every instance of matching with $k = 2$ is inclusion monotone.

3 Existence and Computation

Let us first discuss our existence and computational results. We define an improvement step for a coalition structure S by adding a blocking coalition to S while removing all coalitions that intersect with it from S. It can be seen rather directly that every game has a (strong) lexicographical potential function. As a consequence, a core-stable coalition structure exists in every game and for every reputation scheme, and every sequence of improvement steps always converges. By considering coalitions in non-increasing order of $\frac{w(c)}{\sum _{u \in c} r_u}$, it is possible to arrive at a core-stable structure from any initial structure in at most n steps. The proof is a rather direct extension of [1, Theorem 8], and we include it in the full version of this paper for completeness.

Proposition 2

For any game $G=(V,C,w)$ and proportional sharing based on reputation scheme R, there always exists a core-stable coalition structure. Given any initial coalition structure, we need at most O(n) improvement steps to reach a core-stable coalition structure.

Hence, for any game and any reputation scheme we have both existence and convergence, but it might be the case that every core-stable coalition structure has small social welfare or reputations are extremely different. The subsequent algorithm shows how reputation schemes can provide a trade-off between $\alpha$-boundedness and the PoA. For a given inclusion-monotone instance and a parameter $\alpha > 1$, the algorithm provides a reputation scheme that is $\alpha$-bounded and guarantees a PoA of strictly better than k.

When $\alpha = 1$, we have equal sharing, the price of anarchy is at most k (due to Proposition 1) and a greedy procedure computes the O(n) improvement steps to reach a core-stable state (due to Proposition 2). Algorithm 1 generalizes this approach to obtain improved bounds for $\alpha > 1$. It uses a similar structure as a corresponding algorithm in [14]. In each iteration, we choose one coalition to be a part of our solution and assign the reputation to each agent in this coalition, then remove the agents from consideration. Let c be a coalition with the largest ratio of $\frac{w(c)}{|c|-1+x}$, where $x=\alpha ^{k_{\min }/n}$. There are three cases in the $i^{th}$ iteration:

• 1. If c is a part of the optimal coalition structure $S^*$, we call it $s_{i}^{*}$.

• 2. If c is not in $S^*$ and is overlapping with some coalitions in $S^*$, then we consider $c'$ in $S^*$ such that $c'$ has the highest ratio of $\frac{w(c')}{|c'|}$ among all overlapping coalitions. If $c'$ is large enough to stabilize, we will choose $c'$ instead of c in order to make our solution closest to $S^*$ as much as possible. So we call $c'$ as $s_{i}^{*}$.

• 3. If c is not in $S^*$, but c has a high ratio of $\frac{w(c)}{|c|-1+x}$ so that we should stabilize c instead of stabilizing a coalition from the optimal coalition structure, then we choose c to be $s_{i}^{*}$.

Then, we stabilize $s_{i}^{*}$ by assigning the same reputation to each included agent. This reputation increases by the factor of x in the next iteration. Then we remove all the agents in $s_{i}^{*}$ and their incident coalitions from consideration. The algorithm terminates when there is no coalition left to consider.

Theorem 1

For a given inclusion-monotone instance, and given $\alpha > 1$ and any optimal coalition structure $S^*$, Algorithm 1 computes in polynomial time an $\alpha$-bounded reputation scheme R with PoA at most $\max \{1,k^2/(k-1+\alpha ^{k_{\min }/n})\}$ and a core-stable coalition structure S that achieves both bounds.

Proof

We first consider the running time. The algorithm sorts all coalitions by the ratio of $\frac{w(c)}{|c|-1+x}$, which takes $O(m \log m)$ time. Then, in each iteration we only consider one coalition and its overlapping coalitions, which can be done in O(m) time. In total, the running time is bounded by $O(m^2)$. Recall from the discussion in the introduction that the input size is $\varOmega (n + m)$, hence the algorithm runs in polynomial time.

We now show core-stability of S. As the invariant of the algorithm we maintain that coalitions dropped from consideration will never form any blocking coalition. This holds since we assign reputations that increase by a factor of x in every iteration. Consider three cases as in the algorithm,

• 1. In the first case, since c is the coalition that has the maximum ratio of $\frac{w(c)}{|c|-1+x}$, we assign the same reputation to each agent in c, and each agent gets a profit of $\frac{w(c)}{|c|}$. Consider an overlapping coalition $c'$, and let $u \in c' \cap c$. There are two subcases: (1) $c'$ is a proper subset of c. Since the instance is inclusion monotone and we share profit equally in the coalition, we have

  $$\begin{aligned} p_u(c') = \frac{w(c')}{|c'|} < \frac{w(c)}{|c|} = p_u(c). \end{aligned}$$

  (2) There is an agent $v \in c'\setminus c$ who has a reputation $r_v \ge x r_u$. Then the profit $u\in c\cap c'$ gains from $c'$ is

  $$\begin{aligned} p_u(c')\le \frac{w(c')}{|c'|-1+x} \le \frac{w(c)}{|c|-1+x} < \frac{w(c)}{|c|}=p_u(c). \end{aligned}$$

  This shows that every $u\in c\cap c'$ gains more profit by staying with c.

• 2. In the second case, we choose $c'$ that is in $S^*$ instead of c, each agent in $c'$ gains a profit of $\frac{w(c')}{|c'|}$. Consider an overlapping coalition $c''$, and let $u \in c'' \cap c'$. There are two subcases: (1) $c''$ is a proper subset of $c'$. We apply the same argument as in the first subcase of the first case. (2) There is an agent in $v \in c''\setminus c'$ who has a reputation $r_v \ge x r_u$. Then, the profit $u\in c' \cap c''$ gains from $c''$ is

  $$\begin{aligned} p_u(c'')\le \frac{w(c'')}{|c''|-1+x} \le \frac{w(c)}{|c|-1+x} < \frac{w(c')}{|c'|}=p_u(c'). \end{aligned}$$

  This shows that every $u\in c'\cap c''$ gains more profit by staying with c.

• 3. In the third case, we can use the same analysis as in the first case because we choose the coalition that has the maximum ratio of $\frac{w(c)}{|c|-1+x}$.

This concludes that the resulting state S is core-stable.

Now consider any arbitrary core-stable state $S'$ and coalition c added to S in the first round of the algorithm. Then agents u with $r_u = 1$ are exactly the ones in c, so every overlapping $c' \in S'$ is either a subset of c or has at least one $v \in c' \setminus c$ with $r_v \ge xr_u$ and no agent with reputation less than 1. Hence, the strict inequalities above apply to all agents in c and imply that c is blocking.

Now suppose all coalitions added to S by our algorithm up to round i are in $S'$, but c added in round $i+1$ is not. Then the agents with smaller reputation are exactly the ones in the coalitions added in the first i rounds. As such, they are part of S and do not overlap with c. Hence, every overlapping coalition $c' \in S'$ is either a subset of c or has only agents with same or higher reputation and at least one agent with $r_v \ge x r_u$. Therefore, the strict inequalities above apply to all agents in c and imply that c is blocking. By induction, every core-stable state must contain all coalitions of S, and S is the unique core-stable state.

For $\alpha$-boundedness, observe that the minimum reputation in R is always 1. In each iteration, we add one coalition to S with size at least $k_{\min }$, so there are at most $n/k_{\min }$ iterations. As a consequence, the maximum reputation is at most $x^{n/k_{\min }} = \alpha$, i.e., R is $\alpha$-bounded.

Finally, for the PoA, we see that the solution S of Algorithm 1 deviates from $S^*$ only in iterations that apply the third case, when $c \notin S^*$ and $\frac{w(c)}{|c|-1+x} \ge \frac{w(c')}{|c'|}$ for all $c' \in S^*$. c can intersect at most |c| other coalitions $c' \in S^*$, hence

$$\begin{aligned} \text {PoA}\le \frac{|c|\cdot w(c')}{w(c)} \le \frac{|c| \cdot w(c')}{(|c|-1+x)\cdot \frac{w(c')}{|c'|}} = \frac{|c|\cdot |c'|}{|c|-1+x} \le \frac{k^2}{k-1+\alpha ^{k_{\min }/n}}. \end{aligned}$$

This proves the theorem.   $\square$

The algorithm reveals a trade-off between $\alpha$ and PoA. By increasing $\alpha$, the guaranteed PoA decreases and vice-versa. While the algorithm itself runs in polynomial time, it uses $S^*$ as input, which is NP-hard to compute (finding $S^*$ trivially generalizes, e.g., the standard Set-Packing problem). Hence, the above trade-off mostly applies in terms of existence.

Interestingly, the algorithm also yields a trade-off in terms of (overall) efficient computation. Our analysis of the social welfare of the output structure applies w.r.t. to the social welfare of the input structure. Consequently, if Algorithm 1 is given any input structure $S'$, it will output a core-stable coalition structure S with social welfare at least $w(S) \ge w(S') \cdot (k-1+\alpha ^{k_{\min }/n})/k^2$.

Corollary 1

If Algorithm 1 is applied using any coalition structure $S'$ that represents a $\rho$-approximation to the optimal social welfare, it computes an $\alpha$-bounded reputation scheme with PoA at most $\rho \cdot \max \{1,k^2/(k-1+\alpha ^{k_{\min }/n})\}$.

4 Lower Bounds

In this subsection, we will show a number of lower bounds. Algorithm 1 applies to games that are inclusion monotone, and it shows that we can always reduce PoA to 1 if $\alpha$ is chosen large enough. Next, we will show that there are instances that are not inclusion monotone, where for arbitrarily large $\alpha$ we cannot stabilize an optimal coalition structure.

Proposition 3

There are classes of non-inclusion monotone instances such that (1) every reputation scheme yields a PoS of at least $2-\frac{4}{n+2}$; (2) every $\alpha$-bounded reputation scheme yields a PoS of at least $(n-1+\alpha )/(1+\alpha )$.

The previous proposition shows that the trade-off shown in Theorem 1 does not apply in instances that are not inclusion monotone. The next result complements the bound on $\alpha$ in Theorem 1 when PoS is 1.

Proposition 4

There is a class of inclusion-monotone instances where every reputation scheme with PoS of 1 has $\alpha \ge n-1$.

Fig. 1.

An instance that requires $\alpha \ge n-1$ whenever PoS is 1 (in this case, $n=12$)

Proof

Consider an instance of the type depicted in Fig. 1. The instance $G=(V,C,w)$ consists of a clique of size $\frac{n}{2}$ (denoted by $K_{n/2}$). Every coalition/edge c in $K_{n/2}$ has $w(c)=1$. For each agent, we create an additional agent (called “leaf agent”) and include a coalition with a clique agent of weight $\frac{1}{2}+\epsilon$. The optimal social welfare is $\frac{n}{2}(\frac{1}{2}+\epsilon )$, and $S^*$ is composed of exactly the n / 2 coalitions with leaf agents. For PoS 1, we need to maximize the profit of clique agents in $S^*$, since they are the only ones with deviations. Hence, we can w.l.o.g. assign the minimum reputation of $r_u = 1$ to all leaf agents.

Let $r_1, r_2, \cdots ,r_{n/2}$ be the reputations of clique agents. Consider $r_i$ and $r_j$; in order to avoid a blocking coalition with agents i and j, at least one of them must gain at least as much profit as in $S^*$. Assume i is such an agent, then $(\frac{1}{2}+\epsilon )\cdot \frac{r_i}{r_i+1}\ge 1\cdot \frac{r_i}{r_i+r_j}$. For $\epsilon \rightarrow 0$, this implies $r_j \ge r_i+2$. Since an inequality of this form must hold for every pair $\{i,j\}$ of clique agents, we have

$$\begin{aligned} \max _{i,j\in [\frac{n}{2}]}\{r_i-r_j\}\ge 2(n/2 - 1)=n-2. \end{aligned}$$

Since $r_i \ge 1$ for all $i=1,\ldots ,n$, this implies $\alpha = \max _i r_i \ge n-1$.   $\square$

This lower bound for $\alpha$ is linear in n, but if we apply Algorithm 1 with $k = k_{\min } = 2$ and postulate a PoA of 1, then we can only guarantee $\alpha \le 3^{n/2}$. Hence, in general, our results leave significant room for improvement. Note that the output of Algorithm 1 has the property that in some (in fact, the unique) core-stable coalition structure the profits in each coalition are shared equally. For schemes with this property we can show a drastically improved lower bound, which is asymptotically tight for constant k. Hence, to show existence and computation of schemes with smaller inequality, we need substantially different techniques.

A scheme R has equal sharing in stability if there is a core-stable coalition structure S such that for every $c \in S$ we have $r_i = r_j$, for every $i,j \in c$.

Proposition 5

There is a class of inclusion-monotone instances where every scheme R with equal sharing in stability and PoS of 1 requires $\alpha \ge (k+1)^{\frac{n}{k_{\min }}-1}$.

5 Hardness Results

In this section, we consider computational hardness results that complement our upper bounds in Sect. 3. Even in games with $k=2$, in which an optimum coalition structure $S^*$ is a maximum-weight matching that can be computed in polynomial time, there is no efficient algorithm for computing R that makes $S^*$ core-stable and minimizes the inequality $\alpha$.

Theorem 2

Given an optimal coalition structure $S^*$ and given $\alpha \ge 1$, it is $\mathsf{NP}$-hard to decide whether there is an $\alpha$-bounded reputation scheme such that $S^*$ is core-stable. It remains $\mathsf{NP}$-hard even if every coalition has size exactly k, for any $k\ge 2$.

Proof

We will show a reduction from the Graph Coloring problem. First consider the case when $k=2$. For an instance of Graph Coloring given by an unweighted graph $G=(V,E)$ with $V=\{v_1,\cdots ,v_n\}$, we construct a game $G'=(V',E',w)$ as follows. Let $V' = V_1 \cup V_2$ with $V_1 = V$ and $V_2 = \{v_{n+1},\cdots ,v_{2n}\}$, and $E' = E_1 \cup E_2$ with $E_1 = E$ and $E_2=\{\{v_i,v_{n+i}\}\mid i=1,\cdots ,n\}$. We set $w(e)=1$ if $e \in E_1$ and $w(e)=\frac{1}{2}+\epsilon$ if $e \in E_2$, for an arbitrarily small constant $\epsilon > 0$. Hence, $G'$ is similar in spirit to Fig. 1 except we replace the clique by the coloring instance G. The optimal coalition structure $S^* = E_2$.

First assume G is $\ell$-colorable. We show that there is an $(2\ell -1)$-bounded reputation scheme that can stabilize $S^*$ in $G'$. By Proposition 4, any two adjacent vertices in $V_1$ must have a difference in reputations of at least 2, otherwise the edge will be a blocking pair. So, if a vertex has $i^{th}$ color class in G, then assign the corresponding agent a reputation of $2i-1$ in $G'$. Finally, assign reputation 1 to all agents in $V_2$. This reputation scheme makes $S^*$ core-stable, and the proof is identical to the one in Proposition 4.

Now assume there is a $\alpha ^*$-bounded reputation scheme R that makes $S^*$ core-stable. We show that G is $\frac{\alpha ^*+1}{2}$-colorable. First, we convert R as follows:

• 1. Normalize all the reputations to satisfy $\min _i r_i = 1$.

• 2. Change the reputations of all the leaf nodes to be 1.

• 3. For every normalized reputation value, if it is not an odd integer, decrease it down to next lower odd integer.

It is obvious that after these three conversions, the scheme is still $\alpha ^*$-bounded. Let us argue that the conversion also keeps $S^*$ core-stable. Step 1 does not change anything because scaling all reputations does not change any profit shares. After step 2, agents in $V_1$ receive more profit in $S^*$, so $S^*$ remains core-stable. In step 3, any two agents that have a difference in their reputations of at least two, the difference still remains at least two. Thus, $S^*$ remains core-stable.

After the conversion, every agent in $V_1$ has an odd integer as reputation. Now, we just identify each odd integer with a color class. Since $S^*$ is core-stable, adjacent vertices in G must differ in reputation by at least 2, i.e., belong to different color classes. Hence, G is $\frac{\alpha ^*+1}{2}$-colorable. The result follows for $k=2$.

To show that it remains $\mathsf{NP}$-hard even if every coalition in the instance has size exactly k, we reduce the coloring problem on graph G to hypergraph $G'$ as in the previous reduction. Here, however, for each coalition in $G'$ we add $k-2$ more agents that only belong to that coalition. Every coalition has the same weight as in previous case. To stabilize $S^*$, we need $(\frac{1}{2}+\epsilon )\cdot \frac{r_i}{r_i+k-1}\ge 1\cdot \frac{r_i}{r_i+r_j+k-2}$ for every $v_i,v_j \in V_1$. This leads to $r_j \ge r_i+k$ for any $j>i$. So, any two adjacent vertices in V must have the difference in reputations of at least k (instead of 2 as above). Applying the reduction as above, we can stabilize $S^*$ in $G'$ with an $\alpha ^*$-bounded reputation scheme if and only if G is ($\frac{\alpha ^*+k-1}{k}$)-colorable.   $\square$

It shows that even approximating $\alpha ^*$ is extremely hard, since the reduction preserves the well-known approximation hardness of Graph Coloring [13].

Corollary 2

For any constant $\epsilon >0$, $\alpha ^*$ cannot be efficiently approximated within $n^{1-\epsilon }$ unless NP = ZPP.

Let us also examine an interesting special case reputation scheme where we are allowed only to assign “high” and “low” reputations. More formally, let $R \in \{1,x\}^n$ for some $x>1$, where we call such schemes “restricted reputations”. Unfortunately, the next theorem shows that finding a scheme with optimal $\alpha$ remains $\mathsf{NP}$-hard when we are given a bound W on social welfare of a core-stable coalition structure (but not the exact optimum $S^*$). This is a weaker assumption than providing an optimal coalition structure directly as in the previous theorem. However, the result applies even for matching with $k=2$, where existence of a solution with welfare at least W can be decided in polynomial time. Hence, the difficulty does not lie in finding a good coalition structure but it is again inherent to the correct assignment of reputations.

Theorem 3

Given a positive rational number $x>1$ and a bound on social welfare $W > 0$, it is NP-hard to decide whether there exist restricted reputations that results in a core-stable coalition structure S with $w(S) \ge W$. This holds even for instances with $k=2$.

Corollary 3

For both restricted and general reputations, the following problems are NP-hard: (1) Given $W>0$, find the $\alpha$-bounded core-stable coalition structure S with minimum $\alpha$ such that $w(S)\ge W$; and (2) given $\alpha >0$, find the $\alpha$-bounded core-stable coalition structure with maximum social welfare.

For restricted reputations, we might not be able to stabilize the optimal coalition structure. The final result lower bounds the PoS in terms of parameter x.

Proposition 6

For $x>1$, there are classes of instances such that for every restricted reputation scheme $R \in \{1,x\}^n$ (1) the PoS is at least $\frac{4}{x+1}$; and (2) the PoS is at least $2-\frac{4}{x+3}$.