Distributed generalized coverage through utility design

1^st August 2018, 13:00
Dario Paccagnan
ETH Zurich

Abstract

In this talk we show how game theory can be leveraged to provide near
optimal solutions to a class of hard combinatorial problems which we term general
multi-agent maximum coverage problems (GMMC). In a GMMC problem we are
given a ground set of elements, and n collections of subsets of the ground set. Each
element in the ground set is associated with a value. The goal is to select one subset
from each collection so as to maximize the value of covered elements, weighted by
a function that depends on how many times each element is included in the chosen
subsets. In the game-theoretic setting considered, we let each agent select a set
from each collection and reward him with a corresponding utility function. In the
talk we ask the following two questions. Given agents’ utility functions, how do we
characterize the performance of the worst-case Nash equilibrium? Is it possible to
select utility functions so as to maximize such performance metric?
Our main result is that both the problems of characterizing and optimizing the
price of anarchy can be reformulated as tractable linear programs. We specialize
these results to the case of submodular and supermodular problems. For each case
we obtain novel and tight expressions for the price of anarchy. Relative to the class
of submodular welfare functions, we show that optimally-designed utilities yield an
improved performance compared to the state of the art approximation algorithms.