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
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
\n\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
\n\n Joi nt work with Christos-Alexandros Psomas
\n \ nFor more information, contact k.r.apt at cwi.nl
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