Service Exchange Problem
Authors: Julien Lesca, Taiki Todo
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the service exchange problem where each agent is willing to provide her service in order to receive in exchange the service of someone else. We assume that agent s preference depends both on the service that she receives and the person who receives her service. This framework is an extension of the housing market problem to preferences including a degree of externalities. We investigate the complexity of computing an individually rational and Pareto efficient allocation of services to agents for ordinal preferences, and the complexity of computing an allocation which maximizes either the utility sum or the utility of the least served agent for cardinal preferences. Our contribution is summarized as follows. For finding a PE and IR matching, we provide a poly-time algorithm for a special class of preferences, called set-restricted, and we show that the problem is NP-hard for general preferences. For Sum and Min objectives under cardinal utilities, we showed that maximizing either of them is NP-hard. |
| Researcher Affiliation | Academia | Julien Lesca1, Taiki Todo2 1 Universit e Paris-Dauphine, PSL Research University, CNRS, LAMSADE, 75016 Paris, France 2 Department of Informatics, Kyushu University, Motooka 744, Fukuoka, Japan julien.lesca@dauphine.fr, todo@inf.kyushu-u.ac.jp |
| Pseudocode | Yes | Algorithm 1; Algorithm 2 |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or provide access information for any public dataset. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide details about an experimental setup, hyperparameters, or training settings. |