修 士 論 文 の 和 文 要 旨 研究科・専攻 大学院 情報理工学研究科 情報・ネットワーク工学専攻 博士前期課程 氏 名 辻啓太 学籍番号 1731110 論 文 題 目 双対理論を用いたクラウドファンディングメカニズムデザイン 要 旨 クラウドファンディングとは，起業家がインターネット等を通じ，銀行等の金融仲介者を介 さずに幅広く個人に投資を募る方法である．クラウドファンディングのプラットフォーム例 としては，CAMPFIRE や kickstarter などがある．クラウドファンディングのメリットとし て，(1)銀行等からの融資と比べると資金集めが容易であり，起業が容易，(2)少額から気軽 に事業へ投資する事が出来るなどがある． 一方，現行のクラウドファンディング方式において，プラットフォームから資金を得た起業 家が資金を持ち逃げしてしまう可能性がある．このような問題を起業家のモラルハザードと 呼ぶ．起業家のモラルハザードが多発すると，クラウドファンディングプラットフォームが 市場としての信頼を失ってしまうと考えられる． クラウドファンディングは実社会で運用されているが，クラウドファンディングメカニズム の研究は少ない．メカニズムデザインの例として，Roland による，起業家のモラルハザード を考慮したクラウドファンディングのメカニズムデザインがある．しかし，Roland のモデル は複雑であり，遂行可能なメカニズムを求める事ができず，モデルの解析が困難である． そこで，Myerson によって提案された，プリンシパル・エージェントモデルに対する，線形 計画問題による解析アプローチを取り入れた．双対理論を用いたメカニズムデザインは，ク ラウドファンディングのモデルを線形計画問題として定式化し，双対理論による遂行可能な メカニズムの特徴づけを与えることが出来る． 本研究では，Roland らの考案したメカニズムを混合整数計画問題として表現し，双対理論 を用いたアプローチによってメカニズムの性質を解析することを目的とする．主たる結果と して，モラルハザードを考慮しない場合におけるクラウドファンディングにおいて，個人合 理性と実行可能性を満たすメカニズムに対して解析を行い，性質を明らかにした．さらに， モラルハザードを考慮したクラウドファンディングを展開系ゲームとしてモデル化し，2 段 階の混合整数計画問題として定式化した．
31 1 28
1 2 2 4 2.1 . . . 4 2.2 . . . 4 2.3 . . . 6 2.4 . . . 7 3 8 3.1 Roland . . . 8 3.2 . . . 16 4 19 4.1 . . . 20 4.2 . . . 28 5 38 6 45 6.1 . . . 45 6.2 . . . 45 A 48 A.1 . . . 48 A.2 . . . 48
1
CAMPFIRE [4] kickstarter [5] kickstater [13] Roland [11] Roland [11] Myerson [10] [2] Bayesian [14] Roland Roland2
2.1
n (v1, . . . , vi, . . . , vn)T i vi n− 1 v−i = (v1, . . . , vi−1, vi+1, . . . , vn)T (¯vi, v−i) (¯vi, v−i) = (v1, . . . , ¯vi, . . . , vn)T n 0 0n n× m 0 On×m 1 n [n] ={1, . . . , n} b, v ∈ Rn ∀i ∈ [n], bi ≥ vi b≥ v ∀i ∈ [n], bi > vi b > v2.2
[3] [11] 1 2 2.1. 31 2 all-or-nothing all-in • • • step 1 step 2 step 3 step 4
2.3
N = [n] S0 i∈ N Si S =!ni=0Si X0 i∈ N Xi x0 ∈ X0 xi ∈ Xi i ∈ N (x0, . . . , xn) X =!ni=0Xi " RM :S → X i∈ N Ti i∈ N ti ∈ Ti (t1, . . . , tn)T T =!i∈N Ti " PM :S → T 2.2. (CF ) " RM : S → X PM :" S → T CFM = ( "RM, "PM)2.4
CFM ⟨P ⟩ ⎧ ⎪ ⎨ ⎪ ⎩ min 0T ns s.t. As≥ b, s≥ 0n A∈ Rm+×n, c∈ Rn, b∈ Rm s∈ Rn 2.3. As > b, s > 0n s∈ Rn ⟨P ⟩ ⟨P ⟩ P P = { s ∈ Rn | As > b, s > 0n} ⟨P ⟩ ⟨DP ⟩ ⟨DP ⟩ ⎧ ⎪ ⎨ ⎪ ⎩ max bTu s.t. ATu≤ 0n u ≥ 0m (1) ⟨DP ⟩ D D ='u∈ Rm|bTu≥ 0, ATu ≤ 0n, u ≥ 0m, u ̸= 0m(. (1) P D [7] 2.1. P D 1. P = ∅ =⇒ D ̸= ∅ 2. D = ∅ =⇒ P ̸= ∅3
3.1 Roland
Roland [11] Roland 1 n all-or-nothing Roland 1 I c I ∈ R+: c∈ [0, 1): 1 K ⊆ R+× [0, 1) (I, c) (I∗, c∗)∈ K N = [n] i ∈ N i vi ∈ { 0, 1 } v = (v1, . . . , vn)T V = {0, 1}n i ∈ N i∈ N v∗ i i∈ Nv∗ci v∗ci = ) 1 if vi∗ = 0 0 if vi∗ = 1 CFM n + 1 x = (x0, x1, . . . , xn)T x0 = ) 1 if 0 otherwise, xi = ) 1 if i∈ N 1 0 otherwise i ∈ N tai ∈ R+, tpi ∈ R+ n ta = (ta 1, . . . , tan)T ∈ Rn+ n tp = (tp1, . . . , tpn)T ∈ Rn + (ta, tp) t x t a = (x, t) Roland step 1 (I, c)∈ K step 2 i ∈ N vi ∈ {0, 1} step 3 x0 ∈ {0, 1} step 4 • x0 = 0 , T 0 • x0 = 1 T = * i∈N tai – αT (α∈ [0, 1] α
– . i∈ N tai step 5 x0 = 1 1. i∈ N xi∈ {0, 1} x 2. x i∈ N tpi 3. * i∈N tpi 3.1. a = (x, t) * i∈N (tai + tpi)− I∗x0− c∗ * i∈N xi i ∈ N i∈ N vi∗xi− (tai + tpi) a = (x, t) * i∈N (tai + tpi)− I∗x0− c∗ * i∈N xi+ * i∈N {vi∗xi− (tai + tpi)} = * i∈N (vi∗− c∗)xi− I∗x0 3.1.1 Roland CFM K i ∈ N {0, 1} V = {0, 1}n K × V
{0, 1}n+1 Rn +× Rn+ CFM RM :" K × V → {0, 1}n+1 " PM : K × V → Rn +× Rn+ ((I, c), v) RM((I, c), v)" ((I, c), v) PM((I, c), v)" i ∈ N PM"ai((I, c), v) PM"pi((I, c), v) "
PM((I, c), v) = ("PMa((I, c), v), "PMp((I, c), v))
K N , (I∗, c∗), v∗ CFM (K, N , (I∗, c∗), v∗, CFM) CFM CFM 3.2. CFM = ( "RM, "PM) ((I, c), v) * i∈N " PMai((I, c), v)≥ I∗RM"0((I, c), v), (2) * i∈N
("PMai((I, c), v) + "PMpi((I, c), v))≥ I∗RM"0((I, c), v) + c∗
* i∈N " RMi((I, c), v), (3) n "RM0((I, c), v)≥ * i∈N " RMi((I, c), v) (4) • (2) • (3) • (4) (2) (3) CFM (4) CFM CFM
3.3. RM"∗ :K × V → X " RM∗0((I, c), v) = ⎧ ⎨ ⎩ 1 if * i∈N vi∗ ≥ 1−cI∗∗ 0 otherwise, " RM∗i((I, c), v) = ⎧ ⎨ ⎩ vi∗ if * i∈N vi∗ ≥ 1−cI∗∗ 0 otherwise x x [11] 3.4. (I∗, c∗) (I, c)∈ K v (5) Π((I, c), v|(I∗, c∗)) =* i∈N ("PMai((I, c), v) + "PMpi((I, c), v)) − + I∗RM"0((I, c), v) + c∗ * i∈N " RMi((I, c), v) , (5) step 4 (5) (I, c)∈ K 3.5. v π(v) (I, c) T = * i∈N tai v V (T|(I, c)) = {v ∈ V|-i∈N PM" a i((I, c), v) = T ∧ "RM0((I, c), v) = 1} (I, c)∈ K T =-i∈N ta i ∈ R+ P P (T|(I, c)) = * v∈V (T |(I,c)) π(v) (6)
(I, c)∈ K T ∈ R+ v ∈ V η(v|T, (I, c)) = ) π(v) P (T|(I,c)) if v ∈ V (T |(I, c)) 0 otherwise 3.6. (I∗, c∗) (I, c)∈ K T (7) ¯ Π0(T|(I, c), (I∗, c∗)) = * v∈V (T |(I,c))
η(v|T, (I, c))Π((I, c), v|(I∗, c∗)) (7)
3.7. T α∈ [0, 1] αT α T α α (K, N , (I∗, c∗), v∗, α, CFM) step 4 T (7) 3.8. (I, c)∈ K τ (I, c) = ) T = * i∈N " PMai((I, c), v) . . . . .v ∈ V, "RM0((I, c), v) = 1 / 3.9. (I∗, c∗) (I, c)
¯
Π (8)
¯
Π((I, c)|(I∗, c∗)) = *
T∈τ(I,c)
P (T|(I, c)) max{ ¯Π0(T|(I, c), (I∗, c∗)), αT}
+ *
v∈{v|RM!0((I,c),v)=0}
π(v)Π((I, c), v|(I∗, c∗)) (8)
v ∈ V π(v) .
¯
Π((I, c)|(I∗, c∗)) (I, c)
3.10. v∗i i ∈ N vi ∈ {0, 1}
(I, c)∈ K i v−i i (9)
Ui((I, c), (vi, v−i)|vi∗) = vi∗RM"i((I, c), (vi, v−i))
− ("PMai((I, c), (vi, v−i)) + "PM p
i((I, c), (vi, v−i))) (9)
i∈ N (9)
i ∈ N
(I, c) ∈ K (I, c) ∈ K ρ(I, c)
v−i ∈ {0, 1}n−1 π′(v−i) i∈ N v−i i 3.11. v∗ i i ∈ N vi U¯i (10) ¯ Ui(vi|vi∗) = * (I,c)∈K ρ(I, c) * v−i∈V−i
π′(v−i)Ui((I, c), (vi, v−i)|v∗i) (10)
i∈ N step 2 U¯i(vi|v∗i) vi 3.1.2 CFM 3.12. CFM (11) CFM C –truthful ∀i ∈ N , ∀vi∈ {0, 1}, ¯Ui(vi|v∗i)≤ ¯Ui(vi∗|v∗i) (11)
(11) C –truthful CFM i v∗i i
3.13. CFM (12) CFM E –truthful
∀(I, c) ∈ K, ¯Π((I, c)|(I∗, c∗))≤ ¯Π((I∗, c∗)|(I∗, c∗)) (12)
(12) E –truthful CFM (I∗, c∗)
3.14. CFM (13) CFM obedient
∀T ∈ τ(I∗, c∗), ¯Π0(T|(I∗, c∗), (I∗, c∗))≥ αT (13)
(13) obedient CFM
3.15. CFM C –truthful E –truthful obedient CFM
CFM 3.16. CFM ∀i ∈ N , ¯Ui(vi∗|v∗i)≥ 0 CFM 3.2 3.17. CFM CFM
Roland CFM find RM, "" PM
s.t. -i∈N PM"ai((I, c), v)≥ I∗RM"0((I, c), v),∀(I, c) ∈ K, ∀v ∈ V
-i∈N("PM a i((I, c), v) + "PM p i((I, c), v))≥
I∗RM"0((I, c), v) + c∗-i∈N RM"i((I, c), v),∀(I, c) ∈ K, ∀v ∈ V
n "RM0((I, c), v)≥-i∈N RM"i((I, c), v)∀(I, c) ∈ K, ∀v ∈ V
¯
Ui(vi|v∗i)≤ ¯Ui(vi∗|v∗i),∀i ∈ N , ∀vi ∈ {0, 1},
¯
Π((I, c)|(I∗, c∗))≤ ¯Π((I∗, c∗)|(I∗, c∗)),∀(I, c) ∈ K,
¯ Π0(T|(I∗, c∗), (I∗, c∗))≥ αT, ∀T ∈ τ(I∗, c∗), ¯ Ui(vi∗|v∗i)≥ 0, ∀i ∈ N , " RM :K × V → {0, 1}n+1, " PM :K × V → Rn +× Rn+. Roland [11] Roland 3.1. (K, N , (I∗, c∗), v∗, α, CFM = ( "RM∗, "PM)) CFM [11]
3.2
[10] [2] 1 n [n] n≥ 1 i ∈ [n] Qi i Di D0 D =!ni=0Di, Q = !ni=1Qi D0 i∈ [n] Di, Qid = (d0, d1, . . . , dn)T ∈ D q = (q1, . . . , qn)T ∈ Q 3.18. U0 : D× Q → R i∈ [n] Ui : D× Q → R d∈ D q ∈ Q U0(d, q) i∈ [n] Ui(d, q) P r Q q ∈ Q P r(q) 3.2.1 PAM : D× Q → R q ∈ Q d P AM (d|q) Myerson 3.19. PAM PAM(d|q) ≥ 0, ∀d ∈ D, ∀q ∈ Q, (14) * d∈D PAM(d|q) = 1, ∀q ∈ Q, (15) * τ∈T,ti=τi * d∈D P r(q)PAM(d|q)Ui(d, q) ≥ * t∈T,ti=τi * d∈D
P r(q)PAM(d|(q−i, ¯τi))Ui((d−i, ¯δi(di), q)),
∀i ∈ {1, . . . , n} , ∀τi ∈ Qi,∀¯τi ∈ Qi,∀¯δi : Di → Di (16) (16) (14) (15) PAM q ∈ Q D [10] Myerson 3.20. PAM
* q∈Q * d∈D P r(q)PAM(d|q)U0(d, q) Myerson[10] 3.2 3.2. D, Q ⟨P AP ⟩ ⟨P AP ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ max * q∈Q * d∈D P r(q)PAM(d|q)U0(d, q) s.t. PAM(d* |q) ≥ 0, ∀d ∈ D, ∀q ∈ Q, d∈D PAM(d|q) = 1, ∀q ∈ Q, * τ∈Q,qi=τi * d∈D P r(q)PAM(d|q)Ui(d, q) ≥ * t∈Q,qi=τi * d∈D
P r(q)PAM(d|(q−i, ¯τi))Ui((d−i, ¯δi(di), q)),
∀i ∈ {1, . . . , n} , ∀τi ∈ Ti,∀¯τi ∈ Ti,∀¯δi : Di → Di
PAM [10]
4
CFM Roland (I, c)∈ K ρ(I, c) = |K|1 , v π(v) = 21n i∈ N v−i π′(v−i) = 2n1−1 4.1. CFM S = K × V i vi CFM S(i, vi) (I, c)∈ K CFM S(I, c) 4.2. β ∈ S CFM (xβ, taβ, tpβ)∈ {0, 1} n+1 × Rn +× Rn+ xβ = (x0β, . . . , xnβ)T,taβ = 0 ta1β, . . . , tanβ1T tβp =0tp1β, . . . , tpnβ1T ta iβ i∈ N tpiβ i∈ N xβ, taβ, t p β 4.3. X ∈ {0, 1}(n+1)×|S| xβ X =2x1, . . . , x|S| 3 TA ∈ Rn×|S| ta β TA =0ta1, . . . , ta|S|1 TP ∈ Rn×|S| tp β TP =0tp1, . . . , tp|S|1 X, TA, TP CFM4.1
CFM X, TA, TP X, TA, TP 4.1. (I∗, c∗) (I, c) ∈ K , v (17) Π((I, c), v|(I∗, c∗)) = * i∈N 0 taiβ + tpiβ1− I∗x0β − c∗ * i∈N xiβ (17) β = ((I, c), v) . xβ, taβ, tpβ ((I, c), v) CFM X, TA, TP∀i ∈ {0} ∪ N , "RMi((I, c), v) = xiβ,
∀i ∈ N , "PMai((I, c), v) = taiβ, ∀i ∈ N , "PMpi((I, c), v) = tpiβ
Π((I, c), v|(I∗, c∗)) =* i∈N ("PMai((I, c), v) + "PMpi((I, c), v)) − + I∗RM"0((I, c), v) + c∗ * i∈N " RMi((I, c), v) , Π((I, c), v|(I∗, c∗)) =* i∈N ("PMai((I, c), v) + "PMpi((I, c), v)) − + I∗RM"0((I, c), v) + c∗ * i∈N " RMi((I, c), v) ,
=* i∈N (taiβ + tpiβ)− I∗x0β − c∗ * i∈N xiβ X, TA, TP β ∈ S ΠX,TA,TP(β|(I∗, c∗)) = -i∈N 0 ta iβ + tpiβ 1 − I∗x0β − c∗ * i∈N xiβ (I∗, c∗) (I, c) T V (T|(I, c)) 4.1. (I, c)∈ K ∀v ∈ V, T1, T2 ∈ τ(I, c), v ∈ V (T1|(I, c)) ∧ v ∈ V (T2|(I, c)) =⇒ T1 = T2 . (I, c)∈ K v ∈ V
∃T1, T2 ∈ τ(I, c), T1 ̸= T2, v ∈ V (T1|(I, c)) ∧ v ∈ V (T2|(I, c))
V (T1|(I, c)) = ) v ∈ V . . . . . * i∈N " PMai((I, c), v) = T1∧ "RM0((I, c), v) = 1 / ((I, c), v) CFM * i∈N "
PMai((I, c), v) = T1 V (T2|(I, c)) ((I, c), v)
CFM * i∈N " PMai((I, c), v) = T2 T1 ̸= T2 4.2. (I, c)∈ K 4 v ∈ V ..."RM0((I, c), v) = 1 5 = 6 T∈τ(I,c) V (T|(I, c)) . "RM0((I, c), v) = 1 v 4.1
4 v∈ V ...-i∈N PM"ai((I, c), v) = T ∧ "RM0((I, c), v) = 1 5 4 v ∈ V ..."RM0((I, c), v) = 1 5 = 6 T∈τ(I,c) V (T|(I, c)) X, TA, TP 4.2. (I∗, c∗) (I, c) (18) 1 2n * β∈S(I,c) ) * i∈N (taiβ + tpiβ)− I∗x0β − c∗ * i∈N xiβ / (18) . (I∗, c∗) (I, c) (I∗, c∗) (I, c) ¯ Π((I, c)|(I∗, c∗)) = * T∈τ(I,c) P (T|(I, c)) ¯Π0(T|(I, c), (I∗, c∗)) + * v∈V|!RM0((I,c),v)=0 π(v)Π((I, c), v|(I, c)) (19) (I∗, c∗) (I, c) T ¯ Π0(T|(I, c), (I∗, c∗)) = * v∈V (T |(I,c))
η(v|T, (I, c))Π((I, c), v|(I∗, c∗))
η
η(v|T, (I, c)) =
) π(v)
P (T|(I,c)) if v ∈ V (T |(I, c))
π(v) = 21n * T∈τ(I,c) P (T|(I, c)) ¯Π0(T|(I, c), (I∗, c∗)) = * T∈τ(I,c) P (T|(I, c)) * v∈V (T |(I,c)) π(v)
P (T|(I, c))Π((I, c), v|(I∗, c∗))
= * T∈τ(I,c) * v∈V (T |(I,c)) π(v)Π((I, c), v|(I∗, c∗)) = 1 2n * T∈τ(I,c) * v∈V (T |(I,c)) Π((I, c), v|(I∗, c∗)) 4.2 1 2n * T∈τ(I,c) * v∈V (T |(I,c)) Π((I, c), v|(I∗, c∗)) = 1 2n * v∈V|!RM0((I,c),v)=1 Π((I, c), v|(I∗, c∗)) (20) (20) (19) ¯ Π((I, c)|(I∗, c∗)) = * T∈τ(I,c) P (T|(I, c)) ¯Π0(T|(I, c), (I∗, c∗)) + * v∈V|!RM0((I,c),v)=0 π(v)Π((I, c), v|(I, c)) = 1 2n * v∈V|!RM0((I,c),v)=1 Π((I, c), v|(I∗, c∗)) + 1 2n * v∈V|!RM0((I,c),v)=0 Π((I, c), v|(I∗, c∗)) = 1 2n * v∈V Π((I, c), v|(I∗, c∗)) 4.1 (I, c) S(I, c) ¯ Π((I, c)|(I∗, c∗)) = 1 2n * v∈V Π((I, c), v|(I∗, c∗)) = 1 2n * β∈S(I,c) ) * i∈N (taiβ + tpiβ)− I∗x0β − c∗ * i∈N xiβ /
X, TA, TP (I, c) ˜ ΠX,TA,TP((I, c)|(I∗, c∗)) = 1 2n * β∈S(I,c) ΠX,TA,TP(β|(I∗, c∗)) = 1 2n * β∈S(I,c) ) * i∈N (taiβ+ tpiβ)− I∗x0β − c∗ * i∈N xiβ / X, TA, TP 4.3. i∈ N v∗i vi ∈ {0, 1} (I, c) i (21)
Ui((I, c), (vi, v−i)|vi∗) = v∗ixiβ − (taiβ + tpiβ). (21)
β = ((I, c), (vi, v−i))
.
Ui((I, c), (vi, v−i)|vi∗) = vi∗RM"i((I, c), (vi, v−i))
− ("PMai((I, c), (vi, v−i)) + "PM p
i((I, c), (vi, v−i)))
xβ, taβ, tpβ ((I, c), (vi, v−i)) CFM X, TA, TP
β = ((I, c), (vi, v−i))
∀i ∈ {0} ∪ N , "RMi((I, c), (vi, v−i)) = xiβ,
∀i ∈ N , "PMai((I, c), (vi, v−i)) = taiβ,
∀i ∈ N , "PMpi((I, c), (vi, v−i)) = tpiβ
Ui((I, c), (vi, v−i)|vi∗) = vi∗RM"i((I, c), (vi, v−i))
− ("PMai((I, c), (vi, v−i)) + "PM p
i((I, c), (vi, v−i)))
X, TA, TP , β ∈ S i∈ N
UiX,TA,TP(β|vi∗) = v∗ixiβ − (taiβ + tpiβ)
4.4. i∈ N v∗i vi i (22) ¯ Ui(vi|vi∗) = 1 2n−1|K| * β∈S(i,vi) 4
vi∗xiβ− (taiβ+ tpiβ)
5 (22) . ¯ Ui(vi|v∗i) = * (I,c)∈K ρ(I, c) ⎧ ⎨ ⎩ * v−i∈{0,1}n−1
π′(v−i)Ui((I, c), (vi, v−i)|vi∗)
⎫ ⎬ ⎭ π′(v−i) = 2n1−1 ρ(I, c) = |K|1 i vr S(i, vi) ¯ Ui(vi|v∗i) = * (I,c)∈K ρ(I, c) ⎧ ⎨ ⎩ * v−i∈{0,1}n−1
π′(v−i)Ui((I, c), (vi, v−i)|vi∗)
⎫ ⎬ ⎭ = 1 |K| * (I,c)∈K ⎧ ⎨ ⎩ * v−i∈{0,1}n−1
π′(v−i)Ui((I, c), (vi, v−i)|vi∗)
⎫ ⎬ ⎭ = 1 2n−1|K| * β∈S(i,vi) 4
v∗ixiβ − (taiβ + tpiβ)
5 X, TA, TP vi ∈ {0, 1} i∈ N ¯ UiX,TA,TP(vi|v∗i) = 1 2n−1|K| * β∈S(i,vi) 4
v∗ixiβ − (taiβ + tpiβ)
5
X, TA, TP CFM
4.5. CF M X, TA, TP * i∈N taiβ ≥ I∗x0β,∀β ∈ S, * i∈N (taiβ + tpiβ)≥ I∗x0β + c∗ * i∈N xiβ,∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S . CFM ((I, c), v)∈ K × V * i∈N " PMai((I, c), v)≥ I∗RM"0((I, c), v), (23) * i∈N
("PMai((I, c), v) + "PMpi((I, c), v))≥ I∗RM"0((I, c), v) + c∗
* i∈N " RMi((I, c), v), (24) n "RM0((I, c), v)≥ * i∈N " RMi((I, c), v) (25) ((I, c), v) CFM X, TA, TP ∀i ∈ {0} ∪ N , "RMi((I, c), v) = xiβ,
∀i ∈ N , "PMai((I, c), (v) = taiβ, ∀i ∈ N , "PMpi((I, c), (v) = tpiβ (23) (24) (25) * i∈N taiβ ≥ I∗x0β,∀β ∈ S, * i∈N (taiβ + tpiβ)≥ I∗x0β + c∗ * i∈N xiβ,∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S
4.6. CFM X, TA, TP ∀i ∈ N , ¯UiX,TA,TP(vi∗|vi∗)≥ 0 . CFM i ∈ N ¯ Ui(v∗i|vi∗)≥ 0 i∈ N X, TA, TP ¯ UiX,TA,TP(v∗i|v∗ i) ∀i ∈ N , ¯UiX,TA,TP(v∗i|vi∗)≥ 0 C –truthful 4.7. CFM C –truthful X, TA, TP ∀i ∈ N , ¯UiX,TA,TP(vi∗|v∗i)≥ ¯UX,T A,TP i (vi∗c|vi∗) . CFM C –truthful vi i∈ N ¯ U (vi∗|v∗ i)≥ ¯U (vi∗c|vi∗) X, TA, TP vi ∈ {0, 1} i∈ N U¯X,T A,TP i (vi|v∗i) E –truthful 4.8. CFM E –truthful X, TA, TP
∀(I, c) ∈ K, ˜ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ ˜ΠX,TA,TP((I, c)|(I∗, c∗)) . CFM E –truthful
X, TA, TP (I, c)
˜
(K, N , (I∗, c∗), v∗, CFM) C –truthful E –truthful CF M (26) find X, TA, TP s.t. * i∈N taiβ ≥ I∗x0β,∀β ∈ S, * i∈N (taiβ+ tpiβ)≥ I∗x0β + c∗ * i∈N xiβ,∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S, ¯ UiX,TA,TP(vi∗|v∗i)≥ 0 ≥ 0, ∀i ∈ N , ¯ UiX,TA,TP(vi∗|v∗ i)≥ ¯UX,T A,TP i (vi∗c|vi∗),∀i ∈ N , ˜
ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ ˜ΠX,TA,TP((I, c)|(I∗, c∗)),∀(I, c) ∈ K,
X ∈ {0, 1}(n+1)×|S|, TA∈ Rn×|S| + , TP ∈ Rn×|S| + (26)
4.2
(K, N , (I∗, c∗), v∗, CFM) CFM CFM ⟨F IP ⟩ ⟨F IP ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ find X, TA, TP s.t. * i∈N taiβ ≥ I∗x0β,∀β ∈ S, * i∈N 0 taiβ + tpiβ1≥ I∗x0β+ c∗ * i∈N xiβ∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S, ¯ UiX,TA,TP(v∗ i|vi∗)≥ 0, ∀i ∈ N X ∈ {0, 1}(n+1)×|S|, TA∈ Rn×|S| + , TP ∈ Rn×|S| + (27)K, N , (I∗, c∗), v∗ (28) ⟨F IMIP ⟩ * i∈{0}∪N * β∈S 0· xiβ + * i∈N * β∈S 0· taiβ +* i∈N * β∈S 0· tpiβ, (28) ⟨F IMIP ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ max * i∈{0}∪N * β∈S 0· xiβ + * i∈N * β∈S 0· taiβ +* i∈N * β∈S 0· tpiβ, s.t. * i∈N taiβ ≥ I∗x0β,∀β ∈ S, * i∈N 0 taiβ+ tpiβ1≥ I∗x0β + c∗ * i∈N xiβ,∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S, ¯ UiX,TA,TP(v∗i|vi∗)≥ 0, ∀i ∈ N X ∈ {0, 1}(n+1)×|S|, TA ∈ Rn×|S|+ , TP ∈ Rn×|S| + (29) ⟨F IMIP ⟩ (X, TA, TP) = (O (n+1)×|S|, On×|S|, On×|S|) ⟨F IMIP ⟩ ⟨F IMIP ⟩
⟨F ILP ⟩ FILP ⟨F ILP ⟩
⟨DF ILP ⟩ ⟨F ILP ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ max * i∈{0}∪N * β∈S 0· xiβ + * i∈N * β∈S 0· taiβ+ * i∈N * β∈S 0· tpiβ s.t. * i∈N taiβ ≥ I∗x0β,∀β ∈ S, * i∈N 0 taiβ + tpiβ1≥ I∗x0β + c∗ * i∈N xiβ,∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S, ¯ UiX,TA,TP(vi∗|v∗i)≥ 0, ∀i ∈ N X ∈ [0, 1](n+1)×|S|, TA ∈ Rn×|S| + , TP ∈ Rn×|S|+ , (30)
⟨DF ILP ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ min * i∈{0}∪N * β∈S δiβ s.t. I∗θβ + I∗ιβ − nκβ + δ0β ≥ 0, ∀β ∈ S, c∗ιβ + κβ − v ∗ i
2n−1|K|λi+ δiβ ≥ 0, ∀i ∈ N , ∀β ∈ S(i, vi∗),
c∗ιβ + κβ + δiβ ≥ 0, ∀i ∈ N , ∀β ∈ S(i, vi∗c),
−θβ − ιβ + 2n−11|K|λi ≥ 0, ∀i ∈ N , ∀β ∈ S(i, v∗i), θβ = 0, ιβ = 0,∀i ∈ N , ∀β ∈ S(i, v∗ci ), θβ ≥ 0, ∀β ∈ S, ιβ ≥ 0, ∀β ∈ S, κβ ≥ 0, ∀β ∈ S, λi ≥ 0, ∀i ∈ N ,
δiβ ≥ 0, ∀i ∈ ∀i ∈ {0} ∪ N , ∀β ∈ S
(31) |S| θ, ι, κ θ = (θ1, . . . , θ|S|), ι = (ι1, . . . , ι|S|), κ = (κ1, . . . , κ|S|) n λ λ = (λ1, . . . , λn)T ∆∈ R(n+1)×|S|+ ∆ = ⎡ ⎢ ⎣ δ01 . . . δ0|S| .. . . .. ... δn1 · · · δn|S| ⎤ ⎥ ⎦ 2.1 ⟨DF ILP ⟩ δiβ i∈ {0} ∪ N β ∈ S δiβ ≥ 0 FILP ⟨DF ILP ⟩ (32) DFILP = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (θ, ι, κ, λ, ∆) . . . . . . . . . . . . . . . . . . . . . . . . . . . * i∈N ∪{ 0 } * β∈S δiβ = 0, I∗θβ+ I∗ιβ − nκβ+ δ0β ≥ 0, ∀β ∈ S, c∗ιβ + κβ− v ∗ i
2n−1|K|λi+ δiβ ≥ 0, ∀i ∈ N , ∀β ∈ S(i, vi∗),
c∗ιβ + κβ+ δiβ ≥ 0, ∀i ∈ N , ∀β ∈ S(i, vi∗c),
−θβ − ιβ + 2n−11|K|λi ≥ 0, ∀i ∈ N , ∀β ∈ S(i, vi∗), θβ = 0, ιβ = 0,∀i ∈ N , ∀β ∈ S(i, vi∗c), θβ ≥ 0, ∀β ∈ S, ιβ ≥ 0, ∀β ∈ S, κβ ≥ 0, ∀β ∈ S, λi ≥ 0, ∀i ∈ N , δiβ ≥ 0, ∀i ∈ {0} ∪ N , ∀β ∈ S, (θ, ι, κ, λ, ∆)̸= (0|S|, 0|S|, 0|S|, 0n, O(n+1)×|S|) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (32)
2.1 ⟨F ILP ⟩ (32) DFILP • FILP DFILP • FILP DFILP ∀i ∈ N , v∗ i = 1 4.3. ∀i ∈ N , v∗ i = 1 DFILP . 0 ⟨DF ILP ⟩ β ∈ S 1 β ∈@i∈N S(i, vi∗c) 2 β ∈@i∈N S(i, v∗ i) 3 β ∈ S \ (A i∈N S(i, v∗i)∪ A i∈N S((i, vi∗c))) β 1 β (θ, ι, κ, λ, ∆) DFILP (θβ, ιβ, κβ, λ, 0n+1) I∗θβ + I∗ιβ − nκβ ≥ 0, (33) c∗ιβ+ κβ ≥ 0, ∀i ∈ N , (34) θβ = 0, ιβ = 0, (35) θβ ≥ 0, (36) ιβ ≥ 0, (37) κβ ≥ 0, (38) λi ≥ 0, ∀i ∈ N (39) (35) (33) (33) = I∗· 0 + I∗· 0 − nκβ =−nκβ ≥ 0
(38) κβ = 0 θβ = ιβ = κβ = 0, λi ≥ 0, ∀i ∈ N (40) 3 β (θ, ι, κ, λ, ∆) DFILP (θβ, ιβ, κβ, λ, 0n+1) β Jβ = ' j ∈ N ..β ∈ S(j, v∗cj )( N \ Jβ β I∗θβ + I∗ιβ− nκβ ≥ 0 (41) c∗ιβ + κβ − vi∗ 2n−1|K|λi ≥ 0, ∀i ∈ N \ Jβ (42) c∗ιβ + κβ ≥ 0, ∀i ∈ Jβ (43) − θβ − ιβ + 1 2n−1|K|λi ≥ 0, ∀i ∈ N \ Jβ (44) θβ = 0, ιβ = 0, (45) θβ ≥ 0, (46) ιβ ≥ 0, (47) κβ ≥ 0, (48) λi ≥ 0, ∀i ∈ N (49) (45) (41) (41) =−nκβ ≥ 0 (50) (48) κβ = 0 (42) (42) =− vi∗ 2n−1|K|λi ≥ 0 (51) ∀i ∈ N , v∗ i = 1 v ∗ i 2n−1|K| = 2n−11|K| > 0 ( ) =− vi∗ 2n−1|K|λi ≥ 0 =⇒ λi = 0 (52) θβ = ιβ = κβ = 0, λi = 0,∀i ∈ N \ Jβ ∀i ∈ Jβ, λi ≥ 0
λi β i i ∈ Jβ β ∈ S \ (A i∈N S(i, v∗i)∪ A i∈N S((i, v∗ci ))) ∀i ∈ N , λi = 0 (53) θβ = ιβ = κβ = 0 λi = 0,∀i ∈ N (54) 2 β (θ, ι, κ, λ, ∆) DFILP (θβ, ιβ, κβ, λ, 0n+1) I∗θβ+ I∗ιβ − nκβ ≥ 0, (55) c∗ιβ + κβ − vi∗ 2n−1|K|λi ≥ 0, ∀i ∈ N , (56) − θβ − ιβ + 1 2n−1|K|λi ≥ 0, ∀i ∈ N , (57) θβ ≥ 0, (58) ιβ ≥ 0, (59) κβ ≥ 0, (60) λi ≥ 0, ∀i ∈ N (61) λi β (53) (57) (57) =−θβ− ιβ − 1 2n−1|K| · 0 =−θβ− ιβ ≥ 0 (62) θβ, ιβ − θβ− ιβ ≥ 0 ⇐⇒ θβ = ιβ = 0 (63) (55) (63) (55) = I∗· 0 + I∗· 0 − nκβ =−nκβ ≥ 0 (64)
(60) κβ = 0 θβ = ιβ = κβ = 0 (65) (40) (54) (65) 0 (θ, ι, κ, λ, ∆) = (0|S|, 0|S|, 0|S|, 0n, O(n+1)×|S|) * i∈N v∗i = n DFILP
∃i ∈ N , v∗i = 0 4.4. ∃i ∈ N , v∗i = 0 DFILP . ϵ ⟨DF ILP ⟩ θ = 0|S|, ι = 0|S|, κ = 0|S|, λi = ) 0 if vi∗ = 1 ϵ if v∗ i = 0 ,∀i ∈ N , ∆ = O(n+1)×|S| (66) DFILP DFILP * i∈{ 0 }∪N * β∈S δiβ = 0, (67) I∗θβ + I∗ιβ− nκβ + δ0β ≥ 0, ∀β ∈ S, (68) c∗ιβ+ κβ− v ∗ i
2n−1|K|λi+ δiβ ≥ 0, ∀i ∈ N , ∀β ∈ S(i, vi∗), (69)
c∗ιβ+ κβ+ δiβ ≥ 0, ∀i ∈ N , ∀β ∈ S(i, v∗ci ), (70)
− θβ− ιβ+ 1 2n−1|K|λi ≥ 0, ∀i ∈ N , ∀β ∈ S(i, v∗i), (71) θβ = 0, ιβ = 0,∀i ∈ N , ∀β ∈ S(i, vi∗c), (72) θβ ≥ 0, ∀β ∈ S, (73) ιβ ≥ 0, ∀β ∈ S, (74) κβ ≥ 0, ∀β ∈ S, (75) λi ≥ 0, ∀i ∈ N , (76) δiβ ≥ 0, ∀i ∈ {0, 1, . . . , n}, β ∈ S (77) (66) (67) (68) (66) (68) = I∗· 0 + I∗· 0 − n · 0 + 0 = 0≥ 0 (69) (66)
• vi∗ = 0 i∈ N (69) = c∗· 0 + 0 − 0 2n−1|K|ϵ + 0 = 0≥ 0 • vi∗ = 1 i∈ N (69) = c∗· 0 + 0 − 1 2n−1|K| · 0 + 0 = 0≥ 0 (70) (66) i∈ N , β ∈ S(i, vi∗c) (70) = c∗· 0 + 0 + 0 = 0≥ 0 (71) (66) • vi∗ = 0 i∈ N 2n−11|K| > 0, ϵ > 0 (71) =−0 − 0 + 1 2n−1|K|ϵ = 1 2n−1ϵ > 0 • v∗ i = 1 i∈ N (71) =−0 − 0 + 1 2n−1|K|0 = 0≥ 0
(72) (77) θ = 0|S|, ι = 0|S|, κ = 0|S|, λi = ) 0 if vi∗ = 1 ϵ if v∗ i = 0 ,∀i ∈ N , ∆ = O(n+1)×|S| DFILP 4.3 4.4 i ∈ N FILP FILP
5
CFM Π0(T|(I, c), (I∗, c∗)) T x ta tp Π0(T|(I, c), (I∗, c∗)) (I∗, c∗) (I, c) ∈ K T ∈ τ(I, c) ¯ Π0(T|(I, c), (I∗, c∗)) = * v∈V (T |(I,c))η(v|T, (I, c))Π((I, c), v|(I∗, c∗)) (78)
= * v∈V (T |(I,c)) π(v) -v′∈V (T |(I,c))π(v′) Π((I, c), v|(I∗, c∗)) (79) = * v∈V (T |(I,c)) 1 2n 2n
|V (T |(I, c))|Π((I, c), v|(I
∗, c∗)) (80) = 1 |V (T |(I, c))| * v∈V (T |(I,c)) Π((I, c), v|(I∗, c∗)) (81) 5.1. (I, c) ∈ K τ (I, c) ) * i∈N taiβ . . . . .β ∈ S(I, c), x0β = 1 / . τ (I, c) τ (I, c) = ) * i∈N " PMai(((I, c), v) . . . . .v∈ V, "RM0((I, c), v) = 1 /
((I, c), v) CFM i ∈ N X, TA " RM0((I, c), v) = x0β, " PMai((I, c), v) = taiβ (I, c) S(I, c) (I, c) ∈ K τ (I, c) τ (I, c) = ) * i∈N taiβ . . . . .β ∈ S(I, c), x0β = 1 / X, TA, TP (I, c) TX,TA(I, c) = ) * i∈N taiβ . . . . .β ∈ S(I, c) ∧ x0β = 1 / (82) (I, c) T V (T|(I, c)) v ((I, c), v) 5.2. (I, c) T v ((I, c), v) SX,TA(T|(I, c)) = ) β ∈ S(I, c) . . . . . * i∈N taiβ = T ∧* i∈N xiβ = 1 / . (I, c) T v V (T|(I, c)) V (T|(I, c)) = ) v∈ V . . . . . * i∈N " PMai((I, c), v) = T ∧ "RM0((I, c), v) = 1 /
((I, c), v) CFM i ∈ N β = f ((I, c), v) X, TA " RM0((I, c), v) = x0β, " PMai((I, c), v) = taiβ SX(I, c) = { β ∈ S(I, c) | x 0β = 1} (I∗, c∗) (I, c)∈ K T X, TA, TP ¯ Π0(T|(I, c), (I∗, c∗)) = 1 |SX,TA (T|(I, c))| * β∈SX,T A(T|(I,c)) ) * i∈N (taiβ + tpiβ)− I∗x0β − c∗ * i∈N xiβ / X, TA, TP (I∗, c∗) (I, c)∈ K T ¯ ΠX,T0 A,TP(T|(I, c), (I∗, c∗)) = 1 |SX,TA (T|(I, c))| * β∈SX,T A(T|(I,c)) ) * i∈N (taiβ + tpiβ)− I∗x0β − c∗ * i∈N xiβ / obedient X, TA, TP 5.3. CFM obedient X, TA, TP ∀T ∈ TX,TA(I, c), ¯ ΠX,T0 A,TP(T|(I, c), (I∗, c∗))≥ αT . CFM obedient ∀T ∈ τ((I∗, c∗)), ¯Π0(T|(I∗, c∗), (I∗, c∗))≥ αT (I, c) T X, TA, TP Π¯X,TA,TP 0 (T|(I, c), (I∗, c∗))
(I∗, c∗) (I, c) X, TA, TP 5.4. (I, c) (I, c) ¯ Π((I, c)|(I∗, c∗)) = 1 2n * T∈TX,T A(I,c)
|SX,TA(T|(I, c))|max4Π¯0X,TA,TP(T|(I, c), (I∗, c∗)), αT5
+ 1 2n * β∈S(I,c)\SX(I,c) ΠX,TA,TP(β|(I∗, c∗)) . (I, c) (I, c) ¯ Π((I, c)|(I∗, c∗)) = * T∈τ(I,c)
P (T|(I, c)) max{ ¯Π0(T|(I, c), (I∗, c∗)), αT}
+ * v|!RM0((I,c),v)=0 π(v)Π((I, c), v|(I∗, c∗)) P (T|(I, c)) =-v∈V (T |(I,c))π(v) * T∈τ(I,c)
P (T|(I, c)) max{ ¯Π0(T|(I, c), (I∗, c∗)), αT}
= 1 2n
*
T∈TX,T A(I,c)
|SX,TA(T|(I, c))|max4Π¯0X,TA,TP(T|(I, c), (I∗, c∗)), αT5
(I, c) v ∈4v..."RM0((I, c), v) = 0 5 S(I, c)\ SX(I, c) * v|!RM0((I,c),v)=0 π(v)Π((I, c), v|(I∗, c∗)) = 1 2n * v|!RM0((I,c),v)=0 Π((I, c), v|(I∗, c∗)) = 1 2n * β∈S(I,c)\SX(I,c) ΠX,TA,TP(β|(I∗, c∗)) E –truthful X, TA, TP
5.5. CFM E –truthful d X, TA, TP
∀(I, c) ∈ K, ¯ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ ¯ΠX,TA,TP((I, c)|(I∗, c∗)) . CFM E –truthful
X, TA, TP (I, c)
¯
ΠX,TA,TP(((I, c))|(I∗, c∗)) (I, c)
¯
ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ ¯ΠX,TA,TP((I, c)|(I∗, c∗))
CFM obedient ¯ ΠX,TA,TP((I∗, c∗)|(I∗, c∗)) ˜ ΠX,TA,TP((I∗, c∗)|(I∗, c∗)) CFM obedient CFM E –truthful X, TA, TP (I, c) ˜
ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ ¯ΠX,TA,TP(((I, c))|(I∗, c∗)) ¯
ΠX,TA,TP(((I, c))|(I∗, c∗)) max
¯
ΠX,TA,TP(((I, c))|(I∗, c∗)) E –truthful (I, c) ¯ ΠX,TA,TP(((I, c))|(I∗, c∗)) = 1 2n * T∈TX,T A(I,c)
|SX,TA(T|(I, c))|max4Π¯0X,TA,TP(T|(I, c), (I∗, c∗)), αT5
+ 1 2n * β∈S(I,c)\SX(I,c) ΠX,TA,TP(β|(I∗, c∗)) T ZT ZT ZT ≥ ¯ΠX,T A,TP 0 (T|(I, c), (I∗, c∗)), ZT ≥ αT
T ZT ZT ≥ max
4 ¯
ΠX,T0 A,TP(T|(I, c), (I∗, c∗)), αT5
ZT CFM obedient CFM E –truthful
∀(I, c) ∈ K, ˜ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ 1 2n * T∈TX,T A(I,c) |SX,TA(T|(I, c))| 2n ZT + 1 2n * β∈S(I,c)\SX(I,c) ΠX,TA,TP(β|(I∗, c∗)), ∀(I, c) ∈ K, ∀T ∈ TX,TA(I, c), ZT ≥ ¯ΠX,T A,TP 0 (T|(I, c), (I∗, c∗)), ∀(I, c) ∈ K, ∀T ∈ TX,TA(I, c), ZT ≥ αT (K, N , (I∗, c∗), v, α, CFM) CFM ⟨T AP ⟩ ⟨T AP ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ find X, TA s.t. * i∈N taiβ ≥ I∗x0β,∀β ∈ S, nx0β ≥ * i∈N xiβ,∀β ∈ S, X ∈ {0, 1}(n+1)×|S|, TA∈ Rn+×|S|. I∗, c∗ ⟨T AP ⟩ X X TA T A X X TA TA ⟨T P P ⟩
⟨T P P ⟩ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ find TP, Z s.t. * i∈N (taiβ + tpiβ)≥ I∗x0β+ c∗ * i∈N xiβ,∀β ∈ S, ¯ UiX,TA,TP(v∗i|v∗ i)≥ 0 ≥ 0, ∀i ∈ N , ¯ UiX,TA,TP(v∗i|v∗ i)≥ ¯UX,T A,TP i (vi∗c|vi∗),∀i ∈ N , ¯ ΠX,T0 A,TP(T|(I, c), (I∗, c∗))≥ αT, ∀T ∈ TX,TA(I∗, c∗), ˜ ΠX,TA,TP((I∗, c∗)|(I∗, c∗))≥ 1 2n * T∈TX,T A(I,c) |SX,TA(T|(I, c))| 2n ZT + 1 2n * β∈S(I,c)\SX(I,c) ΠX,TA,TP(β|(I∗, c∗)),∀(I, c) ∈ K, ZT ≥ ¯ΠX,T A,TP 0 (T|(I, c), (I∗, c∗)),∀(I, c) ∈ K, ∀T ∈ TX,T A (I, c), ZT ≥ αT, ∀(I, c) ∈ K, ∀T ∈ TX,T A (I, c), TP ∈ Rn×|S| + , ZT ∈ R+,∀(I, c) ∈ K, ∀T ∈ TX,T A (I, c) ⟨T P P ⟩ I∗, c∗, X, TA T = B(I,c)∈KTX,TA(I, c) Z = (Z T)T∈T ⟨T P P ⟩ X, TA ⟨T P P ⟩ TP ⟨T AP ⟩ X, TA X, TA ⟨T P P ⟩ TP ⟨T P P ⟩ ⟨T AP ⟩
6
6.1
Roland CFM CFM (V, N , (I∗, c∗), v) CFM CFM6.2
[8] CFM CFM [9][1] CFM
[1] Bruno F. Laurenco, Tomonari Kitahara, Masakazu Muramatsu and Takashi Tsuchiya:An extension of Chubanov’s algorithm to symmetric cones Mathe-matical Programming,MatheMathe-matical Programming,pp 1–33,2018
[2] Bernard Salanie,( ) , , : ,2005 [3] CAMPFIRE,https://camp-fire.jp/about, 2017 9 27 [4] CAMPFIRE,https://camp-fire.jp/proposals/ readyfor, 2018/7/17 [5] Kickstarter https://www.kickstarter.com/about?ref=global-footer, 2018/12/23 [6] G. , , : ,2015
[7] Hayato Waki,Masakazu Muramatsu:Facial Reduction Algorithms for Conic Optimazation Journal of Optimization Theory and Applications,vol158, pp188–215,2013
[8] Hu Ming,Li Xi, Shi Mengze:Product and pricing decisions in crowdfunding Mar-keting Science,vol3,pp331-345,2015
[9] : , 2001
[10] Roger B.Myerson:Optimal coordination mechanisms in generalized princi-pal–agent problems Mathematical Economics vol10 issue1,pp67-81,1982
[11] Stausz Roland:A Theory of Crowdfunging :Mechanism Design Approach with Dedand Uncertainly and Moral Hazard American Economics Paper vol107 No6, pp.1430-76, 2017
[12] , : . , 2013
[13] US Court Punishes Kickstarter Campaign For Crowdfunding Theft,https:// www.ubergizmo.com/2015/09/us-courts-punish-kickstarter-campaign/,
2018/12/23
[14] Yiannis Giannakopoulos:Duality Theory for Optimal Mechanism Design Doctor of Philosophy,University of Oxford,2015
A
A.1
C ⊆ Rn ∀u, s ∈ C, ∀α ∈ [0, 1], αu + (1 − α)s ∈ C C K ⊆ Rn u∈ K, λ > 0 λu∈ K K 'm∈ Rn ..∀u ∈ K, uTm≥ 0( K∗ K K Rn ++ Rn + Rn+ u ∀s ∈ Rn++, sTu ≥ 0 A.1. C, E ⊆ Rn y ∈ Rn, y ̸= 0 n cTy≤ eTy(c∈ C, e ∈ E) [9]A.2
A ∈ Rm×n m b 2.1 P {s ∈ Rn|As > b, s > 0 n} D {u ∈ Rm|ATu≤ 0 n, bTu≥ 0, u ≥ 0m, u ̸= 0m} P D • P = ∅ =⇒ D ̸= ∅ • D = ∅ =⇒ P ̸= ∅A.1. P = ∅ ∨ D = ∅ . P ̸= ∅ ∧ D ̸= ∅ s∈ P u ∈ D uT(As− b) s∈ P (As− b) > 0m u∈ D u̸= 0m u≥ 0m uT(As− b) > 0 uT(As− b) uT(As− b) = uTAs− uTb = (ATu)Ts− uTb ATu ≤ 0n s > 0n (ATu)Ts ≤ 0 bTu ≥ 0 (ATu)Ts− uTb≤ 0 (ATu)Ts− uTb > 0 A.2. P = ∅ =⇒ D ̸= ∅ . m A = { As − b | s > 0n} P ∃i ∈ [m],-nj=1aijsj ≤ bi ⇐⇒ -j=1n aijsj − bi ≤ 0 . Rm++ = {c ∈ Rm|∀i ∈ [m], c i > 0} A ∩ Rm++ = ∅ y̸= 0m ∀w ∈ A, ∀v ∈ Rm ++, yTw ≤ yTv ∀v ∈ Rm ++, yTv ≥ 0 ∃v ∈ Rm ++, yTv < 0 λ > 0 λyTv < 0 λv∈ Rm ++ λ λyTv ' yTv ..v ∈ Rm + ( yTv ≥ 0 ∀v ∈ Rm ++, yTv ≥ 0 y Rm++ R++m∗ Rm++∗ Rm+ y∈ Rm + ∀w ∈ A, yTw≤ 0 ⇐⇒ ∀s > 0n, yT(As− b) ≤ 0 ⇐⇒ ∀s > 0n, (ATy)Ts≤ yTb (ATy)Ts ≤ 0 ∃s > 0 n, (ATy)Ts > 0 λ (ATy)Tλs λs > 0n ' (ATy)Ts..s > 0n( (ATy)Ts ≤ 0 s > 0n ATy≤ 0n bTy≥ 0 y D
A.3. D = ∅ =⇒ P ̸= ∅
. P = ∅ A.2 D ̸= ∅
