Efficient algorithms for computing semivalue single point solution concepts of TU cooperative games

Game Theory has gained a lot of importance in recent days due to the several topics to which it can be efficiently applied. In particular, Cooperative Game Theory deals with either an efficient way to allocate utilities among cooperating players, or to describe, as carefully as possible, the relative power of the players. In this last case, players need not to be human beings, as they usually are objects interacting. Thus, for instance, we could be interested in measuring the (relative) power of parties in a Parliament, or in establishing how crucial is a node in a network. In order to do this, semivalues are an important tool. The most famous one is the Shapley Value, and this is due to the fact that it can serve as a general solution of cooperative games, while other semivalues, like, for instance, the Banzhaf semivalue, can be used only to measure power, so their use is limited to the so called simple games. Unfortunately, the definition of semivalues entails exponential computation on the number of players, so the problem of exactly calculating them is hard in the general case. However, in many instances this issue can be tackled, or at least mitigated, by exploiting the structural properties of specific cooperative game classes. In this work I will survey over algorithms of tractable complexity for computing semivalues of some useful game classes. At first I will revise a framework to model a general class of cooperative games, recently introduced in (Tarkowski et al. 2018). In this class, the authors give conditions to check if the semivalues for a game can be obtained polynomially and, when this is true, they provide an algorithm to compute them. Then, I will consider another algorithm, introduced in (T. Matsui and Y. Matsui 2000), to compute semivalues for weighted voting games, a widely employed subclass of simple games. This algorithm is only pseudopolynomial, in the sense that it is polynomial at the condition to put an upper bound on the size of the weights attached to the players. Finally, I will analyze a recent polynomial algorithm to compute the Shapley Value for games defined for Boolean Conjunctive Queries on relational databases. This algorithm was introduced in (Livshits et al. 2020). Studing the algorithm in detail, I will argue by examples that there is a problem in the computation of a subcase. I will explain why, I will propose some possible corrections and provide an improved version which correctly computes all semivalues.

Negli ultimi anni la Teoria dei Giochi ha ottenuto molta rilevanza, dato il gran numero di situazioni in cui può essere applicata efficientemente. In particolare, la Teoria dei Giochi Cooperativi si occupa sia di allocare utilità in modo efficiente tra i giocatori cooperanti, sia di descrivere, nel modo più accurato possibile, il potere relativo dei giocatori. In quest’ultimo caso, non è necessario che i giocatori rappresentino esseri umani, in quanto spesso il problema riguarda oggetti che interagiscono. Quindi, per esempio, potremmo voler misurare il potere (relativo) dei partiti in un Parlamento o stabilire quanto sia cruciale un nodo all’interno di una rete. Per fare questo, i semivalori sono uno strumento importante. Il più famoso di essi è il Valore di Shapley e ciò è dovuto al fatto che può servire come soluzione generale dei giochi cooperativi, mentre altri semivalori, come, per esempio, il semivalore di Banzhaf, possono essere usati solo per misurare il potere dei giocatori, perciò il loro impiego è limitato ai cosidetti giochi semplici. Sfortunatamente, la definizione di semivalore comporta un calcolo esponenziale sul numero di giocatori, quindi, nel caso generale, ottenere tali valori è un problema di complessità intrattabile. Spesso questo problema può essere affrontato, o perlomeno mitigato, sfruttando le proprietà strutturali presenti in specifiche classi di giochi cooperativi. In questo lavoro esaminerò diversi algoritmi di complessità trattabile per il calcolo dei semivalori in alcune utili classi di giochi. Per prima cosa presenterò una cornice teorica usata per rappresentare una classe molto generale di giochi cooperativi, introdotta recentemente in (Tarkowski et al. 2018). In tale classe, gli autori forniscono delle condizioni per controllare se i semivalori per un gioco possono essere calcolati polinomialmente e, se questo è il caso, presentano un algoritmo per ottenerli. Successivamente, considererò un altro algoritmo, introdotto in (T. Matsui and Y. Matsui 2000), per calcolare i semivalori dei giochi che modellano le votazioni pesate, essendo una sottoclasse di giochi semplici ampiamente utilizzata. Questo algoritmo è solo pseudopolinomiale, nel senso che risulta polinomiale una volta stabilito un limite massimo dei pesi associati ai giocatori. Infine, analizzerò un recente algoritmo polinomiale per calcolare il Valore di Shapley nei giochi definiti su Interrogazioni Congiuntive Booleane nelle basi di dati relazionali. Tale algoritmo è stato introdotto in (Livshits et al. 2020). Studiando dettagliatamente l’algoritmo, argomenterò con esempi che esso presenta un problema nel calcolo di un sottocaso. Spiegerò perché, proporrò alcune possibili correzioni e ne fornirò una versione migliorata che calcola correttamente tutti i semivalori.