抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
著者らは,パレート最適性(PO)と共に,1つの良い(EF1)と1つの良い(EQ1)までの公平性の人気のある公平性の概念を用いて,付加的評価を有するエージェントに対する一連の不可視商品の公正で効率的な割当ての問題を研究した。EF1+PO割当を計算する擬似多項式時間アルゴリズムが存在し,EF1と分数パレート最適(fPO)の両方である割当ての存在の非構成証明は,POよりも強い概念である。EF1+fPO割当てを計算する擬似多項式時間アルゴリズムを提示し,その結果,以前の結果を改善した。また,この技法は,EQ1+fPO割当が,値が正であり,それが擬似多項式時間で計算できるときに常に存在することを示した。また,kが定数であるk-aryインスタンスのクラスも考慮し,すなわち,各エージェントは,商品に対してほとんどのk値を持つ。このような事例に対して,EF1+fPO割当ては,強い多項式時間で計算できることを示した。すべての値が正である場合,そのようなインスタンスに対するEQ1+fPO割当は,強い多項式時間で計算できることを示した。次に,エージェントの数が一定であり,EF1+PO(同様にEQ1+PO)割当が多項式時間で計算できることを示した。これらの結果は,二値または同一評価の既知のケースを超えて多項式時間計算可能性を著しく拡張した。また,商品のために一定の多くの異なる値を有する多くのエージェントがあるとき,Nash福祉最大化割当てを計算する多項式時間アルゴリズムを設計した。最後に,複雑性側面に関して,著者らはEF1+fPO割当てを計算する問題が複雑性クラスPLSにあることを示した。【JST・京大機械翻訳】
