Approximate Tradeoffs on Matroids

We consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents an agent's utility. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then, a natural aim is to find tradeoffs. We investigate tradeoff solutions with guarantees for the agents. The focus is on discrete problems having a matroid structure. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.

Authors

• Laurent Gourvès
• Jérôme Monnot
• Lydia Tlilane

Keywords

No keywords are indexed for this paper.