Juan VIDAL-PUGA Eric BAHEL María GÓMEZ-RÚA�Universidade de Vigo Virginia Tech Universidade de Vigo �13 JULY 2023

Stability in shortest path problems

(old title)

ADVANCED ANALYTICS FOR A BETTER WORLD

Juan VIDAL-PUGA Eric BAHEL María GÓMEZ-RÚA�Universidade de Vigo Virginia Tech Universidade de Vigo �13 JULY 2023

Stable and weakly additive cost sharing in shortest path problems

Formerly Stability in shortest path problems

ADVANCED ANALYTICS FOR A BETTER WORLD

Outline

1. Shortest path problems
1. Motivation
2. Model
2. Core selection and other basic properties
3. Cost sharing rules
4. Cost Additivity and other properties
5. Characterization results

Motivation

• Consider a group of agents located at different geographical points who need to ship their demands of some homogeneous good from a fixed point (the source) to their respective locations.
• We can construct a network where each node represents one agent and each arc the cost of shipping one unit of the good through this connection.
• The cost on each arc of the network is linear in the total demand crossing it.
• Each agent can transport her demand directly from the source to her location, or indirectly (through intermediary nodes) if it turns out to be cheaper.
• The intermediaries have property rights over their respective locations and may refuse to provide access in order to ship the demand of a particular demander.

Motivation

• Cost Sharing Problem: the demanders have to determine the cheapest route (or shortest path) allowing to ship their demands, and the group has to decide how to reward intermediaries (who allow other to connect to the source at a lower

cost)

• Examples of applications: public transportation networks, airlines networks, resource supply chains, package delivery, ...
• An optimal network configuration obtains when each agent ships her demand through one of her shortest paths, that is, the path (from the source to the agent) that minimizes the unitary shipping cost.

The model

A Shortest Path Problem (SPP) is a tuple P = (N, c, x), where:

• N = {1, ..., n} is the set of agents who need to ship units of some commodity from a fixed point 0 (source) to their locations.
• c = {c(i, j) : i ∈ N∪{0}, j∈N, i≠j} is a cost matrix of nonnegative numbers giving the unit cost of shipping demands through each arc (i, j).
• x ∈ ℝ₊^N is the demand vector: each agent i ∈ N has a demand x_i ∈ ℝ₊ (of the commodity) to ship from the source to her location.

​

The set of SPP will be denoted as ℙ.

Since x and c depend on N, we can denote a SPP as P = (c, x).

The model

A Shortest Path Problem (SPP) is a tuple P = (N, c, x), where:

• N = {1, ..., n} is the set of agents who need to ship units of some commodity from a fixed point 0 (source) to their locations.
• c = {c(i, j) : i ∈ N∪{0}, j∈N, i≠j} is a cost matrix of nonnegative numbers giving the unit cost of shipping demands through each arc (i, j).
• x ∈ ℝ₊^N is the demand vector: each agent i ∈ N has a demand x_i ∈ ℝ₊ (of the commodity) to ship from the source to her location.

​

Note that:

1. The source (0) is not an agent.
2. The unit costs c(i,j) need not be symmetric. If c(i,j) = c(j,i) for any i, j ∈ N, we say that the SPP has symmetric arcs.

The model

Given i ∈ N, a path (of length K) to agent i is a sequence p ≡ (p_k)_k=0,....,K such that:

1. p_k ∈ N, for k = 1, 2, . . . , K
2. p₀ = 0 and p_k = i
3. p_k ≠ p_k′ for any distinct k, k′

Note that all paths p originate from the source 0 and cross each node p_k only once.

We denote as Pⁱ the set containing all paths to agent i.

Given P = (c, x), for any path p (of length K) to agent i,

c(p) ≡ ∑_k=1,...,Kc(p_k−1, p_k)

Thus, c(p) is the cost of shipping one unit from the source to agent i via path p.

For any i∈N, we call shortest path to agent i to any path p̄ⁱ ∈ Pⁱ that solves the problem

min{c(p) : p∈Pⁱ}.

The model

We define the cost of any nonempty coalition S ⊆ N as:

​

C_P(S) ≡ min{∑_j∈S x_j c(p^j) : p^j ∈ P^j and [p^j] ⊆ S, ∀j ∈ S}

​

where [p] denote the set of agents in the range of p, that is:

​

[p] ≡ {i ∈ N : p_k = i for some k = 1,... , K}.

​

C_P(S) is the lowest possible cost of shipping (from the source) the respective

demands of the members of S when using only the connections available in S.

In particular, C_P(S) = 0 whenever x_S = 0 (there is no demand to ship).

We also adopt the usual convention that C_P(∅) = 0.

The model

• A cost sharing rule (CSR) is a mapping y: ℙ⟶ℝ^N that assigns to each P ∈ ℙ a cost allocation y(P) ∈ ℝ^N such that ∑_i∈N y_i = C_P(N).

​

A cost sharing rule is a mechanism which, for any given problem P, allows to divide

between agents the total cost C_P(N) of satisfying their respective demands and assuring efficiency.

Note that we allow for negative cost shares.

Core selection

Given a shortest path problem P = (c, x), the core of P is the set

​

Core(P) ≡ {y ∈ ℝ^N : ∑_i∈N y_i = C_P(N), ∑_i∈S y_i ≤ C_P(S), ∀S ⊊ N}.

​

• A cost sharing rule y satisfies Core Selection if y(P) ∈ Core(P) for all P ∈ ℙ.

​

The selected cost allocation should not allow any subgroup of players to profitably defect from the grand coalition (in other words, using only the connections available to the players in this subgroup to fulfill their demands should result in a higher cost than the join cost share of the subgroup).

Another basic properties

For every j ∈ N, denote by e^j ∈ ℝ^N the vector of demands characterized by e^j_j = 1

and e^j_i = 0, if i ∈ N\{j}.

We call the SPP (c, e^j) an elementary SPP.

​

• A cost sharing rule y satisfies Demand Additivity if y(P) = ∑_j∈N x_j y(c, e^j) for all (c, x) ∈ ℙ.

​

This property allows to extend a cost allocation rule from elementary problems (where only one agent demands a single unit, which is typically shipped via intermediaries) to general problems (where each agent has an arbitrary demand).

Another basic properties

Given a bijection σ: N → N and given P = (c, x), P′ = (c′, x′) ∈ ℙ, we say that P′ is σ-equivalent to P if it holds that:

(a) x′_i = x_σ(i) for all i ∈ N, and

(b) c′(i, j) = c(σ(i), σ(j)) for all i,j ∈ N and c′(0, i) = c(0, σ(i)) for all i ∈ N.

​

• A cost sharing rule y satisfies Anonymity if, for all bijection σ: N⟶N and all P, P′ ∈ ℙ such that P′ is σ-equivalent to P, y_i(P′) = y_σ(i)(P) for all i ∈ N.

​

Given two problems that are identical up to a permutation σ of the players’ labels, each agent i should pay the same cost share in P′ as its counterpart σ(i) pays in the equivalent problem P.

Basic properties

• A cost sharing rule y satisfies Core Selection if y(P) ∈ Core(P) for all P ∈ ℙ.

​

• A cost sharing rule y satisfies Demand Additivity if y(P) = ∑_i∈N x_i y(c, eⁱ) for all P=(c, x)∈ℙ.

​

• A cost sharing rule y satisfies Anonymity if, for all bijection σ: N→N and all P, P′ ∈ ℙ such that P′ is σ-equivalent to P, y_i(P′) = y_σ(i)(P) for all i ∈ N.

​

We first focus on cost sharing rules that satisfy these three properties.

​

We call any cost sharing rule in this family an Anonymous Demand-Additive Core Selector (ADACS)

Demander rule

Each agent pays the cost of their shortest path for each unit demanded.

​

y^d_i(c, x) = x_i min{c(p) : p∈Pⁱ}, for all (c, x)∈ℙ and i∈N.

​

Agents who demand zero pay nothing.

This rule is favorable to demanders.

​

y^d = (180, 0, 80).

Demander rule

Each agent pays the cost of their shortest path for each unit demanded.

​

y^d_i(c, x) = x_i min{c(p) : p∈Pⁱ}, for all (c, x)∈ℙ and i∈N.

​

Agents who demand zero pay nothing.

This rule is favorable to demanders.

​

y^d = (180, 0, 80).

Demander rule

Each agent pays the cost of their shortest path for each unit demanded.

​

y^d_i(c, x) = x_i min{c(p) : p∈Pⁱ}, for all (c, x)∈ℙ and i∈N.

​

Agents who demand zero pay nothing.

This rule is favorable to demanders.

​

y^d = (180, 0, 80).

Supplier rule

For each P = (c, x) ∈ ℙ and i∈N, y^s_i(P) is the demand additivity CSR defined as:

​

• y^s_i(P^j) = min{c(p) : p∈P^j\{p̄^j}} if i = j
• y^s_i(P^j) = (c(p̄^j) − min{c(p) : p∈P^j\{p̄^j}}/(|p̄^j| − 1) if i∈ [p̄^j]\{j}
• y^s_i(P^j) = 0 if i ∉ [p̄^j]

​

where p̄^j denotes (one of) the shortest path(s) to j∈N under the cost matrix c and

P^j ≡ (c, e^j).

​

The supplier rule charges to each demander j the cost of her second shortest path,

and equally splits between all suppliers of j the excess payment thus collected.

Supplier rule. An example

• The cost of the shortest path to agent 1 is c(0231) = 90 and that of the of the second shortest paths is c(021) = 60 + 70 = 130. The difference between the cost of both paths is 130 − 90 = 40.
• There are two intermediaries (agent 2 and agent 3) who help agent 1 to connect ot the source on path p̄¹ = 0231. Hence, y^s(P¹) = (130, −20, −20).
• For agent 3, the costs of the shortest path and the second shortest path are respectively c(023) = 80 and c(03) = 120.
• There is only one intermediary (agent 2) on path p̄³ = 023.�Hence, y^s(P³) = (0, −40, 120).
• Thus, �y^s(P) = 2·(130, −20, −20) + 1·(0, −40, 120) = (260, 80, 80)

​

​

​

Supplier rule. An example

• The cost of the shortest path to agent 1 is c(0231) = 90 and that of the of the second shortest paths is c(021) = 60 + 70 = 130. The difference between the cost of both paths is 130 − 90 = 40.
• There are two intermediaries (agent 2 and agent 3) who help agent 1 to connect ot the source on path p̄¹ = 0231. Hence, y^s(P¹) = (130, −20, −20).
• For agent 3, the costs of the shortest path and the second shortest path are respectively c(023) = 80 and c(03) = 120.
• There is only one intermediary (agent 2) on path p̄³ = 023.�Hence, y^s(P³) = (0, −40, 120).
• Thus, �y^s(P) = 2·(130, −20, −20) + 1·(0, −40, 120) = (260, 80, 80)

​

​

​

Supplier rule. An example

• The cost of the shortest path to agent 1 is c(0231) = 90 and that of the of the second shortest paths is c(021) = 60 + 70 = 130. The difference between the cost of both paths is 130 − 90 = 40.
• There are two intermediaries (agent 2 and agent 3) who help agent 1 to connect ot the source on path p̄¹ = 0231. Hence, y^s(P¹) = (130, −20, −20).
• For agent 3, the costs of the shortest path and the second shortest path are respectively c(023) = 80 and c(03) = 120.
• There is only one intermediary (agent 2) on path p̄³ = 023.�Hence, y^s(P³) = (0, −40, 120).
• Thus, �y^s(P) = 2·(130, −20, −20) + 1·(0, −40, 120) = (260, 80, 80)

​

​

​

Supplier rule. An example

• The cost of the shortest path to agent 1 is c(0231) = 90 and that of the of the second shortest paths is c(021) = 60 + 70 = 130. The difference between the cost of both paths is 130 − 90 = 40.
• There are two intermediaries (agent 2 and agent 3) who help agent 1 to connect ot the source on path p̄¹ = 0231. Hence, y^s(P¹) = (130, −20, −20).
• For agent 3, the costs of the shortest path and the second shortest path are respectively c(023) = 80 and c(03) = 120.
• There is only one intermediary (agent 2) on path p̄³ = 023.�Hence, y^s(P³) = (0, −40, 120).
• Thus, �y^s(P) = 2·(130, −20, −20) + 1·(0, −40, 120) = (260, 80, 80)

​

​

​

Supplier rule. An example

• The cost of the shortest path to agent 1 is c(0231) = 90 and that of the of the second shortest paths is c(021) = 60 + 70 = 130. The difference between the cost of both paths is 130 − 90 = 40.
• There are two intermediaries (agent 2 and agent 3) who help agent 1 to connect ot the source on path p̄¹ = 0231. Hence, y^s(P¹) = (130, −20, −20).
• For agent 3, the costs of the shortest path and the second shortest path are respectively c(023) = 80 and c(03) = 120.
• There is only one intermediary (agent 2) on path p̄³ = 023.�Hence, y^s(P³) = (0, −40, 120).
• Thus, �y^s(P) = 2·(130, −20, −20) + 1·(0, −40, 120) = (260, 80, 80)

​

​

​

Supplier rule. An example

• The cost of the shortest path to agent 1 is c(0231) = 90 and that of the of the second shortest paths is c(021) = 60 + 70 = 130. The difference between the cost of both paths is 130 − 90 = 40.
• There are two intermediaries (agent 2 and agent 3) who help agent 1 to connect ot the source on path p̄¹ = 0231. Hence, y^s(P¹) = (130, −20, −20).
• For agent 3, the costs of the shortest path and the second shortest path are respectively c(023) = 80 and c(03) = 120.
• There is only one intermediary (agent 2) on path p̄³ = 023.�Hence, y^s(P³) = (0, −40, 120).
• Thus, �y^s(P) = 2·(130, −20, −20) + 1·(0, −40, 120) = (260, 80, 80)

​

​

​

Alexia rule

Fix a bijection π : N⟶{1,2,...,n}.

Focusing on an elementary problem (c, e^j) ∈ ℙ, let p̄^j be a shortest path to the demander j and let m ≡ |[p̄^j] \ {j}|.

We define a particular cost allocation denoted as y^π.

In the trivial cases where m=0 or π(j) = 1, we have y^π_j(c, e^j) = c(p̄^j) and y^π_i(c, e^j) = 0

for all i ∈ N \ {j}.

Otherwise, we write without loss of generality

{1_π , . . . , m_π} ≡ {i ∈ [p̄^j] \ {j} : π(i) < π(j)} ≠∅.

Alexia rule

• First, call p^j₁ (one of) the cheapest path(s) to j among those that do not contain agent 1_π; and then assign to player 1_π the cost share y^π_1π(c, e^j) = c(p̄^j) − c(p^j₁) = α⁰ − α¹ ≤ 0.
• Next, consider the reduced SPP (N \ {1_π}, c₁ , e^j), where the cost matrix c₁ is defined by: for all k ∈ (N \ {1_π})∪{0}, k ∈ N \ {1_π} (with k≠l), �c₁(k, l) = min(c(k, l), c(k, 1_π) + c(1_π, l) − y^π_1π).

In words, any two agents of the reduced problem have the option to connect via agent 1_π after paying to it the fee y^π_1π in case they find it beneficial.

• Then, mimicking the first step for this reduced problem, one can assign to agent 2_π the cost share y^π_2π(P^j) = c₁(p̄^j₁) − c₁(p^j₂) = α¹ − α².
• We repeat the update of the cost matrix and compute the cost shares until all intermediaries {1_π,..., m_π} have been served.
• Finally, one must assign to the demander j a cost share that covers the cost of the shortest path and the fees paid to all intermediaries:�y^π_j(c, e^j) = c(p̄^j) − y^π_1π(c, e^j) − ... − y^π_mπ (c, e^j).

Alexia rule

For each P = (c, x) ∈ ℙ, y^a_i(P) is the demand additivity CSR defined as:

​

y^a(c, e^j) = ∑_𝜋∈𝛱y^π(c, e^j)/|𝛱|

​

where 𝛱 is the set of all bijections π : N ⟶ {1,2,...,n}.

​

Alexia rule. An example

Fix bijection π = [321] and agent j = 1. Let consider the elementary problem (c, e¹).

• t = 1. Recall that p̄¹ = 0231 is the shortest path to agent 1. Then m = |[p̄¹] \ {1}| = 2 (i.e., the number of agents in the range of p̄¹ \ {1}).

Moreover 1_π = 3. �We denote α⁰ = c(p̄¹) = 60 + 20 + 10 = 90.

• Let α¹ be the lowest cost of serving agent j = 1 while excluding agent 3 (c(p^j₁)). In this case, c₁(021) = 60 + 70 = 130 = α¹.

We define

y^π_1π (c, e¹) = c(p̄^j) − c(p^j₁) = α⁰ − α¹ ≤ 0, i.e.,

y^π_1π (c, e¹) is the difference between the cost of the

shortest path to agent 1 (c(p̄¹)) and c(p¹₁).

Thus, y^π₃(c, e¹) = 90 − 130 = −40.

​

​

​

Alexia rule. An example

Fix bijection π = [321] and agent j = 1. Let consider the elementary problem (c, e¹).

• t = 1. Recall that p̄¹ = 0231 is the shortest path to agent 1. Then m = |[p̄¹] \ {1}| = 2 (i.e., the number of agents in the range of p̄¹ \ {1}).

Moreover 1_π = 3. �We denote α⁰ = c(p̄¹) = 60 + 20 + 10 = 90.

• Let α¹ be the lowest cost of serving agent j = 1 while excluding agent 3 (c(p^j₁)). In this case, c₁(021) = 60 + 70 = 130 = α¹.

We define

y^π_1π (c, e¹) = c(p̄^j) − c(p^j₁) = α⁰ − α¹ ≤ 0, i.e.,

y^π_1π (c, e¹) is the difference between the cost of the

shortest path to agent 1 (c(p̄¹)) and c(p¹₁).

Thus, y^π₃(c, e¹) = 90 − 130 = −40.

​

​

​

Alexia rule. An example

Fix bijection π = [321] and agent j = 1. Let consider the elementary problem (c, e¹).

• t = 1. Recall that p̄¹ = 0231 is the shortest path to agent 1. Then m = |[p̄¹] \ {1}| = 2 (i.e., the number of agents in the range of p̄¹ \ {1}).

Moreover 1_π = 3. �We denote α⁰ = c(p̄¹) = 60 + 20 + 10 = 90.

• Let α¹ be the lowest cost of serving agent j = 1 while excluding agent 3 (c(p^j₁)). In this case, c₁(021) = 60 + 70 = 130 = α¹.

We define

y^π_1π (c, e¹) = c(p̄^j) − c(p^j₁) = α⁰ − α¹ ≤ 0, i.e.,

y^π_1π (c, e¹) is the difference between the cost of the

shortest path to agent 1 (c(p̄¹)) and c(p¹₁).

Thus, y^π₃(c, e¹) = 90 − 130 = −40.

​

​

​

Alexia rule. An example

• t = 2: We consider the reduced SPP (N\{1_π}, c₁, e^j), where the cost matrix c₁ is defined by:�c₁(k, l) = min(c(k, l), c(k, 1_π) + c(1_π, l) − y^π_1π), �for all k ∈ (N \ {1_π}) ∪ {0}, k ∈ (N \ 1_π) (with k ≠ l).

In this case:

• c₁(0, 1) = min(c(0, 1), c(0, 3) + c(3, 1)−y^π₃) �= min(200, 120 + 10 − (−40)) = 170.
• c₁(0, 2) = min(c(0, 2), c(0, 3) + c(3, 2)−y^π₃) �= min(60, 120 + 20 − (−40)) = 60.
• c₁(2, 1) = min(c(2, 1), c(2, 3) + c(3, 1)−y^π₃) �= min(70, 20 + 10 − (−40)) = 70.

Alexia rule. An example

• t = 2: We consider the reduced SPP (N\{1_π}, c₁, e^j), where the cost matrix c₁ is defined by:�c₁(k, l) = min(c(k, l), c(k, 1_π) + c(1_π, l) − y^π_1π), �for all k ∈ (N \ {1_π}) ∪ {0}, k ∈ (N \ 1_π) (with k ≠ l).

In this case:

• c₁(0, 1) = min(c(0, 1), c(0, 3) + c(3, 1)−y^π₃) �= min(200, 120 + 10 − (−40)) = 170.
• c₁(0, 2) = min(c(0, 2), c(0, 3) + c(3, 2)−y^π₃) �= min(60, 120 + 20 − (−40)) = 60.
• c₁(2, 1) = min(c(2, 1), c(2, 3) + c(3, 1)−y^π₃) �= min(70, 20 + 10 − (−40)) = 70.

Alexia rule. An example

• t = 2: We consider the reduced SPP (N\{1_π}, c₁, e^j), where the cost matrix c₁ is defined by:�c₁(k, l) = min(c(k, l), c(k, 1_π) + c(1_π, l) − y^π_1π), �for all k ∈ (N \ {1_π}) ∪ {0}, k ∈ (N \ 1_π) (with k ≠ l).

In this case:

• c₁(0, 1) = min(c(0, 1), c(0, 3) + c(3, 1)−y^π₃) �= min(200, 120 + 10 − (−40)) = 170.
• c₁(0, 2) = min(c(0, 2), c(0, 3) + c(3, 2)−y^π₃) �= min(60, 120 + 20 − (−40)) = 60.
• c₁(2, 1) = min(c(2, 1), c(2, 3) + c(3, 1)−y^π₃) �= min(70, 20 + 10 − (−40)) = 70.

Alexia rule. An example

• t = 2: We consider the reduced SPP (N\{1_π}, c₁, e^j), where the cost matrix c₁ is defined by:�c₁(k, l) = min(c(k, l), c(k, 1_π) + c(1_π, l) − y^π_1π), �for all k ∈ (N \ {1_π}) ∪ {0}, k ∈ (N \ 1_π) (with k ≠ l).

In this case:

• c₁(0, 1) = min(c(0, 1), c(0, 3) + c(3, 1)−y^π₃) �= min(200, 120 + 10 − (−40)) = 170.
• c₁(0, 2) = min(c(0, 2), c(0, 3) + c(3, 2)−y^π₃) �= min(60, 120 + 20 − (−40)) = 60.
• c₁(2, 1) = min(c(2, 1), c(2, 3) + c(3, 1)−y^π₃) �= min(70, 20 + 10 − (−40)) = 70.

Alexia rule. An example

• t = 2 (cont.): Mimicking the fist step for this reduced problem, we obtain:

α¹ = c₁(p̄¹) = c₁(021) = 130 (cost of the shortest path to 1 in c₁); and

α² = c₁(p¹₂) = 170 (lowest cost of the shortest cost of serving agent 1 in c₁ while excluding agent 2).

We assign to agent 2_π = 2,

y^π₂(c, e¹) = α¹ − α² = 130 − 170 = −40.

• Finally, we get

y^π₁(c, e¹) = c(p̄¹) − y^π_1π(c, e¹) − y^π_2π(c, e¹) = 90 − (−40) − (−40) = 170.

That is to say, y^π(c, e¹) = (170, −40, −40).

Alexia rule. An example

• t = 2 (cont.): Mimicking the fist step for this reduced problem, we obtain:

α¹ = c₁(p̄¹) = c₁(021) = 130 (cost of the shortest path to 1 in c₁); and

α² = c₁(p¹₂) = 170 (lowest cost of the shortest cost of serving agent 1 in c₁ while excluding agent 2).

We assign to agent 2_π = 2,

y^π₂(c, e¹) = α¹ − α² = 130 − 170 = −40.

• Finally, we get

y^π₁(c, e¹) = c(p̄¹) − y^π_1π(c, e¹) − y^π_2π(c, e¹) = 90 − (−40) − (−40) = 170.

That is to say, y^π(c, e¹) = (170, −40, −40).

Alexia rule. An example

• t = 2 (cont.): Mimicking the fist step for this reduced problem, we obtain:

α¹ = c₁(p̄¹) = c₁(021) = 130 (cost of the shortest path to 1 in c₁); and

α² = c₁(p¹₂) = 170 (lowest cost of the shortest cost of serving agent 1 in c₁ while excluding agent 2).

We assign to agent 2_π = 2,

y^π₂(c, e¹) = α¹ − α² = 130 − 170 = −40.

• Finally, we get

y^π₁(c, e¹) = c(p̄¹) − y^π_1π(c, e¹) − y^π_2π(c, e¹) = 90 − (−40) − (−40) = 170.

That is to say, y^π(c, e¹) = (170, −40, −40).

Alexia rule. An example

• t = 2 (cont.): Mimicking the fist step for this reduced problem, we obtain:

α¹ = c₁(p̄¹) = c₁(021) = 130 (cost of the shortest path to 1 in c₁); and

α² = c₁(p¹₂) = 170 (lowest cost of the shortest cost of serving agent 1 in c₁ while excluding agent 2).

We assign to agent 2_π = 2,

y^π₂(c, e¹) = α¹ − α² = 130 − 170 = −40.

• Finally, we get

y^π₁(c, e¹) = c(p̄¹) − y^π_1π(c, e¹) − y^π_2π(c, e¹) = 90 − (−40) − (−40) = 170.

That is to say, y^π(c, e¹) = (170, −40, −40).

Alexia rule. An example

Proceeding as before, we obtain the cost shares y^π described by the following table, for each bijection π ∈ Π and each elementary problem P^j.

​

​

​

​

​

​

​

​

​

​

That is,

y^a(c, e¹) = (130, −20, −20), y^a(c, e³) = (0, −20, 100).

Hence, y^a(P) = x₁ y^a(c, e¹) + x₃ y^a(c, e³) = 2y^a(c, e¹) + y^a(c, e³) = (260, −60, 60).

Family ADACS

Theorem

The demander rule y^d is an ADACS

​

Theorem

The supplier rule y^s is an ADACS.

​

Theorem

The alexia rule y^a is an ADACS.

Cost additivity

We may request cost shares to be additive in the cost matrix.

​

• A cost sharing rule y satisfies Cost Additivity if �y(c+c′, e^j) = y(c, e^j) + y(c′, e^j) �for any two elementary problems (c, e^j), (c′, e^j)∈ℙ.

​

However, no cost sharing rule satisfies this property.

​

Take for example N = {1,2} and c, c’ given by the figures. Then, for any j∈N, C_{(c,ej )}(N) = C_(c′,ej) (N) = 0 whereas C_(c+c′,ej)(N) = 1.

Hence, this property is incompatible with efficiency.

​

​

Cost additivity

• A cost sharing rule y satisfies One-path Cost Additivity if �y(c+c′, e^j) = y(c, e^j) + y(c′, e^j)

when (c, e^j), (c′, e^j) ∈ℙ are elementary problems with a common shortest path to agent j.

Theorem

If n > 2, then the demander rule y^d is the unique cost sharing rule satisfying Core Selection and One-path Cost Additivity.

​

If instead n = 2 (say, N = {1, 2}), then a cost sharing rule y satisfies Core Selection and One-path Cost Additivity if and only if there exists a function α : ℝ₊^N→ [0, 1]² such that, for all (c, x) ∈ ℙ,

y(c, x) = α₁(x) · y^s(c, x) + (1 − α₁(x)) · y^d(c, x), if c(0, 2) > c(0, 1) + c(1, 2);

y(c, x) = α₂(x) · y^s(c, x) + (1 − α₂(x)) · y^d(c, x), otherwise.

​

First characterization

Cost additivity

• A cost sharing rule y satisfies Two-path Cost Additivity if �y(c+c′, e^j) = y(c, e^j) + y(c′, e^j)

when (c, e^j), (c′, e^j) ∈ℙ are elementary problems with a common shortest path and a common second-shortest path to agent j.

Other properties

• A cost sharing rule y satisfies Supplier Equal Change if �y_i(c, e^j) − y_i(c, e^j) = y_k(c′, e^j) − y_k(c′, e^j) for all i, k ∈ [p̄^j] \ j

when (c, e^j), (c′, e^j) ∈ℙ are elementary problems with a common shortest path p̄^j to agent j.

​

If the shortest path to agent j remains the same from the cost matrix c to the cost matrix c′, then all suppliers of agent j should see their cost shares change in the same way.

Other properties

• A cost sharing rule y satisfies Path Independence if �y_j(c, e^j) = y_j(c′, e^j) for all j ∈ N

when (c, e^j), (c′, e^j) ∈ℙ are elementary problems with |N| > 1, c(p̄^j_c) = c′(p̄^j_c′) and �min{c(p^j) : p^j ∈P^j\{p̄^j_c}} = min{c′(p^j) : p^j ∈P^j\{p̄^j_c’}}.

​

A demander should pay the same subsidy to its respective groups of suppliers (under c and c′) if these groups have the same added-value. In other words, what should determine the amount paid to the suppliers is the reduction in the demander’s shipping cost rather than the size or composition of the group of suppliers.

Second characterization

Theorem

An ADACS y satisfies Two-path Cost Additivity, Supplier Equal Change, and Path Independence if and only if it is a convex combination of the supplier rule and the

demander rule, that is to say, if and only if y = α·y^s + (1 − α)·y^d for some α ∈ [0, 1].

ADVANCED ANALYTICS FOR A BETTER WORLD