抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
社会的選択設定における連続指示機構の成功によって動機づけられて,著者らは種々の組合せ最適化問題に取り組む際にその有用性を探究した。抽象的モデルを考慮することにより,エージェントのセットが行動順序と呼ばれる特定の順序で作用するように依頼された。各エージェントは,行動順序に先行するエージェントの作用を与えて,最大可能な値を与える方法で作用する。著者らの目標は,エージェント(a.k.a.,社会福祉)にほぼ最適な総値を与える行動シーケンスを計算することである。著者らは,エージェントが順序集合Sにおいてエージェントの後に作用するとき,エージェントiを得る値v_i(S)へのクエリアクセスを仮定した。多項式に多くの質問を用いて達成できる社会福祉に関する厳密な限界を確立した。これらの限界は,一般的に最適社会福祉の僅かな準線形近似を示すが,その評価が基礎となる組合せ領域に由来するとき,優れた近似を得ることができる。評価は,評価が二部マッチング,有向グラフにおけるアーバレッセンス,およびBoole表現の充足可能性を用いて定義されるとき,単純なクエリ効率アルゴリズムが2近似を生成する。真実性に関連する問題を議論し,VCG様支払いを用いて,著者らのアルゴリズムのいくつかを真に実装できる方法を示した。最後に,行動シーケンスによって生成された組合せ最適化ソリューションの品質の楽観的尺度を提供する概念である,シリアルディケータシップの価格を導入し,研究する。【JST・京大機械翻訳】
