On proportional allocation in hedonic games

Martin Hoefer, Wanchote Jiamjitrak*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

6 Sitaatiot (Scopus)


Proportional allocation is an intuitive and widely applied mechanism to allocate divisible resources. We study proportional allocation for profit sharing in coalition formation games. Here each agent has an impact or reputation value, and each coalition represents a joint project that generates a total profit. This profit is divided among the agents involved in the project based on their reputation. We study existence, computational complexity, and social welfare of core-stable states with proportional sharing. Core-stable states always exist and can be computed in time O(m log m), where m is the total number of projects. Moreover, when profits have a natural monotonicity property, there exists a reputation scheme such that the price of anarchy is 1, i.e., every core-stable state is a social optimum. However, these schemes exhibit a strong inequality in reputation of agents and thus imply a lacking fairness condition. Our main results show a tradeoff between reputation imbalance and the price of anarchy. Moreover, we show lower bounds and computational hardness results on the reputation imbalance when prices of anarchy and stability are small.

OtsikkoAlgorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings
ISBN (painettu)9783319666990
DOI - pysyväislinkit
TilaJulkaistu - 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Algorithmic Game Theory - L’Aquila, Italia
Kesto: 12 syysk. 201714 syysk. 2017
Konferenssinumero: 10


NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta10504 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


ConferenceInternational Symposium on Algorithmic Game Theory


Sukella tutkimusaiheisiin 'On proportional allocation in hedonic games'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä