330
B385
No. 1700 COPY 2
STX
BEBR
FACULTY WORKING
PAPER NO. 90-1700
The Planning Problem with
Coalitional Manipulation
Bhaskar Chakravorti
QIC
<tf u*
WORKING PAPER SERIES ON THE POLITICAL ECONOMY OF INSTITUTIONS NO. 42
College of Commerce and Business Administration
Bureau of Economic and Business Research
University of Illinois Urbana-Champaign
Papers in the Political Economy of Institutions Series
No. 1 Susan I. Cohen. "Pareto Optimallty and Bidding for Contracts" Working Paper # 1411
No. 2 Jan K. Brueckner and Kangoh Lee. "Spatially-Limited Altruism, Mixed Clubs, and Local
Income Redistribution" Working Paper #1406
No. 3 George E. Monahan and Vijay K. Vemuri. "Monotonicity of Second-Best Optimal Contracts"
Working Paper #1417
No. 4 Charles D. Kolstad, Gary V. Johnson, and Thomas S. Ulen . "Ex Post Liability for Harm
vs. Ex Ante Safety Regulation: Substitutes or Complements?" Working Paper #1419
No. 5 Lanny Arvan and Hadi S. Esfahani. "A Model of Efficiency Wages as a Signal of Firm
Value" Working Paper #1424
No. 6 Kalyan Chatter jee and Larry Samuelson. "Perfect Equilibria in Simultaneous-Offers
Bargaining" Working Paper #1425
Jan K. Brueckner and Kangoh Lee. "Economies of Scope and Multiproduct Clubs" Working
Paper #1428
Pablo T. Spiller. "Politicians, Interest Groups, and Regulators: A Multiple-Principals
Agency Theory of Regulation (or "Let Them Be Bribed" Working Paper #1436
Bhaskar Chakravorti. "Asymmetric Information, 'Interim' Equilibrium and Mechanism
Design" Working Paper #1437
Bhaskar Chakravorti. "Mechanisms with No Regret: Welfare Economics and Information
Reconsidered" Working Paper #1438
Bhaskar Chakravorti. "Communication Requirements and Strategic Mechanisms for Market
Organization" Working Paper #1439
Susan I. Cohen and Martin Loeb . "On the Optimality of Incentive Contracts in the
Presence of Joint Costs" Working Paper #1445
Susan I. Cohen and Martin Loeb. "The Demand for Cost Allocations: The Case of Incentive
Contracts Versus Fixed-Price Contracts" Working Paper #1455
No. 14 Jan K. Brueckner and Kevin M. O'Brien. "Modeling Government Behavior in Collective
Bargaining: A Test for Self-interested Bureaucrats" Working Paper #1481
No. 15 Jan K. Brueckner. "Estimating a Bargaining Contract Curve: Prior Restrictions and
Methodology" Working Paper #1490
No. 16 Peter C. Reiss and Pablo T. Spiller. "Competiton and Entry in Small Airline Markets"
Working Paper #14 97
No. 17 Pablo T. Spiller. "A Note on Pricing of Hub-and- Spoke Networks" Working Paper #14 98
No. 18 Larry DeBrock. "Joint Marketing Efforts and Pricing Behavior" Working Paper #1500
No. 19 Frank A. Wolak and Charles D. Kolstad. "A Model of Homogenous Input Demand Under Price
Uncertainty" Working Paper #1502
No. 20 Susan I. Cohen. "Reputation, Intertemporal Incentives and Contracting" Working Paper
#1511
No. 21 Lanny Arvan and Antonio Leite. "A Sequential Equilibrium Model of Cost Overruns in
Long Term Projects" Working paper #1514
No. 22 Jan K. Brueckner and Pablo T. Spiller. "Competiton and Mergers in Airline Networks"
Working Paper #1523
No. 23 Hadi S. Esfahani. "Reputation, Product Quality, and Production Technology in LDC
Markets" Working Paper #89-1525
No. 24 Hadi S. Esfahani. "Moral Hazard, Limited Entry Costs, and 'Introductory Offers'"
Working Paper #89-1526
No. 25 Bhaskar Chakravorti. "Mechanisms with No Regret: Welfare Economics and Information
Reconsidered" Working Paper #89-1527
No. 26 Susan I. Cohen. "Implicit Cost Allocation and Bidding for Contracts" Working Paper
#89-1558
No. 27 Rafael Gely and Pablo T. Spiller. "A Rational Choice Theory of the Supreme Court"
Working Paper #89-1559
BEBR
l
FACULTY WORKING PAPER NO. 90-1700
College of Commerce and Business Administration
University of Illinois at (Jrbana-Champaign
November 1990
The Planning Problem with Coalitional Manipulation
Bhaskar Chakravorti
Department of Economics
University of Illinios at (Jrbana-Champaign
Champaign, IL 61820
»
This research was partially supported by a grant from the Investors in Business Education. I am
grateful to Lanny Arvan and Charles Kahn for their comments.
Digitized by the Internet Archive
in 2011 with funding from
University of Illinois Urbana-Champaign
http://www.archive.org/details/planningproblemw1700chak
I
ABSTRACT
We study the problem of devising a planning procedure for the provision of an efficient level of a public
good, while allowing for the surplus distribution rule to be dependent on the level of the public good.
In general, we study time-dependent surplus distribution. The MDP family of procedures would be
subject to manipulation via pre-play communication among coalitions of agents in such situations. We
begin with Truchon's (1984) elegant non-myopic MDP procedure and provide a new procedure that
exhibits finite, monotone convergence to Pareto- efficiency in Subgame-Perfect Coalition-proof
equilibrium. This procedure also implements any "regular" surplus distribution rule that is dependent
on the public good level. The solution concept of Subgame-Perfect Coalition-proof equilibrium, is an
extension of the semi-consistency definitions of Kahn and Mookherjee (1989) of Coalition-proof
equilibrium for infinite- strategy games. The coalition-proofing device given is more generally
applicable.
JEL Classification: 026,027.
Keywords: Planning procedure, surplus distribution, convergence, implementation, Subgame-Perfect
equilibrium, Subgame-Perfect Coalition-proof equilibrium.
.
1. INTRODUCTION
Iterative planning procedures play a central role in the literature on
efficient public goods provision problems with informational asymmetry
between the Center and consumers. The MDP (Malinvaud (1971, 1972), Dreze
and Vallee Poussin (1971)) procedures and their descendants have succeeded
in resolving the incentive problem under the assumption of Nash equilibrium
behavior.
The purpose of this paper is to re-examine the planning problem in
environments where the Center is interested in distributing the social
surplus as a function of the available amount of the public good and, in
general, as a function of time. We argue that this requirement raises the
possibility of pre-play communication among coalitions of agents.
Manipulation by such coalitions can cripple planning procedures that are
designed under the assumption that strategic behavior is unilateral.
Our starting point is the elegant procedure of Truchon (1984). It has
some of the strongest properties within the the MDP family of procedures.
Truchon's modification of the MDP procedure achieves (in Subgame-Perfect
equilibria of the induced game) efficiency and monotone finite convergence
in quasi-linear economies with non-myopic strategic behavior. In the
Truchon procedure, as in most other procedures in the MDP family, the
surplus distribution rule is constant over time. For a wide variety of
reasons, the Center may want to relax this requirement. Time-dependency of
the surplus distribution rule introduces the possibility of coalitional
manipulation of the procedure.
We shall first provide some examples to motivate our interest in such
distribution rules. Second, we shall give the intuition underlying the
incentives for coalition formation.
Suppose that the Center intends to distribute the surplus arising from
the procedure at each point in time as a function of the currently
available quantity of the public good. An example of such a situation
would arise if the public good were a facility being provided to benefit
primarily lower income individuals. When the amount available of the
facility is small, the Center may want to divert a larger proportion of the
surplus to those with low incomes and eventually phase out the special
treatment as the facility grows.
Consider two other examples. A planning procedure typically takes a
considerable length of time to converge. The Center may want to retain the
freedom to vary the surplus distribution over time so as to give additional
support to different groups of agents at different points in time.
Moreover, if the plan were to be terminated prematurely (as many plans
often are) and if the Center's notion of equity is a function of the level
of the public good available, then it must be concerned about equity of the
division at each point in time and not just at the "final" distribution
(i.e. after convergence to an efficient allocation).
When the distribution rule is non-constant over time, the Truchon
procedure may be manipulated by coalitions. Truchon modifies the MDP
procedure by introducing a minimum threshold level of instantaneous
adjustment in the public good, e. A critical feature of Truchon's proof of
existence of a Subgame-Perfect equilibrium is the construction of a
2
strategy profile that generates a surplus of c everywhere along the path
to convergence. He shows that any single consumer's message to the Center
does not affect any other consumer's direct contribution to the financing
of a given quantity of public good. Given this, Truchon argues that if a
2
consumer had two alternative announcements, one that generates surplus e
2
at each instant and another that generates a surplus other than c , if both
announcements lead to the same public good level eventually, then the
consumer is no better off by choosing the second announcement. The
intuition behind this is simple: if I cannot affect anybody else's taxes
and the eventual quantity of the public good, given a fixed surplus
distribution rule, increasing the surplus would only reduce the amount of
private good that I will eventually have. Lowering the surplus below e
would only terminate the procedure since the adjustment in the public good
would fall below the minimum e.
Truchon's arguments critically depend on the fact that a deviation by
one agent does not affect the contributions of any other. If the surplus
distribution rule varies over time, there may be an incentive for
coalition-formation. I can make a deal with you whereby I increase my
2
contribution (and raise the surplus above e ) in periods in which the
distribution rule favors you and you agree to do the same in periods in
which the distribution rule favors me. We may both be made better off if
sufficiently large portions of the surplus are diverted to us in periods
when we are favored by the distribution rule. Since, the procedure
operates in continuous-time, for certain types of time-dependencies of the
distribution rule, we could make such agreements self -enforcing by
constructing an infinite sequence of "punishments", whereby I would reduce
my contribution in periods in which you are favored by the distribution
rule if you had defected from our agreement in the past and you agree to do
the same thing... and so on. The intuition underlying the interlocking
system of punishments is similar to that employed in establishing the Folk
Theorem. Under such agreements, it is conceivable that Truchon's results
would not hold.
We develop a coalition-proof procedure. Our procedure inherits all
the desirable properties of the Truchon procedure. The convergence,
incentive and existence properties are shown to hold in Subgame-Perfect
Coalition-proof equilibria of the induced game. Moreover, the
procedure implements a wide class of "regular" distribution rules.
The notion of Subgame-Perfect Coalition-proof equilibrium is obtained
as an extension of the semi-consistency concept of Kahn and Mookherjee
(1989), which builds on earlier definitions of coalition-proofness
appropriate for finite games by Bernheim, Whinston and Peleg (1987) and
Greenberg (1986, 1989). Since we deal with games that have non-finite
strategy spaces, the semi-consistency approach is more appropriate for our
purposes.
The coalition-proofing device employed in the paper is quite general.
Even though our focus is on the Truchon procedure, the same technique can
be used to coalition-proof any planning procedure in the MDP-class that is
susceptible to coalitional manipulation.
Section 2 contains the model. Section 3 defines the notion of
coalition-proofness used in the paper. Section 4 introduces the planning
procedure. Section 5 contains the results and the final section concludes.
2. PRELIMINARIES
We consider an economy with the following characteristics. There is a
set of consumers, N = {l,...n} with n > 1, a private good and a public
good. The consumption of the private good by consumer i is denoted x and
the total quantity of the public good produced is denoted y, with Y = IR
denoting the domain of possible public good levels. In the sequel, we
shall write the profile (g ) as ? and {g ) as g . Each i e N is
r 1 1€N 6 6J J€N\0> -I
2
characterized by a pair (u , w ) where u : R -> R is i's utility function
l i l *
and o) € R is i's initial endowment of the private good. The initial
endowment of the public good is denoted y(0).
We assume the existence of willingness-to-pay functions v i Y -> R and
a cost function c: Y -> R for the public good satisfying several fundamental
2
assumptions. For all i € N, for all (jc , y) € R , u (x , y) = x + v (y)
i.e. the utility functions are linear in the private good. For all i € N,
v is strictly concave, c is strictly convex and both v and c are
i i
continuously differentiable. In addition, for all i € N, and all y € Y,
dv (y)/dy > 0, v (0) = 0 and dc{y)/dy > 0, c(0) = 0.
In the sequel, we use a (y) to denote dv (y)/dy and £(y) to denote
dc(y)/dy which are to be interpreted as the "true" marginal willingness to
pay by i and the marginal cost of producing a level y of the public good.
The set of feasible allocations is Z = <z = (*:, y) € R : Y [u> -
x ) = c(y)>. z € Z is Pareto-efficient if there exists no z' € Z such that
for all i € N, u (z') a u (z ) with strict inequality for some i. z € Z is
1 i 1 i
individually rational if for all i € N, u (z ) £ u (u , y(0)). A necessary
and sufficient condition for z = Oc, y) to be Pareto-efficient is:
T a (y) s £(y) and (T a (y) - |3(y))y = 0.
In the sequel, we shall denote a Pareto-efficient level of public good
PE PE
as y . Given the assumptions on the economy, y exists and is unique.
The utility functions are known to the consumers and the Center cannot
observe them. The cost function associated with production of the public
good is observable to the consumers and the Center.
A planning procedure is a dynamic mechanism which accepts messages
from the consumers and recommends an adjustment in the allocation of
resources at each instant in time, t € [0, oo). z(t) = (x(t), y(t)) denotes
the levels of x and y at the instant t. With a slight abuse of notation,
we shall write a (y(t)) and ft(y(t)) as a (t) and £(t) respectively. For
PE
the rest of the paper, we shall assume that 0 < y(0) < y This
assumption can be dropped without affecting the results in a substantive
manner (refer to the concluding section for a discussion).
Let A denote the interior of the (n - 1) dimensional unit simplex.
Given that a planning procedure generates a surplus during its
operation, let <p : Y -> A be a surplus distribution scheme which specifies a
division of the surplus depending on the existing level of the public good.
A procedure T induces a differential game, denoted T{T). The state of
the game at t is z(t). The strategy space for consumer (or player) i, S ,
is the space of rules that determine the messages sent by i at each t. If
T stops at time T (using an overdot to denote the time-derivative, y(m(T) =
0), with ziT) as the realized allocation, then the payoff to consumer in
the game TCP) is u (z(D). In the interim, at any instant t € [0, T], if
the allocation realized by T is z(t), we have a proper subgame of V[T).
A Nash equilibrium (NE) of r(T) is a profile s € x S such that any
i€N
unilateral deviation by any i € N to s e S does not improve i's payoff.
s is a subgame- perfect equilibrium (SPE) of TCP) if for every proper
subgame of T(!P), its restriction to the subgame is such that any unilateral
deviation by any i € N to s e S restricted to the subgame does not
improve i's payoff in the subgame.
We shall also consider the possibility of pre-play communication among
coalitions of consumers and deviations from equilibrium by such coalitions.
The solution concept employed will be a variation on the notion of
"Coalition-proof" equilibria. This requires some additional structure,
which is presented in the next section.
3. COALITION -PROOF NESS
This section presents the equilibrium concept that will be used to
find a solution to the game induced by a planning procedure. We assume the
possibility of pre-play communication and the formation of
(possibly non-binding) agreements among coalitions of consumers.
The solution concept is a derived from that of Coalition-proof Nash
equilibrium (CPE) introduced by Bernheim, Whinston and Peleg (1987). We
shall employ a variation, due to Kahn and Mookherjee (1989), that is
appropriate for games with infinite strategy spaces. An added advantage of
this version is that the definition is non-recursive (unlike that of
Bernheim, Whinston and Peleg (1987)) and is based on a (simpler)
consistency approach due to Greenberg (1986, 1989). By extending Kahn and
Mookherjee's work, we shall define a subgame-perfect modification of their
semi-consistent CPE.
Given a planning procedure T, fix a proper subgame V of TCP). V is
summarized as a triple <N> S, v>, where N is the set of players, S is the
joint strategy space in the game TCP) and v: S -» 1R is the payoff function
in the subgame with v(s) = v(s) if s and s are identical in the subgame.
An agreement among a subset of players is a pair (s, Q) where s € S and Q Q
N. Let 4{D denote the set of all such agreements, given the subgame T.
An agreement is interpreted as a specification of the strategies adopted by
the parties to the agreement, given the strategies fixed for all other
players.
(s', Q') € 4(T) trumps (s, (?) € 4{D in the subgame I" if
(i) (?'£(?
(iii) Vj * Q', s' = s and
J J
S
(iv) Vi € Q\ v (s') > v (s).
r r r
A semi-consistent partition of 4iT) is a triple {G , B , U } where the
three elements of the partition are defined as follows:
r r
G is a set of good agreements in 4{V) defined by G = {(s, Q) € 4{T):
[3(s\ Q') € 4{T) such that (s\ Q') trumps (s, Q) in the subgame r] =*
[(s\ Q') € Br]>.
r r
B is a set of bad agreements in 4(T) defined by B = {(s, (?) e j4(D:
r
BCs', Q') € G such that (s\ (?') trumps (s, Q) in the subgame T}.
r r
U is a set o/ ugly agreements in j4(D defined as the complement of G
u Bf in ^(D.
Kahn and Mookherjee (1989) have shown that such a partition exists and
is unique for any T.
Next, consider the set of all agreements in the game TOP), denoted 4,
and three subsets of j4, denoted §", S, 11.
§■ is the set of perfectly good agreements defined by ^ = <(s, Q) e 4:
r
(s, Q) € G for every proper subgame D.
£ is the set of perfectly bad agreements defined by S = {(s, Q) e 4:
r
(s, Q) € B for at least one proper subgame D.
V. is the set of perfectly ugly agreements defined as the complement of
^ vj S in 4.
The following result shows that {§, S, V.) constitutes a partition of
4. In addition, such a partition is also unique. This forms the basis for
defining our equilibrium concept.
LEMMA I: {*§ , B, U} is a partition of 4. Such a partition of 4 exists and
is unique.
Proof: First, we shall show that {§ , S, XL} is a partition of 4. Suppose
otherwise. By definition, S* u S u U = *4 and 1i n (§ u S) = 0. Hence, we
must have & r\ *B * 0. Choose (s, Q) € & n 23. (s, Q) € ^ implies that for
r
every subgame T, (s, Q) € G . (s, (?) € S implies that for some T, (s, (?) €
r
B . We obtain a contradiction, since by Kahn and Mookherjee's (1989)
r r
results, for every T, G r\ B = 0.
The existence of the partition {&, £, 1i> follows from the construction
r r r
of {G , B , U > given in Kahn and Mookherjee (1989) for any T.
To prove uniqueness, suppose that there are two partitions {^, 8, 12}
and <^', £*, tO of 4. By the results in Kahn and Mookherjee (1989), for
r r i\
every proper subgame T, {G , B , t/ > is a unique semi-consistent partition.
r
(s, (?) e !*, implies that in every proper subgame F, (s, (?) € G and hence
(s, (?) € if'. Similarly, the converse is true. Thus, !* = !*'. Also, (s, (?)
r
€ £ implies that for some proper subgame T, (s, Q) € B . But then (s, (?) e
£'. Again, the converse holds analogously. Hence £ = £'. ■
r r r r
Next, we shall partition the set U into {U , (/ , [/ >, where the
G B C
three elements of the partition are defined as follows:
r r
U is a set of almost good agreements in 4(T) defined by U = {(s, (?)
G G
r r
e U : [3(s\ <?') € U such that (s\ <?') trumps (s, (?) in the subgame T] =>
Us', <?') € UTB]}.
r r
£/ is a set of almost bad agreements in 4(D defined by U = {(s, (?) €
B B
UT: \Q\ > 1 and 3(s', <?') 6 (/r with | <?* | =1 such that (s', <?') trumps (s,
(?) in the subgame D.
r r r r
U is the complement of U u U in U .
c K G B
Finally, let 1i be the set of perfectly almost good agreements defined
G
r r
by U = <(s, (?) € i4\^: (s, Q) € G u [/ for every proper subgame D.
G G
By definition, U Q U.
G
10
A sub game- per feet coalition-proof equilibrium (SPCPE) of TCP) is a
strategy profile such that (s, AO e If u XL .
G
The perfectly good set of agreements has an internal and external
consistency in every proper subgame which justifies its inclusion in the
desirable set of solutions. In any proper subgame, an agreement in this set
cannot be destroyed except by some agreement which is not a credible threat
since the latter will itself be destroyed by another good (and, therefore,
credible) agreement. In the same spirit, we also admit agreements that are
perfectly "almost" good as solutions. These agreements have the property
that in any proper subgame, they are either good or are trumped only by
agreements which are almost bad. An almost bad agreement made by a
coalition does not pose a credible threat to any other agreement since it
is subject to a unilateral deviation by a member of the coalition. Even
though this deviation may be deviated from, it is hard to imagine that a
player will keep an agreement he/she has made with other players when there
exists an opportunity for the player to benefit from some deviation. Any
threat to the first unilateral deviation also poses a threat to the
agreement the player has made with others. An almost bad agreement is
inherently unstable, hence an agreement that is threatened only by such
unstable agreements may be expected to survive.
An SPCPE is also an SPE. This can be seen by observing that an SPE is
an agreement (s, N) € 4 such that in every proper subgame T, (s, N) is not
trumped by any agreement in 4(T) involving a single-player coalition.
A case can be made for including all perfectly ugly agreements in the
solution as well, simply because they are not perfectly bad. However, we
choose a stronger definition of an equilibrium and prove existence of such
equilibria. In addition, every NE (and, therefore, every element of a
11
superset of any weakening of a coalition-proof equilibrium) is shown to
have the desirable objectives of Pareto-efficiency, individual rationality
and <p-equitable distribution. Hence, a weaker definition of
coalition-proofness is unnecessary.
4. THE PROCEDURE
In this section, we shall present a planning procedure whose objective
is to realize a Pareto-efficient and individually rational allocation of
resources and to re-distribute the resulting surplus. The surplus
distribution must be consistent with the Center's equity objective,
summarized by a distribution scheme <p. In the procedure below, we
introduce a function 5: [0, <») -» A which specifies a division of the
surplus at each instant in time. For every choice of 5, we have a planning
procedure T[8). We shall show in the following section that 5 may be
taylored a priori by the Center to "implement" the desired objective <p in
equilibria of the game induced by the procedure.
The planning procedure, !P(<5), and its induced game rCP(<5)) is defined
as follows.
Let each consumer choose the functions W : Y -» R, A : Y -» A and cr : Y
ll i
-» {1, 2,...}, where W is continuously differentiate. Each i € N has a
message at every instant t € [0, «), m (t) = (a (y(£)), X iy(t)),
cr (y(t))), written, with slight abuse of notation as (a (£), A.(t), o\ (£)),
where a (t) = dW (y{t))/dy, X (t) € A and <r (t) € {1, 2, ...}. The
i 11 i
time-path of messages (m (t)) _ is written m . M is the message space
for i, with M it) denoting the message space at time t.
Each consumer's message includes an announcement such that for some
12
real-valued function of y in the class C , the announcement at each instant
t is the derivative of the function evaluated at y(t). This function may
or may not be equal to v for each i. In addition, each consumer also
announces an element in the (n - l)-dimensional unit simplex and a strictly
positive integer. The announcement A is written as (A , A ,...An). AJ
may be interpreted as consumer i's opinion on the proportion of the tax
burden that consumer j should bear. This message space is designed by the
Center. If a consumer chooses to participate in the planning process,
he/she commits to sending messages drawn from the specified message space.
The planning procedure T{5) is given below. At every £, the space of
message profiles M(£) = x M (£) is partitioned into three subsets
1€N
containing messages that satisfy one of three cases. Depending on which
case the message profile satisfies, one of the alternative sets of
differential equations applies.
For all t € [0, oo) and m(t) = (a(t), A(t), <r(t)), let K(m(t)) = {i €
N: V j € N, <r (t) £ cr (£)>. We consider three cases:
i j
Case A: There exists k € N such that
(i) Vi, j € N\{k), a (t)/a (t) = \l(t)/X}(t) and
(ii) Vi e N\{k>, a- it) = 1.
l
Case B: At least one of the conditions for Case A is not met and | K(m(t))
= 1.
Case C: At least one of the conditions for Case A is not met and | K(m(t))
> 1.
For all t € [0, oo), given an initial position (x(0)> y(0)) and m(t)
(ait), A(t), <r(t)h
13
In every case, given e > 0,
y(m(t)) =
f [ ait) - /3(t)
if I^ap) - W) a e and
lcN 1
in some arbitrarily small neighborhood of t.
otherwise
For all i € N, given 5: [0, oo) -» A,
If m(t) satisfies either Case A or Case C, then
x(m(t)) = - a (t)y(mf t» + 8 m\y0n(t))f
If m(t) satisfies Case B, then
xim(t)) = - a(t)y(m(t)) + [y(m(t))V
x (m(t)) = - a (t)y(m(t))
if K(m{t)) = {i}
if Kimit)) * {i>
The basic construction of the procedure is as follows. At any
instant, a message profile may satisfy the conditions of one of three
cases. If there are a - 1 consumers whose announcements of a and A meet
the proportionality condition (i) above and whose integer announcements are
equal to one, then Case A is met. If Case A is not met and no consumer
announces a higher integer than all of the others, then Case C is met.
Otherwise, we have Case B. If the message profile satisfies either Case A
or C, the Truchon procedure is applied. The public good is adjusted
according to the MDP rule provided that the difference between the
aggregate of the a-announcements and the marginal cost is at least equal to
a threshold c. Otherwise, under Case B, the public good is adjusted using
Truchon's algorithm. However, the consumer who announces the maximal
integer is given the entire surplus equal to [y(t)l at t.
14
The procedure T(8) induces a differential game, denoted rCP(S)). The
(closed loop) strategy space in TOP) for consumer i, S t is the product of
the class of C functions from Y to R and the class of functions mapping Y
to A X U, 2,...}.
REMARK: In light of the restriction on the strategy space in the game TCP)
which requires that a consumer's a-announcement at every t should be the
derivative of a real valued C function of y evaluated at y(t)t our (and
Truchon's) notion of SPE is a little different from the standard concept.
To check for subgame perfection of a candidate strategy list, s, we check
for optimality even when the restriction of s to a particular subgame is
inadmissible because of the restriction on the strategy space. This
definition preserves the fundamental spirit of backwards induction: at any
£, s is i's best response to s , hence, at any time prior to t, there is
no reason for i to play a strategy that makes s inadmissible in future.
The normative properties of the procedure can be given in two parts.
The first is a minimal desideratum. It requires that the procedure have at
least one equilibrium with the desired properties. The second part is
stronger and requires that the desirable properties be true in every
equilibrium.
T{8) achieves Pareto-efficiency, individual rationality and
<p-equitable distribution if:
there exists an SPCPE of T(iP(5)), in which we have monotone convergence to
a Pareto-efficient allocation in finite time, say T, and at every t € [0,
T], 8{t) = <piy(t)).
T{8) implements Pareto-efficiency, individual rationality and
<p-equitable distribution if it achieves these properties and
15
in every SPCPE of TCPid)), we have monotone convergence to a
Pareto-efficient allocation in finite time, say T, and at every t e [0, T],
6(t) = <p(yit)).
5. RESULTS
In this section, we show that the procedure introduced in the previous
section has the desired normative properties, provided a regularity
condition on the distribution scheme is satisfied. This condition is
defined as follows. It ensures that an individual accumulates surplus in a
smooth manner over time.
A surplus distribution scheme (p is regular if for all i € N, there
exists a continuously dif f erentiable function $ : Y -» R such that <p (y) =
i i
d$ {y)/dy. With slight abuse of notation, we shall write <p(y(t)) as (pit).
THEOREM 1: Assume that <p is regular. There exists 5 such that the game
r(T(8)) achieves Pareto-efficiency, individual rationality and (p-equitable
distribution.
Proof: Define 5: [0, ») -> A by 5(f) = <p{y(0) + cdt) for all V € [0,
oo). Choose s = (W ', A, <r) such that the following conditions hold for all t
€ [0, oo), where m is the message profile corresponding to s:
Vi e N,
and
dW (y(t))/dy s *(t) + 6 (t)e
1 i i
£ dW (y{t))/dy - &(t) = c.
16N
whenever possible
dW (y(t))/dy = a (t) + 5 (t)e
otherwise.
16
Vic e N, \a) = [dWk(y(t))/dy]/[£ dW(yit))/dy],
<r (t) ■ 1.
i
By construction, m(t) satisfies Case A in every t e [0, oo). The first
component of each consumer's strategy is identical to the strategy
constructed in Truchon's (1984) Theorem 1. By the same theorem, given that
under Case A, the outcome of our procedure follows that of Truchon, T(8)
PE
converges to y in finite-time. Also, by construction of s, we have
dW (y(t))/dy ^ a. (t) + S (t)e for all i e N and t prior to convergence.
Since the left hand side of the inequality is the tax paid by i and the
right hand side is the utility gain in terms of the private good, we have
monotonicity. Also, it may be checked that in every t prior to
convergence, y(m(t)) = e. By construction of 5, the procedure achieves
<p-equity.
Next, we need to show that the strategies given above constitute an
SPCPE.
By construction of Case A, any unilateral deviation from m by agent i
to m* is such that (m'(t), m (£)) also satisfies Case A in every t € [0,
oo). Also, by construction of the procedure, the surplus distribution at
each t is unaffected by the strategies played in the game . Hence, by
Theorem 1 of Truchon (1984), s is an SPE of FCPid)). Next, we need to check
that s is also an SPCPE.
There are two possibilities to consider:
(i) there exists no agreement that trumps (s, N) in any subgame, in which
It is for precisely this purpose that we choose to distribute the surplus
in the procedure using a rule 5, rather than directly using <p. The image
under <p is affected by the strategies chosen in the game.
17
case (s, N) € S"; and
(ii) otherwise.
Suppose (ii) is true.
Choose a proper subgame of rOP(S)), say T, that begins at time T and
is', Q) € d(D such that (s, N) is trumped by (s\ Q) with |<?| > 1. By
Pareto-efficiency of the outcome under s, Q * N. Let m' be the message
profile corresponding to s*. Also, choose I, a non-degenerate sub-interval
• •
of [T, oo) in the subgame such that u (m(t)) * u (m'(t)) for some q € Q and
q q
all t € I. Let m'(£) = (aYt>, \'(t), <r'(£)) for all £ € I. We
consider two alternative possibilities:
(I) in almost every t e I, K(m'{t)) = {q};
(II) otherwise.
If (II) is true, there are two further possibilities to be considered:
(Il-a): (I) is not true and m'(£) satisfies Case A for all t in a
non-degenerate subset V of I: In this case, for each t € I\ a'{t) *
i
• •
a (£) for some i € Q, otherwise we would have u im(t)) = u (mYt)). Thus,
1 q q
\'k(t)/\'l(t) * a'(t)/a'(t) for some k * <?.
k k k 1
(Il-b): (I) is not true and m'(t) does not satisfy Case A for all t in
any non-degenerate subset V of I.
Consider is", {j}) € jd(D such that j € Q\{q} if (I) is true and j = q
if (II) is true. Let the message corresponding to s" be m" = (a", X", cr")
where (a", A") = (a', A'), o-" = <r* and (r"(t) > <r"(t) for all £ € N\{j)
~i J J '
and all £ € I. In every case (I) or (Il-a) or (Il-b) above, by
construction, m"(£) satisfies Case B, with K(m"(t)) = {j)in every £ € /. j
is guaranteed the entire surplus under Case B at each £ € 7. j is made
better off by this deviation, given that for all £ € I, S (£) < 1 and given
strict monotonicity of preferences. Thus, is", {j}) trumps (s', Q) in the
18
r r
subgame T, which implies that (s\ Q) € B u U . Since this argument holds
D
for all proper subgames T and all (s\ Q) € 4(T), such that (s\ Q) trumps
(s, N) in f, we conclude that is, N) € !* u V. . ■
REMARK: Observe that all the subsequent results given below would be true
if we were to use NE as our equilibrium concept. Hence, these results are
robust to a weakening of the definition of SPCPE.
THEOREM 2: For all 8: [0, to) -» A, T(8) implements individual rationality
and Pareto-efficiency.
Proof: From Theorem 1, we know that T(8) achieves individual rationality
and Pareto-efficiency. Implementation of individual rationality follows
from the fact that no consumer will choose a strategy in an NE that makes
him/her worse off than he/she was at t = 0.
To check for implementation of Pareto-efficiency, suppose otherwise,
* * *
i.e. Ti.8) terminates under an NE at an allocation z = (x , y ) such that
y * y . Thus,
I a (y*) - 0(y*) * 0. [11
i€N
Given that the termination time is T, we must have
and for all V > T,
X a(T) - 0(7) = e. [2]
i€N
£ a (f) - 0(f) < e.
i€N
Let the message profile corresponding to the NE be m. m(T) must satisfy
either [31 or [4] and [5] tyelow, otherwise the marginal contribution of
each consumer would not equal the marginal utility gain to the consumer —
a pre-condition for optimality of a message in an NE. The left hand sides
of the equations below give the marginal contribution of the consumers and
19
the right hand sides give the marginal utility gains. If m(T) satisfies
Case A or Case C, we must have
Vi € N, a {T) = a (y*) + 5 (T)e [3]
If m(T) satisfies Case B, we must have
given Kimit)) = {k>, a (T) = a (y*) + e [4]
k k
and
Vi e N\{k>, a^T) = a (y*) [51
In each case, we have
lam = J> (y*) ♦ e [61
j€N j€N
PE
However, given that 0 < y(0) < y , [11, [2] and [6] are incompatible.
Hence, we have a contradiction. ■
Next, we prove a crucial result.
LEMMA 2: If s is an NE of TCP(S)) for some S and T is the termination time
of T[8) under m, the message profile corresponding to s, then for any
non-degenerate interval I Q [0, T), there does not exist k e N such that
K(m(t)) = (k) for every t € I.
Proof: Let m = (a, A, <r) denote the message profile corresponding to s, an
NE for the game TCP(8)) with T as the termination time under m and let I be
a non-degenerate sub-interval in [0, T). Suppose that K(m(t)) - {k} for
all t € I. For any t € I, there are two possibilities to be considered.
(a) m(t) satisfies Case A. Then
(i) Vi, j € N\{k}t a (t)/a (t) = \\t)/\\t) and
i j i i
(ii) Vi € W\0c>, <r{t) = 1.
l
(b) m(t) satisfies Case B.
In either case, consider a deviation by i € N\{k) to m = (a , X , <r )
i ill
20
such that a. - a. and X - X . <r (£) is such that for all j € N\{i} and
i i i i i J
all t 6 I, <r (t) > a- (t>. By definition, we have K(m (i), m (£)) = <i>
for all t € I. For all £ € I, since K(m(t)) = {k}, we have <r (£) > <r (t)
k j
for all j e N\{i, k}. Hence, by construction, (m (£), m (£)) satisfies
Case B for all t € J.
By the outcome rule associated with Case B, in either one of the
possibilities above, i obtains the entire surplus in every t e I by
deviating unilaterally from m. Given that 5 (•) < 1 and given strict
monotonicity of preferences, i is strictly better off after the deviation.
Hence, we have a contradiction with the assumption that s is an NE. ■
Given this lemma, Case B is applicable in an NE only over a time
interval that has measure zero. Under either Case A or Case C, the
procedure T{8) yields the same outcomes as the Truchon procedure.
The next lemma follows as a corollary of Lemma 2 in Truchon (1984).
LEMMA 3: Fix some i € N, s , s' € S and s € X S and let m and m'
l i 1 -1 j€N j
denote the message profiles that correspond to s and (s' , s ). Suppose
CP(8)) converges to y under m and m\ Let T and T be the termination
times under m and m' respectively. If
(i) K(m'(t)) * {i} at almost every instant prior to 7"
(ii) y(m(t)) = c for all t € 10, T)
(Hi) for some non-degenerate interval I in [0, T'), y(m'(t)) > c for all t
e I,
then i is strictly worse off playing s' as opposed to s .
LEMMA 4: In each NE of F(T(8)), if T is the termination time of T(8) under
21
the NE, then for almost every t € [0, T), y(t) = e.
PE
Proof: From Theorem 2, we know that the outcome under every NE is y . Fix
an NE s such that (given that m is the message profile corresponding to s)
P(5) terminates at time T under m and for some non-degenerate interval, I,
in [0, T), we have y(m(t)) > c for all t € I. For any i, there is a
unilateral deviation to s' such that the resulting message profile (m\
l i
• PE
m ) satisfies ybn'it), m (t)) ■ e for all t prior to attaining y and
• PE
y{.m\{t), m (£)) = 0 thereafter. Hence, the procedure converges to y
under (m\ m ). By Lemma 2 above, we know that m(t) cannot satisfy K(m(t))
■ {i> for almost every t prior to T. By Lemma 3 above, i strictly prefers
s* over s . This contradicts the assumption that s is an NE. ■
Thus, we have the following result.
THEOREM 3: There exists 5 such that T(8) implements <p.
Proof: Since in every NE and for any 5, 'P(d) adjusts the public good at a
rate of e almost everywhere along the path to termination, we can choose 5
such that Sit') = (p(y{0) + \ edt) for all V € [0, «). Given this choice
of 5, ^(5) implements (p. m
6. CONCLUDING REMARKS
This paper achieves two objectives. First, Pareto-efficiency and
individual rationality in a public goods allocation problem are implemented
using a planning procedure. Moreover, it is possible to distribute the
surplus as a function of the level of the public good available. Second,
the procedure is immune to manipulation by coalitions of consumers. A
22
price that we have had to pay is in terms of an increase in the complexity
of the outcome rules and the amount of information that is transmitted to
the Center at each instant.
Fortunately, the rules for partitioning the message space are quite
simple and the outcome rules are easy to implement. The original
procedures required consumers to report their marginal willingnesses to
pay. Our procedure requires some additional messages. The X announcements
have a ready interpretation: they are each consumer's opinion regarding
what the distribution of the tax burden should be. The integer
announcements have no direct interpretation. Construction of mechanisms
with such "greatest integer games" is common in implementation theory. An
interesting aspect of our construction is that the integer announcements
are used not only to delete unwanted equilibria (which is the role they
play in implementation theory) but also to prove the existence of an
equilibrium. Such integer games have, however, been criticized for the
lack of interpretation via a "real-world" institution (see Kreps (1990)).
Throughout the paper, we have assumed that y(0) > 0. Truchon's
procedure has the disadvantage that it may never get started in the absence
of this assumption. In a Nash equilibrium, the a-announcements could be
too low (see Truchon (1984) for an example) and the threshold e is never
attained. A slight modification of the outcome rules of the procedure
given in this paper eliminates this non-starting inefficient Nash
equilibrium in the case where y(0) = 0. This modification has not been
incorporated into the results above since it distracts from the main points
of paper. The intuition underlying the modification is simple: use the
integer announcement game to provide consumers the incentive to make
a-announcements that are sufficiently high. If y(0) = 0, and the
a-announcements are "too low", then let the consumer who announces the
23
highest integer decide A, i.e. the distribution of the tax burden. The
total taxes to be paid is given by e + 3(0). In a Nash equilibrium of the
modified game, the a-announcements will be sufficiently high. Otherwise,
each consumer will have the incentive to announce the highest integer and
choose X such that he/she pays no taxes.
The effects of relaxation of some of the other assumptions are
discussed in Truchon (1984).
A weakness that our procedure shares with any mechanism based on Nash
equilibrium or its refinements is the assumption of complete information
among the players. The information asymmetry exists between the consumers
and the Center. A more general treatment of the problem would allow for
incompleteness of information among the consumers themselves, which is an
open question. Complete information problems, nevertheless, constitute an
important class in the theory of implementation and
incentive-compatibility. See Moore (1990) for a survey.
Another question that remains open is the consideration of planning
problems in which the surplus distribution rule is dependent on the
messages or on the existing distribution of the private good. The problem
of coalitional manipulation is present in such situations as well. This
question will be addressed in future research on the subject.
24
References
BERNHEIM, D., M. WHINSTON AND B. PELEG: 1987. "Coalition-Proof Nash
Equilibria I. Concepts," Journal of Economic Theory, 42, 1-12.
DREZE, J. AND D. DE LA VALLEE POUSSIN: 1971. "A Tatonnemont Process for
Public Goods," Review of Economic Studies, 38, 133-150.
GREENBERG, J.: 1986. "Stable Standards of Behavior: A Unifying Approach to
Solution Concepts," mimeo Stanford University.
GREENBERG, J.: 1989. "Deriving Strong and Coalition-Proof Nash
Equilibria from an Abstract System," Journal of Economic Theory, 44.
KAHN, C. AND D. MOOKHERJEE: 1989. "The Good, the Bad and the Ugly:
Coalition-Proof Equilibrium in Games with Infinite Strategy Spaces," mimeo
University of Illinois at Urbana-Champaign and Stanford University.
KREPS, D.: 1990. "Nash Equilibrium?" invited lecture at the 6th. World
Congress of the Econometric Society in Barcelona, Spain.
MALINVAUD, E.: 1971. "A Planning Approach to the Public Good Problem,"
Swedish Journal of Economics, 1, 96-111.
MALINVAUD, E.: 1972. "Prices for Individual Consumption, Quantity
Indicators for Collective Consumption," Review of Economic Studies, 39,
385-406.
MOORE, J.: 1990. "Implementation Theory under Complete Information,"
invited lecture at the 6th. World Congress of the Econometric Society in
Barcelona, Spain.
TRUCHON, M.: 1984. "Non-Myopic Strategic Behavior in the MDP Planning
Procedure," Econometrica, 52, 1179-1190.
25
No. 28 Rafael Gely and Pablo T. Spiller. "An Economic Theory of Supreme Court Statutory
Decisions The State Farm and Grove City Cases" Working Paper #89-1560
No. 29 Rafael Gely and Pablo T. Spiller. "The Political Economy of Supreme Court
Constitutional Decisions: The Case of Roosevelt's Court Packing Plan" Working Paper
#89-1561
No. 30 Hadi S. Esf ahani . "Reputation and Product Quality Revisited." Working Paper #89-1584
No. 31 Jan K. Brueckner. "Growth Controls and Land Values in an Open City." Working Paper
#89-1594
No. 32 Jan K. Brueckner. "Tastes, Skills, and Local Public Goods." Working Paper #89-1610
No. 33 Luis Cabral and Shane Greenstein. "Switching Costs and Bidding Parity
in Government Procurement of Computer Systems." Working Paper #90-1628
No. 34 Charles D. Kolstad. "Hotelling Rents in Hotelling Space: Exhaustible
Resource Rents with Product Differentiation." Working Paper #90-1629
No. 35 Santiago Orbiztondo. "Investment Without Regulatory Commitment: The Case of Elastic
Demand." Working Paper #90-1634
No. 36 Bhaskar Chakravorti. "Sequential Rationality, Implementation and
Communication in Games." Working Paper #90-1636
No. 37 Pablo T. Spiller, Rafael Gely. "Congressional Control of Judicial
Independence: The Determinants of US Supreme Court Labor Relations Decisions,
1949/1987." Working Paper #90-1637
No. 38 Hans Brems . "Dynamic Macroeconomics: Fiscal and Monetary Policy."
Working Paper #90-1640
No. 39 Lanny Arvan. "Flexibility Versus Commitment in Strategic Trade Policy
Under Uncertainty: A Model of Endogenous Policy Leadership." Working Paper #90-1651
No. 40 David T. Scheffman, Pablo T. Spiller. "Buyers' Strategies, Entry Barriers, and
Competiton." Working Paper #90-1674
No. 41 Richard Arnould and Larry DeBrock. "Utilization Control in HMOs." Working Paper #90-
1698