caa a22 4500 475769309 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000501xx s 000 0 eng 10.1007/s101070050005 doi (NATIONALLICENCE)springer-10.1007/s101070050005 Totally balanced combinatorial optimization games [Elektronische Daten] [Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi, Wenan Zang] Abstract. : Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.¶We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. Springer-Verlag Berlin Heidelberg, 2000 Key words: combinatorial optimization - duality theory - cooperative games - total balancedness nationallicence Mathematics Subject Classification (1991): 90D12 nationallicence Deng Xiaotie Department of Computer Science, City University of Hong Kong, Hong Kong, P.R. China, e-mail: deng@cs.cityu.edu.hk, CN aut Ibaraki Toshihide Department of Applied Mathematics and Physics, Graduate School of Information, Kyoto University, Kyoto, Japan 606-8501, e-mail: {ibaraki,naga}@kyoto-u.ac.jp, JP aut Nagamochi Hiroshi Department of Applied Mathematics and Physics, Graduate School of Information, Kyoto University, Kyoto, Japan 606-8501, e-mail: {ibaraki,naga}@kyoto-u.ac.jp, JP aut Zang Wenan Department of Mathematics, The University of Hong Kong, Hong Kong, P.R. China, e-mail: wzang@maths.hku.hk, CN aut https://doi.org/10.1007/s101070050005 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101070050005 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Deng Xiaotie Department of Computer Science, City University of Hong Kong, Hong Kong, P.R. China, e-mail: deng@cs.cityu.edu.hk, CN aut NATIONALLICENCE 700 1- Ibaraki Toshihide Department of Applied Mathematics and Physics, Graduate School of Information, Kyoto University, Kyoto, Japan 606-8501, e-mail: {ibaraki,naga}@kyoto-u.ac.jp, JP aut NATIONALLICENCE 700 1- Nagamochi Hiroshi Department of Applied Mathematics and Physics, Graduate School of Information, Kyoto University, Kyoto, Japan 606-8501, e-mail: {ibaraki,naga}@kyoto-u.ac.jp, JP aut NATIONALLICENCE 700 1- Zang Wenan Department of Mathematics, The University of Hong Kong, Hong Kong, P.R. China, e-mail: wzang@maths.hku.hk, CN aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer