6 papers
Complexity of Strong Popularity in Additively Separable Hedonic Games
Matan Gilboa
In a hedonic game, agents need to be partitioned into coalitions, and have a preference order over partitions. A partition is called strongly popular if it beats any other partitio…
Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
Martin Bullinger, Adam Dunajski, Edith Elkind +1
We study stability in additively separable hedonic games when coalition sizes have to respect fixed size bounds. We consider four classic notions of stability based on single-agent…
Complexity of Unambiguous Problems in
Matan Gilboa, Paul W. Goldberg, Elias Koutsoupias +1
Various practical problems within the class possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing al…
Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
Martin Bullinger, Matan Gilboa
We study coalition formation in the framework of hedonic games. There, a set of agents needs to be partitioned into disjoint coalitions, where agents have a preference order over c…
A Characterization of Complexity in Public Goods Games
Matan Gilboa
We complete the characterization of the computational complexity of equilibrium in public goods games on graphs. In this model, each vertex represents an agent deciding whether to…
Complexity of Public Goods Games on Graphs
Matan Gilboa, Noam Nisan
We study the computational complexity of "public goods games on networks". In this model, each vertex in a graph is an agent that needs to take a binary decision of whether to "pro…