修士論文 要旨

オンライン最小採択確率最大化ナップサック問題の解析
数理情報学専攻 48216234
指導教員

善永 徹
河瀬 康志 特任准教授

的に選択してよい．アイテムをナップサックに入れた

1 はじめに後でサイズの実現値 Si が Fi に従って決定する．アイ

将来の状況が不確実な状況において後悔の少ない意思

テムサイズの実現値が決定した後，ナップサック制約を決定を行うことは，オンライン最適化としてコンピュー考慮したアイテムの採択条件と照らし合わせ，違反してタサイエンスの分野で研究されてきた．オンライン最いない場合にはアイテムが採択される．アイテムサイ

適化では，その場その場における選択を「逐次的に到着ズの期待値の合計は 1 以下であり，意思決定者はこれする入力に対して適応的に処理をするアルゴリズム」にを知っている．問題の目的は，各アイテムの採択確率のより決定し，最適な意思決定を試みる．

うち，最小のもの (最小採択確率) を最大化することでAlaei と Alaei らは，オンライン一般化割当問題に対する割当アルゴリズムを設計する手法として魔法使
い問題および一般化魔法使い問題を導入した [1, 2, 3]．
（一般化）魔法使い問題は到着するすべてのアイテムを一定確率以上で採択することを目的とし，アイテムの価値が未知の場合でも利用できる．
（一般化）魔法使い問題は，アイテムサイズがナップサック容量の 1/k以下 (k はあらかじめ定められた正整数) であるという仮定がおかれたオンラインナップサック問題であり，モデルの適用範囲が限定されている．本研究では，アイテムサイズがナップサック容量以下の任意の値を取ることができるオンラインナップサック問題において，すべてのアイテムを一定確率でナップサックに入れるようなアルゴリズムを提案する．

2 問題設定我々が導入する問題は，一般化魔法使い問題 [3] において，アイテムが任意のサイズをとり，ナップサックの残り容量が 1/k 未満の場合にはアイテムを入れることができないという制約をなくしたものである．厳密には次のように定義される．

ある．
本問題設定では，アイテムをナップサックに詰め込んだ後，事後的にナップサック制約を違反したかどうかが判明する．我々はナップサック制約を違反する原因となったアイテムを臨界アイテムと呼び，臨界アイテムが採択されたとみなす設定と不採択となったとみなす設定の 2 種類を検討した．
オンライン最小採択確率最大化ナップサック問題に対するアルゴリズムは，オンライン確率的一般化割当問
題 (OSGAP) に対する競合解消スキーム [5] として利用可能であり，その競合比は元問題に対するアルゴリズムが保証できる最小採択確率の値と一致する．OSGAPは広告割当問題 [2] やアドセル問題 [4] といった応用上重要な問題の一般化となっている．
アルゴリズムの設計には Alaei ら [3] が一般化魔法使い問題に対して提案した γ-保守的魔法使いアルゴリズ
ムを参考にした．このアルゴリズムでは，ナップサッ
ク内のアイテム総サイズと逐次計算される閾値を参照し，選択規則に従って到着したアイテムの選択の確率を決定する．γ-保守的魔法使いアルゴリズムでは，ナップサック内のアイテム総サイズが小さい事象から優先し定義 1. オンライン最小採択確率最大化ナップサックてアイテムを選択し，全体で確率 γ (γ ∈ (0, 1] はあらか

まず 1 単位の容量をもつナップサックが意思決定者にじめ定めた定数) でアイテムが採択されるようにする．

与えられる．その後，意思決定者にいくつかのアイテムが逐次的に与えられる．第 i 番目のアイテムのサイズ

3 臨界アイテム不採択設定

は累積分布関数 Fi に従う．Fi は [0, 1] 上の独立な分

まず我々は臨界アイテム不採択設定では，既存アルゴ布である．第 i 番目のアイテムが到着したときに初めリズムの γ-保守的魔法使いアルゴリズムが有効に機能て意思決定者に Fi が通知される．意思決定者はアイテしないことを示した．これはアイテム総サイズが小さ

ムが到着次第，すぐにアイテムをナップサックに入れるいナップサックを優先して採択していくと，後半にサイか選択する．一度入れないと決めたアイテムは後から

ズ 1 を取るアイテムの採択確率が小さくなることが原入れることはできない．意思決定者はアイテムを確率因である．

オンライン最小採択確率最大化ナップサック問題の解析 (善永 徹)

定理 2. 臨界アイテム不採択設定では，任意の γ (> 0)に対して，あるインスタンスが存在し，γ-積極的魔法使
いアルゴリズムの実行途中で確率 γ でアイテムを採択することができなくなる．

γ-保守的魔法使いアルゴリズムは，サイズが高確率で4 臨界アイテム採択設定
臨界アイテム採択設定では，γ-積極的魔法使いアルゴリズム，γ-保守的魔法使いアルゴリズムの両方において一定の最小採択確率が保証されることを示した．

1 であるアイテムが来た時に，確率 γ での採択はでき

定理 6. 臨界アイテム採択設定では，1/2-積極的魔法使なくなるという問題があった．そこで，そのようなアいアルゴリズムは任意のインスタンスにおいて各アイイテムを確率 γ で採択できるような余裕を残すために，テムを確率 1/2 で採択する．

ナップサック内のアイテム総サイズが大きいものを優先してナップサックを選択し，全体でちょうど γ だけの確率でアイテムを採択するようなアルゴリズムを提案し，γ-積極的魔法使いアルゴリズムと名付けた．
定理 3. 臨界アイテム不採択設定では，1/3-積極的魔法使いアルゴリズムは任意のインスタンスにおいて各アイテムを確率 1/3 で採択する．
不可能性としては，臨界アイテム不採択設定のオンライン最小採択確率最大化ナップサック問題において，任意のアルゴリズムに対し最小採択確率が 3/7 + ε 以下となるインスタンスが存在することを示した．
定理 4. 臨界アイテム不採択設定のオンライン最小採択確率最大化ナップサック問題において，任意のアルゴリズムと任意の ε > 0 に対し最小採択確率が 3/7 + ε 以下となるインスタンスが存在する．

定理 7. 臨界アイテム採択設定では，1/2-保守的魔法使
いアルゴリズムは任意のインスタンスにおいて各アイテムを確率 1/2 で採択する．
不可能性に関しては，臨界アイテム採択設定のオンライン最小採択確率最大化ナップサック問題において，任意のアルゴリズムに対し最小採択確率が 1/2 以下となるインスタンスが存在することを示した．
定理 8. 臨界アイテム採択設定のオンライン最小採択確率最大化ナップサック問題は，保証できる最小採択確率が 1/2 以下となるインスタンスが存在する．
すなわち，臨界アイテム採択設定においては，1/2-積極的魔法使いアルゴリズムと 1/2-保守的魔法使いアルゴリズムの性能はともにタイトである．

参考文献[1] S. Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. In Pro定した問題においては，次の γ-計画的魔法使いアルゴ
ceedings of IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 512–521, 2011.
リズムにより最小採択確率 3/7 を保証できる．
[2] S. Alaei, M.T. Hajiaghayi, and V. Liaghat. Onlineγ-計画的魔法使いアルゴリズム
prophet-inequality matching with applications to adallocation. In Proceedings of the 13th ACM Conferγ を任意の実数，Wi をアイテム i が到着した時点
ence on Electronic Commerce, pages 18–35, 2012.
[3] S. Alaei, M.T. Hajiaghayi, and V. Liaghat. The onにおけるナップサック内の総アイテムサイズの実line stochastic generalized assignment problem. In現値とする．アイテム i がサイズ 1 をとる確率をProceedings of International Workshop on Approxpi とするとき，次のような確率でアイテム i を選imation, Randomization, and Combinatorial Optimization, pages 11–25, 2013.
択する：[4] S. Alaei, M.T. Hajiaghayi, V. Liaghat, D. Pei, and
B. Saha. Adcell: Ad allocation in cellular networks.
0if Wi > 1,
In Proceedings of the 19th European Conference on1−piifε≤W<1,· 1−pAlgorithms, pages 311–322, 2011.
2i
Pr[Wi ] = γ (i +pi)
2[5]M.
Feldman, O. Svensson, and R. Zenklusen. On(1−p)iγ 1 −if Wi = 0.
1−pi +p2i
line contention resolution schemes. In Proceedings ofthe 27th annual ACM-SIAM Symposium on DiscreteAlgorithms, pages 1014–1033, 2016.
定理 5. アイテムサイズを {ε, 1} に限定した臨界アイ問題の入力を 1/n 以下の正数 ε および 1 の 2 値に限

テム不採択設定では，3/7-計画的魔法使いアルゴリズム
は任意のインスタンスにおいて各アイテムを確率 3/7で採択する．