BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//5.981//EN
TZID:Asia/Jerusalem
X-WR-TIMEZONE:Asia/Jerusalem
BEGIN:VEVENT
UID:81@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210616T113000
DTEND;TZID=Asia/Jerusalem:20210616T123000
DTSTAMP:20210609T064041Z
URL:https://web.iem.technion.ac.il/site/iemevents/barter-exchange-with-len
gth-sensitive-utility-functions/
SUMMARY:Barter Exchange with Length Sensitive Utility Functions [ \n Ga
me Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Matan-el Shpiro \n Advisors: \n Where: Bloomfield 424 Fro
m:\nTechnion\nAbstract:\n\nConsider a \\emph{barter exchange} problem over
a finite set of agents\, where each agent owns an item and is also associ
ated with a (privately known) \\emph{wish list} of items belonging to the
other agents. An outcome of the problem is a (re)allocation of the items t
o the agents such that each agent either keeps her own item or receives an
item from her (reported) wish list\, subject to the constraint that the l
ength of the trading cycles induced by the allocation is up-bounded by a p
respecified \\emph{length bound} $k$. The utility of an agent from an allo
cation is $0$ if she keeps her own item\; and it is $\\lambda(\\ell)$ if s
he receives an item from her (true) wish list and participates in a tradin
g cycle of length $2 \\leq \\ell \\leq k$\, where $\\lambda$ is a prespeci
fied monotonically non-increasing \\emph{length function}. (The agent incu
rs a large dis-utility if she receives an item that is neither hers nor be
longs to her wish list.)\n\nIn this talk\, we investigate the aforemention
ed barter exchange problem from the perspective of mechanism design withou
t money\, aiming for truthful (and individually rational) mechanisms whose
objective is to maximize the \\emph{social welfare}. As the construction
of a social welfare maximizing allocation is computationally intractable f
or length bounds $k \\geq 3$\, we focus on (computationally efficient) tru
thful mechanisms that approximate the optimal social welfare. In particula
r\, we establish upper and lower bounds on the guaranteed approximation ra
tio\, expressed in terms of the length bound $k$ and the length function $
\\lambda$. Our main technical contribution is an algorithmic tool that can
be viewed as a truthful version of the \\emph{local search} paradigm.\n\n
(joint with Y. Emek)
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VTIMEZONE
TZID:Asia/Jerusalem
X-LIC-LOCATION:Asia/Jerusalem
BEGIN:DAYLIGHT
DTSTART:20210326T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:IDT
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR