福祉最大化 問題は、経済学 とコンピュータ科学 で研究されている最適化問題です。その目的は、異なる 効用関数 を持つエージェント間で一連のアイテムを分割し、エージェントの効用の合計として定義される福祉が可能な限り高くなるようにすることです。言い換えれば、目的は功利主義のルール を満たすアイテムの割り当てを見つけることです。[ 1 ]
組み合わせオークション の文脈における同等の問題は、勝者決定問題 と呼ばれます。この場合、各エージェントはアイテムの集合に対して入札リストを提出し、落札した入札の合計が最大となるような入札を決定することが目標となります。
定義 m 個のアイテムからなる集合Mと、 n個 のエージェントからなる集合N が存在する。N内の各エージェントiは 効用関数 を持つ。 u 私 : 2 M → R \displaystyle u_{i}:2^{M}\to \mathbb {R} } 単調集合関数 であると想定されます。つまり、Z 1 ⊇ Z 2 {\displaystyle Z_{1}\supseteq Z_{2}} u 私 （ Z 1 ） ≥ u 私 （ Z 2 ） {\displaystyle u_{i}(Z_{1})\geq u_{i}(Z_{2})} u 私 （ ∅ ） = 0 {\displaystyle u_{i}(\emptyset )=0}
割り当てと は、アイテムをn 個の互いに素な部分集合に順序付けして分割したもので、エージェントごとに 1 つの部分集合があり、次のように表されます。X = （ X 1 、 … 、 X n ） {\displaystyle \mathbf {X} =(X_{1},\ldots ,X_{n})} M = X 1 ⊔ ⋯ ⊔ X n {\displaystyle M=X_{1}\sqcup \cdots \sqcup X_{n}} 資源配分の福祉 は、各主体の効用の合計である。W （ X ） := ∑ 私 ∈ N u 私 （ X 私 ） {\displaystyle W(\mathbf {X} ):=\sum _{i\in N}u_{i}(X_{i})}
福祉最大化問題とは、 W ( X )を最大化する配分Xを見つけることである。
福祉最大化問題には、許容される効用関数の種類、アルゴリズムが効用関数にアクセスする方法、および許容される配分に追加の制約があるかどうかによって、多くのバリエーションが存在する。
添加剤 加算エージェントは、加算集合関数 である効用関数を持ちます。すなわち、すべての加算エージェントi とアイテムj に対して、次の値があります。v 私 、 j {\displaystyle v_{i,j}} u 私 （ Z ） = ∑ j ∈ X 私 v 私 、 j {\displaystyle u_{i}(Z)=\sum _{j\in X_{i}}v_{i,j}} Zごとに。すべてのエージェントが加法的である場合、福祉最大化は単純な 多項式時間 アルゴリズムで実行できます。各アイテムj を、次の条件を満たすエージェントに与えます。v 私 、 j {\displaystyle v_{i,j}}
公平性の制約 公平な 羨望のない配分 （EF1）、 1項目まで比例配分（PROP1）、または1項目まで 公平な 配分（EQ1）など、すべての配分の中で福祉を最大化したい場合がある。この問題は、 n が可変の場合、強いNP困難である。任意の固定n ≥ 2の場合、 この問題は弱NP困難であり、[ 2 ] [ 3 ] 動的計画法 に基づく擬似多項式時間 アルゴリズムが存在する。[ 2 ] n = 2 の場合、この問題には完全な多項式時間近似スキームが 存在する。[ 4 ]
エージェントの種類が少ない場合、アイテムの種類が少ない場合、または値のレベルが小さい場合は、この問題を多項式時間で解決するアルゴリズムがあります。[ 5 ] バイナリ（すべてのアイテムの値が0または1のいずれか）である場合、および 一般化バイナリ と呼ばれるより一般的なクラスの効用の場合にも、この問題を多項式時間で解決できます。[ 6 ]
グロス代替剤 総代替効用は 加法効用よりも一般的です。総代替エージェントによる厚生最大化は多項式時間で実行できます。これは、総代替エージェントの場合、常にワルラス均衡が 存在し、効用の合計を最大化するためです。[ 8 ]
サブモジュラエージェント 劣モジュラーエージェントは、劣モジュラー集合関数 である効用関数を持つ。これは、エージェントの効用が限界的に減少すること を意味する。劣モジュラー効用は、総代替効用よりも一般的である。
貪欲アルゴリズム 最大の福祉は、以下の多項式時間貪欲アルゴリズム によって近似的に求めることができる。
X 1 = X 2 = ... = X n = 空として初期化します。任意の順序で、 各項目gについて： 各エージェントi について、g に対する限界効用 u i X i g ) - u i X i 限界効用が最も大きいエージェントにアイテムgを与える。 リーマン、リーマン、ニサン[ 9 ] [ 12 ] g をエージェントiに割り当てると仮定する。これは、その時点での i に対するg の限界効用であるv の量だけ福祉に貢献する。最適解では、gは 別のエージェントkに与えられるべきであると仮定する。g を iからk に移動した場合、福祉がどのように変化するかを考えてみよう。
k の効用は、 g の限界効用によって増加するが、貪欲選択では最大でvだけ増加する。 残りの i の束の限界効用は、最大でv だけ増加します。これは劣モジュラ性から導かれます。つまり、残りの束にg を追加したときの限界効用は、アルゴリズムが g を処理したときの限界効用よりも高くなることはありません。したがって、 v がアルゴリズムの福祉に寄与する度合いごとに、最適福祉への潜在的な寄与は最大で2v になります。したがって、最適福祉はアルゴリズムの福祉の最大 2 倍になります。この係数 2 は、貪欲アルゴリズムにとって厳しい値です。例えば、2 つのアイテム x、y があり、その評価が次のようになっているとします。
最適な配分は、アリス：{y}、ジョージ：{x}で、福祉は2です。しかし、貪欲アルゴリズムが最初にxを割り当てる場合、xはアリスに割り当てられる可能性があります。そうなると、yがどのように割り当てられるかに関わらず、福祉は1にしかなりません。
値オラクルを用いたアルゴリズム 価値オラクル
ドブジンスキーとシャピラ[ 13 ] n / （ 2 n − 1 ） {\displaystyle n/(2n-1)} Vondrak [ 1 ] : [ 14 ] は、高い確率で (1-1/e) 近似を見つけるランダム化多項式時間アルゴリズムを発表しています。彼らのアルゴリズムは、連続貪欲アルゴリズム、つまり、分数 バンドル (各項目jの割合 p j を含むバンドル) を貪欲な方向に拡張するアルゴリズム(勾配降下法 と同様) を使用しています。彼らのアルゴリズムは、分数バンドルの値を計算する必要があります。これは、各項目j が確率p j m 回の 呼び出しが必要になる場合がありますが、ランダムサンプリング によって高い確率で近似 的に計算できます。これにより、高い確率で (1-1/e) 近似を達成するランダム化アルゴリズム が実現します。分数バンドルを効率的に評価できる場合（たとえば、効用関数が集合被覆関数である場合）、アルゴリズムを決定論的にすることができます。[ 14 ] ： Sec.5 [ 15 ] （ 1 − 1 / e − ϵ ） {\displaystyle (1-1/e-\epsilon )} ϵ > 0 {\displaystyle \epsilon >0} （ n 種類の 異なる劣モジュラ関数を用いた）福祉最大化問題は、マトロイド制約の下で 単一の 劣モジュラ集合関数を最大化する問題に帰着させることができます。[ 9 ] [ 1 ] [ 14 ] m 個のアイテムとn 個の エージェントを持つインスタンスが与えられた場合、 m * n 個の (エージェント、アイテム) ペアを持つインスタンスを構築します。ここで、各ペアはアイテムをエージェントに割り当てることを表します。各ペアのセットに、対応する割り当ての総福祉を割り当てる単一の関数を構築します。すべての効用が劣モジュラである場合、この福祉関数も劣モジュラであることが示せます。この関数は、各アイテムが最大で 1 つのエージェントに割り当てられることを保証する分割マトロイド制約の下で最大化する必要があります。
需要オラクルを用いたアルゴリズム エージェントの効用にアクセスするもう1つの方法は、需要オラクル
DobzinskiとSchapira [ 13 ] Feige とVondrak [ 16 ] （これは上記の困難性の結果とは矛盾しない。困難性の結果は値オラクルのみを使用するため。困難性の例では、需要オラクル自体が指数関数的に多くのクエリを必要とする） 。
添加剤 エージェントの効用が劣加法集合関数 （劣モジュラ関数よりも一般的）である場合、1 m 1 / 2 − ϵ {\displaystyle {\frac {1}{m^{1/2-\epsilon }}}} [ 11 ]
Feige [ 17 ] 分数劣加法 評価の特殊なケースに対しては (1-1/e) 近似を与えます。
超添加剤 エージェントの効用が超加法集合関数 （超モジュラーよりも一般的）である場合、（ ログ m ） 1 + ϵ m {\displaystyle {\frac {(\log m)^{1+\epsilon }}{m}}} [ 11 ]
専心的なエージェント 単一目的のエージェントは、 特定のアイテムのセットのみを欲しがります。すべての単一目的のエージェントi に対して、要求されるセットD i と値V i > 0 が存在し、u 私 （ Z ） = { V 私 Z ⊇ D 私 0 さもないと {\displaystyle u_{i}(Z)={\begin{cases}V_{i}&Z\supseteq D_{i}\\0&{\text{otherwise}}\end{cases}}} 場合に限る。
単一思考のエージェントによる福祉最大化は、 たとえV 私 = 1 {\displaystyle V_{i}=1} i について。この場合、問題は集合パッキング と同等であり、NP困難であることが知られています。さらに、定数係数の範囲内で近似することはできません（劣モジュラエージェントの場合とは対照的です）。[ 18 ] O （ m ） {\displaystyle O({\sqrt {m}})} 19 ]
総代理店 エージェントが任意の単調効用関数（補完アイテム を含む）を持つことができる場合、福祉最大化は係数の範囲内で近似するのが難しい。O （ n 1 / 2 − ϵ ） {\displaystyle O(n^{1/2-\epsilon })} ϵ > 0 {\displaystyle \epsilon >0} [ 20 ] 状態空間探索 に基づくアルゴリズムは、実際には非常にうまく機能します。[ 21 ]
参考文献 1 2 3 Vondrak, Jan (2008-05-17). 「価値オラクルモデルにおける劣モジュラ福祉問題の最適近似」 .第40回ACM理論計算シンポジウム （STOC '08）論文集. ニューヨーク州ニューヨーク、米国：Association for Computing Machinery. pp. 67–74 . doi : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 . 1 2 Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (2022-10-13). "Computing welfare-Maximizing fair allocations of indivisible goods" . European Journal of Operational Research . 307 (2): 773–784 . arXiv : 2012.03979 . doi : 10.1016/j.ejor.2022.10.013 . ISSN 0377-2217 . S2CID 235266307 . ↑ Sun, Ankang; Chen, Bo; Doan, Xuan Vinh (2022-12-02). "分割不可能なアイテムの割り当てにおける公平性と福祉の最大化" . Autonomous Agents and Multi-Agent Systems . 37 (1): 8. doi : 10.1007/s10458-022-09587-1 . ISSN 1573-7454 . S2CID 254152607 . ↑ ブー、シャオリン。リー・ジハオ。リュー・シェンシン。ソン・ジアシン。タオ、彪帥（2022-05-27）。 「不可分財の公正な配分における社会福祉の最大化の複雑さについて」。 arXiv : 2205.14296 [ cs.GT ]。 ↑ Nguyen, Trung Thanh; Rothe, Jörg (2023-01-01). "少数のエージェントタイプ、少数のアイテムタイプ、または小さな値レベルでの公平かつ効率的な割り当て" . 人工知能 . 314 103820. doi : 10.1016/j.artint.2022.103820 . ISSN 0004-3702 . S2CID 253430435 . ↑ カマチョ、フランクリン。フォンセカ・デルガド、リゴベルト。ピノ・ペレス、ラモン。タピア、グイド (2022-11-07)。 「一般化された二値効用関数と公平な割り当て」 。 数学社会科学 。 121 : 50–60 . 土井 : 10.1016/j.mathsocsci.2022.10.003 。 ISSN 0165-4896 。 S2CID 253411165 。 ↑ Dror, Amitay; Feldman, Michal; Segal-Halevi, Erel (2022-04-24). "On Fair Division under Heterogeneous Matroid Constraints". arXiv : 2010.07280 [ cs.GT ]. ↑ Kelso, AS; Crawford, VP (1982). "Job Matching, Coalition Formation, and Gross Substitutes". Econometrica . 50 (6): 1483. doi : 10.2307/1913392 . JSTOR 1913392 . 1 2 3 Lehmann, Benny; Lehmann, Daniel; Nisan, Noam (2001-10-14). "限界効用が減少する組み合わせオークション" . 第3回ACM電子商取引会議議事録 . EC '01. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 18–28 . arXiv : cs/0202015 . doi : 10.1145/501158.501161 . ISBN 978-1-58113-387-5 . S2CID 2241237 . ↑ Khot, Subhash; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak (2008-09-01). "劣モジュラ効用関数を持つ組み合わせオークションの近似不可能性の結果" . Algorithmica . 52 (1): 3– 18. doi : 10.1007/s00453-007-9105-7 . ISSN 1432-0541 . S2CID 7600128 . 1 2 3 Mirrokni, Vahab; Schapira, Michael; Vondrak, Jan (2008-07-08). "組み合わせオークションにおける福祉最大化のための厳密な情報理論的下限" . 第9回ACM電子商取引会議議事録 . EC '08. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 70–77 . doi : 10.1145/1386790.1386805 . ISBN 978-1-60558-169-9 . S2CID 556774 . ↑ Fisher, ML; Nemhauser, GL; Wolsey, LA (1978)、 「劣モジュラ集合関数を最大化するための近似分析—II」 、Balinski, ML; Hoffman, AJ (編)、 Polyhedral Combinatorics: Dedicated to the memory of DR Fulkerson 、ベルリン、ハイデルベルク：Springer、pp. 73–87 、 doi ： 10.1007/bfb0121195 、 ISBN 978-3-642-00790-3 2023年2月26日 取得1 2 Dobzinski, Shahar; Schapira, Michael (2006-01-22). 「劣モジュラ入札者による組み合わせオークションのための改良された近似アルゴリズム」 . 第17回ACM-SIAM離散アルゴリズムシンポジウム（SODA '06）議事録 . 米国：応用数理学会. pp. 1064–1073 . doi : 10.1145/1109557.1109675 . ISBN 978-0-89871-605-4 . S2CID 13108913 . 1 2 3 カリネスク、グルイア;チェクリ、チャンドラ。パル、マーティン。フォンドラーク、ヤン (2011-01-01)。 「マトロイド制約を受ける単調サブモジュラー関数の最大化」 。 SIAM ジャーナル オン コンピューティング 。 40 (6): 1740 ～ 1766 年。 土井 : 10.1137/080733991 。 ISSN 0097-5397 。 ↑ Buchbinder, Niv; Feldman, Moran (2024). Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint . 65th IEEE Symposium on Foundations of Computer Science. IEEE. pp. 700–712 . ↑ Feige, Uriel; Vondrák, Jan (2010-12-09). "需要クエリを伴う劣モジュラ福祉問題" . Theory of Computing . 6 : 247– 290. doi : 10.4086/toc.2010.v006a011 . ↑ ファイゲ、ウリエル (2006年5月21日) 「効用関数が劣加法性の場合の福祉最大化について」 。 第 38回ACM理論計算機科学シンポジウム議事録 。STOC '06。米国ニューヨーク州ニューヨーク：Association for Computing Machinery。pp. 41–50。doi ： 10.1145 / 1132516.1132523。ISBN 978-1-59593-134-4 . S2CID 11504912 . ↑ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006). "On the complexity of approximating k -set packing". Computational Complexity . 15 (1): 20– 39. CiteSeerX 10.1.1.352.5754 . doi : 10.1007/s00037-006-0205-6 . MR 2226068. S2CID 1858087 . 21ページを参照：「最大クリーク（したがって最大独立集合および最大集合パッキングも）は、O （ n 1 − ϵ ） {\displaystyle O(n^{1-\epsilon })} ↑ ↑ Lehmann, Daniel; Oćallaghan, Liadan Ita; Shoham, Yoav (2002-09-01). "近似的に効率的な組み合わせオークションにおける真実の開示" . Journal of the ACM . 49 (5): 577– 602. doi : 10.1145/585265.585266 . ISSN 0004-5411 . S2CID 52829303 . ↑ Sandholm, Tuomas; Suri, Subhash (2000-07-30). 「組み合わせオークションにおける最適勝者決定のための改良アルゴリズムとその一般化」 . 第17回人工知能全国会議および第12回人工知能革新的応用会議議事録 . AAAI Press: 90–97 . ISBN 978-0-262-51112-4 。
