平等なアイテム割り当て
公平なアイテム割り当て問題

平等主義的アイテム割り当て（最大最小アイテム割り当てとも呼ばれる）は、公平なアイテム割り当て問題であり、公平性の基準は平等主義ルールに従います。目標は、エージェントの最小値を最大化することです。つまり、すべての可能な割り当ての中で、エージェントの最小値が可能な限り大きくなる割り当てを見つけることが目標です。同じ最小値を持つ割り当てが2つ以上ある場合、目標はこれらの割り当ての中から、2番目に小さい値が可能な限り大きくなる割り当てを選択することです。これをレキシミン順序で繰り返します。そのため、平等主義的アイテム割り当ては、レキシミンアイテム割り当てと呼ばれることもあります。

各エージェントにとって各アイテムjの価値が0 または定数v jのいずれかである特殊なケースは、サンタクロース問題と呼ばれます。サンタクロースは固定の贈り物のセットを持っており、最も不幸な子供が可能な限り幸せになるように、子供たちに贈り物を分配したいと考えています。

関連する問題は次のとおりです。

正規化

平等主義のルールには2つのバリエーションがある: [1]

  • 絶対的平等主義（または絶対的レキシミン）、最大化にはエージェントの名目値を使用する。
  • 相対的平等主義（または相対的語彙目録）では、最大化には正規化された値（バンドル値をすべての項目の値で割った値）が使用されます。

エージェントの評価が既に正規化されている場合、つまりすべてのエージェントがすべてのアイテムの集合に同じ値を割り当てる場合、2つのルールは同等です。しかし、正規化されていない評価では、ルールは異なる場合があります。例えば、アイテムが4つあり、アリスがそれらを1,1,1,1と評価し、ジョージがそれらを3,3,3,3と評価した場合、絶対レキシミンルールはアリスに3つのアイテム、ジョージに1つのアイテムを割り当てます。これは、この場合の効用プロファイルが(3,3)であり、最適であるためです。一方、相対レキシミンルールは、両エージェントの合計値が1に正規化された場合の正規化された効用プロファイルが(0.5,0.5)であり、最適であるため、各エージェントに2つのアイテムを割り当てます。

正確なアルゴリズム

一般的な問題は NP 困難ですが、小さなインスタンスは制約プログラミング技術によって正確に解決できます。

ランダム化アルゴリズム

デムコとヒル[4]は、期待値において平等なアイテム割り当てを達成する ランダム化アルゴリズムを提示している。

近似アルゴリズム

以下、nはエージェントの数、mはアイテムの数です。

サンタクロース問題の特殊なケースの場合:

  • バンサルとスビリデンコ[5]は線形計画法の丸めに基づく近似アルゴリズムを提示した。 O ( log ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) {\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}
  • Feige [6]は多項式時間定数因子近似アルゴリズムが存在することを証明したが、その証明はLovászの局所補題を使用しており非構成的であった。
  • Asadpour、Feige、Saberi [7] は、配置線形計画法の整数ギャップが1/4であることを証明した。これは、ハイパーグラフマッチングを用いた1/4近似アルゴリズムを意味する。しかし、彼らはこのアルゴリズムが多項式ステップ数で収束することを証明できなかった。
  • Annamalai、Kalaitzis、Svensson [8]は多項式時間13近似アルゴリズムを提示した。
  • Davies、Rothvoss、Zhang [9]は、基本線形計画にマトロイド制約を導入することで近似係数を4に改善した。

一般的なケースでは、加法的な評価を持つエージェントの場合：

  • BezakovaとDani [10]は2つのアルゴリズムを提示した。1つ目は、最適平等価値の - 因子近似値を与える。2つ目は、1つの財まで平等な割り当てを求める。つまり、各エージェントは、最適平等割り当てにおいて最大で1つの品目を差し引いた価値を受け取る。彼らのアルゴリズムは、Lenstra、Shmoys、およびTardosによる以前のアルゴリズム[11]に基づいており、基本的には1つの家事まで平等な割り当てを求める。どちらのアルゴリズムも似たようなアイデアに基づいている。彼らは、部分的平等割り当てを求める線形計画法の基本的な実行可能解を求め、各エージェントが最大で1つの財を失うか、最大で1つの家事を得るようにそれを丸める。 ( m − n + 1 ) {\displaystyle (m-n+1)}
  • AsadpourとSaberi [12]は近似アルゴリズムを提示した。彼らのアルゴリズムは、木上の分数マッチングを丸める反復法を用いている。また、問題から少数の人々を除外することを許容する場合、より良い境界値も提供している。 O ( n ⋅ log 3 ⁡ n ) {\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}
  • Chakrabarty、Chuzoy、Khanna [13]は、任意のに対して実行時間が の近似アルゴリズムを与えた。各アイテムが最大2人のエージェントに対して非ゼロの効用を持つ特殊なケースについては、彼らは2因子近似アルゴリズムを与え、それより良い因子に近似することは困難であることを証明した。 O ( m ε ) {\displaystyle O(m^{\varepsilon })} O ( m 1 / ε ) {\displaystyle O(m^{1/\varepsilon })} ε ∈ Ω ( log ⁡ log ⁡ m log ⁡ m ) {\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}
  • ゴロビン[14]は、任意の整数 に対して、エージェントの一部が少なくとも 以上の効用を得るアルゴリズムを提示した。この結果は、問題の適切な線形計画緩和から得られるものであり、この線形計画における最良の結果である。彼はまた、2つの財クラスを持つ特殊なケースに対する近似アルゴリズムも提示した。 k {\displaystyle k} ( 1 − 1 / k ) {\displaystyle (1-1/k)} O P T / k {\displaystyle OPT/k} O ( n ) {\displaystyle O({\sqrt {n}})}
  • エージェントの数が一定の場合、Woeginger法を用いたFPTASがある。[15]

サブモジュラー効用関数を持つエージェントの場合:

  • ゴロビン[14]は近似アルゴリズムと、一般的な効用関数に対するいくつかの近似不可能性の結果を与えた。 ( m − n + 1 ) {\displaystyle (m-n+1)}
  • ゴーマンス、ハーヴェイ、岩田、ミルコニ[16]は近似アルゴリズムを提示している。 O ( m ⋅ n 1 / 4 ⋅ log ⁡ n ⋅ log 3 / 2 ⁡ m ) {\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}
  • Nguyen、Roos、Rothe [17] [18]は、より強い硬度の結果をいくつか示しています。

通常は平等な配分

標準的な平等主義のルールでは、各エージェントが各オブジェクトに数値を割り当てることが求められます。多くの場合、エージェントは順序効用のみを持ちます。順序設定への平等主義のルールの一般化には2つの方法があります。

1. エージェントがバンドル集合全体にわたって順序付けされた順位を持つと仮定する。任意の離散割り当てが与えられた場合、任意のエージェントiについて、 r ( i ) をエージェント i のバンドルの順位として定義する。つまり、 i が最良のバンドルを獲得した場合は r(i)=1、2番目に最良のバンドルを獲得した場合は r(i)=2 となる。このrはサイズn（エージェント数）のベクトルである。順序付けされた平等割り当てとは、r の最大要素を最小化する割り当てである。需要減少法は、任意の数のエージェントと任意のバンドル順序に対して、順序付けされた平等割り当てを求める。

2. エージェントがアイテム集合に対して順序付けされた順位を持つとする。離散的または分数的な割り当てが与えられた場合、任意のエージェントiと正の整数kに対して、エージェントi がk 個の最上位無差別クラスから受け取る割合の合計をt ( i , k ) と定義する。このtは最大でn * mのベクトルであり、nはエージェント数、mはアイテム数である。順序的平等主義割り当てとは、レキシミン順序においてベクトルtを最大化する割り当てである。等速摂食アルゴリズムは、順序的平等主義割り当てを返す唯一のルールである。[19]

オンライン平等配分

オンライン設定では、商品は1点ずつ届きます。到着したらすぐに割り当てる必要があります。

川瀬と澄田[20]は2つの変種を研究している。敵対的変種については、競争比率が1/nのアルゴリズムを提示し、それが最良であることを示している。一方、iid変種については、ほぼ最適なアルゴリズムを提示している。

他の公平性基準との比較

比例性

比例配分が存在する場合、相対的レキシミン配分も比例的になります。これは、比例配分において、エージェントの最小相対値は少なくとも1/ nであるため、最小相対値を最大化する場合も同様のことが成り立つためです。しかし、上記の例に示すように、絶対的レキシミン配分は比例的にならない場合があります。

嫉妬のなさ

1. すべてのエージェントが非ゼロの限界効用を持つ同一の評価を持っている場合、相対的レキシミン割り当てはPOとEFXです。

  • leximinの改良版であるleximin++は、一般的な同一の評価でEFX（POではない）を保証します。[21]

2. 加法的評価を持つ2人のエージェントの場合、相対的レキシミン割り当てはEF1である。[21] : Thm.5.5 ただし、

  • 絶対的レキシミン配分は、加法的評価を持つ2人のエージェント間でもEF1にならない可能性がある。例えば、4つの財があり、それぞれを{0,1,1,1}と{3,3,3,3}と評価する2人のエージェントがいるとする。この場合、唯一の絶対的レキシミン配分は、最初のエージェントに{1,1,1}、2番目のエージェントに{3}を与えるが、2番目のエージェントは羨望の念を抱く。[22] : 32 
  • 相対的レキシミン配分は、3人以上のエージェントの場合、EF1とはならない可能性がある。例えば、4つの財があり、3人のエージェントがそれぞれ{30,0,0,0}、{20,5,5,0}、{0,12,12,6}と評価しているとしよう。評価値は正規化されている（合計値は30）ことに注意されたい。レキシミン配分では、最初の財はエージェント1に割り当てられなければならない。次に、2番目と3番目の財はエージェント2に割り当てられ、財はエージェント3に残る。しかし、エージェント3は財を1つ取り除いた後でもエージェント2を羨望する。[23] : 22 

3. すべてのエージェントがマトロイドランク関数（つまり、2値周辺関数を持つサブモジュラー）の評価を持つ場合、絶対レキシミン割り当ての集合は最大積割り当ての集合と等価であり、そのような割り当てはすべて最大和とEF1である。[22]

4.家事（負の効用を持つ項目）の不可分な割り当ての文脈では、加法的な評価を持つ3人または4人のエージェントがいる場合、任意のレキシミン最適な割り当てはPROP1とPOである。一般的に同一の評価を持つn人のエージェントがいる場合、任意のレキシミン最適な割り当てはEFXである。[24]

マキシミンシェア

すべてのエージェントが同一の評価を持っている場合、平等主義的割り当ては、定義により、各エージェントに少なくとも最大のシェアを与えます。

しかし、エージェント間の評価が異なる場合、問題は異なります。最大シェア配分は満足度問題であり、各エージェントが同一評価閾値を超える価値を受け取ることを保証することが目的です。一方、平等主義配分は最適化問題であり、各エージェントが可能な限り高い価値を受け取ることを目的とします。場合によっては、結果として得られる配分が大きく異なる可能性があります。例えば、4つの財があり、それらを{3,0,0,0}、{3-2 ε,ε,ε ,0}、{1-2 ε ,1,1,2 ε }（εは小さな正の定数）と評価する3人のエージェントがいるとします。評価は正規化（合計値が3）されているため、絶対レキシミンと相対レキシミンは同等であることに注意してください。

  • レキシミン割り当てにより、効用プロファイル (3, 2ε, 2ε ) が生成されます。最初のアイテムはエージェント 1 に渡される必要があります。そうでない場合、最小の効用は 0 になります。次に、2 番目と 3 番目のアイテムはエージェント 2 に渡される必要があります。そうでない場合、次に小さい効用はε以下になります。そのため、エージェント 3 は最後のアイテムのみを取得します。
  • エージェントの最大シェア値は0、ε、1です。したがって、最大シェア割り当てでは、エージェント3に最初の3つの項目のうちの1つを与える必要があります。この場合の可能な効用プロファイルは、(0、2ε 、 1)または(3、ε、1+ 2ε )です。

この例は、 k > 3 の任意の k に対して、1-out-of- k MMSに拡張できます。k +1 個の財があり、3 人のエージェントがそれぞれ { k , 0, ..., 0}、{ k -( k -1) ε , ε, ..., ε , 0}、{1- kε , 1, 1, ..., k ε } と評価します。レキシミン効用プロファイルは ( k , kε, kε ) である必要がありますが、エージェント 3 の 1-out-of- k MMS は 1 です。

実世界への応用

レキシミンルールは、公立学校の未使用教室をチャータースクールに公平に割り当てるために使用されてきた。[25]

参考文献

  1. ^ シーガル・ハレヴィ、エレル;シクライ、バラーズ R. (2019-09-01)。 「ケーキカットにおける単調性と競争均衡」。経済理論。68 (2): 363–401 . arXiv : 1510.05229。土井：10.1007/s00199-018-1128-6。ISSN  1432-0479。S2CID  179618。
  2. ^ ブーヴレ、シルヴァン;ルメートル、ミシェル (2009-02-01)。 「制約ネットワークにおけるレキシミン最適解の計算」。人工知能。173 (2): 343–364。土井: 10.1016/j.artint.2008.10.010。ISSN  0004-3702。
  3. ^ ダッラーリオ、マルコ;モスカ、ラファエレ (2007)。 「ハードキャンディーを公平に配分する方法」。数学社会科学。54 (3): 218. CiteSeerX 10.1.1.330.2617。土井：10.1016/j.mathsocsci.2007.04.008。 
  4. ^ デムコ, スティーブン; ヒル, セオドア P. (1988年10月1日). 「分割不可能な物体の公平な分配」 .数学社会科学. 16 (2): 145– 158. doi :10.1016/0165-4896(88)90047-9. ISSN  0165-4896.
  5. ^ バンサル, ニヒル; スヴィリデンコ, マキシム (2006). 「サンタクロース問題」.第38回ACMコンピューティング理論シンポジウム議事録 - STOC '06 . p. 31. doi :10.1145/1132516.1132522. ISBN 1595931341。
  6. ^ Feige, Uriel (2008-01-20). 「公平性を最大化する割り当てについて」.第19回ACM-SIAM離散アルゴリズムシンポジウム議事録. SODA '08. カリフォルニア州サンフランシスコ: Society for Industrial and Applied Mathematics: 287–293 .
  7. ^ Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008). 「サンタクロースとハイパーグラフマッチングの出会い」. Goel, Ashish; Jansen, Klaus; Rolim, José DP; Rubinfeld, Ronitt (編).近似、ランダム化、および組合せ最適化. アルゴリズムとテクニック. コンピュータサイエンス講義ノート. 第5171巻. ベルリン、ハイデルベルク: Springer. pp.  10– 20. doi :10.1007/978-3-540-85363-3_2. ISBN 978-3-540-85363-3。
  8. ^ Annamalai, Chidambaram; Kalaitzis, Christos; Svensson, Ola (2017-05-26). 「制限付きMax-Min Fair Allocationのための組み合わせアルゴリズム」. ACM Transactions on Algorithms . 13 (3): 37:1–37:28. arXiv : 1409.0607 . doi :10.1145/3070694. ISSN  1549-6325. S2CID  14749011.
  9. ^ Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (2018-07-18).サンタクロース、ハイパーグラフ、マトロイドの物語. 第14回ACM-SIAM離散アルゴリズムシンポジウム論文集. Society for Industrial and Applied Mathematics, 2020. pp.  2748– 2757. doi :10.1137/1.9781611975994.
  10. ^ Bezáková, Ivona; Dani, Varsha (2005). 「分割不可能な財の配分」ACM SIGecom Exchanges . 5 (3): 11. CiteSeerX 10.1.1.436.18 . doi :10.1145/1120680.1120683. S2CID  1176760. 
  11. ^ Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). 「無関係な並列マシンのスケジューリングのための近似アルゴリズム」 .数理計画. 46 (1): 259– 271. doi :10.1007/BF01585745. ISSN  1436-4646. S2CID  52867171.
  12. ^ Asadpour, Arash; Saberi, Amin (2010-01-01). 「分割不可能な財の最大最小公平配分のための近似アルゴリズム」 . SIAM Journal on Computing . 39 (7): 2970– 2989. doi :10.1137/080723491. ISSN  0097-5397.
  13. ^ Chakrabarty, D.; Chuzhoy, J.; Khanna, S. (2009-10-01). 「公平性の最大化に向けた財の配分について」. 2009 第50回IEEEコンピュータサイエンス基礎シンポジウム. pp.  107– 116. arXiv : 0901.0205 . doi :10.1109/FOCS.2009.51. ISBN 978-1-4244-5116-6. S2CID  165160。
  14. ^ ab ゴロビン、ダニエル (2005). 「分割不可能な財の最大最小公平配分」 CMU . 2016年8月27日閲覧。
  15. ^ Woeginger, Gerhard J. (2000-02-01). 「動的計画法の定式化は、どのような場合に完全多項式時間近似スキーム（FPTAS）の存在を保証するのか？」 INFORMS Journal on Computing . 12 (1): 57– 74. doi :10.1287/ijoc.12.1.57.1​​1901. ISSN  1091-9856.
  16. ^ Goemans, Michel X.; Harvey, Nicholas JA; Iwata, Satoru; Mirrokni, Vahab (2009-01-04) 「あらゆる場所での劣モジュラ関数の近似」、2009 Annual ACM-SIAM Symposium on Discrete Algorithms の議事録、産業応用数学協会、pp.  535– 544、doi :10.1137/1.9781611973068.59、hdl : 1721.1/60671、ISBN 978-0-89871-680-1, S2CID  14308006 , 2020年11月22日取得
  17. ^ Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). 「マルチエージェント資源配分における社会福祉最適化のための近似可能性と非近似可能性の結果の概観」Annals of Mathematics and Artificial Intelligence . 68 ( 1– 3): 65– 90. CiteSeerX 10.1.1.671.3497 . doi :10.1007/s10472-012-9328-4. S2CID  6864410. 
  18. ^ Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). 「マルチエージェント資源配分における社会福祉最適化の計算複雑性と近似可能性」.自律エージェントとマルチエージェントシステム. 28 (2): 256. doi :10.1007/s10458-013-9224-2. S2CID  442666.
  19. ^ Bogomolnaia, Anna (2015年7月1日). 「ランダム割り当て：シリアルルールの再定義」 . Journal of Economic Theory . 158 : 308–318 . doi :10.1016/j.jet.2015.04.008. ISSN  0022-0531.
  20. ^ 川瀬 康; 隅田 ハンナ (2022). 「オンライン・マックス・ミニ・フェア・アロケーション」 . Kanellopoulos, Panagiotis, Kyropoulou, Maria, Voudouris, Alexandros (編).アルゴリズムゲーム理論. コンピュータサイエンス講義ノート. 第13584巻. シュプリンガー・インターナショナル・パブリッシング. pp.  526– 543. doi :10.1007/978-3-031-15714-1_30. ISBN 978-3-031-15714-1。
  21. ^ ab プラウト, ベンジャミン; ラフガーデン, ティム (2020-01-01). 「一般評価によるほぼ羨望フリー」. SIAM Journal on Discrete Mathematics . 34 (2): 1039– 1068. arXiv : 1707.04769 . doi :10.1137/19M124397X. ISSN  0895-4801. S2CID  216283014.
  22. ^ ab Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). 「評価が合わない場合の公正かつ効率的な配分を見つける」.アルゴリズムゲーム理論. コンピュータサイエンス講義ノート. 第12283巻. pp.  32– 46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1. S2CID  208328700。
  23. ^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-24). 「最大ナッシュ福祉の不当な公平性」. ACM Transactions on Economics and Computation . 7 (3): 12:1–12:32. doi : 10.1145/3355902 . ISSN  2167-8375. S2CID  202729326.
  24. ^ Chen, Xingyu; Liu, Zijie (2020-05-11). 「分割不可能な家事の割り当てにおけるLeximinの公平性」arXiv : 2005.04864 [cs.GT].
  25. ^ 黒川, デイビッド; プロカッチャ, アリエル・D.; シャー, ニサルグ (2015-06-15). 「現実世界におけるレキシミン配分」.第16回ACM経済・計算会議議事録. EC '15. オレゴン州ポートランド: 計算機協会. pp.  345– 362. doi :10.1145/2764468.2764490. ISBN 978-1-4503-3410-5. S2CID  1060279。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Egalitarian_item_allocation&oldid=1317961321"