面向多個(gè)自利Agent的資源分配問(wèn)題的研究.pdf

1、如何根據(jù)多個(gè)自利Agent對(duì)某些資源的喜好有效地、公平地給他們分配資源，這在經(jīng)濟(jì)學(xué)和計(jì)算機(jī)科學(xué)中都是非常重要的，在這個(gè)過(guò)程中往往要考慮經(jīng)濟(jì)效益與社會(huì)平等。在計(jì)算機(jī)科學(xué)和人工智能領(lǐng)域，除了“效益”和“公平”這兩個(gè)維度，我們還很關(guān)心資源分配中的“計(jì)算性問(wèn)題”:即如何設(shè)計(jì)高效的算法來(lái)得到一個(gè)“好”的分配，以及分配中涉及到的其他計(jì)算性問(wèn)題。本文將從計(jì)算效率角度研究分配制度設(shè)計(jì)問(wèn)題，設(shè)計(jì)能以高的計(jì)算效率得到兼顧經(jīng)濟(jì)效益和社會(huì)平等的分配方案和算法。

2、
　　本文首先研究了在不帶貨幣支付(side payment)的情況下不可分割物品的分配問(wèn)題。本文提出了一個(gè)并行的不帶誘導(dǎo)過(guò)程的資源分配協(xié)議來(lái)對(duì)不可分割物品進(jìn)行分配。在分配過(guò)程的每一輪次中，我們選擇一些Agent（根據(jù)特定的并行分配政策）報(bào)告自己在剩余的物品中最喜歡的一個(gè)，如果在這一輪次中只有一個(gè)Agent報(bào)告某個(gè)物品，那么這個(gè)Agent獲得該物品，否則，由多個(gè)Agent抽簽決定物品的歸屬。理論和實(shí)驗(yàn)結(jié)果表明這個(gè)分配協(xié)議在功利主義

3、和平均主義標(biāo)準(zhǔn)下均比之前的串行無(wú)誘導(dǎo)協(xié)議更有優(yōu)勢(shì)，同時(shí)本文對(duì)這個(gè)協(xié)議下的策略性問(wèn)題進(jìn)行了研究。然后本文從可計(jì)算性角度研究了如何在限價(jià)環(huán)境下對(duì)不可分割資源進(jìn)行合理地分配。筆者提出了一個(gè)多項(xiàng)式時(shí)間的算法來(lái)尋找資源的“供不應(yīng)求集合”，然后設(shè)計(jì)了一個(gè)可以在多項(xiàng)式時(shí)間內(nèi)得到“受限的Walrasian均衡”的動(dòng)態(tài)競(jìng)價(jià)分配制度，定義并指出了如何計(jì)算買方Agent的“期望利潤(rùn)”和資源的“期望價(jià)格”，并從期望利潤(rùn)的角度討論了該制度下的策略性問(wèn)題。