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

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

第一作者簡介

Hongning Yuan

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

香港城市大學(xué)

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

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

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

via：ECAI  2016

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

原論文下載

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