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

摘要：本文中，我們對于一條線上具有兩個異構(gòu)設(shè)施的設(shè)施選址游戲，提出了可選偏好模型。在這個新模型中代理允許有可選偏好，這為代理報告提供了更多的靈活性。致力于最小化代理成本或總成本的最大值，我們提出了不同的確定性策略-證明（ strategy-proof）機制（無需貨幣轉(zhuǎn)移）。根據(jù)代理關(guān)心哪個有可選偏好的設(shè)施，我們考慮了兩種版本的可選偏好模型：最?。P(guān)心最近的），最大（關(guān)心最遠的）。對于最小變型，我們對于最大成本目標提出了一個2-近似的機制，以及最低下界4/3，和總成本目標的（n/2+1）-近似機制，以及最低邊界2。對于Max變型，我們?yōu)樽畲蟪杀灸繕颂岢隽俗顑?yōu)機制，且為總成本目標提出了2-近似機制。

第一作者簡介

Hongning Yuan

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

香港城市大學

文章總結(jié)及應(yīng)用場景

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

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

via：ECAI  2016

PS : 本文由雷鋒網(wǎng)獨家編譯，未經(jīng)許可拒絕轉(zhuǎn)載！

原論文下載

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。