電子情報通信学会総合大会講演要旨
DS-1-4
選択関数付き秘書問題
○河瀬康志(東工大)
古典的秘書問題は,面接者がn人の候補者と順次面接し即座に採否を決定する場合に,
最適な候補者を採用できる確率を最大化する戦略を求める問題である.
本発表では,「選択関数付き秘書問題」を導入する.
ここで,選択関数は候補者の集合に対する選好を表す.
この問題では,複数の候補者を採用し,選択関数によって定まるもっとも良い候補者集合を
採用できる確率(成功確率)を最大化する戦略を求めることを目的とする.
本発表では,選択関数が経路独立性を満たし選択関数の幅(選択されうる最大人数)がkのとき,
成功確率が少なくとも1/ek以上である戦略を与え,その最適性を示す.
さらに,経路独立性を満たさない場合については,選択関数の幅が2であっても,
成功確率がいくらでも小さくなるインスタンスが存在することを示す.