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.