Int. Journal of Game Theory, Vol. 10, lssue 1, page 35-43. 9
Vienna.
Game Theory and the Tennessee Valley Authority 1 ) By P.D. Straffin, Beloit2), and J.P. Heaney, Gainesville 3)
Abstract: The problem of fair allocation of joint costs was considered by the TVA in the 1930's, in relation to apportioning costs of dam systems among participatory uses. Methods proposed to solve this problem foreshadowed various game theory solution concepts including the core, a special case of the nucleolus, and the imputation which minimizes the maximum propensity to disrupt. A method equivalent to the latter, but with a different rationale, is now in standard use among water resource engineers.
Since the mathematical theory of games is an abstraction from decision problems of considerable practical importance, it is not surprising that k e y ideas o f the t h e o r y were foreshadowed in the thought o f scholars and practitioners in other areas. F o r instance, the work of Edgeworth [1881] and BOhm-Bawerk [1891] foreshadowed the idea o f the core o f a cooperative game with sidepayments, w h i c h w a s first defined and studied explicitly in game theory by Gillies [ 1953] and Shapley in the early 1950's4). The purpose o f this note is to draw attention to a case o f foreshadowing which appears to be much less familiar. During the 1930's, engineers and economists o f the Tennessee Valley A u t h o r i t y (TVA) in the United States independently developed ideas related to certain solution concepts of n-person cooperative games, in particular to the core, the nucleolus [Schmeidler], and the imputation which minimizes the m a x i m u m propensity to disrupt [Gately]. We think that knowledge of this work should be interesting and useful to modern game theorists. An excellent survey o f historical and modern approaches to the kind o f allocation problem the TVA was considering has recently appeared as Young et al. [ 1980].
1) The first author was supported in part by the Rockefeller Foundation under RF 77030, Allocation No. 81, and the U.S. Environmental Protection Agency, Grant No. R 802411. 2) Professor Philip D. Straffin Jr., Department of Mathematics, Beloit College, Wisconsin 53511, USA. 3 ) Professor James P. Heaney, Department of Environmental Engineering Sciences, University of Florida,' Florida 32611, USA. 4) The idea, although not the name, of the core does appear in yon Neumann/Morgenstern [1944], for instance in a footnote on page 41, where it is rejected as a solution concept because it is empty for a zero-sum game, and in section 67, where the core of a three-person economic game is calculated.
36
P.D. Straffin, and J.P. Heaney
1. Formulation of the Problem, and the Core The TVA was formed in the early 1930's as a response to the Great Depression and authorized to undertake large scale, multiple purpose water resource development projects in the Tennessee River basin. The major purposes to be served were improved navigation, flood control, and provision of electric power, with subsidiary benefits to irrigation, national defense and the production of fertilizer. Sections 9a and 14 of the Tennessee Valley Authority Act mandated that the cost of TVA projects be specifically allocated among the purposes involved [Parker]. Because the amount of cost allocated to the purpose of providing electrical power would affect the rate at which TVA power wouli be sold, and hence the extent to which it would compete with privately produced power, the allocation problem was extremely important and controversial. TVA engineers and consultants devoted considerable time and thought to a number of cost allocation methods in the late 1930's. Their work is surveyed inParker [1943] and Ransmeier [1942], which are our major sources for the development which follows. To formulate the cost allocation problem, let N be the set of n purposes among which costs must be allocated. For most TVA projects, N was effectively the set (navigation, flood control, power}. For any subset S C N, let C(S) be the cost of a project designed for the purposes in S only. Thus C(N) is the total projects cost with all purposes included, and C(i) is the cost of an alternate project which would accomplish only purpose i. A cost allocation is a vector (Ca, 9 9 c n) such that n
t'=l
ci = C ( N )
ci >/ O.
(1)
Here ci, of course; is the cost allocated to the i-th purpose. The problem is to choose
the cost allocation vector in a way which is equitable and defensible. Here is the first "preliminary criterion of a satisfactory allocation" listed by Ransmeier in his presentation of the problem [1942, p. 220]: The method should have a reasonable logical basis. It should not result in charging any objective with a greater investment than the fair capitalized value of the annual benefit of this objective to the consumer. It should not result in charging any objective with a greater investment than would suffice for its development at an alternate single purpose site. Finally, it should not charge any two or more objectives with a greater investment than would suffice for alternate dual or multiple purpose improvement. The last two sentences say that we should have (2)
Ci ~ C(i)
and E c i <~ C(S) iES
for all S C N.
(3)
Game Theory and the Tennessee Valley Authority
37
The connection of these criteria with the theory of games becomes clear if we define for an allocation problem the associated savings game (N, v), where
v(S) = Z C(O -- C(S). i~S
(4)
v(S) is the savings which can be realized by a coalition S of purposes. The function v is always zero-normalized, v(0 = 0, and in cases of interest to the TVA, C was subadditive so that v is superadditive: v(S U T) >~v(S) + v(T) when S n T = r Choosing an allocation (cx . . . . . Cn) of costs is equivalent to choosing an allocation ( x l , . . . , x n) of savings, where x i = c ( 0 - c,.
(5)
In terms of the savings game, criteria (1), (2) and (3) become n
Y, xi = v(N ) i=1
(6)
x i >t 0
(7)
and
iES
x i >I v(S)
for all S c N.
(8)
The first two criteria say that the savings vector (xl, 9 x n) should be an imputation. The third criterion says that this imputation should lie in the core of the savings game. The idea of the core was thus foreshadowed before von Neumann/Morgenstern's treatise [1944], and a decade before its importance became manifest in game theory. The possibility that the core of the savings game might be empty was not recognized by Ransmeier. The reason for this was probably practical: because of the strong economies present in multipurpose river basin development, the TVA savings games were always convex, v(S) + v(T) <<,v(S U T) + v(S N T) for all S, T C N. For convex games the core is always nonempty, and in fact is always "large" [Shapley].
2. Equal Allocation of Non-separable Costs, and the Nucleolus TVA engineers were interested in choosing a specific imputation as the solution to the allocation problem, and they considered more than a dozen possible methods for doing this [Ransmeier, chapters 8 - 13;Parker]. Almost all of these methods begin by charging each purpose a minimum cost called its separable cost. Separable costs are the total change in the cost of a project due to adding a purpose to a project already designed for the other purposes. They include direct costs - those costs which are solely
38
P.D. Straffin, and J.P. Heaney
attributable to the single purpose - plus the additional costs of enlarging the multiple purpose components of the project, e.g. the incremental cost of enlarging a multipurpose dam. The separable cost of purpose i is thus defined by SC i
C(N)--C(N-
(9)
i).
When the savings game is convex, it is easy to check that the total of separable costs will always be less than or equal to the total cost: n
sc=
z
(10)
sci
i=l Hence the allocation problem becomes the problem of how to allocate the nonseparable cost NSC=C(N)-SC.
(11)
Two of the methods which were proposed for doing this are of particular interest. The first is the rather naive idea that non-separable costs should be proportioned equally:
(12)
ci = S C i + N S C . n
In terms of the savings game, notice that sc.
= c(~
- C(N -
0 = C(O -
v(~
+ v(N-
(13)
i)
and n
N S C = 2 ( v ( N ) -- v ( N - j ) )
(14)
-- v ( N ) ,
]=1 so that x i = c(o
- c i = v (AO - ~ ( i
-
0 -- n
@1 =
(v(~-
~ ( / - ] ) ) - v(N)l.
(15)
In relation to the simplex of imputations of the savings game, this vector E = (xl . . . . . Xn) is the point which is equidistant from the hyperplanes x i = v ( N ) - v ( N -- i) which define the (n -- 1)-person coalition constraints of'the core
(see the examples in Figure 1). A major problem with this allocation method is that it only guarantees that the (n -- 1)-person coalition constraints of the core are met. In particular, the one-person coalition constraints of the core may not be met, so that the savings vector E defined
Game Theory and the Tennessee Valley Authority
39
by this method may not be an imputation. This situation is shown in Figure la. In cost terms, this means, as Ransmeier noted, that the method may assign one purpose a higher cost than would be necessary for an alternate single purpose project. The other extreme is represented in Figure 1c. Here the (n -- l)-person coalition constraints of the core are tighter, and equal apportionment of non-separable costs actually gives the nucleolus os the savings game. In a recent paper, Suzuki/Nakayama [1976] give necessary and sufficient conditions for this to be true, and point out that these conditions may often be met in cost allocation problems. Of course, the intermediate case where the point E is in the core but is not the nucleolus can also occur. This is illustrated in Figure 1b. 3
l
~ x3=O
t "E
\\
2
~_~.
l,? ,/"'v%t/~
\
•
l
I
- 2
lb) v(12) : 60, v(13) = v(23) = 30 E = (43.3,43.3,13.3) is in the core, but is not the nucleolu~.
/
la) v(12) = 80, v(13) = v(23) = 10 Enl~(5t6i7o56.7.-13.3) is not an
1
t~
IZ
x,3=O
A J ~ ~
~
~~00-5
V'~-%
lc) v(12) = 50, v(13) = v(23) = 40 E = (36.7,36.7,26.7) is the nucleolus. Fig. 1 : Possible behaviors in the savings game of the point E (equal allocation of non-separable costs). In each of these games v(123) = 100, v(1) = v(2) = v(3) = 0.
40
P.D. Straffin, and J.P. Heaney
3. The Alternative Cost Avoided Method, and the Propensity to Disrupt The second allocation method of interest was first proposed by Martin Glaeser, a TVA consultant, in 1938 [Ransmeier, p. 270]. In this method, each purpose is assigned its separable cost as before, but the non-separable costs are assigned in proportion to C(0 -- SCt.: ci = s c i +
c(i) - sci
NSC.
n
(16)
z ccs)-scj
/=1
Since C(/) is the cost of accomplishing purpose i by an alternate single-purpose project, and SC i is the marginal cost of including purpose i in the multi-purpose project, C(i) - SC i is the alternate cost avoided by including purpose i in the joint project. This scheme is thus known as the "alternate cost avoided" method of allocation. Using equations (5), (13) and (14), we can check that in the savings game the allocation in (16) corresponds to
= v(N)--v(N--!) Xi
v(N)
(17)
n
Z v(N)--v(N--]) ]=1
so that savings are allocated in proportion to v(N) -- v(N -- i). Since for convex games we then have 0 <~x i <~v(N) - v ( N - i), both the one person and (n -- 1)-person coalitional constraints of the core are satisfied. In particular, the resulting allocation is always in the core when n = 3, although it may not be when n > 3. The second author has recently proposed a possible modification of the method to deal with this problem [Heaney ]. In 1974, Gately proposed a new solution concept for n-person cooperative games [Gately]. Gately was also working with a savings game arising from a cost allocation problem - allocating costs to Indian states involved in cooperative development of electric power - but his approach was quite different from those we have been considering. Define player i's propensity to disrupt an imputation (xl . . . . . Xn) in the core to be
d. =j:~i t
xy - v ( N - i)
x i -- v (i)
= v(N)--xi
-- v ( N - - i) x i
= v_(N)--v(N--i)
-- 1.
(18)
x i
d. is the ratio of what the members of coalition N - - i would lose if player i disrupted l the grand coalition, to what player i himself would lose. If this ratio is large, player i has a powerful threat to disrupt the grand coalition unless his payoff is increased. Gately proposed that we choose for our solution the imputation which minimizes the maximum propensity to disrupt. This solution concept has been studied and generalized in Fischer/Gately [19 75], L ittlechild/Vaidya [ 1976], and Charnes et. al. [ 1978].
Game Theory and the Tennessee Valley Authority
41
Now notice that the way to minimize the maximum d i is to make all the di's equal, which is done by choosing the xi's in proportion to v(N) - v ( N - i). This is precisely what is done in formula (17). Hence Gately's apportionment method based on minimizing the maximum propensity to disrupt is exactly the TVA alternate cost avoided method. This particular foreshadowing has the fortunate property that the two different reasonings leading to the same solution reinforce each other. If Gately's solution is not new, his argument does strengthen the justification of the older method.
4. Sample Allocations for the TVA Ten Dam System As an example of how the foregoing allocation schemes work, consider the cost allocation problem for the original TVA ten dam system. Denote the purposes of navigation, flood control, and power as 1,2, and 3 respectively. Cost figures were then as follows (in $1000):
C(1)
= 163,520
v(1)
= 0
C(2)
= 140,826
v(2)
= 0
C(3)
= 250,096
v(3)
= 0
C(12)
= 301,607
v(12)
= 2739
C(13)
= 378,821
v(13)
= 34,795
C(23)
= 367,370
v(23)
= 23,552
C(123) = 412,584
v(123) = 141,858.
Table 1, adapted from Ransmeier [1942, p. 329], shows the calculations necessary for the alternate cost avoided allocation method. Table 2 compares the cost allocations of the two TVA methods, equal allocation of non-separable costs (E) and the alternate cost avoided method (A), with the allocations corresponding to two solution concepts from modern game theory, the nucleolus (N) and the Shapley value (S). Notice that in this case E is not equal to N, since the two-person coalition core constraints are not the "tight" constraints on N.
Alternate cost C (i) Separable cost SCi C (i) - SCi Allocation of NSC Total charges (sum of rows 2 and 4)
Nav~ation (1)
Flood Control(2)
Power (3)
Total
163,520 45,214 118,306 72,262 117,476
140,826 33,763 107,063 65,394 99,157
250,096 110,977 139,119 84,974 195,951
554,442 189,954 = SC 364,488 222,630 = NSC 412,584 = C(N)
Tab. 1 : Calculations for the alternate cost avoided allocation for the TVA ten dam system (costs in $1000).
42
P.D. Straffin, and J.P. Heaney
Equal allocation of non-separable costs (E) Alternate cost avoided (A) Nucleolus (N) Shapley value (S)
Navigation (1)
Flood Control (2) Power (3)
119,424 (28.9 %) 117,476 (28.5 %) 116,234 (28,2 %) 117,829 (28.6 %)
107,973 (26.2 %) 99,157 (24.0 %) 93,540 (22.7 %) 100,756 (24.4 %)
185,187 (44.9 %) 195,951 (47.5 %) 202,810 (49.1%) 193,999 (47.0 %)
Tab. 2: Cost allocations for the TVA ten dam system by four methods (costs in $1000). 5. Current Status of the Allocation Problem The final TVA cost allocation was "not based exactly on any one mathematical calculation or formula, the final sums being fixed by judgment and not by computation." [Parker, p. 183]. However, the alternate cost avoided method was the principal method used to guide that judgment, and a modification of this method is the allocation method which has gained widest acceptance among water resource engineers and is still in use today. In this modification, we recognize that an alternate single purpose project to accomplish purpose i would in fact not be undertaken unless its estimated benefits B(0 were greater than its cost C(0. Hence the C(/) in the allocation formula (16) should be replaced by min [B(/), C(0]: rain[B(/), C(0 ] -- SCi e i = SC i +
n
j=l
NSC.
(19)
rain [B(j), Cq)] - SCj
The figure min[B(i), C(i)] measures the benefits of accomplishing purpose i, limited by the alternate cost of accomplishing purpose i. Hence min[B(i), C(0 ] - S C i are the remaining benefits accruing to purpose i after the marginal cost of including it in the multi-purpose project have been deducted. Since the method assigns each purpose its separable cost and then assigns non-separable costs in proportion to remaining benefits, it is known as the separable cost remaining benefits (SCRB) method of allocation. This method was recommended to the United States Inter-Agency Committee on Water Resources in 1950 [Federal Inter-Agency River Basin Committee], and is emphasized in current water resources texts [see, for example, James/Lee, chapter 23]. It was recognized by Ransmeier that the TVA allocation work was relevant to the broader kind of accounting problem faced by a private industrial company which must allocate joint "overhead" costs among its different divisions. Although there is little evidence that early direct transference of ideas was made, it is true that solution concepts from game theory have recently begun to appear in the accounting literature. See, for instance Shubik [1962], Jensen [1977], and Hamlen et. al. [1977]. We may now have come full circle, with game theoretic solution concepts beginning to be applied to the kinds of problems which gave rise to related ideas before the advent of game theory itself. There is one final way in which the early TVA work foreshadowed the viewpoint of game theory. Here is the TVA three dam allocation report to the 75th Congress [Ransmeier, p. 384]:
Game Theory and the Tennessee Valley Authority
43
A number of theories of cost allocation were studied carefully by the Committee in its attempt to reach a conclusion as to the shares of the joint investment that should be assigned to the various f u n c t i o n s . . . Every method of allocating the common plant investment necessarily involves assumptions and estimates the formulation of which is dependent on widely varying opinions of i n d i v i d u a l s . . . The Committee's conclusions are, therefore, in the form of a recommended policy based on judgment and not on any one allocation theory. No single allocation method, or no single game theoretic solution concept, can claim to be uniquely "best.'" In this domain, rationality seems to demand a multiplicity of viewpoints, and narrow insistence o n the virtues of one method is a vice rather than a virtue. References
B6hm-Bawerk, E. yon: Positive Theory of Capital (translated by W. Smart). New York 1923. Original 1891. Charnes, A., J. Rousseau and L. Seiford: Complements, mollifiers and the propensity to disrupt. Int. J. Game Theory 7, 1978, 37-50. Edgeworth, F.: Mathematical Psychics. London 1881. Federal Inter-Agency giver Basin Committee: Proposed practices for economic analysis of river basin projects. USGPO, Washington, D.C., 1950. Fischer, D., and D. Gately : A comparison of various solution concepts for three-person cooperative games with non-empty cores. Center for Applied Economics, New York University, 1975. Gately, D. : Sharing the gains from regional cooperation: a game theoretic application to planning investment in electric power. International Economic Review 15, 1974, 195-208. Gillies, D.B. : Some theorems on n-person games. Ph.D. thesis, Department of Mathematics, Princeton University, 1953. Hamlen, S., W. Hamlen and Jr. Tschirhart: The use of core theory in evaluating joint cost allocation schemes. Accounting Review 52, 1977, 616-627. Heaney, J. : Efficiency/equity analysis of environmentalproblems: a game theoretic perspective. Proc. International Conference on Applied Game Theory. Vienna 1979. James, L., and R. Lee" Economics of water Resources Planning. New York 1971. Jensen, D. : A class of mutually satisfactory allocations. Accounting Review 52, 1977. Littlechild, S., and K. Vaidya: The propensity to disrupt and the disruption nudeolus in a characteristic function game. Int. J. Game Theory 5, 1976, 151-161. Parker, T. : Allocation of the Tennessee Valley Authority projects. Trans. Amer. Soc. Civil Eng. 108, 1943, 174-187. Ransmeier, J.S.: The Tennessee Valley Authority: A Case Study in the Economics of Multiple Purpose Stream Planning. Nashville 1942. Schmeidler, D. : The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17, 1969, 1163-1170. Shapley, L. : Cores of convex games. Int. J. Game Theory 1,1971, 11-26. Shubik, M.: Incentives, decentralized control, the assignment of joint costs and internal pricing. Management Science 8, 1962, 325-43. Suzuki, M., and M. Nakayama: The cost assignment of cooperative water resource development: a game theoretical approach. Management Science 22, 1976, 1081-1086. Von Neumann, J., and O. Morgenstern : Theory of Games and Economic Behavior (Third Edition). New York 1953. Original 1944. Young, H.P., N. Okada and T. Hashimoto: Cost Allocation in Water Research Development. IIASA, Laxenburg, Austria 1980. Received February 1979 (revised version, July 1980)