In this paper, we address the selfish bin covering problem, which is greatly related both to the bin covering problem, and to the weighted majority game. What we are mainly concerned with is how much the lack of central coordination harms social welfare. Besides the standard PoA and PoS, which are based on Nash equilibrium, we also take into account the strong Nash equilibrium, and several new equilibrium concepts. For each equilibrium concept, the corresponding PoA and PoS are given, and the problems of computing an arbitrary equilibrium, as well as approximating the best one, are also considered.
We define two simple algorithms for the bin covering problem and give their asymptotic performance.  Bin covering takes as input a list of items with sizes in (0, 1) and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the classical one-dimensional bin packing problem, but has for many years lagged behind the latter in terms of the quality of the best approximation algorithms. We design algorithms for this problem that close the gap, both in terms of worst- and average-case results. We present (1) the first asymptotic approximation scheme for the offline version, (2) algorithms that have bounded worst-case behavior for instances with discrete item sizes and expected behavior that is asymptotically optimal for all discrete “perfect-packing distributions” (ones for which optimal packings have sublinear expected waste), and (3) a learning algorithm that has asymptotically optimal expected behavior for all discrete distributions. The algorithms of (2) and (3) are based on the recently-developed online Sum-of-Squares algorithm for bin packing. We also present experimental analysis comparing the algorithms of (2) and suggesting that one of them, the Sum-of-Squares-with-Threshold algorithm, performs quite well even for discrete distributions that do not have the perfect-packing property. The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of 12, 23, and 34 the optimal number, at running time costs of O(n), O(nlogn), and O(nlog2n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items. In the dual bin packing problem, the objective is to assign items of given size to the largest possible number of bins, subject to the constraint that the total size of the items assigned to any bin is at least equal to 1. We carry out a probabilistic analysis of this problem under the assumption that the items are drawn independently from the uniform distribution on [0, 1] and reveal the connection between this problem and the classical bin packing problem as well as to renewal theory. We deal with the variable-sized bin covering problem: Given a list L of items in (0,1] and a finite collection B of feasible bin sizes, the goal is to select a set of bins with sizes in B and to cover them with the items in L such that the total size of the covered bins is maximized. In the on-line version of this problem, the items must be assigned to bins one by one without previewing future items. This note presents a complete solution to the on-line problem: For every collection B of bin sizes, we give an on-line approximation algorithm with a worst-case ratio r(B), and we prove that no on-line algorithm can perform better in the worst case. The value r(B) mainly depends on the largest gap between consecutive bin sizes. In the bin covering problem there is a group L=(a1,?,an) of items with sizes s?(ai)?(0,1), and the goal is to find a packing of the items into bins to maximize the number of bins that receive items of total size at least 1. This is a dual problem to the classical bin packing problem. In this paper we present the first asymptotic fully polynomial-time approximation scheme for the problem.