On Variants of Network Flow Stability

摘要

In a stable network flow problem, we are given a directed and capacitated network, where each vertex has strict preference over their incident edges, and need to find a flow between a source and a sink that is stable with respect to deviations along any path. A common interpretation of this problem is that the vertices represent agents and the edges represent potential contracts between the endpoint agents; a directed edge from an agent A to an agent B represents the possibility of agent B buying products via a contract from agent A. A stable flow is an equilibrium trade pattern, where no group of agents can all benefit from rerouting the flow along a path among themselves. The stable flow problem is well studied and has several applications in supply chain and trading networks. However, the Kirchhoffs law, which requires the inflow is equal to the outflow for every vertex of the network, limits the applicability of this problem. For example, in a supply chain network, one vertex can represent a manufacturing firm that takes raw materials as input and produces certain part-products while another vertex might correspond to an assembly firm whose inputs are the part-products and outputs are finished products. Clearly, the Kirchhoffs law does not hold for both manufacturing and assembly nodes in this example. In this paper, we consider a generalization of the traditional stable flow problem, in which the outflow is monotone piecewise linear to the inflow for each vertex. We first show the existence of flow stability by reducing this variant of stable flow problem to Scarf's Lemma, then introduce a path augmenting algorithm that runs in polynomial time. We first define a monotone piecewise linear mapping network (MPLM-network). A convex monotone piecewise linear mapping network (CMPLM-network) is defined as a subcategory of MPLM-networks where the slopes of the piecewise linear functions are in increasing order for every agent. A linear mapping network (LM-network) is a subcategory of CMPLM-networks where the amount of outgoing contracts of every agent with incoming contracts is a linear function on the amount of incoming contracts. A flow assignment is stable if there does not exist a blocking path in a network. A flow assignment has a blocking path P if the first agent in P prefers to offer contracts to the second agent in P to some other agents she had already offered, while intermediate agents still have space for signing contracts, and the last agent in P prefers to accept the contracts offered by the penultimate agent in P to some other agents she had already accepted. The existence of stable flow in CMPLM-networks can be proved by a reduction to Scarf's Lemma. LM-networks, as a subcategory of CMPLM-networks, always have a stable flow assignment. Every MPLM-network has a corresponding LM-network by transforming each agent into a subnetwork. Therefore, stability always exists in MPLM-networks. A constructive way to find a stable flow in acyclic LM-networks is similar to the path augmenting algorithm for the original stable flow problem. The approach is a variant of deferred acceptance algorithm among agents. The main difference is in LM-networks, flow conservation no longer holds. As a result, in each path augmenting iteration, we augment along a path from the source agent to the sink agent, or along a σ-cycle, a path from the source agent to a cycle. The running time for LM-network is O(|V||E|). For MPLM-networks, the running time of our algorithm is O(|V|(|E| + K)) where K is the total number of piecewise linear segments. For each cyclic LM-network, there exists an equivalent acyclic LM-network consists of the source vertex, the sink vertex, and three layers of vertices between the source and the sink. Hence, we can constructively find a stable flow in a cyclic LM-network by reducing this instance to its equivalent acyclic LM-network. The numbers of vertices and edges in the acyclic network are just a constant factor of that in the cyclic network. The running time is O(|V||E|) and similarly the running time for cyclic MPLM-networks, the running time is O(|V|(|E| + K)).