{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:08:40Z","timestamp":1767182920312,"version":"3.40.5"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"type":"electronic","value":"9781643685489"}],"license":[{"start":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T00:00:00Z","timestamp":1729036800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,10,16]]},"abstract":"<jats:p>We identify strategy proof mechanisms for facility location that simultaneously approximate well both the maximum distance from the nearest facility and the minimum utility of any agent. Somewhat surprisingly, while the deterministic MEDIAN\u00a0and the randomized ENDORAV\u00a0mechanisms perform optimally with respect to approximating the maximum distance, neither perform optimally with respect to approximating the minimum utility. With deterministic mechanisms for locating a single facility, we prove that the MIDORNEAREST\u00a0mechanism is optimal with respect to approximating both the maximum distance and the minimum utility. By comparison, the MEDIAN\u00a0mechanism has an unbounded approximation ratio for approximating the minimum utility. With randomized mechanisms for locating a single facility, we construct the first mechanism that is optimal with respect to approximating the minimum utility. For deterministic and randomized mechanisms locating two or more facilities, we identify strategy proof mechanisms that are within a constant factor of optimal with respect to both objectives.<\/jats:p>","DOI":"10.3233\/faia240907","type":"book-chapter","created":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T13:41:01Z","timestamp":1729172461000},"source":"Crossref","is-referenced-by-count":1,"title":["Approximate Mechanism Design for Facility Location with Multiple Objectives"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2998-8668","authenticated-orcid":false,"given":"Toby","family":"Walsh","sequence":"first","affiliation":[{"name":"AI Institute, UNSW Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2024"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA240907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T13:41:01Z","timestamp":1729172461000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA240907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,16]]},"ISBN":["9781643685489"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia240907","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"type":"print","value":"0922-6389"},{"type":"electronic","value":"1879-8314"}],"subject":[],"published":{"date-parts":[[2024,10,16]]}}}