2026-07-22T10:45:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7832 2024-03-06T10:41:20Z ddc:004 open_access

Profit Sharing and Efficiency in Utility Games Gollapudi, Sreenivas Kollias, Kostas Panigrahi, Debmalya Pliatsika, Venetia Price of anarchy submodular maximization coverage functions We study utility games (Vetta, FOCS 2002) where a set of players join teams to produce social utility, and receive individual utility in the form of payments in return. These games have many natural applications in competitive settings such as labor markets, crowdsourcing, etc. The efficiency of such a game depends on the profit sharing mechanism - the rule that maps utility produced by the players to their individual payments. We study three natural and widely used profit sharing mechanisms - egalitarian or equal sharing, marginal gain or value addition when a player joins, and marginal loss or value depletion when a player leaves. For these settings, we give tight bounds on the price of anarchy, thereby allowing comparison between these popular mechanisms from a (worst case) social welfare perspective. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sreenivas Gollapudi and Kostas Kollias and Debmalya Panigrahi and Venetia Pliatsika 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.43 urn:nbn:de:0030-drops-78329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.43 eng https://creativecommons.org/licenses/by/3.0/legalcode