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
truthfully, or can
they benefit from
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.
If the agent believes the probability is 40%, then she should sell some