Combinatorics, or combinatorial mathematics, is a difficult field to define. It cuts across many branches of mathematics yet a mathematician will clearly sense which problems are of a combinatorial nature. Perhaps the simplest definition is that it is concerned with configurations or arrangements of elements, usually finite in number, into sets. Three basic types of problem are posed. Firstly the existence of certain configurations; secondly, once their existence is proved, the classification or enumeration of the configurations meeting the requirements imposed; and thirdly the construction of algorithms for finding the configurations in question.

Why has combinatorics been the poor relation of the mathematical tools used in economics? The first and most obvious explanation is that the evolution of theoretical or mathematical economics has led us in the opposite direction to that in which combinatorics is useful. Ever since the ‘marginal revolution’ there has been clear emphasis on the use of differential methods and an implicit acceptance of the perfect divisibility of goods. Indeed if we consider the most elaborate extension of the basic Arrow–Debreu model it is to one in which there is a continuum of agents and a continuum of goods. This is just the sort of context in which the combinatoric approach is of little use.

Yet the economist may well feel that discrete problems are of importance and that indeed the world is best represented as one where goods are not infinitely divisible and where the number of agents is finite. Now given the standard assumptions of convexity, at least in production, the perfectly competitive model may indeed be regarded as a satisfactory ideal or limiting case and the finiteness of a real economy is just an inconvenience. In this case it would seem that combinatorics has little role to play.

However although we may consider taking divisibility as a reasonable idealization in a large economy (even this may be questioned – seeIndivisibilities) as soon as convexity is dropped as an assumption for production the problem of finiteness cannot be avoided. If there are increasing returns to scale there will be a minimum profitable plant size and there will be a fundamental indivisibility. At this point combinatoric analysis comes back into its own, and no argument can be made for using infinitely divisible goods as a reasonable approximation. Thus the existence of non-convexities will lead us back into a situation which may, for example, be game-like and in which we will be looking for a solution with a finite number of large plants.

This is to suggest that realism may lead us away from the smooth differential world to which economists are accustomed towards a discrete one in which combinatorics plays an important role.

Nevertheless, till now, finiteness and the combinatoric approach have not occupied a significant place in economics. However, some examples will show that certain branches, although not central, have made extensive use of such an approach.

The development of mathematical programming, in particular of linear programming, has relied particularly on combinatorics. The algorithms developed to solve such problems are essentially combinatoric. Many economic models have been built on the basis of the ‘activity analysis’ or fixed coefficient production approach.

Game theory has made extensive use of combinatorics and provides an interesting example of how the combinatoric approach can be confronted with one using continuous functions or compact sets.

Combinatoric arguments are used to show that the core of a balanced game is non-empty. A simple argument shows that a market game is balanced and further it can be shown that the only allocations remaining if we replicate a given economy are competitive. This leads us to the conclusion that a competitive or Walrasian allocation exists. Now the latter statement is known to be equivalent to the existence of a fixed point for a continuous mapping. Thus we arrive by combinatorical methods at the same result as that obtained by an apparently very different tool.

This argument is reinforced by the fact that the algorithms developed for finding approximate competitive equilibria are essentially combinatoric in nature. They consist in systematically examining points in the price space, of evaluating the total excess demand of an economy at these points and finding a path which leads to a reduction in the excess demand until it is close to zero. Again, the approximation of fixed points of countinuous functions is obtained by a combinatoric approach.

There are many other examples of ways in which combinatoric analysis has proved useful. Arrow’s theorem on the impossibility of a social welfare function is typically proved in the case of a finite number of individuals faced with a finite number of social alternatives. The problem is to find a way of aggregating individual preference orders on these alternatives into a social order in a way which satisfies certain simple axioms. The usual line of proof consists of finding certain configurations of individual preferences which lead via the axioms to a contradiction with the existence of a social order. The reasoning here too is combinatoric. The introduction of graph theory to describe communication patterns in economics has brought into economic theory a field which has long been regarded as fundamentally combinatoric. The use of ‘matching’ models to analyse job search and unemployment is yet another example.

Whilst these few rather arbitrary examples show that combinatorial analysis has not been absent from economic theory it is also clear that it has not been central.

However, it seems likely that economics is to evolve towards the sort of models now widely studied in computer science, away from global optimization towards more simple forms of ‘rationality’ as embodied in simple automata. Furthermore the computation of equilibrium even for underlying continuous models is becoming increasingly important. All this together with a recognition of certain fundamental indivisibilities in economics is likely to move combinatorics to a much more central position on the stage of economic theory.

See Also