BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260410T025716Z
UID:Seminar-EcCo-580@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20180801T130000
DTEND:20180801T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Dario Paccagnan: Distributed generalized coverage through utility design\n\nIn this talk we show how game theory can be leveraged to provide near\noptimal solutions to a class of hard combinatorial problems which we term general\nmulti-agent maximum coverage problems (GMMC). In a GMMC problem we are\ngiven a ground set of elements, and n collections of subsets of the ground set. Each\nelement in the ground set is associated with a value. The goal is to select one subset\nfrom each collection so as to maximize the value of covered elements, weighted by\na function that depends on how many times each element is included in the chosen\nsubsets. In the game-theoretic setting considered, we let each agent select a set\nfrom each collection and reward him with a corresponding utility function. In the\ntalk we ask the following two questions. Given agents’ utility functions, how do we\ncharacterize the performance of the worst-case Nash equilibrium? Is it possible to\nselect utility functions so as to maximize such performance metric?\nOur main result is that both the problems of characterizing and optimizing the\nprice of anarchy can be reformulated as tractable linear programs. We specialize\nthese results to the case of submodular and supermodular problems. For each case\nwe obtain novel and tight expressions for the price of anarchy. Relative to the class\nof submodular welfare functions, we show that optimally-designed utilities yield an\nimproved performance compared to the state of the art approximation algorithms.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=580
LOCATION:
END:VEVENT
END:VCALENDAR