NSF CCF director and CS theorist Sampath Kannan talked about similarities between CS and econ: Both deal with human-created artifacts and both talk about understanding the possible and the impossible. I would argue that while computers are a human-created artifact, computation itself is a natural process. I suppose an economists might make a similar argument.
Most importantly Sampath talked about the strong support of the NSF in both CS and Econ to focus more on these communities. The NSF Econ program office Nancy Lutz also promoted this view talking about the fondness of math in both fields.
Much of my research in the last couple of years has been looking at ways to apply tools of computational complexity to economic models which is what I'll be talking about later today. Can we harness the computational powers of "the market"? How does agents of limited computational ability change the outcomes of economic situations? Can we use computation to help explain economics phenomenon? Somehow I need to talk more complexity theorists to work on these problems. Why should algorithms people have all the fun?
On that note the accepted papers for SODA is out and Noam picks out the ones related to CS/Econ issues.
Both CS and Economics are social sciences which make use of math as a tool.
ReplyDeleteSome of us think CS is math, which is a constraining view on CS and hurts its scope and applicability.
can you please sent me relationship between software engineering and ecnomics??
DeleteI have a lot of sympathy for Kamal Jain's camp ... a serious question is: What does the CS have to say about this week's Paul Krugman column How Did Economists Get It So Wrong?
ReplyDeleteIt seems pretty clear that in the 21st century, all branches of engineering (including CS) will evolve into "yellow book" disciplines ... in the sense that higher levels of abstraction will be embraced ... but isn't also clear that these next-generation yellow books will have to consist of more than axioms, proofs, and theorems?
Economic is a case in point. As Krugman argues, economists (as an academic community) unwisely embraced irrelevant axioms in order to more easily prove elegant theorems ... doesn't this amount to a cognitive "linearity trap" (as the QIS/QIT community calls it) that all of the engineering professions, including CS, would be prudent to avoid?
Hate to be so off-topic, but did anyone ever post on the blogosphere about who got jobs where for this fall? Or is that *still* in process? I'm very interested in how the poor economy affected CS theory hiring, and I'm sure many others are too. Maybe I missed it?
ReplyDeleteThey have not even posted the list of CI fellow recipients even though the awards were given about two months ago.
ReplyDeleteIMHO, anonymous' post is not off-topic.
ReplyDeleteBecause if there were a demonstrably good answer to the question "What does CS have to say about this week's Paul Krugman column How Did Economists Get It So Wrong?" ... then perhaps the (academic) CS job market would not be so dismal ... for the common-sense reason that CS would be demonstrably relevant to restoring value to planetary-scale investments and enterprises.
If you consider CS as Social Science (a view I have posted on this blog in the past) then you would see there are many more interdisciplines, besides Algorithmic Game Theory. For an example, business science is an integration of "user experience" and "business models", the former component is CS and the latter is economics.
ReplyDeleteThese interdisciplines are very important and add values on top of their respective components. For an example, it is very hard to imagine that pure economists would have invented generalized second price auction as used in search advertising. Part of the justification of generalized second price auction is the computational and conceptual simplicity.
My own view is that CS is a triangle, with engineering, social science, and objective science(math) as its three corners. Earlier people mostly used computers in their work, so we researchers mostly focused on the side consisting of engineering and objective science. But now people use computers everywhere in their daily lives, so the social aspect is becoming more and more important. Indeed, if you see CS theory in the last 10 years, we are continously moving towards the centroid of this triangle. Game Theory as such is a social science (individual rationality is a social axiom.)
I think many researchers in my own company (Microsoft) also like to study the integration of CS in our daily social lives. Our group (Theory) has spun an entire research center inspired to study the centroid of this triangle.
"Hate to be so off-topic, but did anyone ever post on the blogosphere about who got jobs where for this fall?"
ReplyDeleteThis information should be kept secret, so as to keep new graduate students from knowing what they are getting into. If your advisor is in the network, then he might be willing to help you out.
Last year's hiring cycle?
ReplyDeleteCostis -> MIT
Nina -> GAtech
Prasad -> GAtech
Chris -> GAtech
Alexandr -> Microsoft
Lots of people -> MSR and Princeton post-docs
Costis and Nina were from the year before and the list was very incomplete:
ReplyDeletePrasad -> GaTech
Chris -> GaTech
Anup -> Washington
Yury -> TTI-Chicago
Mohit -> McGill
Alexandr -> Microsoft SV
Satyen -> Yahoo
Lots of people -> MSR and Princeton post-docs
Others?
The economists at the workshop were so quick to point out that Krugman's article should have been called How did macro-economists get it wrong?
ReplyDeleteRyan W. -> IBM Almaden (postdoc?)
ReplyDeleteVirginia V. -> Berkeley (CI fellow)
Katrina L. -> Cornell (postdoc?)
Who are the other CI fellows in theory? Was there only one?
Lance says: ...Krugman's article should have been called How did macro-economists get it wrong?
ReplyDeleteOn the other hand, we have Reinhard Selten's aphorism: Game theory is for proving theorems, not for playing games.
Supposing that the micro-economics community may similarly have "got it wrong", is it clear that anyone would ever find this out? Or care?
I'm not saying I agree with Selton---in fact, I definitely disagree---but given recent economic events, both inside and outside of academia, don't these points of view need to be explicitly rebutted?
The graduating theory students from UCI this year:
ReplyDeleteKevin Wortman => Cal State Fullerton (non-research university)
Nodari Sitchinava => postdoc at Aarhus, Denmark
Two others that I know of from the University of Utrecht:
Rodrigo Silveira => postdoc in Barcelona
Maarten Löffler => postdoc at UCI
There seems to be a much higher than normal number of accepted SODA papers that have all authors from outside the US. Is this true? Or is it the same as years past?
ReplyDeletecan you please sent me relationship b/w software engineering and ecnomics??
DeleteAlso Cora Borradaile is moving from a postdoc at Waterloo to a faculty position at Oregon State U.
ReplyDeleteJust like temperature is an average of particles motion, macro economics share a similar relationship with microeconomics.
ReplyDeleteThe entire scheme of accountability free house loans is a micro-economics phenomenon. On the web there are numeorus examples where micro-economists proved out to be wrong.
Of course, this is true with any social science, so there is no reason to defend this. Are doctors wrong when patient die under their treatment? No. You have to also look at the records of those patients too who lived under their treatment.
Overall macro-economics is a solid science with a good track record of success. You could see one bubble or recession, but then you should also see that the same system has fueled the economic expansion for a much longer time. The system self corrects with such a recession is also a success of macro-economics.
Kamal Jain said [this, that, and the other example] are successes of macro- and micro-economics]
ReplyDeleteWith respect, Kamal, doesn't your post specify criteria of success that are sufficiently low, that every academic discipline is (by definition) successful?
If we set the bar to a higher, more realistic standard ... for example "Successful academic enterprises are those that substantially increase the likelihood that the end of the 21st century will witness a peaceful, prosperous, healthy planet with ten billion people on it" -- then how would you rate the profession of academic economics?
John, my response was directed towards Lance posts. I do not think micro-economists should simply transfer the blame to macro-economists. BTW, by my research, I am closer to micro-economics. I still see gaps and shortcomings in my own work too, and seek to align with reality.
ReplyDeleteI think the marriage of CS and Economics is like match made in heavens. CS do worst case analysis (which is pessimistic), and Economists have this notion of rational people (which is optimistic), and I hope we would get to some midpoint at some near future.
What's the next "theory crossover" research bubble after the CS/Econ one bursts (~5 years)?
ReplyDeleteI'm placing my bets on comp bio. Logarithmic approximation ratios on unrealistic protein-folding models!
Kamal, I am mainly in agreement with your posts ... which in turn are reasonably consonant with the themes that were voiced in the recent five-part Nature series "Meetings that changed the World".
ReplyDeleteOf course, most academic meetings don't change the world all that much ... leading one Nature editorialist to dyspepticly assert: "Scientists these days rarely expect to hear much new science at a conference ... all too often, meetings lack clarity of purpose and seem hastily constructed."
Maybe this Nature editorialist was just having a bad day? Because I did attend three meetings this summer whose union was (IMHO) pretty world-changing ... did anyone else have this experience?
Because I did attend three meetings this summer whose union was (IMHO) pretty world-changing ...
ReplyDeleteSo don't leave us hanging -- tell us what they were and how they changed the world!
I did attend three meetings this summer whose union was (IMHO) pretty world-changing ... did anyone else have this experience?
ReplyDeleteI attended three meetings this summer that have probably influenced my own life quite bit (and perhaps I can influence the world). I attended the Molecular Programming conference for the first time, and got a much better sense of the experimental state of the art, and how theory might play a role in advancing practice. I attended PODC 2009, and gained a co-author who suggested a project that seems quite exciting. I attended the Barriers Workshop, and I can't pinpoint something specific I "got" out of it, but speaking vaguely, I think I have a better intuition for how complexity plays a role in other questions of computer science.
I think the world only changes if human beings change it. Whether I gained tools that will help me change the world -- and whether I choose to make use of those tools -- only time will tell.
Overall macro-economics is a solid science with a good track record of success. You could see one bubble or recession, but then you should also see that the same system has fueled the economic expansion for a much longer time. The system self corrects with such a recession is also a success of macro-economics.
ReplyDeleteI respectfully disagree. If you read Krugman's article, he clearly points out to the fact that macro-economics theory today has no place for recession, and this notion of recession being a self-correction is like saying that wild fires are self-correction or earthquakes are self-correction. What system has fueled economic expansion? The fresh water school actually argues that govt. intervention (monetary or fiscal) does not help the economy. If you believe that, then the macroeconomists had no role in the growth. If you don't, they were giving you wrong advice all along. All this is made much worse by economists advising politicians on talking on talk shows with perfect certainity when they are simply defending their partisan/ideological agendas.
Put differently, no science can be called solid if it can be used to argue that large deficits are good for the economy as well as the converse in exactly the same situation. It is not sound. I thought such systems were called astrology.
...and Economists have this notion of rational people (which is optimistic),...
This is another misleading indoctination coming from the economists. The rationality assumption underlying all GT and econ is that people are infinitely rational and that they believe that others are infinitely rational, and they believe that everyone believes that everyone is rational,.... and so on.
This is a much much stronger assumption than rationality that is hidden under the word rationality.
Economists also realize that by their theories it is irrational to vote. Yet, more than 50% of the people do vote.
Somehow when arguing why markets are efficient, they forget that they just pointed out that more than half the population is irrational.
Talking of standards: imagine if engineering experts weigh in on the design of the bridge and it collapses after 10 years. I don't think you would be happy with hearing that it was a natural self-correction. Somehow image of a few tens of people falling and dying is more tragic-looking than that of millions of people losing their jobs because of causes well outside their control, though I am not sure it is actually any less tragic.
Both CS and Economics are social sciences which make use of math as a tool.
ReplyDeleteThere is no justification to this statement.
The theory of computing (ToC) has precisely the same relation to the empirical world as other branches of mathematics. Mathematics is, roughly put, the study of structures and quantities and their inter-relations. Algorithms can be viewed as mathematical objects, and indeed we can formalize all reasoning of ToC inside (say) ZFC. This is not the case for economics at large. We do not know, for instance, what are the axioms of economic behavior. But we do know what are the axioms of computing machines. They are extremely simple (putting aside questions of complexity).
The realization of an algorithm - which is an abstract or ideal object - in the empirical world, is precisely the same as the realization of a geometric object (e.g., triangle) in the empirical world:
If I implement Euclid's division algorithm with weeds in the forest, i.e., physically implement the steps in the algorithm with the help of weeds, I will end up with the correct number of weeds.
If I draw a triangle in the sand on the beach, I will get a shape whose sum of degrees is 180.
I do not see any difference between the two examples above.
But we do know what are the axioms of computing machines.
ReplyDeleteQuantum computing anyone?
They are extremely simple (putting aside questions of complexity).
Putting aside complexity is like saying that designing cars is trivial, shall we put aside friction.
The realization of an algorithm - which is an abstract or ideal object - in the empirical world,
The model of computation over which is implemented may radically alter the performance of the algorithm, in terms of its time complexity.
Quantum computing anyone?
ReplyDeleteQuantum computers cannot go beyond the computable functions. So putting aside complexity issues we know precisely the axioms, and they are simple. So quantum computers, are still inside ZFC.
Moreover, we may have two theories, one with classical axioms and the other quantum axioms, if you insist.
And thus we can also consider
complexity questions. This answers your first argument.
The model of computation over which is implemented may radically alter the performance of the algorithm, in terms of its time complexity.
I don't know what you mean by the phrase "over which is implemented", and how this is relevant here.
Also, the same arguments can be raised in mathematics:
"There are more geometries than the natural Euclidean geometry. So we don't know the axioms..",
or
"Implementing a triangle in physical reality is dependent on the medium on which it is drawn, etc."
Moreover, this is not the point of view or issues that concern ToC. We have, say, a lower bound on the number of comparisons one has to perform for a certain task. And this lower bound is universal and absolute, disregarding implementation issues.
Achieving results in ToC is by building the concept in the mind. Not in physical reality. This is precisely mathematics.
You might argue that you think that this is not what ToC should do. But this is not what we are arguing here (that is, what is ToC), rather putting forward a new agenda (what ToC should be).
There is no justification to this statement.
ReplyDeleteI said restrictive, and another word of a restriction is a subset. What you described in the rest of your comment is a subset of activities TCS folks do.
For an example, the upcoming social addition to TCS (such as algorithmic game theory) would not satisfy such a restrictive view and would not grow to its full applicability if forcedfully restricted to this subset of activities as described in the rest of your comment.
So putting aside complexity issues we know precisely the axioms, and they are simple.
ReplyDeleteSure, if we put aside complexity, then complexity is math. Any other insights you want to share with us?
Krugman focuses on the fact that in order to analyze macroeconomic questions mathematically, economists ended up over-simplifying and the result was that their models were incorrect. Do we risk the same thing with our algorithmic models of human action in game theory?
ReplyDeleteAt the moment "behavioral" economists seem to be ascendant. Does their work provide mathematical models that we can apply CS techniques to? There are a number of examples where the standard micro-economics approach of pure rational self-interest is not borne out (often in situations that involve cultural notions of "fairness" and "envy"). Can they be captured in the kinds of models that CS can analyze. Are they relaed to the analysis of repeated games?
Krugman focuses on the fact that in order to analyze macroeconomic questions mathematically, economists ended up over-simplifying and the result was that their models were incorrect. Do we risk the same thing with our algorithmic models of human action in game theory?
ReplyDeleteRisk the same thing? Oversimplification and consequent incorrectness are almost universal in algorithmic game theory. There are at best a handful of realistic scenarios being analyzed (and that's debatable). Everything else is totally implausible - it's not even taken seriously by the economists, as anything more than theoretical analysis of toy models.
Overall macro-economics is a solid science with a good track record of success.
ReplyDeleteKamal, this is farcical. Macro folks had a poor academic reputation before the bubble. Efficient Market Theory?? As someone who made the switch from Econ to CS, working in reality just feels better.
Efficient market theory is not the only thing in macro-economics. When I analyze a real world business situation, I not only analyze it from a micro-economics point of view (also called bottom up), but I also analyze it from macro-economics point of view too (also called top down constraint). It is quite rare that you would get a result opposing the bottom up constraint, and it is even rarer that you would get a result opposing the top down constraint.
ReplyDeleteIn fact the choice of a market is a single big decision which has a huge influence on a business outcome.
One of the hot topics in algorithmic game theory these days is advertising. Many papers do not talk about the macro-structure and talk only about the micro-structure. If the results do not stand the scrutiny of the macro-analysis, that they are not very applicable.
Of course we know that EMT does not work. But there is nothing suggested which works better than EMT. If you make an investment based on a theory that a person would willingly leave money on the table, then you are less likely to make money than believing in EMT (which essentially says that you can spread your investment to the entire market, or also called buying the market, or simply buying an index fund such as S&P or Dow Jones Industrial). Indeed there are not statistically significant number of investors who could beat these index funds consistently (you could find 1 in a 1000 fund managers who beats the market ten years in a row, but that should not be a surprise).
Oversimplification and consequent incorrectness are almost universal in algorithmic game theory.
ReplyDeleteThis is ok in the beginning provided that:
1. The results are explicitly labeled as toy examples.
2. There is a natural path to make the models more realistic, as the area becomes better understood.
Sure, if we put aside complexity, then complexity is math. Any other insights you want to share with us?
ReplyDeleteI said explicitly: if you want to consider quantum computation instead of classical computation (which is the only reason I said we can put aside complexity issues) one can just start from a simple set of axioms for that purpose.
And thus we can also consider
complexity questions. This answers your first argument.
For the second argument (that of applicability that effects complexity): please explain what is the difference between, e.g., proving a (complexity) lower bound on the number of comparisons needed to do for computing a certain function and proving a (mathematical) result in geometry. These are two absolute results, and they are not dependent on empirical factors. Proving complexity lower bounds of this absolute nature is what mainstream complexity theory does, and this is precisely mathematics.
please explain what is the difference between, e.g., proving a (complexity) lower bound on the number of comparisons needed to do for computing a certain function and proving a (mathematical) result in geometry.
ReplyDeleteEasy. The first is motivated by some real life considerations while the second one isn't.
It's the same difference between a physicist studying a string model with the hope of replacing the standard model, and a mathematician playing with branes just because they are cool mathematical objects.
Indeed there are not statistically significant number of investors who could beat these index funds consistently (you could find 1 in a 1000 fund managers who beats the market ten years in a row, but that should not be a surprise).
ReplyDeleteThis, in some sense, is an example of ketchup economics. Yes, an efficient market will have this property. But so will a game of roulette.
The primary argument of EMT is that the market absorbs all information and that the value of a stock is an indication of the companies value. I don't see, e.g., what changed at Google reduced it's value by half beween may 2008 and jan 2009.
Another way to ask whether stock valuations are in line with a company's worth is the following: suppose you were given stocks that you could not trade ever but only got the dividend from the company's profit for the rest of your life. Such a stock should be worth less since it has lower liquidity. But even so, would you pay half of the stock price? A tenth?
After all the information has been observed by the traders in an economic system, the system is supposed to behave as the game of roullette, e.g., the coins of the nature can't be observed before they are tossed.
ReplyDeleteIf you have an insider information in either a trading system or a gambling system, you could win. That's why insider info in the former is considered equivalent to cheating in the latter.
The value of stock can be reduced not only by what chages at the company, but what beliefs are changed about the company. I do not want to speculate about a particular company, but the beliefs of the people changed in the time period mentioned by you and that there is a probability of sky is falling. This coin was not actually tossed. So traders who belived that the sky would not fall, could have made some money with some probability, but could lose if the sky actually had fallen.
Regarding your last question, it depends upon the demand and supply, of how many such non-tradeable stocks are available and how many people have the natural spending pattern (e.g., a retiree may need that money as dividend itself). For an example, I can't trade my unvested Microsoft stocks. But if Microsoft guarantees my job and let me trade them, then I would get pretty much the current full value for them. In fact, if I have an account with a broker who let me short some of those stocks, I could actually get the full value of them today itself. So many variables come in to picture, one of them is trust.
So in your scenario, if that person is trusted, the person can't trade the stock but the person could short it.
If you disallow shorting then the value would be the intersection of demand and supply (and beliefs, since the underlined think is an stochatsic or even uncertain piece of instrument).
There are two hypothesis in your comment about what determines the value of a stock.
ReplyDelete1. Demand and supply.
But in usual microeconomics, I as a buyer have an externally determined valuation of the item. My remark was that the externally determined valuation, i.e. the expected time-adjusted dividend, does not seem to be related to the price of the item.
2.Based on all the available information, an all powerful entity could come up with the expected value of the company.
As far as I can tell, the central premise of EMT is that through demand and supply, the market determined price is the price in 2. Ther may be such a theorem under a setting where everyone is infinitely rational, everyone believes that everyone is infinitely rational, and so on ad infinitum, given infinite time for the price to stabilize. However, that does not seem to be borne out in practice. The stock market does not support such a claim. Experiments such as the baby-sitter market do not support that claim.
Consider a hypothetical setting where all traders on wall street believe that the price of X is going to temporariliy (say for several months) bubble up due to actions of irrational players (or due to inelasticity of the short term demand of X). Then as a trader, I can either buy X, feeding the bubble, making a short-term profit. Or not buy X, maybe short it, lose money in the short-term, see my (possibly irrational) customers withdraw their money and go to other profit-making traders, and go bankrupt. What would I do?
The fact that irrational players exist, or possibly even a false belief that irrational players exist is enough to break all your theorems, and break real markets.
Which came first, people behavior or our models? I think people behavior.
ReplyDeleteSo people can't be irrational ever. Our model could be incomplete in describing their behavior. This would be a problem with all branches of sciences, including objective sciences such as Physics.
Different branches of science would have this problem to different extent. So the right attitude is to argue w.r.t. our current understanding of the world. So if you need to argue EMT, then you need to put forward something which you believe provide better understanding than EMT (say Anti-EMT). Otherwise EMT provides certain level of understanding, better than other known theories. So it is a success, for now but open for future evolution.
Yeah, you could argue that EMT provide negative understanding by producing a scenario where two person, equal in all their knowledge, but one believing in EMT and other does not, and the the other person win in making bette decisions (say more profit).
So people can't be irrational ever. Our model could be incomplete in describing their behavior. This would be a problem with all branches of sciences, including objective sciences such as Physics.
ReplyDeleteConsider the following physical theory: every action in the universe takes place as specified by a particular string of 0's and 1's. This theory is not falsifiable, in fact it is true by definition: I am not telling you what this string is or how it can be created.
Your argument about "people can't be irrational ever" is of the same nature: it is true for some definition of a utility function, but if we cannot come up with a utility function, it is not really a useful theory.
EMT starts from there and says, "well it's hard to come up with a realistic utility function, so let's start with something simple that we can prove theorems about". Then it goes on to derive conclusions that are valid under the restrictive assumptions. And then these economists go and tell the world with absolute authority how to design markets, how to manage the economy, to argue against any sort of regulation, etc.
If I were to come up with a drug to cure myopia that kills 25% percent of the patients, I don't think anyone who argues against it will be required to come up with another cure for myopia. I don't see why pointing out the falsehood of EMT requires me to come up with an anti-EMT.
I think it is important that the economists realize that EMT is just a theory, that occasionally provides insights about the real world, but on the whole has little to do with human economics. For most economists, EMT and rationality is like a relegion, and such indoctrination is harmful for the society.
Yeah, you could argue that EMT provide negative understanding by producing a scenario where two person, equal in all their knowledge, but one believing in EMT and other does not, and the the other person win in making bette decisions (say more profit).
This wasn't an unrealistic scenario imho. And it illustrates the fallacy of the fundamental assumptions of EMT.
An orthogonal question: EMT assumes that each player is small an thus a price taker. When this assumption breaks (e.g. in the stock market with big banks and hedge funds), is there anything one can say even under these restrictive assumptions.
All I am asking is suggest alternative. Yes, I said our rationality theories are incomplete. But to argue that people are irrational, you have to suggest an alternative. Non-theory is an alternative too.
ReplyDeleteSimilarly, you have to suggest an alternative to EMT.
Let me take your example itself. If a drug kills 25% of people, it is bad drug, if the alternative kills fewer. In your example, not using the drug is a valid alternative.
But if a drug kills 25% is used to treat a disease which kills 50% of people, then that drug is useful.
Sometimes EMT suggests against the regulation. If EMT is not complete, it does not mean having that regulation is desirable. You have to come with an alternative theory which can guide you. Absense of the alternative theory is also an alternative.
You neither wants to suggest an alternative theory, not want to say absence is a better alternative. It is like, heads you win, tail I lose.
I say that EMT, Rationality etc are the state of the art. Economics is an inherent subjective field. You can't have a 100% accurate theory. If a theory is only 1% more accurate than random decisions, then it is a useful theory. The only way to criticize their practitioners and theoreticians, is to suggest a better alternative. People are irrational is not an alternative thoery. Markets are not efficient is not an alternative theory either. Because they do not help you decide between two options, A and B. If we pick A, and it turned out to be a bad decision, "you could argue, hey, people are irratonal and therefore A is a bad choice", and you could say the same thing if we pick B. Theories are supposed to guide. They are suppose to throw some visibility, even if they do not perfectly illuminate the options. A theory is useless, if its conclusion has zero correlation with reality (you are not claiming this). A theory is bad, if either you have a superior theory which we are ignoring, or the conclusion of the theory has negative correlation with reality (in case of binary choices, may be negative of the theory is useful!). State your position, in what sense you intend to criticize economics, or algorithmic game theory.
Easy. The first is motivated by some real life considerations while the second one isn't.
ReplyDeleteIt's the same difference between a physicist studying a string model with the hope of replacing the standard model, and a mathematician playing with branes just because they are cool mathematical objects.
This shows only the following: ToC and mathematics are the same activity or have the same practice, that is, both search for absolute mathematical results; but where mathematicians consider a mathematical problem to be valuable by it's intrinsic value to mathematics (what you call in a simplistic manner "being cool"), theoretical computer scientists consider mainly mathematical problems that concern algorithms within some well defined computational models. And the computational models that ToC people use correspond to physical computing machines.
So, in other words, ToC is a subfield of mathematics: it studies a subset of all mathematical problems.
But, ToC is not aimed at building a correct model of some unknown empirical world. So the analogy to physics is incorrect. In natural sciences we need to model an outside world; this outside world is given to us by means of empirical data. And this empirical data is apparently the only information we have on this unknown world. When we build a model of physical reality, we need to have a correspondence between two different things: the model and the physical world. The criterion for this model is that IT IS TRUE (and we might never know absolutely that the model is true).
But in ToC we don't necessarily have this doubt. For example, if we prove a lower bound on the number of comparisons one needs to do in the RAM model then we know that every run of an algorithm in our computer, written in a language which can be simulated without increase in number of steps by RAM programs, will make at least this number of comparisons. We know this without a doubt because we built the computer and programmed it.
CS (but not ToC, which is a mathematical subject) has also aspects of engineering. But not of empirical sciences and certainly not of social sciences, which is what I tried to argue at first (at least not currently; this might change in the future, but I cannot see an advantage in such a change).
With regard to the "Interface between computer science and economics" -- this week Paul Willmott gave a cogent interview on CNBC.
ReplyDeleteWillmott argues is that high-frequency trading has destroyed our individual and collective ability to assess risk and assign value ... obviously this wasn't supposed to happen ... but it did.
The technical discussions on the Willmott forum is enlightening too. These professional traders don't even try to defend the axioms of EMT. Why is that?
CS (but not ToC, which is a mathematical subject) has also aspects of engineering. But not of empirical sciences and certainly not of social sciences,
ReplyDeleteThis is absolutely correct. I have no problems if some people start a new area of study (say applications in economics and such). But why this insistence that it is part of TCS when its clearly not ? As it is the fundamental problems of TCS are very far from being even approachable at this point -- so instead of spending our energy on trying to make incremental progress on these deep questions, why this fatal attraction of the social "sciences" ?
I suspect all this has to do with funding and publication venues and such.
Anonymous asks: Why this fatal attraction of the social "sciences" ?
ReplyDeleteThat's easy ... deans and chairs seek students and revenue ... they see Paul Willmott siphoning off both with Certificates in Quantitative Finance.
From a student's point of view, isn't Willmott offering an attractive package relative to a traditional CS/ToC PhD: 1/8 the time, 1/4 the cost ... and immensely superior job and/or enterprise prospects ... and as much "yellow book" math as the student has the heart to learn?
Furthermore, aren't Willmott-type package particularly attractive to elite, mathematically mature students -- the ones who are largely capable of teaching themselves ... the students that traditional graduate programs are most keen to recruit?
What's missing from Willmott-type programs? Mainly, the exposure to liberal academic values that is attained by living (for several years) within a traditional academic community.
To the extent that academic graduate programs are neglecting these traditional liberal education values ... well ... won't Willmott-type certificate programs eventually take away their students and revenue?
Why would they use EMT to defend their high speed trading? EMT or other economics theory would say, do not trade unless you have specific beliefs/knowledge about the underline investment being traded.
ReplyDeleteOn the other hand, high speed trading or algorithmic trading is entirely based on identifying patterns in the stock charts. These stock charts represents the collective beliefs and pschology of the other traders weighted by their investment. Trading based on the stock charts may increase the extent of market oscilations. These high speed tradings are anti-Economics. If you believe in these things, you should not believe in economics. If you want to make points against such activities, IMHO, your only tools so far are the beliefs in economics. It is not them, who should be invoking the economic axioms to defend their actions.
But, ToC is not aimed at building a correct model of some unknown empirical world. So the analogy to physics is incorrect.
ReplyDeleteAu contraire. The RAM model is an abstraction of an empirical world and when it fails we propose alternatives (word RAM, I/O model) the same way physicists do.
As well, shall a new realistic computational model arise we would be interested on it (quantum computers, randomized algorithms any one?).
I wonder what is it with the math wannabes here who go through great contortions to deny the obvious motivations of the algorithms we develop.
If you wish not to care about applications, then for sure you are a mathematician. That is your personal choice as opposed to a quality of TCS.
and as much "yellow book" math as the student has the heart to learn?
ReplyDeleteFrom experience I can say that for the average US math graduate students (who are all very, very smart) it really takes at least a year (in fact, often close to two) to learn the basics of real analysis, complex analysis and algebra as taught in most grad schools. I see no way of shortening this. By learning, I mean obtaining a real understanding of these subjects -- which is usually tested in grad schools by written comprehensive exams. Of course, browsing through the yellow books one can pick up enough theorems to convince others of ones knowledge -- but such superficial knowledge would be of no use against any challenging research problem.
Anonymous asserts: For the average US math graduate students (who are all very, very smart) it really takes at least a year (in fact, often close to two) to learn the basics of real analysis, complex analysis and algebra
ReplyDeleteThis is absolutely correct IMHO ... and furthermore, without this foundational knowledge, there is no hope of correctly using modern computation/simulation tools in any discipline: finance, engineering, chemistry, physics, or (especially) biology.
At the FOMMS conference this was called "The education problem". NSF officials at FOMMS held out hope that this challenge could be addressed easily and inexpensively, by having incoming graduate students attend week-long workshops.
Most FOMMS attendees, however, were more aligned with anonymous' way of thinking ... that there is no educational silver bullet that will rapidly impart these skills.
It was striking that (especially in biology where nowadays the highest-level maths are found) the most prosperous sectors of the academic ecosystem are evolving to resemble Wall Street trading groups ... rookies and veterans mixed together ... learning on-the-fly in a dynamically evolving and highly competitive research environment.
I'm not saying it should be this way ... nonetheless that's the way it is working.
I say that EMT, Rationality etc are the state of the art. Economics is an inherent subjective field. You can't have a 100% accurate theory. If a theory is only 1% more accurate than random decisions, then it is a useful theory. The only way to criticize their practitioners and theoreticians, is to suggest a better alternative. People are irrational is not an alternative thoery. Markets are not efficient is not an alternative theory either. [...] A theory is useless, if its conclusion has zero correlation with reality (you are not claiming this).
ReplyDeleteSimply being the best-we-have-so-far and having-positive-correlation-with-reality don't, in my book, make a "solid theory".
In many settings, such as healthcare, there are alternatives to the EMT-prescribed approach, that empirically have worked quite well in several countries. It is important to critique a theory that makes definite recommendations based on faulty assumptions.
Why would they use EMT to defend their high speed trading? EMT or other economics theory would say, do not trade unless you have specific beliefs/knowledge about the underline investment being traded.
[...]If you believe in these things, you should not believe in economics. If you want to make points against such activities, IMHO, your only tools so far are the beliefs in economics.
I am missing something here. From what I can tell, EMT would in fact say that such correlations-based training cannot be profitable in an efficient market and hence such traders would lose, or rather given the rationality assumption, not even exist. But these people exist and make a lot of money. So if economics is about explaining reality rather than postulating a perfect world, shouldn't economist actually worry about the existence of such entities? I am not sure what you mean by "make points against such activities" : in a world that EMT prefers, any profitable activities should be encouraged.
Fast trading is not actually making that much money, even these days. The scale is too small to contradict EMT. GS is maybe making more, but they are probably just laundering their AIG/bailout money somehow. :)
ReplyDeleteAnonymous asserts: Fast trading is not actually making that much money, even these days.
ReplyDeleteLOL!
Theorem: if that information is reliable, then (by EMT) you will keep it secret & short the fast-traders.
Given: You didn't keep it secret.
Lemma: The information is unreliable.
It's incredibly obvious, Mandrake! :)