Herbert Scarf

Herbert Eli Scarf
300 px Herbert Scarf
Born	(1930-07-25)July 25, 1930 Philadelphia, Pennsylvania
Died	Sag Harbor, New York
Nationality	American
Institution	Yale University
Field	Economics, Mathematics
Alma mater	Princeton University Temple University
Awards	John von Neumann Theory Prize (1983)
Information at IDEAS / RePEc

Herbert Eli Scarf (July 25, 1930 – November 15, 2015) was an American economist and Sterling Professor (Emeritus as of 2010) of Economics at Yale University. He is a member of the American Academy of Arts and Sciences, the National Academy of Sciences and the American Philosophical Society. He served as the president of the Econometric Society in 1983. He received both the Frederick Lanchester Award in 1973 and the John von Neumann Medal in 1983 from the Operations Research Society of America and was elected as a Distinguished Fellow of the American Economic Association in 1991.

Scarf never received formal training in economics. Both his undergraduate training at Temple University and his graduate work at Princeton University were in mathematics. For the past five decades, however, he has worked at the frontiers of both economic theory and operations research and has made a number of extraordinarily significant contributions to both of these fields. He is internationally famous for his early epoch-making work on optimal inventory policies and his highly influential study with Andrew Clark on optimal policies for a multi-echelon inventory problem, which initiated the important and flourishing field of supply chain management. Equally, he has gained world recognition for his classic study on the stability of the Walrasian price adjustment processes, his fundamental analysis (with Gerard Debreu) on the relation between the core and the set of competitive equilibria (the so-called Edgeworth conjecture, named after the Irish economist, Francis Ysidro Edgeworth, Feb 8, 1845–Feb 13, 1926), his remarkable sufficient condition (i.e., balancedness) for the existence of a core in non-transferable utility games and general exchange economies, his seminal paper with Lloyd Shapley on housing markets, and his pioneering study on increasing returns and models of production in the presence of indivisibilities. All in all, however, the name of Scarf is always remembered as a synonym for the computation of economic equilibria and fixed points. In the early 1960s he invented a path-breaking technique for computing equilibrium prices. This method is nowadays known as Scarf’s algorithm and has made general equilibrium theory applicable to large, realistic economic problems. This work has generated a major research field in economics termed Applied General Equilibrium Analysis and a corresponding area in operations research known as Simplicial Fixed Point Methods (or Algorithms). Scarf’s algorithm and its subsequent refinements and alternatives have become practical tools for assessing the consequences for the entire economy of a change in the economic environment or a major change in economic policy – to engage in comparative statics when the model of equilibrium is too large to be solved graphically or by simple numerical calculations.

Early life and Education

Herbert Eli Scarf was born on July 25, 1930, in Philadelphia, Pennsylvania, to parents of Ukrainian Jewish origins. His father, Louis Harris Scarf, immigrated from Ukraine to the United States in 1905 at the age of 18. His mother, Lena Elkman, came immigrated in the same year at the age of 5. They married in 1929 and had twin sons next year: Frederick Leonard Scarf and Herbert Eli Scarf. Herbert and Frederick attended the same public primary school and the South Philadelphia High School in Philadelphia. Herbert Scarf became interested in mathematics in his early adolescence after reading the book Men of Mathematics by E.T.Bell. He began reading books on calculus, geometry, number theory, and theoretical mechanics on his own in high school. He was ranked first in the Pennsylvania Statewide Mathematical Tournament for high school students organized by Temple University in 1947.

Herbert Scarf and his brother Frederick both attended Temple University in 1948 for their undergraduate studies. During that time both lived with their parents and commuted by subway between their parents’ house and the university. Their father owned a small business but was hit badly by the Great Depression and did not quite recover from it.

At Temple University, Herbert Scarf chose mathematics as his major subject. He began attended graduate courses on Real and Complex Variables, Analysis, Probability Theory, and Statistics in his sophomore year. He vividly remembered Professor Marie Wurster, who always encouraged him, and spent an enormous amount of time talking to him about mathematical topics. In 1950, he placed in the top 10 of the William Lowell Putnam Mathematical Competition, the major mathematics competition among universities in the United States and Canada.

In the fall of 1951, Herbert Scarf was awarded a scholarship from Princeton University where he received his graduate training in mathematics. His brother Frederick attended MIT to study physics. Frederick ultimately became a distinguished space scientist and died in Moscow at the age of 57.

Among Scarf’s many classmates at Princeton were Ralph E. Gomory, Lloyd Shapley, John McCarthy, Marvin Minsky, Serge Lang and John Milnor. He also met Martin Shubik, then a graduate student at the Department of Economics. By that time John Nash and Harold Kuhn had already left Princeton, but Scarf often saw them during their regular returns. At Princeton, Scarf became a close friend of Gomory. Though he did not study game theory while at Princeton, Scarf knew Martin Shubik, Lloyd Shapley, and John Nash, all who were actively involved in the early development of game theory.

After World War II, Princeton had become a sanctuary for a large number of world-leading scientists who had escaped from Nazi occupied Europe. Among them were Albert Einstein, John von Neumann, and Kurt Gödel. Scarf often saw Einstein strolling with Gödel from Einstein’s office at the Institute for Advanced Studies to his house on Mercer Street. Einstein always smiled benignly but his friend Gödel rarely did.

Scarf published his first scientific article ``Group invariant integration and the fundamental theorem of algebra” in the Proceedings of the National Academy of Sciences, in May, 1952. He attended Professor Saloman Bochner’s lectures about Haar Measure on Compact Topological Groups. One day Scarf made a sudden connection between this topic and theme he had been thinking about for some time. As a result he proposed an entirely novel proof for the fundamental theorem of algebra, stating that every polynomial in a single variable has at least one complex root.

Scarf’s academic adviser was Salomon Bochner. The two men maintained a good relationship until the latter's death death in 1982. Other professors in the Department of Mathematics were Emil Artin, William Feller, Ralph Fox, Solomon Lefschetz and Albert Tucker. Scarf wrote his PhD dissertation on partial differential equations over manifolds and received his PhD in 1954.

Career at Rand, Stanford, and Yale

Scarf worked at Bell Labs in the summer of 1953 and travelled every day between Princeton and the laboratory with John Tukey, an eminent statistician. At Bell Labs Scarf encountered Claude Shannon, the inventor of information theory. In June 1954, Scarf left Princeton to join the Rand Corporation. He chose Rand instead a more conventional academic job, because he desired to be involved in applied rather than abstract mathematics. The Rand Corporation was founded by the US Defense Department in 1948 in order to apply a variety of analytical tools to the economic, political and strategic problems of the Cold War and provided an ideal environment for researchers with applied interests.

Among his colleagues at Rand were Lloyd Shapley, George Dantzig, Richard Bellman, Ray Fulkerson, and Lester Ford. Dantzig, the inventor of the simplex method, had arrived a bit earlier and was applying his methods to a large variety of basic problems. Bellman was trying to formulate and solve all possible optimization problems with a dynamic structure as dynamic programming problems. Fulkerson and Ford were working together on network flow problems which became the springboard for the flourishing field of combinatorial optimization. At Rand, Scarf worked with Shapley on games with partial information and differential games with survival payoffs and was occasionally joined by John Nash when he visited as a consultant. This activity resulted in two early papers of Scarf and Shapley on game theory.

At Rand, Scarf was first assigned to the Mathematics Department but after a year the organization was visited by a budgetary crisis and Scarf was transferred to the Department of Logistics – a junior subset of the Department of Economics. His colleagues in the logistics group were mainly concerned with maintenance, repair, scheduling and inventory management which had little to do with the economic and strategic questions of the Cold War. Scarf was not assigned to any specific research topic. He learned about inventory problems by himself and wrote his first paper in this field. He met Samuel Karlin and Kenneth Arrow at Rand. They were both interested in inventory problems (Arrow had already written a remarkable paper on inventory theory with Harris and Marschak) and they invited Scarf to spend the academic year of 1956–1957 at the Department of Statistics, Stanford University.

At Stanford, Scarf worked intensively on inventory problems and demonstrated his extraordinary analytical skill and penetrating discernment on the nature of fundamental problems, when he published his two epoch-making papers on dynamic inventory problems: the first (1959) is on the optimality of policies and the second paper (1960), with Andrew Clark, on optimal policies for a multi-echelon inventory problem. Scarf also collaborated intensively with Arrow and Karlin on inventory problems. This collaboration resulted in three landmark volumes: Studies in Mathematical Theory of Inventory and Production, 1958, Contributions to the Theory of Inventory and Replacement, 1961, and Multistage Inventory Models and Techniques, 1963. Arrow and Karlin also became Scarf’s good friends and mentors.

Scarf’s visit was originally for a single year but the invitation was extended and in the fall of 1957 he was appointed as assistant professor in the Department of Statistics and subsequently an associate professor until he left Stanford in 1963. While working on inventory problems, Scarf became very interested in economics from discussions with Arrow and Hirofumi Uzawa and by attending the seminars on Mathematics in the Social Sciences organized by Arrow, Karlin and Patrick Suppes. He was particularly fascinated by general equilibrium models which he considered to be the central paradigm of economic theory.

In 1958 and 1959, Arrow and Leonid Hurwicz published two basic papers (the latter one with Robert Block) in Econometrica. They proved that the Walrasian price adjustment process formalized by Paul Samuelson (1941) converges globally to an equilibrium for exchange economies with divisible goods when all goods are gross substitutes. It was much speculated that such processes would converge in any reasonable economy with divisible goods. But Scarf (1960) soon dashed such hopes by producing a simple example with three consumers and three commodities that was globally unstable. This was Scarf’s first classic article in economic theory and was the very beginning of his remarkable career in the economics profession.

On Tjalling Charles Koopmans’ invitation, Scarf spent the academic year of 1959–1960 at the Cowles Foundation at Yale University. Koopmans, whom Scarf had met earlier at Rand, became a very close friend and mentor of Scarf. During his visit Scarf gave a seminar talk on his counter-examples. The seminar was chaired by James Tobin who was then the director. Among his audience were Gerard Debreu, Donald Hester, Alan Manne, Art Okun, Edmund Phelps, Bob Summers, and Jacob Marschak. During the same academic year, Scarf was invited to give a talk at Columbia University on his counter-examples. His old colleague Martin Shubik was in the audience. After the talk Scarf and Shubik took a long walk from 125th street to Shubik’s apartment in Sutton Place, New York. During the walk, Shubik passionately talked about and tried to persuade Scarf to solve the so-called Edgeworth conjecture that the core of an exchange economy would converge to its set of competitive equilibria if the number of traders in the economy tends to infinity.

Shubik’s enthusiasm sparked Scarf’s interest in this question and he started thinking seriously about the topic. He read von Neumann and Morgenstern’s book: The Theory of Games and Economic Behavior, Edgeworth’s analysis of the contract curve with two goods and two types of traders in his book: Mathematical Psychics, and Shubik’s 1959 paper on this subject. Several months later a decisive moment came when Scarf found a way, albeit extremely complicated, of proving the Edgeworth conjecture; see his 1961 paper: ``An analysis of markets with a large number of participants”. Debreu subsequently improved Scarf’s argument and published it in his 1963 paper: ``On a theorem of Scarf”. But a significant simplification of Scarf’s argument came when Scarf met Debreu on one occasion in December 1961, as Debreu eloquently described it in his 1983 Nobel Prize lecture: ``Associated with our joint paper is one of my vivid memories of the instant when a problem is solved. Scarf, then at Stanford, had met me at the San Francisco Airport in December 1961, and as he was driving to Palo Alto on the freeway, one of us, in one sentence, provided a key to the solution; the other, also in one sentence, immediately provided the other key; and the lock clicked open.” This collaboration yielded their 1963 paper: ``A limit theorem on the core of an economy,” which is one of the most fundamental results in general equilibrium theory. It is an important milestone for at least three reasons: First, it provides an important justification for the assumption of perfect competition that is fundamental in the treatment of neoclassical economic equilibrium models; second, it shows that competition and cooperation are just two sides of a coin for economic activities under the right circumstances; third, it became the starting point for a large literature on the core equivalence.

In 1963, Scarf moved to the Cowles Foundation and the Department of Economics at Yale University and was appointed as a full professor. In 1979 he became a Sterling Professor—the highest recognition for academic staff at Yale. He was the Director of the Cowles Foundation for the periods of 1967–71 and 1981–84. Since 1963 Scarf has remained at Cowles except for visiting appointments at Cambridge, Stanford and other institutes. He found the environment at Cowles extremely suited to him, as he describes it in the preface of his 1973 book: ``The standard of mathematical rigor and clarity of thought which prevail at Cowles are well known to the economics profession. But perhaps more important is the persistent though subtle suggestion that the highest aim of even the most theoretical work in economics is an ultimate practical applicability.”

During his first few years at Cowles Scarf concentrated on the problem of finding a method for computing economic equilibria. His work on the core equivalence result had suggested a roadmap. If he could find a way to calculate a point in the core of a game based on a general equilibrium model, then this method would serve to find an approximate equilibrium allocation, at least in an economy with a large number of traders. This activity resulted in the first major core existence theorem for a large class of cooperative games without side payments. He proved that an N-person game has a nonempty core if the game is balanced. Scarf’s first proof of this theorem relied on Brouwer’s fixed point theorem, but his hope was to provide a numerical method for computing a point in the core, making no use of fixed point theorems. Good fortune loves those who are well-prepared. Robert Aumann was visiting the Cowles Foundation during the academic year 1964–65. Scarf described his problem to Aumann, who suggested that he take a look at a recent paper by Lemke and Howson (1964). In this article, they proposed an algorithm for computing a Nash equilibrium in a finite two person non zero-sum game. In a single evening, Scarf realized that he could directly translate the Lemke-Howson’s algorithm through a limiting process into an elementary and constructive proof of his core existence theorem. This result was reported in his 1967 classic article: ``The core of an N-person game,” and became one of the most important theorems in cooperative game theory.

Having found an algorithm for the core, in November 1965, Scarf finally realized that he could explore this technique to design a novel algorithm for approximating equilibrium prices directly, without relying on the relation between the core and the competitive equilibrium. This path-breaking work marked the successful culmination of his long battle for transforming abstract general equilibrium analysis into a practical tool for the evaluation of economic policy. The result is published in his 1967 article: ``The approximation of fixed points of a continuous mapping”. It must be noted that Scarf's Ph.D. student, the Argentinian Rolf Mantel (who later contributed to the development of the Sonnenschein–Mantel–Debreu theorem in General Equilibrium Theory) presented earlier -in his 1966 doctoral thesis- a slightly different algorithm, based on the ``conification” of the economy. Back in Argentina Mantel developed a program implementing this algorithm for an economic planning agency (Tohmé 2006).

Since the early 1970s, Scarf launched his longest, hardest and most ambitious struggle: to tackle economies with indivisibilities, increasing returns and nonconvexity. In fact in 1963 he already wrote: ``Notes on the core of production economy,” which was widely circulated but was not published until 1986. In this note, he studied economies where the production set exhibits increasing returns. He showed that if the production possibility set satisfies customary properties, but is not a cone, then there is a collection of consumers with conventional preferences and specific initial endowments for which the core is empty. His seminal article with Shapley in 1974: ``On cores and indivisibilities,” marked the first victory in his battle tackling indivisibilities and has become a most-cited classic article in the field.

In the 1940s and 1950s, Dantzig and Koopmans had developed the activity analysis model of a production possibility set with constant returns to scale. When factor endowments are specified, the model leads directly to a linear program which can be solved by Dantzig’s simplex method. The method makes use of competitive prices to test for the optimality of a proposed feasible solution.

However, neither decreasing returns nor constant returns reflect economic reality. Since the beginning of the Industrial Revolution in the 1760s, economies of scale and increasing returns based on large indivisible pieces of machinery or forms of productive organization such as the assembly line are prominent features of every industrialized nation. Unfortunately, economic theory based on the assumption of convexity and perfect divisibility does not offer any clue to this challenging economic problem. The difficulty of dealing with indivisibilities has long been recognized by many leading economists including Lerner (1944), Koopmans and Beckmann (1957), and Debreu (1959), as Lerner (1944) points out: ``We see then that indivisibility leads to an expansion in the output of the firm, and this either makes the output big enough to render the indivisibility insignificant, or it destroys the perfection of competition. Significant indivisibility destroys perfect competition.”

Scarf was interested in economies with indivisibilities in production, i.e., where activity levels are constrained to be integers, an extreme form of non-convexity. When factor endowments are specified we are led to the general integer program for which there is no pricing test to detect whether a feasible production plan is indeed optimal. His major goals have been (1) to replace the pricing test by a local neighbourhood search and (2) to develop a mechanism for efficiently finding this test set. In the early 1980s, he made a decisive victory in achieving his first goal. Using his early concept of primitive sets arising in his research on the core and the computation of equilibria, Scarf succeeded in developing a quantity test set. He proved that this test set is unique and minimal, depending on the technology matrix alone and not on the specification of the particular factor endowment. It consists of a finite number of integral production plans. When this test set is available, one can easily use it to verify if a production plan is optimal or not, and if it is not optimal, one can use the test set to obtain a better production plan.

Scarf has worked with a group of mathematicians on this subject for many years. He has found several important special classes of technology matrices for which the test set can be easily identified. However, important questions remain open and the battle is not yet over, as he states in his 1983 Presidential Address of the Econometric Society (1986, Econometrica):``At the present time, I am far from being able to present a convincing argument which relates the structure of neighbourhood systems (i.e., test sets) to the administrative arrangements that might be taken by a large industrial enterprise.” Up to this very moment, his struggle goes on. Indeed, as a Chinese poem says: ``An old war-horse may be stabled, yet still it longs to gallop a thousand miles; and a noble-hearted man though advanced in years never abandons his proud aspirations.”

Major Works

1. $(S,s)$ Optimal Inventory Policies

Every organization encounters inventory problems of one kind or another. Consider a typical situation: A retailer faces uncertain demand for its product from customers over time. He has to pay a reorder cost and a unit cost when he orders the good from its producer. Over time, he also needs to pay the holding cost of its inventory and a shortage cost if the good runs out of stock. The retailer’s problem is to determine how much to order in each period of time so as to minimize expected cost. Scarf (1958) solved the problem in a characteristic manner by introducing a generalized notion of convexity, called $K$-convexity. Given a constant $K\ge 0$ a function $f(x)$ is called $K$-convex if,

$f(x)+a[\frac{f(x)-f(x-b)}{b}]\le f(x+a)+K$

for all positive $a, \, b$, and all $x.$ Note that $0$-convexity is equivalent to ordinary convexity.

Scarf demonstrated inductively that the minimum expected cost was $K$-convex and that the optimal policy for the dynamic inventory problem is given, for each period of time, by a pair $(S,s)$ of numbers. If, at the beginning of an ordering period, the stock has fallen below the lower level, $s$, it is optimal for the retailer to raise the stock to the upper level, $S$, otherwise no order is placed. The cost functions may be shown to be $K$-convex under a variety of conditions – for example whenever holding and shortage costs are linear, more generally, convex. Thus $(S,s)$ policies are optimal for many practical dynamic inventory problems and have become a benchmark solution in inventory management. $(S,s)$ policies had been used in practice for many years. Their operating characteristics were first discussed in Arrow, Harris and Marschak (1951), but the proof of optimality was first provided by Scarf.

2. Optimal Policies in Multi-echelon Inventory Problems

Clark and Scarf (1960) were the first to study a multi-echelon inventory problem and initiated the field of supply chain management. They considered a general situation in which there are several installations, say 1, 2, …, N, with installation 1 receiving stock from 2, with 2 receiving stock from 3, etc. If installation k-1 places an order from installation from k, the length of time for the order to be filled is determined not only by the natural delivery time between these two sites, but also by the availability of stock at installation k. The problem is to determine optimal purchasing quantities at each installation when delivery times, purchase costs, demand distributions, holding and shortage costs and other parameters are given.

They proved that the optimal policies for the N installations can be found by solving recursively a dynamic programming problem in which the value function depends on the inventory levels at each installation and the orders from successive installations which have not yet been delivered. Their important contribution was to demonstrate that under certain plausible conditions, the value functions can be decomposed into the sum of functions of a single variable, each of which satisfies its own recursive equation which can be solved easily.

3. Global Instability of the Competitive Equilibrium

Consider a situation: Several traders each bring his/her bundle of goods to a market place and wish to exchange their goods. In the general equilibrium model, the exchange takes place at prices that equilibrate demand and supply for every good. How are these prices to be found?

The market is guided by an invisible hand – a price adjustment mechanism – to an equilibrium state. You examine each good in the market and increase the price of the good if its demand is more than its supply but decrease its price if the relation holds the other way. Léon Walras had proposed the first such process in 1874, and Paul Samuelson formalized such a procedure as a system of differential equations in 1948.

Arrow and Hurwicz (1958), and Arrow, Block and Hurwicz (1959) found that the price adjustment process proposed by Samuelson always converges to an equilibrium if the goods are gross substitutes. It was then speculated that the same process would work for any reasonable market of divisible goods. Scarf (1963) dashed such hopes by showing a series of counterexamples among which the first example involves three consumers and three complementary commodities, and has a unique equilibrium. He demonstrated that if the initial price vector is not the equilibrium price vector, this process will generate a cycle of non-equilibrium price vectors and never converge to the equilibrium.

4. Core and Competitive Equilibrium Equivalence

Consider an economic system composed of many self-interested individuals each of whom is endowed with a bundle of goods, has preferences over the available bundles and wishes to achieve a maximal satisfaction by exchanging his/her own goods with others. The system requires every individual to respect the private ownership and the voluntary and non-coercive trade rule. Given this system, what will be a natural outcome of chaotic and countless independent actions of these self-interested agents? Adam Smith in his book ``The Wealth of Nations” (1776) first recognized how the invisible hand – a competitive market mechanism – can reconcile the complicated and conflicting forces of self-interested agents and guides the system to an equilibrium. The equilibrium is a state in which there exists a system of prices (i.e., market-clearing prices) at which every agent gets a best bundle of goods under his/her budget constraint and the supply of each good meets its demand. The list of the bundles obtained by all agents in the equilibrium state is called a competitive equilibrium allocation and is a redistribution of all agents’ initial endowments of goods. Wald (1936), Arrow and Debreu (1954), and McKenzie (1959) among many others established fundamental results on the existence of competitive equilibrium. The assumption of perfect competition or price-taking behaviour is crucial in these analyses. It essentially requires that the influence of every agent in the system should be negligible.

Another equally appealing and natural outcome of the economic system was first proposed by Francis Edgeworth in his book ``Mathematical Psychics’’ (1881), and is now known as the core allocation (in the case of two goods, it is any point in the contract curve of the Edgeworth box). Formally, a redistribution of all agents’ initial endowments of goods among all agents in the system is a core allocation if no group of agents can redistribute their own initial endowments among themselves so as to improve the satisfaction of someone in the group without impairing that of any other in the group. Clearly, a core allocation is Pareto efficient in the sense that there is no way to make some agent better off without making any other worse off. It is now well known that every competitive equilibrium allocation must be a core allocation but a core allocation need not be a competitive equilibrium allocation. Edgeworth worked with an economic system consisting of only two agents and two goods, and then replicated the economy many times. What he found is that as the replication tends to infinity, the set of core allocations converges to the set of competitive equilibrium allocations. This result provides a perfect justification of price-taking behaviour but in a very specific setting. However, Edgeworth’s approach is based on the geometrical picture of the Edgeworth box and cannot be applied to the general case involving more than two agents and more than two types of goods. The general case is known as Edgeworth conjecture and remained widely open for many several decades.

Based on the earlier paper of Scarf (1962), Debreu and Scarf (1963) resolved the outstanding theoretical problem in a brilliant and elegant manner. They started with a general economy consisting of any finitely many agents and a finite number of goods and proved that if one replicates the economy infinitely many times, then the set of core allocations coincides with the set of competitive equilibrium allocations. This offers an impeccable validation of perfect competition in a most general and most natural setting. This study has spawned a large body of literature on the relationship between the core and the set of competitive equilibrium allocations. One of the most significant contributions to this literature is the paper of Aumann (1964). Having heard Scarf’s discussion on his original 1962 paper at a conference at Princeton in 1962, Aumann established a model of pure exchange economy with a continuum of agents in which the core and the set of competitive equilibrium allocations are the same.

5. The Core of an N-Person Game

The problems of resource distribution in an economic system may be resolved by the tool of competitive equilibrium theory or by more general and more flexible techniques of game theory. In a competitive equilibrium setting, every consumer acts in response to a set of prices by choosing bundles to maximize her utility under her budget constraint and every firm selects production levels at which the highest profit is achieved . The system reaches an equilibrium at which consistent production plans and allocation of goods are made and all participants are in harmony with one another. When these economic problems are studied in the framework of game theory, we need to specify a set of production and distribution activities available to each possible coalition of economic agents. It is, however, often sufficient and also convenient to summarize the detailed strategic possibilities open to each coalition by a set of possible utilities that can be achieved by the coalition. A stable and desirable outcome of the system is a core allocation of the game which assigns every agent a utility, and from which neither any individual agent nor any group of agents will have incentive to deviate. Scarf (1967) studied this problem and provided sufficient conditions under which a core allocation always exists.

Formally, Scarf considers the following general game with a finite number of agents. Let $N$ denote all the agents in a system who are engaging in some business, economic, or political activities. These agents are called players and each nonempty group of players is called a coalition. For each coalition $S\subseteq N$, let $\mathbb{R}^S$ stand for the Euclidean space of dimension equal to the number of players in $S$ and whose coordinates are indexed by the elements in $S$. Each coalition $S$ is associated with a set $V(S)$ of possible utility vectors which can be achieved by the coalition if all players in the coalition cooperate. The set $V(S)$ is a subset of $\mathbb{R}^N$and the i-th component $x_i$ of each element $x\in V(S)$ indicates a utility for player $i\in S.$ The following assumptions are made on the sets $V(S)$:

1. For each coalition $S$, $V(S)$ is closed and bounded from above.

2. If $x\in V(S)$ and $y\in \mathbb{R}^N$ with $y_i\le x_i$ for all $i\in S$, then $y\in v(S)$.

We say that a utility vector $x\in V(N)$ is blocked by a coalition $S$ if there exists a utility vector $y\in V(S)$ such that $y_i>x_i$ for all $i\in S$. That is, when the coalition cooperates, every player in the coalition can actually achieve a higher utility than that given by $x$. A utility vector in $V(N)$ is in the core if no coalition can block it. An intriguing and fundamental question is what kind of game has a nonempty core. To answer this question, Scarf introduces the class of so-called balanced games.

A family $\Omega$ of coalitions in the game is said to be balanced if there exist nonnegative numbers $\delta(S)$, for every coalition $S\in \Omega$, such that $\sum_{i\in S\in \Omega}\delta(S)=1$ for every $i\in N.$ (Any partition of the grand coalition $N$ is a simple example of a balanced family.) The game is said to be balanced if for every balanced family $\Omega$, a utility vector $u$ must be in $V(N)$ if $u$ is in $V(S)$ for every coalition $S\in \Omega$. Scarf proved the following theorem based on a finite algorithm.

Scarf’s Theorem: Every balanced game has a nonempty core.

6. Scarf’s Combinatorial Lemma

To prove his core existence theorem on the balanced game, Scarf (1967) introduced an elegant and fundamental combinatorial lemma which has found applications in various subjects.

Let $A$ and $C$ be two $n\times m$ matrices of the following form:

$\mathbf{A}=\begin{bmatrix} 1 & 0& \cdots & 0 &a(1,n+1)& \cdots & a(1,m)\\ 0 & 1& \cdots & 0 &a(2,n+2)& \cdots & a(2,m)\\ & & \cdots & & & \cdots & \\ 0 & 0& \cdots & 1 &a(n,n+1)& \cdots &a(n,m)\end{bmatrix}$

and $\mathbf{C}=\begin{bmatrix} c(1,1) & \cdots & c(1,n) &c(1,n+1)& \cdots & c(1,m)\\ c(2,1) & \cdots & c(2,n) &c(2,n+2)& \cdots & c(2,m)\\ & \cdots & & & \cdots & \\ c(n,1) & \cdots & c(n,n) &c(n,n+1)& \cdots &c(n,m)\end{bmatrix}$

The matrices $A$ and $C$ are said to be in standard form if for every row $i$, $c(i,i)$ is the minimum of the elements in its row, and if for every non-diagonal element $c(i,j)$ in the square submatrix of $C$ formed by the first $n$ columns, and for every $k$ with $n<k\le m$, we have $c(i,j)\ge c(i,k)$.

Scarf’s Lemma: Assume that $A$ and $C$ are two $n\times m$ matrices in standard form, and that $b$ is a nonnegative vector such that the set $\{x\mid Ax=b \,\mbox{and}\, x\ge 0\}$ is bounded. Then there exists a feasible basis for the system of linear equations $Ax=b$ and $x\ge 0$, so that if we define $u_i=\min c(i,j)$ for all columns $j$ in this basis, then for every column $k$, we have $u_i\ge c(i,k)$ for some index $i$.

7. The Computation of Economic Equilibria

Scarf’s book ``The Computation of Economic Equilibria” (Yale University Press, 1973) is considered his magnum opus. It is a monumental work both in economic theory and in applied mathematics. Scarf ingeniously developed the first general constructive method for the explicit numerical solution to the neoclassical model of economic equilibrium and has made it possible to transform such a model from an abstract representation of an economy into realistic models of actual economies, permitting us to evaluate the effects of significant changes in the environment and in economic policies.

One of the central themes of economic theory is that the behaviour of a highly complex economic system can be seen as an equilibrium outcome arising from the interactions of many individuals within the system with different and even conflicting interests and motivations. This fundamental idea was first formulated by Walras (1874) and further significantly developed by Wald (1936), Arrow and Debreu (1954), and McKenzie (1959) among many others as the neoclassical model of competitive equilibrium. When cast in a mathematical form such a model will become a system of highly nonlinear equations with multiple variables which represent prices of goods and services in the studied economy. The typical argument for the existence of a solution in this system is to apply Brouwer’s fixed point theorem (1912) – a fundamental theorem in mathematics which, however, does not offer any effective numerical solution. Brouwer’s theorem states that every continuous function $f:S^n\to S^n$ mapping from a unit simplex $S^n$ into itself must have a fixed point $f(p^*)=p^*$, where

$S^n=\{x\in \mathbb{R}^n_{+} \mid \sum_{i=1}^nx_i=1\}$

is the unit simplex whose elements are non-negative and the sum of all components equals one. As soon as we know a fixed point for the function constructed from the studied economy, we know its corresponding equilibrium in the economy.

Scarf proposed an algorithm for calculating a fixed point as stated in Brouwer’s theorem. As a result, he gave the first constructive proof for Brouwer’s theorem which is a major tool for establishing the existence of a solution to problems arising in various subjects. Scarf’s algorithm can be described as follows. One first subdivides the unit simplex $S^n$ into a finite simplicial subdivision. Each subsimplex is the convex hull of its vertices. Then one assigns each vertex a label from the set $\{1, 2, \cdots, n\}$, where the label of each vertex $x$ is given by $l(x)=\min \{j\mid f_j(x)\le x_j>0\}$. By definition, $x_j=0$ implies $l(x)\ne j.$ A labelling rule with this property is said to be proper. According to a remarkable combinatorial theorem called Sperner’s lemma (1928), if we are given a simplicial subdivision of a unit simplex and a proper labelling rule, there always exists a completely labelled subsimplex, i.e., a simplex each of whose $n$ vertices carry a distinct label.

It is easy to show that if the labels are correctly selected, a completely labelled subsimplex contains an approximate fixed point of the function. The finer the subdivision, the better will be the approximation. Now the problem of finding an approximate fixed point is to search for a completely labelled subsimplex. Unfortunately, the original proof and its subsequent arguments for Sperner’s lemma were inductive in nature and thus virtually impossible to implement. Scarf (1967, 1973) introduced an effective and finite algorithm that can always find a completely labelled subsimplex.

The basic idea of Scarf’s algorithm can be clearly illustrated for $n=3$ and the same logic applies to higher values of $n.$ We can embed the unit simplex in a larger simplex as shown in Figure 1. The larger simplex is subdivided by linking its three new vertices with the vertices lying on the boundary of the original unit simplex. A proper labelling always leads to

$l(x^1)=1$, $l(x^2)=2$, and $l(x^3)=3$, where $x^1=(1,0,0)$, $x^2=(0,1,0)$, and $x^3=(0,0,1)$

are the vertices of the original unit simplex $S^3.$ Each of the new vertices can be labelled by 1, 2, or 3 in such a way that no additional completely labelled simplex is created. This construction makes it very easy to find a triangle whose three vertices carry two of the three desired labels. Scarf’s algorithm begins with the triangle whose two vertices are the vertices of the larger simplex and bear labels 1 and 2, as shown in Figure 1. Then the algorithm generates a sequence of adjacent triangles, each of which has vertices labelled 1 and 2. The sequence is uniquely determined by the initial triangle. When the algorithm enters a new triangle, it exits through an edge whose vertices bear labels 1 and 2, which is different from the edge used to enter the triangle. If the triangle is not completely labelled, there will be a unique other edge whose vertices carry labels 1 and 2, and the algorithm leaves this edge to move into a new triangle. Remarkably, this algorithm will never return to any triangle that it has previously visited. Since the number of the triangles is finite, the algorithm must terminate with a completely labelled triangle.

The argument for the convergence can be vividly described with a tale (Scarf (1973, p. 48)): We can think of the larger simplex as a house, and of its triangles as rooms. A room has a door if the two vertices of one of its edges bear labels 1 and 2. It is clear that a completely labelled triangle is a room with only one door, all other rooms have either two doors or no door at all. By the construction, the house has precisely one door leading to the outside. Scarf’s algorithm begins with the known outside door and proceeds from room to room, never departing from a room by the door used in entering it. The algorithm can never return to a room previously entered nor leave the house, and therefore must find a room with only one door – a completely labelled simplex! This idea has been explored to create the so-called Sperner Game (Kyle Burke http://www4.wittenberg.edu/academics/mathcomp/kburke and Shang-Hua Teng http://www-rcf.usc.edu/%7Eshanghua/).

File:Image-of-the-illustration-of-Scarf-algorithm.jpg

Figure 1: The Illustration of Scarf's Algorithm

Scarf’s algorithm has initiated a major research field in economics known as Applied General Equilibrium Analysis (see Shoven and Whalley (1992)) and a corresponding area in operations research termed Simplicial Fixed Point Methods or Algorithms (see Todd (1976) and Yang (1999)).

8. The Housing Market

The assumption of perfect divisibility is essential in neoclassical economic analysis. However, this assumption often contradicts our casual observation of economic reality. In fact, many traded commodities are inherently indivisible, such as houses and cars. In a pioneering article (Shapley and Scarf (1974)), Scarf and Shapley studied a market with a finite number of traders, each with a single indivisible good (e.g., a house) that they wish to exchange. Each trader has preferences over houses but has no use for more than one item. There is no money or other medium of exchange so the only effect of the market activity is to permute the indivisible goods among the traders in accordance with their purely ordinal preferences. With the aid of Scarf’s core existence theorem they proved that this market always possesses a core allocation—a redistribution of items among all traders that cannot be improved upon by any individual, or any group of individuals. To find a core allocation, they also introduced a mechanism – called the top trading cycle method which had been discovered by David Gale.

The mechanism works as follows: Each trader i points to the trader j whose house trader i likes best. Clearly, there is at least one cycle of traders such that each trader most prefers the house owned by the subsequent trader in the cycle. The mechanism assigns every trader in the cycle the house he likes best, and removes all of the members of the cycle from the market. The remaining traders repeat the same process until every trader is accounted for. Remarkably it is now known that when faced with this mechanism, it is in the best interest of every trader and every group of traders to act sincerely – there are no gains to be made by misrepresenting an individual’s preferences.

9. Production with Indivisibilities and Integer Programming

The assumption of convex production sets plays a pivotal role in neoclassical economic theory. If the production possibility set is convex then any efficient production plan will be supported by a set of competitive prices. The simplex method proposed by George Dantzig is an effective device for discovering these prices from the underlying linear programming problem. Unfortunately, such prices will no longer exist when the production set displays increasing returns to scale, indivisibilities, or other forms of nonconvexity. The most important example of a production set with indivisibilities is an activity analysis model in which all activity levels are constrained to be integers rather than arbitrary real numbers. Production sets with indivisibilities represents the most extreme form of nonconvexities in production and correspond to integer rather than ordinary linear programming problem. In this case, there is no simple test, like the pricing test arising from convex production sets, to verify whether a production plan is optimal or not.

To study this problem, Scarf (1981, 1986) developed an entirely different analytical apparatus-called a neighbourhood system, to replace the pricing test. Consider a general integer programming problem of the form:

$\begin{align} && \max(a(0,1)h_1+a(0,2)h_2+\cdots+a(0,n)h_n)\\ &&{\operatorname{s.t.}}\quad a(1,1)h_1+a(1,2)h_2+\cdots+a(1,n)h_n\ge b_1\\ &&\quad a(2,1)h_1+a(2,2)h_2+\cdots+a(2,n)h_n\ge b_2\\ &&\quad \vdots\quad \vdots\quad \vdots\quad\vdots \quad\\ &&\quad a(m,1)h_1+a(m,2)h_2+\cdots+a(m,n)h_n\ge b_m \end{align}$

where $h_1, h_2, \cdots, h_n$ are integer-valued variables, and $b_1, b_2, \cdots, b_m$ are integer constants. For each integral vector $h=(h_1,h_2,\cdots, h_n)$, the neighbourhood of the vector $h$ is a finite set $N(h)$ of integral vectors satisfying the two conditions: (i) $N(h)=\{h\}+N(0)$, and (ii) $k\in N(h)$ implies $h\in N(k).$

The first condition indicates that for any two different integral points, their neighbourhoods are translates of each other, and the second condition shows the symmetric property of the neighbourhood system. Each element in $N(h)$ is called a neighbour of $h.$ If we are given a feasible solution $h$ to the above integer program we can test its set of neighbours $h+k$, for $k\in N(h')$, to see if one of them is feasible and yields a higher value of the objective function. If none of them is feasible, then $h$ is a local maximum with respect to this neighbourhood system.

Scarf has shown that under mild conditions on the technology matrix $A=(a(i,j))$ there is a unique, smallest neighbourhood system, with the property that a local maximum is always global. This unique minimal neighbourhood system depends only on the technology matrix and not on the factor endowment. Thus to verify whether a production plan is optimal, one just needs to check if all its neighbours are either infeasible or yield an inferior value of the objective function. Therefore the minimal neighbourhood system provides a unique quantity test for optimality in the case of a production set with indivisibilities analogous to the pricing test in the case of a convex production set. Scarf (also together with his coauthors) has identified many important classes of production technology matrices for which the minimal neighbourhood system can be easily computed.

Scarf’s neighbourhood system has found applications in a variety of different areas: Algebraic Geometry, Cooperative Game Theory, Reliability Theory Multi-Commodity Network Flows, Graph Theory and the Stable Paths Problem. However, it is difficult to find the minimal neighbourhood system associated with an arbitrarily given technology matrix and one is forced to use computational procedures borrowed from Algebraic Geometry.

Personal life

Scarf met Margaret Klein a month or so before his graduation from Temple University in 1951, and married her in 1953. They had three daughters and eight grandchildren. Maggie Scarf is a well-known writer of best-selling books on psychological issues. He died on November 15, 2015 at the age of 85.

Mentors

Herbert Scarf was intellectually influenced by Kenneth Arrow, Saloman Bochner (Scarf’s PhD adviser), George Dantzig, Gerard Debreu, Tjalling Koopmans, and Maxwell Scarf (Herbert Scarf’s uncle).

PhD Students

Scarf was a superb teacher and adviser, a concerned and dedicated colleague, and an inspiration and role model to his students at Yale and Stanford and his colleagues all over the world. His clarity of thought and vision and thoroughness of knowledge are highly appreciated by his students and the readers of his work. He supervised (or been a major mentor for) about 30 PhD students. They are Frank Proschan (1959, Stanford), Donald Roberts (1960, Stanford), Donald Iglehart (1961, Stanford), Murray Geisler (1962, Stanford), Menahem Yaari (1962, Stanford), Louis Billera (1968, City University of New York), and the rest all graduated from Yale, Rolf Mantel (1965), Ana Martirena-Mantel (1965), Duncan Foley (1966), Eugene Poirier (1966), Terje Hansen (1968), Michael Keren (1968), Frank Levy (1969), Yukio Noguchi (1972), Michael Todd (1972), John Shoven (1973), John Walley (1973), Andrew Feltenstein (1976), Marcos Fonseca (1978), Timothy Kehoe (1979), Ludo van der Heyden (1979), Jaime Serra Puche (1979), Andrew Caplin (1983), Phillip White (1983), Kazuya Kamiya (1986), Joshua Reichert (1986), Michael Mandler (1989), Jingang Zhao (1992), and Xin Wang (1997).

Major Publications

1. On differential games with survival payoffs (with L.Shapley), 1958, in Volume III, Contribution to the Theory of Games, eds. D. Dresher, A.W.Tucker and P.Wolfe, Princeton University Press.

2.

3. Optimal policies for a multi-echelon inventory problem (with A.J.Clark), 1960, in Management Science, Vol. 6, No.4, pp. 475–490.

4. Some examples of global instability of the competitive equilibrium, 1960, in International Economic Review, Vol.1, No. 3, pp. 157–172.

5. An analysis of markets with a large number of participants, 1962, in Recent Advances in Game Theory, ed. M. Maschler, The Ivy Curtis Press.

6. A limit theorem on the core of an economy (with G.Debreu), 1963, in International Economic Review, Vol.4, No.3, pp. 235–246.

7. The core of an N-person game, 1967, in Econometrica, Vol. 35, No. 1, pp. 50–69.

8. The approximation of fixed points of a continuous mapping, 1967, in SIAM Journal of Applied Mathematics, Vol. 15, No.5, pp. 1328–1343.

9. On the existence of a cooperative solution for a general class of N-person games, 1971, in Journal of Economic Theory, Vol. 3, No. 2, pp. 169–181.

10. The Computation of Economic Equilibria, Yale University Press, New Haven, 1973.

11. On cores and indivisibilities (with L.Shapley), 1974, in Journal of Mathematical Economics, Vol.1, No. 1, pp. 23–37.

12. The solution of systems of piecewise linear equations (with B.C. Eaves), 1976, in Mathematics of Operations Research, Vol.1, No.1, pp. 1–27.

13. Production sets with indivisibilities, part I: generalities, 1981, in Econometrica, Vol. 49, No. 1, pp. 1–32.

14. Production sets with indivisibilities, part II: the case of two activities, 1981, in Econometrica, Vol. 49, No. 2, pp. 395–423.

15. Integral polyhedral in three spaces, 1985, in Mathematics of Operations Research, Vol.10, No.3, pp. 403–438.

16. Neighbourhood systems for production sets with indivisibilities, 1986, in Econometrica, Vol.54, No.3, 507–532.

17. The generalized basis reduction algorithm (with L.Lovász), 1992, in Mathematics of Operations Research, Vol.17, No.3, pp. 751–764

18. The Frobenius problem and maximal lattice free bodies (with D.F.Shallcross), 1993, in Mathematics of Operations Research, Vol.18, No.3, pp. 511–515.

19. The complex of maximal lattice free simplices (with I.Bárány and R.Howe), 1994, in Mathematical Programming, Vol. 66, No. 3, pp. 273–281.

20. The allocation of resources in the presence of indivisibilities,1994, in Journal of Economic Perspectives, Vol. 8, No. 4, pp. 111–128.

21. Matrices with identical sets of neighbours (with I.Bárány), 1998, in Mathematics of Operations Research, Vol.23, No.4, pp. 863–873.

22. The topological structure of maximal lattice free convex bodies: the general case (with I.Bárány and D.F.Shallcross), 1998, in Mathematical Programming, Vol. 80, No. 1, pp. 1–15.

23. Uniqueness of equilibrium in a multi-country Ricardo model (with C.A. Wilson), 2005, in Frontiers in Applied General Equilibrium Modeling: In Honor of Herbert Scarf, eds. T.J. Kehoe, T.N. Srinivasan and J. Whalley, Cambridge University Press.

References

1. Arrow, K. J., H.Block, and L.Hurwicz (1959): ``On the stability of the competitive equilibrium, II," Econometrica, 27, 82–109.

2. Arrow, K.J., and G.Debreu (1954): ``Existence of an equilibrium for a competitive economy,” Econometrica, 22, 265–290.

3. Arrow, K.J., T.Harris, and J. Marschak (1951): ``Optimal inventory policy,” Econometrica, 19, 250–272.

4. Arrow, K.J., and L.Hurwicz (1958): ``On the stability of the competitive equilibrium, I," Econometrica, 26, 522–552.

5. Aumann, R.J. (1964): ``Markets with a continuum of traders,” Econometrica, 32, 39–50.

6. Brouwer, L.E.J. (1912):``Über Abbildungen von Mannigfaltigkeiten,” Mathematische Annalen, 71, 97-115.

7. Debreu, G. (1959): Theory of Value, Yale University Press, New Haven.

8. Edgeworth, F.Y. (1881): Mathematical Psychics, Kegan Paul, London.

9. Koopmans, T.C., and M. Beckmann (1957): ``Assignment problems and the location of economic activities,” Econometrica, 25, 53–76.

10. Lemke, C.E., and J.T. Howson (1964): ``Equilibrium points of Bi-matrix games,” SIAM Journal of Applied Mathematics, 12, 413–423.

11. Lerner, A. (1944): The Economics of Control, Macmillan, New York.

12. Mantel, R.R. (1966): Toward a Constructive Proof of the Existence of Equilibrium in a Competitive Economy, Yale University Ph.D. thesis (published in Yale Economic Essays, 8 (1968), 155-196).

13. McKenzie, L.W. (1959): ``On the existence of general equilibrium for a competitive market,” Econometrica, 27, 54–71.

14. Samuelson, P. (1941): ``The stability of equilibrium: comparative statics and dynamics," Econometrica, 19, 97–120.

15. Shoven, J.B., and J.Whalley (1992): Applying General Equilibrium, Cambridge University Press, New York.

16. Shubik, M., (1959): ``Edgeworth market games.” In Tucker, A.W., and R.D.Luce, eds., Contributions to the Theory of Games, IV. Princeton University Press, 267–278.

17. Smith, A., (1776): The Wealth of Nations, W.P.Strahan and T. Cadell, London.

18. Sperner, E. (1928): ``Neur Beweis für die Invarianz der Dimensionszahl und des Gebietes,” Abh.a.d. Math.Sem. d. Univ. Hamburg, 6, 265–272.

19. Todd, M.J., (1976): The Computation of Fixed Points and Applications, Springer-Verlag, Berlin.

20. Tohmé, F. (2006): ``Rolf Mantel and the computability of general equilibria: On the origins of the Sonnenschein-Mantel-Debreu theorem”, History of Political Economy, 38 (SUPPL.), 213-227.

21. Von Neumann, J., and O.Morgenstern (1947): Theory of Games and Economic Behavior, Princeton University Press, Princeton.

22. Wald, A., (1936): ``Über einige Gleichungssysteme der mathematischen Ökonomie,” Zeitschrift für Nationalökonomie, 7, 637–670.

23. Walras, L., (1874): Eléments ďEconomie Politique Pure. Corbaz, Lausanne.

24. Yang, Z., (1999): Computing Equilibria and Fixed Points, Kluwer Academic Publishers, Boston.

External links

• Personal web site
• The works of Herbert Scarf
• Herbert Scarf at the Mathematics Genealogy Project