The full text on this page is automatically extracted from the file linked above and may contain errors and inconsistencies.
www.clevelandfed.org/research/workpaper/index.cfm
Working Paver 9016
SOME PROBLEMS OF INFINITE REGRESS IN SOCIAL-CHOICE MODELS:
A CATEGORY THEORY SOLUTION
by Fadi Alameddine
Fadi Alameddine is a research assistant at the
Federal Reserve Bank of Cleveland. The author
wishes to thank Paul Bauer, Randall Eberts,
Owen Humpage, Robin Ratliff, and especially
Spyros Vassilakis, whose research and comments
have been instrumental to this study.
Working papers of the Federal Reserve Bank of
Cleveland are preliminary materials circulated
to stimulate discussion and critical comment.
The views stated herein are those of the
author and not necessarily those of the
Federal Reserve Bank of Cleveland or of the
Board of Governors of the Federal Reserve
System.
December 1990
www.clevelandfed.org/research/workpaper/index.cfm
Introduction
In modern Western democracies, economic and political institutions
often have been criticized on moral grounds. The arguments pinpoint the
resulting inequalities and inefficiencies as the evidence of these
institutions' inadequacy to provide justice. However, evaluating institutions
in retrospect (ex post), by contrasting their ex-post resource allocation with
other allocations known to be feasible ex post, is misleading. Social
decisions must be made under conditions of uncertainty. Hence, institutions
must be evaluated before the uncertainty is resolved (ex ante), i.e.,
according to their expected performance, as delimited by the information
available at the time decisions are made. So an institution can be condemned
only if an alternative one exists yielding preferable outcomes (by any measure
to be decided upon) under the same ex-ante information set.
This view is mainly endorsed by economists in the latter part of the
twentieth century. However, it ignores the process by which a given
institution is to be chosen. The process is itself an institution, so that
the statement of the problem embeds in an infinite regress: The process must
itself be the object of choice of some process which, once again, is itself an
institution and therefore the object of choice of another process. Unless this
infinite regress is resolved, further inquiries on social-choice theory will
be limited in scope. Furthermore, because institutional decisions
are
actually
made, a proper theoretical account must capture the process.
This paper is concerned with the solution of the infinite regress
problem as it arises in social-choice theory. My approach is to draw on
www.clevelandfed.org/research/workpaper/index.cfm
arguments that consider social choices in game-theoretic environments where
information is decentralized, and whose fundamental outcomes are the
procedures conducive for players to coordinate decisions. In the tradition of
game theory, these procedures are called mechanisms. The objective is to
establish the existence of a universal mechanism, i.e., a mechanism whose
strategy spaces include all possible proposals to change the mechanism.
Section I outlines what I have termed the "Gauthier framework" and
elaborates how the infinite regress arises. Section I1 maps out a general
style for solving recursive specifications, with category theory providing the
concepts needed for the construction of a universal mechanism. Section I11
adapts the universal mechanism construction, in Vassilakis (1989), to the Nash
demand game, which can be seen as a formal Gauthier bargaining setup.
www.clevelandfed.org/research/workpaper/index.cfm
I. The Infinite Regress Statement Within Gauthier's Framework
The analogy between individual choice and social choice has been aptly
formulated by John Rawls (1971): As each individual rationally decides what
constitutes his own good, a society must decide on its system of justice.
Thus, a society must be modeled as if it has an objective function. In
decision theory, the view supporting rational individual choice is that of
expected utility maximization. The task of social-choice theory is to
construct an objective function from individual utility functions. Social
choice then must be a product of meditated choice by its individuals.
To extract a social-objective function (social-welfare function),
Rawls suggests putting any rational individual behind the veil of ignorance
and asking that person to select the basic rules for a society. This person's
chosen rules are the principles of justice, to which all persons should agree.
As David Gauthier remarked, Rawls' approach is not a viable solution for the
rational-choice problem because it requires individuals to form a concept of
justice prior to the original agreement. From the parallel between the
individual and social choice, such a prior concept cannot be justified. It is
itself a principle of justice and should be the outcome rather than the
assumption of the theory.
The individual preferences (utilities) must be the only argument of
the social-welfare function. If society's preference is represented by a
mapping, then the question becomes how should it depend on individual utility
functions?
www.clevelandfed.org/research/workpaper/index.cfm
My stand echoes Gauthier's (1984, p. 255): "...the principles of
justice are those principles for making social decisions or choices to which
rational individuals, each seeking to cooperate with her fellows in order to
maximize her own utility, would agree." A desirable social welfare function is
not the outcome of single optimization problems, but the outcome of mutually
consistent optimization problems. The mutual consistency is formalized by the
solution concept of a game.
Gauthier proceeds to propose a bargaining game in the spirit of a Nash
demand game. However, the game ' s bargaining procedures are exogenously
specified (see Gauthier [1982], p. 256). For example, he insists that all
parties must be equally able to advocate and advance their intere'sts (fair
play). Furthermore, all agents must have an identical information set when
decisions are made. He then shows that all players have the same dominant
strategy, whose outcome is individually rational (weakly preferred by all
agents over nonparticipation), and incentive compatible (truthful reporting is
a dominant strategy for all players). 2
There are two ways to build on Gauthier's work. The first is to relax
the complete information assumption. In bargaining games, allocations are type
contingent (an agent's type is usually characterized by his preferences and
information set). In general, agents will not take the same actions in
************
Length constraints preclude a presentation of a formal account of
Gauthier's game. Please see the referenced work for a full exposition.
'
Gauthier does not explicitly use these terms. However, by a Coasian
argument, these results can be directly extracted.
www.clevelandfed.org/research/workpaper/index.cfm
equilibrium because their actions reveal their private information, which
might have an adverse effect on their payoff. This, in turn, restricts the set
of feasible mechanisms. To illustrate, the appendix contains a simple voting
game, first advanced by Holmstrom and Myerson (1983).
Second, the comments directed at Rawls' veil of ignorance can be
channeled against any exogenous condition that the philosopher imposes. Fair
play (on the procedural level) is itself a principle of justice and hence
should not be assumed. One could surmise that fair play must be agreed upon by
some prior bargaining session, but the rules of this session cannot be
exogenously imposed either. Therefore, we must construct yet another
bargaining mechanism to solve the problem at this level.3 Clearly, this
problem will appear at every level. The resulting infinite regress must be
dealt with by constructing a mechanism in which strategy spaces contain
proposals for amending the rules of any game; I call this mechanism universal.
This argument is beyond a mere technicality. If we are to extract the
principles of justice from the equilibrium of a game based on a given
mechanism, then it is imperative to show that such a mechanism is not only
feasible, but that it is chosen exclusively by the players, and not introduced
exogenously by the analyst through the procedural rules. Consider a game,
representing a society, with n agents faced with the problem of allocating the
resources in their economy. I refer to this game as the underlying game.
Initially, all agents have a given endowment and a set of strategies. If play
************
This idea is advanced in Crawford (1985).
www.clevelandfed.org/research/workpaper/index.cfm
takes place noncooperatively, i.e., a "war of all against all" scenario, the
resulting Nash equilibrium is usually Pareto inefficient. As a parable, we can
think of the well-known prisoners' dilemma game. The Nash equilibrium
coincides with both players confessing, which is clearly suboptimal to both
not confessing.4 Now, agents can suggest Pareto improvements by attempting
preplay negotiations. Players try to coordinate their actions through
mechanisms that determine the play of the underlying game. Preplay
negotiations can be viewed as a separate round of bargaining over mechanisms,
but there is no guarantee that an agreement will be reached in this game
either. The point is that whatever procedural constraints the philosopher
wishes to introduce, he must show them to be the outcome of a previous stage
of bargaining. Furthermore, this point remains valid whether the constraints
are introduced on the procedures of the underlying game or on the procedures
of the subsequent preplay negotiations.
This section concludes with a brief discussion concerning the solution
concept of a game and Nash equilibria. Although it may appear that this paper
has identified a Nash equilibrium as the solution to a game, this view is
misleading. Instead, I present the concept of a Nash equilibrium along the
same lines as Kreps (1990): "The concept (of a Nash equilibrium) is advanced
as an answer to the question: If there is an obvious way to play the game (a
way that all players can figure out and all expect the others to do the same),
************
Once again, length constraints forbid offering a full account of the
prisoners' dilemma game. However, this game is popular enough to be found in
almost any book related to game theory.
www.clevelandfed.org/research/workpaper/index.cfm
what p r o p e r t i e s must t h e " s o l u t i o n l
possess?" The answer, adopted i n t h i s
paper, i s t h a t t h e Nash equilibrium concept i s t h e necessary, y e t not
s u f f i c i e n t , condition f o r an outcome t o be a s o l u t i o n .
www.clevelandfed.org/research/workpaper/index.cfm
11. Resolving the Infinite Regress Problem
The previous section concluded by asserting that the solution to a
game must be a Nash equilibrium. This section introduces the concept that
game theory and, subsequently, economic theory have been employed to prove the
existence of equilibria. I then proceed to offer a general style (general
approach) for solving infinite regress, while introducing the associated
mathematical notions.
Given a noncooperative game G=(I,S,U), where I is the set of players,
S the vector of strategy spaces, and U:II(S)--->R a utility function for
each agent, we can define a best reply map for all i t s in I.5 The best
reply map provides a natural relation to equilibrium points. An equilibrium
point must be a best reply to itself, and any strategy combination that is a
best reply to itself must be an equilibrium point. The following lemma
formalizes this concept.
1. Lemma: (Friedman [I9861 p. 36) Let G=(I,S,B) be a noncooperative game.
s
E
S is an equilibrium point of G iff s
E
f(s),
i.e., s is a fixed
point of f.
So, given the mathematical specification of a game, the problem of
solving for the equilibria reduces to the existence of fixed points.
The best reply mapping for player i is defined as a relationship
associating each strategy combination of s E S with si E Si according
to the following rule: fi(s)=(ti E S, Ui(s\ti)=max U(s\sti)). The best
reply mapping is f(s)=fl(s)x . . .xfn(s).
www.clevelandfed.org/research/workpaper/index.cfm
Conditions for uniqueness, stability, and parametric dependence of the fixed
point are sought thereafter.6
Let us now investigate a bargaining game. Suppose we have two agents
(1 and 2), and one perfectly divisible good (X). Agents have identical utility
functions, and without loss of generality we let Ul(x)=U2(x)=x.
The players
must agree on a division of the good. They simultaneously announce a demand
D(xi)
E
R+, with i=l, 2. If agreement is achieved, the agreed-upon
division is implemented. If no agreement is achieved, the good is evenly split
between the players: 1 gets X/2 and 2 gets X/2. For the moment, we assume the
players know each other's utility functions. Therefore, players know each
other's reaction function f :R+-- ->R+; in addition, the players know that f is
common to both. The fixed point solution of this game is rather trivial
because
~(xi)=f(~(xj) )
and D(xj)=f (D(xi) ) , with xi=xj2x/2.
Let us complicate the situation by relaxing the common knowledge assumption
and by postulating that if no agreement is achieved, then neither player
receives anything, so U1=U2=0. Now players have an incentive to coordinate
their announcements, by suggesting mechanisms that induce cooperative play.
However, equilibrium expectations are too important to ignore. Agents do not
have the knowledge of each other's reaction functions, so 1 (2) cannot decide
on a mechanism unless he forms beliefs on 2 (1)'s reaction function over
By stability, I mean that starting with an arbitrary initial point, the
system will converge to the fixed point.
www.clevelandfed.org/research/workpaper/index.cfm
mechanisms. In essence, 1 (2) must assess the probability that 2 (1) agrees to
a given mechanism. Let S be the set of all possible mechanisms. Let P(S) be
the set of probability measures on S , such that for
assigned a probability p(s).
beliefs belong to Dl(x 2)=p(S).
V
s
E
S, s is
So 1's beliefs belong to Dl(x 1)=P(S),
and 2's
Yet, 2 (1)'s reaction function is itself a
function of his beliefs. So 1 (2) needs to form beliefs on 2 (1)'s beliefs
about 1 (2)'s reaction function. Thus:
o2(x1)=~(~x~,(x2) )
and D2(x 2)=P(SxDl(x 1) ) .
Proceeding in this way, we get a system of difference equations:
D~+~(~~)=P(S~D~(~~))
Dt+l(x 2 )=P(SxDt(x 1) ) , t2l
with
D~(X~))=P(S)
Clearly, Dt(x 1)=Dt(x 2)=Dt(x),
for i=l, 2.
t21, and we can write
Dt+l(x>=P(SxDt(x>>=F,(D(x)).
We can interpret each F-(D(x))
J
in Fj-l(D(x)),
as an attempt at coordinating actions
that is, F-(D(x))=F(S-l(D(x))).
J
In this formulation, the
players' suggestions about mechanisms are a function of their beliefs about
each other's reaction mapping. Using arrows, we can represent the system
diagramatically:
2. Diagram:
Fo(D(x) )t-with FO(D(x))
F1(D(x) )+
F2 (D(x) )+
. . .+
Fn(D(x) )+
being the original game played noncooperatively.
Fn+l(D(~))
---
www.clevelandfed.org/research/workpaper/index.cfm
Unfortunately, traditional analysis cannot provide a solution for this
system of difference equations. Consequently, traditional fixed-point theorems
cannot be invoked. First, the left-hand side is a set of points in R+, while
the right-hand side is a set of probability measures. Second, the domain of F
cannot be restricted to be a set anymore, since for a fixed point of F to
exist, F must map sets (rather than the elements between them). So the domain
of F must be the collection of all sets, which is not a set, by the Russell
paradox. The mathematical tool of categories provides a proper setting.7
Indeed, as will be seen later, category theory provides appropriate notions of
continuity, limits and fixed points.
3. Definition: A category K is defined by
i-a class of objects: x,y,. . . ; denoted by obj(K).
ii-a class of arrows (morphisms) between those objects: f,g,. . . ;
denoted by K(x,y) for each x and y in obj(K).
An associative operation called composition that associates to each
pair of morphisms f:x--->y,g:y--->za morphism fg:x--->z,and for every
object x, a morphism i&:x--->x, the identity on x , such that fi&=f
i&g=g
and
.
Note that the object class of a category provides a setting for the
domain of F (defined in section I11 as a collection of strategy sets). We can
define a structure preserving relation between categories.
For a rigorous treatment of category theory, see Arbib and Manes (1975)
and Mac Lane (1971).
www.clevelandfed.org/research/workpaper/index.cfm
4. Definition: Given two categories K and C, a functor F:K--->Cassigns to
Vx E obj(K) F(x)
morphism F(f)
E
E
obj(C),
and to each morphism f
C(F(xl),F(x2)),
E
K(xl,x2) a
in such a way that composition and
identity are preserved:
F(fg)=
(Ff) (Fg)
F(i%)=Fi%.
We can think of a functor F as giving a representation of K in C. Now
we introduce a concept that translates the representation F to another
representation G:K--->C.
5. Definition: Given two functors F:K-->C,and G:K-->C,a collection of
morphisms in C <xn: xF-->xG with x
E
obj(K)>
is a natural transformation
from functor F to G if for all xl x2 in obj(K) and for any f
E
K(xl,x2)
the following diagram commutes, that is, if different paths yield the same
overall function.
I concentrate on (right and left) chains in a category C, then study their
relation to fixed-point concepts. A right chain is an arbitrary sequence
<c,/eO>
of morphisms of the form
www.clevelandfed.org/research/workpaper/index.cfm
Co->C1->C2
->.
...
6. Definition: Given a category K we define its dual (opposite) category KOP
by
obj (kOp)=obj (k)
~'P(a,b)=(b-->a': f
E
K(a,b))
with composition defined by c-->b-->a=c-->a;
identities are the same as K with
arrows reversed.
A left chain in COP is a right chain in C.
7. Examples:
We can readily think of a category whose morphisms are left chains.
Let W be the category with
i-obj(w)=N
ii-Vj&i
E
(all natural numbers).
obj(w),
if jsi, 3 exactly one arrow from i to j
(there are no other morphisms).
If i-->j-->k,for i,j,k E obj(w),
define composition to be the
unique arrow i-->k. Identity arrow is i-->i, for all i20.
The dual wOP is obtained simply by changing the order of arrows: if j>i, there
is exactly one morphism from j to i, i20.
Diagram 2, developed earlier, is an example of left chains. If we can
construct an X such that the above diagram commutes at every level, then we
would have a candidate for a universal mechanism. In diagrammatic form, we
wish to construct
www.clevelandfed.org/research/workpaper/index.cfm
8. Diagram:
with all triangles commuting.
If vo . . .vn are natural transformations, then X would be the limit of
functor F. Under the proper specification, X turns out to be the desired fixed
point. We have motivated the following definitions.
9. Definition: A constant functor Ic:K--->Cis a functor that assigns to
k
E
obj(K) the same c E obj(C),
morphism idk
and to each morphism in K the identity
on k.
10. Definition: Let F:K--->Cbe a functor. A limit of F is an object c
E
C
and a natural transformation u: 1,--->F with the following universal property:
If c'
E
obj(C) such that c'
#
c and ut:IC--->F
is any other natural
transformation, 3 a unique morphism f:c'--->cin C that makes the
following diagram commute tr k E obj(K).
www.clevelandfed.org/research/workpaper/index.cfm
Recall that the objective in this section has been to show how the
concepts of limits and fixed points can be generated outside the realm of
traditional analysis, which can be built only on well-founded sets. So far, a
definition of these terms has been offered using categories (objects and
arrows) and functors. The relation between the limit and the fixed point(s) of
a functor is formalized by the generalized Kleene fixed-point theorem. First,
we must introduce some new concepts
11. Definition: Given x&y
E
obj(K),
f:x-->y is said to be an isomorphism
if 3 a g:y--->xsuch that fg=idy and gf=idx. In diagrammatic form,
commutes.
12. Definition: Given a functor F:K--->K,an object x of K is a fixed point of
K if 3 an isomorphism f:x--->F(x) in K.
13. Definition: A terminal object in a category K is an object denoted by 1
such that V x
E
obj(K),
3 a unique morphism !:x--->l.An initial
object in K is a terminal object in KOP.
14. Definition: A functor F:C-->K is continuous if whenever C,:C,<---C,+~
is a
left chain in C and (U,u) is a limit for <cn>, then (mT,Fu) is a limit for
<FCn>
.
www.clevelandfed.org/research/workpaper/index.cfm
15. Generalized Kleene Fixed-Point Theorem: Let K be a category with an
initial object 1 such that every right chain has a colimit. Then every
continuous functor F:C--->Chas a least fixed point the colimit of the right
chain
. . . 4 - ~ 2 ()11(F)'
-1.
Proof. (see Manes and Arbib [1986], p. 270).
Note that the Kleene fixed-point theorem applies to right chains. But
as indicated in diagram 8 , we are interested in the limit of a left chain.
Theorem 16 establishes a fundamental result of category theory that allows us
to state the dual of the fixed-point.theoremwithout a reference to any proof.
16. Dualitv Principle for Category Theory (Arbib and Manes [1975]):
Let T be any construct defined for any category K. Then the dual of T ,
called COT, is the construct defined for any category K by defining T in KOP
and reversing all arrows.
If T is a theorem true for all categories K, then the dual of T,
obtained by reversing all the arrows of T, is true for all categories KOP, and
thus (since (KOP)OP=K) is true for all categories.
17. Dual: Let K be a category with a terminal object D(x) and such that every
left chain has a limit. Then every continuous functor F:K--->Khas a greatest
fixed point the limit of the left chain
FO(D(x))+
F1(D(x))t---
F2(D(x))-
...+-.
Fn(D(x))+
Fn+l(D(~))....
Stability of the fixed point is the result of it being an
approximation from the iteration process represented by the left chain. The
uniqueness of the greatest fixed point is settled by the following results.
www.clevelandfed.org/research/workpaper/index.cfm
18. Theorem: Limits are unique up to isomorphism.
19. Corollarv: The greatest fixed point of F:K-->K is unique up to
isomorphism.
Note that F may have other fixed points; however, they cannot be obtained as a
limit of the same chain.
20. Proposition: This specification guarantees that the fixed point (if it
exists) is continually dependent on the parameters of the game.
Proof. As a limit X is contingent on the underlying game by the construction
of the left chain.
Manes and Arbib (1986) present a reference for the adaptation of
categorical techniques to computations of data types. Vassilakis (1989, 1990)
provides categorical constructions relevant to economic theory.
www.clevelandfed.org/research/workpaper/index.cfm
111. A "Revised" Nash Demand Game
The previous section showed how the existence of a universal mechanism
reduces to the existence of the fixed point of a functor. I have not
explicitly constructed that functor; nor have I determined its proper domain
and range categories. This section presents an adaptation of the universal
mechanism constructed in Vassilakis (1989). The underlying game consists of
the Nash demand game. Agents simultaneously announce a demand vector xi
E
Xi, the dimension of which is determined by the number of traded goods in that
economy. Every player has an initial endowment ei. A von Neuman-Morgenstern
utility function is defined. If the demand matrix x=(x l...xn) is such that
Cxi 5 Cei, i.e., markets clear, then every agent receives his demand,
thus a utility of Ui(xi).
Otherwise, if Exi > Cei then the game is
played noncooperatively: every player consumes his endowment and receives a
utility of Ui(ei) 5 Ui(xi). The Nash equilibria form the set of demand
matrices yielding Pareto-efficient outcomes.
This specification of Nash equilibria eliminates suboptimal equilibria
similar to the equilibrium arising in the prisoners' dilemma game. However,
the game has multiple equilibria. Every matrix x with the specification
Cxi
=
Cei is Pareto optimal and hence an equilibrium. Players can
suggest different mechanisms to chose among the equilibria by playing a game
over mechanisms. Yet, as argued earlier, it must also be shown that the latter
game yields a solution. Eventually, we are led to an infinite regress. The
construct, presented in Vassilakis (1989), considers an aggregate revision
functor that gives every player the power to suggest a new outcome at every
www.clevelandfed.org/research/workpaper/index.cfm
level of play. Recall that the objective is to extract the existence of a
fixed point of a functor over mechanisms.
Let I be the following category:
Obj(I)=players, denoted by an integer i=l,. . . ,n
K(i,i)=idi, for all i in obj(1).
There are no other morphisms.
Categories with only identity morphisms are called discrete.
Let a collection of strategy spaces be a functor S:I-->K,where K is a
category whose objects are abstract sets and whose morphisms are abstract
input/output programs. A given S(i) specifies player i t s strategy space. One
of the benefits of choosing category I to be discrete is that it enables us to
define the aggregate strategy space as SlxS2x. . . Sn= II Si (X
denotes the product).
I define a mechanism to be a triple (S,f,O), where S= II Si ,
0 E obj(K)
is an outcome space, and f: II Si--->Ois a morphism in K. A
~) A
primitive mechanism can be depicted as a triple ( A , ~ , R with
E
obj (K)
such that
A= II Ai
a:
=
11 [0, Cei
1;
II [0, Cei 1--->Rn,
a(xl,x2, . . . ,xn)=(xl,x2,
. . . , xn)
if Exi 5 Cei
and (el,e2,. . . ,en) if Exi > Cei.
Here the primitive mechanism denotes the play of the Nash demand game (the
underlying game) without cooperation, capturing all the multiple equilibria.
In order to relate the ideas developed so far, the next section introduces
some new concepts.
www.clevelandfed.org/research/workpaper/index.cfm
Definition: The category of functors from I to K , denoted by [I-->K],has as
objects all functors F:I--->Kand as morphisms all natural transformations
between them. In this instance I call - - > the functor space constructor.
Definition: Given categories K and C, I construct the product category KxC
as follows: <k,c>
E
obja(xC> if k
E
obj(K) and c
E
obj (C). A
morphism of KxC is a pair <f,g,> with f a morphism in K and g a morphism
in C. Composition is defined in terms of the composites in K and C:
<f',gfXf,g,>= <f'f,glg>.
Definition: A coproduct is a colimit of a functor F:I--->Kon a discrete
category I. For example, in the category Set, whose objects are all sets and
whose morphisms are the inclusion map, coproduct is the disjoint union. The
coproduct of two objects is denoted by
"+".
Definition: A polynomial functor F:K--->Kis a functor that can be constructed
from constant or identity functors through the use of products, coproducts and
compositions.
Each agent must be endowed with the capability of either proposing to
coordinate in a given mechanism or proposing to coordinate on the proposals in
that mechanism. So an agent's revision functor is defined as
Ri:[I-->K]xK--->KxKby Ri(S,O)=(S',Of), where
O f = [II Si--->0]is a new outcome space
and S'= Ofx[O'x. . .xOf-->O']
is a new strategy space for each player i. The revision functor defines what
each agent can propose. This definition captures the fact that given a game
with strategy space S and outcome space 0, each agent i can simultaneously
www.clevelandfed.org/research/workpaper/index.cfm
make two proposals. The first proposal is a mechanism f
E
O f , that is, i's
proposal on how to coordinate actions on the original game (S,O). The second
proposal is a mechanism that selects one out of n proposals in 0'.
The aggregate revision functor
R:[I-->K]xK--->[I-->K]xK
is defined by R(S,O)=(A,Rn)+(~',O'),
where Sf:I-->Kwith II S'(i)=S1; S'
and 0' are defined as above. A universal mechanism (S,f,O) must be a fixed
point of that functor: (S,O)-(A,Rn)+R(s,O).
The meaning of the fixed point
equation is that a strategy is either primitive or a revision strategy for
each i in obj(I),
where Si-Ai+[O1x. . .x0'-->01] with O1=[II S-->O],
and that an outcome is either primitive or an outcome of the revision
mechanism X-Rn+[II Si--->O].
To satisfy the statement of the functorial fixed-point theorems, a
a category K is needed that satisfies the following:
1. K has limits of the left chains.
2. K has a terminal object.
3. K has polynomial functors, all of which are continuous.
4. K has a functor (called a function space constructor) -->: KxK--->L
defined on two objects x and y in obj(K) by -->(x,y)=[x-->y], such that
- - > is continuous. Note that the morphism space does not belong to K but to
a larger category L of which K is a subcategory. In other words,
L is the
category with the desired function space. However, L has too many morphisms
www.clevelandfed.org/research/workpaper/index.cfm
for [L-->L]to be made into a functor. Thus, I restrict the set of
morphisms in L to K and obtain functoriality (see Manes and Arbib [1986],
p. 313).
To state the main theorem of this section, again, some new concepts
must be identified. I turn to partially ordered sets (posets). A poset can be
seen as a specialization of a category that allows for much insight about
general categories with minimal loss of generality. When posets are regarded
as categories, a monotone map (function) represents the same concept as a
functor.
Definition: A partially ordered set, poset, is a pair (P,R) where P is a set
and R is a binary relation on P, which is a partial order on P. Then the
following axioms hold:
i- Reflexivity: xRx
ii- Transitivity: xRy
A
yRz
+
xRz
iii- Antisymmetry: xRy
A
yRx
-+
xEy.
Note that posets are themselves categories; examples are W and wOP.
Definition: A poset is a domain if it has a least element and if whenever
(xn: n=1,2,3,. . . ) is an ascending chain in P (i.e.,
5 xn+l), then a least
upper bound (LUB) {xn) exists.
Definition: Given domains D and D', let [D-->Dl]be the set of all continuous
functions f:D-->Dl partially ordered by fRg o f(x)Rg(x),
V
x
E
D.
Proposition (Manes and Arbib [1986]): [D-->D1]is a domain under R. I call
[D-->Dl] a function space domain.
Definition: Given domains Dl,. . . ,Dn, define
www.clevelandfed.org/research/workpaper/index.cfm
i- Dlx . . .xDn=(xl,
. . . ,xn)
with xi E D , (xl,...,%) I (yl,...,yn)
iff xiRyi E Di.
ii- Dl+. . . + D ~ = { ~ ) U ( ~ ) X D ~
.u(n)xDnl
U..
where
4 2 ,
V z in Dl+. . .+Dn, while (i ,x)R(j ,y) if i=j and xRy in Di.
Proposition: Dlx . . .xDn and Dl+ ...+ Dn are both domains.
Definition: Categories of Domains
i- Let Domc be the category with
obj (Dom,) =domains
and K(D,D1)=continuous maps.
ii- Let Dom be the category with
obj (Dom)=domains
and K(D,D1)=strict maps.
iii- Let Domadj be the category with
obj (Domadj)=domains
and K(D,D1)=maps having an adjoint.
Remark: Domadj is a subcategory of
Dam,.
Fact: Both Domc and Dom have limits (colimits) of left (right) chains, as well
as an initial (terminal) object.
Fact: Any polynomial functor
Dome-->Dome
is co-continuous and therefore has a
least fixed point.
Proof (sketch). Constant functors and the identity functor are
co-continuous, and so is any composition of co-continuous functors. The
product of co-continuous functors is continuous in closed categories. The
coproduct of co-continuous functors is also co-continuous.
www.clevelandfed.org/research/workpaper/index.cfm
The necessary and sufficient resources are now in place to provide a
category that can capture the universal mechanism I have, so far, been
seeking.
Theorems :
i- D--->[D-->Dlextends to a functor Domadj-->Domadj.
ii- The terminal object in Dom is terminal Domadj.
iii- Given a left chain in Domadj with limit (a,n) in Dom, it follows that
(a,n) is its limit in Domadj.
iv- The functor [D-->Dl is continuous.
v- Every polynomial functor Dom-->Dom maps Domadj into Domadj.
P r o o f . Manes and Arbib (1986), pp. 311-317.
Indeed, by inspection Domadj satisfies d e s i d e r a t a 1-4 enumerated
earlier in this section. However, I have not yet shown the existence of the
fixed point .
Corollarv: (Vassilakis [1989]) A universal mechanism exists.
P r o o f . (S,O) is defined as a fixed point of a functor defined by the
continuity-preserving operations on left-chain functors (the product operation
preserves continuity). The outcome function f: II Si--->Xis arbitrary.
It must still be shown that the transformation of the proposals into
outcomes is well defined.
Corollary: (Vassilakis 1989) If (S,f,O) is a universal mechanism, then there
exists a unique outcome function f' : II S' i+A-->o'+R~ (with S' and 0'
defined as above) that is consistent with f, in the sense of making the
following diagram commute:
www.clevelandfed.org/research/workpaper/index.cfm
X*
g
O'+ 0
where O:S1+A-->S and g : ~ ' + ~ n - -are
> ~ the fixed-point isomorphisms.
Proof. f ~ = ~ - l (
(0
f))is well defined. Note that f' transforms proposals
into outcomes.
Hence, f' extends uniquely to an outcome function on the proposed
revisions of f. This completes the specification of the "revised" Nash demand
game .
So far, I have defined f to be an input/output morphism of K (a
function of Domadj). An explicit specification of f is tantamount to an
explicit specification of the game, but this must be addressed in future
research.
www.clevelandfed.org/research/workpaper/index.cfm
IV. Conclusion
This paper h a s attempted t o show how c a t e g o r y t h e o r y p r o v i d e s t h e
t o o l s f o r s o l v i n g t h e i n f i n i t e r e g r e s s t h a t appears i n t h e s t a t e m e n t of many
social-choice theories.
t h e Nash demand game.
A r e v i s i o n f u n c t o r was c o n s t r u c t e d and s p e c i f i e d on
Solving t h e " r e v i s e d " Nash demand game i s beyond t h e
scope of t h e p r e s e n t p r o j e c t and w i l l have t o be explored i n a n o t h e r p a p e r .
The aim h e r e was simply t o o u t l i n e t h e main d i f f i c u l t i e s f a c i n g s o c i a l - c h o i c e
t h e o r i e s and t o show how c a t e g o r i c a l t o o l s can be used f o r c o n s t r u c t i n g t h e
a p p r o p r i a t e models by p r o v i d i n g a s e t t i n g f o r t h e concepts of c o n t i n u i t y ,
l i m i t s , and f i x e d p o i n t s .
The d i s c o n t e n t w i t h moral philosophy h a s been a r t i c u l a t e d by Williams
(1985).
I n h i s a c c o u n t , t h e d i f f i c u l t i e s a r e r o o t e d i n t h e f a c t t h a t modern
m o r a l i t y t h e o r i e s a r e " . . . g o v e r n e d by a dream of a community of r e a s o n t h a t i s
t o o f a r removed . . . " ( p . 1 9 7 ) .
I n our c a s e , t h e exogenous b a r g a i n i n g
procedures and t h e " n i c e " p r o p e r t i e s they must have i n o r d e r f o r t h e Gauthier
r e s u l t s t o go through
reason.
a r e e s s e n t i a l l y t h e embodiment of t h a t community of
The n o v e l t y i n t h i s paper stems from i t s a b i l i t y t o provide a
c o n s t r u c t i o n t h a t escapes t h e a n a l y s t ' s b i a s e s .
Other p e r t i n e n t problems can be s e t t l e d by t h e same t e c h n i q u e s ; f o r
example, bounded r a t i o n a l i t y and u n i v e r s a l b e l i e f s spaces ( s e e Mertens and
Z a m i r [1985]).
While t h e r e remains much t o be done t o expand t h e boundaries
o f moral philosophy, I hope t o have o f f e r e d a promising approach.
www.clevelandfed.org/research/workpaper/index.cfm
Appendix
This game illustrates how information leakages restrict the set of
feasible mechanisms.
identical.
In this game, agents' information sets are not
I define an incentive-efficient mechanism as an incentive-
compatible mechanism such that there is no other incentive-compatible
mechanism that is at least as good for all agents, and strictly better for at
least one agent, in the truthful equilibrium. The term ex ante refers to a
situation in which agents have not yet observed their types; interim refers to
the case in which agents have observed only their types and not other agents'
types.
Consider the two-agent economy, where an agent is either type a or
type b with equal probability.
Suppose we have three decisions {A,B,C). The
utility of each agent under every decision is self regarding and a function of
his respective type as represented in table 1.
Table 1
Let D be the following decision rule:
D(la,2a)=A,
D(la,2b)=B, D(lb,2a)=C,
D(lb,2b)=B.
Decision rule D selects C only if agent two's type is la. Otherwise, if two is
type 2b, then only decision B is chosen. Rule D is incentive compatible,
www.clevelandfed.org/research/workpaper/index.cfm
which can be confirmed by inspection. For types la, lb, and 2b, it is trivial
to show that an honest reporting is the dominant strategy. Type 2a can either
get B with probability one, by actually reporting his false type, or get A or
C with equal probability by honestly reporting his type. Since the expected
utility of both prospects is identical for type 2a, he is willing to report
his type honestly when D is implemented (under risk neutrality).
Decision
rule D is interim incentive-efficient. However, if agent one knows that he is
type la, then he knows that both he and player two prefer decision A over the
outcome proposed by decision rule D. Thus, agent two would expect (with
probability one) agent one to call for decision A if one was type la.
agent one insists on D then agent two can infer that type one is lb.
If
In this
event, agent two is better off reporting 2b, regardless of his true type, in
order to avoid decision C altogether; decision D's incentive-compatibility
property is thereby destroyed. Because of its simplicity, this example does
not show an even stronger case where an ex-ante incentive efficiency is not
interim incentive-efficient;however, it should be clear that such a case is
possible.
www.clevelandfed.org/research/workpaper/index.cfm
References
Arbib, M., and Manes, E., Arrows. Structure and Functors:
Imperative, Academic Press, New York, 1975.
Crawford, V., "Efficient and Durable Decision Rules:
Econometrica, Vol. 53, No. 4, July 1985.
The Categorical
A Reformation,"
Friedman, J., Game Theory with Application to Economics, Oxford University
Press, New York, 1986.
Gauthier, D., "Justice as Social Choice," in Morality. Reason and Truth, D
Copp and D. Zimmerman, eds., Rowman and Allanheld, Totowa, New Jersey,
1984, pp. 251-269.
Holmstrom, B., and Myerson, R . , "Efficient and Durable Decision Rules with
Incomplete Information," Econometrica, Vol. 51, No. 6 , November 1983.
Kreps, D . , A Course in Microeconomic Theory, Princeton University Press,
Princeton, New Jersey, 1990.
for the Working
- Mathematician, Springer-Verlag, New
Mac Lane, S . , Categories
York, 1971.
Approaches to Program Semantics,
Manes, E., and Arbib, M . , Algebraic
Springer-Verlag, New York, 1986.
Mertens, J.F., and Zamir, S . , "Formulation of Bayesian Analysis for Games of
Incomplete Information," International Journal of Game Theory, Vol. 14,
Issue 1 , 1985.
Rawls, J . , A Theory of Justice, The Belnap Press of Harvard University,
Cambridge, Massachusetts, 1971.
Vassilakis, S., "Economic Data Types," Working Paper No. 252, University of
Pittsburgh, 1989.
. "Functorial Fixed Points. A Non-Technical Introduction,"
Mimeo, University of Pittsburgh, 1990.
Williams, B., Ethics and the Limits of Philosophy, Harvard University Press,
Cambridge, Massachusetts, 1985.
@FedFRASER