|
Article Excerpt
1. Introduction
Distributed systems model today's organizations where people, information, and devices are distributed. A distributed system is characterized by decentralized decision making without complete information. For example, the resource-allocation problem in a large organization is an important case. On the one hand, actual production decisions are left to the division managers who do not know resource availabilities or overall production plans throughout the company. They minimize local costs by using local resources to run their operations. On the other hand, a central resource planner might be able to obtain complete resource availabilities for the company, but is usually unaware of the specific production plans and constraints governing the usage of resources. From the central planner's perspective, the information is incomplete and the planning is decentralized.
Distributed resource allocation is by no means restricted to one organization. The rapid development of Internet technologies has enabled the creation of virtual enterprises for sharing geographically distributed resources. Sharing distributed resources dynamically in a commercial environment requires appropriate decisions about resource usage to be made on an economic basis. In this paper, we propose a market-based, distributed, computational framework for resource sharing to support the related distributed-systems optimization problem.
From a social-welfare perspective, we can formulate the distributed organization's resource-allocation problem as a central planner's optimization problem. There are independent constraints governing local operations of each division, and there are also coupling constraints representing shared resources, such as total available manpower. The objective of the central planner is to minimize the total operating cost without having full knowledge of the operation of each individual division. Optimization problems with such structure can be solved using the method of decomposition. There are two main approaches. The first approach, known as Dantzig-Wolfe decomposition (Dantzig and Wolfe 1960), decomposes the central planner's problem into subproblems, which correspond to each division's independent parts, and a master problem, which ties together the subproblems. An alternative approach, known as Benders decomposition (Benders 1962), is essentially the same as Dantzig-Wolfe decomposition applied to the dual. Therefore, Dantzig-Wolfe decomposition is usually called the primal decomposition and Bender's decomposition a dual decomposition. In practice, the Dantzig-Wolfe decomposition uses delayed column-generation techniques (Gilmore and Gomory 1961) and Benders decomposition uses delayed constraint generation and cutting-plane methods (Kelley 1960).
An economic viewpoint of the Dantzig-Wolfe decomposition is that it is a price-directed decomposition whereas Benders decomposition is resource-directed. In the price-directed decomposition, the central planner first sets prices of shared resources. The division managers report to the central planner how they would use the shared resources according to the prices. Then the central planner reassesses the prices based on the proposals of resources usage and repeats the process until an optimal solution to the overall problem is found. In Bender's resource-directed method the central planner simply proposes a distribution of shared resources directly among divisions. The divisions report prices they would pay for this allocation. The central planner then updates the proposed distribution of resources according to the reported prices.
Although these decomposition schemes have economic interpretations, they are limited in applicability to actual decentralized organizations and distributed systems. First, a central authority (i.e., the central planner) plays a critical role in evaluating the proposals and further influencing the resource allocation. In real distributed systems, it is quite common that such authority does not exist nor, if it did, is omniscient enough to carry out this task, which raises the question of who would undertake this coordination role. In addition, the information communicated in the system requires agents to submit proposals that would normally be considered private knowledge. Agents may not have proper incentives to truthfully reveal such information in a decentralized decision-making environment. Therefore, we propose a market-based approach that can actually be played out by real distributed agents.
Market-based methods, such as auctions, could be efficiently embedded in certain properly designed decomposition schemes and are completely applicable in a distributed setting. For example, one of the earliest applications can be seen with the assignment-auction algorithms (Bertsekas 1981). Later the assignment-auction algorithm was applied to a comprehensive class of linear network flow problems (Bertsekas 1990). More recently, Fan et al. (2003) outlined a novel, decentralized framework to manage a supply chain competitive resource allocation using a double-auction market. They model the supply chain system as a linear decomposable system. Initially agents are endowed with resources for their production processes. Agents may buy or sell bundled orders in a double-auction market to seek efficient use of their resources and improve on their production. A market-matching program is used to find trades that maximize trade surplus. Fan et al. (2003) showed that this process leads to truthful behavior by the agents as the number of agents approaches infinity. Also, market trading monotonically improves the overall objective and thus makes the decentralized-system goal congruent between the overall welfare and agent goals.
Although interesting, the approach by Fan et al. has a number of limitations making it impractical to implement in real-world applications. In this paper, we build upon the model by Fan et al. to address all these unsolved issues. First, we design an algorithm to show that the process converges to the centralized problem's solution and under what conditions the convergence is finite. (The numerical example in [section]4 does not converge under their mechanism.) Second, we expand their agent's bundle-formation process to consider the cost-benefit trade-off of selling resources to other agents versus keeping them for internal use and are able to identify the best bundles that improve an agent's welfare. Third, we explore the possibility of illiquid markets. If there is no market match from the submitted bundles, the market process needs a recovery mechanism to avoid halting prematurely. Finally, we analyze strategic behavior of agents who game the system for their own benefits.
Specifically, we build on the model by Fan et al. (2003) and expand it in four general directions. First, we extend and improve the market structure. We introduce a market maker (our dealer) to facilitate market trades. We also introduce a new type of bundle selection and relax the bundle-formation process. Fan et al. use a synchronous sealed-bid double-auction call market. We do also but realizing an asynchronous, continuous market may be more realistic, because communication and information delays are unavoidable, we also provide an asynchronous form (in the online addendum provided in the e-companion). (1) Second, we remove a number of limitations found in the model by Fan et al. including illiquidity, premature stopping, no market feedback, no proof for finite convergence, etc. Much of this is illustrated in the e-companion. Third, we address strategic behavior by the agents in a more general way. They show that as the number of agents approaches infinity, truthful bidding will emerge. We look at the finite case and discover that our mechanism is robust to a common type of strategic behavior (i.e., to rational underbidding). Finally, we perform a large-scale simulation to study the computational impact on convergence and social welfare under a number of endogenous and exogenous factors.
Our market-trading idea also improves on traditional decomposition-based methods in a number of ways. First, our mechanism requires less information revelation from agents. Agents are motivated by wealth-improving trading activities while never needing to disclose their internal workings or production plans. They have the flexibility to control their resource usage such that resources can be obtained when they need them and can be traded away when they have excesses or cannot use them as effectively as others. Agents play a more active and natural role and are entitled to more decision rights regarding the resources usage than seen in traditional decomposition approaches. For example, the Dantzig-Wolfe central planner can direct agents to follow a combination of production schedules submitted throughout the process. We do not require such authority. Second, we replace the central planner with a dealer. Our dealer provides liquidity and economic transactions that improve the social welfare and mimics what is almost always found in real marketplaces. Third, certain types of strategic behavior from agents are addressed as well. Our market mechanism is specially designed to deal with information asymmetries that are more consistent with most real-world, distributed decision making problems. It could be operated in both synchronous and asynchronous market environments and actually be played-out by self-interested distributed agents. Finally, we discuss some strategies the dealer can use to improve market performance.
In [section]2, we present a general linear-programming (LP) model of a central problem and introduce our decomposition idea. We define the components of our market-based distributed solution process, namely agents, a dealer, a marketplace, a trading mechanism, and a settlement process. Section 3 discusses the main properties of our algorithm that guarantees finite convergence of our distributed approach to a central optimal solution. In [section]4 we present a numerical example showing the process of price adjustment, resource allocation, etc. In [section]5, we show our algorithm remains optimal (by adding a minor restriction on the auction rule) in the presence of agent myopic strategic behaviors. Section 6 provides a brief discussion of a set of simulation studies from the e-companion that seek to explore the role of exogenous factors (e.g., initial endowments and initial market prices) and the role of various endogenous factors including strategic behaviors that agents and the dealer may employ. Section 7 summarizes our results and lists possible future research topics. Most proofs are in the appendix.
2. The Market-Based Decomposition Algorithm
The distributed organization's optimization problem we discussed in [section]1 can be modeled as the following linear program that we refer to as the central problem:
[min.[x.sub.j][greater than or equal to]0] [[summation].sub.j=1.sup.k] [d'.sub.j][x.sub.j]
s.t. [N.sub.j][x.sub.j] [less than or equal to] [n.sub.j] j = 1,..., k (1)
[[summation].sub.j=1.sup.k] [C.sub.j][x.sub.j] [less than or equal to] c,
where [d.sub.j] is a vector of Agent j's cost, [d'.sub.j] its transpose, [x.sub.j] [member of] [R.sup.L.sub.j] are decision variables controlled by Agent j, [N.sub.j] and [C.sub.j] are matrices of appropriate dimension, [n.sub.j] is the capacity vector of Agent j's independent resources, c is a m-dimensional vector of joint capacity available in the system, and k is the number of agents. The central planner's objective is to minimize the overall operating cost of the system. The first set of constraints restricts the use of independent resources for each of the k agents. The second set of constraints indicates the coupling constraints tied to the k agents who share the m resources, reflecting the competition for resources in the distributed system.
ASSUMPTION 1. This problem has a bounded solution and is nondegenerate (either naturally so or possibly through preprocessing the problem or using some epsilon perturbation).
A central planner wants to make the best use of the resources and to allocate the resources efficiently among the k independent agents. If she can access all this information, she can directly solve this LP problem to get an optimal solution. Let [x.sub.j]*, j = 1, 2,..., k, denote an optimal solution. Let p* denote related optimal shadow prices for the shared resources. This solution provides us with...
|
