Merlin de la Haye

Merlin de la Haye, Pascal Lenzner, Farehe Soheil et al.

Hedonic games are fundamental models for investigating the formation of coalitions among a set of strategic agents, where every agent has a certain utility for every possible coalition of agents it can be part of. To avoid the intractability of defining exponentially many utilities for all possible coalitions, many variants with succinct representations of the agents' utility functions have been devised and analyzed, e.g., modified fractional hedonic games by Monaco et al. [JAAMAS 2020]. We extend this by studying a novel succinct variant that is related to modified fractional hedonic games. In our model, each agent has a fixed type-value and an agent's cost for some given coalition is based on the differences between its value and those of the other members of its coalition. This allows to model natural situations like athletes forming training groups with similar performance levels or voters that partition themselves along a political spectrum. In particular, we investigate natural variants where an agent's cost is defined by distance thresholds, or by the maximum or average value difference to the other agents in its coalition. For these settings, we study the existence of stable coalition structures, their properties, and their quality in terms of the price of anarchy and the price of stability. Further, we investigate the impact of limiting the maximum number of coalitions. Despite the simple setting with metric distances on a line, we uncover a rich landscape of models, partially with counter-intuitive behavior. Also, our focus on both swap stability and jump stability allows us to study the influence of fixing the number and the size of the coalitions. Overall, we find that stable coalition structures always exist but that their properties and quality can vary widely.

Morteza Alimi, Merlin de la Haye, Pascal Lenzner et al.

Potential functions are a key tool in theoretical computer science with applications ranging from the runtime analysis of algorithms and data structures, through the analysis of the expected behavior of random processes and search heuristics, to proving the existence of equilibrium states in strategic games. Typically, proofs that employ potential functions are short, elegant, and easy to verify, yet very powerful. Moreover, potential functions are essential ingredients for constructive proofs, in particular in algorithmic game theory. There, a key question is the existence of equilibrium states, but the most powerful theorem in the field -- Nash's theorem -- is unfortunately non-constructive. For many strategic games, potential functions come to the rescue by enabling constructive proofs that sometimes even yield efficient algorithms for finding equilibria. We add to this by providing a novel class of entropy-inspired log-multinomial potential functions for natural game-theoretic settings where rational agents of different types strategically choose actions to maximize their utility. In particular, we consider utility functions that are based on the fraction of same- and other-type agents taking the same action. We demonstrate the versatility of the new potential function class by presenting simple equilibrium existence proofs for two recent game-theoretic models, for which only involved technical proofs were previously known. Even better, the new potential function class yields efficient algorithms for constructing equilibria for much more general models. Thereby, we positively resolve several open problems.