Search

We study the multidimensional vector packing problem with selfish items. An item is a d-dimensional non-zero vector, whose rational components are in [0, 1]. A set of items can be packed into a bin if for every $$1 \le i \le d$$ , the sum of the ith components of all items of this set does not exceed 1. Items share costs of bins proportionally to the $$\ell _1$$ -norms of items, and each item corresponds to a selfish player in the sense that it prefers to be packed into a bin minimizing its resulting cost. This defines a class of games called vector packing games. We show that any game in this class has a packing that is a strong equilibrium, and that both the strong price of anarchy and the strong price of stability are logarithmic in d. We also provide an algorithm that constructs a packing that is a strong equilibrium. Furthermore, we show improved and nearly tight lower and upper bounds of $$d+0.657067$$ and $$d+0.657143$$ , respectively, for any $$d\ge 2$$ , on the price of anarchy. This exhibits a difference between the multidimensional problem and the one-dimensional problem, for which that price of anarchy is at most 1.6428.

The subset sum algorithm is a natural heuristic for the classical Bin Packing problem: In each iteration, the algorithm finds among the unpacked items, a maximum size set of items that fits into a new bin. More than 35 years after its first mention in the literature, establishing the worst-case performance of this heuristic remains, surprisingly, an open problem. Due to their simplicity and intuitive appeal, greedy algorithms are the heuristics of choice of many practitioners. Therefore, better understanding simple greedy heuristics is, in general, an interesting topic in its own right. Very recently, Epstein and Kleiman (Proc. ESA 2008, pp. 368---380) provided another incentive to study the subset sum algorithm by showing that the Strong Price of Anarchy of the game theoretic version of the Bin Packing problem is precisely the approximation ratio of this heuristic. In this paper we establish the exact approximation ratio of the subset sum algorithm, thus settling a long standing open problem. We generalize this result to the parametric variant of the Bin Packing problem where item sizes lie on the interval $$(0, \alpha ]$$(0,?] for some $$\alpha \le 1$$?≤1, yielding tight bounds for the Strong Price of Anarchy for all $$\alpha \le 1$$?≤1. Finally, we study the pure Price of Anarchy of the parametric Bin Packing game for which we show nearly tight upper and lower bounds for all $$\alpha \le 1$$?≤1.

Following recent interest in the study of computer science problems in a game theoretic setting, we consider the well known bin packing problem where the items are controlled by selfish agents. Each agent is charged with a cost according to the fraction of the used bin space its item requires. That is, the cost of the bin is split among the agents, proportionally to their sizes. Thus, the selfish agents prefer their items to be packed in a bin that is as full as possible. The social goal is to minimize the number of the bins used. The social cost in this case is therefore the number of bins used in the packing. A pure Nash equilibrium is a packing where no agent can obtain a smaller cost by unilaterally moving his item to a different bin, while other items remain in their original positions. A Strong Nash equilibrium is a packing where there exists no subset of agents, all agents in which can profit from jointly moving their items to different bins. We say that all agents in a subset profit from moving their items to different bins if all of them have a strictly smaller cost as a result of moving, while the other items remain in their positions. We measure the quality of the equilibria using the standard measures PoA and PoS that are defined as the worst case worst/best asymptotic ratio between the social cost of a (pure) Nash equilibrium and the cost of an optimal packing, respectively. We also consider the recently introduced measures SPoA and SPoS, that are defined similarly to the PoA and the PoS, but consider only Strong Nash equilibria. We give nearly tight lower and upper bounds of 1.6416 and 1.6428, respectively, on the PoA of the bin packing game, improving upon previous result by Bilo. We study the Strong Nash equilibria of the bin packing game, and show that a packing is a Strong Nash equilibrium iff it is produced by the Subset Sum algorithm for bin packing. This characterization implies that the SPoA of the bin packing game equals the approximation ratio of the Subset Sum algorithm, for which an almost tight bound is known. Moreover, the fact that any lower bound instance for the Subset Sum algorithm can be converted by a small modification of the item sizes to a lower bound instance on the SPoS, implies that in the bin packing game SPoA=SPoS. Finally, we address the issue of complexity of computing a Strong Nash packing and show that no polynomial time algorithm exists for finding Strong Nash equilibria, unless P=NP.

We study the multidimensional vector packing problem with selfish items. An item is d-dimensional non-zero vector, whose rational components are in [0,1], and a set of items can be packed into a bin if for any 1 ≤ i ≤ d, the sum of the ith components of all items of this set does not exceed 1. Items share costs of bins proportionally to their l1-norms, and each item corresponds to a selfish player in the sense that it prefers to be packed into a bin minimizing its resulting cost. This defines a class of games called vector packing games. We show that any game in this class has a packing that is a strong equilibrium, and that the strong price of anarchy (and the strong price of stability) is logarithmic in d, and provide an algorithm that constructs such a packing. We also show improved and nearly tight lower and upper bounds of d + 0.657067 and d + 0.657143 respectively, on the price of anarchy, exhibiting a difference between the multidimensional problem and the one dimensional problem, for which that price of anarchy is at most 1.6428.

We study the multidimensional vector scheduling problem with selfish jobs, both in non-cooperative and in cooperative versions, in two variants. These variants differ in the private costs of the jobs: in the first variant, the cost is the l ∞ norm (maximum over components) while in the second variant it is the l 1 norm (sum of components) of the load. We show existence of assignments that are Nash, strong Nash, weakly and strictly Pareto optimal Nash equilibria in these settings. For the first variant, we improve upon the previous bounds on the price of anarchy for the non-cooperative case, and find tight bounds for every number of machines and dimension. For the cooperative case we provide tight bounds on the strong prices of anarchy and stability, as well as tight bounds on weakly and strictly Pareto optimal prices of anarchy and stability, for every number of machines and dimension. For the second variant, which was not considered before, we again consider all the aforementioned measures, and find tight bounds, each of which being a function of the number of machines and the dimension, showing cardinal differences in the behavior of these measures both between the two variants, and in comparison to the one-dimensional case.

The subset sum algorithm is a natural heuristic for the classical Bin Packing problem: In each iteration, the algorithm finds among the unpacked items, a maximum size set of items that fits into a new bin. More than 35 years after its first mention in the literature, establishing the worst-case performance of this heuristic remains, surprisingly, an open problem. Due to their simplicity and intuitive appeal, greedy algorithms are the heuristics of choice of many practitioners. Therefore, better understanding simple greedy heuristics is, in general, an interesting topic in its own right. Very recently, Epstein and Kleiman (Proc. ESA 2008, pages 368-380) provided another incentive to study the subset sum algorithm by showing that the Strong Price of Anarchy of the game theoretic version of the Bin Packing problem is precisely the approximation ratio of this heuristic. In this paper we establish the exact approximation ratio of the subset sum algorithm, thus settling a long standing open problem. We generalize this result to the parametric variant of the Bin Packing problem where item sizes lie on the interval (0, ?] for some ? ≤ 1, yielding tight bounds for the Strong Price of Anarchy for all ? ≤ 1. Finally, we study the pure Price of Anarchy of the parametric Bin Packing game for which we show nearly tight upper and lower bounds for all ? ≤ 1.

We consider a scheduling problem where each job is controlled by a selfish agent, who is only interested in minimizing its own cost, which is defined as the total load on the machine that its job is assigned to. We consider the objective of maximizing the minimum load (cover) over the machines. Unlike the regular makespan minimization problem, which was extensively studied in a game theoretic context, this problem has not been considered in this setting before. We study the price of anarchy (poa) and the price of stability (pos). We show that on related machines, both these values are unbounded. We then focus on identical machines. We show that the $\textsc{pos}$ is 1, and we derive tight bounds on the $\textsc{poa}$ for m ≤ 6 and nearly tight bounds for general m. In particular, we show that the $\textsc{poa}$ is at least 1.691 for larger m and at most 1.7. Hence, surprisingly, the $\textsc{poa}$ is less than the $\textsc{poa}$ for the makespan problem, which is 2. To achieve the upper bound of 1.7, we make an unusual use of weighting functions. Finally, in contrast we show that the mixed $\textsc{poa}$ grows exponentially with m for this problem, although it is only ?(logm/loglogm) for the makespan.

Following recent interest in the study of computer science problems in a game theoretic setting, we consider the well known bin packing problem where the items are controlled by selfish agents. Each agent is charged with a cost according to the fraction of the used bin space its item requires. That is, the cost of the bin is split among the agents, proportionally to their sizes. Thus, the selfish agents prefer their items to be packed in a bin that is as full as possible. The social goal is to minimize the number of the bins used. The social cost in this case is therefore the number of bins used in the packing. A pure Nash equilibrium is a packing where no agent can obtain a smaller cost by unilaterally moving his item to a different bin, while other items remain in their original positions. A Strong Nash equilibrium is a packing where there exists no subset of agents, all agents in which can profit from jointly moving their items to different bins. We say that all agents in a subset profit from moving their items to different bins if all of them have a strictly smaller cost as a result of moving, while the other items remain in their positions. We measure the quality of the equilibria using the standard measures PoAand PoSthat are defined as the worst case worst/best asymptotic ratio between the social cost of a (pure) Nash equilibrium and the cost of an optimal packing, respectively. We also consider the recently introduced measures SPoAand SPoS, that are defined similarly to the PoAand the PoS, but consider only Strong Nash equilibria. We give nearly tight lower and upper bounds of 1.6416 and 1.6428, respectively, on the PoAof the bin packing game, improving upon previous result by Bilo, and establish the fact that PoS= 1. We show that the bin packing game admits a Strong Nash equilibrium, and that SPoA=SPoS. We prove that this value is equal to the approximation ratio of a natural greedy algorithm for bin packing.

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308–320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.