CS 286r – Student Comments,
Zhenming Liu
This is another interesting paper that studies the usability
and sustainability of scrip systems in a game theoretical way. The model and
some of the results are intriguing. It looks like an important pioneer study in
this area.
A few comments/questions regarding the models/results:
1. All the
agents are homogeneous in this model. It is clearly interesting to see the
system’s behavior with heterogeneous agents. My guess is most of the theorems
do not break.
2. The
assumption that everyone has at most $k$ dollar in section 3 looks strange to
me. In particular, the author is using a local argument to justify the
assumption (i.e., “since if someone has more than k dollars, he will just spend
money until he has at most k dollar) while I thought the point of the analysis
is to find the system’s global behavior.
3. The result of
Theorem 3.1 looks quite weak. It did not specify whether it is polynomial-time
convergent (I think it would be quite hard to prove poly-time convergent though).
Nevertheless, some of the papers’ experiments seem to add further evidence for
the convergent behavior.
4. In section 4, only existence of Equilibria is proven. Maybe it will also be interesting to see whether the equilibria is unique.
Haoqi Zhang
The main contribution of the paper is the game theoretic
modeling of a scrip system for P2P networks. Specifically, the authors show
that players playing a simple threshold strategy (e.g., offer services if money
is below a certain amount) leads to a Nash Equilibrium of the game in which the
entropy can be maximized in terms of money each player holds. The authors then
show that the total amount of money (adjusted for price) is a parameter that
can be chosen to maximize social welfare.
I enjoyed the paper because the authors provide a lot of
good intuition for comparative statics in the system.
Also, the authors not only allow but specifically model the affect of
altruistic agents on the system. I found the analysis to be very clean, and the
model to be applicable to a number of realistic situations.
The authors have already pointed out many of the work's shortcomings - one which I find potentially troubling is the assumption that players join with no money. Would minor fluctuations in the money supply cause large changes in behavior?
Travis May
Free loaders are ubiquitous on the internet. A small number of altruistic users provide a
very large percentage of the content and distribution channels that free-loading
individuals use across the internet. Not
only does this phenomenon exist in peer-to-peer systems, but it’s also common
in other systems that we’ve looked at, such as Wikipedia
or Yahoo Answers. The presence of free
loaders is common because there is no clear incentive for posting content, yet
a clear incentive for downloading content – creating a “tragedy of the commons”
where insufficient individuals are contributing to the system for it to
adequately serve its number of users.
The solution that is proposed is the use of “scrip” (or
money). By adding a currency to the
system, users are incentivized to cooperate, so they
do not have to be simply “altruistic.” However, the paper argues that
individuals follow a threshold strategy, in which they have “enough” money at
some threshold $k and are no longer willing to work for more money.
The most straightforward solution to this problem seems to
be the use of real currency over an artificial currency. Real currency means that there is always a
substitute use for the currency, so nobody ever has “enough” or “too much” money. There will also be no incentive for hoarding, and no variable incentives across users: the value
of cooperation will be immediately clear.
Of course, using real currency runs into two main problems. First, on a technical level, processing micro-transactions
can be problematic as current payment systems require sizable fees that make
micro-transactions prohibitively expensive.
Second, this system can be seen to favor wealthy participants. Fortunately, both of these objections can be
overcome.
While micro-payments would be ideal, an internal currency could still be used – just as long as the internal currency can be readily converted into a real currency at a fixed value. The exchange market would require transaction fees to occur only once as the initial transaction is made, but subsequent transactions would all use the internal currency and face no fee. The second, normative, response could in fact be more problematic. However, is it any worse for a system to give arbitrary power to the wealthy than early adopters (at the expense of new members). Furthermore, is this system truly exploitative if it provides an otherwise non-existent source of real income for the individuals who are then willing to provide their resources.
Malvika Rao
A very interesting paper which presents a formal model of a
scrip system
and shows the existence of Nash
equilibrium when agents use a threshold
strategy. It raises several
interesting questions - both theoretical and
practical implementation issues. It
would be interesting to see what
happens when a cost of membership
is enforced in these scrip systems,
keeping in line with the cost
models introduced in the previous papers we
have seen. Once again sybils and collusion pose a
problem. It would be
interesting to explore those issues further.
Michael Aubourg
A first remarkable feature of online services is that the
individual utilizing the resources of the system derives a greater benefit from
it than the cost to the same individual providing it.
We can illustrate this example with several examples :
On Kazaa, it almost doesn't cost
me anything to share my files. Only a share of my bandwidth.
On the contrary, I gain a big utility when I download a file :
I save the time I would have to spend in order to find the file somewhere else
on Internet, or I save the money I would have to spend, to buy the file (music)
in a real store.
Similarly, replying to a question asked by someone else does
only cost me the time to write the answer down. On the opposite, receiving a
free answer to a question I asked clearly raises my utility.
Now I would like to speak about altruists. Such a person
feels pleasure from the sense that they provide the music that everyone is
playing.
Does it really exist ? Can we
really feel pleasure to share with unknown people ?
Furthermore, thanks to the nowadays speed increasing, a lot of people do now "massive
downloading"
without necessarily listening to
the music after. So I am not sure this notion still does make sense.
In addition, I did not understand what pushed the authors to
think that the Markov Chain arisen in the paper is rapidly mixing.
In the part 6, the need for money is not as critical if
money is easier to obtain, and this is quiet important.
Theoretically speaking, an agent can indeed drive down or
up, the cost of fulfilling a request by introducing or removing many sybils. But does it exist in reality ?
The number of sybils should be really important to have a noticeable effect. The author often mentions the sybils attack. In his model, there is no cost for being a member of the system. But this is unlikely to happened. The 0-cost is almost impossible. So even if the costs are small, this should have a great impact on sybils attack.
Sagar Mehta
This paper considers the use of scrip systems in P2P
networks as a mechanism to encourage sharing and decrease free-riding. The
paper provides primarily theoretical results, showing the existence of a NE
where agents utilize a threshold strategy, computing efficiency, and optimizing
the price to maximize efficiency. One thing that confused me about the model
was the payment system described. In the paper, there was an actual exchange
between requester and provider. But in true P2P networks, multiple agents
provide some service simultaneously. For instance, in BitTorrent
a file is broken up into pieces. Is the payment meant to be spread across each
provider in that case? I'm not sure if the model described correctly accounts
for this. I think a slight variation of the scrip system is also worth
examining. In an online system where it is easy to measure things such as
upload/download ratio, the system itself can restrict the speed of downloads
depending on the number of files a user is currently sharing.
Another thought I had on P2P systems: by their nature, it is hard to control the spread of viruses through them – which basically reduces the utility of everyone using the system. I don't think a model of a P2P system can be complete without incorporating some malicious users. This can be accomplished by having some small probability that you will have great disutility from a file download. I'd be interested in incentive strategies that seek to make P2P systems immune to such attacks.
Nikhil Srivastava
The Friedman paper analyzes threshold strategies in scrip systems, motivated by the recurring example of downloads in a P2P network, and shows the existence of a Nash equilibrium for one such strategy in all agents. It also calculates the optimal money supply that maximizes efficiency in such a system. Of particular importance is the fact that new users come in with zero money (reducing the Sybil threat), and the money supply can be adjusted accordingly to provide the the same incentive structure. I wonder why it is "prohibitively expensive to ensure that bank account balances can never go negative" - perhaps something to do with implementation and tracking information in a distributed system.
Angela Ying
The first paper discussed theoretical results for scrip
systems in P2P sharing networks. In this system, users must "pay" to
download files and are "paid" to upload files. The result of the
paper says that eventually this system converges to an equilibrium where for a
certain k, if a user has more than k in money he will download files until he
reaches k, and if a user has less than k he will upload files until he reaches
k. This is assuming that all users are "standard" i.e. not altruistic,
such that in a non-scrip system the user will lose utility if he shares files. This
paper is interesting because it proposes a system that is sybil-proof,
since users start with 0, and works in an environment where there are no
altruistic users. A problem with this assumption is that currently, there are
pretty much altruistic users in any P2P sharing network, which would cause
interesting effects such as "hoarding" that would prevent the system
from reaching an equilibrium.
This paper proposes a very cool idea for P2P systems. However,
I had a couple of questions and concerns about it. First of all, I was unclear
about the cost structure for new users, and how the entire system would be
initialized (would the makers of the software have all the money, which they
distribute?) to have money in the system at all. Second of all, this paper
seems to assume that everyone has the same demand and the same supply (in
quantity) of files, which may not necessarily be true. Presumably, a user with
more private MP3s to begin with would not need as many new MP3s to download,
whereas a user with no MP3s to begin with would need many MP3s to download and
none to share.
Finally, for future work I think it would be interesting to
look at the effects of a scrip system where one is able to use real money to
purchase points in the system.
For the second paper on Yootopia, it discussed a bunch of decision mechanisms and their pros and cons in terms of fairness and other measures, and then proposed a system based on bartering Yootles, presumably in a virtual world. Essentially it establishes a prediction market, but you can barter, auction, vote, and do a lot of the mechanisms that are discussed in the paper. While this is an interesting system, I question the usefulness. What motivates people to participate in the yootles system? I was not sure how such a system could be applied, and how all of these decision mechanisms are used in that context.
Peter Blair
Efficency and Nash Equilibria in Scrip System for P2P
In P2P networks, it is often the case that a few users are
providing the bulk of content that is shared on the website. The other users in
effect are "free riders" -- benefiting from the service without
contributing to it. With increasing cost to the super users in the form of
increased cost for bandwidth from ISP to the possiblity
of getting sued from media houses owning the copy write, these P2P networks
risk loosing some of their most important network nodes. To address this
concern, the authors survey the constant strategies
used to encourage more democratic sharing on P2P networks such as a barter
system in which the network is a meeting place for users with mutual exchange
interest. This market structure is in efficient in terms of matching mutally interested parties, so there is some need for a
global currency system, in this case the scrip that is modelled.
The authors show that there is a threshold strategy that is a nash equilibrium of the P2P
network where a user will accept a request given that she has below a certain
threshold value in her network account. In equilibrium it turns out that the
number of users with a given amount of money maximizes the entropy of the
system. An interesting point that is mentioned in the article with respect to
new users is to require that they bring some value to the site by either
offering a private MP3 collection or something of the sort. Presumably, this
could be a good way to guard against whitewashing. I would like to see this
idea explored further.
Yootopia
In this paper the authors propose a type of proxy for money which can be used by agents to facilitate mamizing social welfare in group context. The unit of currency is called the yootle and the goal to to create a decision making process that respects a number of desirable qualitities e.g. maximizes social welfare, is pareto optimal, incentivizes truth telling, is envy proof (agents do not wish to trade places), etc. The authors then characterize different type of games that have some some these properties, cataloguing how these games work and even proposing a few new mechanisms. It seems like a system like this would work well in election-type environments but might not fare any better than monetary currency in more transactional situations where relative power of the agents in the group is determined in part by individual wealth and stature within the group context.
Alice Gao
The main contribution of this paper was to provide a model
of P2P networks and analyze the equilibria based on a
scrip system. First of all, the paper
proposed a model superior than the previously proposed models based on the
prisoner's dilemma game. Next, the paper
assumed that everyone is playing threshold strategy, and discovered that the
system will rapidly converge to the maximum entropy distribution. The last section stated the fact that there
exists a non-trivial equilibrium where all users play some threshold strategy.
I especially like the model proposed by the paper. When we were reading the paper "the
cheap social cost of pseudonyms", I found that the model using the
prisoner's dilemma game was not realistic enough. This paper addressed several issues regarding
this point. The matching model used by
this paper incorporated the idea that given a request, there may be people who
are willing, unwilling, able, or unable to satisfy the request. So the matching process should account for
these possibilities.
Also, I found the analysis on the convergence behaviour to the maximum entropy distribution to be very
intriguing. I believe for these systems,
it is more important to investigate the process by which the system achieves
some equilibrium than merely stating that some equilibria exist.
Although this is a very simple example in which agents don't change
their strategies, it is still a very useful approach to be applied to other
cases.
The section discussing sybil attacks and collusions is also very interesting. An interesting extension of this paper would be to investigate possible sybil attacks and collusions to determine the degree to which certain manipulations could derive monetary gains.
Nicholas Wells
Efficiency and Nash Equilibria in
a Scrip System for P2P Networks
The authors analyze a scrip system and shows that there is
an NE of agents using threshold strategies. They show that maintaining a ratio
between agents and money should be one of the most important things to maintain.
One criticism of this paper is that the authors analyze a
system that is costless to join. By adding an initial cost to the system, there
is a difference in the utility function that may change their results. This would
be an interesting course of study to take to advance this research. It is one
that the authors also mention for future work.
Another question that I have is whether they sufficiently
addressed the different behaviors of users. Users may not necessarily follow
the same strategies that the authors use and with enough users they probably
will not.
In general, I just wonder how the maintenace
ratio supposedly would change with these different utility functions. It would
be interesting to compare this more to actual data too.
Lastly, I just wanted to let everyone know that there's this
scrip system website called goozex.com that is currently giving out free video
games in order to get new users to the website. (they
actually just give free points - enough for 1 game). I just joined and
apparently, they just shipped out my free video game. It's supposed to be a
video game trading site using a scrip system. The only thing preventing people
from getting multiple free video games is that there is only one account per
mailing address. If you sign up for an account, say that nicholasw22
recommended you.
Yootopia!
In this paper, the authors examine the online monetary
system, yootopia! They examine how it becomes used
just as regular currency in some cases. They introduce several mechanisms for
achieving certain properties in the system. They also discuss the implementation
of their yootopia system in general.
I think it would be interesting to discuss how the previous paper is relevant to this one.
Rory Kulz
Efficiency and Nash Equilibria in
a Scrip System for P2P Networks
Agents are picked uniformly at random to make requests, but
in a real
P2P network, it is more likely that a small number of users
do a lot
of downloading whereas a large
number of users do substantially less.
While, as they say, this permits a model-specific sybil attack that
would not occur in practice, what
are the other implication sof this
assumption which seems extremely
strong?
The problem of altruists outlined in Proposition 2.1 breaks
down
entirely if we don't assume a
discounting of future utils (i.e. delta
is 1) or yields an unrealistic
bound for a if we assume delta
sufficiently close to 1. Furthermore,
the idea that there are enough
altruists to service every request
is quite unrealistic. The paper
fails to analyse
the most important case, which they mention in the
conclusion: "What happens
between these extremes [of no altruists and
sufficiently many altruists]?"
Effectively, this paper makes a lot of sense and has a good
proposal
at heart, but the implications of
introducing scrip need to be fleshed
out more; there are just too many
questions remaining in the
conclusion.
Yootopia!
There's a lot here, sort of overwhelming. The NFA mechanism
is pretty
interesting, and I think actually
pretty reasonable for plenty of
scenarios.
There's plenty of opportunities for
future work, of course. One thing
I noticed is that almost all the sorts of mechanisms
considered have
the budget-balance property, i.e. they
don't require any sort of
subsidy. Can we possibly achieve
more results by subsidizing the
market somehow?
Lastly, what has become of Yootopia?
The site appears to be down,
though something is brewing over at Yootles.com.
Ziyad Aljarboua
Although the cost of providing services in P2P networks is
low (e.g. cost of bandwidth), it can still be nontrivial. This structure leads
users to only benefit from the system and not contribute to it.
This paper presents a model for interaction in P2P networks.
It shows that adding a monetary incentive in the system can lead to Nash
equilibrium where users contribute to the system as opposed to only utilizing
its resources. It analyzes the effect of varying the amount of money on they
system's overall efficiency. Efficiency was shown to be maximized when an
appropriate ration between the total amount of money and number of agents is
maintained.
In this model, user's requests (e.g. for files) are
propagated to users who can satisfy these requests but their action is
completely voluntary. If the request is satisfied, requester utility becomes 1
and supplier encores a cost of less that 1. Using this method, we can capture
the total utility of users over a period of time. Using the model presented in
this paper, users who satisfy requests achieve positive utility instead by
making the requester pay some specific amount. It is shown here that with this
model, there exists a Nash equilibrium when all agents
use a threshold strategy.
To best understand this model, i find it a good idea to think of eBay. Because while this model seems to present a new idea, I find it a traditional one where users pay for a service or a product just like in eBay. Also, as mentioned in this paper, this scheme might produce many problems such as nonpayment or false transaction. And the only way to address such issues is by a reputation system which is something the writers have dismissed from the beginning.
Xiaolu Yu
The main contribution of the first paper is exploring a
group of decision mechanisms for group decision making and prediction. New
mechanism decision auction is introduced for redistributing the VCG surplus to
achieve greater fairness and social efficiency while retaining a semblance of
incentive compatibility. The authors point out another mechanism with
altruistic players, normally fair auction is less incentive compatible than
decision auction. The use of Yootles is valid because
some statistical studies have shown that there is no statistical difference in
the results when play money is used instead of real money.
A large part of the value of prediction market is not only
in predicting answers to questions to a certain extent of accuracy, but also in
gathering thorough information and knowledge out of the ensemble market to make
better decisions. Participants must be able to collect reasonable incentives to
make their efforts worthwhile, but social rewards like reputation may be more
effective than purely monetary rewards, since financial rewards are too small
and awkward sometimes due to legal and regulatory reasons, according to Bo Cowgill from Google. This leads
me to think if Yootopia would work better if such
social rewards are introduced, at least as a supplementary of Yootles.
The second paper analyzes a scrip system and shows that a
Nash equilibrium where all agents play a threshold strategy exists. By
maintaining the appropriate ration between the total amount of money and the
number of agents, efficiency is maximized. A fixed population of rational users
is critical to the stability of a system.
The authors suggest some extension of their work, one of them is to impose a small cost to become a member of the system. Another possible way, which is al widely employed in many p2p system currently, could be using monetary incentives to solve the free riding problem. Users have to pay to download files from other peers. The payments may either be in real money or in an internal used currency. How the system performance changes as the total amount of internal currency available could be an interesting topic to study.
Brett Harrison
This paper presents a theoretical model for a particular
kind of scrip system, applicable to P2P networks. In P2P networks, users make
requests for a transfer, such as the transfer of a music file, and other users
respond to that request by volunteering to transfer to the requesting users. There
are some clear problems with the basic structure of P2P networks, which include
Sybil attacks, whitewashing, and dependence on altruism. A scrip system tries
to combat some of these problems by introducing a cost to requesting a transfer
and a reward to volunteering for a transfer. The paper specifically analyzes
equilibrium strategies for threshold strategies where a user volunteers for a
transfer if that user has less than K dollars for some constant K.
I think this a fine paper with some interesting theoretical
results. However, the problem I have with scrip systems is that they defeat the
purpose of many modern, successful P2P networks. For example, the reason that
the majority of users participate in Bittorrent or Kazaa is that they did not want to pay money for certain
downloadable things, such as music and movies. The fact that the scrip system
introduces a cost to any request seems to undermine the motivation behind the
creation of many of these P2P systems. The paper does not analyze how, given a
general utility function that could place much higher value in money, a person
might not choose to enter the P2P as a requester in order to save money, and a
person might enter a P2P system only as someone who accepts requests in order
to make money. This behavior doesn't seem to be stable. Moreover, once the "alruists" are volunteering for requests mainly to
receive monetary gain, they aren't really altruists anymore, and the incentive
model changes.