Routing-Proofness in Congestion-Prone Networks

Abstract

We consider the problem of sharing the cost of connecting a large number of atomless agents in a network. The centralized agency elicits the target nodes that agents want to connect, and charges agents based on their demands. We look for a cost-sharing mechanism that satisfies three desirable properties: efficiency which charges agents based on the minimum total cost of connecting them in a network, stand-alone core stability which requires charging agents not more than the cost of connecting by themselves directly, and limit routing-proofness which prevents agents from profitable reporting as several agents connecting from A to C to B instead of A to B. We show that these three properties are not always compatible for any set of cost functions and demands. However, when these properties are compatible, a new egalitarian mechanism is shown to satisfy them. When the properties are not compatible, we find a rule that meets stand-alone core stability, limit routing-proofness and minimizes the budget deficit.

1. Introduction

Congestion is a form of negative externality to the networks of any size. These networks can include but are not limited to road networks, internet networks, telecommunication networks as well as utility power grid networks and other networks [1,2,3,4,5,6]. The emergence of congestion can be attributed to the instance in which a large number of selfish agents, each wishing to route traffic via one’s preferred links (or edges), without taking into account the actions of other agents in the network [7]. Such selfish routing behavior generates discrepancy between the socially optimal traffic pattern (minimizing overall delay or cost) and the selfish-routing behavioral outcome (also known as the non-cooperative Nash equilibrium). [8,9] suggest that the non-cooperative Nash equilibrium need not in general optimize the social welfare (minimizing overall delay or cost in this context). Indeed, the non-cooperative Nash equilibrium could generate a loss substantially higher than the social optimum. This implies that the discrepancy could cause some unwanted direct or indirect consequences such as network congestion, traffic paralysis as well as social welfare loss.

An earlier work by Roughgarden [8] investigates and quantifies the efficiency loss of the network performance due to the self-interested agents. The degradation is calculated by the worst-possible ratio between the Nash equilibrium and the social optimal traffic and is called the price of anarchy (POA) [8]. The closer the POA is to one, the less efficiency loss it generates between the Nash equilibrium and social optimum. Roughgarden shows that if the cost (latency) functions on the links in the network are linear, then the POA is equal to $\frac{4}{3}\approx 1.333$; if the cost functions are cubic, then the POA is approximately 1.896; and if the cost functions are polynomials of degree $\le p$ where $p>0$, then POA is a asymptotically equal to $\theta \left(\frac{p}{lnp}\right)$ as $p\to \infty$1. Finally, if the cost functions are unrestricted to any allowable class of functions (e.g., linear, quadratic, cubic, polynomials, etc.), then the POA is unbounded. These results indicate that the efficiency loss can be immensely large and the consequences generated by the selfish routing behavior can be extremely severe in the network.

In order to avoid such consequences, it is therefore important to manage the congestion of a network. In this paper, we consider a network with a set of nodes in which every node interconnects with at least one other node by a link. There is a variable congestion cost associated with each link that depends on the units of demands sent by agents. The cost may represent any maintenance cost or accessing fee of the links. Different links may have different congestion costs. There are a large number of self-interested agents who wish to route their traffic from an arbitrary node to another node using the links in the network. We assume the self-interested agents are interested in routing only via links that will incur the minimal cost or delay. In addition, we also include the possibility for a single agent performing a special type of strategic maneuver (or similarly, routing maneuver). The concept of strategic maneuver was first introduced by Dominique and Moulin [5], and followed by Moulin [10], who study mechanisms where coalition of agents in a large network can furtively create several alias and misreport themselves as several agents. Formally, that means an agent may report and route her traffic to the target node as two or more agents in hope of lowering her connection cost. To illustrate such scenario, we suppose there is an agent with initial node i and target node j. Then, she may report herself as two agents first connecting from node $i\leftrightarrow k$, then from node $k\leftrightarrow j$ if she finds such strategic maneuver is less costly than connecting directly from node $i\leftrightarrow j$.

Unlike the decentralized networks such as road networks or internet networks, the networks being considered in this paper are operated in a centralized manner. We imagine there is a central authority that possesses the power to elicit the demand characteristics from all agents in the networks and is capable of computing and implementing the optimal traffic pattern at any time. Meanwhile, we imagine there is a centralized agency that will help satisfy the needs demanded by the agents at minimal total delay or cost. Since agents are self-interested, they need not have the incentive to reveal their true routing schemes. The centralized agency is therefore vulnerable to any misreports by individual units, or by a coalition of subgroup of units. Such strategic maneuver behavior will potentially distort the socially optimal traffic pattern (minimizing overall cost or delay) in the sense that links with relatively lower cost are more likely to be congested, which may in turns incurring higher total cost or delay.

Therefore, in order to prevent effectively such strategic maneuvers, thereby improving the performance of a network, there is a need to design cost-sharing mechanisms to charge on each agent in the network so that the action of strategic maneuver will make no difference in terms of lowering connection costs. Moulin calls any cost-sharing mechanisms or cost-sharing rules routing-proof if they are invulnerable to such strategic maneuvers [10]. Technically, it is not as difficult to find a routing-proof mechanism, if routing-proofness is the only constraint that we are aiming to satisfy. For instance, the simple average cost mechanism (AC) will do2. By splitting the total cost equally among all agents in the network, each agent is to pay a share of the average cost. As a result, any agent who intends to report as two or more agents will simply have to pay double or more of the average cost. Nevertheless, this mechanism may not be charging every agent or coalition fairly if the average cost exceeds the cost of a subnetwork meeting all connection needs of the group (stand-alone objections). This fairness-related constraint is known as stand-alone core stability and is the primary design constraint in the minimum cost spanning tree problem [10] and a variety of other problems.

Our work, therefore, has the objective to design or propose a cost-sharing mechanism satisfying the following three properties:

• Efficiency: the minimum total cost of connecting all agents to their target nodes;
• Stand-alone core stability: no groups of agents pay more than the cost of a subnetwork meeting all connection needs of the group;
• Routing-proofness: no agent can lower its cost by reporting as several agents along an alternative path connecting her target nodes.

1.1. Innovation of the Paper and Overview of the Results

While efficiency and stand-alone core stability are standard properties in the literature (see related literature section), the main innovation of this paper comes from studying the three properties together in a large economy with congestion. Previous work by Moulin [10] studied these properties in a model without congestion cost, where the cost associated with each link is fixed and the costs are independent of the units of traffic sent by agents. This assumption, while convenient, is not realistic in a variety of networks such as traffic, telecommunication and other large and complex networks (e.g., the internet). Our paper extends the model introduced by Moulin [10] to the case with variable congestion costs that depend on the units of traffic being connected in our network. The adoption of variable congestion costs substantially increases the difficulty of computing the efficiency of a general network. In particular, computing the social optimum (efficiency) of a general network is Non-deterministic Polynomial-time-hard (NP-hard) [12], unless the cost functions satisfy certain conditions (e.g., linearity or all cost functions are identical in the network [12]). Thus, our work is sharply different from [10] where the minimum cost (efficiency) can easily be computed by applying a simple greedy algorithm [13].

The second innovation of the paper comes from studying the case where there are a large number of self-interested agents in the network such that each of them only controls a negligible fraction of the overall traffic (i.e., agents have zero mass). These types of assumptions are critical for the internet and other large an complex networks, where even if an agent reroutes in the network, then because the amount of traffic each agent controls is infinitesimally small relative to the overall traffic, the costs charged to agents should not be too sensitive and changing significantly. This assumption is also relevant for rerouting in airline networks, where agents wishing to fly from A to B, can instead buy two one-way tickets, from A to C and C to B, if proven cheaper than a direct ticket from A to B. One agent manipulating the airline system will have no effect on prices and a substantially large amount of population is needed for changes in prices to take effect. Furthermore, in practice, it is relatively hard to coordinate a large group of agents that change prices in a network. In order to address this feature, we introduce a new axiom, the limit routing-proofness, that adapts Moulin’s concept of routing-proofness to the case where agents are extremely small relative to the overall traffic. We study the limitation of such an axiom in a congestion-prone network. In particular, we provide the necessary and sufficient conditions for the existence of rules that satisfy limit routing-proofness along with efficiency and stand-alone core stability (Theorem 1).

A third innovation of the paper comes from actually introducing a mechanism that satisfies these three properties when they are compatible. Our mechanism builds on perhaps the most studied mechanism in the cost-sharing literature, the uniform rule [14,15], and adapt it to our network setting with congestion in a way that Limit routing-proofness is satisfied. In order to compute the outcome of the mechanism, we actually provide an algorithm to compute the prices that agents pay, and show that such prices coincide with the cost-shares of our new mechanism (Proposition 1).

1.2. Related Literature

The stand-alone core stability and efficiency are two traditional properties in the network literature [4,10,16,17]; while routing-proofness is a relatively more recent idea [5,10,18]. The predecessor of routing-proofness was first coined the axiom of no transit originated by Hanriet and Moulin in [5]. In [5], Hanriet and Moulin suggest two cost-allocation methods: private-cost and external cost methods that satisfy the axiom of additivity, sustainability and no transit. These methods work only for the case without congestion.

The closest paper to our work is Moulin [10], who studies a congestion-free network cost-sharing problem and where the no transit axiom is renamed as routing-proofness. The paper constructs two core stable and routing-proof cost-sharing rules: weighted Shapley value (WSH) and weighted spanning rule (WSP) together satisfying the stand-alone core stability and routing-proofness. The first family of the rules requires only that the connecting costs to be zero or one, whereas the second family allows for arbitrary costs but requires a spanning traffic. As such, neither of these rules work in our general congestion-prone setting.

Another related paper is a real-world application of routing-proofness by Dong, Guo and Wang [18]. In there, a highway toll pricing method is proposed to assign the toll charges to different types of agents in a linear network. The proposed method satisfies the stand-alone test for vehicles, cost recovery (for road sections with no cross-subsidizing) and a version of routing-proofness in the sense that no agents can reduce the toll charges by exiting and re-entering the highway consecutively [18]. In contrast with the papers above, the model presented in [18] is a congestion-prone network rather than congestion-free, but the proposed method only works in a linear network, whereas our networks would typically have cycles, and that is where the strength of our routing-proofness property comes from.

Related work also comes from the cost-sharing literature on the implementation of efficient costs. Juarez and Kumar [2] discuss the appropriateness on the implementation of various efficient cost-sharing mechanisms when agents choose their paths strategically as if they are in a routing game. A comparison of different classes of mechanisms such as the average cost mechanism, proportional to stand-alone mechanism, (weighted) egalitarian mechanism and the Shapley mechanism is done. It is important to note that the paper does not deal with routing-proofness issues, and as such, all the mechanisms studied there fail to meet our test.

Other implementation work include Hougaard and Tvede [19,20], who characterize cost-minimizing networks at the equilibrium of games by changing the announcement rule. The sequential sharing of costs and profits is studied axiomatically in Juarez et al. [11]. Kumar [21] also investigates secure implementation in cost-sharing models without congestion, while Hougaard et al. [22] study the sharing of profits in trees and Moulin et al. [23] study the division of the costs/profits of non-redundant items. In contrast with this literature, our work is the first to address from an axiomatic view the division of costs in congestion-prone networks by atomless agents.

2. The Model

A network cost-sharing problem (or simply a problem) is a triple $\mathit{P}=\langle N,C,\theta \rangle$, where $N=(V,L)$ is a network with finite set of nodes $V=\{n_1,\dots ,n_r\}$ and a finite set of undirected links $L=\{l_1,\dots ,l_s\}$ connecting such nodes. $C=(C_1(·),\dots ,C_s(·))$ is a vector of cost functions associated to each link, where the cost function $C_i:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+}$ associated to link $l_i$ is strictly increasing and strictly convex. The vector $\theta =({\theta }_1,\dots ,{\theta }_s)\in {\mathbb{R}}_{+}^s$ is the traffic demand associated to each link, where ${\theta }_i$ representing the units of traffic demanded on link $l_i$ (i.e., ${\theta }_i$ represents the mass of the agents interested in connected the two nodes of link $l_i$). We denote by $\mathcal{P}$ the set of all network cost-sharing problems.

For an arbitrary network cost-sharing problem $\mathit{P}$, the link $l_i$ will be simply denoted by i if there is no confusion. Given the cost function $C_i$ associated to link i, we denote by $A{C}_i\left(x\right)=\frac{C_i\left(x\right)}{x}$ the average cost associated to such link. Let ${\mathcal{P}}_i=\{p_1,\dots ,p_t\}$ be the set of all feasible paths without cycles that connect link i in the network.3

Definition 1.

(a) Given a path k and $\alpha >0$, we denote by $\alpha ·k=(v_1,\dots ,v_s)\in {\mathbb{R}}^s$ such that $v_i=\alpha$ if $i\in k$ and $v_i=0$ if $i\notin k$.

(b) Given any link $i\in L$ and a demand ${\theta }_i$ for that link, a connection vector $(w_1^i,\dots ,w_s^i)$ generates demand ${\theta }_i$ if there exists non-negative weights ${\{{\alpha }^k\}}_{k\in {\mathcal{P}}_i}$ such that ${\sum }_{k\in {\mathcal{P}}_i}{\alpha }^k={\theta }_i$ and $(w_1^i,\dots ,w_s^i)={\sum }_{k\in {\mathcal{P}}_i}{\alpha }^k·k$.

(c) Given demands $({\theta }_1,\dots ,{\theta }_s)$, a connection vector $(w_1,..,w_s)$ is feasible if for every link $i\in \{1,\dots ,s\}$ there exists a connection vector $(w_1^i,\dots ,w_s^i)$ that generates demand ${\theta }_i$ such that $(w_1,\dots ,w_s)={\sum }_{i=1}^s(w_1^i,\dots ,w_s^i)$.

While agents demanding link i are interested in connecting the nodes of such link, this connection can be achieved directly via link i or indirectly via alternative paths connecting link i. In particular, the demands of traffic ${\theta }_i$ on link i can be split into multiple alternative paths where each particular path indirectly connects link i (part (b) in definition above). A connection vector $(w_1,\dots ,w_s)$ is said to be feasible if it is the sum of all these paths.

Definition 2.

The total cost (or simply a cost) of a feasible connection vector $(w_1,\dots ,w_s)$ is $C(w_1,\dots ,w_s)={\sum }_{i=1}^s{C}_i\left(w_i\right)$.

With each element $w_i$ represents all possible amounts of traffic on link i, the total cost of connecting all agents with connection vector $(w_1,\dots ,w_s)$ is the sum of each cost function $C_i(·)$ evaluated at $w_i$ for all $i=1,\dots ,s$.

Recall that we are in a centralized setting where the planner has the ability to select the paths of some agents demanding a given link. A natural objective for the planner is to select a path that minimizes the cost. This is incorporated in the following definition.

Definition 3.

Given a set of demands $({\theta }_1,\dots ,{\theta }_s)$, a feasible connection vector $\left(w_1^{*},\dots ,w_s^{*}\right)$ is efficient if for any other feasible connection vector $(\widetilde{w_1},\dots ,\widetilde{w_s})$, we have $C(w_1^{*},\dots ,w_s^{*})\le C(\widetilde{w_1},\dots ,\widetilde{w_s})$.

We say that a feasible connection vector of a given set of demands is efficient if there exists a feasible connection vector $(w_1^{*},\dots ,w_s^{*})$ such that the total cost evaluated at $(w_1^{*},\dots ,w_s^{*})$ is always less than or equal to the total cost evaluated any other connection vectors $(\widetilde{w_1},\dots ,\widetilde{w_s})$. Such connection vector will generate the least cost (also referred as efficient cost) of serving all the agents in the network.

Definition 4 (Mechanism and efficient mechanism).

(a) A cost-sharing mechanism (also called rule or solution) is a continuous function ξ $:\mathcal{P}\to {\mathbb{R}}_{+}^s$ that allocates a set of cost shares for the use of every link at every network cost-sharing problem. (b) A cost-sharing mechanism is efficient at problem P if it divides the efficient cost among agents:

$$\sum _{i\in L}{\xi }_i\left(\mathit{P}\right)·{\theta }_i=C^{*}\left(\mathit{P}\right)$$

where $C^{*}\left(\mathit{P}\right)$ is the efficient cost at a problemP.

We focus on a mechanism that allocates payments based on the demands of single links. That is, the planner cannot distinguish the names of agents who demand the same link. This is a standard assumption in the cost-sharing literature. An efficient cost-sharing mechanism is a centralized mechanism that meets the demands efficiently and redistribute this cost based only on the demand of every link. Thus, the sum of the charges assigned by the mechanism, when multiplied by the demands of each link, is equal to the efficient cost at a given problem.

Definition 5 (Stand-alone core stability).

Consider a network cost-sharing problem $\mathit{P}=\langle N,C,\theta \rangle$. A cost-sharing mechanism ξ satisfies the stand-alone core stability at $\mathit{P}$ if for any link i, we have that ${\xi }_i\left(\mathit{P}\right){\theta }_i\le C_i\left({\theta }_i\right)$.

Definition 5 ensures the absence of stand-alone objections from agents caused by overcharging from the implemented mechanism. This constraint plays an important role in terms of fairness to prevent agents from being charged more than the cost of the links they actually demanded. Moreover, it also helps to prevent agents who demand inexpensive links from subsidizing those who demand expensive links in a network.

Definition 6 (Limit routing-proofness).

Consider a network cost-sharing problem $\mathit{P}=\langle N,C,\theta \rangle$. A cost-sharing mechanism is limit routing-proof (LRP) at P if for each link i, and each path $p_k\in {\mathcal{P}}_i$ that connects link i we have that:

$${\xi }_i\left(\mathit{P}\right)\le \sum _{j\in p_k}{\xi }_j\left(\mathit{P}\right).$$

(1)

Limit routing-proofness prevents agents from routing their demand along alternative paths that may also meet their demand. In particular, at a problem P, by Equation (1), an agent demanding link i pays ${\xi }_i\left(\mathit{P}\right)$. If such an agent decides to demand an alternative path $p_k$ that also connects i (by posing as separate agents along path $p_k$) his charge will be ${\displaystyle \sum _{j\in p_k}}{\xi }_j\left(\mathit{P}\right)$, which is not smaller than ${\xi }_i\left(\mathit{P}\right)$ under limit routing-proof (LRP).

3. Efficiency, Stand-Alone Core Stability and LRP

The trade-off between stand-alone core stability and incentive compatibility (here, interpreted as routing-proofness) for efficient mechanisms has already been identified in the literature. Indeed, in a related network model where the connection demands of agents need to be met, Juarez and Kumar [2] study two mechanisms: the average-cost mechanism (AC) that divides the cost of the efficient network equally among all the agents and the proportional to stand-alone mechanism (PR) that divides the cost of the efficient network in proportion to the cost of their demands.4 In our setting, the AC mechanism meets LRP, as any agent pays the same cost-share regardless of the link demanded, thus an agent splitting their demand in two or more links will pay twice or more their cost-share. Unfortunately, it is easy to see that AC does not meet the stand-alone core stability, as it might happen that agents demanding a very inexpensive link cross-subsidize agents demanding very expensive links. PR is an exact opposite situation, meeting stand-alone stability but failing to meet LRP. Therefore, neither of them meet our three objectives. Other traditional mechanisms, like Aumann–Shapley, also fail to meet our demanding LRP. Therefore, in addressing the compatibility between stand-alone core stability, efficiency and limit routing-proofness, new mechanisms need to be developed.

One of the most studied rules in the cost-sharing literature is the uniform rule [14,15,24], which is a variation of AC that respect stand-alone core stability. This rule can be trivially adapted to our network setting by considering the cost of each link as the demand of the agents.5 Both the uniform rule and AC divide the total cost of the network across all agents, however, their similarity begins to diverge when the charges reach the threshold of the stand-alone cost of a link (presumably the smallest stand-alone cost first). In that case, AC will disregard the stand-alone cost and continue increasing charges to agents on each link i equally without bound. In contrast, the uniform rule will stop assigning charges to agents whose links have reached their stand-alone costs. The remaining cost will then be covered by the links in which the stand-alone costs are yet to be reached. Note that this characteristic will definitely preserve the property of stand-alone core stability. Unfortunately, the uniform rule does not meet LRP. The next section provides a variation of the uniform rule that meets LRP, stand-alone core stability and efficiency, whenever possible. We call it the egalitarian mechanism.

3.1. A New Egalitarian Mechanism

Given a network cost-sharing problem $\mathit{P}=\langle N,C,\theta \rangle$, our ultimate objective is to find a cost-sharing mechanism such that the set of cost shares allocated by the mechanism will be efficient, limit routing-proof and core stable. In order to achieve that, we formulate the network cost-sharing problem along with the constraints into a set of system of equations.

$$\begin{array}{cc}\hfill \sum _{i=1}^s{\lambda }_i{\theta }_i& =EFF({\theta }_1,\dots ,{\theta }_s)\hfill \end{array}$$

(2)

$$\begin{array}{cc}\hfill {\lambda }_i{\theta }_i& \le C_i\left({\theta }_i\right)\mathrm{for}\mathrm{all}i=1,\dots ,s\hfill \end{array}$$

(3)

$$\begin{array}{cc}\hfill {\lambda }_i& \le \sum _{\begin{array}{c}l\in p_k\end{array}}{\lambda }_l\mathrm{for}\mathrm{all}{p}_k\in {\mathcal{P}}_i\mathrm{and}\mathrm{for}\mathrm{all}i=1,\dots ,s\hfill \end{array}$$

(4)

$$\begin{array}{cc}\hfill {\lambda }_i& \ge 0\mathrm{for}\mathrm{all}i=1,\dots ,s.\hfill \end{array}$$

(5)

We denote ${\lambda }_i$ the payment charged to each agent on link i. Other variables are defined exactly the same way as the model in Section 2. $EFF({\theta }_1,\dots ,{\theta }_s)$ represents the efficient cost of the network computed as a function of $({\theta }_1,\dots ,{\theta }_s)$. We express efficiency in this form because computing the efficiency (social optimality) of a network is generally a NP-hard problem.6

Equation (2) requires that the sum of the charges, when multiplied by the demands over all links $i=1,\dots ,s$ is exactly equal to the efficiency of the network. In particular, this constraint represents the efficiency property.

Equation (3) describes the stand-alone core stability for all agents demanding link i. Essentially, this constraint says that the amount of assigned charges to each agent on link i should never exceed the cost of connecting the target pairs by themselves via link i.

Equation (4) represents the limit routing-proofness constraint for a general network. Recall that for any link i, ${\mathcal{P}}_i$ is the set of all feasible alternative paths $\{p_1,\dots ,p_t\}$ that connect link i. The limit routing-proofness constraint then implies that the charge ${\lambda }_i$ on link i must be less than or equal to the sum of ${\lambda }_l$ for $l\in p_k$ on all possible paths $p_k\in \{p_1,\dots ,p_t\}$7.

Equation (5) is an obvious one, which says that the cost-shares assigned to agents must be greater than or equal to zero. The systems (2)–(5) might have multiple solutions or they might not have any, is it will be shown in the following sections.

Definition 7 (Egalitarian solution at λ*).

Consider a parameter ${\lambda }^{*}>0$. The egalitarian solution at ${\lambda }^{*}$, denoted by $\left(E{G}^{T_{{\lambda }^{*}}}\right)$, assigns at the network cost-sharing problem $\langle N,C,\theta \rangle$ the set of cost-shares $({\lambda }_1^{*},\cdots ,{\lambda }_s^{*})$ such that the cost share of link $i=1,\dots ,s$ is determined by

$$\begin{array}{cc}\hfill & {\lambda }_i^{*}=\underset{p_k\in {\mathcal{P}}_i}{min}\left\{{\lambda }^{*},A{C}_i\left({\theta }_i\right),\left[\sum _{\begin{array}{c}l\in p_k\end{array}}{\lambda }_l^{*}\right]\right\}.\hfill \end{array}$$

(6)

This solution achieves revenue equal to $T_{{\lambda }^{*}}={\displaystyle \sum _{i=1}^s}{\lambda }_i^{*}{\theta }_i$.

Note that $E{G}^{T_{{\lambda }^{*}}}$ is a well defined cost-sharing solution, as there exists a unique set of values that satisfy Equation (6). They can be easily computed by starting for small values, say at ${\lambda }^{*}=0$, at which point the solution returns ${\lambda }_i={\lambda }^{*}$ for all $i=1,\dots ,s$. As we increase the value of ${\lambda }^{*}$, the stand-alone constraint ($A{C}_i\left({\theta }_i\right)$) or LRP constraints ($\sum _{\begin{array}{c}l\in p_k\end{array}}{\lambda }_l^{*}$) bind. The formal computation of this rule is described in the next section.

By construction, egalitarian mechanism (EG), $E{G}^{T_{{\lambda }^{*}}}$ meets stand-alone core stability and LRP, but it may not be efficient. Indeed, the revenue generated by EG${}^{T_{{\lambda }^{*}}}$ equals to $T_{{\lambda }^{*}}={\sum }_{i=1}^s{\lambda }_i^{*}{\theta }_i$ which may be smaller or larger than $EFF({\theta }_1,\dots ,{\theta }_s)$. Clearly, $T_{{\lambda }^{*}}$ is non-decreasing in ${\lambda }^{*}$, and it may be that $T_{{\lambda }^{*}}$ is actually constant for a large value of ${\lambda }^{*}$. Indeed, consider two values ${\underline{\lambda }}^{*}$ and ${\overline{\lambda }}^{*}$ such that ${\overline{\lambda }}^{*}>{\underline{\lambda }}^{*}>A{C}_i\left({\theta }_i\right)$ for all i. Under $E{G}^{T_{{\underline{\lambda }}^{*}}}$, the payment ${\lambda }_i^{*}$ to the agents along link i is not larger than $A{C}_i\left({\theta }_i\right)$. Thus, any increases to ${\overline{\lambda }}^{*}>{\underline{\lambda }}^{*}$ will also hit the same stand-alone constraints, and the cost-shares of the agents remain unchanged.

From the analysis, the maximum revenue generated under EG${}^{T_{{\lambda }^{*}}}$ occurs when ${\lambda }^{*}=max\{A{C}_1\left({\theta }_1\right),\dots ,A{C}_s\left({\theta }_s\right)\}$. We denote by $T_{{\lambda }^{*}}^{max}$ such a maximum revenue. Note that if the revenue $T_{{\lambda }^{*}}^{max}>EFF({\theta }_1,\dots ,{\theta }_s)$, then by the continuity of $T_{{\lambda }^{*}}\left({\lambda }^{*}\right)$, we can always find one ${\lambda }^{**}$ such that $T_{{\lambda }^{**}}=EFF({\theta }_1,\dots ,{\theta }_s)$. This ${\lambda }^{**}$ will generate an allocation EG${}^{T_{{\lambda }^{**}}}$8 and it will be called the egalitarian solution (${\mathit{EG}}^{{\mathit{T}}_{{\lambda }^{*}}}$). Note also that when this egalitarian solution exists, it will be efficient, core stable and limit routing-proof.

The computation of EG above is similar to the computation of the uniform rule, except for the additional LRP constraints, $\left[{\displaystyle \sum _{\begin{array}{c}l\in p_k\end{array}}}{\lambda }_l^{*}\right]$, in Equation (6). Such a variation substantially changes how EG assigns cost shares to the agent in different links. In contrast with the uniform rule, the EG mechanism proposed in this paper might not exists for an arbitrary network cost-sharing problem P. The existence of EG depends on whether the last stand-alone cost being reached can cover the loss incurred by the replacement of the limit routing-proofness constraints. We see this in the next sections.

3.2. A Numerical Example of EG

In this section, we will provide a step-by-step numerical example illustrating how EG allocates charges to agents. Consider the network in Figure 1 and a demand $\theta =(2,6,3)$. That is, a total of 11 units of traffic were demanded: two units are demanded on link 1; six units were demanded on link 2; and three units were demanded on link 3.

The computation of the efficient allocation for this network requires no re-routing of traffic, therefore providing an efficient cost equal to $2{\left(2\right)}^2+6^2+3^2=53$.

The stand-alone cost for each link is:

$$C_1\left({\theta }_1\right)=2{\left(2\right)}^2=8,C_2\left({\theta }_2\right)=6^2=36\mathrm{and}{C}_3\left({\theta }_3\right)=3^2=9.$$

Now, we can formulate the problem and apply EG as in Equations (2)–(5):

$$2{\lambda }_1+6{\lambda }_2+3{\lambda }_3=53$$

(7)

$$2{\lambda }_1\le 2{\left(2\right)}^2,6{\lambda }_2\le {\left(6\right)}^2,3{\lambda }_3\le {\left(3\right)}^2$$

(8)

$${\lambda }_1+{\lambda }_2\ge {\lambda }_3,{\lambda }_2+{\lambda }_3\ge {\lambda }_1,{\lambda }_1+{\lambda }_3\ge {\lambda }_2$$

(9)

$${\lambda }_1\ge 0,{\lambda }_2\ge 0,{\lambda }_3\ge 0$$

(10)

Under EG, we have:

$$\begin{array}{c}\hfill \underset{{\lambda }_1^{*}{\theta }_1}{\underbrace{2min\left\{{\lambda }^{*},2\left(2\right),({\lambda }_2^{*}+{\lambda }_3^{*})\right\}}}+\underset{{\lambda }_2^{*}{\theta }_2}{\underbrace{6min\left\{{\lambda }^{*},\left(6\right),({\lambda }_1^{*}+{\lambda }_3^{*})\right\}}}+\underset{{\lambda }_3^{*}{\theta }_3}{\underbrace{3min\left\{{\lambda }^{*},\left(3\right),({\lambda }_1^{*}+{\lambda }_2^{*})\right\}}}=53\end{array}$$

By Equation (6), we have

$${\lambda }_1^{*}=min\left\{{\lambda }^{*},2\left(2\right),({\lambda }_2^{*}+{\lambda }_3^{*})\right\}$$

(11)

$${\lambda }_2^{*}=min\left\{{\lambda }^{*},\left(6\right),({\lambda }_1^{*}+{\lambda }_3^{*})\right\}$$

(12)

$${\lambda }_3^{*}=min\left\{{\lambda }^{*},\left(3\right),({\lambda }_1^{*}+{\lambda }_2^{*})\right\}$$

(13)

Solving the above system simultaneously will give us an egalitarian solution, if there exists one. We attacked this problem by gradually increasing ${\lambda }^{*}$ until the first stand-alone constraint $A{C}_i\left({\theta }_i\right)$ for $i=1,2,3$ is reached. This happens when ${\lambda }^{*}=3$.

Note the fact that the stand-alone constraints of ${\lambda }_1^{*}$ and ${\lambda }_2^{*}$ are still non-binding implies ${\lambda }_1^{*}+{\lambda }_2^{*}>{\lambda }_3^{*}$. So by (11), suppose ${\lambda }^{*}=3$ for all ${\lambda }_i^{*}$, we check if (11) is satisfied:

$$\begin{array}{c}\hfill 2{\lambda }^{*}+6{\lambda }^{*}+3{\lambda }^{*}=2\left(3\right)+6\left(3\right)+3\left(3\right)=33<53.\end{array}$$

Obviously, ${\lambda }^{*}=3$ does not achieve efficiency. Hence, we must continue increasing ${\lambda }^{*}$ on ${\lambda }_1^{*}$ and ${\lambda }_2^{*}$ while leaving ${\lambda }_3^{*}=3$ as its stand-alone constraint is reached.

Next, we applied the same logic and continue increasing ${\lambda }^{*}$. It is easy to see that the next stand-alone constraint being reached will be $A{C}_1\left({\theta }_1\right)$. That is, when ${\lambda }^{*}=4$.

We know that ${\lambda }_3^{*}=3$ and the stand-alone constraint of ${\lambda }_2^{*}$ is still non-binding when ${\lambda }^{*}=4$. This implies ${\lambda }_2^{*}+{\lambda }_3^{*}={\lambda }_2^{*}+3>4={\lambda }_1^{*}$. Thus, the minimum value in (11) will never be the limit routing-proofness constraint. We check (11),

$$2{\lambda }^{*}+6{\lambda }^{*}+3{\lambda }^{*}=2\left(4\right)+6\left(4\right)+3\left(3\right)=41<53$$

Again, efficiency is still not attained with ${\lambda }^{*}={\lambda }_1^{*}={\lambda }_2^{*}=4$ and ${\lambda }_3^{*}=3$. Leaving ${\lambda }_1^{*}=4$ and ${\lambda }_3^{*}=3$, we have by efficiency,

$$\begin{array}{cc}\hfill {\lambda }_2^{*}& =\frac{EFF({\theta }_1,{\theta }_2,{\theta }_3)-{\lambda }_1^{*}{\theta }_1-{\lambda }_2^{*}{\theta }_2}{{\theta }_3}=\frac{53-2\left(4\right)-3\left(3\right)}{6}=6.\hfill \end{array}$$

Recall that (12) implies

$${\lambda }_2^{*}=min\{{\lambda }^{*},6,6(4+3))\}$$

In this case, we need to be cautious about the limit routing-proofness constraint. If it happens that the minimum value is obtained from the limit routing-proofness constraint, then there will be no egalitarian solution satisfying Equation (11).

We proceed to check if $({\lambda }_1^{*},{\lambda }_2^{*},{\lambda }_3^{*})=(4,6,3)$ satisfies all the constraints given by Equations (7)–(13).

$$\begin{array}{cc}\hfill \mathrm{Equation}\left(7\right)& \Rightarrow 2\left(4\right)+6\left(6\right)+3\left(3\right)=53\hfill \\ \hfill \mathrm{Equation}\left(8\right)& \Rightarrow 2\left(4\right)=2{\left(2\right)}^2,6\left(6\right)=36,3\left(3\right)=9\hfill \\ \hfill \mathrm{Equation}\left(9\right)& \Rightarrow {\lambda }_1^{*}+{\lambda }_2^{*}=4+6=10>3={\lambda }_3^{*}\hfill \\ & \Rightarrow {\lambda }_2^{*}+{\lambda }_3^{*}=6+3=9>4={\lambda }_1^{*}\hfill \\ & \Rightarrow {\lambda }_1^{*}+{\lambda }_3^{*}=4+3=7>6={\lambda }_2^{*}\hfill \\ \hfill \mathrm{Equation}\left(10\right)& \Rightarrow {\lambda }_1^{*}=4>0,{\lambda }_2^{*}=6>0,{\lambda }_3^{*}=3>0.\hfill \end{array}$$

Hence, we have found an egalitarian solution EG${}^{T_{{\lambda }_{**}}^{max}}=({\lambda }_1^{*},{\lambda }_2^{*},{\lambda }_3^{*})=(4,6,3)$ such that efficiency, stand-alone core stability and limit routing-proofness are simultaneously satisfied. Interestingly, since the demands ${\theta }_1,{\theta }_2$ and ${\theta }_3$ are precisely the optimal allocations that generates the total minimum cost, the stand-alone core stability and efficiency force the egalitarian solution ${\lambda }_i^{*}=A{C}_i\left({\theta }_i\right)$ for all $i=1,2,3$.

3.3. An Example for Problem Where EG does not Exists

Consider the network in Figure 2 and $\theta =(1,1,4)$. That is, where one unit of traffic demand link 2 ↔ 3, one unit of traffic demand link 1 ↔ 3; and four units of traffic demand link 1 ↔ 2.

Efficiency requires $\frac{7}{3}$ units of traffic demanding link 1 ↔ 2 to be routed along the alternative route on links 1 ↔ 3 and 3 ↔ 2. This will generate an efficient cost equal to

$$EFF({\theta }_1,{\theta }_2,{\theta }_3)=4{(4-\frac{7}{3})}^2+{(1+\frac{7}{3})}^2+{(1+\frac{7}{3})}^2=\frac{100}{3}.$$

In order to compute the stand-alone cost note that

$$C_1\left({\theta }_1\right)={\left(1\right)}^2=1,C_2\left({\theta }_2\right)={\left(1\right)}^2=1,C_3\left({\theta }_3\right)=4{\left(4\right)}^2=64.$$

Thus, if the central authority decides to impose a personalized charge to every agent, then it can impose at most a total amount of $1 to each agent on link 1 and 2; $16 to each agent on link 3.

For EG to exists, it needs to recoup the efficient cost $\frac{100}{3}$. As we increase ${\lambda }^{*}$, the stand-alone constraints of link 1 and 2 are reached immediately followed by link 3. That is, ${\lambda }_i^{*}=A{C}_i\left({\theta }_i\right)$ = 1 for $i=1,2$.

Hence, by efficiency, we have that

$$\begin{array}{cc}\hfill {\lambda }_3^{*}& =\frac{EFF({\theta }_1,{\theta }_2,{\theta }_3)-{\lambda }_1^{*}{\theta }_1-{\lambda }_2^{*}{\theta }_2}{{\theta }_3}\hfill \\ & =\frac{94}{12}=7.8\overline{3}<\frac{64}{4}=16.\hfill \end{array}$$

Thus, the charges assigned to each agent under EG are $({\lambda }_1^{*},{\lambda }_2^{*},{\lambda }_3^{*})=(1,1,7.8\overline{3})$. Note that this solution satisfies stand-alone core stability and efficiency but it fails to meet the limit routing-proofness constraint, as the agents demanding link 3 would prefer to pose as two agents demanding links 1 and 2.

4. The RP Algorithm

We now turn our focus on investigating the necessary and sufficient conditions for the existence of an efficient, core stable and limit routing-proof egalitarian solution. To derive those conditions, we introduce an algorithm called the RP algorithm.

Definition 8 (The RP algorithm).

Given a problem P, the RP algorithm assigns at any step a price to every link in the network. This price can be of two types: temporary or permanent. We define a semi-cycle to be a cycle of links such that all but one of the links have assigned permanent prices.

• Step 0. We start from a network N and assign temporary prices $T_i=A{C}_i\left({\theta }_i\right)$ to every link i in the network. Continue to step 1.
• Step 1. The algorithm ends when all the assigned prices are permanent. For a given set of prices, replace the smallest temporary price with a permanent price of the same value. The rest of the prices are unchanged. If the new prices generate a semi-cycle, then we continue to step 2. Otherwise, we repeat step 1 with the new prices.
• Step 2. For every semi-cycle $p_k$ with link i that has attached a temporary price $T^i$, we replace their temporary price with a new temporary price $T_i^{\prime }=min\left\{T^i,{\sum }_{l\in p_k}{P}_l\right\}.$ Moreover, if every path $p_j\in {\mathcal{P}}_i$ is a semi-cycle, then $T_i^{\prime }$ becomes permanent. We continue to step 1 with the new set of prices.

The algorithm finishes in at most $2s$ steps, where s is the number of links in the network, since every time that step 1 runs, a price moves from temporary to permanent.

By assigning temporary prices at the average cost in step 1, the RP algorithm ensures for stand-alone core stability. On the other hand, replacing a new temporary price either with the minimum of the average cost, or the sum of the prices on the alternative paths of a semi-cycle respects the LRP property.9

Note that the construction of the RP algorithm and EG are similar, but their objectives and operations are slightly different. To be precise, the RP algorithm always finds the feasible and maximal prices that it can charge the agents in order to meet the LRP constraint. This is in contrast with EG where it always allocates the minimal prices to agents subject to their stand-alone costs. Such discrepancy is due to the nature of the operation of EG and the RP algorithm. The RP algorithm always starts from the maximal prices possible (e.g., starts from the stand-alone prices) and solves the problem backwards, whereas EG attacks the problem from the lowest prices possible while gradually increasing it and stops when efficiency is reached.

Example of RP Algorithm

We provide a numerical example showing how prices are computed under the RP algorithm.

Consider an arbitrary network with the links numbered as in Figure 3a. Without loss of generality, suppose the average costs are given as in Figure 3b. By the RP algorithm, we start assigning a temporary price—average cost to each link until every link has a temporary price. For instance, we assign $T_1=A{C}_1=2$ to link 1 and $T_2=A{C}_2=4$ to link 2, etc. Starting from the smallest temporary price, $T_1=A{C}_1=2$, $T_1$ will be replaced with a permanent price $P_1=2$ followed by the second, third smallest temporary prices and so forth at every point in time until the first semi-cycle is formed.

Note that the first semi-cycle is formed by links 1, 2 and 4. Thus, the temporary price $T_3$ on link 3 is replaced by a new temporary price $T_3^{\prime }=min\{{\underbrace{20}}_{A{C}_3},{\underbrace{12}}_{2+4+6}\}$ = 12. This new temporary price $T_3^{\prime }$ will become a permanent price only if all the ascending smaller prices are replaced with permanent prices. Once the price is replaced, we continue to replace the next smallest price, which is price of link 7 in this case. In there a second semi-cycle is formed by links 2 and 7 and we replace the temporary price $T_9$ with $T_9^{\prime }=min\{{\underbrace{25}}_{A{C}_9},{\underbrace{9}}_{2+7}\}=9$.10

Continue replacing in this fashion and ensuring all the semi-cycles are extracted until each temporary price becomes permanent price as shown in Figure 4b.

5. Main Results

We now turn to the main results of this paper. As mentioned in the previous section, our results will rely heavily on the application of RP algorithm.

Proposition 1.

For any network cost-sharing problem the prices given by the RP algorithm coincide with EG${}^{T_{{\lambda }^{*}}^{max}}$.

The proof is in Appendix A.

The RP algorithm takes the permanent price $P_i={min}_{p_k\in {\mathcal{P}}_i}\left\{A{C}_i,{\sum }_{l\in p_k}{P}_l\right\}$ for all i. If the minimum temporary price is ${\sum }_{l\in p_k}{P}_l$ for some $p_k$, then the RP algorithm will never replace any permanent prices less than that. Therefore, the revenue generated under these prices and demands is going to be maximal. That is, RP merely searches for the maximal prices that it can achieve while satisfying together the stand-alone core stability and limit routing-proofness.

On the other hand, EG also allocates charges to agents with respect to the stand-alone core stability and limit routing-proofness. It chooses, or controls the parameter ${\lambda }^{*}$ where the revenue target (this might include efficiency) is just achieved and stops. Hence, if the revenue target is precisely the maximal revenue that is achievable by the RP algorithm, then the allocation EG${}^{T_{{\lambda }^{*}}^{max}}=({\lambda }_1^{*},\dots ,{\lambda }_s^{*})$ coincides with the price vector $\overline{P}=(P_1,\dots ,P_s)$ simply because EG and RP algorithm are constructed in an identical way. Indeed, since the RP algorithm always searches for the maximal revenue that it can achieve in a network, the total charge (resp. total revenue) allocated (resp. collected) by EG can do no better than that maximal revenue. Thus, the maximal revenue provided by the RP algorithm is an upper bound for which EG can achieve in a network.

Theorem 1.

Consider an arbitrary network cost-sharing problem.

a.

Let agent j* be the last agent in the RP algorithm. A stand-alone core stable, efficient and limit routing-proof price vector $\overline{P}=(P_1,\dots ,P_s)$ exists if and only if one of following conditions is satisfied:

i 

$\frac{EFF({\theta }_1,...,{\theta }_s)-{\sum }_{i\ne j^{*}}{P}_i{\theta }_i}{{\theta }_{j^{*}}}\le {min}_{p_k\in {\mathcal{P}}_{j^{*}}}\left\{A{C}_{j^{*}},{\sum }_{l\in p_k}{P}_l\right\}$, where ${\mathcal{P}}_{j^{*}}$ is the set of all feasible alternative paths of $j^{*}$;

ii 

$EFF({\theta }_1,\dots ,{\theta }_s)\le {\sum }_{i=1}^s{P}_i{\theta }_i$

b.

The egalitarian solution exists if and only if either condition (i) or (ii) is satisfied.

The proof is in Appendix A. Theorem 1a states the necessary and sufficient conditions for which the price vector $\overline{P}=(P_1,\dots ,P_s)$ is core stable, efficient and limit routing-proof. Note that condition (ii) is implied by condition (i), but added as a reference. On the other hand, part (b) tells us that the egalitarian solution is guaranteed to exist if either condition (i) or (ii) hold.

Corollary 1.

Given a general network, suppose that the average cost satisfies the (generalized)11 triangle inequality, that is,

$$A{C}_i\left({\theta }_i\right)\le \underset{p_k\in {\mathcal{P}}_i}{min}\left\{\sum _{l\in p_k}A{C}_l\left({\theta }_l\right)\right\}$$

for any demand of link i, then the egalitarian solution exists.

The proof is in Appendix A. Note that this condition is sufficient but not necessary for the existence of egalitarian solution. To see this, consider the following network.

In Figure 5a, the average costs are given by $3, $10 and $5 for link 1, 2, 3 respectively. Clearly, the triangle inequality is not satisfied since $5 + $3 = $8 < $10. Under the RP algorithm, $A{C}_2$ is replaced with a new permanent price taken from the sum of $5 + $3 = $8. We see that there exists an egalitarian solution whenever $EFF({\theta }_1,{\theta }_2,{\theta }_3)\le 3{\theta }_1+5{\theta }_2+8{\theta }_3$. In other words, no solution will be found if $EFF({\theta }_1,{\theta }_2,{\theta }_3)>3{\theta }_1+5{\theta }_2+8{\theta }_3$. Hence, (10) is a sufficient condition rather than a necessary condition.

6. Conclusions and Open Questions

We have introduced the study of routing-proof mechanisms for network cost-sharing models in the presence of atomless agents for an arbitrary set of cost-functions. We have shown that two canonical properties in the cost-sharing literature, efficiency and stand-alone core stability, may be compatible with limit routing-proofness. In order to do so, we have introduced a new mechanisms, the egalitarian mechanism, as a natural selection when these three properties are compatible.

We find three critical open questions. The first pertaining to the study of mechanisms when agents are not atomless. Our work only provides a glimpse of the restrictions needed on the cost-functions to achieve efficiency, stand-alone core stability and a more general routing-proofness constraint where the payment allocated to agents may change depending on the mass rerouted.

The second question pertains to the demands of agents. Our work has focused on agents demanding single links between any pair of nodes. However, by extending the model into demanding multiple links should enhance the applicability of EG and related mechanisms.

Finally, our work has only shown the existence of a mechanism meeting efficiency, stand-alone core stability and limit routing-proofness, but has not provided a full characterization of a mechanism. More work is needed to develop a characterization using axioms in the spirit of limit routing-proofness.