Experiments on Mechanical Turk

Crowd sourcing has just been given a recent visibility boost with DARPA’s Red Balloon contest that was won by the MIT team.  At the same time, Amazon’s well-established (since 2005!) platform for crowd sourcing, the Mechanical Turk, is gaining attention as a platform for conducting behavioral experiments, especially in behavioral economics and game-theory.

Named after the 18th century human-powered chess-playing “machine” called “the Turk”, this platform allows “requesters” to submit “Human Intelligence Tasks” (HITs) to a multitude of human “workers” who solve them for money.  A sample of recent typical tasks include tagging pictures (for 3 cents), writing (and posting on the web) a short essay with a link (for 20 cents), or correcting spellings (for 2 cents, in Japanese).  This allows brief and cheap employment of hundreds and thousands of people to work on simple Internet-doable low-level knowledge tasks.  You may demand various “qualification exams” from these workers, and design such quals of your own.  Obviously workers are in it for the money, but apparently not just that.

Recently, the Mechanical Turk is being used to conduct behavioral experiments.  Gabriele Paolacci is methodologically repeating experiments of Kahneman and Tversky and reporting on them in his blog. Panos Ipeirotis reports on his blog studies of some aspects of the Mechanical Turk as well as results of various behavioral game-theory experiments on it.  I’ve seen others report on such experiments too.  Markus Jacobsson from PARC gives general tips for conducting such human experiments using the Mechanical Turk.

Turk-based behavioral experimentation has the immense appeal of being cheap, fast, and easy to administer.  There are obviously pitfalls such as getting a good grasp on the population, but so does any experimental setup.   Such a platform may be especially appropriate for Internet-related behavioral experiments such as figuring out bidding behavior in online auctions, or how to best frame a commercial situation on a web-page.  Could this be a tool for the yet not-quite-existent experimental AGT?

Economists and Complexity

One of main culture clashes between computer scientists and economists on the CS-econ frontier is whether “complexity of equilibria” matters.  The  CS-y view of the matter is captured in Kamal Jain’s quote: “If your laptop can’t find it then neither can the market“.  Economists mostly don’t care since they see equilibrium reached everyday, contrary to what CS says.  As Jeff Ely quips:  “Solving the n-body problem is beyond the capabilities of the world’s smartest mathematicians.  How do those rocks-for-brains planets manage to do pull it off?“  TCS folks who see complexity as the map of the world can’t really understand this indifference, as Lance Fortnow tweets: “I’m an economist so I can ignore computational constraints / I’m a computer scientist, so I can ignore gravity.“

Computational Complexity map of the world

The beautiful thing about studying systems at equilibrium is precisely the fact that this abstracts away the gory details of the process (aka dynamics aka algorithm) of reaching this equilibrium.  In principle, there are many different difficult-to-understand dynamics that all reach the same easy-to-understand equilibrium point.   This is all very nice as long as the equilibrium is indeed magically reached somehow by the “real” dynamics.  The obvious crucial question is whether this is the case in practice. It seems that the general tendency among economists is to claim “yes”, to which the natural next question in line is “why”?  As computer scientists show, this is not a general characteristic of large games or markets.  Understanding the properties of interesting games and markets that make them actually reach equilibrium should be enlightening.  Maybe it is because economists choose to consider only those that do turn out to converge quickly, ignoring another large and interesting class of strategic scenarios? Maybe it is because economists are thinking about “smallish” games and so their insights will not carry over to more complex realistic scenarios?  Maybe there is some deeper interesting structure that guarantees fast convergence?  Distinguishing between these possibilities is especially crucial as we aim to analyze the new artificial games and markets that are to be found — and designed — on the Internet as well as elsewhere.  Which economic and game-theoretic sensibilities will still hold in these complex unnatural  circumstances?

Complexity is all about understanding such processes.  While the foremost question dealt by computational complexity is that of “time” — how long does a computational process need in order to find the solution — in our case to reach (close-to) equilibrium — this is not the only type of questions and insights provided by complexity theory.  As one can see in the “map above”, there are a stunning variety of complexity classes, each attempting to capture a different facet of the challenge of finding the solution: how much space (memory) is needed? Can we even tell when we reach a solution?  Does randomization help?  Is it helped parallelism?  Are approximations easier?  Does the solution have this or that particular structure? In the case of finding equilibria, the classes PPAD and PLS give a very nuanced explanation of what is involved.  There are also “concrete” models that study explicitly specific parameters such as communication or queries.  One may dislike the fact that this complexity analysis does not restrict attention to natural dynamics but allows arbitrary and unnatural algorithms.  The kind of natural dynamics that economists usually have in mind are some kind of best-replying in case of games and some kind of a Walrasian auctioneer in markets.  The problem is that there are many variants of these that make sense: fictitious play, various forms of population dynamics, more sophisticated types of learning such as regret-minimization, and all these can be enhanced with various orderings, smoothing attempts, tie-breaking rules, strategic look-ahead, re-starts, actions of the central planner, not to mention other more or less complex optimization and learning  attempts.  The strength of complexity analysis is that it applies to all of these.  Any “lower bounds” are definitive: any practical system can be simulated by a computer, and thus no dynamics can succeed in general. (Emphasis on “in general” — as mention above, the problems that you may be interested in may have special structure — so what is it?)   A statement of  an “upper bound” may be less interesting as stated, but immediately raises the challenge of either finding a natural algorithm=process=dynamic or pinpointing the complexity reason explaining why this is impossible.

This is a good point to refute several irrelevant objections to the applicability of computational complexity for analyzing dynamics of games and markets.  The first is the notion that humans or markets can undergo processes that cannot be computed.  Frankly, there is no evidence of this; there is certainly much about the world that we do not understand well enough to simulate, but there is no indication of any natural process that is inherently more powerful than computers.  This is the modern version of the Church-Turing thesis.  (It seems that some quantum phenomena cannot be simulated by usual computers, but that doesn’t change the principle — it just would replace classical computers with quantum ones in the few places that it matters.)  Even if you do subscribe to metaphysical dualism, do you want to base economics on it?  The second types of objections concern the standard technical notions used in complexity which obviously leave much wiggle-room: “polynomial time”, with its hidden constants, is not synonymous with efficient; worst-case analysis is not always the right notion, etc.  The point is that these are simply concise notions that usually seem to capture the issues well.  There always are cases where more refined notions are needed, and in such cases complexity theory can provide more precise answers: for example in analysis of basic problems like sorting or matrix multiplication, very exact results are obtained (with no hidden constants) similarly, cryptography is not based on worst-case analysis, etc.  There is no indication so far that the usual somewhat coarse notions of computational complexity miss something significant when applied to games or markets — quite the contrary in fact.  If such evidence emerges then complexity will not become irrelevant; simply more refined analysis will be used.

Take for example the stunning difference between reaching a Nash equilibrium and reaching a Correlated equilibrium.  While the latter is reached by various natural regret-minimization dynamics, there are no “non-trivial” dynamics that, in general, reach the former.  Let me say a word about this “non-triviality” by giving an example of what I would consider a trivial process: suppose that each player chooses a strategy at random every “turn”, unless his last strategy was already a best-reply to those of the others (up-to some indifference).  At some time, the players will happen to “hit” an (-) equilibrium.  This type of dynamics that simply search over the whole space of strategy profiles provides no insight and is not useful in most practical situations.  The point of the triviality is not that of the random choices but rather that of essentially trying every possibility.  Many other proposed “dynamics” for Nash equilibrium or for market equilibrium are similarly trivial — in some cases they resort to simply trying all possibilities (in some approximate sense).  The dynamics for correlated-Nash are not like this at all — they only look at a tiny “small-dimensional” fraction of the space of possibilities.  Why is that? Complexity theory explains this phenomena clearly: correlated equilibria can be found in polynomial time, but finding a Nash equilibrium (or many types of market-equilibrium) is PPAD-complete.

Grading a game theory course

A few days ago I re-heard the story of how the game-theory course in the Technion was graded. I’ve heard versions where the professor was Ran Smorodinsky and other versions with Dov Monderer, but I haven’t checked out what “really” happened. (Anyone with the real facts is welcome to send in a comment…) Here is the story.

In the last day of class, the Professor gathered all the students and made the following offer: He wants to have an average grade of X (say 80) in the course with a standard deviation of Y (say 15). If all students agree upon everybody’s grades in a way that conforms to these constraints, then this is how they will be graded, and the exam will be canceled. Otherwise, the scheduled exam will take place as usual and will determine the grades. The professor then left the class and let the students try to reach a joint decision.

Some versions of the story continue thus: the best student in class immediately got up; said that she will not accept anything less than 100; and immediately left the room too.

Facebook Hiring in AGT

A large number of AGT researchers work in just three large companies: Google, Microsoft, and Yahoo, mostly working on ad auctions. From two or three data points, it seems that Facebook is now attempting to hire such researchers too (although maybe not in “research” roles). Looking in Facebook’s “careers” page, they are indeed looking for an “advertising auction expert” whose requirements include “Expert knowledge of algorithmic game theory, auction theory, mechanism design and their applications to online advertising” as well as a Ph.D. in CS or OR.

I can well see the potential for Algorithmic Mechanism Design research in Facebook. Facebook’s information about its users is enormous, detailed, and lives within the context of their complex social network. Making good use of this complex information seems to require another level of sophistication relative to today’s ad auctions. Privacy issues are always there, and while Facebook has already had problems in that department, it seems that its users do not consider their “identity” to be too private. I wonder if within a year or two we’ll start seeing research papers coming from Facebook too.

Theoretical Economics as Math

Eran Shmaya, in a beautiful recent blog post, adds some sociological angles to the economists’ never-ending introspection of whether their field is a science, where the starting point of such discussion is Popper’s falsifiability.  The discussion about whether economic theory has any significant prediction power has certainly picked up lately due to the financial crisis that convinced many people that the answer is “No”.  (With a variant taken by many micro-economists claiming that micro is fine and only macro-economics is a superstition.)

Whenever I hear these types of discussions about the prediction power economic theory, I always think about the irony that, as an algorithmic game-theorist, I am mostly interested in using economic theory as a branch of mathematics…  Arrow’s theorem is simply true, not falsifiable.  So is Meyrson’s expression for optimal auctions, as well as many other mathematical tidbits that we, computer scientists, pick up from economic theory.  We don’t really care how well these theorems relate to human situations, since we use them in different circumstances, those related to computer systems.  I often wish that theoretical economists would allow themselves to stray even farther away from the realities of their human subjects.

This is not to say that we, in algorithmic game theory, need not worry about how well our theories correspond with reality.  We should.  We have not really started doing so.   And, it’s getting high time we do.  But our concerns may be more like those of engineers rather than those of scientists.  From economics, I’m happy to just take the theory…

Supremum and mathematical education

My nephew just started his undergraduate degree in Math at the Technion.  When his grandfather, a high-powered engineer (whom I sometimes turn to for solving a differential equation that I need solved) , asked him what they learned in their very first calculus lesson, the answer was “supremum“.  The grandfather was mystified, claiming that “supremum” was not part of the math curriculum at all when he got his engineering degree half a century ago (also in the Technion, it turns out.)  While this can hardly be literally true, it does highlight the difference between the “abstract” approach to math and the “applied approach” which he got as an engineer.  From an abstract point of view, it makes much sense to start  with the notion of supremum, the ubiquitous existence of which essentially defines the real numbers, while I suppose that a more applied approach will hardly emphasize such abstract technical hurdles.  When I studied math at the Hebrew university, we spent an enormous amount of time on such abstract notions up to the point of ending the first year with hardly any practical abilities of figuring out a simple Integral but having a pretty good grasp of properties of zero-measure (yes, first year).

In my department, we have an on-going debate about the type of math that our CS students should get.  Traditionally, we have followed the extremely abstract tradition of our math department which emphasizes the basics rather than applications (even in the “differential equations” course, students rarely solve them, but more often prove existence and such).   In the last decade or so there has been a push in my department to shift some focus to “useful” math too (like being able to actually use singular value decomposition or Fourier transform, as needed in computer vision, learning theory, and other engineering-leaning disciplines).  I’m on the loosing side of this battle and am against this shift away from the “non-useful” fundamentals.   The truth is that most computer scientists will rarely need to use any piece of “useful” math.  What they will constantly need to use is “mathematical maturity”: being comfortable with formal definitions and statements, being able to tell when a proof is correct, knowing when and how to apply a theorem, and so on.

New papers by Brendan Lucier

In the last month, Brendan Lucier has uploaded three conceptually related papers to the arXiv (two of them with co-authors):

1. Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions by Brendan Lucier
2. Bayesian Algorithmic Mechanism Design by Jason D. Hartline and Brendan Lucier
3. Price of Anarchy for Greedy Auctions by Brendan Lucier and Allan Borodin (to appear in SODA 2010)

All three papers aim to improve the approximation ratios obtained by computationally efficient mechanisms.  Each of them gives pretty strong and general results, but at a price: relaxing the notion of implementation from the usual one (in CS) of dominant-strategies.  Specifically, the notions used in these three papers are, respectively:

1. “We consider models of agent behaviour in which they either apply common learning techniques to minimize the regret of their bidding strategies, or apply short-sighted best-response strategies.”
2. “We consider relaxing the desideratum of (ex post) incentive compatibility (IC) to Bayesian incentive compatibility (BIC), where truthtelling is a Bayes-Nash equilibrium (the standard notion of incentive compatibility in economics).”
3. “We study the price of anarchy for such mechanisms, which is a bound on the approximation ratio obtained at any mixed Nash equilibrium.”

In general, I like the strategy of relaxing the required notion of implementation or equilibrium in order to get strong and general results.  This is especially true in the context of algorithmic mechanism design for a few reasons (1) The concept used in CS seems to be so strict that simply not enough is achievable (2) The CS point of view is anyway much stricter than that of Bayesian-Nash commonly used by economists (3) much less seems to be needed in practice in order to ensure cooperative behavior.  (E.g.  people just use TCP truthfully despite the clear opportunities for beneficial manipulation.)  The difficulty with the relaxation strategy is that there are many possible ways of relaxing the game theoretic requirements, and it takes some time to really be convinced which notions are most useful, and in which situations.  I would love to see more community discussions on these as well as other notions of relaxed implementation and equilibrium.

CS and Economics — different attitudes

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.

Secret of Googlenomics

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.

Auction Prescriptions

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.