Communications - March 2010

to give $100 as well. It should be noted that both donors (as well as the charity) prefer this outcome to the outcome that results when they make their decisions separately (which is for both of them to give $0).

In practice, a matching offer is generally made by a single large donor, offering to match donations by multiple smaller donors. As we just saw, simple matching offers can lead to improved results, but they are still restrictive. What can be done if multiple donors want to make their donations conditional on the others’ donations? This type of expressiveness can lead to even better outcomes, but one has to be careful to avoid circularities. For example, consider the case where A will match B’s contribution, and B will match A’s contribution.

We proposed a system in which each donor can make her donation conditional on the total donated to the charity by all the donors combined. 10 In fact, the framework allows for donations to be conditional on the total amounts donated to multiple charities. We also designed algorithms for determining the final outcome based on everyone’s offers, which is NP-hard in general but tractable in special cases. We used this system to collect donations for the victims of the Indian Ocean tsunami, and later for the victims of Hurricane Katrina. While the total amount collected from these events was small (about $1,000), the events gave some insight into how donors use the system. About 75% of the donors made their donations conditional on the total amount collected, suggesting that donors appreciated being able to do so. One interesting observation is that the effectiveness of the system (in terms of how much participants were willing to donate) apparently depended on whose donations the donors were matching. The tsunami event was conducted among the participants of a workshop, so that to some extent everyone knew everyone else; in contrast, the hurricane event was open to anyone. The tsunami event was more successful, perhaps because the participants knew whose donations they were matching. More recent systems also allow donors to make their donations conditional only on the donations from selected parties, taking social network structure into account. 14 I believe this innovation

Are the agents
incentivized to
communicate
their preferences
and beliefs
truthfully, or can
they benefit from
misreporting them?

has the potential to make such systems much more successful.

Prediction markets. The markets I have considered so far generally produce a tangible outcome, such as an allocation of resources. The participating agents have different preferences over the possible outcomes, and the market is a mechanism for finding a good outcome for these preferences. The type of market that I discuss next is a little different.

A prediction market37 concerns a particular future event whose outcome is currently uncertain. For example, the event could be an upcoming sports game, or an election. The agents trading in the prediction market generally cannot (significantly) influence the outcome of the event; the goal of the market is merely to predict the outcome of the event, based on the collective information and reasoning of the participating agents. Typically, the market prediction is in the form of a probability: for example, the market’s assessment may be that the probability that team A will beat team B is 43%. Prediction markets are quite popular on the Web: examples include the Iowa Electronic Markets as well as Intrade. Each of these runs prediction markets on a variety of events; it appears that the political events (for example, predicting the winner of an election) are the most popular.

A common way to run a prediction market is as follows. We create a security that pays out (say) $1 if team A wins, and $0 if team A does not win. We then let agents trade these securities. Eventually, this should result in a relatively stable market price: for example, the security may trade at about $0.43. This can be interpreted to mean that the market (that is, the collection of agents) currently believes the probability that team A will win is about 43%.

If an agent disagrees with this assessment, then she should buy or sell some of the securities. For example, if an agent believes that the probability is 46% (even after observing the current market price of $0.43), then she can buy one of the securities at price $0.43, and her expected payout for this security will be 46% · $1 = $0.46. As she buys more securities, the market price will eventually go up to $0.46.