[Date Prev][Date Next][Date Index]

Talk announcement: Fri, Oct 20, 2017 - Francesco Scarcello "Dealing with the Shapley Value: islands of tractability and useful tools"

Dear Colleagues,

the Institute for Information Systems cordially invites you to the following talk:


Dealing with the Shapley Value: islands of tractability and useful tools

Francesco Scarcello University of Calabria

DATE: 	Fri, Oct 20, 2017
TIME: 	9:00 s.t.
VENUE: 	Seminarraum 187/2, Favoritenstrasse 9-11


Coalitional games provide a formal mathematical framework to model problems where the values of agents
are defined in terms of the coalitions they may form. The total available worth is the value of the
coalition with all players, called the grand-coalition, and a crucial problem in these games is finding
a suitable distribution of this total worth to the agents that is ⿿fair⿝ for all of them.

The Shapley value is a solution concept widely used for this purpose. Unfortunately, computing this
value is a #P-hard problem, so that applying this good theoretical notion is often quite difficult in
real-world problems.

The talk focuses on two well-known kinds of coalitional games, namely, the allocation games and the
matching games, looking for islands of tractability, that is, for classes of these games where the
Shapley value can be computed efficiently. Positive results were known only for very trivial cases, and
it was open whether such results could be extended to bounded treewidth instances. The talk shows that
this is actually the case, by providing polynomial-time algorithms that, among other ingredients, use
recent results on counting problems in databases and constraint satisfaction.

The proposed techniques have been implemented and tested on a real-world application of allocation
problems, namely, the Italian research assessment program, known as VQR. For the large university
considered in the experiments, the problem involves thousands of agents and goods (here, researchers
and their research products). The algorithms described in the talk are able to compute the Shapley
value for most of those agents, and to get a good approximation of the Shapley value for all of them.


With kind support of the Vienna Center for Logic and Algorithms (VCLA) and
the Wolfgang Pauli Institut (WPI).