施設配置ゲームにおける仁・シャープレイ値の計算について  [in Japanese] On Computing the Nucleolus and the Shapley Value of Facility Location Games  [in Japanese]

Search this Article

Author(s)

    • 並河 雄紀 NAMIKAWA Takanori
    • 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology
    • 岡本 吉央 OKAMOTO Yoshio
    • 電気通信大学大学院情報理工学研究科情報・通信工学専攻 Department of Communication Engineering and Informatics, Graduate School of Informatics and Engineering, The University of Electro-Communications
    • 大舘 陽太 OTACHI Yota
    • 北陸先端科学技術大学院大学情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology

Abstract

施設配置ゲームは施設配置問題から生じる協力ゲーム的問題である.この問題では,施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし,最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える.しかし,実際にそのような解を計算しようとすると,計算量理論の意味で難しいことが多い.本稿では,施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する.具体的には,施設の数が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, computaion 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 restrited to two values, we characterize a convex game, which has several nice properties. Furthermore, for general uncapacitated facility location games, we exhibit a case in which the nucleolus and the Shapley value coincide.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 112(272), 25-32, 2012-10-24

    The Institute of Electronics, Information and Communication Engineers

References:  8

Codes

  • NII Article ID (NAID)
    110009636909
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    0913-5685
  • NDL Article ID
    024079006
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top