最良の物件に入居できる可能性を最大にしたければ、部屋探しに充てる時間の３７％（１ヶ月かけるつもりなら最初の１１日間）までは結論を出さずにただ物件を見て回る。・・・３７％以降は、それまでに見たどの物件よりも良い部屋に出会ったらすぐさま保証金を払って契約するのだ。これは「見る」と「跳ぶ」を直感的に満足のいく形で折り合わせた答えであるばかりでなく、最適であることが証明可能な解となる。
「最適停止」問題・・・交際相手を選ぶときだ。
カール・セーガン「科学は一つの知識体系である以上に、考え方そのものである」
ターキー・ドロップ（感謝祭の別れ）・・・高校時代からつきあっていたカップルが別々の大学に入り、最初の年の感謝祭に帰省すると、四日後に大学へ戻るときには別れているというのだ。・・・自分たちはどのくらいよい関係なのかという、もっと奇妙でもっと哲学的な問いとも闘っていた。
最適停止問題として最も有名な秘書問題・・・数学者なら、応募者どうしの相対的な順位を表す序数はわかっても、何らかの一般的な尺度による量的評価を表す基数まではわからないものだ、という言い方をするかもしれない。
最適解は見てから跳べ（Look then leap, Look before you leap（石橋を叩いて渡る）のアナグラム）ルールというものなのだ。
最適戦略に従うと、最良の応募者を採用できる確率が最終的に３７％となる。この戦略自体と成功の確率がぴったり同じ数字になるというのは、この問題の示す興味深い数学的対称性の一つである。
応募者が１００万人いてもやはり成功率は３７％なのだ。つまり、応募者が多ければ多いほど、最適アルゴリズムを知っていることの価値が高くなる。
断られる確率が半々の場合、３７％ルールを導き出したのと同様の数理解析によれば、探索をちょうど四分の一まで終えたらアタックを開始する。断られたら次に現れる「今までで最良」の相手にアタックを続け、OKがもらえるのを待つ。
すぐさまアタックすれば確実に受け入れてもらえるが、あとからアタックした場合には二分の一の確率で拒否されるとしよう。この場合、数学的には、候補者の６１％に会うまでは様子見を続け、残りが３９％を切ってから「今までで最良」の人がいたらそこで決断を下すべきだ。
完全情報のゲームからは意外でいくらか不思議な結果が得られる。恋愛と比べれば金鉱を探し当てるほうがはるかに成功の見込みが高いのだ。つかみどころのない情動反応（すなわち恋愛）を追い求めている人には、経験と比較基準が必要かもしれない。それよりも、収入のパーセント順位と言った客観的な基準で相手を判断している人のほうが、利用できる情報がはるかに多い。
住宅の売却・・・オファーされる価格の範囲がはっきりわかっていて、その範囲内ではどのオファーも等しい確率で生じるというケースだ。・・・この問題で大事なのは、閾値が探索のコストのみで決まるということだ。次によいオファーが来る確率（および探索のコスト）はまったく変化しないので、運や不運は関係がなく、探索の続行に伴って停止価格を下げるべき理由はない。探索をはじめる前に基準を定めたら、後はひたすらそれに従うだけだ。
最適化の専門家であるウィスコンシン・マディソン大学のローラ・アルバート・マクレイ・・・多くの売り手にとって、好条件のオファーを一つか二つ断るというのは気が狂いそうな話だ。・・・本当にとてもきつかったでしょうねー数学が味方をしてくれるということを知らなかったら。
ケプラーの配偶者探しでは見送ったチャンスを呼び戻すことができた点が重要だった。しかし住宅の売却や職探しでは、一度断ったオファーを再検討することが可能だとしても、そしてそのオファーがまだ確実に有効だとしても、決して戻るべきではない。
私が思うに、大学の運営上の三大問題は、学生にとってのセックス、同窓生にとっての運動部、教職員にとっての駐車です。カリフォルニア大学学長クラーク・カー
UCLAのドナルド・シャウプ・・・需要に応じて料金の変更が可能なデジタル式のパーキングメーターを設置し（これはすでにサンフランシスコの中心部で採用されている）、目標とする使用率を念頭に置いて料金を設定する。
私たちはシャウプに、車の多いロサンゼルスでUCLAへの通勤を自身の研究で最適化できているのかと尋ねた。世界随一の駐車問題専門家ともなれば、ひょっとして秘密兵器のようなものをおもちでは？やはりもっていた。「自転車で通勤しています」。
泥棒問題・・・泥棒が繰り返し盗みを働く機会を与えられる。盗みに成功するたびに稼ぎが手に入り、逃げ切れる可能性は常にある。しかし現場を押さえられたら逮捕され、蓄えた財産をすべて失ってしまう。稼ぎの期待値を最大にするには、どんなアルゴリズムに従えばよいだろう。
逃げ切れる確率を捕まる確率で割った数にほぼ等しい回数に達したら、足を洗うべきである。腕利きの泥棒がいつも９０％の確率で逃げおおせるとすれば、90/10=9回やったところでやめるのだ。
われわれがー進化や教育や直感によってー実際に最良の戦略に従っているのかということである。一見したところ、答えはノーである。・・・もっとよい選択肢に出会わぬまま、早々と探索をやめてしまう傾向があるらしい。
ほとんどの被験者は見てから跳べルールに合致した振る舞いを見せたが、全体の五分の四で飛ぶのが早すぎた。
ラパポートは、実生活で最適停止問題の答えを出す際にはこれを念頭に置いていると話してくれた・・・「私はもともとひどくせっかちで、最初に見つけたアパートに決めてしまいたくなるのですが、なんとか気持ちを抑えようと努めるのです！」。
応募者一人の面接にかかるコストが最良の秘書を見つける価値の１％に相当すると考えられる場合、最適戦略は二人の実験で被験者が実際に見るから跳ぶに切り替えたタイミングと完璧に合致することを明らかにした。
不思議なのは、シールとラパポートの実験では探索のコストが設定されていなかったにもかかわらず、被験者があたかもコストが存在するかのように振る舞ったのはなぜかということだ。それは、人には時間のコストというものが常に存在するからだ。これは実験の設計によって生じるのではなく、人の生活に伴うものである。
探索（explore）と活用（exploit）・・・探索とは情報を集めることであり、活用とは既知のよい結果を得るために手元の情報を使うことだ。
多腕バンディット問題・・・賞金の総額を最大にすること・・・いくつかのスロットマシンのアームを引き（探索）、その中で最も良さそうなマシンを選ぶ（活用）必要がある
ピーター・ホイットル 「あらゆる人間の行動にはっきりと現れる葛藤を本質的な形で体現する」
お気に入りの行動と新たな行動を秤にかける場合、それらを実行する時間がどのくらい残っているかという点が何よりも重要となる。
活用の価値は時間とともに上がる一方・・・得た知識を後で活用する時間がありそうな場合には探索し、活用すべき状況になったら活用するのがよい。残り時間がどのくらいあるかによって戦略が決まる。
（映画の）製作会社にしてみれば、シリーズものには固定ファンが約束されている。・・・このような安全策だらけの状況は、・・・短期主義の姿勢の表れである。シリーズものは完全な新作よりもとりあえずヒットする可能性が高い。しかしこんなやり方ばかりしていては、将来の人気シリーズが生まれなくなってしまう。・・・ほぼ完全に活用だけを狙う段階に入ったことによって、映画産業が時代の終焉に近づいているということをほのめかしているようにも感じられるのだ。
コストの増大と収入の下落のはざまで、大手制作会社はヒットすると思われる映画をもっとつくろうとしてきた。それはたいてい、続編、前編、あるいは知名度の高いキャラクターが登場する作品となる。要するに、カジノから追い出される前に、分かっている中で最良のマシンのアームを引いているのだ。
多腕バンディット問題に対処する方法をはっきりと教えてくれる最適アルゴリズムを見つけるのは信じがたいくらい難しいということがわかっている。実際、ピーター・ホイットルによれば、第二次世界大戦中にこの問題の解決を目指す取り組みが「連合軍の分析担当官の体力と気力をひどく奪ったので・・・究極の知的妨害行為の手段として、この問題をドイツ国内に投下したらどうかという声まで上がっていた」らしい。
ロビンズ・・・勝てばキープ、負ければスイッチアルゴリズム・・・最適化を行うべき期間がいつ終わるのかがまったく考慮されないことだ。
ランド研究所の数学者リチャード・ベルマンは、選択肢と機会が全部でいくつあるかがあらかじめ正確にわかっている場合の厳密解を突き止めた。
カジノに長く滞在して選択肢がたくさんある場合には、めまいのするようなーあるいは実行不可能なー量の作業が必要となるかもしれない。・・・プレイする機会が何回あるかは必ずしも正確にわかるわけではない。これらの理由から、多腕バンディット問題は実質的に未解決のままとなっている。ホイットルの言葉を借りれば、すぐさま古典となり、難攻不落の代名詞となったのだった。
ジョン・ギッティンズ・・・幾何級数的割引の想定を用いて、ギッティンズは「少なくともかなりすぐれた近似」と思われる戦略について考えた。多腕バンディットのアームを一本ずつ別々に考えて、それぞれの価値を割り出そうとしたのだ。・・・次にもう一度プレイした場合に勝つ確率がこのくらいならもうプレイを止めてよいと思える、そんな率が存在する。・・・ギッティンズ指数・・・が最も高いマシンで常にプレイするのだ。
隣の芝は青いという古いことわざがあるが、数学はその理由を教えてくれる。既知のものと未知のものとで違いはないと予想されている場合、あるいは未知のもののほうが不利かもしれないと思われている場合でも、未知のもののほうが有利な可能性があるのだ。試されていないルーキーは、実力が拮抗していると思われるベテランよりも価値が高い（少なくともシーズン開幕直後は）が、それはルーキーについての情報のほうが少ないからにほかならない。
ギッティンズ指数は将来の利得に対する幾何級数的割引にもとづいており、各プレイの価値が直前のプレイから一定の割合で下がると想定している。しかし行動経済学や心理学の様々な実験によって、現実の人間はそんな想定をしないということが示されている。それに、選択肢の切り替えに伴ってコストが生じるなら、ギッティンズ戦略はもはや最適でもない。・・・すぐに計算できるものではない。
後悔に着目するのだ。・・・経営学者のチェスター・バーナード・・・「やってみれば、失敗してもなにか少しは得るところがあるが、やってみもしないのは、やればあったかもしれない測りしれない可能性を失うだけだ」
ジェフ・ベゾス「後悔最小化の枠組み・・・私は８０歳になった自分を想像して、「オーケー。今、私は自分の人生を振り返っているところだ。後悔の数が最小限になっていればいいのだが」と言えたらよいと思いました。・・・失敗しても後悔しませんが、挑戦しなかったら後悔するとわかっていました。来る日も来る日も後悔にさいなまれるとわかっていたのです。だからそう考えたとき、驚くほどたやすく決断できたのです。」
後悔の最小化を保証してくれるアルゴリズム・・・信頼上限（UCB; Upper Confidence Bound）アルゴリズムと呼ばれるものである。・・・多腕バンディット問題では信頼区間の上端が最も高い選択肢を選べというきわめて単純な方針が得られる。
不確実性に立ち向かう楽観主義・・・信頼上限アルゴリズムは楽観主義とは完璧に合理的なものだということを示す。今までに得られた証拠を基に、ある選択肢が最良の場合どのくらいよいものとなり得るかに着目することにより、このアルゴリズムは情報の少ない様々な選択肢を底上げする。その結果、意思決定プロセスに探索の要素がおのずと加わり、どの選択肢も大成功をもたらす可能性を持つことから、新たな選択肢に対して積極的に向かっていくようになる。同じ原理を、未知なる領域の価値を高めることによって周囲の空間を探索する「楽観ロボット」との製作に当たる、MITのレスリー・ケルブリングらも用いている。・・・長い目で見れば、楽観主義は後悔に対する最善の防止策となる。
治療法の選択は多腕バンディット問題として扱うべきであり、試験の途中であってもよりよい治療を患者に受けさせる努力をすべきと考えているのだ。・・・１９６９年、ニューヨーク州立大学の生物統計学者のマーヴィン・ゼレンは、適応的な臨床試験の実施を提案した。・・・ある治療法が成功すれば次にそれが使われる確率を上げ、失敗したら使われる確率を下げていくというやり方である。・・・・実際の臨床試験で使われたのは、体外模型人工肺治療（ECMO）・・・ハーヴァード大学公衆衛生学部の生物統計学教授ジム・ウェアらはECMO使用の政党制を確信し、「これ以上の無作為割付を養護するのは倫理的に難しい」と結論した。
試験の実施者らは、ECMOの有用性には「利用できるエビデンスの解釈にばらつきがあるので議論の余地がある」と述べて試験を正当化した。・・・ECMOを支持する方針を取れば死亡リスクが抑制できるという先行する予備的知見と合致すると結論された。
人は概して探索に重きを置きすぎる傾向があるらしい。最良のものよりも新しいものを過度に高く評価しがちなのだ。
われわれは秘書選びでは早まってしまいがちだが、航空会社選びでは探索をやめるのが遅すぎる傾向があるらしい。
人間が自立までにこれほど長くかかる理由・・・成長の過程で探索と活用のトレードオフの解決法を習得するためです。多腕バンディットをプレイするための優れたアルゴリズムでは、早いうちに探索をたくさんして、得た情報をあとで活用する傾向がある。しかしゴプニックは「このパターンには、探索段階にいる間は良い利得が得られないという欠点があります」と指摘する。だから幼児期が存在するのだ。「幼児期には可能性の探索だけすれば良く、利得の心配をする必要はないのです。利得のことは、ママやパパやおばあちゃんやベビーシッターが面倒を見てくれますから」。
- 作者: アリソン・ゴプニック,アンドルー・N・メルツォフ,パトリシア・K・カール,峯浦厚子,榊原洋一
- 出版社/メーカー: PHP研究所
- 発売日: 2003/08/23
- メディア: 単行本
- クリック: 2回
- この商品を含むブログ (4件) を見る
読書をしてきた人なら知っている岐路に私も到達した。この世で与えられた時間に限りがある中で、新しい本をもっと読むべきか、あるいはあのむなしい消費ーむなしいというのは終わりがないからだーをやめて、かつて最も強烈な楽しみを与えてくれた本を読み返すべきかーリディア・デイヴィス
カーステンセンの研究グループは、年齢とともに社会的ネットワークが縮小するのは、重として抹消的な関係を切り捨てて、親しい友人や家族からなる中核的な関係に気持ちを集中するからだということを見出した。
対象のソートに労力を注ぐことは、あとで検索に労力を費やさねばならないことに備える、先制攻撃にほかならない。細かいバランスをどうすべきかはその場の具体的なパラメーターによって決まるが、ソートというのは将来の検索を助ける場合のみ価値がある。・・・無秩序は必ずしも悪くない。
無秩序の害と秩序の害が定量化可能であり、それらに伴うコストは「時間」という共通の通貨で計れる。
チャールズ・ラトウィッジ・ドジソン・・・数学者だったことを知っている人のほうがまれだ。今ではルイス・キャロルとして最もよく知られている。
テニス大会ー順位の正しい決め方および現行方式の誤りを示す証拠
勝ち残りトーナメント方式・・・勝ち残り方式では二位を決めるのに十分な情報も得られない。それどころか、優勝者以外については何もわからないのだ。
数学的事実として、二番目に強い選手が実力に見合った順位となる確率は三十一分の十六にすぎない。実力で上位の四選手が適正な順位となる確率は非常に低く、実際にそうなる確率は一対十二なのだ。
総当たり戦方式・・・もっとも包括的なやり方と言えるが、ひどく手間がかかる。
トリックの指摘によれば、スポーツのリーグが重視するのはなるべく迅速かつ能率的に順位を決定することではない。・・・ソート理論でこれが関心事となることはまずない。
完全なソートをしたいなら、比較はn log n回するのが正しいということは分かっています。これならすべての順位が決められます。
例えば野球では、チームの実力とはほぼ無関係に、一つのチームは全試合の３０％では負けて、全試合の３０％では勝つものなのです。・・・勝ち残り方式・・・最強のチームでも優勝する確率は0.7の６乗、すなわち１２％にも満たない。
サッカー・・・六対一で圧勝しても、その勝利が統計学的な偶然である可能性は７％残っている。
当時の野口悠紀雄は知らなかったが、彼の書類整理方法は最長未使用時間の原理を発展させたものと言える。最長未使用時間法では、キャッシュに新しいアイテムを加えるときにはもっとも古いアイテムを捨てることになっているが、新しいアイテムをどこに置くかは決まっていない。・・・自己組織化リスト・・・あらかじめその順番がわかっていれば、全体を探索するのにかかる時間が最短となるようにデータ構造を最適化することができます。・・・これはオフラインの最適アルゴリズムです。神のアルゴリズムと言ってもいいし、天のアルゴリズムと言ってもいい。もちろん未来のことは誰にもわかりません。だから問題は、未来がわからないなら、この天上の最適アルゴリズムにどれほど近づくことができるか、となります。
最長未使用時間の原理に従ってただアイテムをつねにリストの先頭に戻せば、探索にかかる時間全体は、未来が分かっている場合の二倍以上には決してならないはずだということだ。こんな保証ができるアルゴリズムはほかにない。
別のタスクが完了しないと着手できないタスクがある状況を、スケジューリング理論の研究者は「先行制約」と呼ぶ。
メディアによる事象の取り上げ方は、現実世界で実際に起きる頻度に対応していない。社会学者のバリー・グラスナーの指摘によれば、アメリカでは１９９０年代の間に殺人事件の発生率が２０％下がったが、同じ期間にアメリカのニュース番組で銃による暴力事件が使われた回数は６００％増加した。
オーバーフィッティングがどこよりも強力で厄介なのはビジネスの世界だろう。スティーブ・ジョブズ「インセンティブという仕組みは有効です。だから、人に何かをさせるためにどんなインセンティブを与えるかについては、よく考えなくてはいけません。様々なインセンティブの仕組みから、予想を超えたありとあらゆる結果が生じるのですから。」
Yコンビネーターのサム・オルトマン会長「CEOが何かを評価すると決めたら、それがどんなものであっても会社はそれを実現しようとする。まさにそれが現実なのです」。
面談の実施回数によって評価・・・短時間で面談を終わらせたがり、クライアントの就職を実際に助けることにはあまり時間をかけなくなってしまった。ある連邦執行機関では、捜査官に月間ノルマを与えると、月末には緊急性の高い事件には手を出さず、簡単な事件を選ぶことが判明した。ある工場では生産量の評価を実施したところ、監督者たちが設備の保守や修繕をないがしろにするようになり、その後の大事故につながった。・・・不適切な事柄が巧妙かつ容赦なく最適化されているのだ。
教育の場で、学習内容に対して本当に優れた能力を持つ学生たちのクラスと、「試験対策を教え込まれた」だけのクラスを見分けるにはどうすればよいのか。ビジネスの世界で、本物のスター社員と、会社で重視される成績指標や上司の意向に自分の仕事を抜け目なくオーバーフィットさせただけの社員を、どうしたら区別できるのか。
とりわけ重要な戦略の一つがクロス確認（注：クロスバリデーションのこと、これは「確認」と訳すのは誤りで交差検証法と訳すべき）である。
未知のデータにどのくらい適合するかという「汎化性能」も評価することである。逆説的だが、この時使用データを減らす場合もある。
コンピューター科学者は、モデルの複雑さにペナルティを与えるというこの方針を正則化と呼ぶ。・・・１９９６年、生物統計学者のロバート・ティプシラニがLASSOというアルゴリズムを発見した。
各項の重みに対してこのように縮小する圧力を加えることにより、ラッソは可能な限り多くの重みを完全にゼロとする。そして、結果に対して大きな影響を与える項だけを方程式に残す。
複雑さにペナルティを与えるという原理は自然界でも見られる。次巻、記憶力、エネルギー、注意力には限界があるので、生物はほぼ自動的に単純さへ向かう圧力を受ける。例えば代謝の負担が生物の複雑さを抑えるブレーキの役割を果たし、過度に精巧な機構には熱量のペナルティーを科す。 人間の脳が一日の総摂取熱量のおよそ五分の一を消費するという事実は、人間の知的能力が我々に与えてくれる進化上の利点の証拠となる。
加える処理が少ないと精度が下がるという見方が世間では広く支持されているが、ヒューリスティック研究によれば、情報や計算や時間が少ないほうが実は精度が上がることがわかる・・・より少ない因子とより少ない計算を用いてより単純な答えに達することを好むヒューリスティックは、まさにこの「少ないほうが有効」という効果をもたらす。
制約緩和・・・問題から制約の一部を取り除き、解決したい問題を解き始める。いくらか前進したところで、取り除いていた制約を問題に戻す。つまり、問題を一時的に扱いやすくして、後で本来の問題に戻すというやり方をするのだ。
正直に言って、長年この分野で研究してきた私にとって、これほど多くのアルゴリズム問題でランダム性が有効であることはまさに謎です。効率的で有効なのは確かですが、そのような働きをする理由や仕組みは、まったくもって謎なのです。マイケル・ラビン
偶然を利用することは、最も困難なたぐいの問題に取り組む際に周到で効果的な手段となりえることがわかる。それどころか、他に有効な手がない場合の唯一の手段ということもある。
ある種の問題では最良の決定論的アプローチよりも乱択アプローチのほうがうまくいく。この事実には重大な意味がある。完全に論理的に答えを導くのではなく偶然に頼ることが、問題に対する最良の解法となることもあるのだ。
素粒子の相互作用やソリティアで勝つ確率を計算するような問題の多くは、それ自体が元々確率論的なので、モンテカルロ法のような乱択アプローチで解くのはかなり理にかなっている。しかしランダム製の威力についての最も驚くべき発見は、一見すると偶然などまったく関与しないと思われる状況でもランダム性が利用できるということかもしれない。
ミラー＝ラビン素数判定法と呼ばれ、これを使うと任意の精度で巨大な数でも素数であるかどうかすばやく判定できる。ここで、「である」とはどういう意味かという哲学的な問題が気になってくるかもしれない。我々は数字が確実性を備えた領域であることにすっかりなれきっているので、数が「おそらく素数」だとか「ほぼ確実に素数」だとか言われると抵抗を覚える。どのくらい確実なら十分に確実と言えるのか。実際には、インターネット接続や電子商取引を暗号化する現代の暗号化システムは、偽陽性率が１００万分の１０億分の１０億分の一未満となるように調整されている。これは小数で表せば頭にゼロが２４個並ぶ数であり、地球上に存在する砂粒の総数と同じ回数だけ判定を行った場合に誤って素数と判定される回数が１回未満ということである。ミラー＝ラビンの判定法をわずか４０回適用すれば、この水準に到達できる。
ミラー＝ラビン素数判定法という名前は聞いたことがないかもしれないが、ノートパソコンやタブレット端末、携帯電話ではこれが大活躍している。発見されてから数十年が経ったが、今でも幅広い領域で素数を見つけて確認するのに使われる標準的な方法である。オンラインでクレジットカードを使えば必ず、見えないところでこの判定法が実行されているし、無線や有線で安全に通信するためにもたいていこれが実行されている。
ジッターを投入するにせよ、ランダム再出発を用いるにせよ、あるいは時には質の低下も受け入れるにせよ（Ex. メトロポリス法）、ランダム性は極大値を避けるのにものすごく役立つ。偶然とは、手ごわい最適化問題に対処するのに実行可能な方法であるばかりではない。多くの場合、必要不可欠なのだ。・・・ランダム性をどのくらい利用すべきか。どんな時に利用すべきか。・・・旅行計画の作成が完了したかどうか、どうしたらわかるのか。・・・焼きなまし法
パケット交換・・・一つの接続に一つのチャンネルを占有させるのではなく、発信者と受診者がそれぞれのメッセージをパケットと呼ばれる小さな断片に分割し、共有のデータの流れに合流させる。はがきが光速で運ばれるようなものと考えればよい。
接続と呼ばれるものは、二つの終末点の間で合意によって成立する幻想です。・・・インターネットには接続というものが存在しません。・・・ただ手紙を配達するだけです。
世界で最も翻訳しにくい単語は、コンゴ民主共和国の南東部で使われているチルバ語の「ilunga」であることがわかりました。・・・この言葉は、「どんなひどい仕打ちも一度目は喜んで許し、二度目は我慢するが、三度目には決して許さない人」を表します。
発信者がまずすべきことは「対称性を破る」ことだ。・・・向こうから近づいてきた歩行者を避けようと右に動いたら相手も同じ方向へ動き、今度は二人共同時に反対方向へ動くということを繰り返していては、何も解決しない。
単純な解決策の一つは、両方の基地にコイン投げをさせることだ。・・・競合相手がさらに増えていくと、ネットワークのスループットは崖から落ちるように一気に下るおそれがある。
突破口は、連続して失敗した後の平均待機時間を伸ばすという手だった。具体的には、再送信を試みるまでの最長待機時間を二倍にしていくのだ。・・・指数バックオフと呼ばれる。
競合する通信の数が不明で不可知で絶えず変動し、構造が不明なネットワークに埋め込まれた伝送終端にとって、有効性が期待できるスキームは一つしかない。指数バックオフである。
指数バックオフは、ネットワークのセキュリティーでも重要な役割を果たす。
人間社会では、一定の回数だけチャンスを続けて与え、それ以降はまったく与えないというやり方をすることが多い。三振したらアウトというわけだ。寛容、慈悲、忍耐が求められるほぼすべての状況で、このパターンが通常は支配的である。しかし端的に言って、このやり方は間違っているかもしれない。
付き合いの約束を守らないという迷惑なくせのある幼なじみ・・・誘いの頻度に対する指数バックオフだ。
現在TCP（伝送制御プロトコル）の渋滞制御の中核に位置するのは、加法的増加・乗法的減少というアルゴリズムである。・・・１つ目のパケットが上手く受信されたらパケットをさらに２つ伝送し、これもうまく届いたら今度は一度に４つ伝送する、といった具合に送るパケットを増やしていく。しかしいずれかのパケットの確認応答が発信者側に戻ってこなければ、直ちに加法的増加・乗法的減少アルゴリズムがあとを引き継ぐ。・・・一度に複数のパケットを伝送してそれが全て受信されたとしても、伝送するパケットの個数を二倍にするのではなく、一つだけ増やす。パケットが行方不明になったら、伝送速度を半分に下げる。・・・TCPののこぎり波形と呼ばれる特徴的な帯域幅の波形が生じる。
ピーターの法則（すべての人は昇進を重ね、各々の無能レベルに到達する）・・・階層的組織では、仕事をうまくこなす人間にはその報いとして昇進が与えられるが、その新しい仕事には今までよりも複雑な課題や難しい課題が伴うかもしれない。従業員が昇進を重ねた末に仕事がうまくこなせない地位に達したら、出世の道はそこで行き止まりとなり、後は退職するまでその身分のままだ。そうだとすれば、やがて組織全体が仕事をうまくこなせない人間で埋めつくされるのは当然だ。
一流法律事務所のクラヴァス・スウェイン・アンド・ムーアが考案したクラヴァス方式では、ほぼ新卒者のみを採用して最下級の地位に就かせ、それからは昇進させるか解雇するかのいずれかを何年も続ける。
ピーターの法則が指摘するような組織の停滞と「昇進か解雇か」方式の容赦ない厳しさとの中間に当たる別の方法はないのだろうか。加法的増加・乗法的減少アルゴリズムはまさにそんな方法だ。
TCPののこぎり波形から得られる教えでは、変動して予想のつかない環境では、とりあえず物事をそのまま推し進めることがじつは、資源を最大限に利用する最善の（または唯一の）方法となる場合もあるということだ。大事なのは、失敗への対応を的確かつ柔軟に行うことである。
停止問題・・・アラン・チューリングが１９３６年に証明したとおり、コンピュータープログラムは別のプログラムが果てしなく永久に計算を続ける可能性があるかどうかを明らかにすることが絶対にできない
ロジャー・マイヤーソン「ナッシュ均衡は経済学や社会科学に根本的で広範な影響をもたらしている。生物学におけるDNAの二重らせん構造の発見に匹敵するほどの影響を」
数学の研究対象は真理であり、コンピューター科学の研究対象は計算量である。・・手に負えない問題に関する限りは、解が存在するだけでは十分とは言えない。
カリフォルニア大学バークリー校のコンピューター科学者クリストス・パパディミトリウは、ゲーム理論は「行為者の取る均衡行動を予想するが、均衡状態に到達する過程ーこれこそコンピューター科学者にとって最大の関心事であろうにーについては感知しないのが常である」
スタンフォード大学のティム・ラフガーデン「なるほど。しかし、われわれはコンピューター科学者ですよね？われわれに使えるものがほしい。存在するというだけではなく、どうしたら見つけられるか教えてほしい」
２００５年から２００８年にかけてパパディミトリウと共同研究者らは、ナッシュ均衡を見出すだけでも手に負えない問題であるということを証明した。・・・「均衡という概念が効率的に計算できないなら、合理的行為者の行動に関する予想としての信頼性の多くが失われる。」
MITのスコット・アーロンソン「私の見解としては、ナッシュ均衡が存在するという公理が（たとえば）自由市場と政府の介入との拮抗に関する議論と関係があるとみなされるなら、その近郊を見出すことが［手に負えない］という公理もまた関係があると見なすべきである」
eベイの元リサーチディレクター、カマル・ジャイン「ノートパソコンに発見できないなら、市場にも発見できない」
囚人のジレンマ・・・無秩序の代償を定量化することによって、この分野では分散型システムのメリットとデメリットを評価するための具体的で厳密な方法が得られた。・・・無秩序の代償が小さいということは、よかれ悪しかれ、システムにとくに手を加えなくても、身長に管理された場合と抱いた同程度に良好な状態を保てるということを意味する。これに対し、無秩序の代償が大きい場合には、うまく調整すれば状態が改善される可能性があると考えられる。
共有地の悲劇・・・平均的な労働者は認められている休暇日数の半分しか使わず、驚くべきことに労働者の１５％は休暇をまったく取っていないことが判明した。・・・社員は一番たくさん休んでいるやつと思われたくないので、休暇の取得を躊躇するだろう。結局、最低日数を競うレースになる。
ケン・ビンモア「囚人のジレンマが人間の強力の本質を捉えていると考えるのは明らかに誤りである。そうではなく、囚人のジレンマは、協力が生じにくいように設定された状況を表現しているのだ」
ゲームのルールのせいで悪い戦略を選ばざるを得ない場合には、戦略の変更を目指すべきではないかもしれない。むしろゲーム自体の変更を目指すべきだろう。
メカニズムデザイン・・・どんなルールなら、相手がこちらの望む行動をしてくれるか
を問う。
エバーノートのCEO、フィル・リービンは、全社員を対象として休暇を取得したら１０００ドル支給するという方針を打ち出して話題を呼んだ。・・・ゲーム理論の観点から見るとじつは方向を誤っている。・・・１００万ドルを盗んだ犯人が二人共捕まるなら、１０００万ドルを盗んでも同じことだ。・・・最低限の（休暇の）取得を義務化すればよい。レースを変えることが出来なくても、ゴールは変えられる。・・・安息日を守れといった宗教的戒律は、全能の神から課されたにせよ、もっと身近な宗教コミュニティのメンバーから課されるにせよ、商店主が直面する問題を手際よく解決してくれる。
顕示原理・・・ロジャー・マイヤーソンは、戦略的に真実を隠すことが必要とされるどんなゲームも、単純な正直さ以外に何も必要としないゲームに変換できることを証明した。
ポール・ミルグロム「自分の見ているものは自分に見ることのできる最良のものの一つだということが確信できるのです」
合理的な意思決定の方法として直感的に納得の行く標準的なやり方は、利用できるすべての選択肢を入念に検討し、その中で最良のものを選ぶことだ。・・・それはコンピューターがする仕事についての時代遅れな見方に過ぎない。そんなやり方は、簡単な問題だけに許されるぜいたくなのだ。難しい問題を扱う場合には、最短の時間でもっとも合理的な答えを出せる方法こそ最良のアルゴリズムであり、この場合にはすべての要素をじっくり検討したり全ての計算を完遂したりすることは決してない。
