MARKET-BASED ADAPTIVE ARCHITECTURES FOR INFORMATION SURVIVABILITY 

Excerpts from Proposal Submitted to DARPA/ITO by: 

Michael P. Wellman,1 Jeffrey K. MacKie-Mason,2,3 and Sugih Jamin1 

1Department of Electrical Engineering and Computer Science 
2Department of Economics 
3School of Information 
University of Michigan
  1. Innovative Claims
The central claim of the proposed research is that computational market mechanisms can be designed to enhance the adaptivity, robustness, flexibility-and thus the survivability-of large-scale information systems. We propose to substantiate this claim by building a computational market system for a broad class of large-scale information systems, and demonstrating the system's adaptive response to a range of information warfare attacks. In the process, we will also address important technical issues in bidding protocols, network resource allocation, and the dynamics of survivable system behavior. 

Managing a network system is a large, complex, dynamic optimization problem. Typical network architectures and topologies (e.g., for telecom or electric transmission networks) impose severely nonlinear constraints and very high informational burdens on any attempt to globally optimize the system, especially in real time. Market price systems are a remarkably powerful, extensively studied, mechanism for solving distributed optimization problems. Within a market, agents representing modular services in the system compete to perform tasks to serve their individual objectives. This supports survivability because it rapidly directs resources to their most important uses in the face of dynamically changing needs and resource availability. Moreover, the market approach accommodates redundancy, requires minimal communication, and fundamentally decentralizes control. Recent advances in computing and telecommunications power enable us, for the first time, to seriously contemplate building large-scale, real-time computational markets to control our critical information networks and the application services layered on top of them. 

The market architecture we will implement in this project is based on the Michigan Internet AuctionBot, a configurable auction server that manages bid and pricing protocols according to specified rules. The AuctionBot model will be extended in various ways to support the demonstration of realistic survivability properties, including (1) integration with existing network protocols and service models, and (2) measures to improve the survivability of the market mechanism itself. 

To investigate the properties of this adaptive architecture, we adopt a two-level model of large-scale information systems. The network level represents the physical distribution of the information system. Network resources allocated at this level support domain-specific tasks performed at the information applications level, which generates the substantive product of the overall information system. Our simulation framework will show how relative priorities of alternate tasks drive the allocation of resources throughout the system, and will demonstrate measurable adaptiveness in the face of faults, attacks, and other dynamic factors. 

The market metaphor has often been put forth as an appropriate way to model the distributed allocation of computational resources. In this proposed project, we go beyond ad hoc application of the metaphor, to design and implement a large-scale computational market system, and analyze this system according to rigorous computational and economic standards. The product of this effort will be the first operational demonstration of a comprehensive market in network services. Our research will also yield a precise characterization of market-based architectures, algorithms and protocols for operating computational markets, and specific results about their survivability properties. Together, these elements contribute to a much-needed engineering methodology for computational market systems. 
  1. Technical Rationale
  1. Rationale for the Market-Based Approach 
The hallmark of an adaptive architecture is the ability to respond quickly, robustly, and flexibly to unforeseen faults, resource losses, or other shocks. Robustness and flexibility are often achieved through decentralization-decomposing an information system into separate modules, each capable of broad functionality and controlling its own behavior. An effective response to a shock would be for the system to reconfigure its overall activities to best use the available resources to address the most pressing needs at hand. Solving such a reconfiguration problem is a challenge, especially in a decentralized environment where status information is local, communication is costly, and authority is itself distributed. 

We propose an in-depth investigation of adaptive architectures based on computational markets. The fundamental operational problem for complex, large-scale information systems is the efficient allocation of scarce resources to alternative uses, in order to fulfill system goals (e.g., user satisfaction, effective decision support, profit maximization, robustness to disruption). This requires: the values that alternative uses put on utilizing various resources; the costs of utilizing the resources; a mechanism for gathering and processing the cost and value information in order to allocate the resources to their best uses. 

Markets are the most well-studied of decentralized resource-allocation mechanisms, and since actual information systems are embedded within the real-world market economy, constitute a "standard interface" to the external environment. In a computational market, allocation of resources to activities is dictated by a price system, where modules exchange control of resources according to market-derived prices. Each module, or agent, is defined by the activities to which it can devote resources, and the values or other products it can realize from those activities. The market prices signal relative resource scarcity. Indeed, the price vector in a competitive equilibrium is precisely equal to the vector of shadow values from the optimization of the system's objective function. When agents respond rationally to the price signals, then all resources are allocated efficiently, to their highest value uses. 

This intuition is rendered precise by the well-known welfare theorems of economic theory (see Section III.C.1.3): under appropriate conditions, a market equilibrium is efficient (does not waste resources), and any efficient allocation can be implemented as a market equilibrium. To exploit this remarkable property of competitive markets for survivable information systems, we must engineer the system so that the "appropriate conditions" are approximately in force. This requires careful design of the market structure (i.e., what goods and services are exchanged), as well as the computational infrastructure for deriving and communicating price information. 

The effectiveness of the market-based approach hinges on the market's ability to disseminate rapidly-through changed prices-changes in the scarcity value of remaining resources. Rational agents respond to price changes by redeploying resources. Because this process minimizes communication and avoids global control or synchronization, it is a plausible mechanism for adaptation. 
    1. The Two-Level Model of Networked Information Systems 
To evaluate and demonstrate the effectiveness of market-based adaptive architectures for information survivability, we will construct and analyze a two-level market model of a large-scale networked information system. Each level is described by the resources of primary interest, the agents controlling and using these resources, and the mechanisms used to allocate them. At the network level, we are concerned primarily with communications resources: routers, switches, and transmission links that enable transmission of data among entities in the network, according to the specific network technology. The data transmission is an essential ingredient for the activities at the information applications level, which represents the actual functions or services comprising the information system (for example, command and control, financial services, information gathering and dissemination). At each level, the agents' capabilities are described by their technologies for producing particular kinds of valued resources out of other (more basic) resources. 

Figure 1: Two-level model of a networked information system. 

Our aim with this model is to be generic enough to accommodate the broad range of large-scale information systems that need to be survivable, while providing enough specificity to analyze realistic attack models and resource issues. For example, we would expect to be able to capture JTF ATD Comm Server within this framework, and other related systems. Having an explicit network layer allows us to consider the decentralization of the system both physically and logically, while the service layer allows us to model the consequences of alternate resource allocations for actual tasks. Most importantly, by considering both information applications and delivery, we can derive the value of computational and communication resources from the values of the activities they support, thus providing a principled basis for dynamic configuration decisions in fault or attack situations. 
    1. Computational Market Infrastructure 
The key architectural component of a computational market system is the protocol for establishing prices. The most generic price-determination mechanism is an auction, which is any set of fixed rules for calculating prices and allocations as a function of messages, or bids. The market mechanisms we will implement for this project will build on our existing "AuctionBot"-a configurable auction service for running user-specified auctions over an internet. The current AuctionBot is designed for robustness, scalability, and unique flexibility in the range of auction types it can implement. To extend AuctionBot to serve computational market systems, we will develop an application programming interface (API) to go along with the existing human user interface. 

At the applications level, it makes sense to define our negotiation (i.e., auction) protocols on top of existing network protocols. For allocating the network resources themselves, it may be necessary to integrate negotiation or bidding into the basic protocols themselves. In this project, we will investigate the possibility of introducing price negotiation to the proposed Internet standard Resource Reservation Protocol (RSVP), and of designing pricing protocols at other layers of the network protocol stack. 
    1. Survivability 
Attacks on a networked information system can be expressed in several ways in our model. First, agents performing particular functions can be destroyed or corrupted. A particularly important type of corruption is when they develop malicious intent to subvert the purposes of other agents or the system as a whole. (This possibility emphasizes the value of designing the system based on autonomous agents, rather than assuming that modules behave as dictated by a central system planner.) Second, performance of the system can be disturbed by destruction of resources, or degradation of particular agents' technologies. In the market-based architecture, the system responds to resource destruction or capability degradation by dynamically adjusting prices to compensate for the resulting imbalances. Through a distributed bidding protocol, the system reconfigures its assignment of resources to the most-valued activities, eventually (if the shock dissipates) finding a new equilibrium allocation. Note that the system continues to operate, albeit at suboptimal levels, throughout the adjustment process. 

The degradations, destructions, or corruptions encountered inevitably reduce the system's overall performance (if not, then the system was failing to operate at peak levels in the first place). An adaptive architecture achieves its aim if it ameliorates the performance drop by (1) disseminating signals about the ramifications of the shock efficiently, (2) dynamically reallocating whatever resources are left to their most important activities, and (3) limiting the damage that can be caused by individual malicious modules. We expect the price system to be an effective mechanism for accomplishing the first two of these, and address the third through the basic accountability for resources inherent to a market architecture. That is, the market provides disincentives to manipulation, since to influence any activity an agent must expend resources, and thus the power of any module is limited. 
    1. Survivability of the Market Infrastructure 
Design of market-based architectures, however, must also be cognizant of the likelihood of modules attempting to circumvent the basic rules of the mechanism, thus defeating their adaptation and survivability. Faced with fraudulent or otherwise subversive agents, our challenge is to design into the overall market framework a set of institutions, rules, and policies that are robust to deviant behavior. As noted above, some of the natural features of markets-decentralization and resource-accountability-are helpful, but complementary mechanisms, as might be provided by a "public health infrastructure" will also be important. For example, when public health authorities detect subversive agents, we can confiscate or destroy their resources, and proceed with the market allocation from there. 

We will exploit public health and standard security measures when appropriate to "harden" the institutions implementing resource-allocation mechanisms. But recognizing that these will not be perfect, we adopt a highly decentralized and redundant architecture to manage the dynamic allocation process. Specifically, the market service is implemented by virtual auction servers. The basic idea is that resident on the network is a pool of identical, generic, configurable auction servers, any of them capable of providing the allocation service for any resource. Thus, the only entity that must survive is the set of protocols-no single physical auction server is mission-critical. Whenever an agent is interested in exchanging a resource for which no established market exists, it spawns an auction process to manage the negotiation. 

Enforcement of exchanges must also be designed for survivability. For example, exclusive reliance on a central accounting system would create significant vulnerability. Our design will distribute and replicate enforcement functions wherever possible. We will also accommodate in-band direct validation and exchange schemes (cf. toll booths on highways) rather than out-of-band record keeping and settlements. 
    1. Simulation 
Our evaluation and analysis will be supported by simulations of the two-level network model. Our model of the network level will be detailed and (structurally) realistic, based on our existing Internet simulation models and software. Our model of the service level will be abstract and realistic, building on our experience of constructing commerce models of digital library services (but omitting the domain-specific details). 

Our models of attacks will draw on existing models from the fault-tolerance literature, where appropriate, and will cover attacks ranging in scope, extent, and systematicity. Our empirical analysis will include a small number of in-depth attack scenarios, as well as a larger number of randomly generated situations varying across parametric ranges. We will also analyze the performance of the system in the presence of a variety of deviant agent behaviors. The selection and formulation of these deviations will be informed by the economics literature on asymmetric information, and the law and economics literature. 
    1. Research Issues in Market Design 
Development of the computational market will entail research contributions in protocol design and network modeling, some of which were mentioned above. In addition, the project infrastructure will also enable research on several economic issues in the design of market mechanisms to achieve desired survivability aims. Generally speaking, we will study the relationship of alternate market configurations and mechanisms to overall performance, and undertake welfare analysis of the relative outcomes for particular agents. A representative research question is how, in a closed system, to distribute resources initially to obtain a good balance of activities and ensure robust attack response. A more specific outline of some of the research issues we will address is presented in Section III.C.5. 
  1. Detailed Technical Rationale
We propose to investigate one broad approach to information system survivability-market-based adaptive architectures-in unprecedented depth. The approach applies to distributed decision-support environments, in which (1) system performance is measured by how well the information services contribute to decision quality, and (2) the information system is fundamentally distributed. Distribution may be a consequence of factors such as geographic dispersion of participants, inherent decentralization of authority, costly or risky communication, modular problem decomposition, and intentional redundancy or distribution to promote fault tolerance. 

We characterize a decision-support environment in terms of resources, agents, and allocation mechanisms. Resources include physical materials (RAM, wires, printers, airplanes), services (computation, lookup, scheduling) and other, more abstract ingredients of activity (time, space, attention, expertise). Agents are the fundamental decision-making entities in the system. They can be human or artificial: any system component that selects among requests for its service-or among providers of a needed service-makes decisions. An allocation mechanism assigns resources to agents. Mechanisms realized in our architecture exploit distributed decision-making as the key to robustness and survivability. 
    1. Market-Based Adaptive Systems 
Without loss of generality, every decision is really about resource allocation: choosing to employ a limited resource for one purpose in lieu of others. There are at least three reasons for taking this resource-oriented perspective for information survivability. First, an attack threatens system resources, and performance under attack depends on the delivery of information resources to users. Second, describing what agents do by the resources they require and generate highlights tradeoffs among alternate activities. Third, characterizing multiagent interactions in terms of resources transferred provides structure by simplifying the interfaces among agents. 

Agents use their allocation of resources to achieve their goals in two ways: they consume some resources, and they use others to produce new resources which they then either consume or exchange for mutual advantage with other agents. The state of the entire system can be summarized by the set of agents, the resources each has to devote to its activities, and (in dynamic systems) their commitments to engage in future resource exchanges. We call this summary an allocation. Transitions between states are fully characterized by resource transformations and exchanges, and changes in future commitments. 

The method by which a state transition to a new allocation is determined for a multiagent system is called a mechanism. We shall study mechanisms in which agents engage in a protocol to submit messages to the institutions implementing the mechanism. The mechanism announces the resulting allocation as a function of the messages. 

Agents externally participate in the allocation mechanism to determine their available resources. They internally apply these resources as they see fit. If the division is complete, then we have broken off a significant part of the problem-individual agents applying resources-that does not require interaction. However, separability requires that once we specify the allocation, what any agent does with its resources does not affect the activities of other agents. In economic terminology, this is to say that there are no externalities. 

There are a variety of mechanisms for solving resource allocation problems, including such well-known examples as first-come-first-served with queuing, and allocation by fiat. The defining feature of a market-based mechanism is that the allocation is defined by a set of prices with the following property: every agent may exchange as much of any resource as it desires at the going price for that resource. The price specifies the exchange terms: if resource j is assigned price pj, then one unit of resource 3 may be exchanged for p3/p7 units of resource 7. A market-based mechanism has numerous advantages, including these two: 
In the resource-oriented perspective, decisions are about what resources to devote to which activities. Economics develops the theory of rational choice by agents. The prototypical agent in an economic allocation system seeks to maximize a well-defined objective function subject to constraints on valuable resources (the budget) and on the ability to transform resources into outcomes that affect the objective function (institutional and technological constraints). The objective function may be generally called a utility function; it is any function derivable from an agent's transitive and complete preference ordering. 

One major agent type is the consumer, who obtains utility by final consumption of resources (obtained from endowments, or by exchange with other agents). The human users of our networked information system are viewed as consumers; their valuations of information service outcomes ground the ultimate measure of system performance (in ordinary times and after a disruption). The second major agent type is the producer (whose utility function takes the form of profits), who transforms inputs resources (e.g., data, time, CPU) into outputs, and who obtains utility from the exchange of these outputs for other resources (often, currency). 

A key feature of an agent-based market mechanism (when externalities are absent) is that each agent makes decisions locally, based only on its personal knowledge base and the prices announced by the mechanism. That is, each agent optimizes its objective, subject to its own preferences, its own technological capabilities, its own endowments, and the market prices. Thus, competitive market mechanisms are maximally modular, relying entirely on autonomous local decision-making. Optimal choices require no knowledge of the preferences, technology, endowments or activities-or even the existence-of other agents, which is a valuable property for survivability. 
We define an allocation problem generally as that of constructing a mechanism satisfying various desiderata (involving both outcomes and computation) while obeying feasibility constraints. The most standard criterion for allocations is Pareto efficiency. An allocation a is Pareto efficient if and only if there does not exist a feasible allocation a¢ such that a¢ is strictly preferred by one agent, and at least as preferred by all the rest. 

The results of a market system depend, of course, on the behavior of the agents. The most well-studied case is that of perfect competition, where each agent takes prices as given, ignoring any power it may have to influence them through strategic bidding. The case also assumes that agents care only about their own allocations (i.e., that there are no externalities). A feasible allocation corresponding to the situation where agents maximize utility or profit subject to a given set of prices is called a competitive equilibrium. 

The case for market mechanisms is bolstered in a precise way by the two fundamental welfare theorems of economics. The first states that all competitive equilibria are Pareto efficient. This means that the result of a competitive market allocation process does not waste resources, in the sense of putting them to uses that would be dominated by some other allocation. The second welfare theorem states that for a wide class of agent preferences and technologies (essentially requiring mathematical convexity and again, the absence of externalities), a competitive market-based allocation can be designed to implement any Pareto efficient allocation. 

Competitive equilibrium prices are precisely equal to the shadow values (Lagrange multipliers) from the optimization of the overall system objective function. The price signal that agents receive correctly conveys the relative scarcity value of each resource from the viewpoint of the overall system. If a resource (e.g., a network switch) is degraded or eliminated, then generally all of the shadow values change, but the price dynamics result in direct calculation of the new shadow values for the perturbed system. In consequence, there is generally no loss-of-service disaster scenario that totally disables the system; whatever resources remain will be allocated efficiently to accomplish the best overall performance possible given the post-disaster state. 
Consider a large-scale distributed military command-and-control information system. Commanders are consumer agents, obtaining value from the information provided by the system. Modules that collect, process, and deliver this information are producer agents. For example, sensors produce reports from sensor resources (e.g., sonar detectors). Typically sensor reports require further processing, for example, object recognition. Yet further producers might filter; request further sensing; or perform other tasks. 

Figure 2: Flow of resources in a simplified command-and-control economy. 

Military assets and basic resources are "owned" by the commanders, who supply them to the productive sector in exchange for the finished products of interest. The system is physically as well as functionally distributed-resources available at one location can be made available at another through various network services, offered by agents in a communication network. 

The problem faced by the overall system is to deploy the entire body of available resources to the various sensing, processing, and communications activities so as to maximize the value of the resulting information to the commanders. However, the specific assignments of resources to activities are determined by individual agents, based on local information. Signals of the relative value of alternate uses propagate to the intermediate agents through the price system, which in equilibrium establishes an efficient overall allocation.  Our model of a networked information system distinguishes two levels of service: network, and information application. We separate the levels to take advantage of concepts specifically applicable to the sorts of activities at the respective levels. Although they are conceptually distinct, the two levels are fundamentally linked: information applications require network services to produce their services (and possibly vice versa). Therefore, response to an attack should not be determined separately for network and applications resources. For example: a seemingly sensible response to a downed link such as "reroute traffic to minimize the number of lost packets" is not sensible if it results in delay or loss of some critically important information. When not all services and qualities can be immediately restored the choice of which to offer, and to which application stream, should depend on the relative value of the services to the different application streams at the time of the attack, which necessitates modeling both the network and application services. 
The network level provides delivery services to the application level. Resources at the network level include link bandwidth, buffer space, processing power, memory, and disk space of intermediate nodes. To meet their quality of service requirements, applications negotiate to reserve network resources. Resource reservations may be specified in three dimensions: (1) type and amount of resources required, (2) time between reservation and use of resources, and (3) strictness of the reservation guarantee. 

The quantity of resources reserved determines the worst-case quality-speed and fidelity-of delivery. service assumes traffic can derive utility from the smallest unit of resources that can be made available to it. Such applications, for instance e-mail, may not need to reserve resources. Other applications, such as real-time video conferencing, may have bounded delivery time requirements and thus not be able to derive utility from the network if available resources drop below a certain level. Such applications prefer to reserve resources to ensure usable quality. Other applications such as data fusion for scientific visualization and distributed battlefield simulation may wish to inject data manipulation methods into network nodes. These additionally prefer to reserve processing, memory and disk at intermediate nodes to execute the injected methods. Our market-based approach allows applications to express the intensity of their valuation for resources through bidding. 

We identify three types of reservations based on the time between reservation and use of resources: (1) advance, (2) immediate, and (3) in situ. Traffic streams whose arrival and duration can be determined a priori can bid on network resources in advance. If the arrival and duration of all streams are predetermined, an optimal resource allocation scheme can be precomputed. Other traffic streams may prefer on-demand delivery. Our market-based architecture allows such streams to outbid, and hence preempt, existing streams. Service disruptions and new traffic introduced in response to an information warfare attack may cause existing traffic streams to be rerouted. During disruptions, delivery constraints on packets already in the network may be met by allowing packets to bid for resources and preempt other packets in situ. For each of the three types of reservations we associate a separate resource reservation negotiation protocol. 

The third dimension distinguishing reservations is the strictness of their contractual bounds. Some applications prefer a contractually binding reservation, while others can tolerate occasional degradation in service. Tolerant applications allow the network to increase utilization by taking advantage of statistical multiplexing and oversubscribing resources. A market-based approach to resource allocation allows the network to offer different grades of service at different prices. A more detailed description of our negotiation mechanisms is provided in Section III.D.3. 
Information applications provide information content services to users, as distinguished from the delivery services provided by the network layer. Resources produced at the applications level represent processing, interpretation, selection, or other value-added transformation applied to other resources as provided by other applications, by the network layer, or externally to the system. In general, each application available from the network system will be identified with an agent. Application-level agents decide which resources they need and how to deploy them to provide their application service. The resources for an application are capabilities provided by other agents, characterized by properties: <capability: property1, property2, Ö>. See Section III.D.1. An example network resource that might be required by an information application is <packet delivery: origin=A, destination=B, minimum_bandwidth=64Kbps, maximum_packet_loss=0>. 

Consider two example applications, and some resources they might require:  The web of interdependencies between application and network services makes users vulnerable to loss of service when network disruptions occur. Disadvantaged users may be situated in different locations, in different organizations, using different applications. The market-based approach to survivability is well-suited to coordinate responses across the many different applications and users that rely on the disrupted service.  Consider the effects of an attack on the provision of a crucial object recognition service that can be delivered by two or more supercomputer sites (see section III.C.1.4). Commanders require the service directly and indirectly (through situation assessment services). To perform its service, the recognition agent needs both network and application resources: packet-delivery network service, image data from sensor agents, and authorization and authentication services. Suppose an attack disables one supercomputer provider of recognition services, various network links, and some security servers. What might the operational consequences be?  And how might a market-based allocation system respond to these problems?  The example illustrates how a market-based allocation service enhances survivability: the remaining resources are dynamically reconfigured to those activities that most value them, so that the diminished system provides a set of surviving services that are best from the viewpoint of the commanders. This reconfiguration is engineered by the passing of messages that each surviving agent calculates locally (and thus rapidly and without reliance on possibly disrupted remote services) reflecting its ability to provide resources, and the intensity of its need to obtain resources, given the agent's conditions following the disaster. 
    1. Computational Market Infrastructure 
At the heart of the market-based approach is exchange of resources through a price system, also known as commerce. Any commerce system, computational or otherwise, must support the three fundamental steps of a commercial transaction:  Our infrastructural focus in this project is on the Negotiate step-protocols by which distributed computational agents determine effective allocations of resources. Negotiating agents submit offers to buy or sell resources at various prices, and the allocation mechanism determines the prices and quantities and disseminates information necessary to execute the transaction. We discuss our negotiation approach in Section III.D.2. 
    1. Research Issues in Market Design 
Prior computational market systems have been relatively basic. We aim to develop some general principles for the field by pursuing several fundamental issues. 

Intertemporal resource allocation. For many activities, planning is important. For example, users want to start a video conference with some degree of assurance that network resources will be available to complete it. Thus (futures) markets for reserving resources at particular times may be valuable. However, maintaining markets for all resources at all future times is infeasible. We will investigate the role of transaction costs in determining the optimal market configuration: how many time periods, how many distinguished goods, how many independent and overlapping market regions? 

Risk allocation. Uncertainty is fundamental to attack situations, and therefore instruments for hedging against contingencies or sharing risks is important. We will introduce market-based risk management mechanisms (e.g., insurance and securities) into the system, and evaluate their effectiveness. (Futures markets, mentioned above, are a special case.) 

Strategic behavior. Market efficiency, in a standard mechanism, follows when agents behave competitively, but this cannot be assured for agents who have complete or significant control over particular resources. Such agents advance their individual goals, sometimes at the expense of overall goals, by acting strategically. This situation generalizes to include "foreign" agents infiltrated into the system to compromise system performance. We will examine the implications of noncompetitive behavior, and architectural factors that might induce agents to act "as if" competitive despite their actual market power, or that otherwise limit their negative impact. 

Externalities. Efficiency is best assured when there are no externalities: one agent's allocation does not directly affect another's well-being. In some cases, physical laws create externalities; in other cases, they arise from incompleteness in the specification of property rights and the number of markets. We will extend our prior work (see Section III.E) to consider externalities in our model information system. 

"War profiteering". Information warfare shocks can create temporary windfall opportunities for well-placed agents. For example, destruction of competing services can render one service provider dangerously critical for overall performance, and thereby enormously powerful. What can we do to limit windfall profits, without inordinately compromising other desirable properties of the mechanism? 

Nonrival resources. Thus far we have considered rival resources, which means that the same resource cannot be allocated to more than one agent. Many resources, especially in information systems, can be multiply and simultaneously used without diminishment. For these nonrival resources, the material balance constraint is inappropriate, and efficient allocation requires modification to the mechanism. 
  1. Detailed Technical Approach
    1. Market-Based Allocation Service Architecture 
The core object of our proposed work is a market-based allocation service architecture covering a broad class of networked information systems. The components are the interface between the agents providing the content and delivery services of the information system, and the modules controlling the distribution of resources necessary to accomplish this business. The architecture is designed to be uniform-central constructs are meaningful to both network and information application services-flexible, robust, and encapsulated. Hence, it can be adapted to a wide variety of information systems regardless of the specific architectures of the network and applications. 

The implementation details of the allocation service will be transparent to network and information application requesters; these agents need only know how to communicate with the allocation subsystem, and how to undertake the resulting exchanges. Consequently, changes in the allocation mechanism do not entail re-engineering the entire networked information system. Functionality can be introduced, and later revised, incrementally. 

To implement such an architecture, it is necessary to define what will be recognized as agents and resources, as discussed in Section III.C.1 above. Other required components of the architecture include: a negotiation protocol for agents to exchange messages with the allocation service, an allocation mechanism which maps messages into allocations, a currency (unit of exchange), banking and security services, and enforcement services. 

Agents. Agents are the fundamental human or software decision-making entities. There must be an agent to represent every choice in the system involving alternate deployments of resources, including both end uses and intermediate processing. For example, agents would represent particular network switches and links, and particular applications such as databases, sensor fusion, email, and safety alerts. Agents are authorized to communicate offers to exchange currency for resources, and to execute such exchanges. 

Institutional and organizational relationships will determine many implementation details. In a closed system, designers have complete control over which agents exist, how they are related, and what strategies they employ. The price system serves solely for internal planning and coordination. In an open system, agents may correspond to real-world autonomous entities with no common authority. Parties other than the designers specify the agents' strategies. Our architecture will support both closed and open computational market systems. 

Generalized Resources. A generalized resource is a capability and associated characteristics, or properties. It can be expressed as <capability: property1, property2, Ö>. Each implementation of the allocation architecture must specify the resource capabilities and properties it recognizes, as part of the negotiation protocol. For example, network level capabilities might include "packet delivery" or "virtual circuit reservation". Properties might include "maximum packet size", "bandwidth", and whether service is "guaranteed" or "predictive". Other properties might include "time of service" (e.g., immediately, no later than x), "quantity", "data delivery tree", and various quality characteristics. 

One crucial property is the time that a resource is available. Today's newspaper is different than next week's, and today's newspaper available today is different than today's available next week. Of course, next week's newspaper available today would be the most useful of all! To represent this variety, strictly speaking, we would need separate resources for each combination ·t1,t2Ò of the newspaper dated t1 available at t2. Restricting attention to t1 2 t2 eliminates only half the cases. A reasonable approximation might be to treat all instances t1 < t2 identically as "old news", thus reducing the required goods to a number linear in the time periods. A more extreme simplification, commonly used, would be to consider only a single time period (i.e., now, usually implicit), and address allocation of future resources when their times come. Intermediate approaches, perhaps the most common, may consider some particularly important future resources, neglecting the rest. 

Whatever properties are included in the description (and on what scales), the specification must be a sufficient description of the resources for all of the agents. As the above examples suggest, this could in general lead to an enormous set of resources. For this architecture to be useful, it must be the case that some potentially distinguishable items be treated as practically indistinguishable, that is, as instances of the same resource. In any allocation scheme, there is an inherent tradeoff between aggregation and fidelity. One advantage of an economically-grounded approach to the problem is that the negotiation over values provides internally consistent guidance on how finely distinguished the resource definitions should be. In the real-world economy, it is possible to sell each slice of bread as a different good, but it is not economically supportable to do so. (Note that we do not need a central planner to decide this by fiat.) The advisability of increasing or decreasing disaggregation can be tested by measuring the change in overall system net surplus (utility). 

Technology and usage changes over time might require revised resource specifications. For maximum flexibility, we incorporate mechanisms for dynamically introducing generalized resources or modifying descriptions of existing ones, using a generic description language based on structured combinations of basic primitives. 

Negotiation protocol. Agents engage in negotiation by announcing their intensities of preference for the delivery and receipt of resources, typically in the form of offers to buy or sell resources at various prices. The allocation mechanism determines and reveals the resulting allocation, and may also respond to requests for information about past, present and future allocation commitments (e.g., quantities and prices for allocated resources), which may be useful for planning. 

Allocation mechanism. A mechanism is a mapping from the space of negotiation messages to allocations. For a particular negotiation episode, the mechanism specifies a partial assignment of generalized resources to agents, covering the resources involved in the negotiation. The allocation returned is partial, as agents participate in multiple overlapping negotiations, simultaneously and across time. To be admissible, a mechanism must produce allocations that are feasible with respect to various technological and institutional constraints. For example, the total allocated usage of a resource (say, queries on a database) must not exceed the total capability of that resource during the specified time period. 

Other architectural components. The allocation architecture requires several other features to ensure feasibility and robustness. Our architecture will accommodate all of these features, although our implementation may address some of their underlying issues in greater depth than others. 
      1. Computational Market Infrastructure 
An implementation of the allocation service architecture requires infrastructure supporting a negotiation protocol, allocation mechanism, and enforcement of allocations. We realize the first two functions via auctions, and the third through exchange protocols. We also consider special-purpose infrastructure supporting commerce at the network level through direct embedding in the network protocols. 
As described above, a resource allocation mechanism is any precise set of rules for determining allocations based on a negotiation protocol. An auction is an institution implementing price-based mechanisms. Although auctions we encounter in daily life tend to adhere to stereotypical forms-public auctions of fine art (typically an "English public outcry" auction), government auctions of oil leases (a "first-price sealed-bid" auction), etc.-the generic auction concept is remarkably flexible. Alternate auction schemes can implement a wide range of mechanisms, differing on allocation rules, bid languages, timing, result revelation, intermediate status revelation, and several other dimensions. The resulting allocations may vary in predictable ways based on these features, for example one auction design may favor a seller more than another, or may offer efficiency guarantees. Similarly, auctions run according to different rules may vary on privacy preservation, timeliness, computational cost, or incentives to bidders to represent their interests truthfully. As part of this project we will construct a comprehensive map of the auction design space, with guidelines for auction specification to prospective market designers. 

Design of a computational market infrastructure is thus tantamount to design of auction mechanisms. Because no single mechanism is always ideal, we advocate a configurable design, and have developed a general auction management tool, currently providing auction service over the Internet. The Michigan Internet AuctionBot is a configurable auction server, available to anyone over the world-wide web. AuctionBot users can submit bids to existing auctions, or set up their own auctions by filling in some simple web forms. By answering a series of questions, auction creators can specify choices along all of the auction design dimensions mentioned above. 

This flexibility is a core principle of the AuctionBot architecture. Bidders submit offers to buy or sell auctioned goods via a uniform web interface, which customizes bid formats based on stored auction parameters. Auction clears, both real and hypothetical, are triggered by a scheduler, which runs asynchronously from the interface and ensures that events happen in their proper order (i.e., an auction scheduled to clear at a fixed time uses the versions of the bids that were active at that time, even if the auction process is backlogged). The auction kernel calculates the actual allocations, based on active bids and prevailing rules for a given auction, and disseminates results via e-mail to the cognizant users. The basic organization of the AuctionBot Internet service is depicted in Figure 3. 

Figure 3: Components of the Michigan Internet AuctionBot. 

The negotiation protocol and allocation mechanisms we develop for this project will follow the basic principle of mechanism configurability. Our allocation service provides virtual auction servers-conceptually separate auction processes for the various resources. The abstract interface to these servers will be consistent with the AuctionBot, and thus we can employ replicas of the Internet service in test demonstrations of the architecture. 

To implement the allocation service, we will develop a software interface (API) with functionality similar to the existing human user interface. This API will consist of a library of routines for submitting and revising bids, retrieving price quote and other status information, and the remaining AuctionBot functions. We also intend to extend this library with higher-level constructs for specifying general bidding strategies, which would then be implemented through lower-level AuctionBot operations. This AuctionBot agentware is currently under preliminary design, and will be a major product of the proposed project. 
An exchange protocol governs the actual transactions in the system: execution of negotiated deals. The extent to which such transactions can be handled by the system depends on the deals and resources involved Specific forms of transactions-payment of standard currency-have received much research and commercial attention, and several workable schemes have been developed. Cryptographic enforcement can be extended to exchanges involving digital information goods, for example as demonstrated by the NetBill payment protocol. We can further adapt this approach to cover a broad category of computational services, by exchanging certificates entitling bearers to the designated generalized resource. 

Our architecture will accommodate special-purpose exchange protocols, but we will not devote much effort to designing them ourselves. We will make an exception for network resources, enforcing negotiated terms whenever possible within the network protocols. 
      1. Network Resource Reservation Architecture 
Our research reservation architecture supports allocation of network resources through negotiated reservations, and enforcement of reservations through network scheduling policies. In keeping with our overall approach, the architecture accommodates multiple negotiation protocols and allocation mechanisms, as well as multiple enforcement regimes. Enforcement includes authentication, which may sometimes be required on a packet basis, and more generally, any measures to ensure that agents receive the resources to which they are entitled. Toward this end, we will exploit research on scheduling disciplines that can enforce such properties. Figure 4 depicts the building blocks of our architecture. 

Figure 4: Building blocks of our network resource reservation architecture. 

For negotiation of network reservations in advance, our auction servers should provide reasonable service. However, the overhead of additional communication rounds may not be acceptable for immediate or in situ resource reservation. In the subsections below, we discuss mechanisms to allocate resources at time scales too short for advance reservation. 
        • Allocation Mechanism 
The allocation mechanism plays the dual role of accounting for available resources and executing auctions. The role of accounting for available resources has traditionally been known in the networking community as admission control. When a traffic stream attempts to reserve some resources, the admission control algorithm decides whether available capacity is sufficient to satisfy the requested amount. Applications that require strict QoS guarantees from the network specify their worst-case resource requirements, which the network must satisfy at all times once their traffic streams have been admitted. If such applications transmit at a variable bit rate, network utilization ultimately suffers. Applications that can tolerate occasional degradation in service allow the admission controller to measure actual resource usage of admitted streams, and resell unused bandwidth. The statistical nature measurement-based control and the inherently unpredictable nature of network traffic precludes such algorithms from offering absolute service guarantees. By offering different grades of service and pricing them appropriately, the network can increase overall utilization and global value. 

Accommodating unanticipated increases in load may necessitate the network to renege on its service commitments to previously admitted traffic streams. Our market-based allocation mechanism allows agents to accept compensation in exchange for reclamation of resources previously allocated to them. Agents may indicate their willingness to relinquish their resources at times of scarcity either by purchasing a preemptible service-at a lower price than non-preemptible services, or by participating in such exchanges as the needs arise. 

To complete a delivery, resources along the path from the source to the destination (where the destination is a nonempty set of network end-systems) must be reserved. A scalable architecture dictates that network resource allocation must be conducted in a distributed fashion, where each intermediate node makes local allocation decisions based on local information. On the other hand, a distributed allocation process that does not attempt to coordinate local allocations could run aground in a global deadlock scenarios in which different applications manage to acquire only partial resources and no application can make further progress. We plan to devise a market-based solution to this problem in which traffic streams traversing large number of hops will know to increase their bids accordingly. 
To ensure scalability and interoperability in a heterogeneous environment, we use soft-states to maintain reservation information and let receivers drive the reservations. Bids for resources periodically propagate from one or more receivers towards the sender. At each router, bids from all receivers for the same traffic stream are collected and either the sum or maximum of all the bids is forwarded to the next router towards the sender. Hence each bid contains the maximum price all receivers downstream are willing to pay for the use of a resource. As receivers join or leave the delivery tree, the maximum bid is automatically adjusted. Note that the price for resource usage may actually be lower than the maximum submitted bid. The M+1st-price mechanism, for example, ensures that each packet is charged the minimum locally efficient amount at each node. This negotiation protocol can be easily implemented as an extension to the Resource ReSerVation Protocol (RSVP) the Internet Engineering Task Force (IETF) is currently working on. A prototypical extension to the RSVP object type to carry bid information is shown in Figure 5. 

Figure 5: Extended IPv6 header carrying reservation and bid description. 

As argued above, when a disrupted traffic stream is rerouted, delivery constraints on packets already in the network can be met only if each packet can bid for resources in situ. To facilitate per-packet bidding, each packet can carry the maximum price its receivers are willing to pay. Recall that at each router our resource negotiation protocol merges the bids from all downstream receivers. By requiring each router to keep this information as part of the connection state, the router immediately adjacent to the disrupted site can stamp each outgoing packet with the maximum bid its receivers downstream are willing to pay. For per-packet bidding, the router must also prepend the service requirement description of the traffic stream to the packet. Figure 5 shows an IPv6 packet header, extended to carry service requirement description and bid information. Applications that can tolerate momentary degradation of service may choose not to engage in per-packet bidding, relying instead on the periodic reservation messages to set up new reservations along a new route. 
  1. Comparison with other ongoing research 
The proposed project builds on, complements, or can be contrasted with ongoing research in several other areas. We cite some of the most salient work in several related categories. 

Computational Markets. The market metaphor for allocation of computational resources has surfaced several times over the years (Sutherland 1968). Adam Smith's "invisible hand" is perhaps the oldest and best understood of so-called "emergent phenomena", and so it is not surprising that many find it appealing for decentralization problems in computing (Miller and Drexler 1988) (cf. (Wellman 1991)). Market-like negotiation is a driving concept in the Enterprise scheduler (Malone et al. 1988), and in the Contract Net protocol (Davis and Smith 1983), which received widespread attention in Distributed AI research. Recently, some researchers have pursued the market approach in depth, for a range of applications (Clearwater 1996; Gagliano et al. 1995; Stonebraker et al. 1994; Waldspurger et al. 1992; Ygge and Akkermans 1996). 

Our work is distinguished by two main features: (1) We address the simultaneous allocation of multiple resource types. Most work on computational markets has focused on a single resource, which limits its applicability and does not exploit many of the advantages of a price system. (2) Many of the extant systems are "market-like", appealing to the market metaphor but not directly corresponding to an economic system. Our methods adhere closest to standard economic theory, resulting in systems that better achieve the performance benefits of a market, and are amenable to analysis using available techniques. 

Game-theoretic methods generally have also received much recent attention in AI research (Boutilier et al. forthcoming; Rosenschein and Zlotkin 1994). From the perspective of game theory, markets represent a special class of mechanisms-one with particular computational advantages, as we have argued. 

Network Resource Allocation. Work on network resource allocation has traditionally concentrated on the following areas: (1) scheduling disciplines to enforce resource reservations (Bennett and Zhang 1996; Demers et al. 1989; Goyal et al. 1996; Goyal et al. 1996; Parekh and Gallager 1993), (2) strictness of resource guarantees (Baker et al. 1996; Clark, Shenker et al. 1992; Ferrari and Verma 1990; Wroclawski 1995), (3) computation of resource requirements and admission control (de Veciana et al. 1995; Elwalid et al. 1995; Gibbens et al. 1995; Guérin et al. 1991; Vin et al. 1994), and (4) resource reservation protocols (Braden, Zhang et al. 1997; Topolcic 1990). Current approaches to admission control are based on the violation prevention paradigm, where the sole criterion for admission is that service commitments made by the network not be violated. We have recently shown (Jamin and Shenker 1997) that admission control algorithms based solely on the violation prevention paradigm can sometimes produce traffic equilibria with some categories of traffic experiencing higher rejection rate than other categories do. By regulating admission through a market, we can extend the paradigm to take other factors into account. While most extant literature on service paradigms assumes a pricing schedule to provide incentives for the adoption of less strict service guarantees, only a handful have explored an actual design (Cocchi et al. 1993), and none has attempted an actual implementation. The resource negotiation protocol RSVP was designed to be extensible in the negotiation parameters it carries. We plan to introduce market-based parameters to the RSVP protocol. 

Network Resource Pricing. Several computer scientists have begun to study price-based approaches to allocating some network resource (Awerbuch et al. 1993; Ferguson et al. 1988; Kurose et al. 1985; Murphy and Murphy 1994; Murphy and Murphy 1995). These models are typically crafted for a particular resource in a particular context; for example, network pricing models usually price a single link. We aim for a more comprehensive pricing architecture. For some preliminary theoretical research on architectures for pricing mechanisms, see the COMET project including (Korilis et al. 1995; Korilis et al. 1997). Another very interesting thread of research has concerned the use of economic mechanisms to allocate multiple qualities of service. See, for example, (Cocchi et al. 1991; Cocchi, Estrin et al. 1993; Shenker 1996). 

Economists also have been studying network resource pricing (see, e.g., the summary of work by MacKie-Mason and colleagues in Section III.E). Gupta et al. (Gupta et al. 1994; Gupta et al. 1995) build a simulation model for priority pricing of multiple resources in a moderately sized network, but the work is not grounded in a technically reasonable network model. Recent relevant theoretical papers include (Brewer and Plott 1996; McAndrews and Rob 1996). For other work, see the extensive bibliography on network economics maintained by Economides. 

Little, if any, research that we are aware of in either economics or computer science squarely addresses the dynamics or the use of market mechanisms to enhance robustness and survivability of networked information systems. Nevertheless, the progress of prior researchers provides an important base for specifying our own network level. 

Electronic Commerce. Most existing work on electronic commerce (Zwass 1996) focuses on what we would consider the last stage-executing an exchange transaction. There is great variety in the many electronic payment systems proposed and developed, and it is clear that no single scheme is best for every purpose (MacKie-Mason and White 1997). Thus, we expect that even after some shakeout in the field, multiple payment systems will coexist, and plan to design an open currency interface to our architecture. The U-PAI system (Ketchpel, Garcia-Molina et al. 1996) integrates multiple schemes by defining an underlying common protocol. Although this approach has some disadvantages (the common-denominator protocol fails to exploit some regularities or provide some features built into the specific protocols), the analysis provides useful insights into the structure of payment protocols. 

Prior to transaction, the parties must negotiate the terms of an agreement. There have been some developments in electronic catalogs, but little on price negotiation per se. General economic literature on auction design is relevant here (McAfee and McMillan 1987; Milgrom 1989), as is reported experience in the design of complex, high-consequence auctions, such as the recent FCC spectrum auction (McAfee and McMillan 1996). We have built on this work in our own reported auction design efforts, and expect to continue to do so. Auction analysis thus far has largely been the province of economists, modulo some computational work on cryptographic bidding protocols (Franklin and Reiter 1996). The emerging auction activity on the World-Wide Web should increase the scope of interest, as well as provide a useful source of comparisons. 

We maintain a wide-ranging bibliography on electronic commerce research and activity. 

Experimental Economics. There has been a recent surge in laboratory experimental research in economics. This work is focused on building economic mechanisms and then measuring the behavior of real participants using that mechanism. There is much to be learned about the practical design and implementation of mechanisms from this literature. Roth maintains pointers to an extensive set of online resources. Recently, some experimental research has focused specifically on building mechanisms for network problems. There have been interesting efforts to design allocation mechanisms for airport slots, natural gas pipelines (McCabe et al. 1989), electric grids and even application layer usage of the space station! 

Fault Tolerance. Fault tolerance, defined as the ability of a system to continue operation when confronted with debilitating resource disruptions, has long been studied by computer scientists. The traditional approach to fault tolerance focuses mainly on redundant resource allocation, distribution of fault points, and monitoring of system vulnerability. One goal of traditional fault tolerance is to array a set of fixed resources to minimize some (typically uniform) measure of vulnerability. We consider our approach of market-based adaptive resource allocation as complementary to the traditional fault tolerance approach. For example, various tasks might have different needs for fault tolerance, expressed as varying willingness to pay for fault tolerance guarantees. Thus, a market might better allocate scarce resources by distributing redundancy to where it is most valued. The allocation service itself needs to tolerate faults, and so might be best implemented on a fault-tolerant substrate. We intend to elucidate the relationship between fault tolerance and adaptivity as the project progresses. 

Complex Adaptive Systems. Other ideas for adaptive architectures are being developed in the field of "complex adaptive systems", which studies emergent phenomena involving nonlinear dynamics in interactions of numerous, possibly adaptive components. Emergent adaptive systems often rely on decentralized decision making by autonomous agents, as in a market mechanism (Arthur 1995; Axtell and Epstein 1997). This is a broad area, encompassing techniques from nonlinear control, ecology, evolutionary computation, and other areas. Although researchers in complex adaptive systems are typically concerned more with analyzing natural and social systems than with engineering them, their models may be put to constructive use. For example, one group of researchers focuses on "agent-based computational economics", which is closely related to our work. However, their interests are primarily to understand the apparently spontaneous appearance of global regularities in economic processes. That is, they develop models of autonomous economic agents, let them interact, and try to understand the resulting dynamics, rather than design systems with desirable properties. As part of this project, we aim to explore this connection through interaction with the University of Michigan program in Complex Systems, in which several of our graduate students are enrolled, and in particular with our School of Information colleagues who work in this area. 

Bibliography 

Arthur, W. B. (1995). Complexity in economic and financial markets. Complexity 1(1): 20-25. 

Atkins, D. E., W. P. Birmingham, E. H. Durfee, et al. (1996). Toward inquiry-based education through interacting software agents. IEEE Computer 29(5): 69-76. 

Awerbuch, B., Y. Azar, and S. Plotkin (1993). Throughput-competitive on-line routing. 34th IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, 

Axtell, R., and J. M. Epstein (1997). Growing Artificial Societies: Social Science from the Bottom Up. MIT Press. 

Baker, F., R. Guérin, and D. Kandlur (1996). Specification of the Committed Rate Quality of Service. 

Beaulieu, J., J. K. MacKie-Mason, and J. Miron (1992). Why Do Countries and Industries With Large Seasonal Cycles Also Have Large Business Cycles? Quarterly Journal of Economics (May): 623-656. 

Bennett, J. C. R., and H. Zhang (1996). Hierarchical Packet Fair Queueing Algorithm. ACM SIGCOMM '96, 

Bergstrom, T., and J. K. MacKie-Mason (1991). Some simple analytics of peak-load pricing. RAND Journal of Economics 22(2): 241-249. 

Boutilier, C., Y. Shoham, and M. P. Wellman (forthcoming). Introduction to the special issue on Principles of multiagent systems. Artificial Intelligence : 

Braden, B., L. Zhang, S. Berson, et al. (1997). Resource ReSerVation Protocol (RSVP). 

Brewer, P. J., and C. R. Plott (1996). A binary conflict ascending price (Bicap) mechanism for the decentralized allocation of the right to use railroad tracks. International Journal of Industrial Organization 14(6): 857-886. 

Cheng, J. Q., and M. P. Wellman (forthcoming). The WALRAS algorithm: A convergent distributed implementation of general-equilibrium outcomes. Computational Economics : 

Clark, D. D., S. J. Shenker, and L. Zhang (1992). Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism. SIGCOMM '92, 

Clearwater, S. H., Ed. (1996). Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific. 

Cocchi, R., D. Estrin, S. Shenker, et al. (1991). A study of priority pricing in multiple service class networks. SIGCOMM '91, 

Cocchi, R., D. Estrin, S. Shenker, et al. (1993). Pricing in computer networks: Motivation, formulation, and example. IEEE Transactions on Networking 1(6): 614-627. 

Davis, R., and R. G. Smith (1983). Negotiation as a Metaphor for Distributed Problem Solving. Artificial Intelligence 20: 63-109. 

de Veciana, G., G. Kesidis, and J. Walrand (1995). Resource Management in Wide-Area ATM Networks Using Effective Bandwidths. IEEE Journal on Selected Areas in Communications 13(6): 1081-1090. 

Demers, A., S. Keshav, and S. J. Shenker (1989). Analysis and Simulation of a Fair Queueing Algorithm. SIGCOMM '89, 

Elwalid, A., D. Mitra, and R. H. Wentworth (1995). A New Approach for Allocating Buffers and Bandwidth to Heterogeneous Regulated Traffic in an ATM Node. IEEE Journal on Selected Areas in Communications 13(6): 1115-1127. 

Ferguson, D., Y. Yemini, and C. Nikolaou (1988). Microeconomic algorithms for load balancing in distributed computer systems. Eighth International Conference on Distributed Computing Systems, 

Ferrari, D., and D. C. Verma (1990). A Scheme for Real-Time Channel Establishment in Wide-Area Networks. IEEE Journal on Selected Areas in Communications 8(3): 368-379. 

Franklin, M. K., and M. K. Reiter (1996). The design and implementation of a secure auction service. IEEE Transactions on Software Engineering 22: 302-312. 

Gagliano, R. A., M. D. Fraser, and M. E. Schaefer (1995). Auction allocation of computing resources. Communications of the ACM 38(6): 88-102. 

Gibbens, R. J., F. P. Kelly, and P. B. Key (1995). A Decision-Theoretic Approach to Call Admission Control in ATM Networks. IEEE Journal on Selected Areas in Communications 13(6): 1101-1114. 

Goyal, P., X. Guo, and H. M. Vin (1996). A Hierarchical CPU Scheduler for Multimedia Operating Systems. USENIX Symposium on Operating Systems Design and Implementation (OSDI), 

Goyal, P., H. M. Vin, and H. Cheng (1996). Start-time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks. ACM SIGCOMM '96, 

Guérin, R., H. Ahmadi, and M. Naghshineh (1991). Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks. IEEE Journal on Selected Areas in Communications 9(7): 968-981. 

Gupta, A., D. O. Stahl, and A. B. Whinston (1994). Managing the Internet as an economic system. University of Texas at Austin. 

Gupta, A., D. O. Stahl, and A. B. Whinston (1995). A Priority Pricing Approach to Manage Multi-Service Class Networks in Real-Time. University of Texas at Austin. 

Hu, J., and M. P. Wellman (1996). Self-fulfilling bias in multiagent learning. Second International Conference on Multiagent Systems, Kyoto, Japan, AAAI Press. 

Jamin, S., P. B. Danzig, S. J. Shenker, et al. (1996). A Measurement-based Admission Control Algorithm for Integrated Services Packet Networks (Extended Version). IEEE Transactions on Networking : 

Jamin, S., S. J. Shenker, and P. B. Danzig (1997). Comparison of Measurement-based Admission Control Algorithms for Controlled-Load Service. To appear in IEEE Infocom '97. 

Ketchpel, S. P., H. Garcia-Molina, A. Paepcke, et al. (1996). U-PAI: A universal payment application interface. Second USENIX Workshop on Electronic Commerce, Oakland, CA, USENIX Association. 

Korilis, Y. A., A. A. Lazar, and A. Orda (1995). Architecting Noncooperative Networks. Journal on Selected Areas in Communications 13(7): 1241-1251. 

Korilis, Y. A., A. A. Lazar, and A. Orda (1997). Achieving network optima using Stackelberg routing strategies. IEEE Transactions on Networking : 

Kurose, J. F., M. Schwartz, and Y. Yemini (1985). A microeconomic approach to decentralized optimization of channel access policies in multiaccess networks. Proceedings of the Fifth International Conference on Distributed Computing Systems, 

MacKie-Mason, J. K. (1994). A spatial smart market for wholesale electricity exchanges. California Energy Institute, UC Berkeley. 

MacKie-Mason, J. K. (1997). Pricing electronic access to knowledge: A field experiment. University of Michigan. 

MacKie-Mason, J. K., and D. Lawson (1991). Local telephone calling demand when customers face optional and nonlinear price schedules. University of Michigan. 

MacKie-Mason, J. K., J. Murphy, and L. Murphy (1996). Feedback and efficiency in ATM networks. International Conference on Communications, IEEE. 

MacKie-Mason, J. K., J. Murphy, and L. Murphy (1996). The role of responsive pricing in the Internet. Journal of Electronic Publishing : 

MacKie-Mason, J. K., and others (1994). A reader's guide to the Blue Book: Issues in California's electric industry restructuring and regulartory reform. Electricity Journal : 

MacKie-Mason, J. K., S. Shenker, and H. R. Varian (1996). Network architecture and content provision: An economic analysis. The Internet and Telecommunications Policy Ed. G. Brock, and G. Rosston. Lawrence Erlbaum. 

MacKie-Mason, J. K., and H. R. Varian (1994). Economic FAQs about the Internet. Journal of Economic Perspectives 8(3): 75-96. 

MacKie-Mason, J. K., and H. R. Varian (1994). Generalized Vickrey Auctions. University of Michigan. 

MacKie-Mason, J. K., and H. R. Varian (1995). Pricing congestible resources. IEEE Journal on Selected Areas in Communications 13(7): 1141-1149. 

MacKie-Mason, J. K., and H. R. Varian (1995). Pricing the Internet. Public Access to the Internet Ed. B. Kahin, and J. Keller. MIT Press. 269-314. 

MacKie-Mason, J. K., and H. R. Varian (1995). Some FAQs about usage-based pricing. Computer Networks and ISDN Systems 28: 257-265. 

MacKie-Mason, J. K., and H. R. Varian (1996). Some economics of the Internet. Networks, Infrastructure, and the New Task for Regulation Ed. W. Sichel. University of Michigan Press. 

MacKie-Mason, J. K., and K. White (1997). Evaluating and selecting a digital money mechanism. Telecommunications Policy Research Ed. G. Rosston, and D. Waterman. Lawrence Erlbaum Associates. 

Malone, T. W., R. E. Fikes, K. R. Grant, et al. (1988). Enterprise: A Market-like Task Scheduler for Distributed Computing Environments. The Ecology of Computation Ed. B. A. Huberman. North-Holland. 177-205. 

McAfee, R. P., and J. McMillan (1987). Auctions and Bidding. Journal of Economic Literature 25: 699-738.McAfee, R. P., and J. McMillan (1996). Analyzing the airwaves auction. Journal of Economic Perspectives 10(1): 159-175. 

McAndrews, J., and R. Rob (1996). Shared ownership and pricing in a network switch. International Journal of Industrial Organization 14(6): 727-746. 

McCabe, K. A., S. J. Rassenti, and V. L. Smith (1989). Designing 'smart' computer-assisted markets: An experimental auction for gas networks. European Journal of Political Economy 5: 259. 

Milgrom, P. (1989). Auctions and bidding: A primer. Journal of Economic Perspectives 3(3): 3-22. 

Miller, M. S., and K. E. Drexler (1988). Markets and Computation: Agoric Open Systems. The Ecology of Computation Ed. B. A. Huberman. North-Holland. 133-176. 

Mullen, T., and M. P. Wellman (1995). A simple computational market for network information services. First International Conference on Multiagent Systems, San Francisco, CA, MIT Press. 

Mullen, T., and M. P. Wellman (1996). Market-based negotiation for digital library services. Second USENIX Workshop on Electronic Commerce, Oakland, CA, USENIX Association. 

Murphy, J., and L. Murphy (1994). Bandwidth Allocation By Pricing In ATM Networks. IFIP Trans. C: Communication Systems C-24: 333-351. 

Murphy, L., and J. Murphy (1995). Feedback and Pricing In ATM Networks. Third Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley, England, 

Parekh, A. K., and R. G. Gallager (1993). A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case. IEEE Transactions on Networking 1(3): 344-357. 

Pennock, D. M., and M. P. Wellman (1996). Toward a market model for Bayesian inference. Twelfth Conference on Uncertainty in Artificial Intelligence, Portland, OR, 

Rosenschein, J. S., and G. Zlotkin (1994). Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. MIT Press. 

Shenker, S. (1996). Service models and pricing policies for integrated services. Public Access to the Internet Ed. B. Kahin, and J. Keller. MIT Press. 

Stonebraker, M., R. Devine, M. Kornacker, et al. (1994). An economic paradigm for query processing and data migration in Mariposa. Third International Conf. on Parallel and Distributed Information Systems, Las Vegas, NV, 

Sutherland, I. E. (1968). A futures market in computer time. Communications of the ACM 11: 449-451. 

Topolcic, C. (1990). Experimental Internet Stream Protocol, Version 2 (ST-II). 

Vin, H. M., A. Goyal, A. Goyal, et al. (1994). An Observation Based Admission Control Algorithm for Multimedia Servers. First IEEE International Conference on Multimedia Computing and Systems, 

Waldspurger, C. A., T. Hogg, B. A. Huberman, et al. (1992). Spawn: A distributed computational economy. IEEE Transactions on Software Engineering 18: 103-117. 

Wellman, M. P. (1991). Review of B. A. Huberman (ed.), The Ecology of Computation. Artificial Intelligence 52: 205-218. 

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

Wellman, M. P. (1995). A computational market model for distributed configuration design. AI for Engineering, Design, and Manufacturing (AI EDAM) 9: 125-133. 

Wellman, M. P. (1996). Market-oriented programming: Some early lessons. Market-Based Control: A Paradigm for Distributed Resource Allocation Ed. S. Clearwater. World Scientific. 

Wroclawski, J. (1995). Specification of the Controlled-Load Network Element Service. Yamaki, H., M. P. Wellman, and T. Ishida (1996). A market-based approach to allocating QoS for multimedia applications. Second International Conference on Multiagent Systems, Kyoto, Japan, AAAI Press. 

Ygge, F., and H. Akkermans (1996). Power load management as a computational market. Second International Conference on Multiagent Systems, Kyoto, Japan, AAAI Press. 

Zwass, V. (1996). Electronic commerce: Structures and issues. International Journal of Electronic Commerce 1(1): 3-23.