Loading article…
経済学では、予算加法評価は効用関数の一種である。これは、一連の品目を与えられたときに、それを次のように評価する人に対応する。[1]
- 各項目jには固定値v jが存在します。
- 固定予算Bもあります。
- アイテムのセットの値は、B とセット内のアイテムの値の合計との間の最小値です。
予算加法評価は、オンライン広告[2] [3] [4] 組み合わせオークション[5] [ 6]資源配分[7] [8] [9] [10] [11]市場均衡[12] [ 13] [14] [15]の研究に有用である。
他の種類の評価との関係
すべての加法評価は、予算が無限である予算加法評価の特殊なケースです。すべての予算加法評価は、サブモジュラ評価です。
参考文献
- ^ Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt (2018年1月)、「予算加法評価によるナッシュ社会福祉の近似」、第29回ACM-SIAM離散アルゴリズムシンポジウム議事録、産業応用数学協会、pp. 2326–2340、doi : 10.1137/1.9781611975031.150、hdl : 11858/00-001M-0000-002D-E7D6-2、ISBN 978-1-61197-503-1、S2CID 1282865
- ^ Mehta, Aranyak (2013-10-16). 「オンラインマッチングと広告割り当て」.理論計算機科学の基礎と動向. 8 (4): 265–368. doi :10.1561/0400000057. ISSN 1551-305X.
- ^ メータ、アラニャク;サベリ、アミン。ヴァジラニ、ウメッシュ。ヴァジラニ、ビジェイ (2007-10-01)。 「AdWords と一般的なオンライン マッチング」。ACM のジャーナル。54 (5): 22-es。土井：10.1145/1284320.1284321。ISSN 0004-5411。S2CID 8481313。
- ^ ブッフビンダー、ニヴ;ジャイナ教、カマル。 Naor, Joseph (Seffi) (2007)、「広告オークション収益を最大化するためのオンライン プライマルデュアル アルゴリズム」、アルゴリズム – ESA 2007、コンピューター サイエンスの講義ノート、vol. 4698、ベルリン、ハイデルベルク：シュプリンガー ベルリン ハイデルベルク、pp. 253–264、doi :10.1007/978-3-540-75520-3_24、ISBN 978-3-540-75519-7、 2020年9月3日取得
- ^ Andelman, Nir; Mansour, Yishay (2004)。「予算制約付きオークション」。Hagerup, Torben、Katajainen, Jyrki (編)。アルゴリズム理論 - SWAT 2004。コンピュータサイエンスの講義ノート。第3111巻。ベルリン、ハイデルベルク：Springer。pp. 26–38。doi :10.1007 / 978-3-540-27810-8_4。ISBN 978-3-540-27810-8。
- ^ Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron; Umans, Chris (2010-01-17)、「VCG ベースの組み合わせオークションの近似不可能性」、2010 年 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、議事録、Society for Industrial and Applied Mathematics、pp. 518–536、doi : 10.1137/1.9781611973075.45、ISBN 978-0-89871-701-3
- ^ アザール、ヨッシ;バーンバウム、ベンジャミン。カーリン、アンナ R.マチュー、クレア。グエン、C. サッチ (2008)。 「予算配分のための近似アルゴリズムの改善」。ルカのアセトにて。ダムガルド、イワン。ゴールドバーグ、レスリー・アン。ハルドルソン、マグナス M.インゴルフスドッティル、アンナ。 Walukiewicz、Igor (編)。オートマトン、言語、プログラミング。コンピューターサイエンスの講義ノート。 Vol. 5125. ベルリン、ハイデルベルク：シュプリンガー。 186–197ページ。土井：10.1007/978-3-540-70575-8_16。ISBN 978-3-540-70575-8。
- ^ Chakrabarty, Deeparnab; Goel, Gagan (2008-10-01)。「予算配分 の近似可能性とサブモジュラー福祉最大化および GAP の改良された下限値について」。2008第 49 回 IEEE コンピュータ サイエンス基礎シンポジウム。IEEE。pp. 687–696。doi :10.1109/ focs.2008.47。ISBN 978-0-7695-3436-7。
- ^ Kalaitzis, Christos (2015-12-21). 「最大予算割り当て問題に対する近似保証の改善」。第 27 回 ACM-SIAM 離散アルゴリズムシンポジウム議事録。フィラデルフィア、ペンシルバニア州: Society for Industrial and Applied Mathematics。pp. 1048–1066。doi : 10.1137 /1.9781611974331.ch74。ISBN 978-1-61197-433-1。
- ^ Srinivasan, Aravind (2008)。「完全情報設定での予算配分」。Goel, Ashish、Jansen, Klaus、Rolim, José DP、Rubinfeld, Ronitt (編)。近似、ランダム化、および組み合わせ最適化。アルゴリズムとテクニック。コンピュータサイエンスの講義ノート。第 5171 巻。ベルリン、ハイデルベルク: Springer。pp. 247–253。doi : 10.1007 / 978-3-540-85363-3_20。ISBN 978-3-540-85363-3。
- ^ Devanur, Nikhil R.; Jain, Kamal; Sivan , Balasubramanian; Wilkens, Christopher A. (2019-01-12). 「リソース割り当て問題のための近似最適オンラインアルゴリズムと高速近似アルゴリズム」。Journal of the ACM。66 ( 1 ) : 1–41。arXiv : 1903.03944。doi :10.1145/3284177。ISSN 0004-5411。S2CID 59337566。
- ^ Feldman, Michal; Gravin, Nick; Lucier, Brendan (2016-01-01). 「組み合わせワルラス均衡」. SIAM Journal on Computing . 45 (1): 29–48. arXiv : 1304.2244 . doi :10.1137/13094339X. ISSN 0097-5397.
- ^ Roughgarden, Tim; Talgam-Cohen, Inbal (2015-06-15). 「価格にアルゴリズムが必要な理由」。第 16 回 ACM 経済計算会議議事録。EC '15。米国オレゴン州ポートランド: 計算機協会。pp. 19–36。doi : 10.1145 / 2764468.2764515。ISBN 978-1-4503-3410-5. S2CID 229372470。
- ^ Garg, Jugal; Hoefer, Martin; Bei, Xiaohui; Mehlhorn, Kurt (2016). 予算加法的効用による市場均衡の計算。ライプニッツ国際情報科学会議 (LIPIcs)。第 57 巻。pp. 8:1–8: 14。doi : 10.4230 / LIPIcs.ESA.2016.8。ISBN 9783959770156.S2CID 564953 。
- ^ Cole, Richard; Devanur, Nikhil; Gkatzelis, Vasilis; Jain, Kamal; Mai, Tung; Vazirani, Vijay V.; Yazdanbod, Sadra (2017-06-20). 「凸プログラム双対性、フィッシャー市場、およびナッシュ社会福祉」。2017 ACM経済計算会議議事録。ニューヨーク、ニューヨーク、米国: ACM。pp. 459–460。arXiv : 1609.06654。doi : 10.1145 / 3033274.3085109。ISBN 978-1-4503-4527-9.S2CID 14525165 。