Authors: Agustín Santos Antonio Fernández Anta José A Cuesta Luis López Fernández
Publish Date: 2015/06/10
Volume: 98, Issue: 8, Pages: 777-801
Abstract
Resource allocation is one of the most relevant problems in the area of Mechanism Design for computing systems Devising algorithms capable of providing efficient and fair allocation is the objective of many previous research efforts Usually the mechanisms they propose deal with selfishness by introducing utility transfers or payments Since using payments is undesirable in some contexts a family of mechanisms without payments is proposed in this paper These mechanisms extend the Linking Mechanism of Jackson and Sonnenschein introducing a generic concept of fairness with correlated preferences We prove that these mechanisms have good incentive fairness and efficiency properties To conclude we provide an algorithm based on the mechanisms that could be used in practical computing environmentsThe function psi that optimizes the assignment with equal expected number of resources for two players defines a straight line psi theta 1 = theta 1 + lambda The decision function is an assignment d = g psi theta = mathop mathrmargmax 12psi 1theta 1 theta 2 = mathop mathrmargmax 12theta 1 + lambda theta 2 when the objective is to maximize the utility and d = g psi theta = underset12mathrmargminpsi 1theta 1 theta 2 = underset12mathrmargmintheta 1 + lambda theta 2 when the objective is to minimize
Keywords: