BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
X-WR-TIMEZONE:Europe/Amsterdam
BEGIN:VTIMEZONE
TZID:Europe/Amsterdam
X-LIC-LOCATION:Europe/Amsterdam
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:/NewsandEvents/Archives/2012/newsitem/4302/7-F
 ebruary-2012-On-Worst-Case-Allocations-in-the-Pres
 ence-of-Indivisible-Goods-E-Markakis
DTSTAMP:20120126T000000
SUMMARY:On Worst-Case Allocations in the Presence 
 of Indivisible Goods, E. Markakis
ATTENDEE;ROLE=Speaker:E. Markakis (Athens)
DTSTART;TZID=Europe/Amsterdam:20120207T160000
DTEND;TZID=Europe/Amsterdam:20120207T000000
LOCATION:CWI, Science Park 123, room L017
DESCRIPTION:We study a fair division problem, wher
 e a set of indivisible goods is to be allocated to
  a set of n agents. Each agent may have different 
 preferences, represented by a valuation function t
 hat is a probability distribution on the set of go
 ods. In the continuous case, where goods are infin
 itely divisible, it is well known that proportiona
 l allocations always exist, i.e., allocations wher
 e every agent receives a bundle of goods worth to 
 him at least 1/n. In the presence of indivisible g
 oods however, this is not the case and one would l
 ike to find worst case guarantees on the value tha
 t every agent can have. We focus on algorithmic an
 d mechanism design aspects of this problem.    In 
 the work of [Hill 1987], an explicit lower bound w
 as identified, as a function of the number of agen
 ts and the maximum value of any agent for a single
  good, such that for any instance, there exists an
  allocation that provides at least this guarantee 
 to every agent. The proof however did not imply an
  efficient algorithm for finding such allocations.
  Following upon the work of Hill, we first provide
  a slight strengthening of the guarantee we can ma
 ke for every agent, as well as a polynomial time a
 lgorithm for computing such allocations. We then m
 ove to the design of truthful mechanisms. For dete
 rministic mechanisms, we obtain a negative result 
 showing that a truthful 2/3-approximation of these
  guarantees is impossible. We complement this by e
 xhibiting a simple truthful algorithm that can ach
 ieve a constant approximation when the number of g
 oods is bounded. Regarding randomized mechanisms, 
 we also provide a negative result, showing that we
  cannot have truthful in expectation mechanisms un
 der the restrictions that they are Pareto-efficien
 t and satisfy certain symmetry requirements.    Jo
 int work with Christos-Alexandros Psomas  For more
  information, contact k.r.apt at cwi.nl
X-ALT-DESC;FMTTYPE=text/html:\n        <p>We study
  a fair division problem, where a set of\n        
 indivisible goods is to be allocated to a set of n
 \n        agents. Each agent may have different pr
 eferences, represented\n        by a valuation fun
 ction that is a probability distribution on\n     
    the set of goods. In the continuous case, where
  goods are\n        infinitely divisible, it is we
 ll known that proportional\n        allocations al
 ways exist, i.e., allocations where every agent\n 
        receives a bundle of goods worth to him at 
 least 1/n. In the\n        presence of indivisible
  goods however, this is not the case\n        and 
 one would like to find worst case guarantees on th
 e value\n        that every agent can have. We foc
 us on algorithmic and\n        mechanism design as
 pects of this problem.\n      </p>\n      <p>\n   
      In the work of [Hill 1987], an explicit lower
  bound was\n        identified, as a function of t
 he number of agents and the\n        maximum value
  of any agent for a single good, such that for\n  
       any instance, there exists an allocation tha
 t provides at\n        least this guarantee to eve
 ry agent. The proof however did not\n        imply
  an efficient algorithm for finding such\n        
 allocations. Following upon the work of Hill, we f
 irst provide\n        a slight strengthening of th
 e guarantee we can make for every\n        agent, 
 as well as a polynomial time algorithm for computi
 ng\n        such allocations. We then move to the 
 design of truthful\n        mechanisms. For determ
 inistic mechanisms, we obtain a negative\n        
 result showing that a truthful 2/3-approximation o
 f these\n        guarantees is impossible. We comp
 lement this by exhibiting a\n        simple truthf
 ul algorithm that can achieve a constant\n        
 approximation when the number of goods is bounded.
  Regarding\n        randomized mechanisms, we also
  provide a negative result,\n        showing that 
 we cannot have truthful in expectation mechanisms\
 n        under the restrictions that they are Pare
 to-efficient and\n        satisfy certain symmetry
  requirements.\n      </p>\n      <p>\n        Joi
 nt work with Christos-Alexandros Psomas</p>\n    \
 n        <p>For more information, contact <a class
 ="email">k.r.apt <span class="at">at</span> cwi.nl
 </a></p>\n    
URL:/NewsandEvents/Archives/2012/newsitem/4302/7-F
 ebruary-2012-On-Worst-Case-Allocations-in-the-Pres
 ence-of-Indivisible-Goods-E-Markakis
END:VEVENT
END:VCALENDAR