Algoritmi per il Calcolo degli Indici di Potere
nei Giochi di Maggioranza Pesata
Eleonora Arcidiacono
673541
Alice Invernizzi
673559
Progetto di Programmazione Avanzata
Politecnico di Milano
Facoltà di Ingegneria
Corso di studi in Ing.Matematica
Anno Accademico 2006-2007
Indice
Introduzione
3
1 Introduzione agli indici di potere
1.1 Classificazione dei giochi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Giochi semplici e giochi di maggioranza pesata . . . . . . . . . . . . . . . . .
1.3 Concetto di soluzione di un gioco cooperativo . . . . . . . . . . . . . . . . . .
4
4
5
5
2 Algoritmi per il calcolo degli indici di potere
2.1 Metodo dell’enumerazione diretta . . . . . . . . . . . . . . . . . . . . .
2.1.1 Commento al codice . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Esempio: Elezioni politiche italiane 2001 e distribuzione del
all’interno della maggioranza . . . . . . . . . . . . . . . . . . .
2.2 Metodo delle funzioni generatrici . . . . . . . . . . . . . . . . . . . . .
2.2.1 Indice di Banzhaf e Coleman . . . . . . . . . . . . . . . . . . .
2.2.2 Indice di Shapley-Shubik . . . . . . . . . . . . . . . . . . . . .
2.2.3 Alcune osservazioni . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 Commento al Codice . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Esempio: Ampliamento della Comunità Europea . . . . . . . . . . . .
2.4 Programmazione dinamica . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 Dummy Player . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Commento al codice . . . . . . . . . . . . . . . . . . . . . . . .
2.4.3 Esempio: Evoluzione del Consiglio dei Ministri dell’UE . . . .
8
8
9
. . . .
. . . .
potere
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
9
11
11
13
14
14
15
18
19
20
21
3 Conclusioni
24
Appendice A
25
Appendice B
31
Appendice C
3.1 Metodo Diretto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Programmazione Dinamica . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Funzioni Generatrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
52
53
54
Bibliografia
57
2
Introduzione
Il seguente elaborato è finalizzato a confrontare e ad implementare algoritmi per il calcolo
degli indici di potere per i giochi di maggioranza pesata. Gli indici di potere permettono di
valutare l’influenza di ogni membro, partecipante al gioco, sull’esito del gioco stesso. Tali
indici forniscono uno strumento essenziale per lo studio a priori, cioè trascurando le effettive
preferenze dei giocatori, del potere di voto e trovano molte applicazioni in campo reale, basti
pensare per esempio allo studio dei sistemi elettorali, votazioni politiche ...
In questa breve introduzione vorremmo illustrare come è stato strutturato il nostro lavoro.
Nel capitolo 1 è presente una breve introduzione alla Teoria dei Giochi e agli indici di potere:
la prima sezione introduce una classificazione di base delle varie tipologie di giochi esistenti;
nella seconda ci si sofferma sull’analisi dei giochi semplici e dei giochi a maggioranza pesata,
che sono le tipologie di cui ci occuperemo per sviluppare un codice numerico; nell’ultima
sezione si introducono i concetti di soluzione per i giochi cooperativi.
Nel secondo capitolo vengono presentati tre possibili algoritmi per l’implementazione degli
indici di potere (Indice di Shapley, Indice di Banzhaf, Indice di Coleman): Metodo dell’enumerazione diretta, Metodo delle funzioni generatrici, Programmazione dinamica. Tutti e
tre gli algoritmi vengono presentati come segue: descrizione ed analisi dell’algoritmo, commento al codice numerico implementato, presentazione ed analisi di un esempio numerico.
Tali esempi sono finalizzati a testare gli algoritmi su casi che riteniamo significativi, nonchè
a fornire una possibile analisi basata sugli indici di potere. I paragrafi sono suddivisi nel
modo seguente: il 2.1 riguarda il Metodo dell’enumerazione diretta; il 2.2 è relativo al Metodo
delle funzioni generatrici; il 2.3 si riferisce alla Programmazione dinamica. L’ultimo capitolo
riporta le conclusioni finali.
In appendice vengono riportati i codici relativi all’implementazione dei tre suddetti algoritmi,
con i relativi commenti.
3
1
Introduzione agli indici di potere
Nelle sezioni seguenti vengono introdotti alcuni concetti essenziali per la comprensione del
lavoro svolto nei successivi paragrafi. Questa breve introduzione non ha la pretesa di essere
esaustiva, ma ha semplicemente lo scopo di introdurre un po’ di notazione e di terminologia propri della Teoria dei Giochi, nonchè alcuni concetti basilari che riteniamo offrano un
background sufficiente per agevolare la lettura dei capitoli successivi.
1.1
Classificazione dei giochi
La soluzione di moltissimi problemi pratici richiede l’analisi di situazioni in cui ci sono due
parti che si oppongono e in cui il risultato di una azione di una delle parti dipende parzialmente
anche dall’azione dell’altra. Per poter analizzare questo tipo di situazioni di conflitto, tipiche,
per esempio, dell’economia, sono state sviluppate particolari tecniche matematiche derivanti
dalla Teoria dei Giochi e il cui scopo è quello di elaborare, secondo linee razionali, le possibili
azioni delle parti avverse.
Secondo la classificazione di Harsanyi (1966) si possono distinguere due classi di giochi:
• Giochi non cooperativi: in cui non sono possibili accordi vincolanti tra i giocatori;
• Giochi cooperativi: in cui sono possibili accordi vincolanti tra i giocatori.
Nel nostro progetto ci occuperemo solo della seconda categoria, i giochi cooperativi, quindi
ci apprestiamo ad analizzarli meglio.
I giochi cooperativi possono essere a loro volta suddivisi in due sottoclassi: giochi a utilità non
trasferibile (NTU) o senza pagamenti laterali e giochi a utilità trasferibile. I giochi di cui ci
siamo occupate appartengono alla seconda sottoclassificazione: ossia esiste un bene traferibile
da un giocatore ad un altro e variazioni unitarie del bene portano a variazione unitarie di
utilità, misurate attraverso una scala comune tra i giocatori. Quando si ha a che fare con
un gioco è importante avere a disposizione una rappresentazione che ne fornisca informazioni
di base (quali ad esempio il numero dei giocatori, le alternative tra cui un giocatore può
scegliere, le informazioni di cui dispone, l’utilità che consegue alla conclusione del gioco per
ogni possibile esito, le strategie possibili, i possibili esiti del gioco). Le rappresentazioni più
comuni di un gioco sono tre: la forma estesa, la forma strategica, la forma caratteristica.
Nella forma estesa le informazioni disponibili sono solitamente rappresentate tramite un albero, detto albero decisionale, ai cui nodi vengono associati i vari giocatori, agli archi le possibili
mosse e alle foglie la vincita di ciascun giocatore. La forma strategica riassume, solitamente
utilizzando tabelle o matrici, informazioni accurate sulle possibili strategie e sui possibili esiti
di ciascun giocatore. La forma caratteristica viene utilizzata unicamente per i giochi cooperativi. Analizziamo quindi quest’ultima possibile rappresentazione dei giochi utilizzando la
notazione appropriata.
L’insieme costituito da tutti i giocatori viene indicato con N ; un sottoinsieme S di N prende
il nome di coalizione. Se S = N si parla di grande coalizione. Da un insieme di N
giocatori si possono formare 2n coalizioni. La forma caratteristica di un gioco ad n giocatori
è rappresentata da una coppia (N, v), dove N rappresenta l’insieme dei giocatori, mentre la
funzione v è definita come:
v : 2n → R
con
4
v(∅) = 0
(1)
Tale funzione è detta funzione caratteristica. La funzione caratteristica v assegna ad ogni
coalizione S ⊆ N il suo guadagno.
1.2
Giochi semplici e giochi di maggioranza pesata
Introduciamo ora una classe particolare di giochi cooperativi: i giochi semplici.
Sia N = {1, ..., n} l’insieme dei giocatori di un gioco cooperativo. Come visto prima, si dice
che tale gioco è espresso in forma caratteristica se ad ogni possibile coalizione S fra membri
di N è associata una vincita v(S). Ogni gioco in forma caratteristica si dice semplice se la
sua funzione caratteristica assume valori nell’insieme {0, 1}, cioè se, per tutte le S ⊂ N , si ha
v(S) = 0 (coalizione perdente) oppure v(S) = 1 (coalizione vincente), con l’assunzione che la
grande coalizione sia sempre vincente, ossia v(N ) = 1
Noi ci occuperemo dei giochi a maggioranza pesata, una particolare classe di giochi semplici,
come è immediato verificare dalla loro definizione. Tali giochi sono adatti a descrivere situazioni di voto, dal momento che i pesi possono rappresentare seggi di partiti politici. Sia
(w1 , ..., wn ) un vettore reale a componenti non negative che chiameremo pesi degli N giocatori.
Per ogni coalizione S indichiamo con
X
w(S) =
wi
(2)
i∈S
il peso della coalizione. Fissiamo un numero reale q, detto quota di maggioranza, tale che
0 < q ≤ w(N )
(3)
Chiamiamo gioco di maggioranza pesata (q; w1 , ..., wn ) il gioco semplice (N, v) la cui funzione
caratteristica vale:
½
1 se w(S) ≥ q
v(S) =
(4)
0 altrimenti
1.3
Concetto di soluzione di un gioco cooperativo
Una delle problematiche principali relative ai giochi cooperativi è la definizione di soluzione,
non è infatti possibile definire in maniera univoca un concetto di soluzione. Tuttavia, esistono
in letteratura svariate proposte in questo senso. In generale una soluzione di questi giochi
è un sottoinsieme di Rn , con opportune caratteristiche. Ricordiamo a tale proposito che è
possibile definire almeno due tipologie di soluzioni: soluzioni di tipo insiemistico e soluzioni
di tipo puntuale. Della prima classe fa parte, per esempio, il nucleo1 che rappresenta uno dei
concetti più importante di soluzione per diverse categorie di giochi cooperativi. Una particolare classe di soluzioni per i giochi semplici, invece, è rappresentata dagli indici di potere.
Gli indici di potere sono utilizzati per determinare il contributo marginale dei singoli giocatori nelle coalizioni, cioè identificano il potere di ciascun giocatore all’interno delle coalizioni
stesse. Un indice di potere è una funzione Ψ che associa ad ogni gioco semplice (N, v) un
vettore Ψ(v) ∈ Rn : Ψ(v) = (Ψ1 (v), ..., Ψn (v)) la cui i -esima componente è interpretata come
una misura dell’influenza che il giocatore i può esercitare sull’esito del gioco.
1
Il nucleo per un gioco (N, v) è definito come: nucleo(v) = {(xi )i∈N :
v(S) ∀S ⊆ N }
5
P
i∈N
xi = v(N )
e
P
i∈N
xi >
Tra gli indici di potere più utilizzati sicuramente bisogna citare l’ indice di BanzhafColeman e l’indice di Shapley.
Occupiamoci ora di introdurre il Valore Shapley per un TU game (gioco ad utilità trasferibile) e di vedere come ricavare l’indice di potere relativo per i giochi semplici. Dato un gioco
(N, v), una famiglia di numeri reali, indiciata sugli elementi di S, cioè (xi )i∈S , rappresenta
una allocazione di payoff tra gli elementi di S. L’idea che si segue per la costruzione del
Valore Shapley è quella di assegnare ad ogni gioco una allocazione, in modo tale da rispettare
alcuni criteri, si segue un approccio di tipo assiomatico. Un primo criterio è la simmetria.
Simmetria significa che se due giocatori si trovano nella stessa identica posizione in un gioco,
allora il Valore Shapley dovrebbe assegnare loro la stessa quantità. Un’altra condizione è
quella di anonimità. Tale proprietà esprime il fatto che quanto viene dato ad un giocatore
non deve dipendere da chi è questo giocatore, ma solo da quanto questo giocatore è in grado
di ottenere da solo e con gli altri. Indichiamo con θ(N ) l’insieme di tutti i giochi (N, v) che
sono definiti su un dato insieme N di giocatori, cioè θ è l’insieme di tutti i TU-game su N .
Chiamiamo valore una funzione Φ definita come segue: Φ : θ(N ) → Rn , dove n = |N |. Vale
a dire, una funzione valore è una regola che, ad ogni gioco, associa un’ allocazione.
Introduciamo alcune definizioni, utili per introdurre la caratterizzazione assiomatica del valore Shapley. Sia σ : N → N una permutazione di N , che ricordiamo è una corrispondenza
biunivoca. Definiamo il contributo marginale di un giocatore i ∈ N . Se S è una coalizione, ed
i 6∈ S, il numero reale v(S ∪ {i}) − v(S) viene detto contributo marginale di i alla coalizione
S. Se si ha che v(S ∪ {i}) − v(S) = v(i) per ogni coalizione S che non contiene i, il giocatore i
viene detto dummy player. Presi, infine, due giochi (N, v) ∈ θ(N ) e (N, w) ∈ θ(N ) definiamo
il gioco somma (N, v + w) ∈ θ(N ) come il gioco tale per cui: (v + w)(S) = v(S) + w(S),
∀S ⊆ N . Siamo ora pronti per introdurre una possibile assiomatizzazione del valore Shapley.
Assioma I (Anonimità): Sia v un gioco e σ : N → N una permutazione.
Allora, Φσ(i) (σv) = Φi (v)
Assioma
II (Efficienza): Per ogni gioco v, Φ(v) è una pre-imputazione,
P
cioè i∈N Φi (v) = v(N )
Assioma III (Dummy player): Se in un gioco v il giocatore i è un dummy player,
allora Φi (v) = v(i)
Assioma IV (Additività): Per ogni gioco v, w si ha: Φi (v + w) = Φi (v) + Φi (w), per
ogni i ∈ N
Theorema 1.1 [Shapley, 1953] Esiste ed è unical’applicazione Φ : θ(N ) → Rn che soddisfa
gli assiomi I, II, III, IV. Tale funzione viene detta Valore Shapley.
Il vettore Φ(v) ∈ Rn sarà detto valore di Shapley del gioco v e può essere calcolato come:
Φi (v) =
1 X σ
mi (v)
n! σ
6
∀i ∈ N
(5)
dove presa una permutazione σ =: N → N definiamo con
mσi (v) = v({σ(1), σ(2), ..., σ(j)}) − v({σ(1), σ(2), ..., σ(j − 1)})
(6)
il contributo marginale di i alla coalizione {σ(1), σ(2), ..., σ(j − 1)} dove j è l’unico elemento
di N per cui i = σ(j). Oppure utilizzando una formula semplificata e più efficiente al crescere
del numero di giocatori coinvolti (dove s è il numero di elementi di S ed n è il numero di
elementi di N ):
Φi (v) =
X
S⊆N,i∈S
(s − 1)!(n − s)!
(v(S) − v(S\{i}))
n!
(7)
Se siamo nell’ambito dei giochi semplici: (v(S) − v(S\{i})) = 1 quando la coalizione S è
vincente e la coalizione (S\{i}) è perdente, negli altri casi il contributo marginale è uguale a
zero. Perciò la formula per il calcolo del valore Shapley diventa:
Φi (v) =
X (s − 1)!(n − s)!
n!
(8)
S∈Ai
dove Ai denota l’insieme di tutte le coalizioni vincenti S che contengono il giocatore i e tali
da rendere le coalizioni S\{i} perdenti. Infine, ricordiamo che la caratterizzazione assiomatica
del valore Shapley, prima introdotta, perde di significato per i giochi semplici, dal momento
che non ha senso per tali giochi richiedere il soddisfacimento dell’assioma di additività.
Si chiama, invece, indice di Banzhaf (1965) il vettore β(v) ∈ Rn la cui componente βi è il
contributo marginale medio del giocatore i rispetto alle possibili coalizioni a cui appartiene,
cioè:
X
1
βi (v) =
(v(S) − v(S\{i}))
(9)
2n−1
S⊆N,S3i
Tutte le coalizioni a cui appartiene il giocatore i sono, in questo caso, considerate equiprobabili. Con notazione analoga a quella adottata in precedenza, per i giochi semplici l’indice
è esprimibile come:
X 1
βi =
(10)
2n−1
S∈Ai
L’indice di Coleman, infine, non è nient’altro che la versione normalizzata dell’indice di Banzhaf ed è esprimibile come il numero di volte in cui un giocatore è cruciale rapportato al
numero totale di casi in cui i giocatori sono cruciali, ovvero è esprimibile come il rapporto
tra il numero di swings del giocatore in esame fratto il numero totale di swings. Da quanto
detto risulta evidente che l’indice di Shapley somma ad uno, per l’assioma di efficenza, mentre
l’indice di Banzhaf2 non necessariamente, dal momento che non si richiede che sia soddisfatta
la proprietà di efficienza3 . Ricordiamo a proposito che gli indici di potere hanno anche un’interpretazione probabilistica cioè esprimono la probabilità che un giocatore ricopra un ruolo
rilevante nel gioco; il fatto stesso di essere una distribuzione di probabilità dà significato alla
condizione di rispettare l’assioma di efficienza.
2
3
L’indice di Coleman che è la sua versione nomalizzate evidentemente si.
Qui per brevità omettiamo la caratterizzazione assiomatica dell’indice di Banzhaf.
7
2
Algoritmi per il calcolo degli indici di potere
Nelle sezioni successive verranno esaminati alcuni algoritmi, presenti in letteratura, per il
calcolo degli indici di potere. Restringiamo la nostra analisi ai giochi di maggioranza pesata,
definiti precedentemente. Questi metodi si basano su approcci differenti ed ognuno di essi
è caratterizzato da alcuni vantaggi e da alcune limitazioni, discussi nei paragrafi seguenti, e
che devono essere considerati per l’applicabilità degli stessi ai casi in esame. Tratteremo nel
dettaglio tecniche per la computazione esatta degli indici di potere, fornendo alcuni esempi
ottenuti sfruttando gli algoritmi implementati.
2.1
Metodo dell’enumerazione diretta
Uno dei metodi più semplici per il calcolo degli indici di potere in un gioco di maggioranza
pesata è quello basato sull’enumerazione diretta. Questo metodo si fonda direttamente sulle
definizioni degli indici, vedi (8)-(10). Illustriamo brevemente come si può operare in questo
caso. Il primo passo consiste nel trovare tutti i sottoinsiemi di ordine k, per k = 1, 2, ...n,
degli n giocatori. Per ogni sottoinsieme si determina il peso, sommando i pesi dei giocatori
che costituiscono la coalizione in esame. Come da definizione, per calcolare l’indice di potere
del giocatore i -esimo è necessario contare il numero di volte in cui il giocatore è determinante
nel far passare una coalizione da vincente a perdente, o meglio valutare il numero di swings.
Fissato il giocatore i -esimo, dopo aver inizializzato gli indici a zero, si effettuano i seguenti
controlli per operare gli aggiornamenti (η rappresenta l’indice di Banzhaf, mentre φ l’indice
di Shapley):
1. Presa un coalizione S con i ∈ S si determina la coalizione S1 = S \ {i};
2. Si calcola il peso di S1 e si verifica che w(S1 ) < q e w(S) = w(S1 ) + wi ≥ q: allora il
giocatore è determinante;
3. Se i controlli precedenti risultano positivi, gli indici vengono aggiornati come segue:
φi = φi +
(n − k)!(k − 1)!
n!
ηi = ηi +
1
2n−1
Questo processo viene ripetuto su tutte le coalizioni S ⊆ N e su tutti i giocatori i = 1, 2, ..., n.
Dal momento che il numero di sottoinsiemi di un insieme di n giocatori è pari a 2n , il tempo
di calcolo per ogni giocatore è esponenziale. La limitazione maggiore per l’applicabilità di tale
tecnica è pertanto dovuta ai costi computazionali che crescono esponenzialmente al crescere
dei giocatori coinvolti. Dal punto di vista del calcolo è evidente, da quanto detto, che tale
procedura non è efficiente; per questo motivo analizzeremo nelle sezioni successive ulteriori
approcci nel tentativo di ridurne i costi. Questo algoritmo, pertanto, è adottabile per giochi
di dimensione ridotta. Questo metodo tuttavia ha un’interpretazione immediata, basata
sulla definizione degli indici, e può essere esteso, con opportune modifiche, anche ai giochi
cooperativi non necessariamente in forma semplice. Ricordiamo infine, come d’altro canto è
evidente da quanto sopra detto, che il metodo fornisce un procedura esatta per il calcolo della
distribuzione del potere.
8
2.1.1
Commento al codice
Commentiamo la struttura del programma Metodo diretto, il cui codice è inserito in appendice.
Sono state implementate due classi, la classe Combinazioni e la sua classe figlia Indice. La
prima classe permette di generare le combinazioni di ordine k su n elementi, utilizzando due
tipologie di metodi: un metodo diretto e un metodo ricorsivo. La procedura diretta (Funzione
Diretto), viene implementata nel seguente modo:
1 Si calcola un combinazione iniziale;
2 Si incrementa la combinazione corrente mantenendo l’ordine lessicografico (Funzione Incremento);
3 Si visualizzano le combinazioni trovate (Funzione Stampacomb).
La seconda procedura, implementata nella Funzione Ricorsivo, si basa su un approccio
ricorsivo. Questo metodo lavora utilizzando la Funzione Combimpl che riceve in ingresso il
numero di giocatori e l’ordine della coalizione desiderata. Si opera in modo ricorsivo, fino
all’esaurimento delle combinazioni di ordine k, e ci si avvale della Funzione Stampacomb per
visualizzare le combinazioni trovate.
La seconda classe implementata, la classe Indice, eredita dalla classe Combinazioni. Tale
classe ha la funzione di calcolare, per ogni giocatore, gli indici parziali di Banzhaf, Shapley e
Coleman. Come spiegato precedentemente, utilizzando la funzione Calcola indice parziale, si
opera nel seguente modo:
• Utilizzando la Funzione Salva, si salvano, in un vettore di struct Coalizioni (contenente
un vettore con la combinazione in esame e il suo peso), le combinazioni correnti, calcolate
tramite la funzione Diretto ridefinita nella classe Indice per consentire il salvataggio dei
dati ;
• Procedendo iterativamente su tutte le coalizioni, si calcolano i pesi tramite la Funzione
Peso coal e si verifica che quest’ultimo sia maggiore della quota di maggioranza;
• Tramite la Funzione Find, si verifica che il giocatore, di cui si sta calcolando l’indice,
appartenga alla coalizione corrente, in modo da poter passare al passo successivo;
• Si calcola la nuova coalizione, privata del giocatore corrente (Funzione Subset), e il
nuovo peso;
• Se la nuova coalizione risulta essere perdente da sola, ma vincente con l’aggiunta del
giocatore corrente, si procede all’aggiornamento degli indici.
Tale procedura viene ripetuta per tutti i giocatori e per tutte le coalizioni. Un volta individuati
gli indici parziali per ogni giocatore, si procede iterativamente per ottenere gli indici totali,
sommando i valori parziali ottenuti, su tutte le coalizioni di ordine k = 1, ...n (Funzione
Totale).
2.1.2
Esempio: Elezioni politiche italiane 2001 e distribuzione del potere all’interno della maggioranza
L’esempio seguente si basa sui risultati delle elezioni politiche avvenute in Italia nel 2001.
Cercheremo di analizzare questi risultati avvalendoci degli Indici di potere calcolati con l’ausilio del programma, da noi sviluppato, basato sull’algoritmo che utilizza il Metodo diretto.
9
Forza Italia
AN
CCD
Lega
CDU
PRI
PSI
Fiamma
% Seggi
46.3
26
11.9
9.6
4.5
0.6
0.6
0.6
N◦ Seggi
82
46
21
17
8
1
1
1
Coleman
26.1364
26.1364
26.1364
10.2273
7.95455
1.13636
1.13636
1.13636
Banzhaf
17.9688
17.9688
17.9688
7.0312
5.4687
0.7812
0.7812
0.7812
Shapley
29.6429
29.6429
29.6429
5.3571
4.6428
0.3571
0.3571
0.3571
Tabella 1: Distribuzione del potere al Senato
Forza Italia
AN
Lega
CCD
CDU
PSI
Indip.
% Seggi
51.5
26.2
8.2
6
4.9
0.5
2.7
N◦ Seggi
189
96
30
22
18
2
10
Coleman
32.3007
32.3007
13.8462
10.7692
4.161538
1.53846
4.161538
Banzhaf
32.8125
32.8125
14.0625
10.9375
4.6875
1.5625
4.6875
Shapley
39.0476
39.0476
9.0476
7.3809
2.3809
0.7142
2.3809
Tabella 2: Distribuzione del potere alla Camera
Nelle tabelle (tab.1, tab.2) sono riportati i risultati ottenuti sia alla Camera che al Senato. Il
numero dei seggi rappresenta il peso attribuito a ciascun partito della maggioranza. La quota
di maggioranza, relativa al Senato, tab.1, è data da 158 seggi. La quota relativa alla Camera
è di 316 seggi, tab.2.
Dalle tabelle risulta evidente che il Polo ha vinto le elezioni: da questa vincita deriva la
creazione della mappa dei poteri, ovvero presidenze, ministeri,... Per quantificare la forza
contrattuale dei vari partiti si possono utilizzare gli Indici di potere. Si può notare, infatti,
che i partiti Forza Italia e Alleanza Nazionale (AN) hanno lo stesso potere sia alla Camera
che al Senato, mentre il CCD, con essi paritetico al Senato, risulta essere molto più debole
alla Camera. Questo fatto può essere spiegato osservando che ciascuno dei tre partiti è
indispensabile per la formazione della maggioranza al Senato (dove, per avere la maggioranza,
sono necessari 158 voti).
Un partito viene detto cruciale per una coalizione se questa è vincente con lui e perdente
senza di lui. Facciamo un esempio con i dati a nostra disposizione: il PRI è cruciale per la
coalizione che forma, al Senato, con Forza Italia, AN, CCD e CDU. Infatti questa coalizione
raggiunge 158 seggi con il PRI, mentre è minoritaria senza.
L’indice di Banzhaf assegna ad ogni partito un potere proporzionale al numero delle coalizioni
per cui risulta essere cruciale. La creazione di una coalizione preelettorale, può portare
ad alcuni partiti svantaggi in termini di seggi, ma vantaggi in termini di realizzazione dei
programmi (aumenta il suo potere). Osservando la tabella riguardante il Senato (tab.1),
notiamo che il potere attribuito dall’Indice di Coleman a Forza Italia (26.1364% ) è poco più
della metà della sua percentuale di seggi nell’ambito della coalizione (46.3%), mentre quello
relativo al CCD è poco più del doppio. I poteri di AN e della Lega variano di poco rispetto
10
alla proporzione dei seggi. Analizziamo la situazione alla Camera: la Lega aumenta di molto
il suo potere (13.8462%) rispetto alla percentuale dei seggi (9.6%). Si osserva che, in questo
caso, l’Indice di Coleman assegna lo stesso potere (32.3007%) a Forza Italia e AN, anche se la
percentuale dei rispettivi seggi era differente. Forza Italia diminuisce il suo potere (32.3007%)
rispetto ai seggi che aveva ottenuto (51.5%), mentre AN aumenta il potere (32.3007% contro
26.2% di seggi). Tutti gli altri partiti hanno un potere assai inferiore.
2.2
Metodo delle funzioni generatrici
In questa sezione introduciamo un’ulteriore tecnica di tipo combinatorio per il calcolo degli
indici di potere basata sul concetto delle funzioni generatrici4 . Iniziamo con l’introdurre
questo metodo per poi analizzare le proprietà, i vantaggi e gli svantaggi di un approccio di
questo tipo. Tratteremo nel seguito separatamente l’algoritmo per il calcolo del valore Shapley
e dell’indice di Banzhaf-Coleman. Premettiamo dunque la definizione di funzione generatrice:
Definizione 2.1 (Funzione generatrice ordinaria) Si definisce funzione generatrice ordinaria (FGO) della successione di numeri reali {ak }k≥0 la funzione f (x):
X
ak xk
(11)
f (x) =
k≥0
dove la variabile x consente di individuare i coefficienti ak corrispondenti a xk in f (x).
2.2.1
Indice di Banzhaf e Coleman
Come visto dalla loro definizione (10) per il calcolo di questi indici è necessario individuare il numero di swings per ogni giocatore e il numero totale di swings. Procediamo come
segue. Calcoliamo il numero di coalizioni, S ⊆ N , di peso w(S), per ogni possibile peso
w = 0, 1, ..., w(N ). Tale numero può essere opportunamente trovato attraverso l’utilizzo della
funzione generatrice cosı̀ definita:
f (x) =
n
Y
(1 + xwj )
(12)
j=1
L’espressione precedente individua un polinomio di grado w(N ) che può essere anche scritto
w(N )
f (x) =
X
aj xj
(13)
j=0
Per i calcoli che ci apprestiamo a compiere sono rilevanti i coefficienti che compaiono nella
(13), mentre la variabile x non ha un vero e proprio significato in questo contesto se non
quello di permettere l’individuazione di tali coeffienti. Gli aj rappresentano infatti il numero
totale di coalizioni che hanno peso uguale a j:
aj = |{S : S ⊆ N, w(S) = j}| j = 0, 1, 2, ..., w(N )
(14)
4
Ricordiamo che questo metodo fu introdotto per la prima volta da Shapley e Mann nel 1962 su suggerimento
di D.G.Cantor.
11
Ovviamente a0 = 1 dal momento che esiste un unico insieme, l’insieme vuoto, che ha peso
nullo (per ipotesi assumiamo dunque che i giocatori abbiamo pesi strettamente positivi).
Analizziamo ora la procedura numerica per il calcolo di tali coefficienti. Utilizzando le funzioni
generatrici notiamo che:
f (x) =
n
Y
wj
w1
(1+ x ) = [1 +x ]
j=1
n
Y
wj
w1
(1 + x ) = [1 + x
w2
+x
+x
w1 +w2
]
j=2
n
Y
(1+ xwj ) = ... (15)
j=3
Il polinomio all’interno delle parentesi allo stadio r -esimo può essere anche scritto nel modo
seguente:
(r)
(r)
(r)
1 + a1 x + a2 x2 + ... + aw(N ) xw(N ) r = 1, 2, ..., n
(16)
Quindi possiamo riscrivere la (15) come segue:
f (x) = [1 +
(1)
a1 x
+ ... +
(1)
aw(N ) xw(N ) ]
n
Y
(1 + xwj )
j=2
(2)
(2)
= [1 + a1 x + ... + aw(N ) xw(N ) ]
n
Y
(1 + xwj )
j=3
...
(n)
(n)
= [1 + a1 x + ... + aw(N ) xw(N ) ]
(17)
Per quanto visto sopra i coefficienti aj possono essere calcolati iterativamente utilizzando
il seguente metodo.
Posto
(0)
(0)
aj = 0 ∀j 6= 0 e a0 = 1
si calcola:
(r)
(r−1)
aj = aj
(r−1)
+ aj−wr
j = wr , ..., sr
sr = w({1, 2, 3, ..., r}) r = 1, ..., n
(18)
(n)
Dopo n iterazioni questo procedimento ci fornisce ∀j i coefficienti aj = aj desiderati.
Ora vediamo come sfruttare opportunamente gli aj per calcolare gli indici di potere. Utilizzando questi coefficienti possiamo, infatti, ottenere il numero di swings per ogni giocatore.
Fissato il giocatore i ∈ N , per ogni j tale che: q − wi ≤ j ≤ q si determina il numero di
coalizioni cj che non contengono il giocatore i e poi si somma su j. Ovvero:
cj = aj − cj−wi
j = 1, 2, ..., v
dove v = w(N ) − wi
(19)
Avendo posto cj = 0 per j < 0. Il numero di swings per il giocatore i è dato da:
ηi =
q−1
X
cj
(20)
j=q−wi
Reiterando questo processo su ogni giocatore i = 1, .., n siamo in grado di determinare il
numero di swings per ogni giocatore e il numero di swings totali. In questo modo è possibile
12
ricavare l’indice di Coleman su tutti i giocatori. Questa procedura ci consente anche di determinare in modo immediata il numero totale di coalizioni vincenti. Noti infatti i coefficienti
aj e la quota q è sufficiente calcolare:
w(N )
ω=
X
aj
(21)
j=q
Per l’indice di Banzhaf, una volta noti il numero di swings dei giocatori, si procede come di
consueto sfruttando la definizione (10). Nella prossima sezione viene illustrato come, con un
procedimento analogo, sia possibile utilizzare questa tecnica anche per calcolare l’indice di
Shapley-Shubik.
2.2.2
Indice di Shapley-Shubik
Per l’indice di Shapley-Shubik possiamo considerare, come proposto da D.G. Cantor, un
funzione generatrice in due variabili x, y. Vediamo come ricavarla. L’indice Shapley può
essere espresso come:
¶
q−1
X k!(n − k − 1)! µ X
X (s − 1)!(n − s)! n−1
i
=
d (j, k)
φi (v) =
n!
n!
S⊂Ai
(22)
j=q−wi
k=0
dove di (j, k) rappresenta il numero di coalizioni a cui appartiene il giocatore i con peso j e
con cardinalità k. Occupiamoci ora di trovare il numero djk che rappresenta il numero di
coalizioni composte da k membri il cui peso totale è j, il motivo sarà chiaro nel seguito. Vale
il seguente risultato:
Proposizione 2.1 [Cantor] Sia [q; w1, w2, ..., wn ] un gioco di maggioranza pesata, la funzione generatrice dei coeffcienti djk è data da:
f (x, y) =
n
Y
(1 + xwj y)
(23)
j=1
che può essere riscritta come:
f (x, y) =
w(N ) n
XX
djk xj y k
(24)
j=0 k=0
Anche in questo caso si utilizza una tecnica iterativa per il calcolo della matrice D = D(n) di
dimensioni (w(N ) + 1) × (n + 1), costituita dai coefficenti djk . La regola di aggiornamento è
la seguente. Posto
(r)
(r)
d00 = 1 e dj0 = 0
∀j 6= 0 ∀r = 1, 2, ..., n
si calcola:
(r)
(r−1)
djk = djk
(r−1)
+ dj−wr ,k−1
∀r = 1, 2, ..., n ∀k = 0, 1, ..., n ∀j = 0, 1, ...w(N )
13
(25)
ponendo, come prima, coefficienti djk con j < 0 o k < 0 pari a 0.
Vediamo ora come da questa matrice sia possibile calcolare l’indice di potere di ciascun giocatore. I coefficenti dijk che compaiono nella (22), si possono ottenere dividendo la (24) per
1 + xwi z. Tali coefficienti vengono calcolati iterativamente come:
dijk = djk − dij−wi ,k−1
(26)
(n)
dove ovviamente djk = djk . Il valore Shapley del giocatore i -esimo si ottiene, infine, come
visto all’inizio, con la seguente formula:
φi =
n−1
X
k=0
2.2.3
q−1
k!(n − k − 1)! X i
djk
n!
∀i = 1, 2, ..., n
(27)
j=q−wi
Alcune osservazioni
Per concludere questa sezione dedicata all’utilizzo delle funzioni generatrici per il calcolo
degli indici di potere, aggiungiamo alcune considerazioni sui costi computazionali richiesti e
sulla conseguente applicabilità di tale procedura. Questo metodo fu utilizzato per la prima
volta da Shapley-Shubik nel 1962. E’ una tecnica esatta per il calcolo degli indici di potere,
come il metodo di enumerazione diretta, ma può essere utilizzata per giochi con un numero
più elevato di giocatori. La complessità temporale di questa tecnica, infatti, è lineare in
n, numero dei giocatori. D’altro canto, la dimensione degli array contenenti gli aj cresce
al crescere della somma dei pesi, fatto che ne limita l’applicabilità a giochi con un sistema
di pesi sensato, di media dimensione. Altro limite di questo algoritmo è la richiesta di un
sistema di pesi e quota interi, come appare evidente dalla procedura esposta nelle sezioni
precedenti. Sottolineiamo inoltre che tale metodo può essere esteso, con le modifiche del caso,
anche a giochi di maggioranza pesata multipli, cioè basati sulla composizione di più giochi di
maggioranza semplice5 .
2.2.4
Commento al Codice
Per implementare l’algoritmo delle funzioni generatrici sono state utilizzate 3 classi: la classe
f generatrice e le due classi figlie i Coleman e i Shapley. La classe f generatrice contiene una
struct con i dati del gioco in esame e una funzione grado per il calcolo del grado massimo
del polinomio generato. Le due classi figlie sono finalizzate al calcolo dei rispettivi indici. La
classe i Coleman è strutturata come segue: per la costruzione dei coefficienti del polinomio si
procede utilizzando la funzione Coefficienti. Quest’ultima funzione tramite l’utilizzo di due
arrays, di cui uno ausiliario, con una procedura iterativa in n (n è il numero dei giocatori)
passi determina i coefficienti tramite la regola di aggiornamento descritta precedentemente.
Vengono poi valutati il numero di swings effettuati da ogni giocatore, tramite la funzione
swing, e il numero totale degli swings. Infine riassemblando le informazioni ottenute con le
funzioni precedenti si determina l’indice tramite la funzione c indice. Tale classe contiene
inoltre una funzione Banzhaf utilizzata per il calcolo dell’indice di Banzhaf.
Per la classe i Shapley si procede in maniera analoga. Tale classe contiene infatti un funzione matrice d per la costruzione della matrice dei coefficienti, una funzione i indice per il
5
A riguardo si può per esempio consultare Algabada, Bilbao, Garcia, Lopez Computing Power Indices in
Weighted Multiple Majority Games, Mathematical Social Science 46, pp.63-80, 2003
14
calcolo vero e proprio dell’indice. La funzione matrice d costruisce iterativamente la matrice
dei coefficienti, tramite l’ausilio di un array bidimensionale ausiliario, con dimensioni pari a
(w(N ) + 1) × (n + 1), mentre matrice d calcola l’indice con le formule viste in precedenza.
2.3
Esempio: Ampliamento della Comunità Europea
L’obiettivo di questo esempio è di calcolare la distrubuzione di potere all’interno del Concilio
dei Ministri dell’ UE a fronte di un suo possibile ampliamento. Utilizzando il metodo delle
funzioni generatrici calcoleremo l’indice di Banzhaf e di Coleman dei paesi partecipanti al concilio, secondo il gioco di maggioranza semplice discusso nel trattato di Nice (Dicembre 2000).
Riporteremo nel seguito i risultati ottenuti tramite il programma f gen in corrispondenza a
due scenari possibili e opposti:
1 Massimo ampliamento dell’ UE: ovvero tutti i candidati vengono ammessi, con il conseguente ampliamento dell’UE a 27 membri. In tal caso si farà riferimento al seguente
gioco di maggioranza semplice: la struttura dei pesi è la seguente
pesi = [29, 29, 29, 29, 27, 27, 14, 13, 12, 12, 12, 12, 12, 10, 10, 10, 10, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 3]
con quota pari a q = 255
2 Nel secondo caso assumeremo che non ci sia alcun tipo di ampliamento. Gli stati membri
sono i 15 già appartenenti all’UE ma il sistema dei pesi viene modificato e il gioco di
maggioranza viene aggiornato con i nuovi pesi e la nuova quota. Nello specifico il gioco
in esame ha la seguente struttura di pesi:
pesi = [29, 29, 29, 29, 27, 13, 12, 12, 12, 10, 10, 7, 7, 7, 4]
con quota pari a q = 169
Dalle tabelle precedenti possiamo notare come coerentemente con l’assioma di simmetria (a
giocatori che hanno lo stesso ruolo, viene attribuito il medesimo potere), giocatori con lo stesso
peso hanno la medesima influenza ai fini del gioco, com’era facilmente osservabile a priori.
Tale assioma ha infatti, per i giochi di maggioranza pesata un’immediata interpretazione.
Possiamo inoltre notare che l’aumento della quota in caso di ampliamento della comunità ( si
passa infatti dal 71.3% al 73.9% dei voti) non permetta più ai quattro membri maggioritari
di bloccare un decisione. Tale incremento non è quindi favorevole nè al Concilio nei ai singoli
membri. In entrambi i sistemi proposti esistono inoltre nazioni che sono sottorappresentate
ed altre sovrarappresentate, come si può osservare dai grafici fig.(1) che riportano in maniera
grafica il contenuto informativo contenuto nelle tabelle tab.(3)-tab.(4). Per esempio, nel
primo scenario, la Spagna è sovrarappresentata con il sistema di pesi prima esposto, mentre la
Germania è sottorappresentata. Si potrebbe pertanto pensare di utilizzare gli indici di potere
per trovare una distribuzione dei voti e una quota che siano il più rappresentativi possibili
(problema inverso o di progettazione del sistema elettorale). Abbiamo infatti mostrato come
in entrambi i casi soltanto alcune nazioni sono correttamente rappresentate, riducendo però
gli errori percentuali commessi nell’attribuzione dei pesi e della quota si garantirebbe a tutti
i cittadini dell’UE di avere medesimo potere di voto.
15
Germania
UK
Francia
Italia
Spagna
Polonia
Romania
Olanda
Grecia
Rep.Ceca
Belgio
Ungheria
Portogallo
Svezia
Bulgaria
Austria
Slovacchia
Danimarca
Finlandia
Irlanda
Lituania
Lettonia
Slovenia
Estonia
Cipro
Lussemburgo
Malta
Quota
Totale Voti
Potere
29
29
29
29
27
27
14
13
12
12
12
12
12
10
10
10
7
7
7
7
7
4
4
4
4
4
3
255
345
Coleman
7.7827
7.7827
7.7827
7.7827
7.4198
7.4198
4.2591
3.9740
3.6843
3.6843
3.6843
3.6843
3.6843
3.0924
3.0924
3.0924
2.1808
2.1808
2.1808
2.1808
2.1808
1.2501
1.2501
1.2501
1.2501
1.2501
0.9421
Banzhaf
1.6344
1.6344
1.6344
1.6344
1.5582
1.5582
0.8944
0.8345
0.7737
0.7737
0.7737
0.7737
0.7737
0.6494
0.6494
0.6494
0.4579
0.4579
0.4579
0.4579
0.4579
0.2625
0.2625
0.2625
0.2625
0.2625
0.1978
%Pop
9.54
8.10
8.09
7.99
6.61
6.55
4.99
4.18
3.42
3.38
3.37
3.35
3.33
3.13
3.02
2.99
2.45
2.43
2.39
2.04
2.03
1.64
1.48
1.27
0.91
0.69
0.65
%Peso
8.41
8.41
8.41
8.41
7.83
7.83
4.06
3.77
3.48
3.48
3.48
3.48
3.48
2.9
2.9
2.9
2.03
2.03
2.03
2.03
2.03
1.16
1.16
1.16
1.16
1.16
0.87
Tabella 3: Indice di Potere con l’aggiunta dei nuovi membri
16
Caso I
Caso II
10
14
9
Spagna
12
8
10
7
Germania
%popolazione
Indice di
Coleman
%popolazione
Indice di
Coleman
Germania
6
5
4
3
8
6
4
2
0
0
2
4
6
%popolazione
8
Coleman
%pop
2
%pop
Coleman
1
Lussemburgo
0
10
0
2
4
6
8
%popolazione
Caso I
12
14
Caso II
10
14
9
indice
%popolazione
%peso
8
%peso
%popolazione
indice
12
10
%popolazione
indice
%peso
7
%popolazione
indice
%peso
10
6
5
4
3
8
6
4
2
2
1
0
0
5
10
15
paesi
20
25
0
30
0
5
10
paesi
Figura 1: Rappresentatività effettiva degli stati membri
17
15
Germania
UK
Francia
Italia
Spagna
Olanda
Grecia
Belgio
Portogallo
Svezia
Austria
Danimarca
Finlandia
Irlanda
Lussemburgo
Quota
Totale Voti
Voti
29
29
29
29
27
13
12
12
12
10
10
7
7
7
4
169
237
Coleman
11.9209
11.9209
11.9209
11.9209
11.1058
5.5439
5.20827
5.20827
5.20827
4.32125
4.32125
3.12257
3.12257
3.12257
2.03177
Banzhaf
6.06995
6.06995
6.06995
6.06995
5.65491
2.82288
2.65198
2.65198
2.65198
2.20032
2.20032
1.58997
1.58997
1.58997
1.03455
Shapley
12.7142
12.7142
12.7142
12.7142
11.2768
5.45427
4.84821
4.84821
4.84821
3.74043
3.74043
2.82745
2.82745
2.82745
1.90421
%Pop
13.97
11.87
11.84
11.7
9.68
6.12
5.00
4.93
4.87
4.59
4.38
3.55
3.5
2.98
1.01
%Peso
12.24
12.24
12.24
12.24
11.39
5.49
5.06
5.06
5.06
4.22
4.22
2.95
2.95
2.95
1.69
Tabella 4: Indice di Potere senza l’aggiunta di nuovi membri
2.4
Programmazione dinamica
Terminiamo questa sezione dedicata agli aspetti di calcolo presentando un’ultima procedura
numerica. In quest’ultima sezione ci occupiamo, infatti, di un ulteriore algoritmo esatto che
può essere utilizzato per il calcolo degli indici di potere, basato su tecniche di programmazione
dinamica. Spendiamo qualche parola per ricordare alcuni concetti di base. La programmazione dinamica consente di risolvere il problema in esame scomponendolo in sottoproblemi e
componendo le soluzioni dei sottoproblemi stessi. Al contrario dei metodi divide et impera,
la scomposizione non genera sottoproblemi risolubili in modo indipendente. La logica che si
segue nella programmazione dinamica è di tipo button up: si parte da problemi piccoli per
trovare le soluzioni dei problemi più grandi. Gli algoritmi che presentiamo in questa sezione,
sia per il calcolo del dummy-player, sia per il calcolo degli indici sono ispirati a questa logica.
Opereremo d’ora in avanti facendo alcune ipotesi. Assumiamo che wi < q ∀i ∈ 1, 2, ..., n,
ovvero che a ciascun giocatore convenga cooperare piuttosto che giocare da solo. Partizioniamo inoltre in maniera opportuna l’insieme N dei giocatori, utilizzando una partizione che
soddisfi le seguenti richieste:
1. sia costituita da sottoinsiemi disgiunti, che, uniti, danno luogo alla grande coalizione;
2. giocatori con il medesimo peso appartengono al medesimo sottoinsieme;
3. i sottoinsiemi sono ordinati con peso decrescente.
Ovvero, in formule, introducendo la notazione che ci sarà utile anche nel seguito:
1. N1 ∪ N2 ∪ ... ∪ Nz = N con Nx ∩ Ny = ∅ ∀x, y
x 6= y
con Ni ⊂ N ∀i = 1, 2, ..., z
2. Presi x, y con 1 ≤ x ≤ y ≤ z si ha che ∀i ∈ Nx , ∀j ∈ Nj , wi > wj
18
3. Preso x con 1 ≤ x ≤ z ∀i ∀j ∈ Nx : wi = wj
Trovata questa partizione, indichiamo con ηx la cardinalità del generico sottoinsieme Nx e con
w̄x il peso dei giocatori appartenenti a Nx . Ora per il calcolo degli indici di potere procediamo
come segue. Per ogni giocatore i, indichiamo con ci (w, t, x) il numero di sottoinsiemi non
contenenti il giocatore i, con peso pari a w, con cardinalità pari a t e a intersezione non nulla
con il sottoinsieme Nx , ovvero:
¯½
¾¯
X
¯
¯
¯
wj = w, |S| = k, S ∩ Nx 6= ∅, S ∩ Nx+1 = ... = S ∩ Nz = ∅ ¯¯
ci (w, k, x) = ¯ S ⊆ N − i :
j∈S
(28)
Effettuando questa ricerca su tutti i sottoinsiemi della partizione, su tutti i sottoinsiemi non
vuoti di ordine inferiore alla grande coalizione e con peso inferiore della quota è possibile
ricavare un definizione alternativa degli indici di potere. Basandoci sulla definizione appena
vista (28), si può dimostrare che gli indici di potere possono essere calcolati come segue:
φi =
n−1
X
k=1
q−1 X
z
X
k!(n − k − 1)!
ci (w, k, x)
n!
w=q−w
i
(29)
x=1
βi = (1/2n−1 )
n−1
X
q−1 X
z
X
ci (w, k, x)
(30)
k=1 w=q−wi x=1
Basandoci sulle def.(29)-def.(30) sopra riportate è possibile calcolare, in tempo pseudopolinomiale, entrambi gli indici simultanenamente per ogni giocatore con peso assegnato. Maggiori
dettagli riguardanti l’algoritmo implementato verranno forniti nella sezione di commento al
codice. Per ora ci limitiamo a notare che la complessità temporale richiesta da questa procedura è limitata superiormente da O(n2 q) e che l’algoritmo si basa come detto su tecniche di
programmazione dinamica.
2.4.1
Dummy Player
La complessità di calcolo della procedura descritta in questa sezione può essere ridotta se si
utilizza un ulteriore accorgimento. Conoscere l’esistenza di eventuali dummy players semplificherebbe il calcolo degli indici. Questi giocatori, infatti, possono essere eliminati dai calcoli,
dal momento che conosciamo già a priori il loro potere. Dalla definizione di dummy player,
sappiamo, infatti, che se il giocatore i -esimo è un dummy player, allora il suo indice di potere
è uguale al valore della sua funzione caratteristica. In particolare, per i giochi di maggioranza
pesata che stiamo considerando, dal momento che nessun giocatore da solo è vincente, il valore degli indici attribuito a giocatori dummy è identicamente nullo, ovvero i giocatori dummy
players sono anche null-players. La procedura descritta nel seguito può essere applicata non
solo all’ultimo metodo presentato, come per altro abbiamo fatto, ma anche ai precedenti.
L’individuazione dei dummy players, per l’algoritmo da noi implementato, si basa sul seguente teorema:
Theorema 2.2 [Dummy − Player] Assumendo di aver ordinato i pesi dei giocatori in
ordine decrescente, il giocatore i-esimo è dummy player se e soltanto se:
αi + wi + wi+1 + ... + wn < q
19
(31)
dove
X
αi = max{
wj :
S ⊆ {1, 2, ..., i − 1}
w(S) < q}
(32)
j∈S
Dal teorema precedente possiamo identificare l’insieme di tutti i dummy players calcolando
la sequenza di valori αi .
Indichiamo con c(x, w) per ogni coppia x, w di interi positivi la seguente quantità:
¯½
¾¯
X
¯
¯
wi = w, S ∩ Nx 6= ∅, S ∩ Nx+1 = ... = S ∩ Nz = ∅ ¯¯
(33)
c(x, w) = ¯¯ S ⊆ N :
i∈S
Si dimostra che un giocatore i ∈ Nx è un dummy player se e soltanto se:
αx + w̄x ηx + ... + w̄z ηz < q
(34)
αx = max{w : 0 ≤ w ≤ q − 1 e ∃y, 1 ≤ y ≤ x − 1 : c(w, y) > 0}
(35)
dove:
Inoltre il numero di coalizioni vincenti può essere calcolato come
w̄x −1
z q+X
X
x=1
c(w, x)
(36)
w=q
L’algoritmo implementato, ispirato a tecniche di programmazione dinamica (si veda la sezione
sucessiva), individua l’esistenza di dummy players e fornisce in output, in caso di esito positivo,
l’indice della partizione da cui i sottoinsiemi possono essere eliminati. O meglio, se fornisce
in uscita, per esempio, un valore y, l’insieme costituito da sottoinsiemi contenenti dummy
players sarà dato da S = Ny+1 ∪ Ny+2 ∪ ... ∪ Nz . Il calcolo degli indici di potere si riduce,
pertanto, allo studio del sottoinsieme N \S. Osserviamo che la complessità temporale di
suddetto algoritmo è limitata da O(nq).
2.4.2
Commento al codice
Nel programma prog dinamica sono state implementate 3 classi: la classe partizione, la
classe dummy player, la classe indice dyn. Vediamo nel dettaglio la struttura generale del
programma e gli aspetti relativi all’implementazione delle tre classi.
Si è seguita, in primo luogo, la seguente prassi:
• Disponendo dell’insieme dei pesi e della quota, si partiziona l’insieme dei giocatori
secondo le regole spiegate precedentemente.
• Si verifica l’esistenza di eventuali dummy-players e si procede di conseguenza alla loro
eliminazione, riducendo il gioco di partenza
• Si calcolano gli indici di potere
Vediamo ora come sono organizzate le tre classi. La prima classe partiziona l’insieme
dei giocatori, secondo i criteri sopra esposti, utilizzando la funzione partition, quest’ultima si avvale della fuzione conta part che individua il numero di partizioni e della funzione
cardinalita subset per il calcolo della cardinalità dei singoli sottoinsiemi e fornisce in uscita la
20
partizione desiderata.
La classe dummy-player ha come obiettivo l’individuazione di eventuali giocatori dummy e
la loro eliminazione dal gioco. La classe è cosı̀ strutturata: esiste una funzione trova dummy
per verificare l’esistenza di giocatori dummy e una funzione delete dummy per la loro eliminazione. La funzione principale trova dummy è basata sull’implementazione di un algoritmo
che opera i seguenti passi:
• Si effettua un ciclo su tutti i sottoinsiemi;
• Si aggiorna la variabile w0 tenendo conto del peso totale del sottoinsieme in esame.
• Si verifica che c(w) si positivo e si itera sulla cardinalità del sottoinsieme.
• Si aggiornano le variabili ausiliarie
• Si calcolano le varibili c∗ , numero di coalizioni minimali vincenti, e αx , secondo le regole
sopra esposte.
• In uscita otteniamo il valore -1 se non esistono dummy-player, oppure l’indice del
sottoinsieme da cui i giocatori sono dummy.
La funzione delete dummy riduce la partizione dei giocatori privandola di eventuali dummyplayers. L’ultima classe permette il calcolo degli indici di potere di un dato giocatore attraverso la funzione index. Tale funzione riceve in ingresso il peso del giocatore e l’indice che si
desidera calcolare. Tale funzione si basa sul seguente algoritmo:
1 Si itera sui sottoinsiemi
2 Si verifica che il giocatore appartenga al sottoinsieme
3 Si cicla sulla cardinalità dei sottoinsiemi
4 Si cicla sul peso dei sottoinsiemi
5 Si aggiornano le variabili ausiliarie
6 Si calcola c(w, x, t) come esposto precedentemente
7 Se sono soddisfatti i criteri di aggiornamento si procede con il calcolo degli indici.
Per dettagli più precisi si faccia riferimento al codice allegato. Tale funzione consente il calcolo
simultaneo degli indici del giocatore in esame. Ogni giocatore inoltre è individuato dal suo
peso: dal momento che giocatori con lo stesso peso hanno lo stesso potere, la distribuzione
del potere avviena in maniera iterativa sui pesi della partizione .
2.4.3
Esempio: Evoluzione del Consiglio dei Ministri dell’UE
In continuazione all’esempio precedente, vogliamo mostrare ora l’evoluzione del sistema di
maggioranza del Concilio dei Ministri dell’ UE dall 1958 al 1995. Facciamo ora un cenno alle
sue caratteristiche essenziali. I pesi sono attribuiti tenendo conto più fattori tra cui il numero
di abitanti dei rispettivi paesi e le decisioni vengono approvate se viene raggiunta una quota
di maggioranza pari solitamente al 71% dei voti. In generale, come possiamo notare dall’evoluzione in tabella, i paesi più popolosi hanno una percentuale di voti relativamente modesta
21
( basti confrontare il Lussemburgo con la Germania), questo a tutela della rappresentatività
dei paesi più piccoli. In compenso per tutelare i paesi più grandi la quota di maggioranza è
abbastanza elevata. Quest’ultimo fatto implica che qualsiasi decisione deve essere approvata
da almeno 2 delle quattro nazioni più grandi (Germani, UK, Francia, Italia). Queste considerazioni sono fatte a priori basandosi sui pesi e sulla popolosità dei vari paesi, senza tener
conto del loro potere. Nelle tabelle seguenti tab.(4) e tab.(5) sono riportati gli indici di potere
degli stati appartenenti alla comunità europea al variare del sistema dei pesi e della quota,
seguendo l’evoluzione effettuata dal 1958 al 1995. Tali risultati sono stati ottenuti tramite il
programma prog din che ci ha permesso di calcolare l’indice di potere dei vari stati oltre ad
eventuali dummy-players. Un’osservazione interessante, messa in luce dal calcolo degli indici.
Possiamo notare come, per esempio, il Lussemburgo passando dal 1958 al 1973 perda il suo
ruolo di Dummy-Player, sebbene riduca il suo peso percentuale. Infatti mentre nel 1958 era
un giocatore Dummy-Player con un peso percentuale pari al 5.88, nel nuovo sistema di pesi
perde tale posizione sebbene il suo peso percentuale si sia ridotto a 3.44. Questo risultato
permette di mettere in evidenza un difetto nell’assegnazione dei pesi nel Consiglio dell’UE
del 1958.
Germania
UK
Francia
Italia
Spagna
Olanda
Grecia
Belgio
Portogallo
Svezia
Austria
Danimarca
Finlandia
Irlanda
Lussemburgo
Quota
1958-1972
Peso-Banzhaf
4 31.25
-4 31.25
4 31.25
-2 18.75
-2 18.75
------10
12
1973-1980
Peso-Banzhaf
10 20.7031
10 20.7031
10 20.7031
10 20.7031
-5 11.3281
-5 11.3281
---3 8.2031
-3 8.2031
2 1.9531
41
1981-1985
Peso-Banzhaf
10 24.6094
10 24.6094
10 24.6094
10 24.6094
-5 12.1094
5 12.1094
5 12.1094
5 12.1094
--3 6.05469
-3 6.05469
2 6.05469
45
1986-1994
Peso-Banzhaf
10 13.9648
10 13.9648
10 13.9648
10 13.9648
8 11.8164
5 7.2265
5 7.2265
5 7.2265
5 7.2265
--3 4.9804
-3 4.9804
2 1.9531
54
Tabella 5: Evoluzione del gioco di maggioranza-Indice di Banzhaf
22
1995
Peso-Banzhaf
10 11.2854
10 11.2854
10 11.2854
10 11.2854
8 9.3444
5 5.9387
5 5.9387
5 5.9387
5 5.9387
4 4.84
4 4.84
3 3.6315
3 3.6315
3 3.6315
2 2.2888
62
Germania
UK
Francia
Italia
Spagna
Olanda
Grecia
Belgio
Portogallo
Svezia
Austria
Danimarca
Finlandia
Irlanda
Lussemburgo
Quota
1958-1972
Peso-Coleman
4 23.8095
-4 23.8095
4 23.8095
-2 14.2857
-2 14.2857
------10
12
1973-1980
Peso-Coleman
10 16.7192
10 16.7192
10 16.7192
10 16.7192
-5 9.14826
-5 9.14826
---3 6.62461
-3 6.62461
2 1.57729
41
1981-1985
Peso-Coleman
10 14.9112
10 14.9112
10 14.9112
10 14.9112
-5 7.33728
5 7.33728
5 7.33728
5 7.33728
--3 3.66864
-3 3.66864
2 3.66864
45
1986-1994
Peso-Coleman
10 12.8713
10 12.8713
10 12.8713
10 12.8713
8 10.8911
5 6.66067
5 6.66067
5 6.66067
5 6.66067
--3 4.59046
-3 4.59046
2 1.80018
54
1995
Peso-Coleman
10 11.1621
10 11.1621
10 11.1621
10 11.1621
8 9.24238
5 5.87383
5 5.87383
5 5.87383
5 5.87383
4 4.7872
4 4.7872
3 3.59191
3 3.59191
3 3.59191
2 2.26381
62
Tabella 6: Evoluzione del gioco di maggioranza-Indice di Coleman
Germania
UK
Francia
Italia
Spagna
Olanda
Grecia
Belgio
Portogallo
Svezia
Austria
Danimarca
Finlandia
Irlanda
Lussemburgo
Quota
1958-1972
Peso-Shapley
4 23.33
-4 23.33
4 23.33
-2 15
-2 15
------10
12
1973-1980
Peso-Shapley
10 17.8571
10 17.8571
10 17.8571
10 17.8571
-5 8.09524
-5 8.09524
---3 5.71429
-3 5.71429
2 0.952381
41
1981-1985
Peso-Shapley
10 15.5195
10 15.5195
10 15.5195
10 15.5195
-5 7.18615
5 7.18615
5 7.18615
5 7.18615
--3 3.05916
-3 3.05916
2 3.05916
45
1986-1994
Peso-Shapley
10 13.4199
10 13.4199
10 13.4199
10 13.4199
8 11.1255
5 6.37446
5 6.37446
5 6.37446
5 6.37446
--3 4.25685
-3 4.25685
2 1.18326
54
Tabella 7: Evoluzione del gioco di maggioranza-Indice di Shapley
23
1995
Peso-Shapley
10 11.6667
10 11.6667
10 11.6667
10 11.6667
8 9.54601
5 5.51754
5 5.51754
5 5.51754
5 5.51754
4 4.53602
4 4.53602
3 3.52536
3 3.52536
3 3.52536
2 2.06904
62
3
Conclusioni
Nei paragrafi precedenti sono state introdotte alcune tecniche per il calcolo degli indici di
potere. In questa breve sezione conclusiva vorremmo fare alcune considerazioni circa l’applicabilità dei concetti sopra esposti e introdurre alcuni spunti per un possibile ampliamento
futuro. In primo luogo osserviamo che ci siamo limitate ad applicare tecniche esatte per la
computazione degli indici di potere, che restringe l’applicabilità di tali algoritmi a problemi
ridotti, ma comunque già abbastanza significativi. In realtà in letteratura esistono esempi e
proposte di algoritmi approssimati per il calcolo di tali indici. I primi contributi a riguardo
sono dovuti a Shapley-Mann (1960) che applicarono simulazioni Monte Carlo per il calcolo
della distribuzione di potere nel gioco delle elezioni presidenziali americane. Tecniche adeguate sono state poi sviluppate per i cosidetti giochi oceanici, cioè con un numero di giocatori
infinito. Gli indici di potere, inoltre, potrebbero essere utilizzati adeguatamente per risolvere
il cosidetto problema inverso, ovvero data la distribuzione di potere calcolare opportunamente
il sistema di pesi e la quota che la determina. Una possibile applicazione di tale problema riguarda, per esempio, la determinazione di un sistema elettorale ottimale (si vedano a riguardo
le considerazioni fatte a suo tempo nell’esempio sull’UE circa la rappresentatività degli stati
membri).
Un’ultima osservazione: abbiamo visto come gli indici di potere si prestino bene ad applicazioni di tipo politico. Sebbene gli indici di potere, che abbiamo presentato nelle sezioni
precedenti, abbiano un loro importanza per problematiche di questo tipo, un’analisi basata
esclusivamente sul loro utilizzo potrebbe risultare poco realistica. Spieghiamo meglio questo
concetto. Se per esempio i giocatori fossero partiti politici, anche molto distanti ideologicamente tra di loro, gli indici di Banzhaf e Shapley non sarebbero in grado di cogliere propensioni
e avversioni tra i giocatori-partiti. Se ci basassimo solamente su tali indici si avrebbero delle
indicazioni poco precise, o meglio, come detto prima, poco realistiche sulla distribuzione effettiva del potere. A riguardo ricordiamo solamente che sono stati introdotti indici alternativi
che tengono conto delle affinità tra i diversi giocatori, tramite per esempio una distribuzione
di probabilità sulle coalizioni, e che risultati che abbiamo ottenuto in precedenza, potrebbero
essere rivisti alla luce di queste osservazioni.
24
Appendice A
Nel seguito viene riportato il codice relativo all’header file Indici.hpp in cui sono riportate le
dichiarazioni delle classi, delle funzioni e delle variabili globali utilizzate.
#ifndef LIBRERIAINDICE_HH
#define LIBRERIAINDICE_HH
using namespace std;
namespace gioco{
//Definizione di alcune strutture
//Struttura con la definizione di una coalizione
struct coalizioni{
int *v; //insieme dei giocatori
int potere; // peso della coalizione
};
//Struttura con la definizione del gioco
struct gioco_maggioranza{
int quota; // quota da raggiungere per essere vincenti
int *pesi; // pesi dei giocatori
};
//Struttura contenente le caratteristiche dei sottoinsiemi
struct subset{
int peso;
int card;
}; }
typedef long long int64;
//Dichiarazioni delle funzioni
//Funzione per il calcolo del fattoriale
int64 fattoriale(int);
//Funzione per il calcolo del coefficiente binomiale
inline int64 binomiale(int,int);
namespace rielabora_dati{
//Calcolo dell’indice per il metodo di Enumerazione Diretta
void totale(int,int*,int);
//Funzione ausiliaria per il calcolo dell’indice (metodo enumerazione diretta)
void ripeti(int*, int ,int ,int ,int );
//Funzione per l’aggiornamento dei pesi e dei giocatori
25
//viene utilizzata per il calcolo degli indici in presenza di dummy-player
int* nuovi_pesi(int&,int*,gioco::subset*,int&,int,int);
//Funzione per il calcolo degli indici per il metodo di programmazione dinamica
void compute_index(int,int,int*,int,gioco::subset*,int);
//Funzione per l’inserimento dei dati del gioco
int* dati(int&,int&,int);
//Funzione per il salvataggio dei dati
void salva_dati(int*,double*,int,int); }
//Dichiarazione di variabili globali
//Variabile globale contenente l’indice(metodo enumerazione diretta)
extern double* ind;
//Numero di swing totali
extern int swing_tot;
//Variabile globale contenente il numero di coalizioni vincenti
extern double omega1;
//Dichiarazione delle Classi
//Classi utilizzate per il metodo dell’enumerazione diretta
// Classe combinazioni che calcola le k su n combinazioni
class Combinazioni
{
public:
// costruttore/distruttore
Combinazioni(int n, int k);
~Combinazioni();
// metodo Ricorsivo
void Ricorsivo();
// metodo Diretto
virtual void Diretto();
// Contatore delle coalizioni
int n_kCount;
protected:
// visualizza la combinazione corrente
void stampacomb();
// funzione per il metodo ricorsivo
void combimpl(int n, int k, int nbase);
// funzione per il metodo diretto
int incremento(int k);
// n_n=#giocatori, n_k=#sottoinsieme di n
int n_n;
int n_k;
// array della combinazione corrente
int* pvals;
};
26
//Classe indice che eredita da combinazioni
class indice: public Combinazioni{
public:
//costruttore-distruttore
indice(int q, int p[],int n,int k);
~indice();
//Funzione per il calcolo degli indici
void calcola_indice_parziale(int);
private:
//Funzione per il calcolo delle combinazioni
void Diretto();
//funzione per salvare le combinazioni in coalizioni c
void salva();
//vettore contenente l’indice di Shapley
//double* shapley;
//vettore contenente l’indice di Banzhaf
//double* banzhaf;
//vettore contentente l’indice di Coleman
//double* coleman;
//funzione per verificare l’appartenenza di
//un giocatore ad una data coalizione
bool find(int*,int);
//funzione per il calcolo del peso di una coalizione
int peso_coal(int *,int);
//funzione per il calcolo del complementare
int* complementare(int *);
//funzione per calcolare una coalizione ridotta
int *subset(int*,int);
//funzione per salvare le coalizioni calcolate
gioco::coalizioni *c;
//coefficiente binomiale
int64 bin;
//struct contenente i dati del gioco in esame
gioco::gioco_maggioranza g;
//numero di coalizioni vincenti
double omega;
};
//Classe per il metodo delle funzioni generatrici
//Classe per implementare il metodo delle funzioni generatrici
class f_generatrice{
public:
//Costruttore-Distruttore
27
f_generatrice(int q,int*p,int nn);
virtual ~f_generatrice(){
delete[] g.pesi;
cout<<"ok";}
protected:
//Struct che contiene i dati del gioco in esame
gioco::gioco_maggioranza g;
//Funzione per determinare la lunghezza di a_j, grado massimo del
//polinomio che si genera
inline int grado();
//numero dei giocatori
int n;
};
// Classe per il calcolo dell’indice di Coleman,
// che eredita da f_generatrice
class i_coleman:public f_generatrice{
public:
//Costruttore-Distruttore
i_coleman(int q,int*p,int nn);
//Funzione per il calcolo dell’indice di Coleman
double* c_indice();
//Funzione per il calcolo dell’indice di Banzhaf
double* banzhaf();
private:
//Funzione per il calcolo degli swings
int* swing();
//Funzione per il calcolo dei coefficienti a_j
int* coefficienti();
};
//Classe per il calcolo dell’indice di Shapley-Shubik
//che eredita da f_generatrice
class i_shapley:public f_generatrice{
public:
//Cotruttore-Distruttore
i_shapley(int q,int*p,int nn);
//Funzione per il calcolo dell’indice di Shapley
double *s_indice();
private:
//Funzione per il calcolo della matrice D
int** matrice_d();
};
28
/* Classe partizione:
lo scopo è di partizionare l’insieme dei giocatori secondo i seguenti criteri:
1-La partizione è costituita da insiemi disgiunti
2-Giocatori con lo stesso peso appartengono allo stesso sottoinsieme
3-I sottoinsiemi sono ordinati con peso decrescente
*/
class partizione{
public:
//costruttore-distruttore
partizione(int n,int q,int* p);
~partizione();
//ritorna la partizione del vettore pesi
gioco::subset* partition();
//funzione che determina il numero di partizioni
int conta_part();
private:
//struct con le caratteristiche del gioco in esame
gioco::gioco_maggioranza g;
//numero dei giocatori
int n_n;
//funzione che ritorna un vettore contenente i possibili pesi
int* elimina();
//funzione che individua la cardinalità delle partizioni
int* cardinalita_subset();
};
//Classe dummy_player: per il calcolo del dummy player
class dummy_player{
public:
//Costruttore-Distruttore
dummy_player(int n,int q,int*p,gioco::subset* s,int m);
~dummy_player();
//funzione per verificare se esistono dummy-player
int trova_dummy();
//Eliminazione dei dummy player
gioco::subset* delete_dummy();
private:
//numero dei giocatori
int nn;
//struttura del gioco
gioco::gioco_maggioranza g;
//partizione di N
gioco::subset* ss;
//numero di sottoinsiemi
29
int mm;
//numero di coalizioni vincenti minimali
int c;
};
//Classe indice_dyn: per il calcolo degli indici di potere
class indice_dyn{
public:
//Costruttore-Distruttore
indice_dyn(int n,int q,int *p, gioco::subset* s,int m);
~indice_dyn();
//funzione per il calcolo degli indici
double index(int player,int t,int card);
private:
//numero dei giocatori
int nn;
//numero dei sottoinsiemi
int mm;
//struttura del gioco
gioco::gioco_maggioranza g;
//struttura contenente i sottoinsiemi
gioco::subset* ss;
};
#endif
30
Appendice B
Nel seguito è riportato il codice relativo al file Indici.cpp in cui sono contenute le definizioni
delle classi e delle funzioni dichiarate in Indici.hpp.
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<fstream>
#include"Indici.hpp"
using namespace std;
//Definizione delle classi
/*======================
Classe Combinazioni
======================*/
// definizione del costruttore
Combinazioni::Combinazioni(int n, int k)
{
n_n = n;
n_k = k;
n_kCount = 0;
pvals = new int[k];
}
//Definizione del distruttore
Combinazioni::~Combinazioni()
{
delete [] pvals;
}
//stampa la combinazione corrente
void Combinazioni::stampacomb()
{
for(int i=n_k-1;i>=0;i-- )
printf("%d ",pvals[i]);
printf("\n");
}
//metodo Diretto:
// 1. Parte da una combinazione iniziale
// 2. stampa la combinazione corrente
//
incrementa la combinazione corrente
// 3. visualizza il numero di combinazioni trovate
31
void Combinazioni::Diretto()
{
int i=n_k;
int loop;
n_kCount = 0;
for(loop=0;loop<n_k;loop++)
pvals[loop]=i--;
do
{
n_kCount++;
stampacomb();
} while( incremento(0) );
printf("Numero coalizioni: ","\n");
printf("%d\n",n_kCount);
}
//Funzione per incrementare la combinazione corrente
// l’incremento viene effettuato mantenendo l’ordine lessicografico:
//esempio: scelta di 2 elementi su 4 (1,2) -> (1,3) -> (1,4) -> (2,3) -> (2,4)
// (3,4)
int Combinazioni::incremento(int k)
{
int f;
pvals[k]++;
if( pvals[k]>n_n - k )
{
if( k==n_k-1 )
return 0;
f = incremento(k+1);
pvals[k]=pvals[k+1]+1;
return f;
}
return 1;
//Ritorna 1 se esiste la combinazione successiva, 0 altrimenti
}
// metodo Ricorsivo
void Combinazioni::Ricorsivo()
{
n_kCount = 0;
combimpl(n_n,n_k,1);//Funzione ausiliaria
printf("Numero coalizioni: ","\n");
printf("%d\n",n_kCount);
}
32
//Funzione ausiliaria per il metodo ricorsivo
void Combinazioni::combimpl(int n, int k, int nbase)
{
int i;
for(i=nbase;i<=(n-k+1);i++)
{
pvals[k-1] = i;//Inizializzazione della combinazione
if( 1<k ) //Ciclo ricorsivo
combimpl(n,k-1,i+1);
else
{
//Visualizza coalizione corrente
stampacomb();
//Incremento del contatore delle coalizioni
n_kCount++;
}
}
}
/*==============================
Definizione della classe indice
================================*/
//definizione del costruttore
indice::indice(int q,int p[],int n,int k):Combinazioni(n,k){
g.quota=q;
g.pesi=new int[n];
g.pesi=p;
omega=0.0;
bin=binomiale(n,k);
c=new gioco::coalizioni[bin];
for(int j=0;j<bin;j++){
c[j].v=new int[n_k];
for(int i=0;i<n_k;i++){
c[j].v[i]=0;
}
c[j].potere=0;
}
}
//definizione del distruttore
indice::~indice(){ for(int i=0;i<bin;i++) delete[] c[i].v;
delete[] c,g.pesi;
}
//definizione della funzione per salvare le coalizioni
void indice::salva(){ for(int i=n_k-1;i>=0;i--){
33
c[n_kCount].v[i]=pvals[i];
} c[n_kCount].potere=peso_coal(c[n_kCount].v,n_k); }
//definizione della funzione Diretto:
//costruisce il vettore di coalizioni
//contenente tutte le combinazioni di
//ordine k di n giocatori
void indice::Diretto(){
int i=n_k;
int loop;
n_kCount = 0;
for(loop=0;loop<n_k;loop++)
pvals[loop]=i--;
do
{
//Visualizza la combinazione corrente
stampacomb();
//Salva la combinazine corrente
salva();
//Incrementa il contatore delle coalizioni
n_kCount++;
} while( incremento(0) );
}
// definizione della funzione per verificare
// se il giocatore player appartiene
//alla coalizione corrente v
bool indice::find(int *v,int player){
for(int i=0;i<n_k;i++){
if(v[i]==player) return true;
}
return false;
//Ritorna 1 se appartiene e 0 altrimenti
}
//definizione della funzione per il calcolo
//del peso della coalizione corrente
int indice::peso_coal(int *v,int card){
int peso_v=0;
for(int i=0;i<card;i++){
peso_v=peso_v+g.pesi[v[i]-1];//Somma dei pesi dei giocatori
}
return peso_v;
}
// definizione della funzione per calcolare la coalizione
//complementare a quella data v
int* indice::complementare(int* v){
34
int *p;
bool b;
int i=0;
p=new int[n_n-n_k];//Vettore complementare a v
for(int j=0;j<n_n;j++){
//Verifica se il giocatore appartiene alla coalizione
b=find(v,j+1);
if(b==false){p[i]=j+1;
i++;
}
}
return p;
delete[] p;
}
//Funzione per il calcolo della coalizione v privata
//del giocatore player
int* indice::subset(int *v,int player){
int* sub_v;//Vettore contenente la nuova coalizione
int j=0;
//Verifica che il giocatore appartiene alla coalizione
if(find(v,player)){
sub_v=new int[n_k-1];//Vettore di ordine k-1
//Copia del vettore escludendo il giocatore player
for(int i=0;i<n_k;i++){
if(v[i]!=player){ sub_v[j]=v[i];
j++;
}
}
}
//Se non appartiene il vettore resta inalterato
else{ sub_v=new int[n_k];
for(int i=0;i<n_k-1;i++)sub_v[i]=v[i];}
return sub_v; delete[] sub_v; }
//Funzione per il calcolo dell’indice
void indice::calcola_indice_parziale(int t){
int swing=0;//numero totale di swing sulle coalizioni di ordine k
gioco::coalizioni s;//Coalizione ausiliaria
s.v=new int[n_k-1];
double*shapley=new double[n_n];
double* banzhaf=new double[n_n];
double*coleman=new double[n_n];
//inizializzazione degli indici a zero
for(int i=0;i<n_n;i++){
shapley[i]=0.0;
35
banzhaf[i]=0.0;
coleman[i]=0.0;
}
cout<<endl<<"Coalizioni di "<<n_k<<" giocatori: "<<endl;
//Calcolo di tutte le combinazioni di ordine k
Diretto();
//Ciclo sui giocatori
for(int j=0;j<n_n;j++){
//Ciclo sulle combinazioni
for(int i=0;i<bin;i++){
//Verifica che il peso della coalizione
//sia maggiore della quota e
//aggiornamento delle coalizioni vincenti
if(peso_coal(c[i].v,n_k)>=g.quota) omega+=1;
//Verifica che il giocatore j+1 appartenga
//alla coalizione
if(find(c[i].v,j+1)){
//Crea il sottoinsieme priva del giocatore
s.v=subset(c[i].v,j+1);
//Calcola il peso della nuova coalizione
s.potere=peso_coal(s.v,n_k-1);
//Verifica per l’aggiornamento degli indici
//Se il peso della coalizione è minore della quota e
//se la vecchia coalizione era vincente, aggiorna
{if(s.potere<g.quota & s.potere+g.pesi[j]>=g.quota ){
shapley[j]=fattoriale(n_k-1)*fattoriale(n_n-n_k)/double(fattoriale(n_n))+shapley[j];
coleman[j]+=1;
banzhaf[j]+=1/pow(2.0,double(n_n-1));
//banzhaf[j]+=1;
swing+=1;}
}
}
}
} cout<<"Totale swings sulle coalizioni di ordine "<<n_k<<":
"<<swing<<endl; swing_tot+=swing; omega=double(omega/n_n);//Totale
delle coalizioni vincenti sulle coalizioni di ordine k
omega1+=omega;//Totale delle coalizioni vincenti
cout<<endl<<"Coalizioni di ordine "<<n_k<<" vincenti: " <<
omega<<endl;
if(t==1){ for(int i=0;i<n_n;i++) ind[i]+=shapley[i];}
if(t==2) {for(int i=0;i<n_n;i++) ind[i]+=banzhaf[i];}
else if(t==3){for (int i=0;i<n_n;i++)ind[i]+=coleman[i];}
delete[] shapley,banzhaf,coleman; delete[] s.v; }
36
/*======================================
Definizione della classe
partizione
=======================================*/
//Definizione del costruttore
partizione::partizione(int n,int q,int *p){
n_n=n;
g.pesi=new int[n];
g.pesi=p;
g.quota=q;
}
//definizione della funzione partizione
partizione::~partizione() {
delete[] g.pesi;
}
//Funzione che determina il numero di partizioni dell’insieme dato
int partizione::conta_part(){
int part=0;
sort(g.pesi,g.pesi+n_n);
//ordina
reverse(g.pesi,g.pesi+n_n); //riordina in modo decrescente
for(int i=0;i<n_n;i++){
if(g.pesi[i]!=g.pesi[i+1]) part+=1; //conta il numero di partizioni
}
return part; }
//Funzione che individua la cardinalità di ogni sottoinsieme
int* partizione::cardinalita_subset(){
int p=conta_part();//Determina il numero delle partizioni
int* conta=new int[p]; //vettore contenente le dimensioni delle partizioni
for(int i=0;i<p;i++) conta[i]=1;
int i=0;
//calcolo la cardinalità di ogni sottoinsieme
for(int j=0;j<p;j++){
while(g.pesi[i]==g.pesi[i+1]) {
conta[j]+=1;
i++;
}
i++;
}
return conta;
delete[] conta;
}
//Funzione che ritorna un vettore con i possibili pesi del gioco
//esempio se il vettore dei pesi è (1,2,2,3,4,5,5) i pesi possibili sono
//(1,2,3,4,5)
37
int* partizione::elimina(){
int p=conta_part();//Determina il numero delle partizioni
int* sub_v=new int[p];//vettore contenente i possibili pesi
sort(g.pesi,g.pesi+n_n);
reverse(g.pesi,g.pesi+n_n);//ordina in modo decrescente
int j=0;
//calcola i possibili pesi
for(int i=0;i<n_n;i++){
if(g.pesi[i]!=g.pesi[i+1]){
sub_v[j]=g.pesi[i];
j++;
}
}
return sub_v;
delete[] sub_v;
}
//Funzione che ritorna la partizione dell’insieme N dei giocatori
//secondo i criteri sopra esposti
gioco::subset* partizione::partition(){
int p=conta_part();//Determina il numero delle partizioni
gioco::subset* N=new gioco::subset[p];//vetteore che contiene i sottoinsiemi
int* c=new int[p];//vettore che contiene la cardinalità
c=cardinalita_subset();//Determina la cardinalità dei sottoinsiemi
int* w=elimina();//determina i possibili pesi
cout<<endl<<"Numero di partizioni "<<p<<endl<<endl;
for(int i=0;i<p;i++){
N[i].card=c[i];
cout<<"Sottoinsieme "<<i+1;
cout<<" Cardinalità "<<N[i].card;
N[i].peso=w[i];
cout<<" Peso "<<N[i].peso<<endl;}
return N;
delete[] N;
delete[] c;
delete[] w;
}
/*======================================
Definizione della classe
Dummy-Player
========================================*/
//Definizione del costruttore
dummy_player::dummy_player(int n,int q,int*p,gioco::subset* s,int
m){
nn=n;
38
mm=m;
g.pesi=new int[nn];
for(int i=0;i<nn;i++) g.pesi[i]=p[i];
g.quota=q;
ss=new gioco::subset[mm];
for(int i=0;i<mm;i++){
ss[i].card=s[i].card;
ss[i].peso=s[i].peso;
}
c=0;
}
//definizione del distruttore
dummy_player::~dummy_player(){
delete[] g.pesi,ss;
}
//Funzione per verificare se esistono dummy-player
int dummy_player::trova_dummy(){
int* cc=new int[g.quota];//vettore di dimensione pari alla quota
//Variabili ausiliarie
int a_star=0;
int c_prime=0;
int w_prime=0;
//Variabile contenente il numero delle coaizioni vincenti minimali
int c_star=0;
//inizializzazione
for(int i=1;i<=g.quota-1;i++) cc[i]=0; cc[0]=1; for(int
i=0;i<nn;i++) w_prime+=g.pesi[i];
//Implementazione dell’algoritmo
for(int x=0;x<mm-1;x++){//Ciclo sui sottoinsiemi
w_prime=w_prime-ss[x].peso*ss[x].card;
for(int w=a_star;w>=0;w--){
if(cc[w]>0){
c_prime=1;
for(int y=1;y<=ss[x].card;y++){
c_prime=c_prime*(ss[x].card-y+1)/y;//Aggiornamento di c_prime
if(w+y*ss[x].peso<=g.quota-1){
cc[w+y*ss[x].peso]+=cc[w]*c_prime;//calcolo di cc
a_star=max(a_star,w+ss[x].peso*y);//Aggiornamento di a_star
}
else if((g.quota<=w+y*ss[x].peso)&&(w+y*ss[x].peso<=g.quota-1+ss[x].peso))
{
c_star+=cc[w]*c_prime;//Aggiornamento di c_star
}}}}
if(a_star+w_prime<=g.quota-1){
//Ritorna x se esistono dummy player
return x;
}
39
}
c=c_star; cout<<"Non ci sono dummy player"<<endl; return
-1;//Ritorna -1 se non esistono dummy player delete[] cc; }
// Funzione che elimina gli eventuali dummy player dalla partizione iniziale
gioco::subset* dummy_player::delete_dummy(){
int result=trova_dummy();//Cerca gli eventuali dummy player
if(result=-1){
return ss;
}
else{//Eliminazione di eventuali dummy player
gioco::subset* sub_p=new gioco::subset[result+1];
for(int i=0;i<=result;i++){
sub_p[i].card=ss[i].card;
sub_p[i].peso=ss[i].peso;
}
return sub_p;
delete[] sub_p;
}
}
/*=====================================
Definizione della classe
indice_dyn
=======================================*/
//Definizione del costruttore
indice_dyn::indice_dyn(int n,int q,int *p, gioco::subset* s,int
m){
nn=n;
mm=m;
g.pesi=new int[nn];
for(int i=0;i<nn;i++) g.pesi[i]=p[i];
g.quota=q;
ss=new gioco::subset[mm];
for(int i=0;i<mm;i++){
ss[i].card=s[i].card;
ss[i].peso=s[i].peso;
}
}
//Definizione del distruttore
indice_dyn::~indice_dyn(){
delete[] g.pesi,ss;
}
//Funzione per il calcolo degli indici
double indice_dyn::index(int player,int t,int card){
//Vettore contenente gli indici per il giocatore player
40
double* indice=new double(3);
//Matrice di dimensioni quota x n
double** c=new double*[g.quota];
for(int i=0;i<g.quota;i++){//costruzione della matrice
c[i]=new double[nn];
}
//inizializzazione
c[0][0]=1;
for(int i=1;i<g.quota;i++){
for(int j=1;j<nn;j++){
c[i][j]=0;
}}
//Variabili ausiliarie
int t_star=0;
double phi=0.0;//indice di Shapley
double b=0.0;//numero di swing del giocatore
int y_prime=0;
double c_prime=0.0;
int *a=new int[nn];
for(int i=0;i<nn;i++)a[i]=0;
//Implementazione dell’algoritmo
for(int x=0;x<mm;x++){//ciclo sui sottoinsiemi
//verifica se il giocatore player appartiene al sottoinsieme in esame
if(ss[x].peso==player) y_prime=ss[x].card-1;
else y_prime=ss[x].card;
for(int t=t_star;t>=0;t--){
for(int w=a[t];w>=0;w--){
if(c[w][t]>0){
c_prime=1;
for(int y=1;y<=y_prime;y++){
c_prime=c_prime*(y_prime-y+1)/y;//aggiornamento di c_prime
if(w+ss[x].peso*y<=g.quota-1){
c[w+ss[x].peso*y][t+y]+=c[w][t]*c_prime;//Calcolo di c
a[t+y]=max(a[t+y],w+ss[x].peso*y);}//aggiornamento di a
if((g.quota-player<=w+ss[x].peso*y)&&( w+ss[x].peso*y<=g.quota-1)){
//Aggiornamento dell’indice di Shapley e del numero di swing
phi+=fattoriale(t+y)*fattoriale(nn-t-y-1)*c[w][t]*c_prime;
b+=c[w][t]*c_prime;//conta il numero di swing del giocatore player
}
}}}}
t_star+=y_prime;
}
//inizializzazione del vettore indice
indice[0]=phi/fattoriale(nn);//Shapley
indice[1]=b;//numero di swing del giocatore player
indice[2]=b/pow(2.0,nn-1);//Banzhaf
swing_tot+=int(indice[1]*card);//per il calcolo del numero di swing totali
41
if(t==2) return indice[0]; if(t==3) return indice[2]; else
if(t==4) return indice[1];
delete[] indice; for(int i=0;i<g.quota;i++) delete c[i]; delete[]
c; delete[] a; }
//Definizione dei membri
/*======================
Classe f_generatrice
=======================*/
//Costruttore
f_generatrice::f_generatrice(int q,int *p,int nn){
n=nn;
g.pesi=new int[n];
g.pesi=p;
g.quota=q;
}
//Funzione per determinare il grado del
//polinomio associato ai pesi
int f_generatrice::grado(){
int gg=0;
for(int i=0;i<n;i++) gg=gg+g.pesi[i];
return gg;
}
/*=====================
Classe i_banzhaf
=======================*/
//Costruttore
i_coleman::i_coleman(int q,int* p,int nn):f_generatrice(q,p,nn){};
//Funzione per il calcolo dei coefficienti a_j
int* i_coleman::coefficienti(){ int dim=grado(); int* a=new
int[dim+1]; int* a_aux=new int[dim+1];//array ausiliario per il
calcolo dei coefficienti
//inizializzazione dei coefficienti
a_aux[0]=1; for(int i=0;i<=dim;i++){
if(i>0) a_aux[i]=0;
a[i]=0;
}
//Aggiornamento dei coefficienti
//utilizzando la regola (a_j)^r=(a_j)^(r-1)+(a_(j-w_r))^(r-1)
42
//come descritto nell’algoritmo
for(int r=1;r<=n;r++){
for(int j=0;j<=dim;j++){
if((j-g.pesi[r-1])<0) a_aux[j-g.pesi[r-1]]=0;
a[j]=a_aux[j]+a_aux[j-g.pesi[r-1]];
}
for(int i=0;i<=dim;i++)a_aux[i]=a[i];
}
return a; delete[] a,a_aux; }
//Funzione per il calcolo degli swings
//Aggiornamento dei c_j utilizzando la regola
//c_j=a_j-c_(j-w_i)
int* i_coleman::swing(){
int dim=grado();
int *c=new int[dim+1];//Array contenente c_j
int *a=new int[dim+1];//Array contenente i coefficienti a_j
int *eta=new int[n];//Array contenente gli swings
//inizializzazioni
for(int i=0;i<n;i++) eta[i]=0;
for(int i=0;i<=dim;i++) c[i]=0;
a=coefficienti();
for(int r=1;r<=n;r++){
for(int j=0;j<=dim;j++){
if((j-g.pesi[r-1])<0) c[(j-g.pesi[r-1])]=0;
c[j]=a[j]-c[j-g.pesi[r-1]];
}
//calcolo degli swing per ciascun giocatore
for(int k=g.quota-g.pesi[r-1]; k<g.quota;k++) eta[r-1]+=c[k];
}
return eta;
delete[] c,a,eta;
}
//funzione per il calcolo dell’indice di Coleman
double* i_coleman::c_indice(){
int64 somma=0;
//Calcolo degli swings
int* eta=swing();
double* index=new double[n];//Vettore contenente l’indice
//numero totale di swings
for(int i=0;i<n;i++) somma+=eta[i];
cout<<endl<<"Numero totale di swings totali: "<<somma<<endl;
//indice_i=(swings giocatore i)/(swings totali)
for(int i=0;i<n;i++){
index[i]=double(eta[i])/somma;
43
}
return index;
delete[] eta,index;
}
//Definizione della funzione per il calcolo
//dell’indice di Banzhaf metodo delle f_generatrici
double* i_coleman::banzhaf(){ int dim=grado();
int* a=coefficienti();//Calcolo dei coefficienti a_j
int* beta=new int[n];//Vettore per il calcolo degli swings
double* i_banzhaf=new double[n];//Vettore contenente l’indice
double n_winning=0.0;// numero di coalizioni vincenti
int swing_t=0; //numero totale di swing
//Calcola il numero di coalizioni vincenti
for(int i=0;i<=dim;i++){
if(i>=g.quota) n_winning+=a[i];
}
cout<<endl<<"Numero totale di coalizioni
vincenti:"<<n_winning<<endl;
beta=swing();
for(int i=0;i<n;i++)swing_t+=beta[i];
cout<<"Numero totale di swings: "<<swing_t<<endl;
//Calcolo dell’indice di Banzhaf
for(int i=0;i<n;i++) {
i_banzhaf[i]=double(beta[i])/pow(2.0,n);
}
return i_banzhaf;
delete[] i_banzhaf;
delete[] a,beta;
}
/*=========================
Classe i_shapley
===========================*/
//Costruttore
i_shapley::i_shapley(int q,int* p,int nn):f_generatrice(q,p,nn){};
// Funzione per il calcolo della matrice D
//utilizzndo la regola D_jk^r=D_jk^(r-1)+D_(j-w_r,k-1)^(r-1)
//come descritto nell’algoritmo
int** i_shapley::matrice_d(){ int dim=grado(); int** d=new
44
int*[dim+1];//Matrice contenente i d_jk int** d_aux=new
int*[dim+1];//Matrice ausiliaria
//Costruzione delle matrici
for(int i=0;i<=dim;i++) {
d[i]=new int[n+1];
d_aux[i]=new int[n+1];
}
//inizializzazione
for(int i=0;i<=dim;i++){ for(int j=0;j<=n;j++){
d_aux[i][j]=0;
d[i][j]=0;
}
}
d_aux[0][0]=1;
//Aggiornamento dei D_jk come descritto sopra
for(int r=1;r<=n;r++){
for(int j=0;j<=dim;j++){
for(int k=0;k<=n;k++){
if((j-g.pesi[r-1])<0 || (k-1)<0 ) d[j][k]=d_aux[j][k];
else d[j][k]=d_aux[j][k]+d_aux[j-g.pesi[r-1]][k-1];
}
}
for(int i=0;i<=dim;i++){
for(int j=0;j<=n;j++){
d_aux[i][j]=d[i][j];
}
}
}
return d;
//Deallocazione dello spazio relativo
//alle matrici
for(int i=0;i<=dim;i++) {
delete d[i];
delete d_aux[i];
} delete[] d,d_aux; }
// Funzione per il calcolo dell’indice di Shapley-Shubik
double* i_shapley::s_indice(){
int dim=grado();
int **c;
int **a;
c=new int*[dim+1];//Matrice contenente i coefficienti c_jk
a=new int*[dim+1];//Matrice contenente i coefficienti d_jk
int coal_tot=0;//Variabile contenente il numero coalizioni vincenti
int s_tot=0; //Variabile contenente il numero di swings totali
//Costruzione delle matrici
45
for(int i=0;i<=dim;i++){
c[i]=new int[n];
a[i]=new int[n];
}
a=matrice_d();
//Array contenente l’indice
double *eta=new double[n];
//Inizializzazione
for(int i=0;i<n;i++) eta[i]=0;
for(int i=0;i<=dim;i++){
for(int j=0;j<=n;j++){
c[i][j]=0;
}}
//Aggiornamento dei c_jk secondo la regola
// c_jk= d_jk-c_(j-w_i,k-1)
//e calcolo dell’indice
for(int r=0;r<n;r++){
for(int k=0;k<n;k++){
for(int s=g.quota-g.pesi[r];s<g.quota;s++){
for(int j=0;j<=dim;j++){
if((j-g.pesi[r])<0 || k-1 <0) c[j][k]=a[j][k];
else c[j][k]=a[j][k]-c[j-g.pesi[r]][k-1];
coal_tot+=c[j][k];
}
s_tot+=c[s][k];//numero di swings totali
eta[r]=eta[r]+c[s][k]* (fattoriale(k)*fattoriale(n-k-1)/double(fattoriale(n)));
}
}
}
coal_tot=coal_tot/dim;
cout<<endl<<"Numero di coalizioni totali vincenti: "<<coal_tot<<endl;
cout<<"Numero di swings totali: "<<s_tot<<endl;
return eta;
//Si dealloca lo spazio delle matrici
for(int i=0;i<=dim;i++) delete a[i],c[i];
delete[] a,c;
delete[] eta;
}
/*==========================
Definizione delle funzioni
=============================*/
//Definizione del fattoriale
int64 fattoriale(int nn){
46
if(nn==0) return 1L;
return nn*fattoriale(nn-1); }
//Definizione del coefficiente binomiale
inline int64 binomiale(int nn,int k){
return fattoriale(nn)/(fattoriale(nn-k)*fattoriale(k));
}
//funzione per il calcolo dell’indice parziale secondo
//i parametri assegnati
void rielabora_dati::ripeti(int *p,int q,int nn,int k, int t){
indice ii(q,p,nn,k);//crea un oggetto di tipo indice
//Calcolo dell’indice parziale di Banzhaf se t=2, di Shapley se t=1
ii.calcola_indice_parziale(t);
}
//funzione per il calcolo dell’indice totale (Metodo Diretto)
void rielabora_dati::totale(int nn,int *p,int q){
ind=new double[nn];//Vettore contenente l’indice
int scelta;
do{
cout<<endl<<"Scelta dell’indice"<<endl;
cout<<"Calcolo indice di Shapley->1"<<endl;
cout<<"Calcolo indice di Banzhaf->2"<<endl;
cout<<"Calcolo indice di Coleman->3"<<endl;
cout<<"Uscita->0"<<endl;
cout<<"Scelta: ";
cin>>scelta;
if(scelta==0){
cout<<"Uscita"<<endl;
cin.get();
cin.get();
}
if(scelta>3||scelta<0){cout<<"Errore: ripeti scelta"<<endl;}
}while(scelta>3||scelta<0);
//inizializzazione
for(int j=0;j<nn;j++) ind[j]=0;
for(int i=1;i<=nn;i++){
//calcolo dell’indice
rielabora_dati::ripeti(p,q,nn,i,scelta);
47
}
if(scelta==1){
cout<<endl<<"Totale coalizioni vincenti: "<<omega1<<endl;
cout<<"Swings totali: "<<swing_tot<<endl;
cout<<endl<<"Indice di Shapley: "<<endl;
for(int i=0;i<nn;i++) cout<<"Giocatore "<<i+1<<": "<<ind[i]<<endl;
rielabora_dati::salva_dati(p,ind,nn,scelta);
}
if(scelta==2){
cout<<endl<<"Totale coalizioni vincenti: "<<omega1<<endl;
cout<<"Swings totali: "<<swing_tot<<endl;
cout<<endl<<"Indice di Banzhaf"<<endl;
for(int i=0;i<nn;i++){
//ind[i]=double(ind[i]/omega1);
cout<<"Giocatore "<<i+1<<": "<<ind[i]<<endl;
}
rielabora_dati::salva_dati(p,ind,nn,scelta);
}
else if(scelta==3){
cout<<endl<<"Totale coalizioni vincenti: "<<omega1<<endl;
cout<<"Swings totali: "<<swing_tot<<endl;
cout<<endl<<"Indice di Coleman: "<<endl;
if(swing_tot!=0){
for(int i=0;i<nn;i++){
ind[i]=double(ind[i]/swing_tot);
cout<<"Giocatore "<<i+1<<": "<<ind[i]<<endl;}
}
rielabora_dati::salva_dati(p,ind,nn,scelta);
}
delete[] ind; }
// Funzione per l’aggiornamento dei pesi e dei giocatori
int* rielabora_dati:: nuovi_pesi(int &n,int*pesi,gioco::subset*
s,int &np,int q,int c){
for(int i=c+1;i<np;i++) n=n-s[i].card;
for (int i=c;i<np;i++) np=np-1;
int* pesi_nuovi=new int[n];
for(int i=0;i<n;i++) pesi_nuovi[i]=pesi[i];
return pesi_nuovi;
delete[] pesi_nuovi;
}
48
//Funzione per il calcolo degli indici (Programmazione Dinamica)
void rielabora_dati::compute_index(int scelta,int n,int* pesi,int
np, gioco::subset* s,int q ){
//Se scelta è uguale a 1 calcola i possibili dummy player
if(scelta==1){
dummy_player d(n,q,pesi,s,np);
int c=d.trova_dummy();
if(c!=-1){
gioco::subset* s=d.delete_dummy();
cout<<"Ci sono dummy-player"<<endl;
cout<<"Sottoinsiemi rimanenti;"<<endl;
for(int i=0;i<=c;i++) cout<<"Sottoinsieme "<<i+1<<" cardinalità"
<<s[i].card<<" peso "<<s[i].peso<<endl;
}
}
//Se si vuole calcolare un indice
else if(scelta==2||scelta==3||scelta==4){
int* pesi_new;//nuovo vettore per i pesi
gioco::subset* s1;//nuovo vettore contenente i sottoinsiemi
dummy_player d(n,q,pesi,s,np);
int c=d.trova_dummy();
//se esistono dummy-player vengono eliminati
if(c!=-1){
s1=d.delete_dummy();//aggiornamento dei sottoinsiemi
int * pesi_new=rielabora_dati::nuovi_pesi(n,pesi,s1,np,q,c);//nuovo vettore dei pesi
cout<<"Nuovo numero di partizioni "<<np<<endl;
}
//se non esistono dummy-player i sottoinsiemi non cambiano
else{
s1=new gioco::subset[np];
pesi_new=new int[n];
for(int i=0;i<np;i++){
s1[i].card=s[i].card;
s1[i].peso=s[i].peso;
}
for(int i=0;i<n;i++) pesi_new[i]=pesi[i];
}
//Se scelta è uguale a 2 calcola l’indice di Shapley
if(scelta==2){
indice_dyn d(n,q,pesi_new,s1,np);
//A pesi uguali corriponde lo stesso indice di potere,
//il ciclo viene effettuato sui pesi anzichè sui giocatori
for(int i=0;i<np;i++){
49
double m=d.index(s1[i].peso,2,s1[i].card);
cout<<endl<<"Potere giocatore con peso "<<s1[i].peso<<": "<<endl;
cout<<"Valore Shapley: "<<m<<endl;
}
}
//Se scelta è uguale a 3 calcola l’indice di Banzhaf
if(scelta==3){
indice_dyn d(n,q,pesi_new,s1,np);
for(int i=0;i<np;i++){
double m=d.index(s1[i].peso,3,s1[i].card);
cout<<endl<<"Potere giocatore con peso "<<s1[i].peso<<": "<<endl;
cout<<"Indice di Banzhaf: "<<m<<endl;
}
}
//Se scelta è uguale a 4 calcola l’indice di Coleman
if(scelta==4){
indice_dyn d(n,q,pesi_new,s1,np);
double* m1=new double[np];//vettore contenente gli swing
//come prima ciclo è effettuato sui pesi
for(int i=0;i<np;i++){
m1[i]=d.index(s1[i].peso,4,s1[i].card);}//viene calcolato anche il
numero di swing totali
for(int i=0;i<np;i++){
cout<<endl<<"Potere giocatore con peso "<<s1[i].peso<<": "<<endl;
cout<<"Indice di Coleman: "<<m1[i]/swing_tot<<endl;
}
delete[] m1;
}
delete[] s,pesi_new;
delete[] s1;
}
}
//Funzione per l’inserimenti dei dati del gioco
int* rielabora_dati::dati(int &q,int &n,int scelta){
//Inserimento dei dati per il calcolo degli indici
do{
cout<<"Inserisci numero dei giocatori"<<endl;
cout<<"Numero: ";
cin>>n;
if(scelta==1 & n>=21)cout<<"Parametri non consentiti ripeti scelta"<<endl;
}while(scelta==1 & n>=21);
int* pesi=new int[n];
cout<<endl<<"Inserisci dati del gioco "<<endl;
cout<<"Quota:";
50
cin>>q;
cout<<endl<<"Inserisci pesi"<<endl;
for(int i=0;i<n;i++){
cout<<"Giocatore "<<i+1<<": ";
cin>>pesi[i];
}
return pesi;
delete[] pesi;
}
//Funzione per il salvataggio dei dati su file
void rielabora_dati::salva_dati(int* pesi,double*indici,int n,int
scelta){
ofstream f("dati.dat");
if(scelta==1) f<<"Giocatori "<<"Pesi "<<"Shapley"<<endl;
if(scelta==2)f<<"Giocatori "<<"Pesi "<<"Banzhaf"<<endl;
if(scelta==3)f<<"Giocatori "<<"Pesi "<<"Coleman"<<endl;
for(int i=0;i<n;i++){
f<<i+1<<"\t"<<pesi[i]<<"\t"<<indici[i]<<endl;
}
cout<<"Scrittura su file"<<endl;
f.close();
}
51
Appendice C
Nel seguito viene riportato il codice dei tre file main (Metodo diretto.cpp, Funzioni generatrici.cpp,
Programmazione dinamica.cpp) relativi alle tre tipologie di algoritmi utilizzati per l’implementazione degli indici.
3.1
Metodo Diretto
#include<iostream>
#include<ctime>
#include "Indici.hpp"
//Variabili globali
double* ind; //vettore per gli indici
int swing_tot; //numero di swing_totali
double omega1; //numero totale di coalizioni vincenti
using namespace std;
int main( int argc, char *argv[ ], char *envp[ ] )
{
//Dichiarazione delle variabili
int k=1;
int n;//numero giocatori
int q;//quota di maggioranza
int *pesi;//vettore dei pesi
clock_t start,end;
double tempo;
start=clock();
//Inserimento dei dati necessari per il calcolo degli indici
do{ cout<<"Inserisci il numero dei giocatori (al max 20)"<<endl<<"giocatori: ";
cin>>n;
if(n<=0 || n>21) {cout<<"Errore: vincoli non rispettati"<<endl;}
}while(n>21);
pesi=new int[n];
cout<<"Inserisci la quota"<<endl;
cout<<"Quota: ";
cin>>q;
cout<<"Inserisci pesi dei giocatori"<<endl;
for(int i=0;i<n;i++){
cout<<"Peso giocatore "<<i+1<<": ";
cin>>pesi[i];
}
//Calcolo dell’indice
rielabora_dati::totale(n,pesi,q);
52
end=clock();
tempo=((double)(end-start))/CLOCKS_PER_SEC;
time_t tm(0);
cout<<endl<<"Cpu time = "<<tempo<<endl;
cin.get();
cin.get();
delete[] pesi,ind;
return 0;
}
3.2
Programmazione Dinamica
#include<iostream>
#include<ctime>
#include"Indici.hpp"
int swing_tot;//numero degli swing totali
double* ind; //variabile globale per l’indice
double omega1;//variabile globale per il numero di coalizioni vincenti
using namespace std;
int main(){
//Dichiarazioni variabili
int n;//numero giocatori
int q;//quota di maggioranza
int*pesi;//vettore dei pesi
int scelta;
int np;//numero di partizioni
clock_t start,end;
double tempo;
start=clock();
//Inserimento dei dati necessari al calcolo
cout<<"Inserisci numero dei giocatori"<<endl;
cout<<"Numero: ";
cin>>n;
pesi=new int[n];
cout<<"Inserisci la quota"<<endl;
cout<<"Quota: ";
cin>>q;
cout<<"Inserisci pesi dei giocatori"<<endl;
for(int i=0;i<n;i++){
cout<<"Peso giocatore "<<i+1<<": ";
cin>>pesi[i];
}
//Partizione dell’insieme dei giocatori
partizione p(n,q,pesi);//creazione di un oggetto partizione
53
gioco::subset* s=p.partition(); //partizione del sottoinsieme
np=p.conta_part();//conta il numero di partizioni
do {
cout<<endl<<"Calcolare Dummy-Player->1"<<endl;
cout<<"Calcolare indice di Shapley->2"<<endl;
cout<<"Calcolare indice di Banzhaf->3"<<endl;
cout<<"Calcolare indice di Coleman->4"<<endl;
cout<<"Uscita->0"<<endl;
cout<<"Scelta : ";
cin>>scelta;
if (scelta==0){
cout<<"Uscita"<<endl;
cin.get();
cin.get();
return 0;
}
else if(scelta>=5||scelta<0){ cout<<"Errore: ripeti scelta"<<endl;}
}while(scelta>=5|| scelta<0);
//Calcolo degli indici
rielabora_dati::compute_index(scelta,n,pesi,np,s,q);
delete[] s,pesi;
end=clock(); tempo=((double)(end-start))/CLOCKS_PER_SEC; time_t
tm(0); cout<<endl<<"Cpu time = "<<tempo<<endl;
cin.get();
cin.get();
}
3.3
Funzioni Generatrici
#include<iostream>
#include<ctime>
#include<fstream>
#include"Indici.hpp"
using namespace std;
//Variabili globali
double* ind;// vettore contenente gli indici
int swing_tot;//numero di swing totali
double omega1; //numero di coalizioni vincenti totali
int main(){
//Dichiarazioni delle variabili
54
clock_t start,end;
double tempo;
start=clock();
int q;//Quota di maggioranza
int *p;//Vettore dei pesi
int n;//Numero giocatori
int scelta=0;
double* indice;
do{
cout<<endl<<"Calcolo dell’indice"<<endl;
cout<<"Indice di Shapley (max 20 giocatori)->1"<<endl;
cout<<"Indice di Banzhaf->2"<<endl;
cout<<"Indice Coleman->3"<<endl;
cout<<"Uscita->0"<<endl;
cout<<"Scelta: ";
cin>>scelta;
if(scelta<0||scelta>3) cout<<"Errore: ripeti scelta"<<endl;
cout<<endl;}while(scelta<0||scelta>3);
if(scelta==0){
cout<<"Uscita"<<endl;
cin.get();
cin.get();
return 0;
}
p=rielabora_dati::dati(q,n,scelta);
indice=new double[n];
if(scelta==1){
i_shapley f(q,p,n);
ind=f.s_indice();
cout<<endl<<"Indice Shapley"<<endl;
for(int i=0;i<n;i++) cout<<"Giocatore "<<i+1<<": "<<ind[i]<<endl;
rielabora_dati::salva_dati(p,ind,n,scelta);
}
if(scelta==2){
i_coleman b(q,p,n);
cout<<endl<<"Indice Banzhaf"<<endl;
indice= b.banzhaf();
for(int i=0;i<n;i++) cout<<"Giocatore "<<i+1<<": "<<indice[i]<<endl;
rielabora_dati::salva_dati(p,indice,n,scelta);
55
}
else if(scelta==3){
i_coleman f(q,p,n);
cout<<endl<<"Indice di Coleman"<<endl;
ind=f.c_indice();
for(int i=0;i<n;i++) cout<<"Giocatore "<<i+1<<": "<<ind[i]<<endl;
rielabora_dati::salva_dati(p,ind,n,scelta);
}
end=clock(); tempo=((double)(end-start))/CLOCKS_PER_SEC; time_t
tm(0);
cout<<endl<<"Cpu time = "<<tempo<<endl;
delete[] ind,p,indice;
cin.get();
cin.get();
}
56
Riferimenti bibliografici
[1] J.M Bilbao, J.R Fernandez, N. Jiminez, J.J Lopez Voting power in the European Voting
Enlargement, European Journal of Operational Research, 143, 181-196, Settembre 2001.
[2] J.M Bilbao, J.R Fernandez, N. Jiminez, J.J Lopez Generating Functions for Computing
Power Indices Efficiently, Top 8, 2, 191-213, 2000.
[3] T.Cormen, C.Leiserson, R.Rivest Introduzione agli algoritmi, Jackson Libri,1994.
[4] Daoqi Yang C++ and Object-Oriented Numeric Computing, Springer-Verlag, 2001.
[5] F. Bellotti, G.Gambarelli Sistemi Elettorali e Teoria dei Giochi, Progetto Alice, 4, 25-34,
2001.
[6] D. Leech Computation of Power Indices, Warwick Economic Research Paper, 644, Luglio
2002
[7] D.Leech Designing the Voting Sistem for the Council of the European Union, Warwick
Economic Research Paper, 587, Agosto 2001.
[8] R. Lucchetti Di Duelli, Scacchi e Dilemmi, Paravia Bruno Mondadori, 2001
[9] A.Nijenhuis, E.S.Wilf Combinatorial Algorithms for Computer and Calculators ,
Academic Press, 1978.
[10] T.Matsui, Y.Matsui A Survay of Algorithms for Calculating Power Indices of Weighted
Majority Games, Journal of Operations Reserch Society of Japan, 43, 71-86, 2000.
[11] F.Patrone Decisori (Razionali)Interagenti, Edizioni Plus, Pisa University Press,
Febbraio 2006.
57