The common theme of the research is the coordination of persons (or processors) who face a common task and are linked together by a communication network. Successful completion of the task requires access to complex information. Each person has a piece of that information and some of it needs to be communicated to others if the task is to be performed. We seek coordination schemes that are quick and cheap. Some of the research is theoretical and some of it is applied. The research is interdisciplinary: the five PI's come from Computer Science, Economics, Electrical Engineering, and Operations Research. Seminars and interdisciplinary dissertations allow the work of several disciplines to have impact on each problem, whether the problem is theoretical or applied.

What follows is a brief survey of some of the research that was recently completed or is currently underway.

This inquiry is inspired by observed phenomena like ``telecommuting". It appears that communication technology has led some organizations to disperse geographically. Large central headquarters are expensive and the technology permits persons to move to small (and cheap) local sites, where they perform the same tasks they were performing at Headquarters. Some observers claim that this will be an accelerating trend, drastically changing the way organizations behave. In particular there is concern about the control issue. It may be relatively easy to insure that persons at Headquarters make choices and engage in efforts that are good from the organization's point of view. But once they disperse, self- interested behavior may lead to poor choices. If so, the case for dispersal is weakened.

To gain some insights into these matters, a simple class of models was explored in (4). After dispersal, the network itself remains the same as before. Both before and after dispersal, there is a Center, who receives messages from the n members and takes actions in response. In the simplest variant, the n messages directly identify the week's actions. Once the Center has received the n actions, the chosen action n-tuple is taken and the organization earns a gross payoff. That gross payoff is the sum of n terms; each term is a function of all n actions and of the week's environment. We may think of the ith term as person i's contribution to gross payoff. Both before and after dispersal, each member observes a signal --- her private knowledge of the week's environment --- and bases her message to the Center on this signal. The environment changes each week, according to an unchanging probability distribution. The acts of observing the week's signal, choosing an action, coding the choice into a message, and sending the message to the Center require a member to engage in effort (and to spend time).

Before dispersal, the n persons behave like members of a team. Each week the team collects a net payoff, namely the gross payoff minus the sum of the n individual information-processing efforts. The n members choose those messages (actions) which maximize the team's expected net payoff. We may think of each member as collecting her contribution to gross payoff, placing it in a pool, and then collecting from the pool compensation equal to her weekly information-processing effort. The organization (the ``owner") keeps what's left. Each member is a reliable ``team player", who wants the organization's net payoff to be high. Hence the choices made are the right ones, from the organization's point of view. The n persons strike exactly the right balance between information-processing effort and the gross payoff that the effort yields.

After dispersal, things change. The n persons cease behaving like members of a team. Each becomes a player in an n-person game, called the rule game. Each chooses, once and for all, a rule that will tell that person what message (action) to send to the Center once she has observed the week's signal. Her payoff will be the expected value of her gross-payoff contribution minus her information-processing effort. One general question immediately arises: in an equilibrium of the game, will members' choose higher information-processing efforts than they chose before dispersal, or lower efforts? Does dispersal and self-interest lead to under-use or to over-use of the communication network? Interestingly enough, one's general intuition on this point appears to be silent.

A lot depends on the information-processing effort measure that we choose. In the previous work, we chose to recognize that more frequent messages to the Center may be given shorter codings than less frequent ones. Accordingly, we used the classic Shannon measure. Person i's messages to the Center are strings of bits and her effort equals the Shannon information content of those strings times theta, the time required to transmit one bit. (Thus the higher her effort, the longer she spends on information processing).

Some results obtained so far are these: (1) An equilibrium of the rule game cannot be guaranteed to exist. (We cannot appeal, in the conventional way, to mixed strategies to give us existence of equilibria, since the average amount a player collects from a mixture would not correctly allow for the player's information-processing effort when she uses the mixture). (2) When an equilibrium exists it may be one in which information-processing effort is ``too low" (lower than the pre-dispersal effort), but it may also be one in which the effort is too high. That remains true even under the very strong assumption that the n individual gross payoffs are identical. (3) For very small transmission speeds (values of theta), and also for very high ones, equilibria of the rule game indeed exist.

In future research, several variants of the model will be explored. In particular, we will allow for delay (obsolescence of the actions when too much time is spent by members in deciding what the actions should be); and effort measures other than the Shannon measure (e.g., size of the set of possible messages) will be studied.

The coordination of routing decisions in the internet
In work by V. Anantharam and Richard La (an EECS doctoral student who is also pursuing studies in the Economics Department) a game- theoretic approach to the routing problem is taken. Specifically, the focus is a dynamic game version of the static problem considered by A.Orda, R. Rom, and N. Shimkin in their paper ``Competitive routing in multiuser communication networks", IEEE/ACM Transactions on Networking, Oct. 1993, vol.1, (no.5):510-21. In that paper the authors consider a communication network shared by several selfish users. Each user seeks to optimize its own performance by controlling the routing of its demand. This is a static noncooperative game. For a two-node multiple links system, uniqueness of the Nash equilibrium is proven under a convexity assumption, and monotonicity properties of the Nash equilibriun are determined. Partial results of a similar nature are derived for general networks. The analysis is entirely for a static (one stage) formulation of the problem. The new dynamic version allows for the possibility of threats and responses, which is much closer to the reality of the noncooperative setting one anticipates in the developing information superhighway.

Economies of scope in communication
Suppose each of n organizations faces a changing environment. The agents at its nodes use an information-processing procedure that is costly (it uses members' time and effort) to find appropriate new actions whenever the environment changes. If we leave the n goals unchanged and merge the n organizations into one, does the merger increase, decrease, or leave unchanged the total information- processing effort that is needed to achieve those goals? After all, all we are doing is assembling previously separate groups in one "room". If their tasks remain exactly what they were before, then how can merging save us anything?

There are many ways to formulate the problem. Imagine, to start with, that each organization uses a complete communication network. Each agent observes a piece of the environment and then broadcasts a message to all the others. There is then another interchange, in which each broadcasts a new message, based on the previous broadcasts; and so on. When a stationary interchange is reached, an action is taken (by an arbitrarily designated action-taker). The action meets the organization's goal if it is a certain pre-specified function of the organization's current environment. The size of the set of possible messages that the members can broadcast at each step ---the size of the "language" they need to learn --- is a natural and workable measure of the informational effort that the protocol requires.

In previous work (7) it was shown that when every message set is a continuum, and its size is measured by its dimension, then merging the small complete networks into a large one cannot lower the total information-processing effort. If the goals are unchanged, then the sum of the small organizations' message-set dimensions equals the lowest attainable message-set dimension for the merged organization, provided that the protocols obey some regularity conditions. In (7) it was found, by contrast, that when the message sets are finite, there may indeed be cases where merging decreases the total number of messages needed. A surprisingly simple example, with two two-person organizations, shows this to be so. Such examples can be ruled out in various ways, but they suggest that there is a lot more to be learned.

In particular, we have started to consider protocols in which the networks are not complete. Messages are individually addressed (sent from one person to another) rather than broadcast. A protocol's message set is now the set of possible individually addressed messages and the size of that set is the protocol's cost.

When the message sets are continua, we no longer get the "merging-doesn't save-you-anything" result in the straightforward way that we obtain it for the complete-network case. The difficulty is that certain message combinations ---e.g., 1 sends message A to 2 while 2 sends message B to 3 and 3 sends message C to 1 --- might never occur in the protocol, yet A and B and C can each occur within other combinations. Our cost measure gives no "credit" for unused combinations. Merging the small networks into one might mean fewer unused combinations and hence a saving. Using computational-algebra methods based on elimination theory, Marschak, and F. Rojas and J. Eisenberg (doctoral students in Mathematics), are searching for such examples. When the examples are found, we expect to develop interesting conditions that rule them out.

Identification plus Transmission over Channels with Perfect Feedback
The problem is motivated by the observation that private channels are very expensive compared to public ones. Thus it may be very valuable to brioadcast publicly messages that are intended for an individual receiver, provided the receiver can identify those messages that are intended for it. Specifically, suppose a transmitter is connected to N different receivers by a single discrete memoryless channel W, with positive Shannon capacity C, whose output is available to all the receivers and the transmitter, i.e., there is perfect and instantaneous feedback. In n channel uses, the transmitter wishes to send one of M messages to one of the N receivers, whose identity is a priori unknown to the receivers. The requirements are that the intended recipient should decode the transmitted message correctly with high probability, and any other receiver should recognize with high probability that the message is not intended for it (these probabilities are averaged over the M messages). It is proved in (16) that in this situation M and N can simultaneously grow as \exp[nR_1-o(n)] and \exp\\exp[nR_2-o(n)]\, respectively, for all rate-pairs (R_1,R_2) satisfying R_1 \le C and R_2 \le \max_P:I(P;W) \ge R_1 H(W|P), provided the transmitter can use randomized encoding. If the encoding must be deterministic, we prove that all rate-pairs (R_1,R_2) satisfying R_1 \le C and R_2 \le R_1 + \max_P:I(P;W) \ge R_1 H(W|P) are achievable. In both cases these rate regions are shown to be optimal by proving ``strong'' converses.

Agreeing on a common source of randomness
It is well known that if we have two agents, Alice and Bob, who are connected to each other by independent discrete memoryless channels and want to compute a function f(x,y), where x is observed by Alice and y by Bob, then random protocols achieve the desired result much more quickly (on the average) than deterministic ones. But such random algorithms require that both parties agree on a common source of randomness, i.e., they need to agree on a common random number. New work, reported in (17), shows that, even if Alice and Bob do not have access to any external random number generators, they can communicate interactively over the two channels, and exploit channel noise to generate common randomness at a rate of \max\big\\min\lt[ H(W|Q), I(P;V) \rt] + \min\lt[H(V|P), I(Q;W) \rt]\big\ bits per step of communication. Here, V is the channel from Alice to Bob, and W is that from Bob to Alice. The maximum is over all probability distributions P and Q on the input alphabets of V and W respectively. We also prove a strong converse which establishes the above rate as optimal.

The problem can be extended to the case of an arbitrary network of three or more processors. There is a a very promising conjecture on the form of the common randomness capacity of such a network. The conjecture has been proved true for some special cases (e.g. a ring of processors) and work on a general proof is underway.

Distributed computing using unreliable networks
Computing over unreliable networks (with noisy links) is a central problem in distributed computing. One approach to this problem is to encode each message using classical error-correcting codes. This can be quite wasteful if the computation is fine grained, and involves frequent communication. A more efficient approach to this problem is explored in (11), a doctoral dissertation, where it is shown that any computation can be carried out on an unreliable network with a simulation overhead that is constant, independent of the length of the computation. Moreover, the error probability of the simulation is exponentially small in the length of the computation. Achieving the same error bounds using classical coding theory results in a simulation overhead that grows logarithmically in the length of the computation. The dissertation also gives a more simple and tight analysis in the case where the network is a simple chain of noisy links.

Electing a leader
A fundamental task in distributed computation is ``leader election'', or singling out one of the processors. Several important tasks in distributed computation can be reduced to ``leader election''. What makes the problem tricky is that some fraction of the processors might fail during the protocol, and therefore the protocol must be sufficiently robust to withstand such failures. The most general types of failures that can be considered are Byzantine failures, where the failed processors are assumed to collude to try to prevent the protocol from succeeding. There are two parameters of interest for such a protocol: one is the number of rounds, since each round is preceeded by a costly synchronization step. The second is the fraction of failed processors. A simple protocol, reported in (10), works in O(\log n) rounds to elect a leader in an n processor network, where \beta fraction of the processors fail for any \beta < 1/2. This latter bound is tight, since it is known that no protocol can succeed if half of the processors fail.

Coordinating a team of agents who are exploring a tree
In a wide class of problems there are n agents whose common task is to explore an environment. For example, the agents seek to develop a product of specified performance, knowing that there are many approaches or designs as candidates. The situation can be modelled as the exploration of tree, where reaching any sufficiently deep leaf corresponds to completion of the task and one wants to find a leaf quickly. At each node some information has been acquired and a fresh choice among design alternatives has to be made. One way to organize the team of agents is to let each search a subtree quite independently of the others. In (1) it is proved in a formal setting that if instead we require the agents to communicate periodically, while at the same time we allow them to explore independently between the successive communications, then we reduce the total time until the task is completed (until a deep leaf is reached) by an exponential factor.

I. Coordination of electric power systems in a deregulated environment
The work on power system coordination has relied heavily on models of coordination developed over a number of years by members of the Berkeley group whose research on network coordination problems has been supported by ITO grants. The work on power system coordination uses those models to provide a critical analysis of some major schemes for electricity deregulation and to propose an alternative scheme. The California Public Utilities Commission (CPUC) has determined to achieve a more competitive electricity industry and, following a two-year debate, the California Legislature approved the CPUC proposal in August 1996. Our work had a significant bearing on this debate and its impact can be seen in the way that deregulation is being implemented. Thus the practical impact of this work is substantial. The steps followed in California are being watched in every other state in the country.

Not only in California, but around the world, the electric power industries are undergoing a revolutionary transition from vertically integrated regulated or government-run monopolies to a competitive industry. The transmission network plays an essential role in this transition by providing the critical interconnection between geographically dispersed markets. It is, therefore, generally agreed that open access via the transmission network is the key to a competitive electricity industry. The approaches adopted in different countries vary in terms of the market organization, system operation, transmission charges, congestion management, investment incentives, etc. The US electricity system is characterized by a high degree of interconnection and diverse ownership of transmission assets and generation resources. Consequently, the implementation of open transmission access in the US hinges upon the establishment of property rights and coordination protocols for the transmission network along with mechanisms for ownership compensation and usage charges.

By its nature the problem is interdisciplinary. The work has involved faculty and graduate students from Electrical Engineering, Operations Research, Computer Science, and Economics.

We now turn to a summary of specific topics.

(i) Problems of Unit Commitment in Power System Generation
(12) was an interdisciplinary dissertation, supervised by S. Oren and P. Varaiya; (13) and (14) were based on results in (12); (6) was another paper dealing with this class of problems. One of the main contributions in (12) was a new approach to solving unit commitment problems with transmission constraints when there is congestion in the transmission grid. (13) describes variations on Lagrangian relaxation methods, and empirical tests that permit improvement of the final schedule through optimal decommitment of units. (14) shows how to reduce the cost of meeting the spinning reserve requirement by relaxing the constraint at those times at which meeting that requirement is the most expensive. (6) demonstrates the implication of centralized unit commitment in a competitive electricity market where generation resources are independently owned. It calls attention to potential pitfalls of the California restructuring plan.

(ii) Electric power pricing under uncertainty
Paper (5) compared schemes for pricing electric power in terms of how well they coordinate the decisions of participants---consumers, suppliers, and regulators. A scheme is analyzed along two dimensions: the aspects of participants' private information that the scheme reveals; and the efficiency of the allocation the scheme reaches. Information aspects are studied within the framework of economic mechanism theory; allocation efficiency is studied within a stochastic recourse model which takes into account consumer loss due to rationing.

(iii) Competition in transmission
Nodal prices, congestion revenues, transmission capacity rights, and compensation for wire ownership are some of the key concepts used to formulate claims about various proposals to organize competitive and open transmission access. Underlying those claims are implicit assertions (folk theorems) concerning the regulation of transmission access, the determination of power flows, properties of economic dispatch, and the operations of competitive nodal markets for power. The study reported in (18) has two objectives. First, we formulate these folk theorems as explicit mathematical assertions. Second we prove that some of those assertions are true, and we present counterexamples to other assertions. The counterexamples are interesting because they negate plausible beliefs, including the following: (1) uncongested lines do not receive congestion rents (defined through node price differences); (2) nodal prices clear markets for power only if the allocation is efficient; (3) in an efficient allocation power can only flow from nodes with higher prices to nodes with lower prices; (4) strengthening transmission lines or building additional lines increases transmission capacity; (5) transmission capacity rights are compatible with any economically efficient dispatch.

Another paper, (9), challenges several claims about the role of nodal prices and transmission rights that have been accepted by some practitioners and regulators in the discussion of the transition towards a more competitive electricity sector. Recent moves to open up electric power transmission networks to foster generation competition and customer choice have touched off a debate over how the transmission system should be restructured in order to meet the goal. The opposing sides of this debate are now commonly represented by the bilateral model and the pooling model. Both models resort to conventional centralized operation in dealing with the shared resources of an integrated transmission network. The conventional operating paradigm was developed in a different era for electric utilities operated as regulated monopolies. A new operating paradigm is needed for a restructured industry that encourages efficient competition and at the same time maintains necessary coordination to guarantee a high standard of reliability. In (19) a new operating paradigm is proposed. The decision mechanisms that deal with the economics and the reliability (security) of system operation are separated. Economic decisions are carried out by private multilateral trades among generators and consumers. Reliability, on the other hand, is coordinated through the power system operator, who provides publicly accessible data. Using the data, generators and consumers can determine profitable trades that meet the secure transmission loading limits. We prove that any sequence of such coordinated private multilateral trades, each of which benefits all parties to the trade, leads to efficient operations, i.e., maximizes social welfare. The coordinated multilateral trading model achieves all the benefits of a centralized pool operation without the visible, heavy hand of a pool operator in economic decisions. It is shown that the existing communications, computing and control infrastructure is adequate to support the proposed model. It is also shown that the coordinated multilateral trading model can coexist with the traditional model and provides non-discriminatory service to both utility customers and direct-access customers.

II. Coordination and decentralization in manufacturing organizations
There is an emerging trend in manufacturing industries around the world toward decentralization of operational units and a transition from a cost-center approach to a profit-center structure, where distinct divisions of a corporation interact as independent companies. The coordination of such a decentralized structure in order to pursue common goals of the corporation can be accomplished through incentive schemes, market mechanisms, transfer prices and interaction protocols. The following studies investigate the efficacy of such approaches in the context of manufacturing organizations.

(ii) Internal auctions for intermediate products.
Paper (2) looks at the problem of setting production levels and choosing an internal supplier for a vital intermediate product. Those decisions are made in a decentralized manufacturing environment. There are internal suppliers who operate as profit centers with private cost information. The analysis centers on the use of multi-dimensional auctions that facilitate communication between divisions and implement efficiency goals. The mechanism enlists bids in the form of a fixed and variable price. It is designed so as to induce bidders to reveal their true costs of production. It is shown to guarantee efficient resource utilization.

(iii) Informationally efficient schemes for controlling quality and yield in semiconductor manufacturing.
Unpredictable yields in the production of semiconductor chips result in mismatches between supply and demand with respect to the distribution of quality attributes such as speed and power supply. That in turn causes allocative inefficiencies and delivery delays. The work reported in (8) introduces a methodology for pricing both delivery priority and quality attributes (e.g. speed) for custom semiconductor chips. The approach allows information asymmetry and is designed to efficiently coordinate and match the demand with the manufacturing output, through customer self-selection.

1. D. Aldous and U. Vazirani, ``Go-with-the-winners algorithms'', Proceedings of the Symposium on the Foundations of Computer Science, 1995.
   
   
2. J. Bushnell and S. Oren, "Internal Auctions for Efficient Sourcing of Intermediate Products", Journal of Production Management, 12 (1995) pp 311-320
   
   
3. S. Dasgupta, ``The Sample Complexity of Learning Bayesian Networks,'' working paper, 1996.
   
   
4. E. Friedman and T. Marschak, ``Communication Effort in Teams and in Games," in W. Guth and E. Van Damme, eds., Understanding Strategic Interaction: Essays in Honor of Reinhard Selten Springer, 1996.
   
   
5. T. Ishikida and P. Varaiya, ``Pricing of Electric Power under Uncertainty: Information and Efficiency", IEEE Transactions on Power Systems, Vol 10(2), 884-890, May 1995.
   
   
6. R. Johnson, S. Oren, A. Svoboda, ``Equity and Efficiency of Unit Commitment in Competitive Electricity Markets.", Utilities Policy", (accepted for publication), June, 1996.
   
   
7. T. Marschak, ``On Economies of Scale in Communication'', Economic Design, Vol 2, No. 2, 1996.
   
   
8. K.J. Min and S. Oren, "Economic Determination of Spec. Levels and Allocation Priorities of Semiconductor Products," IIE Transactions, Vol 27, (1995) pp. 321-331.
   
   
9. S. Oren, P. Spiller, P. Varaiya and F. Wu, ``Nodal prices and transmission rights: a critical appraisal", The Electricity Journal, Vol 8(3), pp. 24-35, April 1995.
   
   
10. R. Ostrovsky, S. Rajagopalan, U. Vazirani, ``Simple and Efficient Leader Election,'' submitted to \em Siam J. Computing.
    
    
11. S. Rajagopalan, ``A Coding Theorem for Distributed Computation,'' U. C. Berkeley Ph.D. dissertation, 1995.
    
    
12. C-L. Tseng ``Power System Generation Unit Commitment Problems", Ph.D. Dissertation, Dept. of IEOR, University of California at Berkeley, December 1996.
    
    
13. C-L. Tseng, S. Oren, A. Svoboda, R. Johnson, "A Unit Decommitment Method in Power System Scheduling." Report UCB/ERL/IGCT M96/31 (May 1996), University of California at Berkeley.
    
    
14. C-L.Tseng, S. Oren, A. Svoboda, R. Johnson, "Price Based Adaptive Spinning Reserve Requirements in Power System Scheduling." Report UCB/ERL/IGCT M96/32 (May 1996), University of California at Berkeley.
    
    
15. A. Ugarte, ``Coordination Mechanisms for Hi-Tech Manufacturing Organizations" Ph.D. Dissertation, IEOR Department, University of California at Berkeley, Dec. 1995.
    
    
16. S. Venkatesan and V. Anantharam, ``Identification plus Transmission over Channels with Perfect Feedback". UCB/ERL Memorandum, No. M96/34, Electronics Research Laboratory, University of California, Berkeley, May 1996. Submitted for publication in IEEE Transactions on Information Theory.
    
    
17. S. Venkatesan and V. Anantharam, ``The Common Randomness Capacity of a Pair of Independent Discrete Memoryless Channels". UCB/ERL Memorandum, No. M95/85, Electronics Research Laboratory, University of California, Berkeley, September 1995.
    
    
18. F. Wu, P. Varaiya, P. Spiller and S. Oren, Folk theorems on transmission access: proofs and counterexamples, Journal of Regulatory Economics, vol 10(1), pp. 5-23, July 1996.
    
    
19. F. Wu and P. Varaiya, ``Coordinated multilateral trades for electric power", working paper, 51 pp, June 1996. Talks based on this work have been presented to the California Public Utilities Commission and several conferences.