STANLEY REITER

Center for Math Studies
Leverone Hall
Northwestern University
Evanston IL 60208
Office phone: 847-491-2531
Office fax: 847-491-2530
Email: s-reiter@nwu.edu


Design of Decentralized Mechanisms
(Joint work with L.Hurwicz)



The formal analogy between decentralized economic mechanisms and distributed computation is well recognized. A decentralized mechanism on the one hand represents an organization whose performance can be described by a function (or more generally a corres pondence), and, on the other hand, can be interpreted as a distributed computation of that function.

The goals of economic activity can be described by a function (or correspondence). If the function computed by a mechanism is the same as the one specifying the goal, we say that the mechanism realizes the goal. (The term "realize" is the counter part of "implement" but without the game theoretic connotations.)

A design problem consists of: (i) a goal function, together with (ii) a specification of the initial dispersion of information about the arguments of the goal function among a set of agents or processors, and, iii) criteria of informati onal efficiency.

To solve a design problem means to discover or invent a decentralized mechanism that realizes the goal function given the initial dispersion of information, and is informationally efficient. One can invent or discover a mechanism by a creative act, or luc ky insight. Since one cannot count on inspiration alone, it would be helpful if there were a systematic procedure--an algorithm-- that started from the goal function and distribution of information, and produced informationally efficient mechanisms that realize the goal function.

Our earlier work studied the case of smooth goal functions, and used methods that were equivalent to solving (nonlinear) partial differential equations. While they yielded important insights, these methods are not quite algorithmic, and do not apply to di screte cases. We have since developed elementary methods that apply to cases in which the domain of the goal function is finite dimensional, but is without other restrictions. These methods apply when the domain and range of the goal function are discrete ; hence they can be applied in situations typical in both organizational and computational settings, where the sets are finite. The mechanisms they produce are decentralized, and have several desirable properties of informational efficiency. The methods also apply to cases where real variables and functions are involved, and the sets and functions are given by equations.

In the course of this research a mathematical problem arose for which we could not find a solution in the literature. The following is a brief description of our work on this problem. (The reference is: Hurwicz, L. and S. Reiter, "On representation of classes of sets." CMSEMS Disc. Paper # 1176)

A system of distinct representatives (SDR) for a collection of sets consists of an element from each set (its representative) such that the representative uniquely identifies the set it belongs to. Theorem 1 gives a necessary and sufficient condition th at an arbitrary collection of sets have an SDR. Theorem 1 generalizes Hall's theorem, and what we know of the literature extending it. In the context of designing decentralized economic mechanisms it turned out to be important to know when one can const ruct an SDR for a collection of sets that cover the parameter space characterizing N agents

Theorems 2-5 give different characterizations of situations in which the collection of sets is a partition. This is of interest because, in the context of mechanism design, partitions have special properties of informational efficiency.



Complexity in Decentralized Mechanisms
(Joint work with K. Mount)


The complexity of computations is an essential element of the analysis of informational efficiency of decentralized mechanisms. The standard analysis of (time) complexity, based on the Turing machine, is not fully satisfactory when applied to systems li ke economic organizations, which typically involve human agents, and in which parallel computations are important. ( See for instance Zomaya, A. Y., Parallel and Distributed Computing Handbook, New York, McGraw-Hill, 1996. for a discussion of some of the reasons.) We have therefore developed a somewhat different model, the modular network , which seems more naturally applicable to computation performed by economic organizations. The model is based on the neural network of McCulloch and Pitts, but is ext ended to allow computation in Euclidean spaces, and to more general spaces that can be encoded in Euclidean spaces. The set of elementary functions, which consists of Boolean functions in the McCulloch-Pitts model, is a primitive of the modular network m odel. This enables the model to cover a range of possible computational settings. When the model is specialized to a finite alphabet and Boolean functions it is equivalent to the finite automaton model. When the set of elementary operations consists, f or example, of analytic functions of two variables (with the appropriate domains), it connects with work in classical mathematics, namely, Hilbert's 13th problem and the literature on that subject. Other specifications of the set of elementary operations lead to different interpretations.

We apply this model to the decentralized mechanisms discussed above to analyze the informational efficiency of mechanisms that realize the Walrasian goal function in an example. We show that there is trade-off between communication complexity and compu tational complexity in the case studied.

Organizations as Computing Devices

The idea that a decentralized organization, such as a Walrasian mechanism, is a computing device is a relatively old one in economics. I use the modular network model as the basis for a model of organization in which the organization's behavior is desc ribed by a function; we view the organization as computing the value of this function in each environment it might encounter. In carrying out this computation the elementary computing must be assigned to agents to execute, subject to certain constraint s on parallel execution, and with costs associated with both communication and computing, as well as with the number of agents used to carry out the computation. Efficient assignments are analyzed, and some conclusions are reached about the circumstances that lead to centralized and alternatively to decentralized organizational structure.



Return to ITO WorkshopAbstracts

Return to ITO Workshop Home Page