Object Allocation via Swaps along a Social Network
| Autor: | Laurent Gourvès, Anaëlle Wilczynski, Julien Lesca |
|---|---|
| Přispěvatelé: | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Structure (mathematical logic)
Sequence Polynomial Theoretical computer science Social network Computer science business.industry 02 engineering and technology Object (computer science) Simple (abstract algebra) Reachability Social Choice Theory 020204 information systems 0202 electrical engineering electronic engineering information engineering Coordination and cooperation 020201 artificial intelligence & image processing Agent-based and Multi-agent Systems [INFO]Computer Science [cs] business Social choice theory |
| Zdroj: | Proceedings of the the 26th International Joint Conference on Artificial Intelligence (IJCAI’17) 26th International Joint Conference on Artificial Intelligence (IJCAI’17) 26th International Joint Conference on Artificial Intelligence (IJCAI’17), Aug 2017, Melbourne, Australia. pp.213-219, ⟨10.24963/ijcai.2017/31⟩ IJCAI |
| DOI: | 10.24963/ijcai.2017/31⟩ |
| Popis: | International audience; This article deals with object allocation where each agent receives a single item. Starting from an initial endowment, the agents can be better off by exchanging their objects. However, not all trades are likely because some participants are unable to communicate. By considering that the agents are embedded in a social network, we propose to study the allocations emerging from a sequence of simple swaps between pairs of neighbors in the network. This model raises natural questions regarding (i) the reachability of a given assignment, (ii) the ability of an agent to obtain a given object, and (iii) the search of Pareto-efficient allocations. We investigate the complexity of these problems by providing, according to the structure of the social network, polynomial and NP-complete cases. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|