اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Obnoxious Facility Location Game with Dichotomous Preferences
97
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider a facility location game in which $n$ agents reside at known locations on a path, and $k$ heterogeneous facilities are to be constructed on the path. Each agent is adversely affected by some subset of the facilities, and is unaffected by the others. We design two classes of mechanisms for choosing the facility locations given the reported agent preferences: utilitarian mechanisms that strive to maximize social welfare (i.e., to be efficient), and egalitarian mechanisms that strive to maximize the minimum welfare. For the utilitarian objective, we present a weakly group-strategyproof efficient mechanism for up to three facilities, we give a strongly group-strategyproof mechanism that guarantees at least half of the optimal social welfare for arbitrary $k$, and we prove that no strongly group-strategyproof mechanism achieves an approximation ratio of $5/4$ for one facility. For the egalitarian objective, we present a strategyproof egalitarian mechanism for arbitrary $k$, and we prove that no weakly group-strategyproof mechanism achieves a $o(sqrt{n})$ approximation ratio for two facilities. We extend our egalitarian results to the case where the agents are located on a cycle, and we extend our first egalitarian result to the case where the agents are located in the unit square.
قيم البحث
اقرأ أيضاً
We consider a new setting of facility location games with ordinal preferences. In such a setting, we have a set of agents and a set of facilities. Each agent is located on a line and has an ordinal preference over the facilities. Our goal is to desig
n strategyproof mechanisms that elicit truthful information (preferences and/or locations) from the agents and locate the facilities to minimize both maximum and total cost objectives as well as to maximize both minimum and total utility objectives. For the four possible objectives, we consider the 2-facility settings in which only preferences are private, or locations are private. For each possible combination of the objectives and settings, we provide lower and upper bounds on the approximation ratios of strategyproof mechanisms, which are asymptotically tight up to a constant. Finally, we discuss the generalization of our results beyond two facilities and when the agents can misreport both locations and preferences.
We study the facility location games with candidate locations from a mechanism design perspective. Suppose there are n agents located in a metric space whose locations are their private information, and a group of candidate locations for building fac
ilities. The authority plans to build some homogeneous facilities among these candidates to serve the agents, who bears a cost equal to the distance to the closest facility. The goal is to design mechanisms for minimizing the total/maximum cost among the agents. For the single-facility problem under the maximum-cost objective, we give a deterministic 3-approximation group strategy-proof mechanism, and prove that no deterministic (or randomized) strategy-proof mechanism can have an approximation ratio better than 3 (or 2). For the two-facility problem on a line, we give an anonymous deterministic group strategy-proof mechanism that is (2n-3)-approximation for the total-cost objective, and 3-approximation for the maximum-cost objective. We also provide (asymptotically) tight lower bounds on the approximation ratio.
Recommendation systems are extremely popular tools for matching users and contents. However, when content providers are strategic, the basic principle of matching users to the closest content, where both users and contents are modeled as points in so
me semantic space, may yield low social welfare. This is due to the fact that content providers are strategic and optimize their offered content to be recommended to as many users as possible. Motivated by modern applications, we propose the widely studied framework of facility location games to study recommendation systems with strategic content providers. Our conceptual contribution is the introduction of a $textit{mediator}$ to facility location models, in the pursuit of better social welfare. We aim at designing mediators that a) induce a game with high social welfare in equilibrium, and b) intervene as little as possible. In service of the latter, we introduce the notion of $textit{intervention cost}$, which quantifies how much damage a mediator may cause to the social welfare when an off-equilibrium profile is adopted. As a case study in high-welfare low-intervention mediator design, we consider the one-dimensional segment as the user domain. We propose a mediator that implements the socially optimal strategy profile as the unique equilibrium profile, and show a tight bound on its intervention cost. Ultimately, we consider some extensions, and highlight open questions for the general agenda.
We address the problem of strategyproof (SP) facility location mechanisms on discrete trees. Our main result is a full characterization of onto and SP mechanisms. In particular, we prove that when a single agent significantly affects the outcome, the
trajectory of the facility is almost contained in the trajectory of the agent, and both move in the same direction along the common edges. We show tight relations of our characterization to previous results on discrete lines and on continuous trees. We then derive further implications of the main result for infinite discrete lines.
The study of approximate mechanism design for facility location problems has been in the center of research at the intersection of artificial intelligence and economics for the last decades, largely due to its practical importance in various domains,
such as social planning and clustering. At a high level, the goal is to design mechanisms to select a set of locations on which to build a set of facilities, aiming to optimize some social objective and ensure desirable properties based on the preferences of strategic agents, who might have incentives to misreport their private information such as their locations. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting the different variants and methodologies, as well as the most interesting directions for future research.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
