YuruChurch 悠日教會

一般定義

假設某個資源被指派給多個代理，每個代理 $i$ 獲得一份 $X_{i}$ 。每位經紀人 $i$ 有個人偏好關係 $\succeq _{i}$ 對不同的可能份額。如果對於所有 $i$ 和 $j$ ：

X_{i}\succeq _{i}X_{j}

無嫉妒的另一個術語是無嫉妒（NE）。

如果代理的偏好用價值函數來表示 $V_{i}$ ，那麼這個定義就等於：

V_{i}(X_{i})\geq V_{i}(X_{j})

換句話說：我們說代理 $i$ 羨慕經紀人 $j$ 如果 $i$ 更喜歡 $j$ 在他自己的作品上，即：

X_{i}\prec _{i}X_{j}

V_{i}(X_{i})<V_{i}(X_{j})

如果沒有代理嫉妒另一個代理，則該部門被稱為無嫉妒部門。

特殊情況

1958 年，喬治·伽莫夫^和馬文·斯特恩^提出了無嫉妒性^的概念。孩子，使得沒有一個孩子會嫉妒另一個。對於n =2 個孩子，這可以透過分割和選擇演算法來完成，但對於n>2，問題就困難得多。看看令人無羨的切蛋糕過程。

在切蛋糕時，EF 表示每個孩子都認為自己的份額至少與其他人份額一樣大；在瑣事分工中，EF 意味著每個代理人都認為他們的份額至少與其他代理人的份額一樣小（這兩種情況下的關鍵問題是沒有代理人願意與任何其他代理人交換他們的份額）。參見雜務分工。

1967 年，鄧肯^‧福利⁽ Duncan Foley)將無嫉妒性引入了^資源配置的經濟學問題中。只要給予每個人 1/ n的每種資源，就很容易實現無嫉妒。從經濟角度來看，挑戰在於將其與帕累托效率結合。此挑戰首先由David Schmeidler和Menahem Yaari定義。^[³^]參見「有效的無嫉妒分工」。

當要分配的資源是離散的（不可分割的）時，即使只有一種資源和兩個人，也可能無法實現無嫉妒。有多種方法可以解決這個問題：

在參與者之間轉移金錢以補償那些獲得價值較低的物品的人。例如，該解決方案可用於租賃和諧問題以及無嫉妒定價問題。
共享少量物品。例如，在調整後的獲勝者程式中可以完成此操作。
找到近似公平的分配；參見無嫉妒物品分配。
找到盡可能大的部分無嫉妒分配；看到無羨慕匹配。
使用隨機化來找出預期中無嫉妒的分配（「事前」）；參見公平隨機分配。

變體

強無嫉妒性要求每個代理人嚴格地偏好他的捆綁包而不是其他捆綁包。^[ 4 ]

超級無嫉妒性要求每個主體嚴格偏好自己的捆綁商品而不是總價值的1/ n ，並且嚴格偏好其他每個捆綁商品而不是總價值的 1/ n 。 ^[ 4 ]^[ 5 ]顯然，超級無嫉妒意味著強無嫉妒，而強無嫉妒又意味著無嫉妒。

群體無嫉妒性（也稱為聯盟無嫉妒性）是無嫉妒性的強化，要求每個參與者群體都感覺到他們分配的份額至少與任何其他同等規模的群體的份額一樣好。一個較弱的要求是每個個體代理人不嫉妒任何其他代理的聯盟；有時它被稱為嚴格的無嫉妒性。^[ 6 ]

隨機支配無嫉妒性（SD-envy-free，也稱為必要無嫉妒性）是對代理報告項目序數排名的設定中的無嫉妒性的一種加強。它要求對於所有與序數排名相容的加法估值，都保持無嫉妒性。換句話說，每個代理都應該相信，根據他/她對項目的序數排序的響應集擴展，他/她的捆綁包至少與任何其他代理的捆綁包一樣好。透過循環項目分配程序可以獲得 SD-EF 的近似變體，稱為 SD-EF1（SD-EF 最多一個項目）。

沒有合理嫉妒是雙邊市場中無嫉妒的弱化，在雙邊市場中，代理人和「物品」都對另一方有偏好，例如，將學生與學校匹配的市場。如果學生 A 更喜歡分配給學生 B 的學校，同時分配給學生 B 的學校更喜歡學生 A，那麼學生 A 對學生 B 感到嫉妒是合理的。

事前無嫉妒性是將無嫉妒性弱化，用於公平隨機分配的設定。在這種設定下，每個代理商都會收到一份物品抽籤；如果沒有代理人偏好另一個代理人的彩票，即沒有代理人為另一個代理人的彩票分配更高的預期效用，則彩票分配被稱為事前無嫉妒。如果每個結果都是無嫉妒的，則分配稱為事後無嫉妒。顯然，事後無嫉妒意味著事前無嫉妒，但反之則不然。

局部無嫉妒性^[ 7 ]^[ 8 ]（也稱為：網絡無嫉妒性^[ 9 ]或社會無嫉妒性^[ 10 ]^[ 11 ]）是基於社會網絡的無嫉妒性的弱化。它假設人們只知道網路中鄰居的分配，因此他們只能羨慕鄰居。標準無嫉妒性是社會無嫉妒性的一個特例，其中網路是完全圖。

元無嫉妒性要求代理不僅在最終分配方面不會互相嫉妒，而且在協議中的目標方面也不會互相嫉妒。^[ 12 ]參見對稱公平切蛋糕。

嫉妒最小化是一個最佳化問題，其目標是最小化嫉妒的數量（可以用多種方式定義），即使在不可能實現無嫉妒的情況下也是如此。有關分配不可分割物件時所使用的無嫉妒性的近似變體，請參閱無嫉妒項目分配。

與其他公平標準的關係

比例性和無嫉妒性之間的意義

比例性（PR）和無嫉妒性（EF）是兩個獨立的屬性，但在某些情況下，其中一個可能暗示另一個。

當所有估值都是加性集合函數，並且整個蛋糕被分割時，有以下含義：

有兩個伴侶時，PR與EF相等；
如果有三個或更多伴侶，EF 就意味著 PR，但反之則不然。例如，有可能三個合夥人在主觀意見中各自獲得 1/3，但在 Alice 看來，Bob 的份額價值 2/3。

當估值僅為次加法時，EF 仍然意味著PR，但即使有兩個合作夥伴，PR 也不再意味著EF：有可能Alice 的股份在她眼中價值1/2，但Bob 的股份價值更高。相反，當估值僅為超加性時，PR 仍然意味著有兩個合夥人的EF，但即使有兩個合夥人，EF 也不再意味著PR：有可能Alice 的股份在她眼中價值1 /4，但Bob 的股份甚至更值較少的。類似地，當蛋糕沒有全部分完畢時，EF 不再意味著 PR。下表總結了其意義：

估價	2 名合夥人	3+ 個合作夥伴
添加劑	$EF\implies PR$ $PR\implies EF$	$EF\implies PR$
次加性	$EF\implies PR$	$EF\implies PR$
超加性	$PR\implies EF$	-
一般的	-	-

參見

厭惡不公平
公平分配實驗，研究無嫉妒性與其他公平標準的相對重要性。

參考

伽莫夫, 喬治;斯特恩，馬文（1958）。益智數學。維京出版社。國際標準書號 0670583359。
Foley，Duncan（1967）。「資源配置與公共部門」。耶魯經濟學論文。7 (1): 45–98。
David Schmeidler 與 Menahem Yaari (1971 年)。「公平分配」。噴印。
Barbanel，Julius B.（1996-01-01）。「超無羨的蛋糕分割與措施獨立」。數學分析與應用雜誌。197(1 ) :54–60。ISSN0022-247X。
Webb, William A. (1999-11-01)。“一種超級無嫉妒的蛋糕分割演算法”。數學分析與應用雜誌。239 ( 1 ) : 175–179。 ISSN 0022-247X。
周林（1992-06-01）。「大型交換經濟體中的嚴格公平分配」。經濟理論雜誌. 57 ( 1 ) : 158–175。 ISSN 0022-0531。
Abebe, Rediet；克萊因伯格，喬恩；帕克斯，大衛C.（2017-05-08）。「透過社會比較實現公平分配」。第 16 屆自主代理與多代理系統會議論文集。 AAMAS'17。巴西聖保羅：國際自主代理和多代理系統基金會：281–289 。
Beynier, Aurélie; Chevaleyre，Yann；古爾維斯（Gourvès），洛朗（Laurent）；哈魯圖尼揚，阿拉拉特；萊斯卡，朱利安；莫德特，尼古拉斯； Wilczynski，Anaëlle（2019-09-01）。「房屋分配問題中的局部無嫉妒性」。自主代理和多代理系統。33 ( 5 ) : 591–627。 ISSN 1573-7454。S2CID 51869987。
貝曉暉；喬有明；張勝宇（2017-07-07）。「網路化切蛋糕的公平性」。arXiv : 1707.02033 [ cs.DS ]。
Flammini, Michele;毛羅，曼努埃爾； Tonelli，Matteo（2019-04-01）。「論多單位市場中的社會無嫉妒性」。人工智慧. 269：1–26。 ISSN 0004-3702。S2CID 19205358。
布雷德里克, 羅伯特;卡茲馬爾奇克，安德烈；Niedermeier，Rolf（2020-11-23）。「尊重社群網路的無嫉妒分配」。arXiv : 2011.11596 [ cs.GT ]。
真鍋義文；岡本達明（2010）。 Hliněný，Petr； Kučera，Antonín（編輯）。「無元嫉妒的切蛋糕協議」。計算機科學的數學基礎 2010。計算機科學講稿。6281。柏林，海德堡：Springer ：501–512 。原文連結： doi : 10.1007/978-3-642-15155-2_44 .國際標準書號 978-3-642-15155-2。

[1] 伽莫夫, 喬治;斯特恩，馬文（1958）。益智數學。維京出版社。國際標準書號 0670583359。

[2] Foley，Duncan（1967）。「資源配置與公共部門」。耶魯經濟學論文。7 (1): 45–98。

[3] David Schmeidler 與 Menahem Yaari (1971 年)。「公平分配」。噴印。

[:0-4] Barbanel，Julius B.（1996-01-01）。「超無羨的蛋糕分割與措施獨立」。數學分析與應用雜誌。197(1 ) :54–60。ISSN0022-247X。

[5] Webb, William A. (1999-11-01)。“一種超級無嫉妒的蛋糕分割演算法”。數學分析與應用雜誌。239 ( 1 ) : 175–179。 ISSN 0022-247X。

[6] 周林（1992-06-01）。「大型交換經濟體中的嚴格公平分配」。經濟理論雜誌. 57 ( 1 ) : 158–175。 ISSN 0022-0531。

[7] Abebe, Rediet；克萊因伯格，喬恩；帕克斯，大衛C.（2017-05-08）。「透過社會比較實現公平分配」。第 16 屆自主代理與多代理系統會議論文集。 AAMAS'17。巴西聖保羅：國際自主代理和多代理系統基金會：281–289 。

[8] Beynier, Aurélie; Chevaleyre，Yann；古爾維斯（Gourvès），洛朗（Laurent）；哈魯圖尼揚，阿拉拉特；萊斯卡，朱利安；莫德特，尼古拉斯； Wilczynski，Anaëlle（2019-09-01）。「房屋分配問題中的局部無嫉妒性」。自主代理和多代理系統。33 ( 5 ) : 591–627。 ISSN 1573-7454。S2CID 51869987。

[9] 貝曉暉；喬有明；張勝宇（2017-07-07）。「網路化切蛋糕的公平性」。arXiv : 1707.02033 [ cs.DS ]。

[10] Flammini, Michele;毛羅，曼努埃爾； Tonelli，Matteo（2019-04-01）。「論多單位市場中的社會無嫉妒性」。人工智慧. 269：1–26。 ISSN 0004-3702。S2CID 19205358。

[11] 布雷德里克, 羅伯特;卡茲馬爾奇克，安德烈；Niedermeier，Rolf（2020-11-23）。「尊重社群網路的無嫉妒分配」。arXiv : 2011.11596 [ cs.GT ]。

[12] 真鍋義文；岡本達明（2010）。 Hliněný，Petr； Kučera，Antonín（編輯）。「無元嫉妒的切蛋糕協議」。計算機科學的數學基礎 2010。計算機科學講稿。6281。柏林，海德堡：Springer ：501–512 。原文連結： doi : 10.1007/978-3-642-15155-2_44 .國際標準書號 978-3-642-15155-2。

和

‧福利

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

YuruChurch 悠日教會

無嫉妒公平分配

一般定義

特殊情況

變體

與其他公平標準的關係

比例性和無嫉妒性之間的意義

參見

參考

沒有留言:

張貼留言