# Wall Street's version of a combinatorial market

I was poking around TD AMERITRADE and came across this description of conditional orders (login required, or look here), or sequences of orders that are synchronized in various ways:

What is a conditional order and how do I place one?

Conditional orders let you combine two or three individual orders that will, if filled, either cancel or trigger additional orders. Conditional orders are available for both stocks and single-leg option orders (in option-approved accounts).

The following types of conditional orders are available:

• OCA (one cancels another) – submit two orders simultaneously; if one order is filled, the other is canceled.
• OTA (one triggers another) – submit an order and if that order is filled, submit another order.
• OTT (one triggers two) – submit an order and if that order is filled, submit two additional orders.
• OT/OCA (one triggers an OCA order) – submit an order; if that order is filled, submit two orders simultaneously; if one of these orders is filled, cancel the other.
• OT/OTA (one triggers an OTA order) – submit an order; if that order is filled, submit another order. If that order is filled, submit a third order.

At first glance these resemble combinatorial bids that allow traders to buy several things at once, but they’re not. They’re more like bidding agent programs that describe exactly what to do when under various conditions: more complex, but not fundamentally different, than limit orders and stop-loss orders. They can be executed without any cooperation from the exchange.

This brings to light a key distinction: some forms of expressiveness can be achieved by layering increasingly complicated bidding agents on top of an existing exchange. Other types of expressiveness, for example true combinatorial bids, require new optimization routines put directly into the exchange.

The distinction arises in advertising as well. In a sponsored search auction, advertisers can bid lower during the day when people tend to browse and higher in the evening when people tend to buy, and they can even write a program to do it for them automatically. However an advertiser cannot execute a “guaranteed delivery” contract in sponsored search without changing the underlying auction mechanism.

Why should we care about the latter type of expressiveness that requires “smarter” exchange mechanisms? One word: efficiency. Economic efficiency, that is. With greater expressiveness, resources can be shuffled to align more precisely with who wants them the most. Advertising opportunities (a particular user’s attention on a particular page) can go to advertisers who value them most. Financial transactions that otherwise might go unmet can be consummated. Insurance buyers can get better coverage. And gamblers can have more fun.

# Yahoo! Key Scientific Challenges student seed program

Yahoo! Research just published its list of key scientific challenges facing the Internet industry.

It’s a great resource for students to learn about the area and find meaty research problems. There’s also a chance for graduate students to earn \$5000 in seed funding, work with Yahoo! Research scientists and data, and attend a summit of like-minded students and scientists.

The challenges cover search, machine learning, data management, information extraction, economics, social science, statistics, multimedia, and computational advertising.

Here’s the list of challenges from the algorithmic economics group, my group. We hope it provides a clear picture of the goals of our group and the areas where progress is most needed.

We look forward to supporting students who love a challenge and would like to join us in building the next-generation Internet.

# NYCE Day: Thanks and thoughts

NYCE Day 2008 went very well, with over 100 attendees, great talks, and valuable discussion. Many thanks to the four plenary speakers — Costis, Asim, Susan, and Tuomas — and ten rump session speakers who came in from various NYC suburbs like Boston, Pittsburgh, and Palo Alto.

At dinner the night before,1 the organizers agreed that we were nervous because we weren’t at all nervous. Karin and Renee from the New York Academy of Sciences had taken care of almost everything, leaving little for us to fret about. It turned out we were right to not worry and wrong to worry about not worrying: indeed Karin, Renee, and NYAS were absolutely fantastic, orchestrating every detail of the event flawlessly, from technology to catered breaks. The venue itself is gorgeous — a well laid-out space in a modern building in the World Trade Center complex with stunning views2 and a number of nice touches, from an alcove with a computer station to check email to a subtle gradient in the wallpaper that slowly pixilates as your gaze moves from the center toward the side of the room. I came away incredibly impressed with NYAS and delighted to become a member.

Muthu provides an excellent summary of the event, divided into before and after lunch. Read that first and then come back here for my additional thoughts/notes:

1. Costis gave us mostly bad news. He summarized some of his award winning work with Christos Papadimitriou and Paul Goldberg proving that computing equilibrium behavior in almost any moderately complex game may be beyond the reach of our computers,3 let alone our brains. As a saying goes, “if your laptop can’t find it, then neither can the market” [attribution: Kamal Jain?]. Still, all may not be lost. These results, as is the nature of computational complexity results, say only that some games are extremely hard to solve, not all games or even most games. Since nature is not adversarial (Murphy’s Law aside), it may be the case that among games that arise in the real world that we care about, a number of them can be solved for equilibrium. The problem is defining what “realistic” means in this context: an almost impossibly fuzzy task. Costis did end with some positive results, showing that anonymous games can be solved efficiently. Anonymous games crop up in realistic situations, for example in analyzing traffic, where only the quantity of cars near you matters and not the identity of the drivers inside.
2. Asim described a sophisticated Bayesian model well suited for social network data that handles non-existant links — meaning the lack of connection between two people, by far the most common situation — much better than previous approaches. The approach is good for digging deeply into a small data set but at least for now has difficulty with moderately large amounts of data. (To get results in a reasonable amount of time, Asim had to down sample his already fairly modest sized corpus.) The talk didn’t help me overcome my bias that Bayesian methods ala UAI often don’t work well at Internet scales without modification.
3. Susan gave a fantastic and energetic talk. She advocates economic models of online advertising that include more sophisticated users, as opposed to typical models that assume users scan from the top of the page down in a precise sequence. She went further to claim that users may actually choose their search engine based on the quality of the ads. Personally, I’m a bit skeptical about that, though I do agree that there is an indirect effect: search engines with better paying ads can afford to buy more traffic and improve their algorithmic search more. Susan highlighted the enormous shift in mindset required between economic theory and practice when just computing the mean of a data stream can take weeks (though this is changing with tools like Hadoop that can bring such computations down to hours or minutes as Sebastien confirms).
4. Someone asked Tuomas why his expressive commerce company CombineNet uses first-price auctions instead of VCG pricing. He listed four of what he said were dozens of reasons on top of Rothkopf’s thirteen and Ausubel and Milgrom’s list. In fact he went further to say that as far as he knew no real auction anywhere in the world has ever used true VCG pricing for anything more complicated than selling a single good at a time.
5. For those not familiar, a rump session is open to anyone to speak briefly on any relevant topic. As it turns out, in part because brevity forces clarity, and in part because editorial filtering overweights mediocrity, the rump session is often the most interesting part of a conference. The “NYCE rump” session was no exception, with topics spanning ad auctions, reputation, Internet routing, and user generated content. Ivy Li proposed a clever scheme whereby eBay sellers are motivated to reward buyers for honest feedback. Sebastien presented work with Sihem and I on an expressive bidding language for online advertising with fast allocation and pricing algorithms, with the goal of moving the industry toward an open standard. Sampath Kannan on leave at NSF had encouraging news on the funding front, laying out his vision for CS theory funding with an explicit call for proposals at the boundary of CS and economics.
6. I think we did a good job of attracting a diversity of speakers and participants, with talks ranging from computational complexity to Bayesian models of social networks, with academia and industry represented, and with CS, economics, and business backgrounds represented.
 1We had dinner at Gobo, a fantastic restaurant Muthu recommended that truly opened my eyes in terms of the tastes and textures possible with a vegetarian menu. Delicious. 2Speaking of views, I had a stunning and fascinating one from my hotel the night before, looking straight down onto ground zero of the World Trade Center complex from a relatively high floor of the Millenium Hilton (apparently intentionally misspelled). I booked the room for \$185 on Hotwire, and then found out why. Though the WTC site still looks nearly empty, builders appear to be making up for lost time with round the clock construction. Put it this way: the hotel kindly provided complementary earplugs. All in all though the room and view were well worth the cost in dollars and sounds. 3Specifically, computing Nash equilibrium is PPAD-complete for most games. In terms of complexity classes, PPAD is a superset of P and a subset of NP. Almost surely there is no polynomial time algorithm, though the problem is not quite as hard as the classic NP-complete problems like traveling salesman.

# Reminder: NYCE Day and nicer views Oct 3 2008

If you were wavering on whether to attend NYCE Day (New York Computer Science and Economics Day) this Friday October 3, take a look at the New York Academy of Sciences venue where the event will be held. It’s spectacular.

Hope to see many folks there.

Here’s a brilliant idea: Centrist Messenger let’s you buy political ads with a money-back guarantee. You pay only if your preferred candidate wins. If the other candidate wins, you get your money back.

Centrist Messenger backs the guarantee with contracts purchased from intrade, in the same way that Priceline backs its “Sunshine Guarantee” with contracts from WeatherBill. (So presumably fully insured ads cost about twice as much as uninsured ads.)

Centrist Messages can … make strong advocacy of a position and candidate. However, this advocacy cannot demonize the other side, focus solely on personality, or make false representations of the candidates’ positions.

I’ll add Centrist Messenger to WeatherBill, Priceline, Yoonew, and FirstDIBZ (was TicketReserve) as companies fashioning creative ways to package and sell “markets in uncertainty” in the US amid a challenging legal and regulatory landscape.

What other useful and/or fun ways can you imagine re-packaging gambles as either insurance or contingent goods? Here are some of my own brainstorms:

• Buy a ticket to a sporting event whose cost is refunded if your team loses.
• Buy a “streak ticket”: entitles you to a ticket to the next game as long as your team keeps winning. (Variant: “K-loss ticket” entitles you to tickets until your team loses K times.)
• Buy a “playoff run ticket” which gives you tickets, flights, hotel, etc. for the duration of your team’s playoff run. In other words, as long as your team keeps winning, you keep getting tickets, hotel, and flight to the next game. You may be able to buy this at the beginning of the season cheaply since it’s worth nothing if your team does not make the playoffs.
• Buy “price drop” insurance: If that precious electronic gadget you just bought (read: iPhone) drops in price within N days, get K times your money back.

# New York Computer Science and Economics Day (NYCE Day) October 3, 2008

We invite participants to the first New York Computer Science and Economics Day (NYCE Day), viagra 60mg October 3 2008, unhealthy at the New York Academy of Sciences, 7 World Trade Center.

NYCE Day is a gathering for people in the NYC metropolitan area with interests in auction algorithms, economics, game theory, e-commerce, marketing, and business to discuss common research problems and topics in a relaxed environment. The aim is to foster collaboration and the exchange of ideas.

The program features invited speakers Asim Ansari (Columbia), Susan Athey (Harvard), Constantinos Daskalakis (MIT), and Tuomas Sandholm (CMU), and a rump session with short contributed presentations.

You can indicate your interest in the event on upcoming.yahoo but official registration should go through NYAS.

Your participation and suggestions are greatly welcome. Please distribute this announcement to people and groups who may be interested.

Thanks,
NYCE Day Organizers
Anindya Ghose, NYU
David Pennock, Yahoo!
Sergei Vassilvitskii, Yahoo!

P.S. This is one week prior and in the same location as the Symposium on Machine Learning.

P.P.S. For those familiar, NYCE Day is inspired as a Right Coast version of BAGT.

P.P.P.S. The New York Academy of Sciences in a spectacular venue. See for yourself.

# The seedy side of Amazon's Mechanical Turk

I mostly side with Lukas and Panos on the fantastic potential of Amazon’s Mechanical Turk, a crowdsourcing service specializing in tiny payments for simple tasks that require human brainpower, like labeling images. Within the field of computer science alone, this type of service will revolutionize how empirical research is done in communities from CHI to SIGIR, powering unprecedented speed and scale at low cost (here are two examples). My guess is that the impact will be even larger in the social sciences; already, a number of folks in Yahoo’s Social Dynamics research group have started running studies on mturk. (A side question is how university review boards will react.)

However there is a seedier side to mturk, and I’m of two minds about it. Some people use the service to hire sockpuppets to enter bogus ratings and reviews about their products and engage in other forms of spam. (Actually this appears to violate mturk’s stated policies.)

For example, Samuel Deskin is offering up to ten cents to turkers willing to promote his new personalized start page samfind.

EARN TEN CENTS WITH THE BONUS – EASY MONEY – JUST VOTE FOR US AND COMMENT ABOUT US

EARN FOUR CENTS IF YOU:

1. Set up an anoymous email account likke gmail or yahoo so you can register on #2 anonymously

3. Visit http://www.thesearchrace.com/recent.php and vote for:

samfind

By clcking “Pick”

SIX CENTS BONUS:

4. Visit the COMMENTS Page on The Search Race, it is the Button Right Next to “Picks” on this page: http://www.thesearchrace.com/recent.php and

5. Say something awesome about samfind (http://samfind.com) on The Search Race’s Comments page.

Make sure to:

1. Tell us that you Picked us.
2. Copy and Paste the Comment you typed on The Search Race’s Comment page here so we know you wrote it and we will give you the bonus!

In fact, Deskin is currently offering bounties on mturk for a number of different spammy activities to promote his site. On the other hand, what Deskin is doing is not illegal and is arguably not all that different than paying PRWEB to publish his rah-rah press release (Start-up, samfind, Launches Customizable Startpage to Compete with Google, Yahoo & MSN, Los Angeles, California (PRWEB) August 4, 2008). And I have to at least give him credit for offering the money under his own name.

Another type of task on mturk involves taking a piece of text and paraphrasing it so that the words are different but the meaning remains the same. Here is an example:

Paraphrase This Paragraph

Here’s the original paragraph:

You’re probably wondering how to apply a wrinkle filler to your skin. The good news is that it’s easy! There are a number of different products on the market for anti aging skin care. Each one comes with its own special application instructions, which you should always make sure to read and carefully follow. In general, however, most anti aging skin care products are simply applied to the skin and left to soak in.

Requirements:
1. Use the same writing style as much as possible.
2. Vary at least 50% of the words and phrases – but keep the same concepts. Use obviously different sentences! Your paragraph should not be just a copy of the first with a few word replacements.
3. Any keywords listed in bold in the above paragraph must be included in your paraphrase.
4. The above paragraph contains 75 words… yours must contain at least 64 words and not more than 101 words.
5. Write using American English.
6. No obvious spelling or grammar mistakes. Please use a spell-checker before submitting. A free online spell checker can be found at www.spellcheck.net.

If you find it easier to paraphrase sentence-by-sentence, then do that. Please do not enter anything in the textbox other than your written paragraph. Thanks!

I have no direct evidence, but I imagine such a task is used to create splogs (I once found what seems like such a “paraphrasing splog”), ad traps, email spam, or other plagiarized content.

It’s possible that paid spam is hitting my blog (either that or I’m overly paranoid). I’m beginning to receive comments that are almost surely coming from humans, both because they clearly reference the content of the post and because they pass the re-captcha test. However, the author’s URL seems to point to an ad trap. I wonder if these commenters (who are particularly hard to catch — you have to bother to click on the author URL) are paid workers of some crowdsourcing service?

Can and should Amazon try to filter away these kinds dubious uses of Mechanical Turk? Or is it better to have this inevitable form of economic activity out in the open? One could argue that at least systems like mturk impose a tax on pollution and spam, something long argued as an economic force to reduce spam.

My main objection to these activities is the lack of disclosure. Advertisements and press releases are paid for, but everyone knows it, and usually the funding source is known. However, the ratings, reviews, and paraphrased text coming out of mturk masquerade as authentic opinions and original content. I absolutely want mturk to succeed — it’s an innovative service of tremendous value, one of many to come out of Amazon recently — but I believe Amazon is risking a minor PR backlash by allowing these activities to flow through its servers and by profiting from them.

# Call for Papers and Participation: Workshop on Ad Auctions: Chicago, July 8-9 2008

I am happy to announce the following ad auctions workshop and solicit submissions and participants.

=======================================================================
Call for Papers

July 8-9, 2008
Chicago, Illinois, USA

SUBMISSIONS DUE MAY 11, 2008

In conjunction with the
ACM Conference on Electronic Commerce (EC’08)
=======================================================================

We solicit submissions for the Fourth Workshop on Ad Auctions, to be
held July 8-9, 2008 in Chicago in conjunction with the ACM Conference
on Electronic Commerce. The workshop will bring together researchers
and practitioners from academia and industry to discuss the latest

In the past decade we’ve seen a rapid trend toward automation in
advertising, not only in how ads are delivered and measured, but also
in how ads are sold. Web search advertising has led the way, selling
space on search results pages for particular queries in continuous,
dynamic “next price” auctions worth billions of dollars annually.

Now auctions and exchanges for all types of online advertising —
including banner and video ads — are commonplace, run by startups and
Internet giants alike. An ecosystem of third party agencies has grown
to help marketers manage their increasingly complex campaigns.

The rapid emergence of new modes for selling and delivering ads is
fertile ground for research from both economic and computational
perspectives. What auction or exchange mechanisms increase advertiser
value or publisher revenue? What user and content attributes
contribute to variation in advertiser value? What constraints on
supply and budget make sense? How should advertisers and publishers
bid? How can both publishers and advertisers incorporate learning and
optimization, including balancing exploration and exploitation? How do
practical constraints like real-time delivery impact design? How is
exchanges evolve in the next decade? How should they evolve?

Papers from a rich set of empirical, experimental, and theoretical
perspectives are invited. Topics of interest for the workshop include
but are not limited to:

* Comparison shopping
* Mechanism and market design for advertising
* Ranking and placement of ads
* Computational and cognitive constraints
* Game-theoretic analysis of mechanisms, behaviors, and dynamics
* Matching algorithms: exact and inexact match
* Equilibrium characterizations
* Simulations
* Laboratory experiments
* Empirical characterizations
* Pay for impression, click, and conversion; conversion tracking
* Campaign optimization; bidding agents; search engine marketing (SEM)
* User satisfaction/defection
* User incentives and rewards
* Affiliate model
* Click fraud detection, measurement, and prevention
* Price time series analysis
* Multiattribute and expressive auctions

We solicit contributions of two types: (1) research contributions,
and (2) position statements. Research contributions should report new
(unpublished) research results or ongoing research. The workshop
proceedings can be considered non-archival, meaning contributors are
free to publish their results later in archival journals or
conferences. Research contributions can be up to ten pages long, in
double-column ACM SIG proceedings format:
http://www.acm.org/sigs/publications/proceedings-templates
Position statements are short descriptions of the authors’ view of how
ad auction research or practice will or should evolve. Position
statements should be no more than five pages long. Panel discussion
proposals and invited speaker suggestions are also welcome.

The workshop will include a significant portion of invited
presentations along with presentations on accepted research
contributions. There will be time for both organized and open
discussion. Registration will be open to all EC’08 attendees.

The first three workshops on sponsored search auctions successfully
attracted a wide audience from academia and industry working on
various aspects of web search advertising. Following the footsteps of
the previous workshops, the Fourth Workshop on Ad Auctions strives to
be a venue that helps address challenges in the broader field of
online advertising, by providing opportunities for researchers and
practitioners to interact with each other, stake out positions, and
present their latest research findings. While the first three
scope this year to include auctions and exchanges for any form of

Submission Instructions
=======================

Research contributions should report new (unpublished) research
results or ongoing research. The workshop’s proceedings can be
considered non-archival, meaning contributors are free to publish
their results later in archival journals or conferences. Research
contributions can be up to ten pages long, in double-column ACM SIG
proceedings format:
http://www.acm.org/sigs/publications/proceedings-templates
Positions papers and panel discussion proposals are also welcome.

Papers should be submitted electronically using the conference
management system:
no later than midnight Hawaii time, May 11, 2008. Authors should also
email the organizing committee ( adauctions2008@yahoogroups.com ) to
indicate that they have submitted a paper to the system.

At least one author of each accepted paper will be expected to attend
and present their findings at the workshop.

Important Dates
===============

May 11, 2008 Submissions due midnight Hawaii time
a. Submit to:
May 23, 2008 Notification of accepted papers
June 8, 2008 Final copy due

Organizing Committee
====================

Susan Athey, Harvard University
Rica Gonen, Yahoo!
Jason Hartline, Northwestern University
David Pennock, Yahoo!
Siva Viswanathan, University of Maryland

Program Committee
=================

Animesh Animesh, McGill University
Moshe Babaioff, Microsoft
Tilman Borgers, University of Michigan
Max Chickering, Microsoft
Chris Dellarocas, University of Maryland
Ben Edelman, Harvard University
Jane Feng, University of Florida
Slava Galperin, A9
Anindya Ghose, New York University
Kartik Hosanagar, University of Pennsylvania
Kamal Jain, Microsoft
Jim Jansen, University of Pennsylvainia
Sebastien Lahaie, Yahoo!
John O. Ledyard, Caltech
Ying Li, Microsoft
Ilya Lipkind, A9
Preston McAfee, Yahoo!
Chris Meek, Microsoft
John Morgan, University of California Berkeley
Michael Ostrovsky, Stanford University
Abhishek Pani, Efficient Frontier
Martin Pesendorfer, London School of Economics
David Reiley, Yahoo!
Tim Roughgarden, Stanford University
Catherine Tucker, Massachusetts Institute of Technology
Rakesh Vohra, Northwestern University

================

or email the organizing committee:

The absurdity of gambling laws in the US leads to such silliness as:

• In 2007, Google, Microsoft, and Yahoo! paid millions in penalties for placing gambling ads, something they haven’t done since they were told to stop in 2004.

# FYI 2 CFPs: WWW2008-IM & ACM EC'08

Here are two Call For P*s for upcoming academic/research conferences:

1. Call for Participation: For the first time, the World Wide Web Conference has a track on Internet Monetization, including topics in electronic commerce and online advertising. The conference will be held in Beijing April 21-25, 2008. If the Olympics in China are all about image, then the Internet in China is all about, well, Monetization. (A lot of it, growing fast.)
2. Call for Papers: The 2008 ACM Conference on Electronic Commerce will be held in Chicago July 8-12, 2008 in proximity to AAAI-08 and GAMES 2008. Research papers on all aspects of electronic commerce — including personal favorites prediction markets and online advertising — are due February 7, 2008.

You can signal your interest on social events calendar upcoming.org: WWW2008 | EC’08

Hope to see some of you in either the Forbidden or Windy City, as the case may be.