Seat Arrangement Problems under B-utility and W-utility
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910000232792064 |
|---|---|
| author | Rodríguez, José |
| author_facet | Rodríguez, José |
| contents | In the Seat Arrangement problem the goal is to allocate agents to vertices in a graph such that the resulting arrangement is optimal or fair in some way. Examples include an arrangement that maximises utility or one where no agent envies another. We introduce two new ways of calculating the utility that each agent derives from a given arrangement, one in which agents care only about their most preferred neighbour under a given arrangement, and another in which they only care about their least preferred neighbour. We also present a new restriction on agent's preferences, namely 1-dimensional preferences. We give algorithms, hardness results, and impossibility results for these new types of utilities and agents' preferences. Additionally, we refine previous complexity results, by showing that they hold in more restricted settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09965 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Seat Arrangement Problems under B-utility and W-utility Rodríguez, José Data Structures and Algorithms In the Seat Arrangement problem the goal is to allocate agents to vertices in a graph such that the resulting arrangement is optimal or fair in some way. Examples include an arrangement that maximises utility or one where no agent envies another. We introduce two new ways of calculating the utility that each agent derives from a given arrangement, one in which agents care only about their most preferred neighbour under a given arrangement, and another in which they only care about their least preferred neighbour. We also present a new restriction on agent's preferences, namely 1-dimensional preferences. We give algorithms, hardness results, and impossibility results for these new types of utilities and agents' preferences. Additionally, we refine previous complexity results, by showing that they hold in more restricted settings. |
| title | Seat Arrangement Problems under B-utility and W-utility |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.09965 |