Distributed Envy Minimization for Resource Allocation

Arnon Netzer, Amnon Meisels

2013

Abstract

The allocation of indivisible resources to multiple agents generates envy among the agents. An Envy Free allocation may not exist in general and one can search for a minimal envy allocation. The present paper proposes a formulation of this problem in a distributed search framework. Distributed Envy Minimization (DEM) - A Branch and Bound based distributed search algorithm for finding the envy minimizing allocation is presented and its correctness is proven. Two improvements to the DEM algorithm are presented - Forward Estimate (DEM-FE) and Forward Bound (DEM-FB). An experimental evaluation of the three algorithms demonstrates the benefit of using the Forward Estimate and Forward Bound techniques.

Paper Citation

in Harvard Style

Netzer A. and Meisels A. (2013). Distributed Envy Minimization for Resource Allocation . In Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8565-38-9, pages 15-24. DOI: 10.5220/0004186700150024

in Bibtex Style

@conference{icaart13,
author={Arnon Netzer and Amnon Meisels},
title={Distributed Envy Minimization for Resource Allocation},
booktitle={Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2013},
pages={15-24},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004186700150024},
isbn={978-989-8565-38-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - Distributed Envy Minimization for Resource Allocation
SN - 978-989-8565-38-9
AU - Netzer A.
AU - Meisels A.
PY - 2013
SP - 15
EP - 24
DO - 10.5220/0004186700150024