Computational Complexity For Linear Complementary Problems (LCPs) And Linear Programs (LPs)

1.0 Introduction

This post just states what I believe I know about the topic. I am interested in LCPs because the choice of the technique can be formulated as an LCP. Most of the references are beyond me.

2.0 Pivoting Algorithms and Interior Point Algorithms

Two types of algorithms exist for both LCPs and LPs:

• Pivoting methods: These methods start out with a feasible solution, more or less. This solution is improved by improving the basis, until an optimal feasible solution is found, if one exists.
• Interior point methods: These methods work outward, iteratively imposing constraints, until an optimal feasible solution is found.

George Dantzig's simplex algorithm is a pivoting method for LPs. The Lemke algorithm, originally formulated for bimatrix games, is a pivoting method for LCPs. The AI overview, from a Goole search, tells me:

"The Lemke algorithm is a general complementary pivoting method for solving linear complementarity problems (LCPs), whereas the Lemke–Howson algorithm is a specialized combinatorial variant specifically designed to find a Nash equilibrium in two-player (bimatrix) games."

For my purposes, then, I want to focus on the Lemke algorithm, not the Lemke-Howson algorithm.

While not the first, the Karmarkar algorithm is an interior point method for LPs.

3.0 Complexity Classes

A general LCP is NP-complete (Chung 1989). The general LP falls into the complexity class P.

A problem is in the complexity class NP if a non-deterministic algorithm exists that can solve it in polynomial time. If so, a deterministic algorithm also exists that can check a solution in polynomial time. Deterministic algorithms exist for solving problems in the complexity class P in polynomial time. Whether P is equal to NP, or merely a proper subset, is the great unsolved problem in computer science. If an algorithm can be found to solve any one of a number of problems in polynomial time, the equality of P and NP follows. Such problems, like the LCP, are said to be NP-complete (Cook 1983).

Some problems in algorithmic game theory are in complexity classes that lie between P and NP, if these complexity classes are indeed unequal (Roughgarden 2010). The class Polynomial Parity Arguments on Directed graphs (PPAD) is one of these intermediate classes.

4.0 Complexity of Algorithms for Solving LPs

The worst case of some interior point methods for solving LPs is polynomial time. The worst case for the simplex method is exponential, which is worse than polynomial time. The simplex method mostly performs in practice in polynomial time and better than interior point methods. For a long time, why this is so was a mystery.

Daniel Spielman and Shang-Hua Teng solved this mystery in 2004. They were awarded the Gödel prize a couple of year later for this work.

5.0 Special Cases of the LCP

Algorithms for solving the LCP in polynomial time have been found in special cases. These algorithms take advantage of special structures or properties of the square matrix that arises in the specification of a LCP. For example, Cottle, Pang, & Stone (2009) note the existence of a polynomial-time, interior-point algorithm for a LCP with a positive semi-definite matrix.

The solution to the LCP for specifying a long period position can be solved in polynomial time if the given rates of growth and profits are equal.

References

• Chung, S.-J. (1989). NP-completeness of the linear complementarity problem, Journal of Optimization Theory and Applications 60(3), pp. 393-399
• Cook, Stephen A. (1983) An overview of computational complexity, Communications of the ACM 26(6): 401-408.
• Cottle, Richard W., Jong-Shi Pang, & Richard E. Stone (1992, 2009) The Linear Complementary Problem, Society for Industrial and Applied Mathematics
• Karmarkar, N. (1984) A new polynomial-time algorithm for linear programming, Combinatorica 4: 373-395.
• Lemke, Carlton (1965) Bimatrix equilibrium points and mathematical programming, Management Science 11(7): 681-689.
• Lemke, C. E. & Howson, J. T. (1964). Equilibrium points of bimatrix games, SIAM Journal on Applied Mathematics 12 (2): 413–423
• Murty, Katta G. (1997) Linear Complementarity, Linear and Nonlinear Programming, Lemgo, Germany: Heldermann Verlag.
• Roughgarden, Tim. (2010) Algorithmic game theory, Communications of the ACM 53(7): 78-86.
• Spielman, Daniel A. & Shang-Hua Teng (2004) Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM 51(3): 385–463.

Marx Did Not Care About Prices

Richard Wolff Responding To A Question On The Transformation Problem

The marginal revolution of the 1870s not only changed the answers. It also changed the questions. Neither the classical economists nor Karl Marx were studying the allocation of scarce resources among alternate uses.

The dynamic vision of classical political economy was about the wealth of nations, and the accumulation of capital. The latter concern meant classical political economists cared about distribution. They treated workers as consuming their wages, the landed gentry as spending their income on luxuries, and capitalists as investing their income back into growing their wealth. The classical political economists found they needed to know something about value or prices to pursue their main concerns. The theory of value was an unavoidable complication.

At one point, David Ricardo deplored the need for this complication:

"...After all[,] the great questions of Rent, Wages, and Profits must be explained by the proportions in which the whole produce is divided between landlords, capitalists, and labourers, and which are not essentially connected with the doctrine of value...

...The greater the portion of the result of labour that is given to the labourer, the smaller must be the rate of profits, and vice versa. Now this portion must essentially depend on the facility of producing the necessaries of the labourer - if the facility be great, a small proportion of any commodity, the result of capital and labour, will be sufficient to furnish the labourer with necessaries, and consequently profits will be high." -- David Ricardo, letter to McCulloch, 13 June 1820

Karl Marx took over this problem, to a considerable extent. In 1904, Hilferding tried to explain:

"In striking contrast with Böhm-Bawerk, Marx looks upon the theory of value, not as the means for ascertaining prices, but as the means for discovering the laws of motion of capitalist society." -- Rudolf Hilferding, Böhm-Bawerk's Criticism of Marx, Chapter 1: Value as an economic category

Joan Robinson had a low opinion of Marx's labor theory of value. But she was very clear that Marx's point was not about prices:

"Marshall did something much more effective than changing the answer. He changed the question. For Ricardo the Theory of Value was a means of studying the distribution of total output between wages, rent and profit, each considered as a whole. This is a big question. Marshall turned the meaning of Value into a little question: Why does an egg cost more than a cup of tea? It may be a small question but it is a very difficult and complicated one. It takes a lot of time and algebra to work out the theory of it. So it kept all Marshall's pupils preoccupied for fifty years. They had no time to think about the big question, or even to remember that there was a big question, because they had to keep their noses right down to the grindstone, working out the theory of the price of a cup of tea." -- Joan Robinson, 1953, An open letter from a Keynesian to a Marxist

I conclude with a bit from Richard Wolff, above:

"Marx's labor theory of value... has more to do with this notion of how labor is allocated in a society... Marx was not - let me put it another way. When I teach in the American university system, we begin by assuming all students want to understand the great mystery of economics which is why is the price of something what it is. Why is the price of a hamburger $5 and the price of a Mercedes much more than that? And we begin. That's very nice. It's perfectly good to make an economics built of that question. I'm going to now exaggerate to make my point. Marx wasn't interested in that, and I'm not either. I got many more interesting things I want to understand about this economy than why the prices of things are what they are. I understand if you're a capitalist you're very concerned about prices, but if you’re somebody else, you might have all sorts - you might be interested, but you have much more higher priority subjects... Marx is coming at it with a different agenda. And so he starts in a different place and takes it in a different way." -- Richard Wolff

Marx was interested in how can there be a return to ownership, at all, in a competitive market economy.

On The Suppression Of Lorie Tarshis' Keynesian Textbook

The General Theory of Employment, Interest, and Money, by John Maynard Keynes, precipitated an intellectual revolution. It presents a macroeconomic theory that supports policies for eliminating severe depressions in capitalist societies. Some economists produced their own works in trying to understand it. I think of Joan Robinson's Essays in the Theory of Employment & Introduction to the Theory of Employment Alvin Hansen's A Guide To Keynes, for example, or A. C. Pigou's Keynes's General Theory: A retrospective view. Given Keynes' attacks on Pigou's work, the last is fairly extraordinary.

Lorie Tarshis wrote the first undergraduate textbook, from a Keynesian perspective, for students in the United States. Initially, it seemed that this textbook would be successful. Here is an account at the time of an ignorant, reactionary intercession into university teaching:

"Once the atmosphere of hysteria is ignited, the most dubious creatures rush to exploit the honest fears of decent Americans. The recent textbook witch-hunt provides an edifying example. In August, 1947, on the letterhead of an organization calling itself The National Economic Council, Inc., a man named Merwin K. Hart wrote to every member of the boards of trustees of colleges using Elements of Economics, an economics text written by Professor Lorie Tarshis of Stanford University. An enclosed review denounced the book for its exposition of the doctrines of Lord Keynes and identified Keynesianism as a form of Marxism.

Hart's letter had an immediate effect. Organizations of small businessmen passed resolutions in his support. Trustees and alumni wrote outraged letters to college presidents. Yet who was Merwin K. Hart? His record had long been known to students of the American proto-fascist demimonde. He revealed his own notion of Americanism some months later when, in a speech before Harvard's Free Enterprise Society, he inveighed against the Marshall Plan and 'the international Jewish group which controls our foreign policy.' And, at the height of Hart's campaign, the ideas of Keynes were under equal brutal and ignorant attack from another source: that is, from the Communists themselves. 'Keynesianism,' wrote William Z. Foster, 'collides with Marxism at every point.' Foster and Hart, in fact, agreed in objecting not only to Keynes but to such proposals as the Marshall Plan as well; by the kind of reasoning Hart uses on other people, he should have had to classify himself as a Moscow agent.

Fortunately enough college presidents knew Hart's record to stand up courageously to the uproar. Dr. A. I. Strand of Oregon State College wrote bluntly to Hart: 'Your hands are dirty and you smell of foul associations, and now you have the effrontery to set yourself up as the protector of American youth! A greater insult to education has never come to my attention.' The American Economic Association eventually appointed a special committee to deal with the attacks on the Tarshis book and on other economic texts.

The issue is more fundamental than simply the fatuousness of mistaking Keynes for Karl Marx. If all Communism meant was deficit financing, then it would be hard to persuade anyone that it was very terrible. A genuinely Communist textbook would be unacceptable for its distortions of fact, as a Communist teacher, who imported his party views into the classroom, would be an incompetent teacher. The deeper issue is the freedom of the teacher to teach his subject according to his most responsible understanding of it, and not according to the ukase of a board of trustees, a legislature, a political party or a foreign country." -- Arthur Schlesinger, Jr. 1949. The Vital Center: The Politics of Freedom. Boston: Houghton Mifflin: 205-207.

Schlesinger turned out to be wrong. Tarshis’ textbook was successfully suppressed. By the way, my sometime correspondent, William F. Buckley, was equally ignorant and vile in God and Man at Yale. Paul Samuelson, in writing his textbook, consciously tried to avoid Tarshis' fate. He wrote lawyer-like.

Schlesinger's book is depressing. He deplores the ‘lurid atmosphere’ created by Attorney General Mitchell Palmer, with his 'notorious red hunts'. He says the House Un-American Activities Committee (HUAC) is going too far. But, as you can see above, Schlesinger, one of the co-founders of the Americans for Democratic Action (ADA), is all about denying communists employment. He says that the US State Department should be promoting the non-communist left (NCL) in Europe and elsewhere. We need a Third Force. Perhaps Graham Greene read this before writing his novel, A Quiet American. Pyle, the title character, sponsors murder and mayhem in Vietnam in order to find this Third Force. Schlesinger did not have his priorites sorted.

If this is the best of liberalism, I do not want it. (I have yet to read Sam Moyn's 2023 book, Liberalism Against Itself: Cold War Intellectuals and the Making of Our Times.) There will be none of Matthew McManus' The Political Theory of Liberal Socialism if liberals remain afraid of socialism.

Histories Of Heterodox Economics: A Small Bibliography

This is an aspirational bibliography in that I have not read Mata's book. I long ago read his doctoral thesis. I probably have forgotton most of the other books. Katzner's book, about the economics department at the University of Massachusetts at Amherst, is only a memoir in the last chapter.

• Donald W. Katzner. 2011. At the Edge of Camelot: Debating Economics in Turbulent Times. Oxford.
• J. E. King. 2004. A History of Post Keynesian Economics since 1936. Edward Elgar.
• Frederick S. Lee. 2011. A History of Heterodx Economics: Challenging the Mainstream in the Twentieth Century. Routledge.
• Tiago Mata. 2026. Radical Expectations: How the New Left Changed Economics. Cambridge.

Sraffa On Marx Being Approximately Correct

Sraffa (1960) is an epoch-making book. It is a part of a demonstration that neoclassical economic theory is incoherent and incorrect.

Ian Steedman created a stir in the 1970s. He turns Sraffa's theory against some aspects of Marx's theory of value. He argues that labor values are redundant in explaining prices of production and the rate of profits. This was a novel accusation. He also argues that many analyses, such as the effects of variations in the length of the working day, can be made at the level of prices of production.

Sraffa did not see his book as refuting Marx, either before or after publication. John Eaton wrote a review of Sraffa's book. Eaton was the pen name of Stephen Bodington. Sraffa wrote him a letter, in 1961, after this review. A draft is in Sraffa's archives:

"Dear Bodington,

It was most kind of you to send me through M[aurice] D[obb] an offprint of your article in Societa. I am grateful for this splendid review, which presents the subject in a more lucid and interesting way than I should have thought possible; it certainly sets a high standard for the discussion which I hope it will stimulate [initiate?].

should like to take this opportunity to try and give a brief answer to the question you hint at, when you express some doubts as to the usefulness of the construction of the 'Standard Commodity'. First of all I am convinced that it does represent a real property of the econ[omic] system; and while this could be described in other ways, it should not be ignored, even if it did not find immediate application. It is, however, applied in one or two cases in the book: For instance, in the proof that there is a unique set of all-positive prices in the case of single-product industries. (the proof isn't without importance for the number of sets of solutions is very large, being equal to the number of commodities in the system; if any appreciable proportion of these sets could be all-positive, a large element of uncertainty would be introduced.) Another application is for defining basic and non-b[asic] comm[oditie]s. (This can be done intuitively in a system of s[ingle]-p[roduct] industries, but in complicated cases of multi-product industries, this or some equiv[alent] math[ematical] construction is, I think, necessary.)

There are besides, many possible applications, which I have not mentioned in the book, in problems discussed by Marx. Take, e.g., the determination of a general rate of profits, from the rate of surplus value. Marx takes an average of the rates of profits, obtained from the proportion of the different commodities on the basis of 'values', and he gets, as he acknowledges, an approximately correct result. An exact result could however be obtained by taking, instead of a simple average, a weighted average: and it can be shown that the appropriate weights can be derived directly from the proportions in which the comm[odities] enter the st[andard] comm[odity]. Similarly, in th application of M[arx]'s notion of the comm[odity] produced by 'a cap[ital] of av[erage] org[anic] comp[osition]': for an exact result the average must be found in the same way. In other words, that comm[odity] is the st[andard] comm[odity].

I doubt, however, that it would at the present [time?] be wise to direct the discussion onto these lines.

With kind regards,

Yours sincerely," -- Piero Sraffa. D3.12.111/132

I cite Eatwell (1975) in explaining how the standard commodity is a commodity of average organic composition of capital. It provides a solution of the transformation problem.

In finding the general rate of profits, Sraffa starts with the value rate of profits in each industry. The value rate of profits is the ratio of surplus value to the sum of the value of variable capital and constant capital, with each found in the system of labor values. The rate of profits in the system of price of production is the weighted sum of the value rates of profits, where the weights are a modification of the weights for Sraffa's standard system. This weighted sum is one way that Sraffa draws a connection between labor values and prices of production. I have written about this before. Perri (2023) explains further.

Inasmuch as Marx's solution of the transformation problem is not exactly correct, it can be and has been set right.

References

• Enrico Bellino. 2006. Banfi, Eaton, Dobb and Johnson review Sraffa's Production of Commodities. Storia Del Pensiero Economico
• John Eatwell. 1975. Mr. Sraffa's standard commodity and the rate of exploitation. Quarterly Journal of Economics. 89(4): 543-555.
• Stefano Perri. 2023. Sraffa's response to Eaton's review: a note on the standard commodity and Marx's general profit rate.
• Piero Sraffa. 1960. Production of Commodities by Means of Commodities: A Prelude to a Critique of Economic Theory. Cambridge University Press.
• Ian Steedman. 1981. Marx after Sraffa. Verso.

Keen On Steedman On Marx

I have been reading Steve Keen's 1990 doctoral thesis. As I understand it, Marx explains the origin of surplus value, in Capital, by the distinction between the use value and exchange value of labor power. The use value is the labor expended under the capitalist's direction. This labor is generally more than the labor embodied in labor power. The labor embodied in labor power, under volume 1 assumptions, is the money wage.

Keen argues that Rudolf Hilferding's treatment of skilled labor is an application of Marx's use value/exchange value dialetic. Skilled labor is to be explained by the training that goes into upgrading a worker's skill. The value created by skilled labor is not to be explained by the transfer of the labor embodied in skilled labor as being depreciated over time. Hilferding writes, "The labor of the technical educator thus transmits, not only value (which manifests itself in the form of the higher wage), but in addition its own value-creating power." The value created by a skilled worker in a hour of time is not required to be in the same ratio to the value created by a unskilled laborer in a hour of time as the ratio of their respective wages. Their rates of exploitation can vary.

Why can this dialectic not apply to fixed capital, also known as machinery? According to Keen, Marx did momentarily so apply it in the Grundrisse. The use value of a drill, for example, is so many holes drilled over the life of the drill. But, at a more abstract level, the use value of the drill is a value-creating power. Just as the concrete labor performed by a particular kind of skilled laborer is, strictly speaking, incommeasurable with a particular expenditure of unskilled labor, so the concrete application of a drill is also incommeasurable. But, if you think of the one as having value-creating power, in units of abstract labor time, why cannot the other have value-creating power? If so, fixed capital is just as much a source of surplus value as labor power.

The point of this post, though, is to record a footnote for my commonplace book:

"Rosdolsky['s] contribution certainly called into question the traditional interpretation of Marx, but as for actual revisions of Marx's theory on the basis of Rosdolsky's work, little of merit has happened. Marxian theory in general has been in turmoil since the publication, at much the same time as The Making of Marx's Capital was translated into English, of Steedman's Marx after Sraffa (NLB, London, 1977). In fact Sraffian criticism of Marx predates Steedman's book - as Meek's second edition clearly illustrates. However Steedman's work was the most accessible of these critiques, and the most strident. Steedman's demonstration of the implications for the labour theory of value of Sraffian analysis has left Marxism in disarray, with many deserting the fold. Meek's introduction and appendix to his second edition of Studies , and his Smith, Marx and After (Chapman and Hall, London, 1977) imply that he was amongst the many inclined to this position. Those that remain are split into two camps, with one calling for the theory of value to be dropped from Marxism altogether (l.c. Carling, Hodgson, Bose) while the other argues that value, somehow, is fundamental. This second camp is itself heavily divided, with some for business as usual along the lines of the traditional interpretation (l.c. Sweezy and Shaikh), others explaining surplus on the basis of unequal exchange (l.c. Desai, Bowles and Gintis), and still others seeking refuge in Marx's discussion of concrete versus abstract labour (l.c. Mohun, Carling, Sekine) or the non-commodity nature of labour (Bowles and Gintis, Mohun, Laibman)." -- Steve Keen (1990).

I should expand the list of references below to contain more than one.

I tend to not like dialectical arguments, and I try to confine my analysis to to the level of prices of production. I need to look at labor values, in some sense, in calculating the labor expended in a stationary state to produce a given net output. I do this, following, say, Samuelson, in noting a switch point exhibits capital-reversing. I can see why some find the level of prices of production too confining. Marx goes further in volume 1. For example, consider his presentation of primitive accumulation and the 'double freedom' of the worker under capitalism. Or his distinction between absolute and relative surplus value. Maybe a good analysis should treat labor values anyways.

In contrast to Steedman, Sraffa did not see his book as refuting Marx. After the publication of his book, he wrote a letter to John Eaton (pseudonym of Stephen Bodington) responding to Eaton's review (Perri 2023). In it, he started with the value rate of profits in each industry. The value rate of profits is the ratio of surplus value to the sum of the value of variable capital and constant capital, with each found in the system of labor values. The rate of profits in the system of price of production is the weighted sum of the value rates of profits, where the weights are a modification of the weights for Sraffa's standard system. This weighted sum is one way that Sraffa draws a connection between labor values and prices of production.

References

• Stefano Perri. 2023. Sraffa's response to Eaton's review: a note on the standard commodity and Marx's general profit rate

Yanis Varoufakis Has A Podcast

Varoufakis Interviewing Richard Wolff

I recently stumbled across the podcast Econoclasts. Usually, he co-hosts with the Wolfgang Munchau, a journalist. The above is an extract from the end of an episode where Varoufakis, by himself, interviews Richard Wolff.

It takes lots of study to show why marginalist economics is wrong. Varoufakis says that he no longer can recommend to students that they do that study. He asks Wolff what he does. Wolff responds:

"Well, here's what I tell them. And again I share much of what you have to say. In the ten years I spent at Harvard, Yale, and Stanford, I had to learn, I had to teach neoclassical microeconomics and Keynesian macroeconomics and all the rest. I believed then as I guess you did, too, that this was necessary. I had to understand how the system, not just how it worked, but how it rationalized itself, how it imagined itself to be working.

I did learn early on that the system also understands that dichotomy. So, it has economics departments who develop the ideological cover, as you put it, the rationale, why it all works out for an optimal - look at the language - an equilibrium - more silly language, you know - a system that is neither optimal nor presenting itself as all of that.

And then they have a business school where you actually learn a little bit about how to market something, how to go. They recognize the separation of function.

So, I say to students, you have to do something else, which I had to figure out how to do. I'm going to save you the time. And they look at me, but this is what I do, and I'm answering your question. You have to learn Marxian economics. You do. You have to immerse yourself in the volumes of Capital, in the other literature. Not because everything is clear there, it isn't. Not because there aren't contradictions, there are. Not because there's nothing in neoclassical economics you can't make use of. It's not that.

It's that if you think what I am doing is interesting, it's not me. And it's not what I got at Harvard and Yale. What it is, it comes out of trying to squeeze useful understanding out of the Marxian tradition, separated from the propaganda and from the mistakes and the lessons that weren't learned that should have been, in order to do that - you have to do, and the university cannot do that for you precisely because it fits your description. It’s not - it could care less.

It never was interested in - I never had a class in 10 years and except for Paul Baran, I never had a class in which anybody ever put together a Marxian idea, a neoclassical idea, and then went with us as students through what they had to say, where they were silent and shouldn't have been, where ' etc., etc. None of that was ever done. I had to do all that myself or with a few other students. But the payoff is you get a way of thinking, a way of posing questions that you can then use for all of the new material that Marx, you know, died long before it became relevant.

You know that you try to do that when you try to understand the Cloud. What does the Cloud make possible? What are these conglomerations of wealth and power able to do that capitalists couldn't do before? Where does that take us? Where are the obstacles? What is our best - You need a critical mentality.

And I know many people believe they can develop that on their own. I don't think so. I think if you really want to get beyond Marx, which is fine, you got to go through it to get beyond it. You can't skip over it At least, I’ve never seen anyone pull that off." -- Richard Wolff

I learned Marx on my own. It would be challenging to get through even the first volume of Capital in a semester. The teacher could use one of a number of textbooks. (For some reason, I do not have Resnick and Wolff's Contending Economic Theories in that list.)