Narrow Results

We consider the bin packing problem with cardinality constraints in a non-cooperative game setting. In the game, there are a set of items with sizes between 0 and 1, and a number of bins each of which has a capacity of 1. Each bin can pack at most $k$ items, for a given integer parameter $k\ge 2$. The social cost is the number of bins used in the packing. Each item tries to be packed into one of the bins so as to minimize its cost. The selfish behaviors of the items result in some kind of equilibrium, which greatly depends on the cost rule in the game. We say a cost rule encourages sharing if for an item, compared with sharing a bin with some other items, staying in a bin alone does not decrease its cost. In this paper, we first show that for any bin packing game with cardinality constraints under an encourage-sharing cost rule, the price of anarchy of it is at least $2-\frac{2}{k}$. We then propose a cost rule and show that the price of anarchy of the bin packing game under the rule is $2-\frac{2}{k}$ when $k\ge 7$.

A paradox of self-reference in beliefs in games is identified, which yields a game-theoretic impossibility theorem akin to Russell's Paradox. An informal version of the paradox is that the following configuration of beliefs is impossible:Ann believes that Bob assumes thatAnn believes that Bob's assumption is wrongThis is formalized to show that any belief model of a certain kind must have a “hole.” An interpretation of the result is that if the analyst's tools are available to the players in a game, then there are statements that the players can think about but cannot assume. Connections are made to some questions in the foundations of game theory.