PaperlayerView exact revision on arXiv

Source-linked AI summary

Fractional Hedonic Games

Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, Dominik Peters

arXiv:1705.10116v1cs.GT

TL;DR

The paper studies coalition formation when players value coalitions by average member valuations, addressing existence and computation of stable outcomes. It formalizes fractional hedonic games, develops graph-based existence results and algorithms, and shows that cores can be empty and their non-emptiness hard to decide in general.

  • Problem

    Coalition formation needs a succinct model for preferences based on players’ valuations while determining whether stable outcomes exist and can be computed.

  • Method

    The paper formally defines fractional hedonic games and their graph representations, then analyzes core stability across graph classes and economic settings.

  • Results

    The paper gives conditions and polynomial-time algorithms guaranteeing core-stable outcomes, but proves that simple symmetric games can have empty cores and that deciding non-emptiness is Σp_2-complete.

  • Takeaways & Limitations

    Fractional hedonic games provide a framework for network clustering and for modeling settings such as friends-versus-non-friends groups and Bakers and Millers.

  • Takeaways & Limitations

    Whether every bipartite graph has a non-empty core remains open, and the positive bounded-degree result is not extended beyond degree 2.

Abstract

from arXiv · show

The work we present in this paper initiated the formal study of fractional hedonic games, coalition formation games in which the utility of a player is the average value he ascribes to the members of his coalition. Among other settings, this covers situations in which players only distinguish between friends and non-friends and desire to be in a coalition in which the fraction of friends is maximal. Fractional hedonic games thus not only constitute a natural class of succinctly representable coalition formation games, but also provide an interesting framework for network clustering. We propose a number of conditions under which the core of fractional hedonic games is non-empty and provide algorithms for computing a core stable outcome. By contrast, we show that the core may be empty in other cases, and that it is computationally hard in general to decide non-emptiness of the core.

1 INTRODUCTION

The paper introduces fractional hedonic games, where coalition preferences arise from average valuations, and studies their stability, complexity, and applications to network clustering and economic group formation.

  • 1 INTRODUCTION: Fractional hedonic games assign each player an average valuation of coalition members, extending earlier min, max, and sum-based hedonic models.They can be represented by weighted directed graphs; simple symmetric games use undirected unweighted graphs with valuations 0 or 1.
  • 1 INTRODUCTION: Bakers-and-Millers games always admit a core-stable partition, generalizing to more than two player types that seek to minimize their own type’s fraction.The setting models competing bakers and millers choosing coalitions as economic neighborhoods.
  • 1 INTRODUCTION: The paper also motivates fractional hedonic games through political parties, where players may maximize average agreement within their coalition.Party growth can increase disagreement and encourage split-offs.
  • 1 INTRODUCTION: The paper introduces fractional hedonic games and their graphical representation, including simple symmetric games.These games provide a framework for studying coalition formation and network clustering.
  • 1 INTRODUCTION: The core may be empty even in simple symmetric fractional hedonic games, and deciding core non-emptiness is computationally hard.The paper gives a 40-player example and establishes Σp_2-completeness for deciding non-emptiness, implying that finding a core partition is NP-hard.
  • 1 INTRODUCTION: For several graph classes, the paper identifies non-empty cores and polynomial-time algorithms for computing core-stable partitions.The listed classes include bounded-degree graphs, forests, complete multipartite graphs, suitable bipartite graphs, and graphs with girth at least five.

2 RELATED WORK

The related work connects fractional hedonic games to alternative hedonic-game utilities, population ethics, social cohesion, clustering, and economic applications, while distinguishing the paper’s stability focus.

  • 2 RELATED WORK: Additively separable hedonic games sum player values, whereas fractional hedonic games average them, so the two classes are related but distinct.The paper notes that some games in either class cannot be represented in the other.
  • 2 RELATED WORK: The average-versus-sum distinction recalls average and total utilitarianism in population ethics.The comparison concerns how states with different numbers of individuals are evaluated.
  • 2 RELATED WORK: Olsen’s variant of simple symmetric fractional hedonic games makes every maximal matching core stable, unlike the present setting’s incentive to form large cliques.In that variant, every perfect matching is best possible even when large cliques exist.
  • 2 RELATED WORK: Fractional hedonic games differ from social distance games because they evaluate direct valuations rather than utility inversely proportional to induced-subgraph distance.The paper presents fractional hedonic games as more suitable when benefits from friends of friends are absent or undesirable.
  • 2 RELATED WORK: Feldman et al. independently used hedonic games for graph clustering but did not study core or strict-core stability and considered different game classes.Later work also examined welfare maximization and non-cooperative perspectives on fractional hedonic games.
  • 2 RELATED WORK: Prior work applies fractional hedonic games to socially cohesive groups and jurisdictions, with sampled weighted symmetric games in the latter study all admitting non-empty cores.These applications address group disruption, individual needs, scale efficiencies, and geographic heterogeneity.

3 PRELIMINARIES

The preliminaries define hedonic-game preferences, fractional utilities, graph representations, partitions, and core stability, then illustrate how averaging differs from additive utility.

  • 3 PRELIMINARIES: A hedonic game consists of players with preferences over coalitions containing themselves, while outcomes are partitions into coalitions.A partition is individually rational when every player weakly prefers their assigned coalition to being alone.
  • 3 PRELIMINARIES: A fractional hedonic game assigns each player a valuation to every player and ranks coalitions by the average valuation of their members.These valuation functions provide a compact representation of the game.
  • 3 PRELIMINARIES: Valuations can be normalized so that each player’s self-valuation is zero and represented as weighted directed edges.The edge from i to j has weight v_i(j), player i’s valuation of player j.
  • 3 PRELIMINARIES: Simple games restrict valuations to 0 or 1, while symmetric games require mutual valuations to be equal.Simple symmetric games therefore correspond to undirected graphs whose edges represent value 1.
  • 3 PRELIMINARIES: A coalition blocks a partition when all its members strictly prefer it to their assigned coalitions; partitions without blocking coalitions form the core.The strict core uses weak blocking with at least one strict improvement.
  • 3 PRELIMINARIES: In the Figure 1 example, the unique core-stable partition splits six players into two triples, whereas additive utility makes the grand coalition uniquely stable.The triples give utility 2/3 per player, while the grand coalition gives additive utility 3.

4 NEGATIVE RESULTS

The core of fractional hedonic games may be empty, even for simple symmetric games, and deciding core non-emptiness is computationally difficult. The paper gives a 40-player empty-core example and establishes strong complexity barriers for verification and existence.

  • For the five-cycle C5, every coalition of size three or more admits a blocking coalition of size two.Certain partitions with one singleton and two pairs also admit a weakly blocking coalition.
  • 40 players suffice for a simple symmetric fractional hedonic game with an empty core.The paper presents this construction in Figure 3, while leaving open whether smaller examples exist.
  • The core can be empty even in simple symmetric fractional hedonic games.This resolves an earlier open question about whether such an example exists.
  • The paper’s empty-core constructions also provide gadgets for hardness reductions, while existing ILP-based heuristics work reasonably efficiently on some real-world instances.The reported heuristic handles examples with up to 1,000 players, but this does not remove the general Σp2-completeness barrier.
  • Verifying whether a given partition is in the core is coNP-complete, so core non-emptiness is not known to have a simple NP certificate.A direct check would require ruling out all 2^n possible blocking coalitions.
  • Checking whether a simple symmetric fractional hedonic game has a non-empty core is Σp2-complete.The proof uses a reduction from MAX-MIN CLIQUE and subsidies for players placed in singleton coalitions.

5 POSITIVE RESULTS

The paper establishes core existence for several graph-structured fractional hedonic games, often with constructive or polynomial-time procedures. It also characterizes Bakers and Millers games and identifies boundaries where star-based or degree-based approaches fail.

  • Existence results: Core-stable partitions exist for graphs of degree at most two, forests, complete multipartite graphs, bipartite graphs with perfect matchings, regular bipartite graphs, and graphs of girth at least five.These existence proofs are constructive, and each construction can be performed in polynomial time.
  • Bounded degree: Graphs of degree at most 2 admit a non-empty core, using a greedy partition into coalitions of size at most 3.Their connected components are paths and cycles, so immediate-neighbor coalitions support the construction.
  • Forests: Forests have a non-empty core because a dynamic program matches generations into pairs and produces locally satisfactory stable coalitions.An alternative existence argument uses connected coalitions and the forest communication structure, but does not provide a polynomial-time construction.
  • Bakers and Millers: In Bakers and Millers games, a partition is in the strict core exactly when every coalition has proportional representation from every type.The finest strict-core partition is unique up to renaming same-type players and can be computed in linear time; the grand coalition is also in the strict core.
  • Large girth: For simple symmetric games with girth at least five, a star partition in the core always exists, obtained by maximizing a leximin objective over star packings.However, it is unclear whether an optimizing star packing can be found in polynomial time; local maxima provide a polynomial-time alternative in the appendix.
  • Bipartite graphs: Star packings do not characterize all positive cases: K4,10 has a core-stable grand coalition although no partition into stars lies in the core.More generally, whether every bipartite graph has a non-empty core remains open, while perfect matchings guarantee core non-emptiness.

A.1 Empty core

The paper constructs a simple and symmetric fractional hedonic game whose core is empty, using a 40-player clique-based graph derived from a smaller example. The proof shows that every proposed partition admits a blocking coalition.

  • Empty-core construction: The 40-player construction replaces each original a_i and c_i with a 3-player clique and each b_i with a 2-player clique.Connectivity between the resulting cliques preserves the corresponding edge weights of the smaller construction.
  • Proof structure: The proof first forces every A_l and C_l clique to remain intact within a coalition of any core-stable partition.If a clique is not contained in one coalition, the associated highly connected players or cliques form a blocking coalition.
  • Proof structure: For each l, A_l ∪ C_l is blocking whenever the proposed partition places these cliques in incompatible coalition configurations.The argument repeatedly uses utility thresholds such as 5/6, 4/5, and 2/3 to force structural restrictions.
  • Conclusion: The resulting structural restrictions lead to a contradiction, so no partition can belong to the core.The construction is illustrated by a figure whose cliques have sizes three for A_l and C_l and two for B_l.

A.2 Hardness results

The paper proves that deciding whether a simple and symmetric fractional hedonic game has a non-empty core is computationally intractable. The problem is complete for the second level of the polynomial hierarchy.

  • Hardness results: Core non-emptiness is Σp_2-complete even for simple and symmetric fractional hedonic games.This places the decision problem at the second level of the polynomial hierarchy.
  • Hardness results: The proof uses an involved reduction, while shorter reductions establish NP-hardness without restricting games to the simple symmetric class.The cited alternative proofs do not retain the same structural restriction.

MINMAX-CLIQUE

The MINMAX-CLIQUE problem asks whether every selection of one cell per row contains a sufficiently large clique, and remains hard under highly regular grid restrictions. Taking its complement yields a Σp_2-complete maxmin formulation.

  • Problem definition: MINMAX-CLIQUE takes an undirected graph whose vertices are partitioned into an n-row, c-column grid and asks about every one-cell-per-row selection.The selected cells must contain a clique of the target size k.
  • Hardness restrictions: The problem remains Πp_2-complete when there are two columns, all cells have equal size m, and k=n.These restrictions preserve the problem’s hardness.
  • Hardness restrictions: Hardness also holds for target size k=n+nm after adding a clique of 2nm new vertices connected to all original vertices.The new vertices are distributed so that each cell receives m of them.
  • Complement formulation: Taking the complement produces a Σp_2-complete problem in which one asks whether some cell selection avoids a clique of the target size.The transformation changes the quantifier pattern from minmax to maxmin.

MAXMIN-CLIQUE

The hardness reduction encodes a two-column MAXMIN-CLIQUE instance as a simple and symmetric fractional hedonic game with supported players and gadgets. Core-stable partitions correspond to cell selections whose chosen vertices contain no clique of size k.

  • MAXMIN-CLIQUE: MAXMIN-CLIQUE asks whether one can choose exactly one cell from each row so that the selected vertices contain no clique of size k.The reduction starts from equal-sized cells in an n-row, two-column grid.
  • Reduction construction: The constructed game contains row selectors z_i, supported-player sets X_i,j, original vertices, mates, and clique gadgets C_v.Large subsidies and the parameter M enforce the intended coalition structure.
  • Reduction construction: Edges preserve the original graph and add cliques, cell gadgets, selector connections, and copies of the empty-core construction.No edges are added beyond those specified in the reduction.
  • Forward direction: Any core-stable partition places each selector z_i with one cell and its associated players, thereby determining one chosen cell per row.Supported-player subsidies force the corresponding coalition size and neighborhood composition.
  • Partition structure: Players associated with the chosen cells become singletons, while selected vertices are paired with their mates and clique-support players.These assignments are forced by utility thresholds and the empty-core gadgets.
  • Correctness: If the chosen vertices contained a clique of size k, that clique would block the partition; conversely, a clique-stable selection yields a core-stable partition.The proof concludes that the chosen union contains no clique of size k.
  • Complexity consequence: Core non-emptiness with supported players is Σp_2-complete, and the reduction extends hardness to simple and symmetric games without supported players.The construction also supports coNP-completeness for verifying whether a given partition is core-stable.

Graphs with bounded degree

For simple and symmetric fractional hedonic games represented by graphs of degree at most two, the core is non-empty, and a core-stable partition can be computed in polynomial time.

  • The core is non-empty for simple and symmetric FHGs represented by graphs of degree at most two.
  • The algorithm first repeatedly removes triangles, then removes pairs, leaving unmatched vertices as singleton coalitions.The resulting partition consists of coalitions formed by the removed K3s and K2s, plus unmatched vertices.
  • Vertices in removed triangles cannot block because each already belongs to its most favored coalition.
  • A blocking coalition containing a paired vertex cannot contain two unmatched vertices because that would violate the degree bound.
  • Any remaining candidate coalition has one unmatched vertex and two paired vertices, but one paired member must receive utility below 1/2.The paired member receiving utility 1/2 in the computed partition therefore does not strictly prefer the candidate coalition.

Forests

Forests admit core-stable outcomes, while graphs of girth at least five admit both non-empty cores and polynomial-time core computation through star-packings optimized by leximin welfare.

  • Forests: The core is non-empty for simple and symmetric FHGs represented by undirected forests.
  • Forests: For a tree, the construction roots the tree, organizes vertices into breadth-first layers, and builds the partition from the lowermost layers upward.Disconnected forests are handled by applying the tree algorithm separately to each connected component.
  • Forests: The strict-core characterization for Bakers and Millers compares each type’s fraction within every pair of coalitions in the partition.
  • Graphs with large girth: A graph has girth at least five exactly when every pair of distinct vertices has at most one common neighbor.Triangles and four-cycles are precisely the obstructions used in the converse direction.
  • Graphs with large girth: For graphs of girth at least five, the core is non-empty and a core element can be found in polynomial time.
  • Graphs with large girth: Star-packings partition connected components into stars, with vertices outside the packing represented as singleton coalitions; S2 has two centers and no leaves.
  • Graphs with large girth: A star packing maximizing the leximin-ordered utility vector is proved core stable, balancing star sizes and avoiding unnecessary singleton vertices.
Loading 1705.10116v1…