同時食アルゴリズム
分割可能なオブジェクトを割り当てるアルゴリズム

同時摂食アルゴリズム（SE）は、順序付けされた好みを持つエージェント間で分割可能なオブジェクトを割り当てるアルゴリズムです。[1]

「順序的選好」とは、各エージェントがアイテムを最良から最悪まで順位付けできるものの、各アイテムに数値的な値を指定できない（あるいは指定したくない）ことを意味します。SE配分は、パレート効率の弱い順序的変種であるSD効率を満たします（これは、エージェントのアイテム順位付けと一致する加法的な効用関数のベクトルの少なくとも1つに対して、配分がパレート効率的であることを意味します）。

SEは各エージェントの「食べる速度」によってパラメータ化されます。すべてのエージェントに同じ食べる速度が与えられている場合、SEの割り当てはSD羨望フリー性を満たします。これは羨望フリー性の強い順序変種です（これは、エージェントのアイテム順位と一致する加法効用関数のすべてのベクトルに対して、割り当てが羨望フリーであることを意味します）。このSEの特定の変種は、確率的シリアルルール（PS）と呼ばれます。[1]

SEは、エルヴェ・ムーランとアンナ・ボゴモルナイアによって、公平なランダム割り当て問題の解法として開発されました。この問題では、各エージェントが各アイテムを受け取る割合が確率として解釈されます。全エージェントの摂食速度の積分が1であれば、各エージェントに割り当てられる割合の合計も1となるため、割合の行列は、各エージェントが正確に1つのアイテムを受け取る割り当ての抽選に分解できます。摂食速度が等しい場合、この抽選は、エージェントのアイテム順位と一致する効用関数のすべてのベクトルについて、期待値（事前） において羨望の影響を受けません。

SEの変種はケーキカットにも適用され、割り当ては決定論的（ランダムではない）である。[2]

説明

各アイテムはパン（またはその他の食品）として表現されます。各エージェントはまず、お気に入りのアイテムのところへ行き、それを食べ始めます。複数のエージェントが同時に同じアイテムを食べることも可能です。

アイテムが完全に食べられると、それを食べたエージェントはそれぞれ、残っているお気に入りのアイテムに行き、同じ方法でそれを食べ始めます。これをすべてのアイテムが消費されるまで繰り返します。

各アイテムについて、各エージェントがそのアイテムを食べた割合が記録されます。ランダム割り当ての文脈では、これらの割合は確率とみなされます。これらの確率に基づいて、くじ引きが行われます。くじ引きの種類は問題によって異なります。

  • 各エージェントが任意の数のアイテムを受け取ることができる場合、アイテムごとに個別の抽選を行うことができます。各アイテムは、そのアイテムの一部を食べ​​たエージェントのうち、そのアイテムの確率分布に従ってランダムに選ばれた1人に与えられます。
  • 各エージェントが正確に1つのアイテムを受け取る場合、決定論的割り当ての集合上の何らかの確率分布に従って割り当てを選択する単一の抽選が存在する必要があります。これを行うには、n行n列の確率行列を、順列行列の凸結合に分解する必要があります。これはバーコフアルゴリズムによって実行できます。このアルゴリズムでは、順列行列の数が最大でn 2 -2 n +2となる組み合わせが確実に見つかります。

SEにとって重要なパラメータは、各エージェントの摂食速度です。最も単純なケースでは、すべてのエージェントが同じ権限を持つ場合、すべてのエージェントが常に同じ速度で摂食するようにするのが理にかなっています。しかし、エージェントが異なる権限を持つ場合、より権限のあるエージェントに高い摂食速度を与えることが可能です。さらに、摂食速度を時間とともに変化させることも可能です。重要なのは、各エージェントの摂食速度の積分値が、そのエージェントが受け取るべきアイテムの総数と等しいことです（割り当て設定では、各エージェントは正確に1つのアイテムを受け取る必要があるため、すべての摂食速度関数の積分値は1になるはずです）。

例

エージェントは4つ、アイテムは4つ（w、x、y、zで表記）あります。エージェントの好みは以下のとおりです。

  • アリスとボブは、x よりも w を、y よりも z を好みます。
  • キャロルとダナは、x を w よりも、z よりも y よりも好みます。

エージェントは平等な権利を持っているため、1 分あたり 1 ユニットの均等かつ均一な食べる速度で SE を適用します。

最初に、アリスとボブはwへ、キャロルとダナはxへ行きます。両ペアは同時にアイテムを食べます。30秒後、アリスとボブはそれぞれwの半分、キャロルとダナはそれぞれxの半分を獲得します。

次に、アリスとボブはy（残りのお気に入りのアイテム）へ、キャロルとダナはz（残りのお気に入りのアイテム）へ移動します。30秒後、アリスとボブはそれぞれyの半分、キャロルとダナはそれぞれzの半分を獲得します。

分数の行列は次のようになります。

アリス 1/2 0 1/2 0
ボブ 1/2 0 1/2 0
キャロル 0 1/2 0 1/2
ダナ 0 1/2 0 1/2

食べた割合に基づいて、アイテムwはアリスかボブに等確率で与えられ、アイテムyについても同様です。アイテムxはキャロルかダナに等確率で与えられ、アイテムzについても同様です。エージェントごとに正確に1つのアイテムを与える必要がある場合、確率行列は次の2つの割り当て行列に分解されます。

1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1

これらの割り当ての 1 つが 1/2 の確率でランダムに選択されます。

その他の例は、MatchU.ai Web サイトで生成できます。

プロパティ

以下の説明では、すべてのエージェントがリスク中立の選好を持っている、つまり宝くじから得られる効用が結果から得られる効用の 期待値に等しいと仮定します。

効率

摂食速度の任意のベクトルを持つSEは、SD効率（順序効率とも呼ばれる）と呼ばれる効率性を満たす。非公式には、結果として得られる確率行列において、すべてのエージェントが弱SD選好し、少なくとも1つのエージェントが厳密SD選好する行列は他に存在しないことを意味する。

ランダム割り当ての文脈では、 SD 効率は事後効率を意味します。つまり、抽選によって選択されるすべての決定論的割り当てはパレート効率的です。

分数割り当てがSD効率的であるためには、それが何らかの摂食速度関数のベクトルに対するSEの結果である必要があります。[1] : Thm.1 

公平性

等しい摂食速度（PSと呼ばれる）を持つSEは、事前確率的優位性 羨望フリー（sd-envy-free）と呼ばれる公平性を満たす。非公式には、これは各エージェントが、結果として得られる確率行列を考慮し、自身の確率行を他のエージェントの確率行よりも弱く選好することを意味する。公式には、任意の2つのエージェントiとjについて、以下の式が成り立つ。

  • エージェントi が最良のアイテムを入手する確率は、行jよりも行iの方がわずかに高い。
  • エージェントi は、行jよりも行iで 2 つの最良のアイテムのうちの 1 つを取得する確率がわずかに高くなります。
  • ...
  • 任意のk ≥ 1について、エージェントi がk個のベストアイテムのうちの 1 つを行jよりも行iで取得する確率はわずかに高くなります。

sd-envy-freeness は事前に保証されていることに注意してください。つまり、抽選が行われる前のみ公平です。このアルゴリズムは当然のことながら事後的に公平ではありません。抽選が行われた後、不運なエージェントは幸運なエージェントを羨む可能性があります。これは不可分なオブジェクトの割り当てにおいては避けられないことです。

PSは、嫉妬フリーに加えて、別の公平性も満たす。任意の部分配分が与えられた場合、任意のエージェントiと正の整数kに対して、エージェントiがk個の最上位無差別クラスから受け取る割合の合計をt ( i , k )と定義する。このtは最大でn * mのベクトルであり、nはエージェント数、mはアイテム数である。順序的平等主義配分とは、レキシミン順序においてベクトルtを最大化する配分である。PSは、順序的平等主義配分を返す唯一の規則である。[3]

戦略

SEは真実を反映するメカニズムではない。最も好むアイテムが他のどのエージェントにも欲しがられていないことを知っているエージェントは、最も好むアイテムがそのまま残ることを知りながら、2番目に好むアイテムを食べることでアルゴリズムを操作できる。PSの戦略的操作については、以下のことが知られている。

  • PSは、エージェントが下向きの辞書式関係を使用してバンドルを比較する場合に真実です。[3]
  • エージェントは、下向き辞書式関係に関する最善の応答を多項式時間で計算できます。エージェントが2人いる場合、各エージェントは期待効用に関する最善の応答を多項式時間で計算できます。エージェントの数が変化する可能性がある場合、EUに関する最善の応答を計算することはNP困難です。[4]
  • 期待効用に関する最善の対応は循環する可能性がある。しかし、純粋ナッシュ均衡は、エージェントとアイテムの数に関わらず存在する。エージェントが2人の場合、元の選好に関してナッシュ均衡となる選好プロファイルを計算する線形時間アルゴリズムが存在する。いくつかの実証的設定では、PSは操作されにくい。エージェントがリスク回避的で、他のエージェントの戦略に関する情報を持たない場合、そのエージェントの最大最小戦略は真実であることである。[4]
  • 操作行為者は、自身の効用を最大3/2倍に増加させることができる。これはランダムな事例において初めて経験的に観察され[5]、その後正式に証明された[6] 。

PS と同じ問題を解決する ランダム優先順位ルールが真実であることに注意してください。

拡張機能

SE アルゴリズムはさまざまな方法で拡張されてきました。

  • KattaとSethuraman [7]は、弱い順序選好（無差別順位付け）を許容する拡張PS（EPS）を提示した。このアルゴリズムは、パラメトリックネットワークフローのインスタンスを繰り返し解くことに基づいている。
  • Bogomolnaia [3]は、レキシミン順序に基づいて、弱い選好に対するPSルールのより単純な定義を提示した。
  • ユルマズ[8]は無関心と恩恵の両方を認めている。
  • アタナソグラウトとセトゥラマン[9]は、任意の量の無差別と部分的賦与を許容する制御消費（CC）ルールを提示している。
  • Budish、Che、Kojima、Milgrom [10]は、アイテムごとに複数のユニットを許可し、エージェントよりも多くのアイテムを持ち、各エージェントが複数のユニットを取得でき、上限割り当てと実行可能な割り当てに対する2階層制約を持つ一般化PSを提示した。
  • アシュラギ、サベリ、シャメリ[11]は、下限割り当てと上限割り当て、および分配制約（最終的な割り当てだけでなく確率分布に対する制約）を許容する別の一般化PSを提示している。
  • アジズとスタースバーグ[12]は平等主義同時予約（ESR）を提示しており、これは公平なアイテム割り当てだけでなく、無差別の可能性を伴う一般的な社会的選択問題も許容する。
  • アジズとブランドル[13]は、さらに一般的な制約を許容する警戒摂食（VE）を提示している。

事後的な近似公平性の保証

上述の通り、PSによって決定される配分は事前公平性のみを満たし、事後公平性は満たしません。さらに、各エージェントが任意の数のアイテムを取得できる場合、事後不公平性は任意に悪化する可能性があります。理論的には、あるエージェントがすべてのアイテムを取得し、他のエージェントが全く取得できないという状況が考えられます。近年、事前公平性と事後近似公平性の両方を保証するアルゴリズムがいくつか提案されています。

フリーマン、シャー、ヴァイシュ[14]は以下を示しています。

  • 再帰確率シリアル（RecPS）アルゴリズムは、1つのアイテムを除いて全て羨望フリー（EF1）である割り当てに対する確率分布を返します。分布は事前EF、割り当ては事後EF1です。このアルゴリズムのナイーブバージョンは、おそらく指数関数的な数の決定論的割り当てに対する分布を生成し、エージェントと財の数に対するサポートサイズ多項式で十分であるため、アルゴリズムは多項式時間で実行されます。このアルゴリズムは分離オラクルを使用します。
  • 事前最大積配分に基づく別のアルゴリズムは、事前グループ羨望フリー性（GEF、EFとPOの両方を意味する）と事後PROP1+EF 1 1を達成する。これは、これらすべての特性を実現する唯一の配分規則である。EF1配分に分解することはできない。
  • これらのプロパティの組み合わせは、可能な限り最善です。事前 EF (PROP でも) と事前 PO を事後 EF1 と同時に保証することは不可能です。また、事前 EF (PROP でも) を事後 EF1 および部分的 PO と同時に保証することも不可能です。
  • RecPS は、バッドに対して同様の保証 (事前 EF および事後 EF1) を達成するように変更できます。

アジズ[15]は次のように示している:

  • PS抽選アルゴリズムでは、割り当ては事前sd-EFであり、抽選はsd-EF1である決定論的割り当て間でのみ行われます。つまり、EFとEF1の保証は、順序順位と一致する任意の基数効用に対して成立します。さらに、結果は事前および事後ともにsd-POです。このアルゴリズムは、PSアルゴリズムとバーコフアルゴリズムの両方をサブルーチンとして使用します。事前割り当てはPSによって返される割り当てと同等であり、これはPSの結果がEF1割り当てに分解できることを示しています。
  • バイナリ ユーティリティでは、PS 宝くじアルゴリズムはグループ戦略プルーフ、事前 PO、事前 EF、事後 EF1 です。
  • これらのプロパティの組み合わせは最善です。事前 sd-EF、事後 EF1、事後 PO、または事前 PO と事前 sd-EF を同時に保証することは不可能です。
  • 与えられたランダム割り当てが EF1 と PO 割り当ての抽選によって実装できるかどうかを確認することはNP 困難です。

ババイオフ、エズラ、フェイジ[16]は次のように示している。

  • 事前に比例配分され、事後には PROP1 と 1/2 分数最大シェア(および 1/2 分数切り捨て比例シェア) の両方である配分を計算するための多項式時間アルゴリズム。
  • これらの特性はほぼ最適です。事前に PROP 以上を保証することは不可能であり、事後にn /(2 n -1) 以上の切り捨て比例配分シェアを保証することは不可能です。

ホーファー、シュマルホーファー、ヴァリッキオ[17]は、「両方の世界のベスト」宝くじの概念を、異なる権利を持つエージェントに拡張しています。

参照

公平なランダム割り当てに関するページでは、 PS を、ランダム優先順位ルールなど、同じ問題を解決するための他の手順と比較しています。

参考文献

  1. ^ abc Bogomolnaia, Anna ; Moulin, Hervé (2001). 「ランダム割り当て問題への新たな解決策」. Journal of Economic Theory . 100 (2): 295. doi :10.1006/jeth.2000.2710.
  2. ^ Aziz, Haris; Ye, Chun (2014). 「区分定数および区分一様評価のためのケーキカットアルゴリズム」 Liu, Tie-Yan, Qi, Qi, Ye, Yinyu (編). Web and Internet Economics . Lecture Notes in Computer Science. Vol. 8877. Cham: Springer International Publishing. pp.  1– 14. doi :10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID  18365892。
  3. ^ abc Bogomolnaia, Anna (2015-07-01). 「ランダム割り当て：シリアルルールの再定義」 . Journal of Economic Theory . 158 : 308–318 . doi :10.1016/j.jet.2015.04.008. ISSN  0022-0531.
  4. ^ ab Aziz, Haris; Gaspers, Serge; Mackenzie, Simon; Mattei, Nicholas; Narodytska, Nina; Walsh, Toby (2015-05-04). Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. Istanbul, Turkey: International Foundation for Autonomous Agents and Multiagent Systems. pp.  1451– 1459. ISBN 978-1-4503-3413-6。. 古い技術レポート: https://arxiv.org/abs/1401.6523.
  5. ^ Hosseini, Hadi; Larson, Kate; Cohen, Robin (2018-07-01). 「様々な選好とリスク態度における片側マッチングメカニズムの特性の調査」.自律エージェントとマルチエージェントシステム. 32 (4): 534– 567. arXiv : 1703.00320 . doi :10.1007/s10458-018-9387-y. ISSN  1573-7454. S2CID  14041902.
  6. ^ Wang, Zihe; Wei, Zhide; Zhang, Jie (2020-04-03). 「確率的シリアルルールの操作における限定インセンティブ」. AAAI人工知能会議論文集. 34 (2): 2276– 2283. arXiv : 2001.10640 . doi : 10.1609/aaai.v34i02.5605 . ISSN  2374-3468. S2CID  210943079.
  7. ^ Katta, Akshay-Kumar; Sethuraman, Jay (2006). 「完全選好領域におけるランダム割り当て問題の解」. Journal of Economic Theory . 131 : 231–250 . doi :10.1016/j.jet.2005.05.001.
  8. ^ Yılmaz, Özgür (2009). 「弱い選好の下でのランダム割り当て」 .ゲームと経済行動. 66 : 546–558 . doi :10.1016/j.geb.2008.04.017.
  9. ^ Athanassoglou, Stergios; Sethuraman, Jay (2011-08-01). 「部分的自己資本による住宅配分」 . International Journal of Game Theory . 40 (3): 481– 513. doi :10.1007/s00182-010-0251-9. ISSN  1432-1270. S2CID  15909570.
  10. ^ Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). 「ランダム配分メカニズムの設計：理論と応用」. American Economic Review . 103 (2): 585– 623. doi :10.1257/aer.103.2.585. ISSN  0002-8282.
  11. ^ Ashlagi, Itai; Saberi, Amin; Shameli, Ali (2020-03-01). 「分配制約下における割り当てメカニズム」.オペレーションズ・リサーチ. 68 (2): 467– 479. arXiv : 1810.04331 . doi :10.1287/opre.2019.1887. ISSN  0030-364X.
  12. ^ Aziz, Haris; Stursberg, Paul (2014-06-20). 「確率系列のランダム化社会選択への一般化」. AAAI人工知能会議論文集. 28 (1). doi : 10.1609/aaai.v28i1.8796 . ISSN  2374-3468. S2CID  16265016.
  13. ^アジズ、ハリス；ブランドル、フロリアン（2022年9月 1日）「警戒的な食事ルール：制約条件付き確率的経済設計のための一般的なアプローチ」ゲームと経済行動135 : 168–187 . arXiv : 2008.08991 . doi :10.1016/j.geb.2022.06.002. ISSN  0899-8256. S2CID  221186811.
  14. ^ Freeman, Rupert; Shah, Nisarg; Vaish, Rohit (2020-07-13). 「Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation」. Proceedings of the 21st ACM Conference on Economics and Computation . EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp.  21– 22. arXiv : 2005.14122 . doi :10.1145/3391403.3399537. ISBN 978-1-4503-7975-5. S2CID  211141200。
  15. ^ Aziz, Haris (2020-12-07). 「事前公平性と事後公平性の同時達成」. Web and Internet Economics . Lecture Notes in Computer Science. Vol. 12495. ベルリン、ハイデルベルク: Springer-Verlag. pp.  341– 355. arXiv : 2004.02554 . doi :10.1007/978-3-030-64946-3_24. ISBN 978-3-030-64945-6. S2CID  214802174。
  16. ^ Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-02-09). 「Best-of-Both-Worlds Fair-Share Allocations」. arXiv : 2102.04909 [cs.GT].
  17. ^ Hoefer, Martin; Schmalhofer, Marco; Varricchio, Giovanna (2022-09-08). 「両方​​の世界のベスト：権利を持つエージェント」. arXiv : 2209.03908 [cs.GT].
「https://en.wikipedia.org/w/index.php?title=同時摂食アルゴリズム&oldid=1323854158」より取得