Over the past decades, the understanding of how individuals spontaneously gather together received particular attention leading to the definition of several variants of Coalition Formation Games, including the so-called Hedonic Games. In such games, the individuals (or agents) have to be split into disjoint coalitions and express preferences only on the coalition they belong to, and not on how the others aggregate. Subsequently, the more general class of the Group Activity Selection Problem, where agents’ preferences depend also on the activity they are performing, has been introduced. In both these classes of games, the study of the existence, the computability, and the efficiency of suitable stability solution concepts as well as the elicitation of agents’ preferences through strategyproof mechanisms have been addressed. In this work, we consider both the aforementioned research directions. In particular, we put our attention on classes of games in which agents’ preferences are expressed by a utility function and we evaluate the global agents’ satisfaction in a given outcome by means of the utilitarian social welfare. Moreover, we often compare the social welfare of the considered solutions with the social optimum, that is the maximum achievable value of the social welfare. We first introduce and study a new model in the Hedonic Games setting, called Distance Hedonic Games, and we focus on the computation and the efficiency of Nash stable outcomes, i.e. coalition structures in which no agent can unilaterally improve her gain by deviating to another coalition. We then turn our attention to the design of strategyproof mechanisms for two specific classes of games: namely, Friends and Enemies Games and the Additively Separable Group Activity Selection Problem. In both cases, we measure the performances of the proposed mechanisms by considering their approximation ratio with respect to the social optimum.

Gathering Self-Interested People Together: a Strategic Perspective / Varricchio, Giovanna. - (2021 Apr 27).

Gathering Self-Interested People Together: a Strategic Perspective

VARRICCHIO, GIOVANNA
2021

Abstract

Over the past decades, the understanding of how individuals spontaneously gather together received particular attention leading to the definition of several variants of Coalition Formation Games, including the so-called Hedonic Games. In such games, the individuals (or agents) have to be split into disjoint coalitions and express preferences only on the coalition they belong to, and not on how the others aggregate. Subsequently, the more general class of the Group Activity Selection Problem, where agents’ preferences depend also on the activity they are performing, has been introduced. In both these classes of games, the study of the existence, the computability, and the efficiency of suitable stability solution concepts as well as the elicitation of agents’ preferences through strategyproof mechanisms have been addressed. In this work, we consider both the aforementioned research directions. In particular, we put our attention on classes of games in which agents’ preferences are expressed by a utility function and we evaluate the global agents’ satisfaction in a given outcome by means of the utilitarian social welfare. Moreover, we often compare the social welfare of the considered solutions with the social optimum, that is the maximum achievable value of the social welfare. We first introduce and study a new model in the Hedonic Games setting, called Distance Hedonic Games, and we focus on the computation and the efficiency of Nash stable outcomes, i.e. coalition structures in which no agent can unilaterally improve her gain by deviating to another coalition. We then turn our attention to the design of strategyproof mechanisms for two specific classes of games: namely, Friends and Enemies Games and the Additively Separable Group Activity Selection Problem. In both cases, we measure the performances of the proposed mechanisms by considering their approximation ratio with respect to the social optimum.
Hedonic Games; Group Activity Selection; Nash stability; Mechanism Design; Strategyproofness; Game Theory; SocialChoice
Gathering Self-Interested People Together: a Strategic Perspective / Varricchio, Giovanna. - (2021 Apr 27).
File in questo prodotto:
File Dimensione Formato  
2021_PhDThesis_Varricchio.pdf

accesso aperto

Tipologia: Tesi di dottorato
Licenza: Accesso gratuito
Dimensione 2.43 MB
Formato Adobe PDF
2.43 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/23261
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact