BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Weighted Proportional Resource Allocation - Milan Vojnovic\, M
 icrosoft research Cambridge
DTSTART:20101018T133000Z
DTEND:20101018T143000Z
UID:TALK27401@talks.cam.ac.uk
CONTACT:Elena Yudovina
DESCRIPTION:We consider a weighted proportional allocation of resources th
 at allows providers to discriminate usage of resources by users. This fram
 ework is a generalization of well-known proportional allocation accommodat
 ing allocation of resources proportional to weighted bids or proportional 
 to submitted bids but with weighted payments.\n\nWe study a competition ga
 me where everyone is selfish: providers choose discrimination weights aimi
 ng at maximizing their individual revenues while users choose their bids a
 iming at maximizing their individual payoffs. We analyse revenue and socia
 l welfare of this game. We find that the revenue under so called price ant
 icipating users is lower bounded by k/(k+1) times the revenue under standa
 rd third-degree price discrimination with a set of k users excluded. Under
  price anticipating users with linear utility functions\, we find that the
  social welfare is at least 1/(1+2/\\sqrt{3}) of the maximum social welfar
 e (approx. 46%)\, and show that this bound is tight. We extend the latter 
 result to a broad class of utility functions\, which accommodates many uti
 lity functions found in literature and to an oligopoly of multiple competi
 ng providers. Our results suggest that the weighted proportional allocatio
 n achieves competitive revenue and social welfare despite the fact that ev
 eryone is selfish.\n\nThe mechanism allows for resource constraints descri
 bed by general polyhedrons that accommodate a variety of resources\, inclu
 ding networks of communication links\, systems of computing resources\, an
 d sponsored search ad slots.\n\nJoint work with Thanh Nguyen.
LOCATION:MR12\,  Centre for Mathematical Sciences\, Wilberforce Road\, Cam
 bridge
END:VEVENT
END:VCALENDAR