重み付き乱択最適選好マッチング

概要

論文の詳細を見る
人数nのユーザ集合をA,要素数mの商品集合をIとする.ユーザ集合AはA_1,A_2,...,A_kのようにk分割されており,各A_iにはw_1>w_2>…>w_k>Oを満たす重みw_iが割り当てられているものとする.各ユーザに各商品を割り当てる問題-k重み付き商品割り当て問題-を考える.各ユーザx∈Aは商品に対する選好ベクトルを持つ.ユーザxが商品qより商品pを好むとは,選好ベクトルにおいてpが9より上位に位置することであり,任意のマッチングMとM'に対して,M≻_xM'であるとは,ユーザxがM'(x)よりM(x)を好むことを言う.マッチングMがマッチングM'より"選好的である"とは,M≻_xM'を満たすユーザx∈Aの重みの総和がM≻_xM'を満たすユーザy∈Aの重みの総和より大きいことを言い,マッチングMが"最適選好である"とは,Mより選好的であるM'≠Mが存在しないことを言う.Mahdianはk=1の場合,m>1.42nであるならが,商品割り当て問題の乱択入力が高い確率で最適選好的マッチングを持つことを示したが,一般のk≥2に関して,その詳細は未解明であった.本論文では,以下の結果を示す-m=βnを満たす任意βに対して,(下界)β/n^<1/3>=o(1)であるとき,k重み付き商品割り当て問題の乱択入力が確率1-o(1)で最適選好的マッチングを持たない;(上界)n^<1/3>/β=o(1)であるとき,k重み付き商品割り当て問題の乱択入力が確率I-o(1)で最適選好的マッチングを持つ.
2007-06-22

重み付き乱択最適選好マッチング

スポンサーリンク

概要

著者

関連論文

スポンサーリンク