Posts Tagged ‘Theory vs. Practice’

An NSF-targeted workshop on Research Issues at the Interface of Computer Science and Economics has just taken place in Cornell, attended by many central people in the area (but not by me), including several bloggers that reported on it (Lance, Muthu a b c, and Rakesh). This is another one in a sequence of workshops where economists and computer scientists meet to exchange ideas, results, and points of view.

A fruitful issue in the interface is taking account of computational complexity in economic and game-theoretic settings.  This has received much attention (e.g. in Rakesh’s post), and while it certainly is a key issue, I disagree that this is the core issue in this interface.  I believe that even more interesting is the combination and interplay of the different research attitudes of the two communities, a combination that is needed for studying the future economic issues brought by technological advances.

I believe that much of the difference in attitudes comes from economists’ emphasis on “what is” vs. CS emphasis on “what can be”.   Even theoretical economists try to talk about the real world, their examples and motivations are real existing industries and situations, and their philosophical point of view is mostly scientific: understand the world.  Computer Scientists prepare for the future, knowing that most of what exists today will soon become obsolete.  Our motivations and examples often assume a few more years of the steady march of Moore’s law.  These attitudes are the outcome of different situations of these disciplines: economic work that did not correspond with reality was eventually ignored, while CS work that was not forward looking became obsolete.  This distinction is obviously somewhat simplistic and exaggerated, but this does  seem like the general spirit of things.  Indeed the sub-area of economics that was most natural for computer scientists to “blend with” was Mechanism Design which unusually  in economics has an engineering spirit of  “what can be” .  I feel that many of the technical and  cultural differences between the communities have their roots with this difference.

Economists and Game-theorists take their models much more seriously and literally than computer scientists do.  While an economists’ model should correspond to some real phenomena, a CS model should correspond to a host of unknown future situations.  A CS reader is more willing to take the leap of imagination between the model as stated and various unknown future scenarios.  In compensation, the CS reader expects a take-away that transcends the model, often found in the form of mathematical depth.  An economics reader is much more skeptical of a model and demands specific justification, but on the other hand, mathematical depth is not seen as a feature but rather as a nuisance to be buried in the appendix.

The Bayesian point of view of economists vs. the worst-case point of view of computer scientists have a similar root, I think.  In a situation that already exists, there is obviously some empirical distribution, and it is hard to argue against taking it into account.  In a situation that doesn’t exist, there is yet no empirical distribution, so in order to prepare for it we need to either theoretically guess the future distribution, or prepare for worst case.  CS has learned that the first option does not work well.

There are other high-level differences I can think of, but let me give two specific ones.  How does one interpret a 4/3-approximation result in a network setting?  While an economist will certainly consider a loss of 33% to be a negative result (as it would be in almost an existing scenario), a computer scientist will view it as giving up a few months of technological advance — a negligible cost compared to the other difficulties facing the adoption of anything new.

In Mechanism Design, computer scientist focus on the simplest model (dominant-strategy implementation; independent private values; risk-neutrality) and spend most of their efforts exploring the limits of the model, inventing new mechanisms, or proving impossibility, for various  scenarios which are obviously unrealistic today.  Economic theory, on the other hand, has moved on to more sophisticated models (risk aversion, dependent values, etc.), and is not as concerned with the limits of the model — until a real application emerges, like spectrum auctions.

I think that the future exploration of the interface of economics and CS should not only combine notions and results from both fields, but also combine attitudes and points of view.  The latter is even more difficult to do well.

Read Full Post »

Wired magazine published a (rather enthusiastic) popular article on Hal Varian’s role as chief Google economist.  It shortly mentions that Microsoft now has Susan Athey in a similar role.

Read Full Post »

I recently looked again at Ausubel’s multi-unit auction paper, and really liked the crystallization of the first paragraph in it:

The auctions literature has provided us with two fundamental prescriptions guiding effective auction design. First, an auction should be structured so that the price paid by a player—conditional on winning—is as independent as possible of her own bids (William Vickrey, 1961). Ideally, the winner’s price should depend solely on opposing participants’ bids—as in the sealed-bid, second-price auction—so that each participant has full incentive to reveal truthfully her value for the good. Second, an auction should be structured in an open fashion that maximizes the information made available to each participant at the time she places her bids (Paul R. Milgrom and Robert J. Weber, 1982a).

I would say that this is useful practical insight gained from studying theory.

Read Full Post »

Another round in the everlasting soul-searching of the TCS community about its connection with the real world has been lately going on in the “usual” theory blogs (by Mihai, Bill, and Michael, spurred by a workshop on theory and multi-cores) and also by Mark, a self-professed outsider. Among other issues that he points out, Mark complains about “people who devise complicated (never implemented) algorithms, with basic big-O analysis only, and obsession over the worst case” and asks: “how many researchers who devise new algorithms actually have them implemented?”  Mihai, basically argues (in the multi-core case) against being too practical: “there is really no point wasting our time on current technology which is clearly bound to be replaced by some other technology in the next 60-1000 years”, but cannot refrain from mocking “too theoretical” theory (with a stab at algorithmic game theory too): “Which theory community? … The one that thinks Amazon should be happy with an O(lg3n) approximation for its profit?”

I tend to think that much of these complaints comes from taking the models and results of theoretical computer science too literally. The contribution that theory provides is usually not that of someone directly implementing a new algorithm. Usually it is the insights behind the algorithm (or the lower bound or the characterization) that tend to be useful. Such insights may well come from “an O(lg3n) approximation for profit” (which may be near optimal on real distributions, or may suggest a good heuristic or may combine well with other algorithms and optimization goals — all of these best dealt with practically rather than analyzed theoretically). On the other hand even, say, a linear time algorithm for the exact optimal profit may not be directly applicable since it solves the wrong problem or due to additional new constraints or due to the input not being available as assumed or a variety of other reasons.  Thus the “technology transfer” from theory to practice is not really composed of “algorithms” and “results” but rather of “insights”, “techniques”, and “ways of thinking”.  Indeed, when I look at how theoreticians in Google contribute to the practice of the company, I can hardly think of a situation where the contribution was simply a great new algorithm that was simply implemented. Usually, what a theoretical researcher contributes is a point of view that leads to a host of suggestions about algorithmic techniques, heuristics, metrics, notions, interfaces, trade-offs and more — all influenced by theoretical understanding — that together yield improved performance.

Thus the contribution of an “algorithm for X with performance Y in model Z” does not require that model Z is “realistic” or that performance Y is “good” — the real contribution is that obtaining performance Y in model Z provides new insights — insights that can then be used in various possible realistic applications for achieving performance improvements in various cases. It seems that many in our field (including program committees) sometimes forget this and simply view improving Y as a goal by itself (this is related to the old TCS conceptual debate). A well chosen model Z will indeed tend to have the property that improving Y in it indeed correlates well with new insights, but is never quite equivalent.  A major difference between theoretical CS (as well as theoretical economics) and pure math is exactly in the central place of the art of choosing the right model.  This is especially true for Algorithmic game-theory that sits between theoretical CS and theoretical economics that have different sensibilities about good models — but this requires another post.

While judging a single contribution for “insight” is certainly difficult and subjective, in the long run we can tell.  The real test of a community, in the long run, is whether the insights that it has developed over a significant amount of time contribute to other fields. I would claim that theoretical computer science passes this test with flying colors. Looking a generation back TCS has pretty completely re-shaped computer science and optimization.  The more recent products of theoretical CS like approximation algorithms, online algorithms or streaming/sketching algorithms have already had a major influence on how the fields of OS, DB, or AI treat their own problems as well as how the industry looks at many of its problems. I would even claim that the very young field of algorithmic game theory can already boast some of its insights already affecting other fields, and certainly much real Internet activity (yes, yes, ad-auctions and such). Of course it is way too early to judge the contribution of algorithmic game theory or other last-decade fruits of theory.

Read Full Post »

I recently looked at Al Roth’s web page on “Game Theory, Experimental Economics, and Market Design” which is probably the best link collection on the web on these issues.  What caught my eye was the nonchalant unusual combination of “Game theory” and “experimental economics”.  From a CS point of view, we rarely see someone who is both a theoretician and also does “experimental-anything”.  Al Roth’s reasoning for this combination is very simple: “My research is in game theory, experimental economics, and market design (for which game theory, experimentation, and computation are complementary tools)”.

So, should “algorithmic game theory” (in the broad sense) also put significant energy into experimentation?  Should we specifically study the interaction of humans with our systems?  My original point of view was that luckily we are spared the difficulty of dealing with these pesky humans.  As we study rational behavior of fully controlled computer systems,  we get to design their behavior and we will certainly design them to be perfectly rational according to our best analysis (the buzzword is “hyper-rational”).  Thus if our analysis suggests that the rational behavior when working under protocol X is to do Y, then we will just program our software to do so — why shouldn’t we?  Of course, there could be various technical challenges (computational limitation, partial information, etc) but these we can analyse and quantify and handle as well as is possible.  “Rational Choice” debates about the relevance of game theory to human behavior concern economists — not us.

The problem is of course at the boundary of the computerized system: how are the utilities specified?  A well-designed computerized system can act rationally to optimize a given goal, but it must be given this goal by humans.  This is not just a conceptual difficulty, but actually the main challenge in most systems that I know. Elicitation of user preferences via some kind of a user interface is a main technical challenge.  Consider software that is used for participating in some (not too simple) auction such as the adwords auction.  While there are usually many interesting algorithmic and game-theoretic considerations in designing the bidding software (and the auction itself), I would say that the most important design bottleneck is still the user-interface: how do we let the user specify what he wants to get in the auction in an intuitive yet powerful way.  Part of the problem is that “what the user wants” has different meanings: one of them is imprecise and sits in his head, while the other is formal and sits in the software.  All too often optimizing for the latter does not do so for the former.  This brings the framing effect into play in a direct technical sense: what users will seem to want depends on how things are presented to them.  While I can see some companies designing their software as to “push” people towards behavior that optimizes the company’s revenue, it is not clear to me what should our normative goals be in the design of such user interfaces.  

I don’t have a conclusion to end this post, so instead here are two related comments:

  1. I never quite understood the difference between experimental economics and behavioral economics.  My impression is that it is simply a question of your attitude towards game theory: experimental-pro, behavioral-con.  The anti-game-theory bias is probably not that of its founders Kahneman and Tversky.  Shortly after winning the Nobel prize in economics in 2002, I heard Kahneman talk at a dinner held by the Hebrew University’s rationality center.  His point was that while most psychologists would immediately dismiss the economic assmptions of rationality as absurd regarding human beings, the greatness of his co-author Tversky was to realize that there was an important underlying truth to this point of view, and hence that it was interesting to carefully study its limitations.
  2. The experimental vs. theoretical question is part of a much broader set of issues of the theory-vs-practice family.  It seems that algorithmic game theory sits in an interesting cross-roads where we get many perspectives on these issues: from CS, from economics, the wider rational choice debate, the actual Internet, etc.

Read Full Post »

A skeptical reader made the following comment to a previous post:

What exactly do all those AGT researchers do to increase profitability?

Shouldn’t we stop pretending that AGT has any relation to the real world?

 The theory vs. practice debate in every field is interesting, but for now just a few quick comments:

1) Actually it seems to me that ignoring the relation of AGT to the real world is pretending.  It is a fact that many companies are interested in this work, whether or not justifiably so.

2) At least what I did for a while in Google can be seen in this paper.

3) While there are a few “deep” theoretical problems in AGT, most of the interest in this young field is actually figuring out the right questions and models.  An early split from the “real world” would make sure that we end up with the wrong questions and models.

4) It seems to me that this comment is part of a game we theoreticians like to play: “we don’t do anything useful — we just pretend so in order to get grant money”.  I don’t buy.

5) However, I can’t resist participating a bit in this game and sharing a strategy of pretending to be useful: when I started working in the econ/CS border I observed a difference in the way economists and computer scientists gave examples.  While in CS examples would look like “Suppose Alice bids $3 for a pair of socks“, economists would give the same example as “Suppose ATT bids $3B for a spectrum license“, which is so much more practical.  My new suggestion for computer scientists is to move to “Suppose Alice the plumber bids $0.003 for an ad slot”, trumping the $3B, I would say.  (Which makes me wonder how many other human inventions function over a range of twelve orders of magnitude like auctions do?)

Read Full Post »

« Newer Posts

%d bloggers like this: