Modelli di gestione e loro relazione con la progettazione di reti metropolitane
L.Aligata, F.Barbieri, V.Fragnelli, A.Repetto, G.Resta
Abstract
Mediante la ricerca operativa è possibile valutare il costo minimo di un servizio
di trasporto soddisfacente un determinato fabbisogno. In generale il servizio è funzione di variabili di progetto e di
gestione. Un modello di gestione ottimale permette di ridurre il problema a quello dei soli costi associati alle
caratteristiche del progetto, nell'ipotesi che gli impianti vengano poi effettivamente così gestiti. La metodologia messa
a punto permette, a partire dalla topologia della linea, dalle caratteristiche dei mezzi mobili a disposizione e dalla
conoscenza di una matrice origini-destinazioni relativa ai passeggeri di individuare attraverso una serie di prove il
numero di treni strettamente necessario a soddisfare le esigenze dell'utenza ed il loro orario. Si minimizza una funzione
che descrive la velocità media degli utenti in dipendenza del cadenzamento tra i convogli alle varie stazioni e dei tempi
di attesa dei viaggiatori in banchina.
I vincoli imposti riguardano le capienze dei treni, il rispetto del segnalamento ed il numero di persone in attesa di
servizio presenti in banchina. Viene inoltre fatto il confronto tra i risultati così ottenuti e i sistemi gestionali
normalmente utilizzati.
Vengono illustrati in maniera grafica i vantaggi di tipo economico che si possono ottenere usufruendo di questo tipo di
gestione più flessibile e più rispondente alle esigenze dell'utenza. Questo modello è stato applicato a titolo di esempio
al prolungamento della linea B della metropolitana di Roma, attualmente in progetto: è stata ipotizzata una necessità di
trasporto congruente con lo studio preliminare in proposito condotto dalla STEFER.
Alcuni metodi per la risoluzione dell'orario degli equipaggi di una compagnia aerea
V.Fragnelli
Abstract
Si esamina il problema dell'orario degli equipaggi di una compagnia aerea. Partendo dalla conoscenza dell'orario dei
voli, della copertura degli stessi mediante gli aerei e del numero di equipaggi, si cerca una tabella che determini i turni
di ogni equipaggio nel corso di un mese, avendo come vincoli le normative legali sulle ore di volo e di riposo dei membri
dell'equipaggio. Si analizzano differenti filosofie e metodologie ed alcuni algoritmi di risoluzione. Alcune brevi
considerazioni concludono il lavoro.
Alcuni metodi di minimizzazione monodimensionale
V.Fragnelli
Abstract
Si analizzano alcuni metodi delle eliminazioni successive (Fibonacci, sezione aurea, dicotomia) ed alcuni metodi delle
approssimazioni polinomiali utili nella minimizzazione monodimensionale.
Un modello di servizio in sede completamente protetta per una richiesta deterministica
V.Fragnelli
Abstract
Una richiesta di trasporto di elevata intensità può essere soddisfatta solo utilizzando linee di trasporto in sede
completamente protetta. Si espone un modello deterministico che fornisce l'orario ottimale partendo dalla conoscenza della
topologia della linea, delle caratteristiche dei mezzi a disposizione e di una matrice origini-destinazioni. Si minimizza
una funzione che lega la velocità media degli utenti ai cadenzamenti e alle attese, ponendo come vincoli le capienze, il
rispetto della sicurezza e la limitazione alle attese dei passeggeri. La suddivisione della giornata in fasce orarie
suggerisce di utilizzare questo modello, che richiede una conoscenza molto raffinata della richiesta di servizio, per la
risoluzione dei problemi di raccordo tra le fasce orarie e di assorbimento di perturbazioni della richiesta.
Alcune possibili scelte gestionali per un servizio di trasporto su sede completamente protetta
V.Fragnelli, C.Magagnoli, G.Resta
Abstract
La gestione di una linea di trasporto su sede completamente protetta, in un periodo caratterizzato da richiesta di
trasporto costante, è comunemente effettuata disponendo di poche informazioni relative alla richiesta di servizio.
Personale impiegato, numero di vetture utilizzate, cadenzamento imposto, consumo energetico associato, flessibilità del
servizio rispetto a variazioni della richiesta, dipendono comunque da scelte gestionali, oltre che dalla richiesta di
trasporto. Differenti scelte privilegiano, di volta in volta, l'utenza, il personale,il consumo energetico e la
flessibilità.
Interperiodal Relations Allow Disintegration in Characteristic and Transitional Periods
of the Daily Schedule of a Completely Protected Line
V.Fragnelli
Abstract
Si analizzano le caratteristiche del problema dell'orario giornaliero di un servizio di trasporto in sede completamente
protetta. La suddivisione della giornata in fasce orarie suggerisce di differenziare i problemi concernenti i periodi di
regime interni a ciascuna fascia da quelli concernenti i periodi di transizione tra le fasce; i periodi di regime possono
essere descritti con un modello semplice, mentre per i periodi di transizione risulta più utile un modello più sofisticato
che consente una maggiore flessibilità. Viene presentata una filosofia di risoluzione che, riferendosi al metodo del
simplesso ricorsivo, permette di suddividere il problema in sottoproblemi relativi o a periodi di regime o a periodi di
transizione, legati da relazioni interperiodali.
Metodi per il prodotto di matrici sparse per vettori su array processor
V.Fragnelli
Abstract
Si espongono alcuni metodi per la realizzazione del prodotto tra una matrice sparsa ed un vettore denso per un array
processor. Partendo da un'idea di Parkinson si espongono e si confrontano alcuni metodi che sono stati sviluppati e che
richiedono una strutturazione della matrice. In particolare si esaminano una struttura derivante dalle tecniche di graph
colouring, una struttura a diagonali ed una struttura a banda. Questi algoritmi si rivelano molto efficienti nella maggior
parte dei casi. Si espone infine un metodo di Resta che considera matrici con struttura a blocchi ricorsiva e si propongono
alcune generalizzazioni di questo metodo.
L'esposizione è integrata da alcuni algoritmi e subroutine in DAP Fortran per i metodi esposti.
Architetture di processori per il prodotto di una matrice a banda per vettori
V.Fragnelli
Abstract
Si analizza il problema del prodotto di una matrice a banda per un vettore. Viene sviluppato un algoritmo ad elevato
parallelismo e di notevole efficienza, insieme con le strutture dati necessarie. L'algoritmo sviluppato può essere
orientato ad un elaboratore sequenziale, ad un vector processor o ad un array processor. Si richiama il concetto di grafo
di architettura dato da Preparata e si determina una architettura su cui è possibile effettuare il prodotto nel modo più
efficiente possibile, detta mesh of trees. Si introduce la definizione di architettura minimale e si verifica che il mesh
of trees è minimale per il prodotto destro e sinistro di una matrice a banda per un vettore. Si prova che il mesh semplice,
l'architettura tipica degli array processor, emula il mesh of trees per il prodotto matrice a banda per vettore. Alcuni
algoritmi in DAP Fortran sono esposti in Appendice.
An Algorithm for Structuration and Solution of Large Scale Problems Oriented to the Organisation and Management of Transportation Services
V.Fragnelli, G.Resta
Abstract
L'orario di una linea in sede completamente protetta può essere determinato automaticamente in modo ottimale rispetto
ad un dato obiettivo. La descrizione del sistema di trasporto, dell'obiettivo, della richiesta di servizio e dei costi
energetici e del personale può essere molto accurata o meno. In ogni caso viene tenuto conto dell'impatto della richiesta
di trasporto sul servizio. Questo risultato viene raggiunto con un modello di programmazione lineare strutturato che
utilizza le tecniche di dissezione nidificata per identificare la struttura e la cooperazione gerarchica per risolvere il
problema. Entrambe le tecniche consentono calcoli altamente concorrenti se si utilizza un supercomputer. Problemi di
dimensioni maggiori possono essere risolti con le stesse tecniche, ad esempio l'orario per una rete di trasporto e la
progettazione ottimale di un sistema di trasporto, dei quali il problema qui considerato costituisce un sottoproblema.
Architectures for Sparse Band Matrix Dense Vector Multiplication
V.Fragnelli
Abstract
Un algoritmo ad elevato parallelismo e di notevole efficienza per la moltiplicazione di una matrice sparsa a banda per
un vettore denso e le relative strutture dati vengono presentate in tre versioni orientate ad un elaboratore sequenziale,
ad un vector processor e ad un array processor. Riferendosi alla definizione di Preparata di grafo di architettura il mesh
of trees risulta un grafo di architettura molto efficiente e minimale per il problema dato e si prova che può essere
emulato dal mesh semplice. Il mesh of trees può essere utilizzato anche per matrici con struttura a diagonali e
generalizzato alle matrici rettangolari.
Rimedi al degrado di una linea
V.Fragnelli, G.Garbarini, P.Garrone, F.Questa, G.Resta, C.Scatilazzi
Abstract
Si considera una linea di trasporto in sede completamente protetta in condizione di degrado, cioè in cui uno dei due
sensi di marcia non è completamente utilizzabile, per una qualsiasi causa. Tenendo conto dell'entità del degrado si possono
determinare gestioni banalizzate, cioè che utilizzano un tratto di linea a senso alternato, che limitano il disagio per
gli utenti. Stime del comportamento dei passeggeri e dei treni e del disagio si possono ottenere con l'ausilio di modelli
simulativi e gestionali, che forniscono anche indicazioni sui nuovi valori da utilizzare per i parametri di gestione. Tali
modelli possono essere utilizzati anche in fase di progetto per realizzare la linea in modo da consentire una buona
gestione del servizio anche in caso di degrado.
Consumo energetico contro efficienza del servizio in una linea protetta
L.Canepa, V.Fragnelli, G.Resta
Abstract
La determinazione dell'orario giornaliero relativo ad una linea di trasporto in sede protetta si presenta come un
problema di grandi dimensioni. Tuttavia è possibile una opportuna suddivisione del problema al fine di semplificare la
soluzione operando su sottoproblemi. L'analisi dell'andamento della richiesta di trasporto nell'arco della giornata
evidenzia la presenza di fasce orarie caratterizzate da differente richiesta di servizio all'interno delle quali la
richiesta di servizio risulta stabile. Si possono differenziare due tipi di problemi, i primi relativi ai periodi di
richiesta stabile, nei quali i treni mantengono un comportamento omogeneo e i secondi relativi ai periodi di transizione
da una fascia alla successiva, nei quali i treni hanno comportamenti differenziati al fine di adeguarsi alle condizioni
proprie della fascia successiva. Dopo aver risolto i problemi relativi ai periodi di richiesta stabile si utilizzano i
valori ottenuti come condizioni al contorno che determinano il comportamento del primo e dell'ultimo treno dei periodi di
transizione. Viene descritta una semplice metodologia di esecuzione sequenziale che risolve completamente il problema.
Cadenzamento, soste e tempi di percorrenza in risposta alla richiesta di trasporto
V.Fragnelli
Abstract
Si illustra una procedura di studio di un sistema di trasporto metropolitano riguardante la determinazione del
cadenzamento, dei tempi di sosta e dei tempi di percorrenza in dipendenza della richiesta di trasporto specificata sotto
forma di matrice origine-destinazione o di flussi entrata-uscita. I tempi di sosta sono calcolati in modo tale da
permettere la discesa e la salita dei passeggeri interessati. I tempi di percorrenza sono calcolati in maniera tale da
mantenere entro limiti ragionevoli il rapporto tra tempi di viaggio e consumi associati. La gestione risultante può essere
considerata innovativa nel senso che si permette ai convogli di adeguare la velocità al numero di occupanti. Il
cadenzamento viene determinato in modo da controllare il rapporto tra tempo di attesa e tempo di viaggio in quanto per il
viaggiatore medio risulta indistinguibile una situazione caratterizzata da maggiore cadenzamento e minore velocità. Le
variabili sono determinate in modo tale da permettere di assorbire variazioni impreviste della richiesta compensando una
sosta più prolungata con una maggiore velocità del convoglio nel tratto successivo.
Implementazione sul Burroughs B6810 di un codice di ottimizzazione di una linea di trasporto in sede protetta
V.Fragnelli
Abstract
Viene presentata una versione del codice di ottimizzazione per una linea di trasporto in sede protetta implementata
sull'elaboratore Burroughs B6810 disponibile presso il Centro di Calcolo dell'Università di Genova. Tale versione utilizza
la libreria Optima Package del Numeric Optimisation Centre dell'Hatfield Polytechnic.
Gestione del degrado di una linea in sede protetta e gestore di una linea integrabile col simulatore TRANSLIN
M.Bisio, V.Fragnelli, G.Resta
Abstract
La memoria si divide in due parti, la prima dedicata ai risultati relativi alla gestione di una linea in sede protetta
in condizioni di degrado, cioè in cui uno dei due sensi di marcia non è completamente utilizzabile per una qualsiasi causa,
e la seconda dedicata a un progetto di ricerca da condurre con altre Unità Operative del Progetto Finalizzato Trasporti.
Nella prima parte vengono presentati diagrammi e figure corrispondenti a differenti politiche di gestione del degrado di
una linea di trasporto e vengono date indicazioni su alcuni programmi di calcolo che permettono di ottenere tali politiche.
Nella seconda parte viene presentato un progetto di ricerca che deriva dalla integrazione di contributi mutuamente
complementari da parte delle Unità Operative dell'Istituto di Matematica dell'Università di Genova, del Dipartimento di
Energia Elettrica dell'Università di Roma La Sapienza e della Transystem Trasporti Intermodali di Milano. Il risultato
finale di tali ricerche integrate sarà un simulatore in grado di fornire informazioni estremamente dettagliate riguardo ai
regimi elettrici istantanei e alla posizione, velocità ed accelerazione dei convogli, utilizzando in input informazioni
sulla linea e sulla richiesta di trasporto.
Simulazione di un controllo semaforico con preferenziamento al mezzo pubblico
F.Boero, P.Chiappini, V.Fragnelli, A.Miraglia, A.Repetto, G.Resta
Abstract
Viene presentato un modello simulativo semplificato di traffico che permette di descrivere agevolmente anche sistemi di
traffico complessi, al fine di valutare parametri relativi al traffico pubblico e privato. Utilizzando tale modello vengono
simulate e confrontate diverse strategie di controllo dei semafori che permettono di dare il preferenziamento ai mezzi
pubblici. Le strategie analizzate operano variando i tempi di rosso e di verde. L'utilizzo dei semafori con priorità
consente di limitare l'influenza del traffico privato sul servizio pubblico, uniformando i tempi di percorrenza e
migliorando la regolarità del servizio. Il modello permette di valutare i vantaggi per il trasporto pubblico e gli
svantaggi per il traffico privato. Vengono infine analizzati il caso di una direttrice di traffico a senso unico, con
corsia riservata agli autobus, intersecata da strade secondarie a senso unico percorse da traffico privato per studiare
l'impatto sul traffico non privilegiato delle strade secondarie e il caso di una arteria di grande traffico a doppio senso,
con corsia riservata agli autobus, per studiare le reazioni del traffico privato alle richieste
di priorità nelle due direzioni.
An ABS Method for Solving Suitably Structured Linear Systems Is Supported by Parallel Architectures
V.Fragnelli, G.Resta
Abstract
Viene presentato un algoritmo basato su un metodo della classe di Abaffy-Broyden-Spedicato. Il sistema lineare da
risolvere può essere sparso e in questo caso deve avere una struttura policromatica sulle righe. Vengono dati suggerimenti
per utilizzare l'alto grado di libertà della classe. Opportune strutture dati riducono i tempi di calcolo e l'occupazione
di memoria. L'algoritmo presenta un alto grado di parallelismo. Viene analizzata la complessità computazionale
dell'algoritmo e vengono esaminate le architetture parallele in grado di supportare l'algoritmo.
Un monitor a Video-Disco per il rilevamento della richiesta di trasporto
V.Fragnelli, G.Resta
Abstract
La conoscenza di una stima della richiesta di trasporto in un servizio pubblico è essenziale in fase di progettazione
per il dimensionamento delle strutture. Durante la fase di gestione, per far fronte a nuove esigenze dell'utenza, tali dati
devono essere aggiornati utilizzando tecniche economiche, rapide e affidabili. Il metodo presentato si avvale di monitor
collegati ad un video-disco e consente un aggiornamento dei dati on-line, tramite confronto delle immagini reali con quelle
che simulano diverse situazioni di affollamento dei convogli e delle banchine. La rapidità di questo metodo consente di
utilizzare i dati anche al fine di modificare i tempi di percorrenza e di sosta per far fronte a variazioni improvvise e
temporanee della richiesta di servizio.
Una realta' artificiale per rappresentare una linea di trasporto su sede protetta
G.D'Atri, V.Fragnelli, G.Resta
Abstract
Simulatori numerici permettono di valutare indici di prestazioni di una linea di trasporto su sede protetta.
L'interpretazione e la validazione dei risultati ottenuti, d'altronde comunemente richiedono un pesante background
ingegneristico-informatico. Recenti risultati nel settore della tecnologia dei media consentono un'interazione più
orientata ad un utenza non informatizzata. In questo lavoro si applicano tali tecniche al problema di stima e aggiornamento
della domanda. Stime della richiesta di trasporto in un servizio pubblico sono utilizzate in fase di progettazione, per il
dimensionamento delle strutture. Durante la fase di gestione, per far fronte a nuove esigenze dell'utenza, tali dati devono
essere aggiornati utilizzando tecniche economiche, rapide e affidabili. Una rappresentazione con dati semplici permette di
realizzare gli obiettivi prefissati di economicità rapidità e affidabilità. Una tecnica semiautomatica utilizza le
potenzialità esplorative di personale appositamente istruito con riferimento alla valutazione della richiesta di trasporto.
Un simulatore numerico di linee metropolitane
A.Capasso, V.Fragnelli, R. Lamedica, G.Meregalli, B.Perniceni, G.Resta, L.Torriani, S.Vimercati
Abstract
Si presentano i risultati di una ricerca pluriennale, nell'ambito del Progetto Finalizzato Trasporti del Consiglio
Nazionale delle Ricerche (Sottoprogetto II), sviluppata in collaborazione fra Unità Operative universitarie (Università di
Roma La Sapienza e Genova) e Unità Operative industriali (Transystem di Milano). La ricerca è consistita nell'impostazione
teorica, sviluppo, implementazione, documentazione e test di un modello integrato di simulazione di una linea di trasporto
metropolitano. Sono in particolare evidenziati gli aspetti metodologici e modellistici che sono alla base della procedura
realizzata e che costituiscono, sia nella formulazione che nell'applicazione, gli elementi di maggiore originalità della
ricerca.
Esercitazioni di Ricerca Operativa
L.Cantoni, V.Fragnelli
Sommario
Raccolta di esercizi svolti, proposti durante il corso di Ricerca Operativa e come prove di esame.
Extensions of linear operators from hyperplanes of l(n)¥
M.Baronti, V.Fragnelli, G.Lewicki
Abstract
Let Y Ì l(n)¥ be a hyperplane and let A
Î L(Y) be given. Denote A = {L Î L(l(n)
¥,Y):L | Y = A} and
lA = inf{||
L ||: L Î A}. In this paper the problem of
calculating of the constant lA is studied. We present a complete characterization of
those A Î L(Y) for which lA
= ||A ||.
Next we consider the case lA > |
|A ||. Finally some
computer examples will be presented.
Giochi su Reti
V.Fragnelli
Sommario
GRAFI: Definizioni e rappresentazioni.
RETI: Definizioni.
PROBLEMI DI RETI E ALGORITMI: Problema del flusso massimo (max flow-min cut) - Problema del cammino
minimo (SPP) - Problema del minimo spanning tree (SST) - Problema di routing (Commesso viaggiatore - TSP) - Project
Evaluation & Review Technique (PERT).
GIOCHI SUGLI ARCHI E SUI NODI
RIFORMULAZIONE IN TERMINI DI GIOCO: Flow Game - Shortest Path Game - Minimum Cost Spanning Tree Game - Minimum
Cost Forest Game - Spanning Network Game - Fixed Routing Game - Traveling Salesman Game - PERT Game.
RISULTATI: Un gioco totalmente bilanciato è equivalente ad un flow game - Nucleo e
nucleolo di un minimum cost spanning tree game - Nucleo di un minimum cost forest game - Un gioco monotono è equivalente
ad uno spanning network game - Nucleo di un fixed routing game - Nucleo e equa ripartizione di un traveling salesman game
I - II - Nucleo di un NTU game (PERT game) - Grafi e cooperazione.
Balancedness of Infrastructure Cost Games
H.Norde, V.Fragnelli, I.Garcia-Jurado, F.Patrone, S.Tijs
Abstract
In this paper we study the class of infrastructure cost games. A game in this class models the infrastructure costs
(both building and maintenance) produced when a set of users of different types makes use of a certain infrastructure,
which may consist of several facilities. Special attention is paid to one facility infrastructure cost games. Such games
are modeled as the sum of an airport game and a maintenance cost game. It turns out that the core and the nucleolus of
these games are very closely related to the core and nucleolus of an associated generalized airport game. Furthermore we
provide necessary and sufficient conditions under which an infrastructure cost game is balanced.
Giochi a utilità non trasferibile (NTU Games)
G.Ferrari, V.Fragnelli, M.Margiocco
Sommario
Introduzione - Giochi bilanciati - Convessità - Valori
(Il lambda-transfer value. Una assiomatizzazione del lambda-transfer value. Il concetto di soluzione di Harsanyi. Un
classico esempio di Roth.).
Balanced Games Arising from Infinite Linear Models
V.Fragnelli, F.Patrone, E.Sideri, S.Tijs
Abstract
Kalai and Zemel introduced a class of flow-games showing that these games have a non-empty core and that a minimum cut
corresponds to a core allocation.We consider flow-games with a finite number of players on a network with infinitely many
arcs: assuming that the total sum of the capacities is finite, we show the existence of a maximum flow and we prove that
this flow can be obtained as limit of approximating flows on finite subnetworks.Similar results on the existence of core
allocations and core elements are given also for minimum spanning network models (see Granot and Huberman) and
semi-infinite linear production models (following the approach of Owen).
How to Share Railways Infrastructure Costs?
V.Fragnelli, I.Garcia-Jurado, H.Norde, F.Patrone, S.Tijs
Abstract
In this paper we propose an infrastructure access tariff in a cost allocation problem arising from the reorganization
of the railway sector in Europe. To that aim we introduce the class of infrastructure cost games. A game in this class is
a sum of airport games and what we call maintenance cost games, and models the infrastructure costs (building and
maintenance) produced when a set of different types of trains belonging to several agents makes use of a certain
infrastructure. We study some properties of infrastructure cost games and provide a formula for the Shapley value of a
game in this class. The access tariff we propose is based on the Shapley value of infrastructure cost games.
On Shortest Path Games
V.Fragnelli, I.Garcia-Jurado, L.Mendez-Naya
Abstract
A class of cooperative TU-games arising from shortest path problems is introduced
and analyzed. Some conditions under which a shortest path game is balanced are
obtained. Also an axiomatic characterization of the Shapley value for this class of games is provided.
Tree-Connected Peer Group Situations and Peer Group Games
R.Branzei, V.Fragnelli, S.Tijs
Abstract
A class of cooperative games is introduced which arises from situations in which a set of agents is hierarchically
structured and where potential individual economic abilities interfere with the behavioristic rules induced by the
organization structure. These games form a cone generated by a specific class of unanimity games, namely those based on
coalitions called peer groups. Different economic situations like auctions, communication situations, sequencing situations
and flow situations are related to peer group games. For peer group games classical solution concepts have nice properties.
Two Approaches to the Problem of Sharing Delay Costs in Joint Projects
R.Branzei, G.Ferrari, V.Fragnelli, S.Tijs
Abstract
This paper concentrates on cost sharing situations which arise when delayed joint projects involve joint delay costs.
The problem here is to determine "fair" shares for each of the agents who contribute to the delay of the project such that
the total delay cost is cleared. We focus on the evaluation of the responsibility of each agent in delaying the project
based on the activity graph representation of the project and then on solving the important and complicated problem of the
delay cost sharing among the agents involved. Two approaches, both rooted in cooperative game theory methods are presented
as possible solutions. In the first approach delay cost sharing rules are introduced which are based on the delay of the
project and on the individual delays of the agents who perform activities. This approach is inspired by the bankruptcy and
taxation literature and leads to five rules: the constrained equal contribution rule, the (truncated) proportional rule
and the (truncated) constrained equal reduction rule. By introducing two coalitional games related to delay cost sharing
problems, which we call the pessimistic delay game and the optimistic delay game, also game theoretical solutions as the
Shapley value, the nucleolus and the tau-value generate delay cost sharing rules. In the second approach the delays of the
paths in the activity graph together with the delay of the project play a role. A two-stage solution is proposed. The first
stage can be seen as a game between paths, where the delay cost of the project has to be allocated to the paths. Here
serial cost sharing methods play a role. In the second stage the allocated costs to each path are divided proportionally
w.r.t. the individual delays among the activities in the path.
On the Computation of the Nucleolus of Line-Graph Peer Group Games
R.Branzei, V.Fragnelli, S.Tijs
Abstract
Line-graph peer group games are coalitional games modelling economic situations in which agents with potential
individual economic possibilities are connected via a chain-like hierarchy within an organization. We focus on the
nucleolus of such games. Formulae for computing the nucleolus of small games are provided and an iterative algorithm for
the case with more than four agents involved is designed and analysed.
A Note on Bus Games
V.Fragnelli, I.Garcia-Jurado, L.Mendez-Naya
Abstract
In this paper we identify and analyse a new class of cost allocation problems: the bus games. We study under what
conditions a cost allocation problem in this class has a core allocation.
Tikhonov Well-posedness for the Nucleolus
V.Fragnelli, F.Patrone, A.Torre
Abstract
We study Tikhonov well posedness for the nucleolus (a kind of solution for cooperative games introducted from
Schmeidler). This kind of well-posedness is not trivial, because the nucleolus is the minimum for a preorder defined using
the lexicographic order, and it is well known that the lexicographic order is not representable by a utility function and
it is not continuous w.r.t. the euclidean topology.
An Envy-Free Procedure for an Insurance Problem
V.Fragnelli, M.E.Marina
Abstract
We consider a random variable R, representing a risk that has to be insured by n companies and which a premium
P is assigned to. How should they share the risk and the premium in order to be better off?
We suppose that every company i expresses her valuation of a random variable X as the real number Hi(X). Under
suitable hypotheses on the functionals Hi, there exists an optimal decomposition of the risk. According to this
division, we develop a fair division procedure, that guarantees an envy-free division of the premium P and of the risk R.
Fair Division
V.Fragnelli, M.E.Marina
Sommario
Il problema della divisione tra più persone di una torta eterogenea o più in generale quello della divisione di uno o
più beni (divisibili o meno) è stato discusso da più autori. Una approfondita esposizione di tale argomento è stata fatta
in Brams e Taylor (1996, 1999).
Seguendo tali autori una procedura di “fair division” richiede che la soluzione sia almeno proporzionale e poi
che soddisfi alcune altre proprietà quali: assenza di invidia, equità,efficienza.
In questa esposizione vogliamo dare una breve rassegna degli aspetti più significativi del problema e delle procedure
di risoluzione.
On the Balancedness of Semi-infinite Sequencing Games
V.Fragnelli
Abstract
In this paper we analyse under which conditions a sequencing game with infinite number of jobs owned by a finite number
of players is balanced. We define the class of the multiple-job sequencing games, i.e. when each player may own more than
one job and extend the previous results to this situation. Finally we introduce the semi-infinite sequencing games, i.e.
multiple-job sequencing games with infinitely many jobs but finite number of players, and show that under suitable
hypotheses they are balanced.
Environmental Pollution Risk and Insurance
V.Fragnelli, M.E.Marina
Abstract
We consider environmental risks that are evaluated too much heavy for a single insurance company, but they can be
insured by n companies which a premium is assigned to.
This is precisely the Italian scenario where a pool of companies co-insures these risks.
Under a game theoretic approach we start by analyzing how they should split the risk and the premium in order to be
better off. Under suitable hypotheses, there exists an optimal decomposition of the risk, that allow us to define a
cooperative game whose properties and some particular solutions are analysed.
Cost Allocation Problems: An Application of Game Theory
V.Fragnelli
Abstract
Joint cost allocation problems arise in many economic situations, public services, networks, and so on. Fairness
criteria, firstly stated in the so-called Tennessee Valley Authority problem, lead to a strong connection with game
theory. Having this in mind we propose possible interactions of game theory and operations research, in order to help
decision processes.
Profit Sharing in Enterprises
V.Fragnelli, M.E.Marina
Abstract
We consider a problem in which a set of agents have to carry out an enterprise; if they succeed in performing it they
have to pay a cost, but they receive a benefit. In our situation the cost depends on the agents involved, while the
benefit is fixed.
We may refer to connection situations where the objective and the benefit is the connection of two different nodes and
the cost is the minimum cost connection. Other situations matching our hypotheses arise in production and bankruptcy
problems. The model fits also insurance situations where a set of companies may reduce the costs sharing the risk, but the
premium is fixed.
We want to investigate how the agents may share the benefit, taking into account their charges of the costs, so we
analyze some classical solution concepts and properties the value of the benefit varies.
A Simulative Approach to the Choice of the Electoral System
V.Fragnelli, G.Monella, G.Ortona
Abstract
The evaluation of an electoral system is not an easy task. In this paper we analyze two different aspects of the
problem. First, we present a method for selecting the "best" system with reference to two parameters, the
representativeness and the governability. Second, we suggest an additional way to assess the representativeness of an
electoral system.
Co-Insurance Games and Environmental Pollution Risk
V.Fragnelli, M.E.Marina
Abstract
We consider risks that are evaluated too much heavy for a single insurance company, but they can be insured by
n companies which a premium is assigned to, as it happens with the environmental risks.
This is precisely the Italian scenario where a pool of companies co-insures this last kind of risks.
We use a game theoretical approach to analyze how the companies should split the risk and the premium in order to
be better off. Under suitable hypotheses, there exists an optimal decomposition of the risk, that allow us to define a
cooperative game whose properties and some particular solutions are analyzed.
Game Practice and the Environment - Proceedings of the International Meeting held in Alessandria on 12-13 April 2002
C.Carraro, V.Fragnelli (Editors)
Table of contents and Introduction
GAME PRACTICE AND THE ENVIRONMENT
edited by Carlo Carraro and Vito Fragnelli
Introduction - Carlo Carraro and Vito Fragnelli
PART I: CLIMATE NEGOTIATIONS AND POLICY
1. Stable International Agreements on Transfrontier Pollution with Ratification Constraints
S. Currarini and H. Tulkens
2. Can Equity Enhance Efficiency? Some Lessons from Climate Negotiations
F. Bosello, B. Buchner, C. Carraro and D. Raggi
3. Endogenous Strategic Issue Linkage in International Negotiations
C. Carraro and C. Marchiori
4. Kyoto and Beyond Kyoto Climate Policy: Comparison of Open-Loop and Feedback Game Outcomes
J.C. Císcar and A. Soria
PART II: SHARING ENVIRONMENTAL COSTS
5. Cost Sharing in a Joint Project
S. H. Tijs and R. Brânzei
6. A Model for Cooperative Inter-Municipal Waste Collection: Cost Evaluation toward Fair Cost Allocation.
S. Moretti
7. Co-Insurance Games and Environmental Pollution Risk
V. Fragnelli and M.E Marina
8. Environmental Effects of Consumption: an Approach Using Dea and Cost Sharing
H. Keiding
PART III: ENVIRONMENTAL MANAGEMENT AND POLLUTION CONTROL
9. Competition and Cooperation in Natural Resources Exploitation: An Evolutionary Game Approach.
G.I. Bischi, F. Lamantia and L. Sbragia
10. Greenhouse Gases, Quota Exchange and Oligopolistic Competition
S. D. Flåm and O. Godal
11. A Conjectural Cooperative Equilibrium for Strategic Form Games
S. Currarini and M. Marini
INTRODUCTION
Carlo Carraro, University of Venice and FEEM
Vito Fragnelli, University of Eastern Piedmont
Game theory is one of the most useful mathematical tools that economists and mathematicians have been using to deal with
complex economic and policy problems. At the same time, environmental issues are at the heart of many domestic and
international policy processes, where interactions among different stakeholders play a crucial role. It is therefore natural
to adopt game theory as one of the analytical instruments that can enhance our understanding of the interrelations between
the economy and the environment, and that can also provide practical suggestions for policy interventions.
The existing literature on game theory and the environment is vast (Cf. Carraro, 2002, 2003; Finus, 2001; Hanley and
Folmer, 1998; and many others). Therefore, when designing this book, and the conference where the chapters of this book have
been presented and discussed, the main questions were: What are the original features of the book? How does it differ from
the many books already published on the application of game theory to environmental matters?
Of course, each single chapter contains some innovative results that will be highlighted below. However, the design of
the book also contains some specific features that is worth mentioning. First, the book is the outcome of an interdisciplinary
work between economists and mathematicians. Some of the papers have been written by mathematicians who possess sophisticated
mathematical tools and look for an interesting environmental economic problem to apply them. Other papers have been written
by economists who look for adequate tools to deal with relevant policy issues. All papers are the outcome of the interactions
between these two groups of researchers, who helped each other through personal and on-line discussions and through the
reviewing process.
A second distinguishing feature of this book is the “practice” of game theory. The goal was indeed to induce the authors
to look for practical solutions to environmental problems and to use game theory to identify these concrete solutions.
Despite the fact that this second goal has not always been achieved by the papers in this book, it is clear, when reading
the various chapters, that there is a common denominator defined by the objective just described.
The book is divided into three parts. The first one is devoted to climate policy. This is one of the major environmental
problems and certainly one where game theory has been largely used, notable to assess the prospects of future climate
negotiations. This is also the main objective of the four chapters in Part I of the book. They all use game theory to
identify the incentives to sign an international climate treaty as a function of countries’ characteristics, political
institutions, policy strategies and future commitments. For example, Currarini and Tulkens recognise that international
agreements on climate change control require approval by domestic political institutions. Therefore, they employ a voting
game-theoretic model to characterise the stability of such agreements when each country's participation is conditioned upon
a domestic ratification vote. To describe the pre-treaty or no treaty international situation, they propose a concept of
(non-cooperative) political equilibrium and prove its existence. They then move to the diplomatic level, and employ a
coalition formation game to show that there exist cooperative joint policies, yielding a treaty, that are ratified by all
countries and that can be considered stable at the international level. The problem addressed in this chapter has been widely
neglected by the existing literature and this chapter actually provides a major innovation in the economic analysis of
climate change negotiations and international environmental agreements.
The second chapter, by Bosello, Buchner, Carraro and Raggi, addresses another neglected important issue, namely how
equity can influence the participation decision of countries that negotiate on climate change control. A widespread
conjecture suggests that a more equitable distribution of the burden of reducing emissions would enhance the incentives for
more countries - particularly big emitters - to accept an emission reduction scheme defined within an international climate
agreement. This chapter shows that this conjecture is only partly supported by the empirical evidence that can be derived
from the recent outcomes of climate negotiations. Even though an equitable sharing of the costs of controlling GHG emissions
can provide better incentives to sign and ratify a climate agreement than the burden sharing implicit in the Kyoto agreement,
a stable global agreement cannot be achieved. A possible strategy to achieve a global agreement without free-riding
incentives is a policy mix in which global emission trading is coupled with a transfer mechanism designed to offset
incentives to free ride.
Also the third chapter, by Carraro and Marchiori, is aimed to assess the validity of a practical policy proposal. In
particular, this chapter analyses issue linkage as a way to increase co-operation on environmental problems where the
incentives to free-ride are strong. The goal is to determine under what conditions players prefer to link negotiations on
two different economic issues rather than to negotiate on the two issues separately. Suppose that players are asked to vote
on issue linkage before starting negotiations. Under what conditions would they vote in favour of issue linkage? The answer
to this question is not trivial. Issue linkage may indeed increase the number of cooperators on the provision of a public
environmental good (a typical issue characterised by strong incentives to free-ride). However, at the same time, issue
linkage may reduce the number of cooperating players on the other economic issue which is linked to the provision of a
public good. Players therefore face a trade-off. This chapter analyses this trade-off within a game-theoretic framework and
shows under what conditions issue linkage is players’ equilibrium strategy.
The fourth chapter of part I, by Ciscar and Soria, has a more methodological flavour. Most studies assessing the Kyoto
Protocol on climate change have implemented a (simultaneous) single-stage game with an open-loop information structure, where
countries decide at once and at the same time their mitigation efforts for all future periods. Alternatively a (sequential)
multi-stage game can allow a player to react to past moves of the other players. The information structure of this second
game is called feedback. The goal of this chapter is to compare the outcomes under the open-loop and feedback frameworks. For
that purpose a numerical two-region (Annex B and non-Annex B countries) integrated assessment model of the economic and
climatic systems is coupled with a non-cooperative five-stage game. When the game is solved with utility payoffs, the
open-loop and feedback Nash equilibria provide very similar outcomes. With consumption payoffs, the outcomes are different.
Therefore, this chapter suggests that the information structure of the game may matter and must be carefully analysed.
The second part of the book is devoted to another important environmental and economic issue. How can stakeholders,
whether domestically or internationally, share the costs of undertaking emission abatement or more generally the cost of
environment-friendly activities? In this part, cost sharing methods are applied to different environmental problems and
practical answers to the above question are proposed.
In the first paper of part II, by Tijs and Branzei, a group of agents aims to work together in a joint project that can
have different forms. Each feasible form corresponds to a subset of a given set of basic units. The cost of the chosen
project is the sum of the costs of the basic units involved in the project. The benefit of each of the agents is dependent
on the form of the chosen project. A related cooperative game may be helpful in solving the question of how to share the
costs. Under certain conditions this game turns out to be a convex game. For structured joint projects also a flexible
procedure using cost sharing rules from the taxation literature applied to simple cost sharing problems is proposed. It is
worth noticing that many well-known cases in the cost sharing literature fit in the model proposed in this chapter and that
some earlier results are special cases of the results which are obtained in this chapter.
The second paper, by Moretti, focuses on sharing the cost of waste collection. Due to economies of scale imposed by the
need for specialist staff and facilities, inter-municipal cooperation can be very beneficial in achieving groupings with size
large enough to develop - at an affordable cost - a waste collection system suitable to the high standards demanded by EU
legislation. Moreover, municipalities want a cost allocation mechanism that is efficient, equitable and provides appropriate
incentives to cooperate. The aim of this chapter is to offer a model for ex-ante quantitative evaluation of specialist staff
and facilities (and their costs) required for supplying waste collection in new emerging contexts of inter-municipal
cooperation. A validation of the model on a real situation is also presented.
The third paper, by Fragnelli and Marina, proposes a framework to share environmental insurance costs. There are risks,
in particular environmental risks, that are too large and heavy for a single insurance company, but they can be insured by n
companies. This chapter uses a game-theoretic approach to analyse how the n insurance companies should split the risk and the
premium in order to be better off. Under suitable hypotheses, there exists an optimal decomposition of the risk, from which a
cooperative game can be defined and its properties and some particular solutions can be analysed.
In the final chapter of this part of the book, by Keiding, the environmental costs to be shared are those related to
consumption activities. For the assignment of environmental effects to activities, Keiding proposes to use the method of cost
allocation, applied to a multiple of different environmental impacts considered as different “costs”. This leads to a
consideration of vector cost allocation and its relation to ordinary one-dimensional cost allocation methods; in particular,
he considers the stability of cost sharing rules under composition of cost functions, a property which is important in the
application at hand. In addition, the author exploits the well-established methodology of DEA (Data Envelopment Analysis) in
order to aggregate vectors of environmental effects to a single index of relative environmental impact of a consumption
activity. An application of the last part of the approach is given, based on Danish national accounts data and using
emission data as a proxy for environmental effect.
The third part of the book deals with environmental management and pollution control. The first chapter in this third
part, by Bischi, Lamantia and Sbragia, proposes a dynamic model to describe the commercial exploitation, by a population of
strategically interacting agents, of a common property renewable resource. The population of players is assumed to be divided
into two groups: cooperators, that decide their harvesting policy by maximising the overall profit of their group, and
defectors, that just maximise their own profit. An evolutionary mechanism is introduced to describe how the share of
defectors and cooperators within the population changes over time. The chapter provides a qualitative study of a two
dimensional nonlinear dynamical system that describes the time evolution of the resource stock and the population share
between cooperators and defectors. The long run evolution of this dynamical system is analysed by analytical and numerical
methods, and the role of some economic and ecological parameters is investigated.
The second paper, by Flam and Godal, analyses emission trading in an oligopolistic market. Oligopolistic firms use
factor inputs that generate emissions of greenhouse gases. The producers are entitled to emission permits, and they exchange
parts of these. Each firm, when planning its net purchase of permits, anticipates the market clearing price. This chapter
models the clearing mechanism as a core solution of a transferable-utility production game. Agents may reckon that they
affect prices of products and permits. The existence and characterisation of the equilibrium is discussed.
The final chapter, by Currarini and Marini, presents a new cooperative equilibrium for strategic form games, denoted
Conjectural Cooperative Equilibrium (CCE). This concept is based on the expectation that joint deviations from any strategy
profile are followed by an optimal and noncooperative reaction of non deviators. The authors show that a CCE exist for all
symmetric supermodular games. Furthermore, they discuss the existence of a CCE in specific submodular games derived from the
environmental literature.
As a whole, the eleven chapters of this book improve our toolbox to deal with environmental issues and, at the same time,
provide some interesting applications and practical solutions to some relevant environmental policy problems. The work to
achieve this result has been long and difficult. All chapters have been reviewed twice and revised accordingly. All chapters
have been presented at a conference in Alessandria and there discussed and compared. The organisation of all this process has
been possible thanks to the financial and organisational support of the Fondazione Eni Enrico Mattei, of the University of
Eastern Piedmont and of “Ambiente, Territorio e Formazione”. The role of Alberto Cassone, vice Dean of the University of
Eastern Piedmont, and of Fabio Gastaldi, dean of the Faculty of Sciences, has also been very important to facilitate the
organisation of the Alessandria meeting. Special thanks also to Lucia Ceriani, Monica Eberle, Anna Iandolino and Giovanni
Monella for their help in the organisation of the meeting. All reviewers did an excellent job to enhance the quality of the
chapters. We are very grateful to them, as well as to all those who provided comments to earlier versions of the chapters of
this book.
References
Carraro, C. (2002), Governing the Global Environment, E. Elgar, Cheltenham.
Carraro, C. (2003), The Endogenous Formation of Economic Coalitions, E. Elgar, Cheltenham.
Finus, M. (2001), Game Theory and International Environmental Cooperation, E. Elgar, Cheltenham.
Hanley, N. and Folmer, H. (1998), Game Theory and The Environment, E. Elgar, Cheltenham.
A Cost Allocation Problem in Urban Solid Wastes Collection and Disposal
V.Fragnelli, A.Iandolino
Abstract
In this paper we consider a cost allocation problem arising in a consortium for urban solid waste collection and
disposal.
A classical allocation rule is the proportional division according to the volume of wastes collected; here we
propose a different allocation method, rooted in game theory, based on a model developed by Fragnelli et al. (1999),
using the Shapley Value and the Owen Value as allocation rules.
The model was applied to the data of the consortium Ovadese - Valle Scrivia, comparing our results and the
actual ones.
A Fair Procedure in Insurance
V.Fragnelli, M.E.Marina
Abstract
We consider a random variable R, representing a risk that has to be insured by n companies and which a
premium j is assigned to. How should they share the risk and the premium in order to be better
off? Under suitable hypotheses, there exists an optimal decomposition of the risk. According to this
division, we develop a procedure, that results in an allocation of (j, R) that is
efficient, individually rational and envy-free.
Teoria dei Giochi e Ottimizzazione
V.Fragnelli, R.Tadei
Sommario
Dopo aver richiamato le definizioni di base dei giochi cooperativi a utilità trasferibile e dei più comuni concetti
di soluzione, viene presentata una vasta classe di giochi, gli Operations Research Games che costituiscono la
naturale estensione dei problemi classici della Ricerca Operativa al caso in cui sono presenti pi\`u decisori.
Successivamente si esaminano le caratteristiche pi\`u interessanti di questa classe di giochi e infine si introduce un
approccio di Teoria dei Giochi ad un problema di telecomunicazioni wireless.
A Note on The Owen Set of Linear Programming Games and Nash Equilibria
V.Fragnelli
Abstract
In this paper we associate a strategic non-cooperative game to a linear programming game; we analyze the relations
between the core of the given game and the Nash equilibria of the strategic game.
Resolving an Insurance Allocation Problem: A Procedural Approach
D.Ambrosino, V.Fragnelli, M.E.Marina
Abstract
In this paper we study the problem of the determination of a fair allocation in a co-insurance problem, i.e. how some
insurance companies have to share the risk and the premium.
We develop two procedures that produce a proportional and an equitable allocation, respectively. The procedures are applied
to a real situation arising from environmental risk and the resulting allocations are compared with the classical quota
share allocation and with an envy-free allocation determined following a procedure presented by Fragnelli and Marina.
Operations Research Games
V.Fragnelli, R.Tadei
Sommario
In questo articolo viene presentata una vasta classe di giochi, gli Operations Research Games, che costituiscono la
naturale estensione dei problemi classici della Ricerca Operativa al caso in cui sono presenti più decisori, che
interagiscono fra di loro.
Si tratta di giochi cooperativi a utilità trasferibile.
Dopo aver richiamato le caratteristiche principali di tali giochi e dei concetti di soluzione più comuni, vengono
presentati alcuni esempi di Operations Research Games, quali i giochi di produzione, i giochi di connessione ed i giochi di
sequenziamento.
Abstract
In this paper we present a wide class of games, the so-called Operations Research Games, that are the natural
extension of classical Operations Research problems when many decision-makers interact.
We consider cooperative games with transferable utility.
After recalling the main features of this class of games and of the most usual solution concepts, three examples of
Operations Research Games - production games, spanning tree games and sequencing games - are presented.
Subscribing an Insurance Policy Is Gambling?
V.Fragnelli, M.E.Marina
Abstract
In a game theoretical environment it is possible to assign a measure of the skill required for winning in a casino game;
according to this measure we can state the relevance of skill and chance in an insurance contract, both for the insurance
company and for the insured.
Balancedness of the Class of Infinite Permutation Games and Related Classes of Games
V.Fragnelli, N.Llorca, S.Tijs
Abstract
Recently it is proved that all infinite assignment games have a non-empty core. Using this fact, and a technique
suggested by L.S. Shapley for finite permutation games, we prove similar results for infinite permutation games. Infinite
transportation games can be interpreted as a generalization of infinite assignment games. We show that infinite
transportation games are balanced via a related assignment game. By using certain core elements of infinite transportation
games it can be shown that infinite pooling games have a non-empty core.
Infinite Sequencing Games
V.Fragnelli, N.Llorca, S.Tijs
Abstract
Infinite sequencing situations where the number of jobs is countable infinite and the related cooperative TU games are
introduced. It is shown that these infinite games are convex games. Special attention is paid to some gain splitting rules.
Two of the resulting allocations turn out to be extreme points of the core.
Bankruptcy Problems and Minimum Cost Flow Problems
R.Branzei, G.Ferrari, V.Fragnelli, S.Tijs
Abstract
This paper represents classical bankruptcy problems as flow problems and also two new generalized bankruptcy problems.
Such a representation is useful to implement specific division rules from the bankruptcy literature via suitable cost
functions in a related minimum cost flow problem.
The Nucleolus Is Well-posed
V.Fragnelli, F.Patrone, A.Torre
Abstract
The lexicographic order is not representable by a real-valued function, contrary to many other orders or preorders. So,
standard tools and results for well-posed minimum problems cannot be used. We prove that under suitable hypotheses it is
however possible to guarantee the well-posedness of a lexicographic minimum over a compact or convex set.
This result allows us to prove that some game theoretical solution concepts, based on lexicographic order are well-posed:
in particular, this is true for the nucleolus.
Game Theoretic Analysis of Transportation Problems
V.Fragnelli
Abstract
This paper presents some game theoretical approaches to railway problems. The main topic is the definition of a fair
access fee to the European railway network, which matches the directives of the European Union.
Joint Project Management with Penalties and Compensations
R.Branzei, G.Ferrari, V.Fragnelli, S.Tijs
Abstract
In this paper we analyse joint projects in which some activities recover part of the current delay or speed up the
execution of the whole project. These activities can be entitled to a reward, as their good performances reduced the penalty
or led to an extra reward. Bankruptcy problems allow to find good allocation of penalties and rewards. We present some examples
of allocations using a communicating vessel representation.
On Cooperative Games Related to Market Situations and Auctions
R.Branzei, V.Fragnelli, A.Meca, S.Tijs
Abstract
We consider a market situation with two corners. One corner consists of a single seller with one object, and the other
corner consists of potential buyers who all want the object. We suppose that the valuations of the object for the different
buyers are known by all of them. Then two types of cooperative games, which we call market games and ring games,
corresponding to such market situations are considered.
Market games are related to special total big boss games, while ring games are related to special convex games, the
peer group games. It turns out that there exists a duality relation between the market game and the ring game arising from
the same two-corner market situation. For both classes of games relevant solution concepts are studied.
A Fair Tariff System for Water Management
V.Fragnelli
Abstract
Access to water will be one of the most challenging problems in the next years. It involves many aspects and in this
paper we consider the possibility of designing a fair tariff system in order to have also a good evaluation of the amount of
water that a community will need in a given period. Here, we analyze the situation in Italy, taking into account the law and
the consequent organization of the water management.
Particular emphasis is devoted to the truefulness and implementation aspects.
Game Theory as a Tool for Analyzing Terrorism
V.Fragnelli
Abstract
Terrorist attacks may have a deep impact on our society; for this reason it is necessary that all the disciplines give
their contribution for limiting its negative effects. In this note we want to show that Game Theory may be helpful for
studying some aspects of terrorism.
Comparison of Electoral Systems: Simulative and Game Theoretic Approaches
V.Fragnelli, G.Ortona
Abstract
Simulation may be a useful tool to address some basic problems concerning the choice of the electoral system. A case
study is analyzed as an example. The utility of including power indices is discussed. A simulation program is illustrated.
A Note on the Computation of the Shapley Value for von Neumann-Morgenstern Market Games
V.Fragnelli, A.Meca
Abstract
We consider a von Neumann-Morgensternmarket game and present a simple expression for the Shapley value via decomposition
as the difference of an airport game and an extended airport game. The resulting formula has a useful interpretation for designing
an allocation procedure among the agents.
A Game Theoretical Approach to the Classification Problem in Gene Expression Data Analysis
V. Fragnelli, S. Moretti
Abstract
Microarray technology allows for the evaluation of the level of expression of thousands of genes in a sample of cells
under a given condition. In this paper, we introduce a methodology based on cooperative Game Theory for the selection of
groups of genes with high power in classifying samples, according to gene expression patterns. The connection between
microarray games and classification games is discussed and the use of the Shapley value to measure the power of genes for
classification is motivated on particular instances and compared to the interaction index.
Approximate stable solutions in infinite tree problems
J. Sánchez-Soriano, V. Fragnelli, N. Llorca, S. Tijs
Abstract
In this paper infinite minimum cost spanning tree situations and related TU-games are studied. Since the optimal tree
for these situations does not always exist, it is impossible in such situations to implement core solutions based on a
particular tree. Therefore, we study core-like solutions and deal with three cases concerning the total cost of connection:
when it is zero, when it is finite but larger than zero, and when it is infinite.
Convex games with an infinite number of players and sequencing situations
V. Fragnelli, N. Llorca, J. Sánchez-Soriano, S. Tijs, R.Branzei
Abstract
In this paper we study convex games with an infinite countable set of agents and provide characterizations of this class
of games. To do so, and in order to overcome some shortcomings related to the difficulty of dealing with infinite orderings,
we need to use a continuity property. Infinite sequencing situations where the number of jobs is infinite countable can be
related to convex cooperative TU games. It is shown that some allocations turn out to be extreme points of the core of an
infinite sequencing game.
Strategic Manipulations and Collusions in Knaster Procedure
V. Fragnelli, M.E. Marina
Abstract
The Knaster's procedure is one of the simplest and most powerful mechanisms for allocating indivisible objects among
agents requiring them, but its sealed bid feature may induce some agents in altering their valuations. In this paper we
study the consequences of false declarations on the agents' payoffs. A misrepresentation of a single agent could produce
a gain or a loss. So, we analyze a possible behavior of a subset of infinitely risk-averse agents and propose how to
obtain a safe gain via a joint misreporting of their valuations, regardless of the declarations of the other agents.
A Game Theoretic Approach to Emergency Units Location Problem
V. Fragnelli, S. Gagliardo
Abstract
The location of the emergency units may have a deep influence on the intervention time, which in its turn may be
relevant for a positive solution of an emergency situation. In this paper we analyze a particular location problem with a
discontinuous intervention time function. The problem is tackled from different points of view each one resulting in a
different game. The paper refers to a toy model and to a real world situation of locating some additional ambulance in the
province of Milan.
A Game Theoretic Model for Improving a Railway Timetable
V. Fragnelli, S. Sanguineti
Abstract
The EEC directive 440/91 allows to different transport operators to operate different trains on the same network, so the
infrastructure manager has to produce the timetable, taking into account the requests of different agents in a competitive
situation.
Subsequently, the transport operators may cooperate, in order to modify their scheduling and increase their income.
The game theoretical approach models this situation in which the agents search for their own utility, rather than for a
global maximum, as a coalition formation problem. In particular we refer to the C-Solution proposed by Gerber.
Some examples conclude the paper.
Scegliere nell'incertezza: matematica e comportamenti razionali e irrazionali
V. Fragnelli, L. Tibiletti
Abstract
Nelle situazioni in cui il risultato ottenuto da differenti agenti dipende dalle decisioni prese da tutti i decisori,
si parla di interazione strategica. L’interazione tra i differenti decisori porta alla difficoltà di prevedere con certezza
il risultato che ognuno di essi può ottenere. In queste situazioni si suppone che ogni decisore sia «razionale», nel senso
che le sue scelte si orientano verso quei comportamenti che portano a esiti finali più vantaggiosi per lui, quantificati
tramite una funzione di utilità. In questo capitolo si analizzano alcuni esempi classici della Teoria dei giochi in cui il
comportamento dei decisori risulta apparentemente «irrazionale», cioè non orientato all’esito più favorevole.
Questa apparente irrazionalità è spiegabile, nei casi esposti, tramite una opportuna analisi della funzione di utilità
dei decisori e delle utilità attese, in dipendenza delle decisioni prese dagli altri agenti.
Fixed Benefit Games
V. Fragnelli, M.E. Marina
Abstract
We consider a problem in which a set of agents set up a joint venture, paying a cost and receiving a benefit. In our
situation the cost depends on the agents involved, while the benefit is fixed.
Many well-known economic situations and problems fit this model: we can mention minimum cost connection, production,
bankruptcy and co-insurance.
We want to investigate how the agents may share the benefit, taking into account their charges of the costs, so we
analyze the behavior of some classical solution concepts and properties when the value of the benefit varies.
Sequencing Interval Situations and Related Games
S.Z. Alparslan-Gök, R. Branzei, V. Fragnelli, S. Tijs
Abstract
In this paper we consider one-machine sequencing situations with interval data. We present different possible scenarioes
and extend classical results on well known rules and on sequencing games to the interval setting.
The Propensity to Disruption for Evaluating a Parliament
V. Fragnelli
Abstract
The issue of power plays a relevant role in evaluating the representativeness of a Parliament. In this paper a new
governability index is introduced, taking inspiration from the propensity to disruption and referring to the power of the
parties.
Comportamenti cooperativi per incrementare l'efficienza di un orario ferroviario
V.Fragnelli, S.Sanguineti
Abstract
La stesura di un orario ferroviario costituisce una componente molto importante ai fini dell’efficienza del sistema
ferroviario. Per questo problema sono stati recentemente proposti vari approcci che permettono di risolvere il problema
con strumenti automatici, invece del classico approccio manuale. D’altra parte la complessità del problema e i numerosi
fattori che è necessario prendere in considerazione fanno sì che le soluzioni alle quali si perviene, anche per situazioni
di piccole dimensioni, non siano ottimali. In questo articolo proponiamo un metodo basato sui giochi cooperativi a utilità
non trasferibile, che analizza un sottoinsieme di treni in competizione per l’orario ottimale che potrebbero variare il
loro orario rispetto a quello proposto loro dal gestore dell’infrastruttura, senza influenzare le decisioni prese per gli
altri treni, incrementando l’efficienza. Questo approccio si differenzia dai modelli di ottimizzazione in quanto richiede
lo scambio di ulteriori e più dettagliate informazioni sull’utilità solo all’interno di ristretti gruppi di operatori; nei
modelli di ottimizzazione le informazioni sono invece rese note ad un insieme potenzialmente più ampio. La limitata
dimensione dei gruppi permette di ridurre la complessità propria dei metodi basati sulla teoria dei giochi.
Il ruolo della ricerca operativa nell’organizzazione di un sistema di pronto intervento di soccorso sanitario
R. Aringhieri, R. Berchi, G. Carello, V. Fragnelli, D. Morale, A. Pagliosa, A. Pinciroli, G. Righini, G. Sesana
Abstract
La gestione di un sistema di pronto intervento è un problema estremamente complesso per la sua intrinseca dinamicità.
In questo capitolo mostriamo come l’applicazione integrata di differenti tecniche della Ricerca Operativa, quali
Simulazione, Ottimizzazione e Teoria dei Giochi, possano fornire utili indicazioni al management con l’obiettivo di
migliorare il servizio offerto.
A Flow Approach to Bankruptcy Problems
R. Branzei, G. Ferrari, V. Fragnelli, S. Tijs
Abstract
In this note we represent a classical bankruptcy problem as a standard flow problem on a simple network and implement
some known division rules from the bankruptcy literature via suitable cost functions in the related minimum cost flow
problem.
A new family of power indices for voting games
V. Fragnelli, S. Ottone, R. Sattanino
Abstract
In this paper we introduce a new family of power indices, especially designed for voting games, based on three
parameters. A suitable choice of the parameters allows better taking into account particular features of each real
political situation. We propose an archetype of the family and analyze some possible settings of the parameters.
We make also some comparisons with existing indices.
Two-sided market situations with existing contracts
J. Sánchez-Soriano, V. Fragnelli
Abstract
The main aim of this paper is to study two-sided market situations where there are existing contracts which are
exogenously given. These existing contracts could come from a previous competitive period or from any other circumstances.
In any case, all these existing contracts provide an initial feasible solution for the two-sided market situation, perhaps
non optimal in the sense the agents do not obtain jointly the maximum profit that they could get by cooperation. Therefore,
the agents could be interested in improving their results through cooperation but taking into account the existing bilateral
contracts. Thus, taking as starting point what each agent has got with the existing contracts, they have to distribute
among themselves the extra amount that they could get by cooperation. For this kind of cooperative situation we
propose different models and prove some results about the nonemptiness of the core and its relationship with the Owen set.
An Axiomatic Characterization of the Baker-Thompson Rule
V. Fragnelli, M.E. Marina
Abstract
The airport problem is a widely studied allocation problem, with the aim of providing simple and fair sharing rule for the
landing fees. In this note we introduce some fairness criteria and characterize the classical Baker-Thompson allocation rule.
A Bonus-Malus Approach to Project Management
R. Branzei, G. Ferrari, V. Fragnelli, S. Tijs
Abstract
This paper concentrates on the management of delayed projects charged with penalty costs and of expedited projects rewarded
with bonuses, based on an activity graph description of the projects. We propose a two-stage heuristic procedure to assist project
managers to determine ``fair'' shares of penalties or compensations for agents involved when information regarding the project's
schedule and its actual execution is available. Incentives for better performance play a key role in this procedure, which combines
a ``bonus-malus'' approach with a rationing approach. In the first stage, activities' deviations from the schedule are computed
using heuristic algorithms which implement incentives for better performance according to two alternative scenarios. In the second
stage, the deviations of activities computed according to the chosen scenario are adjusted using well-known rules from the literature
on rationing problems. A new family of compensations-penalties solutions, called Mutual Help Solutions, is introduced and illustrated.
Relocating Ambulances at the End of Rescue Missions
V. Fragnelli, S. Gagliardo
Abstract
The standard approach of managing ambulances is based on the idea that each unit has an assigned location. Consequently, at the end
of a mission the ambulance returns at its place; this approach may be improved allowing to relocate the unit in a more profitable way.
In this case profitability refers to efficiency, i.e. look for satisfying the largest number of expected calls or to cover an area
otherwise with scarce available ambulances. The method proposed by the authors, rooted in a game theoretic approach, allows giving a
fast and efficient answer to the question of identifying one of the best location among the empty ones. The idea is to evaluate the
expected calls, or other parameters like the area that may be covered by a unit according to the assigned location, referring to the
Shapley value. The method could take into account the time required for reaching the candidate locations.
Using coalitional games on biological networks to measure centrality and power of genes
S.Moretti, V.Fragnelli, F.Patrone, S.Bonassi
Abstract
Motivation: The interpretation of gene interaction in biological networks generates the need for a meaningful ranking of network
elements. Classical centrality analysis ranks network elements according to their importance but may fail to reflect the power of each
gene in interaction with the others.
Results: We introduce a new approach using coalitional games to evaluate the centrality of genes in networks keeping into account
genes’ interactions. The Shapley value for coalitional games is used to express the power of each gene in interaction with the others
and to stress the centrality of certain hub genes in the regulation of biological pathways of interest. The main improvement of this
contribution, with respect to previous applications of game theory to gene expression analysis, consists in a finer resolution of the gene
interaction investigated in the model, which is based on pair-wise relationships of genes in the network. In addition, the new approach
allows for the integration of a priori knowledge about genes playing a key function on a certain biological process.
An approximation method for practical computation on large biological networks, together with a comparison with other centrality
measures, is also presented.
On 1-convexity and nucleolus of co-insurance games
T.S.H. Driessen, V. Fragnelli, I.V. Katsev, A.B. Khmelnitskaya
Abstract
The insurance situation in which an enormous risk is insured by a number of insurance companies is modeled through a cooperative
TU game, the so-called co-insurance game, first introduced in Fragnelli and Marina (2004). In this paper we present certain conditions
on the parameters of the model that guarantee the 1-convexity property of co-insurance games which in turn ensures the nonemptiness
of the core and the linearity of the nucleolus as a function of the variable premium. Further we reveal conditions when a co-insurance
game is representable in the form of a veto-removed game and present an efficient final algorithm for computing the nucleolus of a
veto-removed game.
Skill and Chance in Insurance Policies
V. Fragnelli, M.E. Marina
Abstract
In a game theoretical setting it is possible to assign a relative measurement of the skill required to each player for maximizing his
payoff in a casino game; according to this approach we analyze the relevance of skill and chance in an insurance contract, both for the
insurance company and for the customer.
Weighted Bankruptcy Rules and the Museum Pass Problem
B.Casas-Mendez, V.Fragnelli, I.Garcia-Jurado
Abstract
In this paper we introduce and characterize some allocation rules for weighted bankruptcy problems. We illustrate the relevancy
of weighted bankruptcy by applying it to analyse the museum pass problem, introduced by Ginsburgh and Zang (2003). This application
is completed with the analysis of real data for the ‘‘Card Musei’’ of the Municipality of Genova.
Embedding classical indices in the FP family
M.Chessa, V.Fragnelli
Abstract
Recently, a new family of power indices, the FP, was introduced by Fragnelli, Ottone and Sattanino (2009), requiring that
the parties of a majority are ideologically contiguous along a left-right axis. The different indices in this family depend on some
parameters that allow representing various situations.
In this paper we analyze how to select the parameters with the aim of representing classical power indices.
We start by relaxing the hypothesis of contiguity. Then, we reduce the relevance of non-contiguous coalitions, defining a sequence
of indices that converges to a modified version of the classical indices. The method is applied to the Italian lower chamber.
Finally, we extend our approach to situations in which the parties are not necessarily ordered according to the left-right axis,
expressing their relations by a graph, following the idea of Myerson (1977).
A note on ''Measurement of disproportionality in proportional representation systems''
M.Chessa, V.Fragnelli
Abstract
In this paper, we add three further indices to the survey on disproportionality by Karpov. Two of them are rooted in the issue of power,
so we discuss the relevance of it in evaluating the disproportionality of a Parliament w.r.t. the voting body.
Dynamic simulations of kidney exchanges
M.Beccuti, V.Fragnelli, G.Franceschinis, S.Villa
Abstract
In this paper we develop a simulator modeling a kidney exchange program, in which donor-recipient pairs with characteristics drawn from a
distribution based on real data join the system over time, and a centralized authority organizes a suitably chosen set of exchanges among the
pairs in the pool at regular intervals of time, as it happens in the Netherlands or in the US. We compare and discuss the results of numerical
simulations on this model varying the matching policy.
A coordination model for enhancing research on rare diseases
M.Chessa, V.Fragnelli, S.Gagliardo
Abstract
Rare diseases affect a great number of patients that suffer of the non existence of effective cures. Medical products for prevention,
diagnosis or treatment of this kind of disorders are called orphan drugs and pharmaceutical industries have not a great interest under
normal market conditions in developing and marketing products for a small number of patients. The Orphan Drug Act and the Regulation on
Orphan Medicinal Products played a relevant role in encouraging the development of new orphan drugs, as in America as in Europe.
A quantitative evaluation of veto power
M.Chessa, V.Fragnelli
Abstract
In this paper we introduce the decisiveness index and the loose protectionism index for a single player, starting form the decisiveness
and the loose protectionism indices for a collective decision-making mechanism defined by Carreras. The attention is mainly focused on the
second one, which is proposed as a quantitative measure of the power of veto of each agent. According to this index, a veto player has veto
power equal to one, while each other player has a fraction according to her/his possibility to block a given proposal. Such an index coincides
with the expected payoff at the Bayesian equilibrium of a suitable Bayesian game, which catch the non-cooperative point of view of a
decision-making mechanism.
Open Problems in Veto Theory
M.Chessa, V.Fragnelli
Abstract
The issue of veto may play an important role in an approval situation, mainly in political science, where several scholars dealt
with this topic. In this survey we want to update the state-of-the-art, paying particular attention to the open problems that various
authors pointed out in their research fields.
Some non standard features of bargaining problems
A.Agnetis, V.Fragnelli
Abstract
In this paper we present two real-world situations in which the standard hypotheses of a bargaining problem do not hold, and discuss
how to tackle these situations.
Open Problems in Cooperative Location Games
V.Fragnelli, S.Gagliardo
Abstract
Location problems describe those situations in which one or more facilities have to be placed in a region trying to optimize a
suitable objective function. Game theory has been used as a tool to solve location problems and this paper is devoted to describe
the state-of-the-art of the research on location problems through the tools of game theory. Particular attention is given to the problems
that are still open in the field of cooperative location game theory.
Cooperative Models for Allocating an Object
V.Fragnelli, S.Gagliardo
Abstract
This paper starts from a classical fair division situation of allocating an object among a set of agents. The problem is studied
from both a cooperative and a bankruptcy point of view, analyzing the fairness properties of the proposed solutions.
A game theoretic approach to co-insurance situations
T.S.H. Driessen, V. Fragnelli, I.V. Katsev, A.B. Khmelnitskaya
Abstract
The situation, in which an enormous risk is insured by a number of insurance companies, is modeled through a cooperative TU game, the
socalled co-insurance game, first introduced in Fragnelli and Marina (2004).
In this paper we show that a co-insurance game possesses several interesting properties that allow to study the nonemptiness and the
structure of the core and to construct an efficient algorithm for computing the nucleolus.
A Note on Communication Structures
V. Fragnelli
Abstract
Several power indices were introduced in order to account for different
aspects of decisional situations. In this note we analyze how to deal with those situations, commonly arising in politics, in which the agents
have some incompatibilities. We present some comments on existing power indices and discuss how communication structures and restricted games
may allow a better evaluation of the power of the parties when incompatibilities play a relevant role. Also the question of the probability of
a coalition to form is discussed.
Dynamic Collusion and Collusion Games in Knaster's Procedure
F.Briata, M.Dall'Aglio, V.Fragnelli
Abstract
In this paper we study the collusion in Knaster's procedure, starting from the paper of Fragnelli
and Marina (2009). First, we introduce a suitable dynamic mechanism, so that the coalition enlargement is always
non-disadvantageous. Then, we define a new class of TU-games in order to evaluate the collusion power of the agents.
How to Divide the Costs of Urban Solid Wastes Collection among Citizens?
V.Fragnelli
Abstract
In this paper we deal with a cost allocation problem arising in a consortium for urban solid wastes collection and disposal.
In particular, we consider the question of allocating the costs directly to the citizens in a fair way. The approach proposed
is based on a game theoretic model that is applied to data from the consortium Ovadese - Valle Scrivia.
A Survey of Allocation Rules for the Museum Pass Problem
B.Casas-Mendez, V.Fragnelli, I.Garcia-Jurado
Abstract
In this paper we consider the problem, introduced by Ginsburgh and Zang (2003), of sharing the income from the sell of passes
that allow the entrance in a set of museums. First we recall some allocation rules and some properties presented in Ginsburgh and
Zang (2004), Beal and Solal (2010), Estevez-Fernandez et al. (2010) and Casas-Mendez et al. (2011). Then we discuss them, finding
the properties satisfied by each allocation rule. The analysis of a real-world example concludes the paper.
The Bargaining Set for Sharing the Power
M.Chessa, V.Fragnelli
Abstract
The evaluation of the power of the parties of a Parliament is usually carried out following a static approach, counting their
numbers of seats and possible ideological relations among them. In this paper we propose a dynamic model in which parties may
blackmail each other in order to increase their power at the expense of others. This model may be solved in terms of the Bargaining
Set (Aumann and Maschler, 1964), a set valued solution, in contrast to the classical power indices that are point valued; so it may
be used to check the robustness of a power division taking into account possible blackmailing activities. The paper is mainly based
on the idea of proposing an existing instrument, the Bargaining Set, as power index to analyze this blackmailing situation.
The computational complexity limits the possibility of applying it to real-world situations, but the possibility of making the
computation easier is shown using some examples.
Introduction to Special Issue on Applications of Cooperative Games, vol. I
V.Fragnelli, G.Gambarelli
Introduction
Many studies have been carried out on the applications of Cooperative Games and on the related generalizations to more theoretical
topics. The results have been published in the most diverse range of scientific journals: from Game Theory to Finance, Logistics,
Medicine, Politics and so on. Consequently, it may be difficult for scholars interested in a general framework on these studies to
find information, looking at different publishers' sites.
The aim
The work collects some surveys on recent results in different fields, in order to have a unified view of the state-of-the-art and
of some open problems. At the beginning we had in mind a single issue, but due to the large number of contributions and to the detailed
analysis of the topics carried out by the authors, it was necessary to divide the material into two issues, the former more
theory-oriented, the latter more application-oriented.
We are conscious that the issues are not exhaustive referring both to the possible fields of application of Cooperative Games and
to the problems considered in each of them, due also to a maximum number of pages for each contribution. However, we hope that our work
will be profitable for the scholars.
The structure
This first issue includes contributions with a theoretical flavor, even if strongly related to concrete applications to real-world
situations. The first three contributions survey cost sharing and related open problems. The first, by Herve Moulin, analyses network
situations; the author argues that the recent axiomatic and singlevalued viewpoint has a strong potential for future developments and
enriches the paper with a large list of references and open problems. The second paper, by Julian Costa and Ignacio Garcia-Jurado,
deals with coalitional values, referring to the class of airport games with coalition structures. The third paper, authored by Christian
Trudeau, presents Kar and Folk solutions and some characterizations, with the aid of some equivalencies between sets of properties.
The three following papers deal with power indices. The first one, by Cesarino Bertini, Josep Freixas, Gianfranco Gambarelli and
Izabella Stach, consists in a comparative analysis of several power indices more or less commonly used, starting from their properties,
in order to suggest the most suitable for the various situations. The second one, by the same authors, analyses some open problems in
simple games, mainly weighted games and power indices. In the third one Michela Chessa and Vito Fragnelli present some questions under
investigation in Veto Theory, with a particular attention to the indices in a quantitative approach.
The following three contributions are surveys on different topics. Some nonstandard features of bargaining situations are presented
by Alessandro Agnetis and Vito Fragnelli. It refers to two real-world situations, namely job scheduling and train timetable, where the
hypothesis of convexity of the feasible region does not hold. Then, there is a multidisciplinary survey on matching by Peter Biro and
Flip Klijn, referring to agents that operate in a job market and illustrating the related open problems. A rich analysis of the
literature on cooperative games with incomplete information is done in the paper by Francoise Forges and Roberto Serrano; they discuss
and point out open problems in exchange economies, cooperative Bayesian games with orthogonal coalitions, and issues of cooperation in
noncooperative Bayesian games.
The issue concludes with a short list of the works on Cooperative Game Theory currently "on the table" of Guillermo Owen, with some
notes on the related open problems: relations between games and graphs, voting situations and in particular multi-stage voting, nonquite
nonatomic games and the issue of licensing a technology in an oligopoly.
Acknowledgments
These issues are sponsored by PRIN of the "Ministero dell'Istruzione, dell'Università e della Ricerca" (MIUR - Education, University
and Research Ministry). We want to thank all the authors for their important contributions and all the reviewers for their valuable work.
The list of reviewers includes: Encarnacion Algaba, Jose Maria Alonso-Meijide, Gustavo Bergantinos, Francesc Carreras, Michela Chessa,
Claude D'Aspremont, Marco Dall'Aglio, Edith Elkind, Stefano Gagliardo, Nicola Gnocchi, Marcin Malawski, Lina Mallozzi, Marco Mariotti,
Jacek Mercik, Elisenda Molina, Stefano Moretti, Herve Moulin, Akira Okada, Fioravante Patrone, Justo Puerto, Arkadii Slinko, Juan
Vidal-Puga and Rajiv Vohra. We want to thank Nicola Gnocchi for his technical support in the editing phases. We want to say special
thanks to all those people who helped us with useful suggestions, mainly Robert Aumann and Guillermo Owen.
Vito Fragnelli and Gianfranco Gambarelli
Guest Editors
Introduction to Special Issue on Applications of Cooperative Games, vol. II
V.Fragnelli, G.Gambarelli
Introduction
This second issue concludes the survey on open problems in the applications of Cooperative Games and on their generalizations to
more theoretical topics. The motivation was to provide the scholars an updated view of the state-of-the-art collecting recent results
in various fields: from Finance to Logistics, Medicine, Politics and so on.
The aim
In the first issue we presented some theory-oriented topics, and in this second one, we collect the application-oriented contributions.
We are conscious that the issues are not exhaustive referring both to the possible fields of application of Cooperative Games and
to the problems considered in each of them, due also to a maximum number of pages for each contribution. However, we hope that our work
will be profitable for the scholars.
The structure
Referring to the classical beginnings of Game Theory, the issue starts with the Economic applications. Guillermo Owen gives an
overview emphasizing the cooperative ones, especially on the relation between the core and the Shapley value, when the number of
players increases without bound.
Then, there are three papers on voting games. The first, written by Matthieu Martin and Maurice Salles, concentrates on the
feature of social aggregation functions. In the second, Manfred Holler and Hannu Nurmi deal with power sharing in Politics and discuss
the modeling via power indices. The third political contribution, authored by Gabrielle Demange, concerns the allocation of seats to
parties and districts. In particular, the main focus of the paper is to discuss fairness and proportionality axioms as well as their
implementation.
Going from allocation to location, the work by Vito Fragnelli and Stefano Gagliardo presents some open problems in optimizing the
location of some facilities according to the minimization of some cost, damage or discomfort and/or the maximization of some profit,
quality or wellbeing.
The next contribution is a survey on application of Cooperative Games to river sharing problems, authored by Sylvain Beal, Amandine
Ghintran, Eric Remila and Philippe Solal. The topic is tackled from different points of view: fair division, water market approach, and
several generalizations of the standard river TU-game.
The issue goes on with two papers dealing with finance. The first, by Yves Crama and Luc Leruth, presents control measures in
Corporate Structures; it shows as some techniques, in particular Power Indices, are more suitable than cut-off methods for describing
the sharing of power among shareholders. The second, by William Thomson, presents recent advances in the game-theoretic analysis of
Bankruptcy and Taxation problems; more specifically, the author deals with the division of an outstanding debt among debtor and creditor.
An overview on applications of Game Theory to Engineering is presented by Joaquin Sanchez-Soriano. The author presents several
applications: from civil to industrial, electrical and electronic engineering, with particular attention to communications networks.
Stefano Moretti surveys applications of coalitional games to Medicine; more precisely, on how to use the Shapley value and the
driven approach property to justify the application of a solution as an appropriate measure of certain biological attributes; several
open problems are presented and discussed.
The issue concludes with a short, but interesting paper by Monica del Pozo, Enrique Gonzales-Aranguena and Conrado Manuel on
applications of cooperative games in Sports. The authors remark that these topics usually require, by their nature, competitive models,
but sometimes cooperative models may also result very useful, for instance status games, team games and multi-choice games.
Acknowledgments
These issues are sponsored by PRIN of the "Ministero dell'Istruzione, dell'Università e della Ricerca" (MIUR - Education, University
and Research Ministry). We want to thank all the authors for their important contributions and all the reviewers for their valuable work.
The list of reviewers includes: Dario Bauso, Steven Brams, Josep Freixas, Nicola Gnocchi, Carmen Herrero, Manfred Holler, Steffen
Jorgensen, Anna Khmelnitskaya, Roberto Lucchetti, Hans Peters, Federica Ricca, Maria Rua, Agnieszka Rusinowska, Joaquin Sanchez-Sanchez,
Ernesto Savaglio, Stefano Secci, Angelo Uristani, Rene van der Brink, Silvia Villa, Stefano Vannucci, Antonio Villar and Georges Zaccour.
We want to thank Nicola Gnocchi for his technical support in the editing phases. We want to say special thanks to all those people who helped
us with useful suggestions, mainly Robert Aumann and Guillermo Owen.
Vito Fragnelli and Gianfranco Gambarelli
Guest Editors
Integer solutions to bankruptcy problems with non-integer claims
V.Fragnelli, S.Gagliardo, F.Gastaldi
Abstract
In this paper, we consider a bankruptcy problem with the additional constraint that the estate has to be assigned in integer unities;
differently from the approaches by other authors, we allow for non-integer claims. This situation poses new questions on the existence
and the uniqueness of the solution. We propose a new solution method that leads to the ‘‘box solution’’, for which uniqueness may be
guaranteed introducing a ranking on the claimants. Some examples complete the paper.
Measuring the relevance of factors in the occurrences of events
V.Fragnelli, J.Freixas, M.Pons, L.Sanmiquel
Abstract
A new way to compare the relevance of the different factors intervening in the occurrences of an event is presented and developed
in this paper. The idea behind the method comes from cooperative game theory but the focus is slightly different because factors are
not necessarily rational decision-makers and because the only data available are obtained by repetition of the event. The concept of
relevance measure for a factor in a set of data is introduced, some significant examples are given and the main properties of relevance
measures are defined and studied. One of these measures, the fair measure, is proved to have interesting properties which characterize
it. Two real world situations, one about traffic accidents and the other one about mining accidents, both of them with real data, are
used to show the use of relevance measures to compare factors in each one of these events.
Further Open Problems in Cooperative Games
V.Fragnelli, G.Gambarelli
Abstract
In 2013, the International Game Theory Review published two special issues on open problems in cooperative games: the first
regarding theory (Fragnelli and Gambarelli, 2013a) and the second applications (Fragnelli and Gambarelli, 2013b). In this paper, our
aim is to present some problems currently "on our table" that were not included in the two issues mentioned above, either because
the topics were too specific or they arose after publication.
The problems are divided into theoretical problems, general models that may be applied to different fields and applicative problems.
A game theoretic model for re-optimizing a railway timetable
V.Fragnelli, S.Sanguineti
Abstract
The Setting. In the Nineties of the last century the European Commission decided to open the railway market to competition,
allowing different railway companies to operate on the same network. Under this framework InfrastructureManagers have to
allocate capacity in order to define the timetable, dealing with possible slot conflicts between competing Transport Operators.
The Problem. An efficient train scheduling requires collecting a lot of information from the Transport Operators, but it may
not be in their interests to reveal their private information. Therefore, it may be useful for real-world applications to
design methods that provide incentives to Transport Operators for cooperating with the aim of increasing their utility; moreover,
this may result in an improvement of the efficiency even for the Infrastructure Managers, so they also have incentives
for favouring the cooperation.
The Proposal. In this paper we propose a game theoretical model in which the agents (Transport Operators) exchange
information on their needs and are compensated by a possible increasing of their utility. This approach represents the situation
as a coalition formation problem. In particular, we refer to the C-Solution proposed by Gerber (Rev Econ Design 5:149–
175, 1), which is applied to some examples, each with different features. This model requires that information is revealed
to a small number of competitors. This is rather important in a market currently still characterized by operator reluctance to
an indiscriminate diffusion of information. Furthermore, the low dimension of the problem allows having a low computational complexity.
Operations Research and Decisions - Special Issues dedicated to SING 10
V.Fragnelli, I.Stach
Editorial
This special issue of the Operations Research and Decisions is dedicated to the Spain-Italy-Netherlands Meeting on Game Theory
SING 10, an international meeting that started as a reference point for game theorists mainly from Spain, Italy and the Netherlands,
but now includes scholars from all over the world that each year congregate in a European city.
In 2014, the meeting was held in Cracow (Poland) and was successfully chaired by Izabella Stach, with outstanding invited speakers,
Gianfranco Gambarelli, Gerard van der Laan, Andrzej Nowak and Ariel Rubinstein, contributions of high scientific quality, and pleasant
and interesting social events, a tour of the old town and visit to Wieliczka Salt Mine. This is a good moment to thank the organizing
and the scientific committees.
Some of the 139 presentations, 135 in parallel sessions and 4 in plenary sessions, are collected in this issue. We hope that they
offer a good, even if restricted, idea of the aims and scope of the SING meetings.
The first paper, by Cesarino Bertini, Jerzy Duda, Bartlomiej Gawel, Andrzej Paliñski, Iwona Skalna and Izabella Stach provides
some interesting statistics about the Spain-Italy-Netherlands Meetings on Game Theory over the years 2005–2014, with special attention
paid to the last one, held in Cracow. They take into account the number of accepted papers, their topics, the number of participants,
dividing them according to country.
Imma Curiel analyzes the electoral system of Suriname, with particular attention paid to the discrepancies in the representation
of various districts. Several apportionment methods have been explored and compared. It is concluded that, in general, the method of
equal proportions provides good performance.
The paper by Vito Fragnelli and Gianfranco Gambarelli, based on the plenary talk by Gianfranco Gambarelli, offers a survey of some
open problems in cooperative games that the authors have pointed out in some recent papers, including theoretical, modelling and
practical problems.
Hannu Nurmi considers the possibility of building a theory of social choice based on individual preference tournaments, when
preferences may be intransitive, incomplete and discontinuous, referring to rational behaviour. A new interpretation of Slater’s rule
has been presented.
Honorata Sosnowska applies the Banzhaf value to evaluating the power of countries in the voting system with rotation which is
planned to be used in the European Central Bank in conjunction with the accession of new members to the economic and monetary union.
The results have been compared with the Shapley value.
We would like to thank all the authors for their important contributions and all the reviewers for their valuable work. Special
thanks have to be given to Jacek Mercik for his constant presence “in the background” and useful suggestions.
Vito Fragnelli and Izabella Stach
Guest Editors
Bankruptcy problems with non-integer claims: definition and characterizations of the ICEA Solution
V.Fragnelli, S.Gagliardo, F.Gastaldi
Abstract
In Fragnelli et al. (2014), we considered a bankruptcy problem with the additional constraint that the estate has to be assigned
in integer unities, allowing for non-integer claims. We dealt with the question of existence and uniqueness of a solution and proposed
the “box method” that is strongly oriented towards the constrained equal losses solution; uniqueness may be guaranteed by introducing
a ranking on the claimants. Here, we introduce a solution oriented towards the constrained equal awards solution and give three
characterizations and a simple method for determining the solution.
Robustness of Legislative Procedures of the Italian Parliament
C. De Michelis, V.Fragnelli
Abstract
The Italian Constitution allows different procedures for approving the laws. In this paper we analyze their ''strength'' correlating
their higher or lower use with the ''strength'' of the government and of the Parliament, measured through two parameters, the governability
and the fragmentation.
Fibonacci representations of homogeneous weighted majority games
V.Fragnelli, G.Gambarelli, N. Gnocchi, F. Pressacco, L.Ziani
Abstract
Isbell (1956) introduced a class of homogeneous weighted majority games based on the Fibonacci sequence. In our paper, we generalize
this approach to other homogeneous representations of weighted majority games in a suitable Fibonacci framework. We provide some
properties of such representations.
Remarks on the Integer Talmud Solution for Integer Bankruptcy Problems
V.Fragnelli, F.Gastaldi
Abstract
In Fragnelli et al. (2014 and 2016), we considered a bankruptcy problem with the additional constraint that the estate has to be
assigned in integer unities, allowing for non-integer claims; we dealt with the extension to our setting of the constrained equal losses
solution and of the constrained equal awards solution. Here, we analyse the possibilities of extending the Talmud solution to the
integer situation, starting from the existing approaches for the non-integer case; some of these approaches are compatible with the
non-integer claims, but in order to comply with as much as possible of the approaches it is necessary to switch to integer claims.
Orders of Criticality in Voting Games
M.Dall’Aglio, V.Fragnelli, S.Moretti
Abstract
In this paper we focus on the problem of investigating the blackmail power of players in simple games, which is the possibility
of players of threatening coalitions to cause them loss using arguments that are (apparently) unjustified. To this purpose, we extend
the classical notion of criticality of players in order to characterize situations where players may gain more power over the members
of a coalition thanks to the collusion with other players.
A Game Theoretic Approach to an Emergency Units Location Problem
V.Fragnelli, S:Gagliardo, F.Gastaldi
Abstract
In this paper we consider the problem of locating emergency units in a given area, defining a suitable class of TU-games. The
Shapley value results to be a very good solution for this class of games. A simple formula for computing the Shapley value is derived.
A real-world example and some comments conclude.
Free-riding in Common Facility Sharing
F.Briata, V.Fragnelli
Abstract
We deal with the free-riding situations that may arise from sharing maintenance cost of a facility among its potential users.
The non-users may ask for a check to assess who the users are, but they have to pay the related cost; consequently, a non-user
may not ask for the check, with the hope that the other non-users ask and pay for it.
In this paper, we provide incentives for asking for the check, without suffering a higher cost.
The Shapley Value in the Knaster Gain Game
F.Briata, A.Dall'Aglio, M.Dall'Aglio, V.Fragnelli
Abstract
In Briata, Dall'Aglio and Fragnelli (2012), the authors introduce a cooperative game with transferable utility for
allocating the gain of a collusion among completely risk-averse agents involved in the fair division procedure introduced
by Knaster (1946). In this paper we analyze the Shapley value (Shapley, 1953) of the game and propose its use as a measure
of the players' attitude towards collusion. Furthermore, we relate the sign of the Shapley value with the ranking
order of the players' evaluation, and show that some players in a given ranking will always deter collusion. Finally, we
characterize the coalitions that maximize the gain from collusion, and suggest an ad-hoc coalition formation mechanism.
Robustness of the Government and the Parliament, and Legislative Procedures in Europe
C. De Michelis, V.Fragnelli
Abstract
In a previous paper (see [3]), we analyzed the procedures of the Italian Constitution, focussing on their strength
correlating it with the strength of the government and of the Parliament, measured through two parameters, the governability
and the fragmentation. Here, we extend the analysis to other European democracies: United Kingdom, France, and Spain.
Modeling the rational behavior of individuals on an e-commerce system
R. Aringhieri, D. Duma, V. Fragnelli
Abstract
With the increasing popularity of e-commerce systems, commercial transactions are becoming more and more frequent. Such
transactions are not direct but mediated, putting the buyer in a position of weakness with respect to the seller, especially
in the case of a failure of a transaction. The literature showed that the reputation can play an important role to reduce
the risks of the buyer in the current e-commerce environment. An online reputation management system (RMS) maintains the reputation,
made of beliefs and/or opinions, that are generally held about someone or something, and it can guarantee the reliability of the
transactions that take place in an e-commerce system. Despite of the fact that the basic element of a RMS – the interaction between
the seller and the buyer – is a classical field of application of the Game Theory (GT) methodologies, the use of a GT approach in
this context seems quite limited and this is probably due to its solution complexity. A way to deal with such a complexity is by
exploiting the capability of the agent based simulation (ABS) approach.
In this paper, we propose a hybrid GT and ABS model for the analysis of an e-commerce system in which a centralized reputation
system is maintained by a trusted third party. We report an extensive quantitative analysis in order to validate the proposed model,
and to evaluate the impact of a set of buyers’ and sellers’ policies on the behavior of the e-commerce system.
Rationing methods for allocating the European Union’s rural development funds in Poland
V. Fragnelli, E. Kiryluk-Dryjska
Abstract
In this paper, we evaluate the applicability of the bankruptcy and the relevance factors methods to the allocation of structural
policy budgets using Polish Rural Development Program as a practical example. Our results demonstrate that the main problem with the
bankruptcy approach used for policy budget allocation is that project claims are not directly related to project importance. Highly
significant programs with small claims are potentially penalized by the proportional solution or by the Constrained Equal Losses
solution, while projects of low importance and small claims may be fully funded using the Constrained Equal Awards solution.
The relevance approach, on the other hand, is highly dependent on the measure computed using expert opinions. This measure is not
influenced by claims. Thus, given reliable expert assessments, the relevance factors method appears advantageous to the bankruptcy
approach. This method is also far superior to the less formal methods currently used by decision-makers.
Horizontal cooperation in a multimodal public transport system: the profit allocation problem
E. Algaba, V. Fragnelli, N. Llorca, J. Sánchez-Soriano
Abstract
We analyse the situation involving several transport companies in an intermodal public transport system. It is assumed that they
cooperate by offering travel cards which can be used on all available means of transport. In order to solve the problem of profit
allocation among the companies involved, we first introduce a coloured graph which describes the transport network and then propose
a game theoreti- cal approach to share the profit among the companies. Two new allocation rules, called the Coloured Egalitarian
Solution and the Coloured Cost Proportional Solution, are introduced and axiomatically char- acterised. Furthermore, it is shown
that both solutions provide stable allocations in the sense that they cannot be improved upon by any coalition of players.
Indices of criticality in simple games
M.Dall'Aglio, V.Fragnelli, S.Moretti
Abstract
We generalize the notion of power index for simple games to different orders of criticality, where the order of criticality
represents the possibility for players to gain more power over the members of a coalition thanks to the collusion with other players.
We study the behaviour of these criticality indices to compare the power of different players within a single voting situation, and
that of the same player with varying weight across different voting situations. In both cases we establish monotonicity results in
line with those of Turnovec (1998). Finally, we examine which properties characterizing the indices of Shapley-Shubik and Banzhaf
are shared by these new indices.