費用2種類の施設配置ゲームの仁とシャープレイ値の計算について  [in Japanese] On computing the nucleolus and the Shapley value of facility location games with two cost values  [in Japanese]

Search this Article

Abstract

施設配置ゲームは施設配置問題から生じる協力ゲームである.この問題では,施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし,最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える.しかし,実際にそのような解を計算しようとすると,計算量理論の意味で難しいことが多い.本稿では,施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する.具体的には,施設の数が2個かつ費用が2種類に制限された場合に,凸ゲームと呼ばれる良い性質を持つクラスに属するための必要十分条件を示す.さらに,施設が2個かつ費用が2種類の場合にはシャープレイ値が顧客数の多項式時間計算可能であることを示す.We study facility location games, which arise from the facility location problem as a cooperative game. In this game, customers in the facility location problem minimize their cost through cooperation, and the minimized cost is distributed among the customers by a solution concept from cooperative game theory. However, computation of such a solution can be hard in the sense of computational complexity theory. We concentrate on an uncapacitated facility location game. When there are at most two facilities, and the cost is restricted to two values, we characterize a convex game, which has several nice properties. Furthermore, when there are at most two facilities, and the cost is restricted to two values, we show that the Shapley value can be computed in polynomial time in the size of customers.

Journal

  • 研究報告アルゴリズム(AL)

    研究報告アルゴリズム(AL) 2013-AL-143(3), 1-8, 2013-02-22

Codes

  • NII Article ID (NAID)
    110009550136
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    JPN
  • Article Type
    Technical Report
  • Data Source
    NII-ELS 
Page Top