Workshops: Official or Unofficial Proceedings?

In the process of organizing DBRank 2010, we had to answer the following question: Should the proceedings for the workshop be "official" or "unofficial"?

Official workshop proceedings are undergoing the same process as the conference papers: Specific camera-ready format, submission by a given date to the proceedings chair, and then are officially hosted at the digital library of the publisher, with all the metadata, digital identifiers (DOI), and so on. (For DBRank 2010, that would be IEEE Xplore.) For buraucratic purposes, these papers are considered "publications."

Unofficial proceedings are, well, unofficial. Typically the workshop chair posts the papers up to the website, and potentially brings printed copies for distribution at the workshop. There is no official publisher, there is no DOI assigned to the papers, and in principle this is not more of a publication than a paper posted to a website.

So, should workshops have official or unofficial proceedings?

There are some arguments aganst official proceedings:

• Increasingly, there is a significant conflict between workshop and conference publications. With some workshops allowing 8- or even 10-page workshop papers, it becomes hard for the authors of these papers to publish the same work in a conference, as there is typically significant overlap. Most database conferences will consider any past paper that is 3 pages or longer, to be a prior publication, and the conference version should have significant new content in order to be considered a "new" paper.
• As conference become increasingly competitive many authors submit to workshops papers that could not "make it" to a conference. A workshop is typically easier to get into, and at the end "you get a paper" out of it. Needless to say, this pretty much violates the spirit of workshops that are supposed to be places for new, relatively immature research, not an archival publication.

On the other hand, there are advantages in having official proceedings:

• It makes the workshop more attractive in the eyes of many authors. Authors get an official timestamp for their work and can point to a paper that has at least been lightly refereed, instead of pointing to a technical report or working paper.
• It makes it easier for someone to locate the papers that were presented in the workshop. The websites for the workshops are not always hosted in "stable" websites and they disappear for various reasons. (For example, the websites for WebDB'99, WebDB 2000, WebDB 2001, and WebDB 2003 are not available any more, because the organizers have moved to different institutions.)

So, what to do? Official or unofficial?

Read more »

Is Amazon Mechanical Turk a black market?

According to Wikipedia, a black market is: "a market where all commerce is conducted without regard to taxation, law or regulations of trade". How is this related to Mechanical Turk?

Today, I received an email, asking about the tax and employment issues regarding Amazon Mechanical Turk. What are the rules about posting tasks on Mechanical Turk? How should these tasks be handled by accounting and human resources departments?

Unfortunately, Amazon did not design Mechanical Turk in a requester-friendly way. In an effort to relieve their accounting and HR department from a big overhead, Amazon transferred to the requesters the risk of violating the US Tax Code and engaging into illegal employment activities.

How can this happen? The key issue is whether there is an employer-employee relationship between the requesters and the workers on Mechanical Turk. The crucial question is:

When you submit funds to your Mechanical Turk account, who are you paying? Amazon.com or the worker?

If it is Amazon, then you are simply letting Amazon deal with all the tax and employment issues associated with the worker: Amazon needs to verify that the worker is eligible for employment, takes care of tax issues, and so on. In this case, hiring someone for a micro-task on Amazon is the same as getting an agency to provide cleaning services to your home: you do not need to care if the person coming to clean your place is eligible for employment, whether the taxes are properly withheld from the paycheck and so on. It is the agency's task to take care of that.

However, Amazon does not follow this route. According to the terms and conditions, paragraph 6.a:

In addition to the disclosures described in our Privacy Notice, we will disclose to Requesters [....] Provider Tax Information. "Provider Tax Information" means tax identification information of Providers, such as a Social Security Number or Employer Identification Number. Requesters use Provider Tax Information to fill out an IRS Form 1099 and send it to Providers. If you are a Requester and want Provider Tax Information from us to complete IRS Form 1099s for Providers you have paid, you must provide us with your company name and employer identification number ("Requester Tax Information"). You hereby consent to disclosure of Provider Tax Information, Requester Tax Information, and other data as described in this Section 6 and our Privacy Notice.

This provision is there because a requester that paid a worker more than 600USD per year, is required to submit 1099-MISC tax forms to these workers. In other words, this tiny provision means that the employer-employee relationship is not between Amazon and the worker but between the requester and the worker. This is in contrast to other marketplaces (e.g., Rent-A-Coder), where the requester pays the marketplace provider, and then the marketplace provider contracts individually the workers, taking care of tax issues, issues of employment authorization and so on.

What are the implications of this policy?

• Requesters may be open to the risk of violating employment laws. It is possible that a requester is illegally employing US-based workers that do not have the right to work in the US.
• Requesters may be open to the risk of violating the US tax code. The requester needs to keep track of how much they paid each individual worker (out of potentially thousands of workers), and send 1099-MISC tax forms to the workers that did more than 600USD worth of HITs over the year for the requester.

OK, these are the risks. What are the potential counter arguments and how can somene avoid these issues?

The employment-eligibility issue: Amazon pays in cash only people that have US bank accounts. This means that the person, if US-based, is legally in the US. I do not know if Amazon checks for employment eligibility (they should). If the person is not US-based, then Amazon pays through gift cards: From what I know, gift cards are not considered compensation, as we regularly give gift cards as awards to students, without worrying about their eligibility to work, and our accounting department never worried about this practice. So, the issue of illegal employment seems to be rather controlled but it would be nice if Amazon took explictly care of that. Yes, it is a big headache for the HR department of Amazon to handle thousands of micro-contractors, but this is the price to pay for running this service.

The tax issue: At the very least, Amazon should have an automatic service to take care of this issue rather than leaving requesters scramble to track all the micro-payments and send the paperwork. It is trivial: If a given requester-worker pair generated more than 600USD worth of HITs over the year, request tax information and send the 1099-MISC forms on their behalf.

A better solution: Request tax and employment-eligibility information from workers BEFORE they can work on the MTurk marketplace. Also, request tax information from all the requesters BEFORE they can post any tasks on MTurk. Then submit the tax forms automatically at the end of the year.

An even better solution: Adopt the Rent-A-Coder model, and consider the MTurk workers as Amazon contractors. Then requesters buy services from Amazon, in the same way they buy computing power on EC2, storage on S3, and so on. In this case, it is very simple to add the MTurk expense under the "software services" line in the accounting report.

Read more »

How Prices Evolve in Prediction Markets?

Last week, Nikolay presented our paper on "Modeling Volatility in Predictions Markets" at the EC'09 conference. One of the questions that we are answering in this paper is, "what is the most likely price of a prediction market contract at some point in the future?"

Let's start with the expected price. If we assume that the markets are efficient, then the current price of the contract is the best possible estimate for the future expected price. However, the current price is NOT the most likely price in the future. In fact the probability of the contract will have the same price in the future is decreasing with time. Why? Because the final price of the contract as we get closer to the expiration will get closer to 0 or 1, as the uncertainty about the outcome decreases over time. So, while the expected price will be equal to the current price, most of the future prices will be closer to 0 and 1.

Below you can see some 3d plots of the "future price density" as a function of the future price P and the time to expiration t. We assume that "now" is t=0 and the contract expires at t=1.

If the current price is 0.5, then the future price density, as a function of the future price P and the time to expiration t, is:

As you can see, the possible prices, when we are close to t=0, are clustered around the current price (in this case 0.5). Then, as we move closer to the expiration, the probability density moves closer to 0 and 1. As this contract had price 0.5, the plot is completely symmetric around the axis P=0.5.

If we have a current contract price at 0.4, then the density becomes more skewed towards 0:

And here is an even more skewed plot, with the current contract price at 0.25:

Just in case you want to create your own plots, here is the Maple code:

with(stats);

normpdf:=(x,mu,sigma)->statevalf[pdf,normald[mu,sigma]](x);

spdf:=x -> normpdf(x,0,1);

normicdf:=(p,mu,sigma)->statevalf[icdf,normald[mu,sigma]](p);

sicdf:=x->normicdf(x,0,1);

f:= (pnow,pfuture,lambda) -> spdf ( sqrt(1/lambda) * sicdf(pnow) - sqrt(1/lambda-1) * sicdf(pfuture))*sqrt(1/lambda-1)/spdf(sicdf(pfuture));

plot3d(eval((f(p,P,t)), {p=0.5}), P=0..1, t=0.1..0.75, axes=boxed, shading=zhue, orientation=[-120, 50]);

So, what can we do with these results? One application is to price the X contracts on Intrade: In the "X" contracts, the question is about the future price movement of a prediction market contract (e.g., "will the contract for Democrats winning the 2012 election be above 0.75 on December 31st, 2010?").

These X contracts are similar to the existing "call" and "put" options on the stock market, where people try to guess where the price of a stock will be in the future. There is a significant difference, though: When a trader prices and trades a call/put option for a share, (e.g., using the vanilla Black-Scholes formula) the trader needs to guess the future volatility of the share price. Through this process, the trade gives to the public valuable information about the future volatility of share price. For prediction markets, trading an X contract does not reveal the same information. Our work shows what the exact form of future price distributions, without the need to provide any volatility estimates. (Volatility can be largely determined by the current price and time to expiration; see the past blog post and the EC'09 paper for details.) So, pricing an X contract requires just to plug in the current price, time to expiration, and strike price (information that is already public) to find the "correct" price for the X contract.

So, am I saying that the X contracts are completely useless? No. But the information revealed by trading these contracts is significantly less compared to the information revealed by trading options on stocks.

Read more »

Books, Journals, Conferences, Blogs

I was reading the overview on Open Access Overview by Peter Suber, and I ran into the following paragraph:

Scholarly journals do not pay authors for their articles, and have not done so since the first journals were launched in London and Paris in 1665. Journals took off because they were more timely than books. For readers, journals were better than books for learning quickly about the recent work of others, and for authors they were better than books for sharing new work quickly with the wider world and, above all, for establishing priority over other scientists working on the same problem. They gave authors the benefit of a fast, public time-stamp on their work. Because authors were rewarded in these strong, intangible ways, they accepted the fact that journals couldn't afford to pay them. Over time, journal revenue grew but authors continued in the tradition of writing articles for impact, not for money.

It was amusing to see that there was this transition from books to journals, for pretty much the same reason that in computer science we have seen a transition from journals to conferences. I am wondering if the senior scholars of the day were commenting on this transition in the same way that Mike Trick commented on the similar tension between journal and conference publications:

if a subgroup chooses a method of evaluation antithetical to the mores of the rest of academe, don�t be surprised if the group gets little respect outside their narrow group

So may be a few years from now, we will see a similar problem as people will start leaving "traditional" peer-reviewing behind, opting for new modes of publication, such as self-publishing. Michael Nielsen has an excellent article on the disruption of scientific publishing. Micheal points to the high quality blog posts from high-quality researchers:

Look at Terry Tao�s wonderful series of posts explaining one of the biggest breakthroughs in recent mathematical history, the proof of the Poincare conjecture. Or Tim Gowers recent experiment in �massively collaborative mathematics�, using open source principles to successfully attack a significant mathematical problem. Or Richard Lipton�s excellent series of posts exploring his ideas for solving a major problem in computer science, namely, finding a fast algorithm for factoring large numbers.

So, does the future of publication rely on self-publishing? Daniel Lemire may be right saying:

To me, the single most important recent event in academic publishing has been the publication by Perelman of his solution to the Poincarr� conjecture on arxiv. This is truly a historical event.

Will this change alter fundamentally the way academia works? I do not think so. It will simply mean that every scholar will be very careful about the quality of the work that is self-published. When everyone can speak, people will only listen to those that generate content of high quality, effectively ignoring those that publish for the sake of publishing.

Read more »

LiveBlogging from HCOMP 2009

I am now attending HCOMP2009, the workshop on Human Computation that I previously advertised in this blog.

Overall, the workshop was well-attended with more than 40 people in the audience, pretty much filling the room. Below you can find the notes that I was keeping during the workshop. (See also the associated tweets.) I hope that they capture nicely some of the discussion for those of you that could not be there.

######################################################################

The workshop started with introductions, and then Luis von Ahn described MonoLingo, a human powered system for translation, using people that know ONLY ONE language. Monolingo relies on the fact that machine translation is pretty good at this point, but not perfect. So MonoLingo starts by by translating each word using a dictionary, giving multiple interpretations for each word. The human then (who is a native speaker of the target language) selects the translation for each word and forms the sentence that makes most sense.

To give the incentives to users to participate, MonoLingo appears to be a language learning site: as the user learns the language, makes small translations posed as exercises. Such small translations are used to contribute to a larger translation task.

The system reminded me a little bit of the crowdsourced-powered New York startup SpeakLike, that I have seen at the New York Tech Meetup.

I was also wondering how to best integrate MonoLingo with the more advanced machine translation systems, e.g., Google Translate, which generate significantly better translations than the word-by-word translation(s) generated by MonoLingo. Perhaps a more iterative approach (e.g., using the TurkIt toolkit and ideas) might actually work wonders in this task, where people take turns to improve the overall translation.

######################################################################

The second talk of the workshop described "Herd It: Designing a social game to tag music" by Luke Barrington, Douglas Turnbull, Damien O�Malley, and Gert Lanckriet.

HerdIt uses an active learning approach to tag music. Users tag music online and then a machine learning algorithm is trained to tag a few more songs etc. (The approach reminds me of our own KDD08 paper on active learning using multiple noisy labelers.)

The HerdIt game starts playing the music and the players sees bubbles floating around each one with a tag (e.g., rock, pop, romantic, ballad etc). The players gets more points when they hit the bubble that corresponds to the more popular tags. The authors also added quizzes in the game (e.g., a song plays and the question "the singer has long hair?" appears). For the quizzed, there is a parimutuel prediction market running in the background, where users bet on different outcomes/answers and the winners split the common pool for the bet.

The HerdIt game, reminds me a little bit of MajorMiner, a music game introduced by Michael Mandel, a classmate of mine at Columbia University.

######################################################################

The third talk described "KissKissBan: A Competitive Human Computation Game for Image Annotation" by Chien-Ju Ho, Tao-Hsuan Chang, Jong-Chuan Lee, Jane Yung-Jen Hsu, and Kuan-Ta Chen.

The authors are building on and improving the ESP game. They try to solve the "coalition problem" (people develop a strategy of typing a "common" word, e.g., "the" and proceeding to the next image) and the problem of limited data diversity of tags if you have a limited user base.

The basic idea is to make the the 2-player ESP game, a 3-player game: a new type of player is introduced, named "blocker". The blocker is trying to prevent the other two users from proceeding by typing the "obvious taboo" words that the other two players may type to describe the depicted image. The more words the blocker catches, the better the score of the blocker. This encourages the diversity of tags, since the two "matcher" players will attempt non-obvious tags to describe the image. The blocker can also observe what words the "match" users are using across images. So if two players develop a cheating strategy and type some unrelated word often (e.g., "the") the blocker can catch that behavior and put such words in the "blocked" list. KissKissBan uses a zero-sum approach where the blocker gets the points that are being lost by the matchers. So the blocker has the incentive of entering many words that are then used by the matchers. I suspect that the blocker also loses points by entering words that are NOT used by the matcher players.

Unfortunately, it does not seem to work if the matchers have access to a communication channel beyond the game (e.g., skype or being in the same room). Also, I would have liked to see some discussion of cheating strategies that can be used in such games.

######################################################################

The third talk was the paper "Community-based Game Design: Experiments on Social Games for Commonsense Data Collection" by Yen-Ling Kuo, Kai-Yang Chiang, Cheng-Wei Chan, Jong-Chuan Lee, Rex Wang, Edward Yu-Te Shen, and Jane Yung-Jen Hsu.

The authors describe a game-based an approach for building "common-sense" ontologies using "virtual pets" that are being "fed knowledge" by the friends of the player (e.g., in a Facebook-like setting). The game has some quiz-like templates (e.g., "______--likes to--______") which are then filled in by friends of the player using sensible values (e.g., "a student--likes to--have no homework"). To make it fun, the pets compete online playing such quizzes and they become smarter, getting "smart points". The smarter pets that have the most knowledge and give the most sensible answers appear in the leaderboards. The pets get points when they give the same answers as the pets of other owners. The game is named "Rapport Game".

Sounded fun having a very distinct East Asian flavor, reminding me of a social-networking-enabled Tamagochi...

######################################################################

After the break, we attended the demos and posters. Unfortunately, the time was not enough to really check the large number of posters and demos that were available.

From the demos, I liked TurkIt a lot, not so much for the library and toolkit, but mainly for introducing the idea of "iterative tasks": People that have used Mechanical Turk know that it is very hard to get people to do a good job in tasks that have free responses. Having a voting round after the submission (e.g., "Is this answer good or not") discourages fraud but does not generate high-quality results; it simply generates results that are "good enough". TurkIt introduces the idea of iterations, essentially soliciting multiple rounds of submissions, where users vote whether the "new" submission is better than the "old" one. Looking at the handwriting recognition task is pretty revealing why the approach works well: The first submitter takes a first pass, leaving blanks wherether the transcription is difficult. The second submitter fills-in (some of) the blanks, the third improves even more and so on. When there is no further improvement, the task ends. Very nice idea, I will be using it in the future.

I also learned about the internal crowdsourcing efforts at IBM (basic conclusion: giving a prize like iPod works much better than trying to motivate people through other marketing and management efforts... a good lesson for people trying to deploy enterprise prediction markets...)

######################################################################

In the second part of the workshop, we have seen some discussion on the role of game theory in the design of the human computation games.

The position paper by Shaili Jain and David Parkes "The Role of Game Theory in Human Computation Systems" gave an outline of promising directions for future research in this area.

The basic idea is that human computation may benefit by using game theoretic concepts to improve the design of the games. The basic argument is that the use of game theory also solved problems in settings like P2P networks, where game theory has been used to avoid the problem of free riding. Shaili gave a brief introduction to game theoretic analysis of some games and systems (e.g., PhotoSlap, ESP game and Yahoo Answers).

The talk advocated a modeling of user actions (e.g., in the ESP games players select "easy" or "difficult" words), the corresponding costs and benefits for the users, and how these affect the outcome of the game. The nice outcome is that game theory helps predict the equilibrium of such games, essentially predicting what the stable state of these games will be.

Some of the intriguing open questions:

1. How to quantify "fun"
2. How to introduce altruism in the models.
3. How to generate game theoretic models for the games described in the GWAP taxonomy (games with output agreement, input agreement, and inversion-problem games).
4. How to use game theoretic concepts of "population games" to model large number of agents that interact.

The high-level conclusion of the talk: It is good to build a game-theoretic model of each game, so that we can see how robust is the game to pertubations of design options.

#####################################################################

The game-theory discussion continued with the paper "On Formal Models for Social Verification" by Chien-Ju Ho and Kuan-Ta Chen.

The authors described how to use game theory to show the effect of sequential verification vs parallel verification. Parallel verification is the process in which two users submit an answer for a question, and if it matches they get a reward. Sequential is the process in which the user submits an answer that needs to match a pre-given "correct" answer. (e.g., "Guess what is the original question for this answer", which allows a sanity check of the answers). The paper provides the corresponding equilibria that result from these mechanisms.

######################################################################

The paper "Efficient Human Computation: the Distributed Labeling Problem" by Ran Gilad-Bachrach, Aharon Bar Hillel, and Liat Ein-dor tackled the following problem: Using humans we can collect labels and tags that describe an object (e.g., an image). When the number of possible labels is large, then we will start seeing consistency problems as different labelers are not coordinated. The labelers may provide correct answers but due to polysemy they end up giving superficially different labels, even though they mean the same thing ("truck" and "lorry"). Or due to homonymy they give the same label even though they mean different things (e.g. "greyhound" the dog, and "greyhound" the bus company).

The authors describe graph-theoretic algorithms that can be used to resolve such problems and provide bounds about the optimality of the proposed approaches. The question arised of how to deal with the fact that the same user may not be self-consistent over time. Also the question on how to deal with users of various degrees of reliability.

######################################################################

The last talk of the workshop was "Financial Incentives and the Performance of Crowds" by Winter Mason and Duncan J. Watts. The authors examine how Turkers respond to various levels of payment. Confirming my own observations, generally Turkers work more for higher pay but do not do much better work in terms of quality. So, paying higher gets more things done but the quality remains statistically the same (my own observation indicates that HITs paying more than 50 cents also tend to attract spammers, effectively decreasing the overall quality!)

In a test of anchoring, authors asked users if they felt that they have been fairly compensated. Interestingly enough, they felt that they were underpaid, valuing their work 2-3 cents more per HIT compared to the payment --- interesting enough, the difference was consistent across levels of payment (e.g., a 5 cent HIT is worth 10, a 10 cent HIT is worth 15 etc). So it may make sense to start giving a low-payment for the HITs at first, and once the psychological anchor is established, increase the payment to satisfy the workers that felt that the initial payment was small :-)

#####################################################################

The overall themes that emerged from the workshop were rather clear: One the one hand, there is the experimental side of human computation, where researchers are trying to devise new incentives for users to participate, new types of actions, and new modes of interaction. On the other hand, we have the more abstract/theoretic side, where researchers are trying to model these actions and incentives to examine what theory predicts about these designs. Also, there is work that examines what to do with the noisy results that are being generated by such games and systems: how can we best handle the noise and use the generated data for data mining purposes?

The final question over dinner was where to organize the next instance of the workshop? There are so many disciplines coming together in this line of work that finding a commonly acceptable venue might be a challenge. Will the CHI people contine coming to KDD? Or will data miners attend CHI to attend this workshop? What about the WWW conference? Would be a good match? I personally favor KDD, but we will have to wait and see the result of the human computation on this issue...

(We also have the wiki with the bibliography in the area http://hcomp2009.wikispaces.com/ which we will have to curate and organize better to reflect the results of this workshop.)

Read more »