SecondReport < Main

Main Web>TWikiUsers>JeremyBarbay>DigitalCooperatives>SecondReport (2006-10-12, JeremyBarbay) (raw view)
<H1>The Lazy Professor Problem</H1>

<H2> Introduction </H2>

A lazy professor has to come up with n questions to include in an assignment for a class. The professor has a choice. He (she) can either generate the n questions himself, or can access an assignment question database and download some problems. However, before the professor can download problems, it must contribute a certain number of problems to the database. At the same time there are other lazy professors at other universities who are doing the same thing. Ideally, we would like to have a mechanism where enough new problems are being uploaded so that no professor has to create an entire assignment by itself, that all professors contribute some problems (i.e. there is no  free-riding ), and that the database grows in proportion with the number of users. 

<H2> The Model </H2>
Assume that there are m agents (professors). Each can upload and download files from the database. Agent i needs to produce ni problems for an assignment. It can generate its own problems but at cost ci for each problem. Thus, its utility for acting on its own is uown i =  cini. Agent i also can contribute problems to the database and, in exchange, download additional problems. In particular, if agent i uploads nup i problems, then it need only download ndown i = ni   nup i . Its utility for participating in such a setup will depend on " The number of items it uploads. Recall that there is a cost, ci, associated with creating an item. Thus, if agent i uploads nup i items then its cost is at least cinup i . " The number of items it is allowed to download. If there is not enough items in the database, or the agent is not allowed to download enough items, then it has to create additional items for its assignment. " Whether there is a cost to downloading problems or not. 

There are several problems which we wish to address.
   1. If an agent agrees to upload a certain number of items, then the database must be large enough so that it can download enough questions.
   2. As more agents use the database, then we would like the database to grow in size. However, I imagine that we would also like the number of contributions a single agent has to make to decrease also. That is, we would like to see the cost of participating in the database decrease. 

<H2> Approach </H2>

The first approach that we can take is to assume that the game is only played once. The problem becomes whether or not there are enough agents willing to upload problems so that in exchange they can download the rest of the problems, and, additionally, how many problems should each agent upload. When formulated like this, I believe it is very similar to a public project problem. In a public project, a group of agents have to decide whether some common object should be implemented (in particular, whether the agents are willing to collectively pay enough for the object). In our database problem, the object would be whether there will be enough problems in the database so that everyone can download the right amount. The  payments  would be number of files each agent has to upload. Agents will have to  bid , that is announce the maximum number of files they are willing to upload. The mechanism would then decide whether there is enough interest, and determine the number of files each agent really does need to upload. I think that a (variation of the) Clarke Tax may work here. There are still some details that need to be worked out. In the Clarke Tax agents declare their valuations for the object   we will have to figure out what we want the valuations to be. It might be something as simple as the number of files they are willing to contribute, their cost for creating a file, or some combination. I am inclined to go with the number of files they would upload and want to download, but I still need to think about this. Second, the Clarke Tax selects the outcome which maximizes the sum of the agents  valuation functions. Again, we need to think about what we are trying to optimize. 

Another approach that could be used is a variation of the Moulin-Shenker cost sharing mechanism. I am not so familiar with this mechanism. However, I am attaching the paper, so if you want we can go through it and see if it would be useful. 

We also want to study different protocols, in particular we are interested in determining what sort of contribution rules are required to make the mechanism work. For example, we might consider a rule that says that for every submission, an agent can download p items. We can define 1 p as the pressure to publish problems. The question now becomes whether we can find a value p such that the upload is maximized. Again, I think we can apply a Clarke Tax like mechanism here, to help figure out what p should be. Note that p will likely be dependent on the ci s and the ni s. Jeremy has hypothesized that the graph will look something like a positive convex function of the presure.

 In the long term, our goal is to actually have a database that grows and regenerates. 

<H2>Appendix</H2> 

<H3>Clarke Tax</H3> 
The Clarke Tax (or Pivotal mechanism) is a member of the Vickrey-Clarke- Groves (VCG) family of mechanisms. This family of mechanisms are for settings where agents have quasi-linear utilities and have several desirable properties including being incentive-compatible and Pareto e cient. 

Agents  utility functions capture their preferences over outcomes. In a quasi- linear setting we assume that an outcome o consists of two components. That is o = (x, t) where x is some choice from a discrete choice set and t is a transfer vector, which specifies how much an agent must pay or be paid. A quasi-linear utility has the form ui(o,  i) = vi(x,  i) + ti where vi(x,  i) is the agent s valuation function, and depends on the choice made by the mechanism and the type,  i of the agent. 

The Clarke Tax works in the following way. First, each agent is asked to submit a valuation function, v2 i to the mechanism, which specifies how much they are willing to pay to have the public project. Note that we do not assume that v2 i = vi, i.e. agents are not required to truthfully state their valuation functions. 

Given the announced valuation functions of the agents, the mechanism de-termines the choice x  such that x  = argmax x m X i v2 i(x) (I am just folding the type of the agent into the valuation function to make the notation easier.) In the public project application, the choice is between implementing the project or not. In our database example it could be between having the database or not. 

The transfers for each agent are computed by ti =X j6=i v2 j(x2)  Xj 6= iv2 j(x ) where x2 is the optimal choice when agent i did not exist. That is x2 = argmax x X j6=i v2 j(x). 

What ends up happening is that by using such a mechanism agents have in- centive to truthfully reveal their valuations. Additionally, the outcome selected is the optimal outcome given the agents preferences. The Clarke Tax is also individually rational. This means that an agent is better o  participating than not participating. One problem with it is that it is not budget balanced which means that we will likely collect more assignment problems than is needed. We will have to think whether this will be a problem. 

-- Main.klarson -- 25 Nov 2004
   * [[%ATTACHURL%/LazyProf.pdf][LazyProf.pdf]]: The PDF version, with correct formules.
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pdf	LazyProf.pdf	r1	manage	48.8 K	2004-11-30 - 13:32	JeremyBarbay	The PDF version, with correct formules.
Topic revision: r3 - 2006-10-12 - JeremyBarbay
Main
TWiki Webs
CSEveryBody
- AIMAS
- CERAS
- CF
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW
My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images
Edit