An official website of the United States government
We study the k-facility location games with optional preferences on the line. In the games, each strategic agent has a public location preference on the k facility locations and a private optional preference on the preferred/acceptable set of facilities out of the k facilities. Our goal is to design strategyproof mechanisms to elicit agents’ optional preferences and locate k facilities to minimize the social or maximum cost of agents based on their facility preferences and public agent locations. We consider two variants of the facility location games with optional preferences: the Min variant and the Max variant where the agent’s cost is defined as their distance to the closest acceptable facility and the farthest acceptable facility, respectively. For the Min variant, we present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost with k ≥ 3 facilities, achieving approximation ratios of 3 and 2n+1 respectively. We complement the results by establishing lower bounds of 3/2 and n/4 for the approximation ratios achievable by any deterministic strategyproof mechanisms for the maximum cost and social cost, respectively. We then improve our results in a special setting of the Min variant where there are exactly three facilities and present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost. For the Max variant, we present an optimal deterministic strategyproof mechanism for the maximum cost and a k-approximation deterministic strategyproof mechanism for the social cost.
more »
« less
Strategyproof Linear Regression in High Dimensions
This paper is part of an emerging line of work at the intersection of machine learning and mechanism design, which aims to avoid noise in training data by correctly aligning the incentives of data sources. Specifically, we focus on the ubiquitous problem of linear regression, where strategyproof mechanisms have previously been identified in two dimensions. In our setting, agents have single-peaked preferences and can manipulate only their response variables. Our main contribution is the discovery of a family of group strategyproof linear regression mechanisms in any number of dimensions, which we call generalized resistant hyperplane mechanisms. The game-theoretic properties of these mechanisms --- and, in fact, their very existence --- are established through a connection to a discrete version of the Ham Sandwich Theorem.
more »
« less
- Award ID(s):
- 1718549
- PAR ID:
- 10075968
- Date Published:
- Journal Name:
- Proceedings of the 2018 ACM Conference on Economics and Computation
- Page Range / eLocation ID:
- 9-26
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.more » « less
-
Multi-output Gaussian process (GP) regression has been widely used as a flexible nonparametric Bayesian model for predicting multiple correlated outputs given inputs. However, the cubic complexity in the sample size and the output dimensions for inverting the kernel matrix has limited their use in the large-data regime. In this paper, we introduce the factorial stochastic differential equation as a representation of multi-output GP regression, which is a factored state-space representation as in factorial hidden Markov models. We propose a structured mean-field variational inference approach that achieves a time complexity linear in the number of samples, along with its sparse variational inference counterpart with complexity linear in the number of inducing points. On simulated and real-world data, we show that our approach significantly improves upon the scalability of previous methods, while achieving competitive prediction accuracy.more » « less
-
We study the group-fair obnoxious facility location problems from the mechanism design perspective where agents belong to different groups and have private location preferences on the undesirable locations of the facility. Our main goal is to design strategyproof mechanisms that elicit the true location preferences from the agents and determine a facility location that approximately optimizes several group-fair objectives. We first consider the maximum total and average group cost (group-fair) objectives. For these objectives, we propose deterministic mechanisms that achieve 3-approximation ratios and provide matching lower bounds. We then provide the characterization of 2-candidate strategyproof randomized mechanisms. Leveraging the characterization, we design randomized mechanisms with improved approximation ratios of 2 for both objectives. We also provide randomized lower bounds of 5/4 for both objectives. Moreover, we investigate intergroup and intragroup fairness (IIF) objectives, addressing fairness between groups and within each group. We present a mechanism that achieves a 4-approximation for the IIF objectives and provide tight lower bounds.more » « less
-
We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In such a variation, agents have preferences on the ideal locations of the facility on a real line, and the facility’s location is fixed in advance where (re)locating the facility is not possible due to various constraints (e.g., limited space and construction costs). To improve the accessibility of agents to facilities, existing mechanism design literature in FLPs has proposed to structurally modify the real line (e.g., by adding a new interval) or provide shuttle services between two points when structural modifications are not possible. In this paper, we focus on the latter approach and propose to construct an accessibility range to extend the accessibility of the facility. In the range, agents can receive accommodations (e.g., school buses, campus shuttles, or pickup services) to help reach the facility. Therefore, the cost of each agent is the distance from their ideal location to the facility (possibility) through the range. We focus on designing strategyproof mechanisms that elicit true ideal locations from the agents and construct accessibility ranges (intervals) to approximately minimize the social cost or the maximum cost of agents. For both social and maximum costs, we design group strategyproof mechanisms and strong group strategyproof mechanisms with (asymptotically) tight bounds on the approximation ratios.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
