Individual Rationality in Topological Distance Games is Surprisingly Hard

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00374698" target="_blank" >RIV/68407700:21240/24:00374698 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.24963/ijcai.2024/308" target="_blank" >https://doi.org/10.24963/ijcai.2024/308</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2024/308" target="_blank" >10.24963/ijcai.2024/308</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Individual Rationality in Topological Distance Games is Surprisingly Hard

Popis výsledku v původním jazyce

In the recently introduced topological distance games, strategic agents need to be assigned to a subset of vertices of a topology. In the assignment, the utility of an agent depends on both the agent's inherent utilities for other agents and its distance from them on the topology. We study the computational complexity of finding individually-rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is non-negative. We perform a comprehensive study of the problem's complexity, and we prove that even in very basic cases, deciding whether an individually-rational solution exists is intractable. To reach at least some tractability, one needs to combine multiple restrictions of the input instance, including the number of agents and the topology and the influence of distant agents on the utility.

Název v anglickém jazyce

Individual Rationality in Topological Distance Games is Surprisingly Hard

Popis výsledku anglicky

In the recently introduced topological distance games, strategic agents need to be assigned to a subset of vertices of a topology. In the assignment, the utility of an agent depends on both the agent's inherent utilities for other agents and its distance from them on the topology. We study the computational complexity of finding individually-rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is non-negative. We perform a comprehensive study of the problem's complexity, and we prove that even in very basic cases, deciding whether an individually-rational solution exists is intractable. To reach at least some tractability, one needs to combine multiple restrictions of the input instance, including the number of agents and the topology and the influence of distant agents on the utility.

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)

Projekt

<a href="/cs/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotika a pokročilá průmyslová výroba</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2024

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ů

Název statě ve sborníku

Proceedings of the 33rd International Joint Conference on Artificial Intelligence

ISBN

978-1-956792-04-1

ISSN

1045-0823

e-ISSN

—

Počet stran výsledku

9

Strana od-do

2782-2790

Název nakladatele

International Joint Conferences on Artificial Intelligence Organization

Místo vydání

—

Místo konání akce

Jeju

Datum konání akce

3. 8. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001347142802100