論文精選 | 實現城市設備智能規劃？——具有可選偏好的設施選址游戲

具有可選偏好的設施選址游戲（Facility Location Games with Optional Preference）

摘要：本文中，我們對于一條線上具有兩個異構設施的設施選址游戲，提出了可選偏好模型。在這個新模型中代理允許有可選偏好，這為代理報告提供了更多的靈活性。致力于最小化代理成本或總成本的最大值，我們提出了不同的確定性策略-證明（ strategy-proof）機制（無需貨幣轉移）。根據代理關心哪個有可選偏好的設施，我們考慮了兩種版本的可選偏好模型：最小（關心最近的），最大（關心最遠的）。對于最小變型，我們對于最大成本目標提出了一個2-近似的機制，以及最低下界4/3，和總成本目標的（n/2+1）-近似機制，以及最低邊界2。對于Max變型，我們為最大成本目標提出了最優機制，且為總成本目標提出了2-近似機制。

第一作者簡介

Hongning Yuan

郵箱：hongnyuan2-c@my.cityu.edu.hk

香港城市大學

文章總結及應用場景

我們研究了兩個有著可選偏好的異構設施選址游戲，重點主要集中于確定性機制。這是一個新的模型，它涵蓋了更多的現實生活場景。我們還發現，如果隨機機制允許的話近似比可以更好。在我們的設置中這兩個設施可以放在連續線上的任何一點，也可以放在一起，這是很有合理的。然而，設施不能放在同一點上的情況也是一個有趣的研究方向。

我們論文中提出的一些機制可以應用到離散的情況下。例如，對于最小變型的最小化最大總成本，除非所有的代理都在一起，不然我們提出的機制將永遠不會找到有將兩個設施放在一起的情況，這種機制可以潛在的擴展到k-設施模型。

via：ECAI  2016

PS : 本文由雷鋒網獨家編譯，未經許可拒絕轉載！

原論文下載

雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。