Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Hedonic games in the real world: machine learning and theoretical extensions

Georgara Athina

Full record

---

Summary

Successful as it may be in mathematically modelling many real-life problems, cooperative game theory regularly adopts assumptions that cannot possibly stand in most specific everyday scenarios. Given this, in our work in this thesis we focus on Hedonic Games—a class of cooperative games in which players form coalitions based on their individual preferences regarding their potential partners— and tackle certain such assumptions in order to provide a model that fits better the real world. To this end, we make several contributions to Hedonic Games, approaching them from both a theoretical and practical pointof view and extending them in various ways. To begin, a prevalent assumption in the literature is that agents are interested solely onthe composition of their own coalition. In our work we lift this assumption by allowing agents to develop preferences not only on coalitions, but also on coalition structures—i.e., partitions of the agents’ space. Specifically, we motivate and put forward the formal definition of hedonic games in partition function form (PFF-HGs), and extend well-studied hedonic games’ classes to this setting.Another usual assumption in the hedonic games literature is that of complete information. However, in the real world this is almost never the case. To tackle this, we examine the problem of uncertainty regarding hidden preference relations in hedonic games. Specifically, we assume that agents interact within an unknown hedonic game setting, observe a small number of game instances, and attempt to learn the hidden aspects of the game.Then, we employ several learning models, both supervised and unsupervised, to approximately extract the latent preference relations and detect desirable collaboration patterns.In particular, we provide a thorough evaluation of the use of linear regression, regression with basis functions, feed forward neural networks, and the online Latent Dirichlet Allocation (LDA) algorithm for approximately learning the unknown preferences across several classes of hedonic games.Last but not least, we initiate the study of a novel class of cooperative games, the Hedonic Utility Games (HUGs), that takes into consideration both hedonic and utility-related preferences. We formally define HUGs, and show how to extend and apply existing stability solution concepts to them. Then, we put forward a novel solution concept, Individually Rational - Individually Stable (IRIS), which characterizes the stability of coalition structures in HUGs and was developed specifically for such settings. In addition, we propose a natural, “trichotomous” hedonic preferences model; study certain HUGs prop-erties in that model; and exploit it to characterize the feasibility of HUGs coalitions, and to obtain a probability bound for pruning the coalitional space. Pruning can thus be exploited to reduce the computational load of deriving globally acceptable (“kernel-stable”) payoff configurations for IRIS partitions.

Available Files

Services