アカウント名:
パスワード:
「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」
うん？ それはつまり 両者が同時に切りたい場所を申告するための公平な環境が必要だよね。話を簡単にするために「中間でカット」することは実現できたと仮定するとしても。
それを2者だけで実現可能なのか?
ちなみに3者を導入すると「裏で取引」が発生する余地が出るので、「公平な第3者」前提は一般には使えないはずなのだが…。
一方で、「同時」とかの条件って、順序性を保証する場合と違って確認が難しかったはずだが…。# 難しいからこそ手品ができる。
なんか一番大事な部分が説明されていない気がする。
箱に入れるとき、箱に入っている間は問題ないとしましょう。それでも箱から取り出すときにすり替えることができる。
もちろん、常にすり替える事ができるとは限りませんが、すり替えることができてすり替える価値がある場合は、すり替えることができる、というのであれば「公平な場」とは言えますまい。「確率的に」すり替えのチャンスが発生する場合があるなら、その段階で「公平な場」とはいえないはずです。
一方で、「たまたますり替えられない状態」だった場合には、その回の交渉を決裂させて再度1からやり直しにすることで「すり替えのチャンス」を作る、という戦略があり得るはずです。
.
たとえば。文字通り同じ動作を二人が同時に行っていることを証明することができないとしましょう。ジャンケンですら、微妙に後出しをすることができますよね？あのように厳密な同時性を証明できない世界を考えてください。というか、厳密な同時性を証明できるなら、その段階で問題は解決していますが、厳密な同時性の証明は他のアルゴリズムでは前提としていないので、ここでもないことにしましょう。
この場合、自分の要求を紙に書いて箱に入れる所までは、紙に何を書いたのか互いに秘密にするとしましょう。で、箱の中に紙がある間、紙をすり替えることは不可能だとします。
しかし、同時性が保証されていない世界では、紙を取り出すときに1つづつ取り出すしかありません。また「二人で一緒に１つの紙を取り出す」のも難しいでしょうから、「どちらかが1つを選んで取り出す」事になるはずです。この場合、1つ目の紙を取り出した段階で「その1つ目の紙に書いてある情報」は両者で共有することになります。仮にこの紙がAさんの主張だったとしましょう。
- 箱の中にはBさんの主張が書いてある。- Bさんは紙になんと書いたのか判っている。- BさんはAさんの主張を知っているので、紙をすり替えることで有利な立場に立てる。またそのための紙は用意してある
という条件が揃った。Bさんの戦略は次のとおりになります。
a) Aさんが取り出した場合は、Bさんは紙になんと書いてあろうが「そんな記述をした覚えはない」と交渉を破棄するb) Bさんが取り出した場合は、紙をすり替える
b が実施可能な場合、この場は「公平な場」とは言えません。しかし、a のせいで「公平に分割する」に至りません。「千日手」状態が起こるだけです。この場合も「公平な場が設置できた」とは言えない。
cut and choose のような戦略はこのような「千日手」状態が発生しません。なので cut and choose よりも「よい」戦略であるためには、「千日手」状態を発生させないような「場」の提示が不可欠のような気がするのですよ。
この問題の厄介なところは「ハッシュ」などの確率論的な同一性証明は「証明になっていない」という点です。たとえ 1/2^128 の確率であろうとも、「一方の紙の中身だけがすり替える前とすり替えた後が同じハッシュ値になる(もう一方は同じ値にならない)」なら、公平な場とは言えない。なので、紙に書いた内容のハッシュ値を、箱から髪を取り出す前に宣言する、という手は使えない。
じゃぁ、自分が紙に書いた内容を事前に宣言するなら? 同時性が保証されないのなら、「後で宣言する」側が有利になる。つまり、Aさんが先に宣言し、Bさんが後に宣言するとして、今Bさんが箱の中にある内容よりも有利な条件を思いついたなら、宣言の際にわざと紙に書いたのと違うことを言って、交渉を決裂させる事ができる(もちろん、ハッシュを使っていても同じこともできます)。もし、万が一にもBさんの紙を箱から取り出す際にすり替えが可能だった場合は、「宣言したのと同じ内容を書いた紙」とすり替えればよい。
「千日手」状態を発生させない条件が見当たらないわけです。
うむ。それで実装できたと思う人はこういう手品を見てから考え直したほうが良い。http://vision.ameba.jp/watch.do?movie=2766998 [ameba.jp]
＞ちなみに3者を導入すると「裏で取引」が発生する余地が出るので、「公平な第3者」前提は一般には使えないはずなのだが…。
第三者がまるごと食べるので二人の間の公平性は担保されます
いや、それでは「問題を完璧に解決していない」という弱点がある。
「第三者がとても食べ切れないほどの分量のケーキを、二者の間で公平に分割するにはどうすればよいか」
# 好きな部分を好きなだけ食って、残りを第三者に押し付ければええやん、という気がするんだが、# 数学者はよほど意地汚いらしい… :p
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
にわかな奴ほど語りたがる -- あるハッカー
ん？その前提は成り立つの?? (スコア:1)
うん？ それはつまり 両者が同時に切りたい場所を申告するための公平な環境が必要だよね。話を簡単にするために「中間でカット」することは実現できたと仮定するとしても。
それを2者だけで実現可能なのか?
ちなみに3者を導入すると「裏で取引」が発生する余地が出るので、「公平な第3者」前提は一般には使えないはずなのだが…。
一方で、「同時」とかの条件って、順序性を保証する場合と違って確認が難しかったはずだが…。
# 難しいからこそ手品ができる。
なんか一番大事な部分が説明されていない気がする。
fjの教祖様
Re: (スコア:0)
電話越しでなければ、紙に書いて箱に入れるとかすればいいので同時に宣言するのはさして難しくない。
Re:ん？その前提は成り立つの?? (スコア:1)
箱に入れるとき、箱に入っている間は問題ないとしましょう。それでも箱から取り出すときにすり替えることができる。
もちろん、常にすり替える事ができるとは限りませんが、すり替えることができてすり替える価値がある場合は、すり替えることができる、というのであれば「公平な場」とは言えますまい。「確率的に」すり替えのチャンスが発生する場合があるなら、その段階で「公平な場」とはいえないはずです。
一方で、「たまたますり替えられない状態」だった場合には、その回の交渉を決裂させて再度1からやり直しにすることで「すり替えのチャンス」を作る、という戦略があり得るはずです。
.
たとえば。文字通り同じ動作を二人が同時に行っていることを証明することができないとしましょう。ジャンケンですら、微妙に後出しをすることができますよね？あのように厳密な同時性を証明できない世界を考えてください。というか、厳密な同時性を証明できるなら、その段階で問題は解決していますが、厳密な同時性の証明は他のアルゴリズムでは前提としていないので、ここでもないことにしましょう。
この場合、自分の要求を紙に書いて箱に入れる所までは、紙に何を書いたのか互いに秘密にするとしましょう。で、箱の中に紙がある間、紙をすり替えることは不可能だとします。
しかし、同時性が保証されていない世界では、紙を取り出すときに1つづつ取り出すしかありません。また「二人で一緒に１つの紙を取り出す」のも難しいでしょうから、「どちらかが1つを選んで取り出す」事になるはずです。この場合、1つ目の紙を取り出した段階で「その1つ目の紙に書いてある情報」は両者で共有することになります。仮にこの紙がAさんの主張だったとしましょう。
- 箱の中にはBさんの主張が書いてある。
- Bさんは紙になんと書いたのか判っている。
- BさんはAさんの主張を知っているので、紙をすり替えることで有利な立場に立てる。またそのための紙は用意してある
という条件が揃った。Bさんの戦略は次のとおりになります。
a) Aさんが取り出した場合は、Bさんは紙になんと書いてあろうが「そんな記述をした覚えはない」と交渉を破棄する
b) Bさんが取り出した場合は、紙をすり替える
.
b が実施可能な場合、この場は「公平な場」とは言えません。
しかし、a のせいで「公平に分割する」に至りません。「千日手」状態が起こるだけです。この場合も「公平な場が設置できた」とは言えない。
cut and choose のような戦略はこのような「千日手」状態が発生しません。なので cut and choose よりも「よい」戦略であるためには、「千日手」状態を発生させないような「場」の提示が不可欠のような気がするのですよ。
.
この問題の厄介なところは「ハッシュ」などの確率論的な同一性証明は「証明になっていない」という点です。たとえ 1/2^128 の確率であろうとも、「一方の紙の中身だけがすり替える前とすり替えた後が同じハッシュ値になる(もう一方は同じ値にならない)」なら、公平な場とは言えない。なので、紙に書いた内容のハッシュ値を、箱から髪を取り出す前に宣言する、という手は使えない。
じゃぁ、自分が紙に書いた内容を事前に宣言するなら? 同時性が保証されないのなら、「後で宣言する」側が有利になる。つまり、Aさんが先に宣言し、Bさんが後に宣言するとして、今Bさんが箱の中にある内容よりも有利な条件を思いついたなら、宣言の際にわざと紙に書いたのと違うことを言って、交渉を決裂させる事ができる(もちろん、ハッシュを使っていても同じこともできます)。もし、万が一にもBさんの紙を箱から取り出す際にすり替えが可能だった場合は、「宣言したのと同じ内容を書いた紙」とすり替えればよい。
「千日手」状態を発生させない条件が見当たらないわけです。
fjの教祖様
Re: (スコア:0)
お互いの紙が提出されたのを確認してから、相手の紙を広げて確認すれば良い。
Re:ん？その前提は成り立つの?? (スコア:1)
うむ。それで実装できたと思う人はこういう手品を見てから考え直したほうが良い。
http://vision.ameba.jp/watch.do?movie=2766998 [ameba.jp]
fjの教祖様
Re: (スコア:0)
＞ちなみに3者を導入すると「裏で取引」が発生する余地が出るので、「公平な第3者」前提は一般には使えないはずなのだが…。
第三者がまるごと食べるので二人の間の公平性は担保されます
Re:ん？その前提は成り立つの?? (スコア:1)
いや、それでは「問題を完璧に解決していない」という弱点がある。
「第三者がとても食べ切れないほどの分量のケーキを、二者の間で公平に分割するにはどうすればよいか」
# 好きな部分を好きなだけ食って、残りを第三者に押し付ければええやん、という気がするんだが、
# 数学者はよほど意地汚いらしい… :p
fjの教祖様