Algorithm And Computation Complexity Results On Bin Coveing Game And Its Core

A cooperative game model with characteristic function N, consists of aplayer set N {1,2,..., n} and a characteristic function:2N R. The game iscalled a profit (cost) game if the characteristic function value (S)of a coalitionS N represents the profit (cost) S can obtains. When the value of a coalition can becomputed via solving a combinatorial optimization problem, the game is called acombinatorial cooperative game. The feature of this kind of cooperative game modelsis that their representation is succinct, that is, the length of their input is polynomial inthe number of the players. Cooperative game theory focus on how to allocate theprofit or cost collectively achieved by a group of selfish cooperative agents in fair andrational ways. Different requirements on the fairness and rationality derive differentsolution concepts of the cooperative game. Among various solution concepts, the coreand some related concepts of approximate core are most important, which impose thesubgroup rationality on the allocations to ensure the grand cooperation’s stability.Currently, the algorithmic and computational complexity issues on the game solutionsare hot spots in the research area of cooperative game. The typical computationalproblems related to the core and approximate core are as follows:(1) Testing nonemptiness: is there any polynomial time algorithm for testing thenonemptiness of the core or approximate core?(2) Construction: how to find a polynomial time algorithm for constructing anallocation in the core or approximate core?(3) Checking membership: is there is any polynomial time algorithm to determinewhether a given allocation belongs to the core or approximate core?This thesis focuses on a kind of cooperative game model arising from bin coveringproblems, called bin covering game. Generally, given a number of items with differentsizes and unlimited number of bins with a fixed size, the bin covering problem is toassign the items in as many bins as possible so that the overall sizes of items assignedto a bin is no less than the fixed bin size (i.e., to cover a bin). Bin covering problemhas many applications in practice, such as project financing, etc. The goal ofestablishing bin covering games is to penetrate into the related profit allocationproblem in such circumstances. The properties of the bin covering game and the related issues on the core andapproximate core from the point of algorithmic and computational complexity vieware discussed in this paper. The Main results are as follows:(1) The new bin covering cooperative game model are first introduced, where eachplayer controls one items with the give size, the characteristic function value of eachcoalition is defined as the maximum number of bins that can be covered by theplayers (items) in this coalition. The properties of the game model and the coreallocations are discussed. Given a0-1program formulation of the bin coveringproblem, an exact algorithm based on the column generation method and dynamicprogramming is proposed to solve the linear program relaxation of the0-1program,which can be used to give the value of the characteristic function of the bin coveringgame in a satisfied approximation guarantee.(2) Given the0-1program formulation (ILPN)of the bin covering problem w.r.t. thegrand coalition, based on the dual theorem of linear programming, it is proved thatthat the core of the bin covering game is nonempty if and only if the linear programrelaxation (LPN)of (ILPN)has integer optimal solutions; and in such case, the core isexactly the set of optimal solutions to the dual program of (LPN). When the core isempty, we show that the minimum value*minthat guarantees the nonemptiness ofthe-approximate core is determined by the difference between optimum values of(ILPN)and (LPN).(3) The algorithmic and computational complexity issue related to the core andapproximate core are discussed. By making use of PARTITION, which is a classicNP-complete problem, it is shown that for bin covering games, testing nonemptinessof the core and the-approximate core (for a given0) are both NP-hard, andchecking whether a given allocation belongs to the core is co-NP-complete even if thecore is known to be nonempty. As a corollary, it is also shown that computing thevalue of*minis also NP-hard. On the other hand, a pseudo-polynomial timealgorithm is proposed for computing*minvia dynamic programming method.