0
本文作者: 章敏 | 2016-09-02 17:34 |
摘要:本文中,我們對于一條線上具有兩個(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é)
我們研究了兩個(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)載須知。