English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a strategic variant of the facility location problem. We wouldlike to locate a facility on a closed interval. There are n agents located onthat interval, divided into two types: type 1 agents, who wish for the facilityto be as far from them as possible, and type 2 agents, who wish for thefacility to be as close to them as possible. Our goal is to maximize a form ofaggregated social benefit: maxisum- the sum of the agents' utilities, or theegalitarian objective- the minimal agent utility. The strategic aspect of theproblem is that the agents' locations are not known to us, but rather reportedto us by the agents- an agent might misreport his location in an attempt tomove the facility away from or towards to his true location. We thereforerequire the facility-locating mechanism to be strategyproof, namely thatreporting truthfully is a dominant strategy for each agent. As simplymaximizing the social benefit is generally not strategyproof, our goal is todesign strategyproof mechanisms with good approximation ratios.  For the maxisum objective, in the deterministic setting, we provide abest-possible 3- approximate strategyproof mechanism; in the randomizedsetting, we provide a 23/13- approximate strategyproof mechanism and a lowerbound of \frac{2}{\sqrt{3}}. For the egalitarian objective, we provide a lowerbound of 3/2 in the randomized setting, and show that no bounded approximationratio is attainable in the deterministic setting. To obtain our deterministiclower bounds, we characterize all deterministic strategyproof mechanisms whenall agents are of type 1. Finally, we consider a generalized model that allowsan agent to control more than one location, and provide best-possible 3- and3/2- approximate strategyproof mechanisms for maxisum, in the deterministic andrandomized settings respectively, when only type 1 agents are present.

Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location