Fair resource allocation in a simple multi-agent setting: Search algorithms and experimental evaluation

Basit Öğe Kaydı
dc.contributor.authorRaftopoulou, P
dc.contributor.authorKoubarakis, M
dc.contributor.authorStergiou, K
dc.contributor.authorTriantafillou, P
dc.date.accessioned2019-10-27T19:21:46Z
dc.date.available2019-10-27T19:21:46Z
dc.date.issued2005
dc.departmentEge Üniversitesien_US
dc.description.abstractWe study the problem of fair resource allocation in a simple cooperative multi-agent setting where we have k agents and a set of n objects to be allocated to those agents. Each object is associated with a weight represented by a positive integer or real number. We would like to allocate all objects to the agents so that each object is allocated to only one agent and the weight is distributed fairly. We adopt the fairness index popularized by the networking community as our measure of fairness, and study centralized algorithms for fair resource allocation. Based on the relationship between our problem and number partitioning, we devise a greedy algorithm for fair resource allocation that runs in polynomial time but is not guaranteed to find the optimal solution, and a complete anytime algorithm that finds the optimal solution but runs in exponential time. Then we study the phase transition behavior of the complete algorithm. Finally, we demonstrate that the greedy algorithm actually performs very well and returns almost perfectly fair allocations.en_US
dc.identifier.doi10.1142/S0218213005002454
dc.identifier.endpage899en_US
dc.identifier.issn0218-2130
dc.identifier.issn1793-6349
dc.identifier.issn0218-2130en_US
dc.identifier.issn1793-6349en_US
dc.identifier.issue6en_US
dc.identifier.startpage887en_US
dc.identifier.urihttps://doi.org/10.1142/S0218213005002454
dc.identifier.urihttps://hdl.handle.net/11454/39019
dc.identifier.volume14en_US
dc.identifier.wosWOS:000234148400001en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.language.isoenen_US
dc.publisherWorld Scientific Publ Co Pte Ltden_US
dc.relation.ispartofInternational Journal on Artificial Intelligence Toolsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectfairnessen_US
dc.subjectresource allocationen_US
dc.subjectnumber partitioningen_US
dc.subjectphase transitionsen_US
dc.titleFair resource allocation in a simple multi-agent setting: Search algorithms and experimental evaluationen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu