Lieu : visioconférence https://meet.jit.si/seminairesSCALP
We introduce resource allocation techniques for a problem where (1) the agents express requests for obtaining item bundles as compact edge-weighted directed acyclic graphs (each path in such graphs is a bundle whose valuation is the sum of the weights of the traversed edges), and (2) the agents do not bid on the exact same items but may bid on conflicting items, that cannot be both assigned. This setting is motivated by a real application: allocating orbit slots to some users in Earth observation constellations, where items are orbit slots and bundles are sets of orbit slots that allow to observe points of interest at some frequency, and where conflicts appear in case of overlapping between two slots on the same satellite. We propose several solution methods for the allocation (utilitarian, exact leximin, approximate leximin, and greedy) and analyze their performance on several scenarios, wrt to global utility, computation time, and fairness of the allocation.