Maximizing Social Welfare in Score-Based Social Distance Games
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Maximizing Social Welfare in Score-Based Social Distance Games
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Maximizing Social Welfare in Score-Based Social Distance Games
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2023
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the 19th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2023
ISBN
—
ISSN
2075-2180
e-ISSN
—
Počet stran výsledku
15
Strana od-do
272-286
Název nakladatele
Open Publishing Association
Místo vydání
Sydney
Místo konání akce
Oxford
Datum konání akce
28. 6. 2023
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
001048648700023