Maximizing Social Welfare in Score-Based Social Distance Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00366224" target="_blank" >RIV/68407700:21240/23:00366224 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4204/EPTCS.379.22" target="_blank" >https://doi.org/10.4204/EPTCS.379.22</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4204/EPTCS.379.22" target="_blank" >10.4204/EPTCS.379.22</a>
Alternative languages
Result language
angličtina
Original language name
Maximizing Social Welfare in Score-Based Social Distance Games
Original language description
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function u_v depends on a generic scoring vector v, which may be customized to match the specifics of each individual application scenario. As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function u_v. We provide more efficient algorithms when dealing with specific choices of u_v or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function u.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 19th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2023
ISBN
—
ISSN
2075-2180
e-ISSN
—
Number of pages
15
Pages from-to
272-286
Publisher name
Open Publishing Association
Place of publication
Sydney
Event location
Oxford
Event date
Jun 28, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001048648700023