BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/4302/7-February-2012-On-Worst-Case-Allocations-in
-the-Presence-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:20120207T160000
DTEND: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 \
n For more information, contact k.r.apt at cwi.nl

\n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/4302/7-February-2012-On-Worst-Case-Allocations-in
-the-Presence-of-Indivisible-Goods-E-Markakis
END:VEVENT
END:VCALENDAR