二分探索よりお得なオンライン価格戦略 - 麻辣坊主

オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です． 出典は R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.1 です． この記事自体は Haifeng Xu 先生の講義スライド の第 1 回をかなり参考にしてます． ゲーム理論と機械学習の様々な興味深いトピックが網羅されていておすすめです． 問題設定 戦略の評価尺度：リグレット 自明な $\mathrm{O}(N)$ リグレット戦略 二分探索による $\mathrm{O}(\log N)$ リグレット戦略 二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略 まとめ 問題設定 あなたは A さんに $N$ 個のリンゴ を，$1$ 日

[tmatsuu]

わいわい

[itochan]

うーむ。「これなら N=10000 日間売っても高々 15 円程度しか損をしません． 」平均ではなく最大ぽい。その時の（損が最大の時の）vは？その時の改良版での損は？うーむ。

[ys0000]

こういうのがちゃんと思いつけるようにならないとダメだな。頑張ろう。

[yarumato]

“二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略。重要なポイントは，売れなかったときの稼ぎは $0$ 円だが，売れれば $p_t$ 円稼げるということです．売ることができた場合の方が傷は浅いのです．”