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