# The Traveling Salesman Game for Cost Allocation: The Case Study of the Bus Service in Castellanza

Authors: Nicola Besozzi; Luca Ruschetti; Chiara Rossignoli; Fernanda Strozzi
Journal: Game Theory
 (2014)

---

## Abstract

This paper studies cost allocation for the bus transportation service in Castellanza, a small town (14,000 inhabitants ca.) close to Varese, Italy. Carlo Cattaneo University (LIUC) is one of the
promoters and funders of this service, together with the City Council and other private agents. The case study is first analysed as a traveling salesman problem (TSP) to find the optimal route. Then the traveling salesman game (TSG) is introduced, where the bus stops are associated with the players of a cooperative game, thus allowing the study of possible allocations of the total cost among them. The optimal route is found by the Branch and Bound algorithm. The Shapley vector and the separable and nonseparable cost are the methods used to allocate the cost of the optimal route among players.


---

## Body

## 1. Introduction

The creation of “public-private partnerships” (PPP) is a growing trend in modern economies as they strive to achieve at least a partial privatisation of public services. In such partnerships the agents involved have to find a way to split the cost of the service. In the town of Castellanza a PPP was created to provide a bus service connecting the main points of interest. The objective of this paper is to explore and compare alternative criteria for allocating the cost of this service.Castellanza is close to the city of Varese, Italy, to the northwest of Milan not far from Malpensa Airport. This small town hosts Carlo Cattaneo University (LIUC) (from here on LIUC) and two private hospitals, plus some public schools.In 2010, the railway station was relocated from the centre to the outskirts of the town. Initially the railway company Trenord provided a bus service between the old station and the new station, and then the City Council took charge with the contribution of some private agents, such as LIUC, some supermarkets, and the private hospitals, which led to the addition of several stops. Some minor changes to the itinerary introduced after August 2013 have not been considered here.In this paper, the bus service is treated as a traveling salesman problem (TSP). The solution of a TSP is a Hamiltonian cycle connecting all the nodes to the origin with minimum cost. Subsequently, a cooperative game is applied to the network by associating the nodes with a set of players (except for the origin, a public node), thus generating a traveling salesman game (TSG) [1]. Game theoretic concepts can then be applied to the allocation of the minimized cost. This allocation, the so-called solution of the game, can follow different criteria.The Shapley vector assigns to each player the average of its marginal contributions to each coalition it is part of [2]; this value is unique and gives a fair allocation. It is calculated using an algorithm developed by Burg [3]. The methods based on separable and nonseparable costs were first introduced in the Tennessee Valley Authority Act [4] and referred to in Tijs and Driessen [5], the concept being first to allocate to the players their separable cost and then to distribute the nonseparable costs amongst them according to specified weights.The alternative solutions are tested for their stability as defined by their belonging to the core. Gillies [6] introduced the concept of the core of a cooperative game, an allocation that no coalition can block. This concept was further developed by Shapley and Shubik [7].Section2 presents the case study as a TSP and gives the optimal route. Section 3 defines the associated TSG. The cost allocation methods are introduced and applied in Section 4. Final comments on the results are given in Section 5.


## 2. The Bus Service in Castellanza as a TSP and the Optimal Route

The following simplifying hypotheses are assumed: (a) variations to the route throughout the day are ignored giving a unique route that touches all the stops; (b) the total cost is simply given by the distance travelled.The map in Figure1, created with the service walkJogRun, shows the twelve stops and the bus route. Each of the bus stops is visited exactly once and the tour ends when the bus returns to the origin, or node A, which is the new station. The total length of the path is 14,370 metres.Figure 1
The bus route.The nodes associated with the bus stops are listed in Table1.Table 1
List of the nodes associated with the bus stops.
Node
Address
A
Via Kennedy
B
Via Luigi Pomini 25
C
Via Vittorio Veneto 25
D
Via Matteotti 24
E
Via Mulini 24
F
Via Lombardia 57
G
Via Tevere 11
H
Via Nazario Sauro 11
I
Via Piemonte 7
J
Via Azimonti 15
K
Viale Borri 33
L
Piazza XXV AprileTable2 gives the matrix of the distances between each pair of nodes in meters.Table 2
Distance matrix (meters).
A
B
C
D
E
F
G
H
I
J
K
L
A
0
1,500
1,800
2,440
2,900
3,080
2,540
2,680
1,390
1,690
900
1,760
B
1,500
0
700
970
1,510
1,640
1,140
1,230
2,210
2,500
1,720
190
C
1,800
700
0
410
880
1,160
1,410
740
2,350
2,580
1,860
590
D
2,440
970
410
0
910
1,400
1,380
710
2,840
2,800
2,340
780
E
2,900
1,510
880
910
0
580
1,050
1,010
3,120
2,780
2,770
1,310
F
3,080
1,640
1,160
1,400
580
0
660
1,700
3,530
3,470
3,040
1,450
G
2,540
1,140
1,410
1,380
1,050
660
0
1,870
3,350
3,640
2,860
950
H
2,680
1,230
740
710
1,010
1,700
1,870
0
2,330
1,980
1,180
1,180
I
1,390
2,210
2,350
2,840
3,120
3,530
3,350
2,330
0
1,100
550
2,380
J
1,690
2,500
2,580
2,800
2,780
3,470
3,640
1,980
1,100
0
540
2,440
K
900
1,720
1,860
2,340
2,770
3,040
2,860
1,180
550
540
0
2,010
L
1,760
190
590
780
1,310
1,450
950
1,180
2,380
2,440
2,010
0The TSP is solved with the Branch and Bound method (B&B) [8] giving a 10,090-meter cycle. The sequence of nodes in the optimal solution is given by ABLGFECDHKJIA (Figure 2).Figure 2
The optimal route with B&B.The difference with the actual path is mainly due to the fact that the bus visits the old station twice, first on its way out (node B) and then on its way back (node L), whilst in the optimal path the two nodes are visited consecutively and may actually be merged.


## 3. The Associated TSG with Three and Four Players

In general, a cooperativen-person cost game with transferable utility is given by a finite set of players N={1,2,…,n} and a characteristic function v associating a cost v(S) with all the subsets S of N, that is, with all the coalitions among players. It is normally assumed that v(Ø)=0. The set of all players N is called the grand coalition. We will consider two different scenarios, with three and four players.


### 3.1. Three Players

Table3 shows the association of the stops with the players in a three-player scenario.Table 3
Association of stops with players in the three-player scenario.
Player
Node
Address
Point of interest
(Public)
A
Via Kennedy
New station
LIUC
D
Via Matteotti 24
LIUC
City Council
B
Via Luigi Pomini 25
Old station
C
Via Vittorio Veneto 25
Town hall
F
Via Lombardia 57
General
G
Via Tevere 11
General
L
Piazza XXV Aprile
Old station
Association
E
Via Mulini 24
Mater Domini  Clinic
H
Via Nazario Sauro 11
Gigante Supermarket
I
Via Piemonte 7
Multimedica Clinic
J
Via Azimonti 15
ISI Secondary School
K
Viale Borri 33
Esselunga SupermarketThe three players are the City Council, LIUC, and an association of private companies and schools. This division gives particular consideration to the City Council as being responsible for the provision of a public transport service and to LIUC as the promoter and funder of a shuttle service from the station to the campus. The association is formed by agents (e.g., supermarkets, public schools, and clinics) that also have an interest in the service.To define the game, it is necessary to solve the TSP for every coalition, that is, for the subnetwork including only the nodes belonging to that coalition, besides the origin. The minimum route associated with every coalition and the corresponding cost are shown in Table4.Table 4
Three-player scenario: coalitionsS and corresponding cost v(S).
S
v
(
S
)
Route
1 (LIUC)
4,880
ADA
2 (City Council)
6,260
ABLGFCA
3 (Association)
8,120
AEHKJIA
1, 2
6,910
ABLGFDCA
1, 3
8,170
ADEHKJIA
2, 3
9,710
ABLGFECHKJIA
1, 2, 3
10,090
ABLGFECDHKJIA


### 3.2. Four Players

Table5 gives the list of players and their stops in the four-player scenario.Table 5
Association of stops and players in the four-player scenario.
Player
Node
Address
Point of interest
(Public)
A
Via Kennedy
New station
LIUC
D
Via Matteotti 24
LIUC
City Council
C
Via Vittorio Veneto 25
Town hall
E
Via Mulini 24
Mater Domini Clinic
F
Via Lombardia 57
General
G
Via Tevere 11
General
J
Via Azimonti 15
ISI Secondary School
Association
H
Via Nazario Sauro 11
Gigante Supermarket
I
Via Piemonte 7
Multimedica Clinic
K
Viale Borri 33
Esselunga Supermarket
Trenord
B
Via Luigi Pomini 25
Old station
L
Piazza XXV Aprile
Old stationThe new partition is based on a slightly different approach. A fourth player, the railway company Trenord, is introduced and is paying for the two stops connecting the old station to the new one (nodes B and L). The secondary school ISI (node J) is given to the City Council, so that the association is now made of purely private agents. The clinic Mater Domini (node E) is also imputed to the City Council, due to its proximity to the other stops already owned by this player.Table6 shows the characteristic function in the case of four players.Table 6
Four-player scenario: coalitionsS and corresponding cost v(S).
S
v
(
S
)
Route
1 (LIUC)
4,880
ADA
2 (City Council)
8,920
ACGFEJA
3 (Association)
5,800
AIHKA
4 (Trenord)
3,450
ABLA
1, 2
9,300
ACDGFEJA
1, 3
6,270
ADHKIA
1, 4
4,910
ABLDA
2, 3
9,610
AGFECHKJIA
2, 4
9,030
ABLGFECJA
3, 4
5,990
ABLHKIA
1, 2, 3
9,990
AGFECDHKJIA
1, 2, 4
9,470
ABLGFEDCJA
1, 3, 4
6,300
ABLDHKIA
2, 3, 4
9,710
ABLGFECHKJIA
1, 2, 3, 4
10,090
ABLGFECDHKJIA


## 3.1. Three Players

Table3 shows the association of the stops with the players in a three-player scenario.Table 3
Association of stops with players in the three-player scenario.
Player
Node
Address
Point of interest
(Public)
A
Via Kennedy
New station
LIUC
D
Via Matteotti 24
LIUC
City Council
B
Via Luigi Pomini 25
Old station
C
Via Vittorio Veneto 25
Town hall
F
Via Lombardia 57
General
G
Via Tevere 11
General
L
Piazza XXV Aprile
Old station
Association
E
Via Mulini 24
Mater Domini  Clinic
H
Via Nazario Sauro 11
Gigante Supermarket
I
Via Piemonte 7
Multimedica Clinic
J
Via Azimonti 15
ISI Secondary School
K
Viale Borri 33
Esselunga SupermarketThe three players are the City Council, LIUC, and an association of private companies and schools. This division gives particular consideration to the City Council as being responsible for the provision of a public transport service and to LIUC as the promoter and funder of a shuttle service from the station to the campus. The association is formed by agents (e.g., supermarkets, public schools, and clinics) that also have an interest in the service.To define the game, it is necessary to solve the TSP for every coalition, that is, for the subnetwork including only the nodes belonging to that coalition, besides the origin. The minimum route associated with every coalition and the corresponding cost are shown in Table4.Table 4
Three-player scenario: coalitionsS and corresponding cost v(S).
S
v
(
S
)
Route
1 (LIUC)
4,880
ADA
2 (City Council)
6,260
ABLGFCA
3 (Association)
8,120
AEHKJIA
1, 2
6,910
ABLGFDCA
1, 3
8,170
ADEHKJIA
2, 3
9,710
ABLGFECHKJIA
1, 2, 3
10,090
ABLGFECDHKJIA


## 3.2. Four Players

Table5 gives the list of players and their stops in the four-player scenario.Table 5
Association of stops and players in the four-player scenario.
Player
Node
Address
Point of interest
(Public)
A
Via Kennedy
New station
LIUC
D
Via Matteotti 24
LIUC
City Council
C
Via Vittorio Veneto 25
Town hall
E
Via Mulini 24
Mater Domini Clinic
F
Via Lombardia 57
General
G
Via Tevere 11
General
J
Via Azimonti 15
ISI Secondary School
Association
H
Via Nazario Sauro 11
Gigante Supermarket
I
Via Piemonte 7
Multimedica Clinic
K
Viale Borri 33
Esselunga Supermarket
Trenord
B
Via Luigi Pomini 25
Old station
L
Piazza XXV Aprile
Old stationThe new partition is based on a slightly different approach. A fourth player, the railway company Trenord, is introduced and is paying for the two stops connecting the old station to the new one (nodes B and L). The secondary school ISI (node J) is given to the City Council, so that the association is now made of purely private agents. The clinic Mater Domini (node E) is also imputed to the City Council, due to its proximity to the other stops already owned by this player.Table6 shows the characteristic function in the case of four players.Table 6
Four-player scenario: coalitionsS and corresponding cost v(S).
S
v
(
S
)
Route
1 (LIUC)
4,880
ADA
2 (City Council)
8,920
ACGFEJA
3 (Association)
5,800
AIHKA
4 (Trenord)
3,450
ABLA
1, 2
9,300
ACDGFEJA
1, 3
6,270
ADHKIA
1, 4
4,910
ABLDA
2, 3
9,610
AGFECHKJIA
2, 4
9,030
ABLGFECJA
3, 4
5,990
ABLHKIA
1, 2, 3
9,990
AGFECDHKJIA
1, 2, 4
9,470
ABLGFEDCJA
1, 3, 4
6,300
ABLDHKIA
2, 3, 4
9,710
ABLGFECHKJIA
1, 2, 3, 4
10,090
ABLGFECDHKJIA


## 4. Cost Allocation Methods for the TSG

In a subadditive game the characteristic functionv satisfies
(1)v(S∪T)≤v(S)+v(T),
with S and T being disjoint subsets of N. Thus, the players join the grand coalition to achieve the minimum total cost and the solution of the game is represented by an allocation of v(N). A vectorx in Rn, where the ith component xi is the cost allocated to player i, is called a preimputation if ∑i∈Nxi=v(N) is satisfied, that is, collective rationality: the total cost is entirely allocated amongst the players. An imputation is a preimputation also satisfying for every i the requirement xi≤v({i}), that is, individual rationality: no player pays more than the stand-alone cost.The solutions belonging to the core are the preimputationsx also satisfying the condition ∑i∈Sxi≤v(S) or intermediate rationality: no coalition pays more than it would on its own. If the core is empty, every cost allocation x is unstable: a coalition that is allocated a cost higher than the stand-alone cost will not accept x.The Shapley vector is the solution satisfying the properties of collective rationality, symmetry (that two players who give the same contribution to every coalition can be swapped without changing the solution), additivity (that the solution of two games added together is the sum of the two solutions of the individual games), and dummy player property (that if a player adds to every coalition only its stand-alone value, then the solution gives it exactly that value). Theith component of the Shapley vector is defined as follows:
(2)xi*=∑S⊆N:i∈SS-1!N-S!N!vS-vSi,
where · represents the number of elements in the indicated set. The difference v(S)-v(S/{i}) is the marginal cost of player i in joining the coalition S as the last.The solutions based on separable and nonseparable costs satisfy collective rationality and symmetry. The separable cost for playeri is given by its marginal cost when i joins the grand coalition; that is,
(3)mi=vN-vNi.The nonseparable cost (that we assume to be nonnegative) is the residue after subtracting the separable costs:(4)gN=vN-∑i∈Nmi.This residual cost has to be distributed amongst the players. In effect, the separable costmi can be considered the lower bound of the cost allocated to player i, whilst mi+g(N), that is, what i pays if all the other players cover just their marginal costs, would be its upper bound. The different ways of splitting g(N) can be defined through the weights wi, so that
(5)xi=mi+wi∑i∈Nwig(N).
The ACAM (alternative costs avoided method) is based on the saving for player i in joining the grand coalition if it had to pay only its separable cost:
(6)wi=vi-mi.
This difference between the stand-alone cost and the marginal cost will be nonnegative if v is subadditive.The CGM (cost gap method) satisfies also individual rationality and the dummy player property. Given the nonseparable cost for coalitionS (that we assume to be nonnegative):
(7)gS=vS-∑i∈Smi,
then mi+g(S) would be the upper bound to the cost that player i has to pay in joining S, so that mi+min⁡S:i∈Sg(S) can be considered the maximum cost that i is willing to pay to join the grand coalition. The weights are thus defined by
(8)wi=min⁡S:i∈S⁡g(S).
To comply with the upper bound, ∑i∈Nmi≥g(N) must apply.


### 4.1. Three Players

Table7 shows the stand-alone cost, the marginal cost, and the solutions given by ACAM, CGM, and Shapley for each player in the three-player scenario. The distance being the only element of cost considered and the additional costs for three independent services as opposed to a single one are neglected.Table 7
Cost allocation for three players.
LIUC
City Council
Association
Total cost
Stand-alone cost
4,880
6,260
8,120
19,260
Marginal cost
380
1,920
3,180
—
ACAM
1,885
3,372
4,833
10,090
CGM
1,922
3,408
4,760
10,090
Shapley vector
1,870
3,330
4,890
10,090According to all solutions LIUC is the least charged player. The associated stop is located in the centre of Castellanza so that its impact on the cost of the grand coalition is limited as also shown by the small marginal cost.The association bears almost half of the total cost though having the same number of stops as the City Council. The stops imputed to the former are more widespread so that their marginal cost is higher.All of the solutions guarantee the players a lower cost than the stand-alone one, thus making cooperation convenient. Besides, there is ample scope for cooperation, the difference between the stand-alone cost and the marginal cost being large for all the players. The former cost represents an upper bound for a player as required by individual rationality, while the latter can be interpreted as a lower bound since it is the cost added by the player when last in joining the grand coalition, so that the other players would ask him to pay at least that amount.Table8 shows the saving of each player as a percentage of its stand-alone cost.Table 8
Savings as a percentage of the stand-alone costs.
LIUC
City Council
Association
ACAM
61%
46%
40%
CGM
61%
46%
41%
Shapley vector
62%
47%
40%LIUC is the player that benefits most from cooperation since its costs are reduced by about 60% followed by the City Council with a reduction of about 45% and last being the association with a 40% saving.


#### 4.1.1. Testing If the Solutions Belong to the Core

To test the stability of the solutionsx=(x1,x2,x3), we can verify if they belong to the core, that is, if they satisfy
(9)x1≤v1,x2≤v2,x3≤v3,x1+x2≤v1,2,x1+x3≤v1,3,x2+x3≤v2,3,x1+x2+x3=v1,2,3.The same conditions can be put in the equivalent form, showing the aforementioned marginal cost and stand-alone cost as, respectively, the lower bound and the upper bound:(10)v1,2,3-v2,3≤x1≤v1,v1,2,3-v1,3≤x2≤v2,v1,2,3-v1,2≤x3≤v3,x1+x2+x3=v1,2,3.For instance, the Shapley vector belongs to the core since conditions (9) are satisfied: in fact, 1,870 < 4,880, 3,330 < 6,260, 4,890 < 8,120, 5,200 < 6,910, 6,760 < 8,170, 8,179 < 9,710, 10,090 = 10,090. All the other solutions in Table 7 also belong to the core, so that in the three-player scenario no player or subset of players can gain from leaving the grand coalition.


### 4.2. Four Players

Table9 shows the different solutions in the scenario with four players, together with the stand-alone and the marginal costs. Compared to the previous scenario, it shows a huge decrease from 3,180 to 620 in the marginal cost of the association, while the City Council almost doubles its marginal cost. In fact, the City Council now has the stop corresponding to the ITI School so, if the association joins the coalition, the path would not require major changes. On the other hand, if the City Council joins the grand coalition as the last player it adds stops that are not close to the current path.Table 9
Results for the four-player scenario.
LIUC
City Council
Association
Trenord
Total cost
Stand-alone cost
4,880
8,920
5,800
3,450
23,050
Marginal cost
380
3,790
620
100
—
ACAM
1,669
5,259
2,103
1,059
10,090
CGM
1,653
5,265
2,109
1,063
10,090
Shapley vector
1,602
5,328
2,220
940
10,090The new player, Trenord, has the minimum marginal cost because, if it joins the grand coalition, the path would not change significantly. It is now the least charged player in the game, a position which was formerly held by LIUC. As in the previous scenario, the positive savings give no player a reason to act on its own.Table10 shows the cost reduction as a percentage of the stand-alone cost for each player. Trenord is the player which benefits most from cooperation. However, every player has a reduction in costs of at least 40%.Table 10
Savings as a percentage of the stand-alone cost in the four-player scenario.
LIUC
City Council
Association
Trenord
ACAM
66%
41%
64%
69%
CGM
66%
41%
64%
69%
Shapley vector
67%
40%
62%
73%


#### 4.2.1. Testing If the Solutions Belong to the Core

It can be verified that all the solutions belong to the core; that is, they satisfy the conditions(11)x1+x2+x3+x4=10,090,bbbbbbbi380≤x1≤4,880,bbbbbb3,790≤x2≤8,920,bbbbbbbi620≤x3≤5,800,bbbbbbbi100≤x4≤3,450.


## 4.1. Three Players

Table7 shows the stand-alone cost, the marginal cost, and the solutions given by ACAM, CGM, and Shapley for each player in the three-player scenario. The distance being the only element of cost considered and the additional costs for three independent services as opposed to a single one are neglected.Table 7
Cost allocation for three players.
LIUC
City Council
Association
Total cost
Stand-alone cost
4,880
6,260
8,120
19,260
Marginal cost
380
1,920
3,180
—
ACAM
1,885
3,372
4,833
10,090
CGM
1,922
3,408
4,760
10,090
Shapley vector
1,870
3,330
4,890
10,090According to all solutions LIUC is the least charged player. The associated stop is located in the centre of Castellanza so that its impact on the cost of the grand coalition is limited as also shown by the small marginal cost.The association bears almost half of the total cost though having the same number of stops as the City Council. The stops imputed to the former are more widespread so that their marginal cost is higher.All of the solutions guarantee the players a lower cost than the stand-alone one, thus making cooperation convenient. Besides, there is ample scope for cooperation, the difference between the stand-alone cost and the marginal cost being large for all the players. The former cost represents an upper bound for a player as required by individual rationality, while the latter can be interpreted as a lower bound since it is the cost added by the player when last in joining the grand coalition, so that the other players would ask him to pay at least that amount.Table8 shows the saving of each player as a percentage of its stand-alone cost.Table 8
Savings as a percentage of the stand-alone costs.
LIUC
City Council
Association
ACAM
61%
46%
40%
CGM
61%
46%
41%
Shapley vector
62%
47%
40%LIUC is the player that benefits most from cooperation since its costs are reduced by about 60% followed by the City Council with a reduction of about 45% and last being the association with a 40% saving.


### 4.1.1. Testing If the Solutions Belong to the Core

To test the stability of the solutionsx=(x1,x2,x3), we can verify if they belong to the core, that is, if they satisfy
(9)x1≤v1,x2≤v2,x3≤v3,x1+x2≤v1,2,x1+x3≤v1,3,x2+x3≤v2,3,x1+x2+x3=v1,2,3.The same conditions can be put in the equivalent form, showing the aforementioned marginal cost and stand-alone cost as, respectively, the lower bound and the upper bound:(10)v1,2,3-v2,3≤x1≤v1,v1,2,3-v1,3≤x2≤v2,v1,2,3-v1,2≤x3≤v3,x1+x2+x3=v1,2,3.For instance, the Shapley vector belongs to the core since conditions (9) are satisfied: in fact, 1,870 < 4,880, 3,330 < 6,260, 4,890 < 8,120, 5,200 < 6,910, 6,760 < 8,170, 8,179 < 9,710, 10,090 = 10,090. All the other solutions in Table 7 also belong to the core, so that in the three-player scenario no player or subset of players can gain from leaving the grand coalition.


## 4.1.1. Testing If the Solutions Belong to the Core

To test the stability of the solutionsx=(x1,x2,x3), we can verify if they belong to the core, that is, if they satisfy
(9)x1≤v1,x2≤v2,x3≤v3,x1+x2≤v1,2,x1+x3≤v1,3,x2+x3≤v2,3,x1+x2+x3=v1,2,3.The same conditions can be put in the equivalent form, showing the aforementioned marginal cost and stand-alone cost as, respectively, the lower bound and the upper bound:(10)v1,2,3-v2,3≤x1≤v1,v1,2,3-v1,3≤x2≤v2,v1,2,3-v1,2≤x3≤v3,x1+x2+x3=v1,2,3.For instance, the Shapley vector belongs to the core since conditions (9) are satisfied: in fact, 1,870 < 4,880, 3,330 < 6,260, 4,890 < 8,120, 5,200 < 6,910, 6,760 < 8,170, 8,179 < 9,710, 10,090 = 10,090. All the other solutions in Table 7 also belong to the core, so that in the three-player scenario no player or subset of players can gain from leaving the grand coalition.


## 4.2. Four Players

Table9 shows the different solutions in the scenario with four players, together with the stand-alone and the marginal costs. Compared to the previous scenario, it shows a huge decrease from 3,180 to 620 in the marginal cost of the association, while the City Council almost doubles its marginal cost. In fact, the City Council now has the stop corresponding to the ITI School so, if the association joins the coalition, the path would not require major changes. On the other hand, if the City Council joins the grand coalition as the last player it adds stops that are not close to the current path.Table 9
Results for the four-player scenario.
LIUC
City Council
Association
Trenord
Total cost
Stand-alone cost
4,880
8,920
5,800
3,450
23,050
Marginal cost
380
3,790
620
100
—
ACAM
1,669
5,259
2,103
1,059
10,090
CGM
1,653
5,265
2,109
1,063
10,090
Shapley vector
1,602
5,328
2,220
940
10,090The new player, Trenord, has the minimum marginal cost because, if it joins the grand coalition, the path would not change significantly. It is now the least charged player in the game, a position which was formerly held by LIUC. As in the previous scenario, the positive savings give no player a reason to act on its own.Table10 shows the cost reduction as a percentage of the stand-alone cost for each player. Trenord is the player which benefits most from cooperation. However, every player has a reduction in costs of at least 40%.Table 10
Savings as a percentage of the stand-alone cost in the four-player scenario.
LIUC
City Council
Association
Trenord
ACAM
66%
41%
64%
69%
CGM
66%
41%
64%
69%
Shapley vector
67%
40%
62%
73%


### 4.2.1. Testing If the Solutions Belong to the Core

It can be verified that all the solutions belong to the core; that is, they satisfy the conditions(11)x1+x2+x3+x4=10,090,bbbbbbbi380≤x1≤4,880,bbbbbb3,790≤x2≤8,920,bbbbbbbi620≤x3≤5,800,bbbbbbbi100≤x4≤3,450.


## 4.2.1. Testing If the Solutions Belong to the Core

It can be verified that all the solutions belong to the core; that is, they satisfy the conditions(11)x1+x2+x3+x4=10,090,bbbbbbbi380≤x1≤4,880,bbbbbb3,790≤x2≤8,920,bbbbbbbi620≤x3≤5,800,bbbbbbbi100≤x4≤3,450.


## 5. Conclusions

As shown by the TSP solution, the current bus route could be reduced to 10,090 kilometres from the initial 14,370 metres.In both the scenarios with three and four players cooperation brings benefits to all af them; in fact the costs are reduced by between 40% and 70%. The solutions given by ACAM, CGM, and Shapley belong to the core, so they enjoy the property of stability.



---

*Source: 696945-2014-12-14.xml*