The WALRAS Transportation Economy

A market-oriented programming approach to the distributed multicommodity flow problem.

WALRAS formulation:

Multicommodity Flow Problem

In the multicommodity flow problem, the task is to allocate a given set of cargo movements over a given transportation network so as to minimize cost. The transportation network is a collection of locations, with links (directed edges) identifying feasible transportation operations. Associated with each link is a specification of the cost of moving cargo along it, as a function of total quantity moved. We assume that the cargo is homogeneous, and that amounts of cargo are arbitrarily divisible. A movement requirement associates an amount of cargo with an origin-destination pair. A solution to the problem specifies the amount to transport on each link in order to satisfy all requirements at minimum total cost.

In the distributed version of the problem, we decentralize the decision making by allocating separate responsibility for each movement requirement.

Goods

In the WALRAS formulation of the problem, we include two types of goods.
  1. Transportation on a link (i,j), representing an amount of cargo transported from i to j. There is one of these goods for each edge in the network.
  2. Basic transportation resources. This can be interpreted as an amalgam of the factors of transportation: vehicles, fuel, labor, etc.

Agents

Shippers

 Each shipper is associated with a movement requirement of the form:
Move x units of cargo from location i to location j.

The shipper's task is to find the minimum-cost way to satisfy this requirement. A price-taking shipper would simply calculate the shortest path in the network, where costs are the current prices of the transportation goods. The actual behavior of shippers in our implementation is more complicated, however.

Shippers are endowed with basic transportation resources, and use income from this endowment (in addition to profit shares of the producers) to purchase transportation goods, according to their path analysis. Note that the shippers are nonstandard consumers in that their problem cannot be case as maximization of a utility function, strictly speaking. For that reason, the transportation economy is not really an instance of the general-equilibrium framework.

Carriers

Carriers are agents of type producer who have the capability to transport cargo units over specified links, given varying amounts of transportation resources. We associate one carrier with each available link. The production function for each carrier is simply the inverse of the cost function for that link.

In the case of a decreasing returns technology, the producer's (carrier's) optimization problem has a unique solution. The optimal level of activity maximizes revenues minus costs, which occurs at the point where the output price equals marginal cost. Using this result, carriers submit supply bids specifying transportation services as a function of link prices (with resource price fixed), and demand bids specifying required resources as a function of input prices (for activity level computed with output price fixed).

Arbitrageurs

A second class of producers, called arbitrageurs, act as specialized middlemen, monitoring isolated pieces of the network for inefficiencies. Each arbitrageur is associated with a triple of locations (i,j,k), and produces transportation from i to k by buying capacity from i to j and j to k. Its production function simply specifies that the amount of its output good, transport from i to k, is equal to the minimum of its two inputs, transport from i to j and j to k. If the price of the output exceeds the sum of prices of its inputs, then its production is profitable. Its bidding policy is to increment its level of activity at each iteration by an amount proportional to its current profitability (or decrement proportional to the loss).

To incorporate arbitrageurs into the transportation market structure, we first create new goods corresponding to the transitive closure of the transportation network. Next, we add an arbitrageur for every triple of locations (i,j,k) such that (1) i-->j is in the original network, and (2) there exists a path from j to k that does not traverse location i. These two conditions ensure that there is an arbitrageur for every pair connected by a path with more than one link, and eliminate some combinations that are either redundant or clearly unprofitable.

Results

Model S (shippers only)

Prices are set to average cost. Since average cost is below marginal cost (for a congested network), this gives shippers an incentive to overuse common links. The result is a suboptimal allocation, known as the user equilibrium. This is an example of the classic tragedy of the commons.

Model SC (shippers and carriers)

In this model, we "privatize" the network by creating a carrier agent for each link. Carriers price the transportation goods at marginal cost, which give the shippers the proper incentives. The result is a global optimum, or system equilibrium.

Model SCA (... and arbitrageurs)

By introducing arbitrageurs, we decentralize the problem further. Shippers may now purchase directly a good corresponding to their origin-destination pair, so there is no need for path analysis. No agent is concerned with more than three goods. The result is the system equilibrium. The behavior of the SCA model is isomorphic to a standard algorithm for distributed multicommodity flow originally due to Gallager (1977).

Extensions

In ongoing and future work, we are extending the transportation economy in several ways:

References

 This work was first reported in the proceedings of AAAI-92. A complete description appeared in a 1993 JAIR article:

A market-oriented programming environment and its application to distributed multicommodity flow problems. Journal of Artificial Intelligence Research, 1:1-23, 1993.

See the references in this paper for other related work.

Author: Michael Wellman (wellman@engin.umich.edu)
Last Updated: 6/7/94