Distributing tasks in committees

An algorithmic research in a cooperative game theory problem

Master thesis (2020)

Authors

I.D. van Kreveld Applied Sciences

Contributors

M.M. de Weerdt Algorithmics - EEMCS (supervisor 1)
F.A. Oliehoek Interactive Intelligence - EEMCS (supervisor 2)
R.J. Fokkink Applied Probability - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2020 Ivo van Kreveld
Game Theory Cooperative Games Strategyproofness Fair Division Task Distribution Computational Complexity
More Info
expand_more

Published Date

11-06-2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Cooperative game theory studies multi-agent environments where agents are able to make binding agreements. A lot has been written about dividing goods or other positive gains among the agents. This study investigates ways to distribute tasks with a negative utility in a strategyproof way. The intended application is a group of people or companies who can distribute such tasks between them to benefit from each other. The agents value tasks being done, but would rather not do it themselves. They can however, distribute the tasks to mutually benefit. Agents value tasks differently and also have different costs for them. This study investigates the theoretical properties of this problem. Particularly, we look at the Core, which is the set of solutions where agents have no incentive to form coalitions between them and ignore the result of the mechanism. Then, two algorithms are proposed to solve the problem. Finally, experiments are done to predict what results would occur in practice.