Scholarlink

<p>In this paper, we study the heterogeneous facility location game with fractional preferences under resource constraints. In this model, a group of agents are positioned along the interval [0,&#xa0;1], where each agent has position information and fractional preferences indicated as support weights for facilities. Our main focus is to design mechanisms that choose and locate one facility out of two facilities while motivating agents to truthfully report their information, aiming to approximately maximize the social utility, defined as the sum of utilities of all agents. Based on the types of private information held by agents, we consider three different settings. For the known-preferences setting, we provide a deterministic group strategy-proof mechanism with 2-approximation and a randomized group strategy-proof mechanism with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\frac{4}{3}\)</EquationSource> </InlineEquation>-approximation. We also provide lower bounds of 2 on the approximation ratio for any deterministic strategy-proof mechanism and 1.043 for any randomized strategy-proof mechanism. For the known-positions setting and the general setting, we present a deterministic group strategy-proof mechanism with 6-approximation and a randomized strategy-proof mechanism with 4-approximation, respectively. Furthermore, we give lower bounds of 1.554 for any deterministic strategy-proof mechanism and 1.2 for any randomized strategy-proof mechanism in the known-positions setting. Finally, we extend the model to the scenario of choosing <i>k</i> facilities out of <i>m</i> facilities. For the known-preferences setting, we provide a 2-approximate deterministic group strategy-proof mechanism, which is also the best deterministic strategy-proof mechanism. For the known-positions setting, when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(k \ge 2\)</EquationSource> </InlineEquation>, we give a lower bound of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2-\frac{1}{k}\)</EquationSource> </InlineEquation> for any deterministic strategy-proof mechanism.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Heterogeneous facility location games with fractional preferences and limited resources

  • 期刊论文

  • 发表日期：

    2025年10月13日

查看全文
  • Jiazhu Fang,
  • Qizhi Fang,
  • Wenjing Liu,
  • Minming Li

摘要

In this paper, we study the heterogeneous facility location game with fractional preferences under resource constraints. In this model, a group of agents are positioned along the interval [0, 1], where each agent has position information and fractional preferences indicated as support weights for facilities. Our main focus is to design mechanisms that choose and locate one facility out of two facilities while motivating agents to truthfully report their information, aiming to approximately maximize the social utility, defined as the sum of utilities of all agents. Based on the types of private information held by agents, we consider three different settings. For the known-preferences setting, we provide a deterministic group strategy-proof mechanism with 2-approximation and a randomized group strategy-proof mechanism with \(\frac{4}{3}\) -approximation. We also provide lower bounds of 2 on the approximation ratio for any deterministic strategy-proof mechanism and 1.043 for any randomized strategy-proof mechanism. For the known-positions setting and the general setting, we present a deterministic group strategy-proof mechanism with 6-approximation and a randomized strategy-proof mechanism with 4-approximation, respectively. Furthermore, we give lower bounds of 1.554 for any deterministic strategy-proof mechanism and 1.2 for any randomized strategy-proof mechanism in the known-positions setting. Finally, we extend the model to the scenario of choosing k facilities out of m facilities. For the known-preferences setting, we provide a 2-approximate deterministic group strategy-proof mechanism, which is also the best deterministic strategy-proof mechanism. For the known-positions setting, when \(k \ge 2\) , we give a lower bound of \(2-\frac{1}{k}\) for any deterministic strategy-proof mechanism.