BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250901T120000
DTEND;TZID=Asia/Kolkata:20250901T130000
DTSTAMP:20260923T224505
CREATED:20250806T062326Z
LAST-MODIFIED:20250809T094539Z
UID:1766-1756728000-1756731600@homecse.iitd.ac.in
SUMMARY:Giving Some Space Can Be Hard: Two New Models to Match Agents with Locations by Shivika Narang
DESCRIPTION:Abstract: There can be a multitude of reasons to match agents to specific locations in a given space. In this talk we cover two: distributing delivery orders and assigning shared hostel rooms. For both settings we shall try to find solutions that satisfy desirable properties and characterize instances for which they exist.\n \nWe first initiate the study of fair distribution of delivery tasks among a set of agents wherein delivery jobs are placed along the vertices of a graph. Our goal is to fairly distribute delivery costs (modeled as a submodular function) among a fixed set of agents while satisfying some desirable notions of economic efficiency. We characterize instances that admit fair and efficient solutions by exploiting underlying graph structures. Unfortunately\, finding these solutions proves to be NP-hard. We complement this by designing an XP algorithm (parameterized by the number of agents) that can find all fair and efficient solutions when they exist. We conclude this discussion by theoretically and experimentally analyzing the price of fairness.\n \nWe shall then introduce Leontief utilities to the problem of roommate matchings. We aim to find strategyproof mechanisms that give good bounds on agent welfare. We first find that no approximation to welfare can be achieved under strategyproof mechanisms for either Leontief or additive utilities. Even for binary additive utilities no maximum welfare mechanism can be strategyproof. In contrast\, we then –surprisingly– find that binary Leontief utilities enable us to find strategyproof mechanisms that maximize welfare.\n \nJoint work with Hadi Hosseini\, Sanjukta Roy and Tomasz Was.\n \nBio: Shivika Narang is a postdoctoral fellow at UNSW Sydney. Previously she was a postdoc at Simons Laufer Mathematical Sciences Institute\, Berkeley (SLMath) and completed her PhD from IISc Bengaluru. During her PhD\, she received the Tata Consultancy Services Research Fellowship. Her work is currently focused on finding fair and efficient solutions to societal problems. She largely works in computational social choice\, especially matching and allocation problems.
URL:https://homecse.iitd.ac.in/event/giving-some-space-can-be-hard-two-new-models-to-match-agents-with-locations-by-dr-shivika-narang/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR