Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCardi, Pierre
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLesca, Julien
dc.date.accessioned2022-02-18T12:42:34Z
dc.date.available2022-02-18T12:42:34Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22668
dc.language.isoenen
dc.subjectFairnessen
dc.subjectComputational Social Choiceen
dc.subjectWorst Case Analysisen
dc.subject.ddc006.3en
dc.titleWorst-case Bounds for Spending a Common Budgeten
dc.typeCommunication / Conférence
dc.description.abstractenWe study the problem of spending a budget that is common to agents. Agents submit demands to a central planner who uses the budget to fund a subset of them. The utility of an agent is the part of the budget spent on her own accepted demands. In a fair solution, the successful demands of each agent would represent a 1/ fraction of the budget. However, this is rarely possible because every demand is indivisible, i.e. either accepted in its entirety or rejected. We are interested in worst-case bounds on the largest proportion of the budget that is dedicated to the least funded agent. Our approach is not to solve the corresponding max min problem for every instance, but to tackle the problem from a higher level. The size of the largest demand compared to the budget and the number of agents, are two parameters that significantly influence how much the worst-off agent gets. We propose worst-case bounds on the best utility of the least funded agent for the class of instances where the number of agents and the most expensive demand are fixed to given values. A characterization of this quantity is provided for 1 and 2 agents. For more than 2 agents, we propose lower and upper bounds that constitute a 14 15-approximation of the optimal value. Every existence result is complemented with a polynomial algorithm that builds a feasible solution satisfying our bounds.en
dc.identifier.citationpages288-296en
dc.relation.ispartoftitleProceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2021)en
dc.relation.ispartofeditorEndriss, Ulle
dc.relation.ispartofeditorNowé, Ann
dc.relation.ispartofeditorDignum, Frank
dc.relation.ispartofeditorLomuscio, Alessio
dc.relation.ispartofpublnameIFAAMASen
dc.subject.ddclabelIntelligence artificielleen
dc.relation.ispartofisbn978-1-4503-8307-3en
dc.relation.conftitle20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2021)en
dc.relation.confdate2021-05
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2022-02-18T09:50:49Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record