面向多個自利Agent的資源分配問題的研究.pdf

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

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

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