1
日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

クラウドソーシングとメカニズムデザイン
松原 繁夫

本稿では，クラウドソーシングを対象としたメカニズムデザイン研究について紹介する．クラウドソーシングは，
Amazon Mechanical Turk の普及などにともない，近年非常に注目を集めている．クラウドソーシングには，必然的に人が含まれるため，そのインセンティブをどう設計するかが課題となる．本稿では，マイクロタスク型クラウド
ソーシングにおけるワーカの特性，タスク割当法，結果集約法について述べ，つぎに，コンペティション型クラウド
ソーシングに関する研究を紹介する．また，DARPA ネットワークチャレンジに関する研究も紹介する．

This paper introduces mechanism design researches for crowdsourcing. Recently, Amazon Mechanical Turk
has become popular and crowdsourcing has got much attention. Crowdsourcing inevitably includes humans
in the process. Thus, how to design incentives is a considerably signiﬁcant problem. This paper shows studies about workers’ proﬁle, task allocation problems, and aggregation methods in micro-task crowdsourcing,
and then shows studies about competition-type crowdsourcing. In addition, we show studies about the
DARPA Network Challenge.

に制御しようという考え方である．

1 はじめに計算機科学や情報技術分野においても，インターメカニズムデザイン研究は 1960 年代にミクロ経済

ネットの発展により，異なる目標や選好を持った異な学やゲーム理論の分野において始まり，現在，計算機る組織が参加する状況を対象とすることが増え，戦略

科学や情報技術と結びついて発展を遂げている．メカ的振る舞いの元での社会選択を議論することの重要性

ニズムデザイン理論は，人，あるいは，エージェントが増している [27]．一方で，システムの大規模化・複が合理的に振る舞う，つまり，自己の効用を最大にす

雑化にともない，メカニズム設計においても計算量のるように振る舞うという仮定の元で，望ましい社会的問題が生じるため，アルゴリズムの開発などの点で，選択を遂行する制度を設計するための方法論を与え経済学分野から計算機科学分野への期待も大きいとるものである．設計者にとって望ましい社会的選択と言える．

は，例えば，オークションの場合には，社会的余剰のさて，これまでのメカニズムデザインの研究対象と最大化や収入最大化の実現などに対応する．ここでのしては，オークションが取り上げられることが多かっ基本的な考え方は，人やエージェントは自らの利益とた．しかし，近年，メカニズムデザインの研究対象となる場合には嘘をつくなど戦略的な行動をとることしてクラウドソーシングが注目を集めつつある．クラもあるとの仮定の元で，人やエージェントの行動を直ウドソーシングという用語は，Jeﬀ Howe の命名によ

接制御しようとするのではなく，適切にゲームの規則るもので [16]，Wikipedia では以下の説明が与えられを設計することで，人やエージェントの行動を間接的ている．
クラウドソーシングは，狭義では不特定多Crowdsourcing and Mechanism Design.
Shigeo Matsubara, 京 都 大 学 大 学 院 情 報 学 研 究 科 社
会 情 報 学 専 攻, Dept. of Social Informatics, Kyoto
University.

数の人に業務を委託するという新しい雇用
形態．ウェブサービスのトレンドの一つでもある．群衆（crowd）と業務委託（sourcing）

日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

2を組み合わせた造語．

る．例えば，2009 年 12 月に，DARPA（国防総省国

アウトソーシングという用語はかなり普及している

防高等研究事業局）ネットワークチャレンジが実施さと思われるが，アウトソーシングが特定の人，組織にれた [5]．これは，米国内の秘密の場所 10 か所に係留業務を委託するのに対し，クラウドソーシングでは不された気象用風船を，いかに早く見つけるかという特定多数に業務を委託する点に特徴がある．最近は課題であった．そこで求められたのは，各地域に散らクラウドソーシングという用語も認知を得つつある

ばった潜在的なボランティアを集めて，効率的な問題

が，クラウドコンピューティングと混同される場合も解決を可能とする大規模チームを形成することであっある．クラウドコンピューティングのクラウドは雲をた．この実験では，MIT チームが 9 時間かからず 10意味するのに対し，クラウドソーシングのクラウドは個の気球を見つけることに成功し，優勝した [29]．

群衆の意味であるので注意されたい．

MIT チームは，再帰的なインセンティブスキーム

クラウドソーシングが注目を集めているのは，Ama-

を通して，多くのボランティアに参加するよう動機

zon Mechanical Turk (MTurk) の出現によるところづけた．例えば，A が B をチームに誘い，B が C をが大きい．Mechanical Turk は，元々は社内のタスクチームに誘い，C が D をチームに誘い，D が 1 個の処理用に開発されたものであるが，2005 年に外部に風船を見つけた場合，D に$2,000，C に$1,000，B に公開され，Human Intelligence Tasks (HITs) と呼ば$500，A に$250 を支払うというものである．これは，れるマイクロタスクの主要な取引市場となっている．

正に MIT チームはメカニズムデザインの問題を解いそこでは，Web ページの分類，録音データの書き起ていたことを意味する．

こし，検索結果の妥当性検証などのタスクが 1 件数

以下，2 章では，タスクという側面から見たクラウ

セント程度で取引されている．これらのタスクの多く

ドソーシングの分類を紹介し，本稿で議論する範囲を

は，計算機で自動化するのは困難であるが，人にとっ明確にする．3 章では，組織ではなく，個々のワーカては比較的簡単に処理できるという特徴を持つものの動機づけに関する研究を紹介する．4 章では，ワーである．

カへのタスクの割当て問題を議論する．タスク依頼者

これは人工知能研究の新しい形であるとも言える．

はワーカの正確なスキル水準を知らないという点で，従来の人工知能研究は人の知的活動のモデルを計算機

従来のタスク割当て問題と性質が異なる．また，クラの上で実現しようとしてきた．それに対し，クラウド

ウドソーシングでは，同じ問題を複数のワーカに与ソーシングでは，非専門家による単純な作業を組み合え，結果を統合することで品質の改善を図る場合が多わせて複雑なタスクを実行することを考え，組み合わい．そこで，に 5 章では，意見集約法に関する研究

せ方の知識を計算機に持たせようとするものである．

を紹介する．6 章では，コンペティション型クラウド

また、メカニズムデザイン研究という視点で見れば，ソーシングに関する研究を紹介する．コンペティショ

これまでオークションなどでは設計したメカニズム

ン型もマイクロタスク型と並んで，現行のクラウドを実際に人を使って性能検証することは難しかった．

ソーシングの主要な形態である．7 章では，将来のク

それに対し，クラウドソーシングでは高々数ドルで実ラウドソーシングとして，DARPA ネットワークチャ

際に性能検証が行える．この点が，多くの研究者が興レンジの問題に再度焦点を当て，関連する研究を紹介

味を持つ理由となっていると考えられる．

する．最後に 8 章を結びとする．

さて，後述するように，MTurk においてはインド
人のワーカが多い．よって，Web ページの分類や画

2 クラウドソーシングの分類

像へのタグ付けといった単純なタスクを，安価な労働

本章では，本稿で議論の対象とする範囲について明力を使って処理しているだけと見る読者もいるかもし確にする．クラウドソーシングの分類・定義に関してれない．しかし，クラウドソーシングを対象にしたメは様々な議論がある [8] [11] [9] [1]．例えば，Wikipedia

カニズムデザイン研究はより広がりのあるものであをクラウドソーシングの一つと考える立場もあれば，

日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集3

クラウドソーシングに該当しないと見る立場もある．

まず，MTurk のような取引市場にワーカとして登録

金銭の授受が行われるか，また，タスク依頼者とワーするかどうか，(2) 複数のタスクがある中でどのタスカという明確な関係が存在するかなど，様々な分類軸

クを選択するか，(3) あるタスクを選択した後，どのが考えられる．

程度の労力を投入するか，といった様々な点に影響を

まず，本稿では，金銭の授受が行われる場面を議論与える．インセンティブ設計においては，外因的インの対象とする．これは，後述するように，タスク自体

センティブ（金銭的報酬や仮想的なポイントなど）との面白さやタスクの社会的意義が，ワーカの振る舞い

内因的インセンティブ（タスク自体の面白さ，他者とに影響しないと言うことではない．それらはインセン交流への欲求など）をどううまく組み合わせるか，まティブ設計において重要な要素である．しかし，メカた各々をどの程度与えるかを検討することが必要であ

ニズムを設計するとした際に，金銭報酬額に比べて，る．また，メカニズムデザイン的視点からは，インセ

タスクの面白さや社会的意義などを任意の水準に設定

ンティブシステムが，ワーカの戦略的操作からどの程することは難しい．また，画像のタグ付けや録音デー

度頑健であるかを確認する必要がある．

タの書き起こしなどは，その便益がもっぱらタスク依メカニズムデザイン手法を適用する上で，まず頼者に属するため，無報酬ではワーカの参加を得るこは個々のワーカの性質，つまり，どのような効用関とが難しい．このようなタスクも多く存在するため，数を持つかを知ることが重要である [31]．Ross らは金銭授受が行われる場面を議論の対象とする．

MTurk におけるワーカの人口分布を調査している．

さて，金銭授受をともなうクラウドソーシングもいやや古く 2009 年 11 月時点での調査であるが，米国がくつかに分類できる（例えば， [19] などを参照）．本

56%，インドが 36%，英国，カナダなどその他の国が稿では，マイクロタスク型とコンペティション型を取8%となっている．インドのワーカが多いことが特徴

り上げる．マイクロタスク型は，上述のように Webである．ワーカが MTurk から得る年間の報酬額は，ページの分類は画像のタグ付けなど，数分程度で処理$10,000 以下の区間が多く 32%，$10,000-$20,000 ができるタスクである．MTurk で取り引きされるタス

14%，$20,000-$30,000 が 12%といった数値になってクの多くはマイクロタスク型であり，画像へのタグ付

いる．年間$10,000 の報酬を得ようとすれば，週当た

けタスクなどは 1 件数セント程度の報酬である．定り$200 分程度のタスクを処理することになる．また，

額報酬のものが多いが，アンケートに回答するなど付

米国のワーカの年収は，$10,000 から$70,000 程度ま加的な作業をした場合にボーナスを支払うといった設で均等に近い形で分散しているのに対し，インドの定がなされる場合もある．

ワーカの年収は$10,000 以下が 64%と非常に多い．こコンペティション型は T シャツのデザインやロゴのことから，米国のワーカは暇つぶしといった参加動のデザインなどクリエイティブなタスクに対して用い機が多く，インドのワーカは生活の糧を得るといったられるものである．報酬額も数百ドルなど大きくなる

参加動機が多いと推察される．

が，一方で，デザインが採用された 1 ワーカしか報酬

国によって賃金水準が異なるが，米国のワーカとイが得られない設定となっていることが多い．どのデザ

ンドのワーカが混合した状態にあることが，MTurkインを採用するかは，依頼者自身が決定する場合もあの一つの特徴と言える．では，ワーカの振る舞いにれば，閲覧者の投票等により決定される場合もある．

ついて，もう少し詳しく見てみよう．Horton らは，ワーカの留保賃金を計測する方法を提案している [15]．

3 ワーカの特性

留保賃金とは，ワーカがタスクをする／しないの境とクラウドソーシングには必然的にワーカが含まれなる報酬額はいくらかということである．Horton らる．タスク依頼者にとって望ましい結果を得るには，の採った方法は単純なもので，報酬額を少しずつ減額

タスク内容の指示とともに，どのようにインセンティ

していき，どこでタスクを継続することを止めるをブを与えるかが課題となる．インセンティブは，(1)

観察するという方法である．それをタスクの難易度，

日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集4

つまり，タスク処理にどれくらい時間を要するかを変る．また，外因性動機づけよりも内因性動機づけの方化させ，各場合における留保価格を計測した．中央値

が強い刺激になると報告している．

は時間当たり$1.38 であった．

また，Shaw らは経済的インセンティブと社会的イ

さらに結果を分析することで，(1) 報酬額が減れば，ンセンティブの影響を調査している [32]．例えば，事ワーカが働く時間は短くなる，(2) タスクがどれくら

後に回答の正確さが評価されますといった一文をタスい時間を要するかは，ワーカが働く時間に影響を与クの指示内容に付加したり，このタスクを担当してく

えない，ということ知見を得た．前者は予測されたこ

ださり感謝しますといった一文を付加することでワーとであるが，後者は経済学における合理的モデルかカの振る舞いに変化が生じるかを調べている．その結らはうまく説明できない．ワーカが合理的であれば，果は，結果が他者と不一致であれば報酬を減額するとタスク処理に時間がかかれば，タスクを継続して処いった経済的インセンティブの操作は回答の正確さの理しないはずである．この結果を元に，Horton らは，向上に寄与したが，社会的インセンティブは統制条件

MTurk において target earner が存在すると結論づと比べて有意な差が確認されなかったというものでけている，つまり，一日に稼ぐ目標を決めており，そある．

の額に達すれば働くことを止めるワーカが存在するということである．

Shaw らは経済的インセンティブの影響を調査した
ものの，初期報酬額やボーナス・ペナルティ額の設定

つぎに興味が持たれる点は，作業量ではなく作業の法については明確な指針を与えていない．王らは，不質である．Mason らは報酬額を上げることで，作業

誠実ワーカの参加を防ぐことを目的として，成果報

品質が向上するかどうかを調べた [23]．画像を時間順

酬方式を用いた報酬設定法を提案している [35]．クラに並べ替えるタスクや，パズルを解くタスクを用いウドソーシングにおける効率的なタスク解決の実現て，報酬額を変えてワーカの振る舞いが観察された．

には，不誠実ワーカの影響排除が必要である．これまその結果は，報酬額を上げると，ワーカがそのタスクで，機械学習手法を用いた，不誠実ワーカの結果へのを選択するよう動機づけられ，また，タスクの処理速影響を排除する方法が提案されている．しかし，事後度を向上させるが，一方で，作業品質自体は向上しなの対処ではなく事前に不誠実ワーカの参加を防げれいというものであった．この実験では，報酬は作業品

ば，より効率的なタスク解決が可能になると考えら質に条件づけられておらず，特に報酬額と作業品質にれる．MTurk 上での実験では，固定報酬方式に比べ因果関係が存在しないため，当然の結果と考えることて成果報酬方式が不誠実ワーカの参加を防ぐのに有もできる．

効であることを示しているが，結果の予測精度はまさて，上述のように，インセンティブは報酬によだ十分ではない．興味深い結果の一つは，初期報酬をるものだけではない．Rogstadius らは，内因性動機0 とするよりも，小額の報酬を与える方が不誠実ワーと外因性動機がワーカに与える影響を評価しているカの参加を防ぐ効果が高いことである．初期報酬が 0[30]．タスクは画像中の血球の数とマラリアに感染しの場合，かえってワーカはタスク依頼者が報酬 0 でた血球の数を数えるタスクである．内因性動機に関仕事をさせることはないと考える，といった理由の存しては，NPO 団体が人命救助のためにこのタスクを

在が考えられる．

行っているという記事をワーカに読ませた場合と，あ実験に用いているタスクが異なるため，各研究間る営利目的の製薬企業がこのタスクを行っているといの単純な比較は難しいが，様々なインセンティブのう記事を読ませた場合を比較している．タスクに対組合せに関する実験を非常に安価に行えるところがする社会的意義が強調される場合とされない場合でMTurk の利点と言える．ただし，報酬に対する反応ある．実験結果は，内因性動機づけにより，つまり，などは，実験経済学や社会心理学においても多くの知NPO 団体のための作業という文脈を与えることによ見が蓄積されている．実験が安価に行えるからといっり，より正確な作業結果が得られることを示していて，既存の知見を再確認するだけの実験とならないよ日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集
う注意が必要である．

5

依頼者にとって各ワーカのスキルが既知であり，かつ，ワーカが同時に存在している場合には，よく知ら4 タスク割当法

れた割当問題として定式化でき，ハンガリー法など既本章では，タスク割当てに関する研究について紹介

存のアルゴリズムを用いて解くことができる．これする．分類タスクにおいては，一人のワーカに依頼しに対し，ワーカが逐次現われる場合，つまりオンライ

た場合，ワーカが真面目に作業をしたとしても，分類

ン版の問題においては，ワーカのスキル分布はわかっを間違える場合がある．よって，1 つの分類問題を複ているとしても，高スキルワーカがいつ現われるか，

数のワーカに与え，得られた結果を統合することでよ

計何人現われるかはわからない．そのため，最初に低り高精度な解が得られると期待される．結果の統合

スキルワーカが現われた場合に低難度のタスクを割法に関しては次章で詳しく述べるが，例えば多数決

り当てるのか，中難度のタスクを割り当てるのかとを用いることが考えられる．ここで問題となるのは，

いったことを決定しなければならない．この問題は，

1 つのタスクに複数ワーカを割り当てれば，解の推定

オンラインアドワーズ問題として知られる問題と同精度を向上させることができるが，一方で，より多くじになる [6]．オンラインアドワーズ問題とは，検索のワーカに依頼すれば費用が増大する．よって，推定

連動広告オークションにおいて，様々な検索キーワー

精度の向上と費用抑制をどう両立させるかが課題とドが逐次現われるときに，各キーワードに対する入札なる．

額を決定する問題である．Devanur らは，期間を前

2 値の分類タスク，例えば Web ページが男性向け

半と後半の 2 つに分け，前半でキーワードの出現分布

か女性向けかを判断するといったタスクに対して，最を学習し，後半でその情報を元に最適な入札額を決

初に 5 人のワーカに尋ねると決めれば，途中経過に定する方法を提案している．これは，探索（explore）

関わらず 5 人のワーカに尋ねることが多い．この状と活用（exploit）を組み合わせたものとなっている．

況に対し Parameswaran らは，例えば，男性向けに

Ho らの問題設定では，さらにワーカのスキルも最

2 票，女性向けに 1 票入った時点で，男性向けと判断

初は不明としている．この問題に対して，まずオフラ

するか，女性向けと判断するか，つぎのワーカに尋ね

イン版に関して線形計画問題として定式化し，その双るかを動的に制御する方法を提案している[28]．こ対問題を解き，Devanur らの方法と同じく期間を前

れは，各時点において，当該ページを男性向けと判断

半と後半に分け，前半をスキル分布の学習およびワーした場合の推定誤差，女性向けと判断した場合の推定

カのスキル推定に用い，後半では，獲得した情報を元誤差を計算することで，推定誤差が要求値以内に収まに，タスク依頼者が得る利益が最大となるように，逐るようにフローを制御している．Tran-Thanh らは，

次現われるワーカにタスクを割り当てる方法を提案

異なる種類のタスクが含まれ，その処理費用が異なる

している．

場合に議論を拡張し，さらに推測誤差における上限を求めている [34]．

なお，上述の研究においては，ワーカの選好や戦略的行動についてはまだ考慮されていない．それに対さて，分類タスク以外にも，タスクの割当て方が課

し，Singer らは，オンラインでワーカが到着する場

題となる場合がある．それは，ワーカのスキルが異な合に，価格設定とタスク割当てを自動化する方法を提り，かつ，高スキルのワーカにすべてのタスクを依頼案している [33]．タスク依頼者がタスクの完了期限をすることができない場合である．難易度の高いタスク

課し，ある知られた分布に従い到着するワーカがタスを低スキルワーカに，難易度の低いタスクを高スキル

ク処理に要する費用や数を虚偽申告する可能性があワーカに割り当てるようなことをすれば，全体のタスるとの仮定の元で，タスク依頼者の予算制約の元ででク処理性能が低下することは明らかであろう．

きるだけ多くのタスクを処理し，支払いを最小化する

Ho らは，ワーカのタスク割当て問題をオンライン
タスク割当て問題として定式化している [14]．タスク

誘因両立なメカニズムを提案している．
また，松原らは，複数タスク割当問題に対して，タ日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

6

スク依頼者がワーカ全体の選好分布を知っているが，

しかし，Ghosh らは，依頼者が一人の良いワーカを

ワーカ個々の選好は知らないとの仮定の元で，タスク

存在し，そのワーカが 50%以上の精度で評価付けを選好に関するワーカの虚偽申告を防ぐメカニズムをすることを知っていれば，評価されるコンテンツが増提案している [24]．

えるに従い，推定誤差が 0 に収束することを示している．ここでは，コンテンツを，多段階ではなく，が5 結果集約法

良い／悪いの 2 クラスへの分類を要求する点が問題

本章では，複数のワーカから得られた結果を集約すを単純にしている．提案方法は，悪意のあるワーカにる際に生じる課題とその解法について述べる．上述

よる戦略的操作に対して頑健であることが示されてのように，クラウドソーシングの特徴の一つとして，いる．戦略的操作とは，コンテンツの評価を故意に変

不特定多数のワーカにタスクを依頼する点がある．こ化させようとして，真の評価とは異なる評価を報告す

れは，タスク依頼者にとって個々のワーカのスキルをることである．しかし，つねに真の評価とは異なる評

確認できない，あるいは，ワーカが誠実にタスク処理

価を報告するワーカがいたとすれば，そのワーカの報を行っているか確認できない，といったことが生じ，

告は評価決定に有益である．なぜなら，そのワーカの結果の作業結果の品質保証が難しくなる．この問題に報告をつねに反転させて評価に組み込めば良いから

対し，結果の信頼性を保証するために，複数のワーカである．よって，悪意のあるワーカにとって，できるに同じタスクを依頼し，その結果を統合することがよ

最善のことはランダムに評価を報告することとなる．

く行われている．

結果，最終評価には影響を及ぼせないことになる．こ

現在，よく用いられるのは単純多数決であるが，れが実現できるのも，一人の良いワーカの存在を知っ

Mao らは投票方式の選択について議論している [22]．

ていて，そこを起点に各ワーカの精度を評価できるか

ワーカの判断に不確かさが存在することに鑑み，ノイらである．

ズが含まれたデータから正しいランキングを推定できるかという課題を設定し，単純多数決，ボルダ法，

6 コンテスト

Maxmin 法，Kemeny 法，Thurstone モデルを比較

本章では，コンペティション型クラウドソーシング，

している．Condorcet モデルと Thurstone-Mosteller

いわゆるコンテストに関する研究を概観する．コンモデルという 2 つのノイズに関する理論モデルの上テストは，all-pay オークションと見ることができる．

で検証したところ，推定性能で優れているのはボルダ

All-pay オークションとは，勝敗に関わらず，入札者法であった．しかし，MTurk 上での実験では，ボル全員が自己の申告額を支払うオークション方式であダ法は推定誤りが多く，単純多数決が比較的良い性能

る．コンテストにおいては，上位のワーカには報酬がを示した．これは，理論的なノイズモデルが，現実を与えられるが，それ以外のワーカには報酬が与えられうまく捨象できていないことを意味する．Mao らは，ない．タスク処理には何らかの費用が発生するため，理論が役に立たないというのではなく，クラウドソー

下位のワーカはその費用を回収できないことになる．

シングにおける投票の研究は始まったばかりであり，

この点で，コンテストでは all-pay オークションが行

理論と現実のギャップを埋めていくことが必要とまとわれていると見ることができる [7]．

めている．

さて，報酬総額は変えないとして，一位のワーカだ

Ghosh らは，コンテンツの良否を閲覧者が評価付けに報酬を与える方が良いのか，二位のワーカにもけして決定する状況を扱っている [12]．タスク依頼者

報酬を与える方が良いのか，メカニズム設計においにとっては，コンテンツの品質も不明であるし，ワーて興味が持たれる点である．後者の場合，一位となっ

カの品質も不明な状態である．ワーカに関して何の情た場合の報酬額が減るため，ワーカは努力水準を下げ

報もなければ，ランダムに意思決定する以上に精度よるかもしれない．一方，二位のワーカにも報酬が与えくコンテンツの良否を判断することは不可能である．

られるとなれば，より多くのワーカの参加を得るこ日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

7とができ，全体として多くの成果物が得られるかも物の和で表される場合は変化しない．一方，結託が生しれない．この問題に対し，Moldovanu らは，依頼

じると，結託外のワーカから結託内のワーカに効用を者の効用が成果物の総和によって規定される場合に，移転させることになる．また，結託が社会的余剰を増どのように報酬を設定すれば良いかを議論している

加させる場合があることを示している．

[25]．これは，例えば，旅行プランを作成する場合な

Gao らは，成果物の品質（最適解の品質）だけをど，部分と部分を組み合わせてより良いプランを作成問題にするのではなく，同時に分散を小さくすること可能な場合に相当する．ワーカの費用関数が投入労力を目的として，どのようかコンテスト形式が良いかをに関して線形，あるいは，凹関数で表されるときは，議論している [10]．報酬総額が同一という前提のもと一位のワーカにのみ報酬を与えるのがタスク依頼者

で，以下のコンテスト方式が比較されている．

にとって良く，一方，ワーカの費用関数が凸関数で表• 2 ワーカを集めて，勝者のみが報酬を獲得

わされるときは，一位だけでなく，二位以下にも報酬• 4 ワーカを集めて，勝者のみが報酬を獲得を与える設定とすることが依頼者にとって良いことを• 4 ワーカを集めて，2 つのコンテストを実施．報示している．一方，文献 [26] では，依頼者の効用が成酬額は 2 つのコンテストで差を付ける

果物の中で最大の品質水準によって規定される場合に• 4 ワーカを集めて，まず 2 ワーカずつでコンテスついて議論している．これは，例えば，ロゴデザイン

トを行い，勝者に報酬を与える．さらに勝者同士など，複数のデザインを組み合わせて使用するといっでコンテストを行い，その勝者に報酬を与える．

たことが難しい場合に相当する．

理論的解析においては，依頼者の期待効用のみを考え

また，DiPalantino らは，複数の難易度の異なるタ

れば方法 1 が優れており，期待効用と分散の両方を考スクが存在し，ワーカのスキルも異なる場合に，ワー慮する場合には方法 3 と方法 4 が優れることを示し

カがどのようにタスクを選択するかを解析し，依頼者ている．ただし，MTurk 上での実験では理論予測とにとって最適な結果を与える報酬設定法を提案してい一部異なる結果が得られており，方法１よりも方法 2

る [7]．そして，Taskcnċom というクラウドソーシンが優れるという毛ｋｋが得られている．

グサイトのデータを用いて，提案モデルの妥当性を検証している．

さて，多くの研究では，ワーカの参加が外因的である，つまり，参加するかしないかは戦略空間外にある

さて，上述の研究は決定論的モデルを仮定していと仮定して議論している．しかし，コンテストに参加る．つまり，参加者のスキルが決まっていて，投入す

して個人合理性を満たすことが難しい場合には，ワーる労力によって，成果物の品質が定まると仮定していカはコンテストに参加しないであろう．この参加が内る．それに対し，Cavallo らは，成果物の産出過程に因的である場合のコンテストを，Ghosh らは議論し不確実性がある場合を扱っている [2]．この場合，一ている [13]．ここでの興味は，自由参加，つまりワー位のワーカに全ての報酬を与えるのではなく，少しでカの意思に任せるのが良いか，あるいは，コンテスト

も貢献があったワーカには報酬を配分するメカニズム

参加に補助金を与えるのが良いかという判断である．

が効率的となることを示している．

後者は，参加すること自体に報酬を支払うため，多く

Lev らは，コンテストにおいて，参加者同士が協力のワーカが参加するようになるが，コンテスト勝者へする場合について議論している [21]．協力の形態の一の報酬は，その分減じられることになる．分析の結果

つは合併（merger）であり，これは他の参加者からは，参加に対して課税する，つまり，コンテスト参加

誰と誰が協力しているかを観察できる場合である．もに対してワーカに課金し，それをコンテストの勝者へ

う一つの形態は結託（collusion）であり，これは他のの報酬額に含めるという方法が，依頼者にとって最善

ワーカから誰と誰が協力しているかを観測できないとなることを示している．

場合である．合併の場合は参加者の期待効用は変化せず，また，依頼者の効用についても，各ワーカの成果

日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

8を防ぐ報酬設定法を提案している [4]．

7 DARPA ネットワークチャレンジ
本章では，1 章で触れた，DARPA ネットワーク

8 むすびチャレンジの課題を再訪したい．この問題は，ソー

本稿では，近年注目を集めているクラウドソーシン

シャルネットワークの存在の元で，ある情報を持った

グを取り上げ，そこに存在するメカニズムデザインの者（DARPA ネットワークチャレンジでは風船の位

課題や研究を紹介した．多くの研究では，ワーカの振置を知っている者）に到達するために，問い合わせ

る舞いを予測する理論モデルを構築した後で，実際にをどう伝播させれば良いかというものである．よりMTurk などで実験を行ってデータを収集し，理論と具体的には，どのように報酬設定すれば，短時間で現実のギャップを埋めるというアプローチを採ってい

低費用で目的を達成できるかという問題である．

る．理論予測と整合しない結果が得られている研究もKleinberg らの研究は本課題に対する先駆的な研究でいくつかあるが，それは，ワーカの振る舞いにおけるあり，固定報酬契約というインセンティブメカニズム

バイアスなどをより深く知る機会が与えられているを考察している [18]．これは，例えば，風船を発見しと見ることができる．また，MTurk などで実験を行た場合に$2,000 の報酬を与えるとして，ネットワー

う際には，どのようなタスクを設定するかで結果が変ク上のある節点 A が節点 B を勧誘し，つぎに，節点化する可能性がある．この点では，まだアートというB がこの申し入れを受け入れれば，節点 B は報酬の側面もあるが，評価タスクの整理など今後行われてい一部，例えば，$1,500 を報酬額として節点 C に問い

くと考えられる．

合わせネットワークへの参加を勧誘するといった方法

また，2 章で述べたように，本稿では MTurk などである．この固定報酬契約の元では，ネットワークの

金銭報酬のあるクラウドソーシングに関する研究を主

分岐係数（幅優先探索で遭遇する新たな節点の平均に取り上げた．しかし，ESP ゲームなど，金銭報酬で数）の値が 2 のところで相転移し，2 以上であれば低はなく，ゲームの面白さを主な参加動機とする Game

費用で目的の節点を発見できるが，2 より小さければwith a purpose (GWAP) なども興味深い．GWAP

費用が指数的に爆発することを示している．

に関するインセンティブ設計については，文献 [20] なCebrian らは，分割契約方式を提案している [3]．こどを参照されたい．

れは，優勝した MIT チームが採用した戦略と同じで最後に，クラウドソーシングは，複雑なタスクを世ある．目的とする情報を持った者に所定の報酬を支払

界各地に分散した労働力を使って処理するという点

い，その者に到達する情報を提供したもの，つまり，で，生産性や社会の流動性を大きく改善する機会を与問い合わせネットワークに勧誘した者に少し少ない報えると言える．一方で，ワーカの側から見て，不当に酬額を支払い，というように順次遡っていく方法であ安い報酬で単純な作業に従事させれるという批判もる．この方法では，分岐係数が 2 より小さい場合である．文献 [17] では，研究者らが自分たちの子供をクも，低費用で目的の節点を発見できることを示してラウドという仕事環境で働かせたいと考えられるよいる．

うになるには，どのような課題があるかを議論していただし，分割契約方式には固定報酬契約にない問題

る．議論が尽くせているとは言えないが，計算機科学がある．それは，根節点が目的節点に至る経路に存在的な手法だけでなく，社会に与える影響も考えて議論する節点は，架空の節点を入れることで付加的な報酬

していくことが求められる．

を得られるという点である．節点 A が，自己の架空

謝辞 本研究は，日本学術振興会科学研究費基盤研名義である節点 A’ を作りだし，節点 A が節点 A’ を究 (S) (24220002, 平成 24 年度〜28 年度) の補助を勧誘し，節点 A’ が節点 B を勧誘とした場合，外部か受けた．

らは節点 A と節点 A’ が同一かどうか判断できない．
この問題に対して，Chen らは，架空名義節点の挿入

日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集
参 考 文 献[ 1 ] Brabham, D. C.: Crowdsourcing, The MIT
Press, 2013.
[ 2 ] Cavallo, R. and Jain, S.: Eﬃcient crowdsourcing contests, Proceedings of the 11th International
Conference on Autonomous Agents and Multiagent
Systems (AAMAS’12), 2012, pp. 677–686.
[ 3 ] Cebrian, M., Coviello, L., Vattani, A., and Voulgaris, P.: Finding red balloons with split contracts:
robustness to individuals’ selﬁshness (STOC’12),
Proceedings of the 44th symposium on Theory ofComputing, 2012, pp. 775–788.
[ 4 ] Chen, W., Wang, Y., Yu, D., and Zhang,
L.: Sybil-proof mechanisms in query incentive networks, Proceedings of the fourteenth ACM conference on Electronic commerce (EC’13), 2013,
pp. 197–214.
[ 5 ] DARPA: DARPA network challenge, http://archive.darpa.mil/networkchallenge/, 2009.
[ 6 ] Devanur, N. R. and Hayes, T. P.: The adwords
problem: online keyword matching with budgetedbidders under random permutations, Proceedings ofthe 10th ACM conference on Electronic commerce(EC’10), 2009, pp. 71–78.
[ 7 ] DiPalantino, D. and Vojnovic, M.: Crowdsourcing and all-pay auctions, Proceedings of the 10th
ACM conference on Electronic commerce (EC’09),
2009, pp. 119–128.
[ 8 ] Doan, A., Ramakrishnan, R., and Halevy, A. Y.:
Crowdsourcing systems on the World-Wide Web,
Communications of ACM, Vol. 54, No. 4(2011),
pp. 86–96.
[ 9 ] Estellés-Arolas, E. and González-Ladrón-DeGuevara, F.: Towards an integrated crowdsourcing
deﬁnition, Journal of Information Science, Vol. 38,
No. 2(2012), pp. 189–200.
[10] Gao, X. A., Bachrach, Y., Key, P., and Graepel, T.: Quality Expectation-Variance Tradeoﬀs
in Crowdsourcing Contests, Proceedings of theTwenty-Sixth AAAI Conference on Artificial Intelligence (AAAI’12), 2012.
[11] Geiger, D., Seedorf, S., Schulze, T., Nickerson,
R. C., and Schader, M.: Managing the Crowd:
Towards a Taxonomy of Crowdsourcing Processes,
17th Americas Conference on Information Systems(AMCIS’11), 2011.
[12] Ghosh, A., Kale, S., and McAfee, P.: Who moderates the moderators?: crowdsourcing abuse detection in user-generated content, Proceedings ofthe 12th ACM conference on Electronic commerce(EC’11), 2011, pp. 167–176.
[13] Ghosh, A. and McAfee, P.: Crowdsourcing withendogenous entry, Proceedings of the 21st international conference on World Wide Web (WWW’12),
2012, pp. 999–1008.
[14] Ho, C.-J. and Vaughan, J. W.: Online Task Assignment in Crowdsourcing Markets, Proceedings of
the Twenty-Sixth AAAI Conference on Artificial

9Intelligence (AAAI’12), 2012.
[15] Horton, J. J. and Chilton, L. B.: The labor
economics of paid crowdsourcing, Proceedings ofthe 11th ACM conference on Electronic commerce(EC’10), 2010, pp. 209–218.
[16] Howe, J.: Crowdsourcing: Why the Power of the
Crowd Is Driving the Future of Business, Crown
Publishing Group, 2008.
[17] Kittur, A., Nickerson, J. V., Bernstein, M., Gerber, E., Shaw, A., Zimmerman, J., Lease, M., andHorton, J.: The future of crowd work, Proceedingsof the 2013 conference on Computer supported cooperative work (CSCW’13), 2013, pp. 1301–1318.
[18] Kleinberg, J. and Raghavan, P.: Query Incentive
Networks, Proceedings of the 46th Annual IEEE
Symposium on Foundations of Computer Science(FOCS’05), 2005, pp. 132–141.
[19] クラウドソーシングジャパン: クラウドソーシン
グ の 主 な 取 引 方 法, http://crowdsourcing.jpn.com/
crowdsourcing/, 2013.
[20] Law, E. and von Ahn, L.: Human Computation (Synthesis Lectures on Artificial Intelligenceand Machine Learning), Morgan & Claypool Publishers, 2011.
[21] Lev, O., Polukarov, M., Bachrach, Y., andRosenschein, J. S.: Mergers and collusion in allpay auctions and crowdsourcing contests, Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems (AAMAS’13), 2013, pp. 675–682.
[22] Mao, A., Procaccia, A. D., and Chen, Y.: Better Human Computation Through Principled Voting, In the 27th AAAI Conference on Artificial Intelligence (AAAI’13), 2013.
[23] Mason, W. and Watts, D. J.: Financial incentives and the ”performance of crowds”, SIGKDD
Explor. Newsl., Vol. 11, No. 2(2010), pp. 100–108.
[24] 松原繁夫, 水島拓也: クラウドソーシングにおける複数タスク割当て, 2013 年度人工知能学会全国大会（第27 回）予稿集, 2013. 3M4-OS-07e-3.
[25] Moldovanu, B. and Sela, A.: The Optimal Allocation of Prizes in Contests, The American Economic Review, Vol. 91, No. 3(2001), pp. 542–558.
[26] Moldovanu, B. and Sela, A.: Contest architecture, Journal of Economic Theory, Vol. 126,
No. 1(2006), pp. 70–96.
[27] Nisan, N.: Introduction to Mechanism Design(for Computer Scientists), Algorithmic Game Theory, Nisan, N., Roughgarden, T., Tardos, É., andVazirani, V. V.(eds.), Cambridge University Press,
2007.
[28] Parameswaran, A. G., Garcia-Molina, H., Park,
H., Polyzotis, N., Ramesh, A., and Widom, J.:
CrowdScreen: algorithms for ﬁltering data withhumans, Proceedings of the 2012 ACM SIGMODInternational Conference on Management of Data
(SIGMOD’12), 2012, pp. 361–372.
[29] Pickard, G., Rahwan, I., Pan, W., Cebrian,

10

日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

M., Crane, R., Madan, A., and Pentland, A.:
Time Critical Social Mobilization: The DARPA
Network Challenge Winning Strategy, Science,Vol. 334(2011), pp. 509–512.
[30] Rogstadius, J., Kostakos, V., Kittur, A., Smus,
B., Laredo, J., and Vukovic, M.: An Assessmentof Intrinsic and Extrinsic Motivation on Task Performance in Crowdsourcing Markets, Proceedings ofthe Fifth International AAAI Conference on Weblogs and Social Media(ICWSM’11), 2011.
[31] Ross, J., Irani, L., Silberman, M. S., Zaldivar,
A., and Tomlinson, B.: Who are the crowdworkers?:
shifting demographics in mechanical turk, CHI ’10
Extended Abstracts on Human Factors in Computing Systems (CHI EA’10), 2010, pp. 2863–2872.
[32] Shaw, A. D., Horton, J. J., and Chen, D. L.: Designing incentives for inexpert human raters, Pro-

ceedings of the ACM 2011 conference on Computer supported cooperative work (CSCW’11), 2011,
pp. 275–284.
[33] Singer, Y. and Mittal, M.: Pricing mechanisms for crowdsourcing markets, Proceedings of the
22nd international conference on World Wide Web(WWW’13), 2013, pp. 1157–1166.
[34] Tran-Thanh, L., Venanzi, M., Rogers, A., andJennings, N. R.: Eﬃcient budget allocation withaccuracy guarantees for crowdsourcing classiﬁcation
tasks, Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems (AAMAS’13), 2013, pp. 901–908.
[35] 王美楽, 松原繁夫: クラウドソーシングにおける不誠
実ワーカーの排除に向けた報酬設定法の提案, 合同エージェントワークショップ＆シンポジウム (JAWS2012),2012.