Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPrices of anarchy of selfish 2D bin packing games
118
0
0.0
(
0
)
Added by
Fl\\'avio Miyazawa
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider a game-theoretical problem called selfish 2-dimensional bin packing game, a generalization of the 1-dimensional case already treated in the literature. In this game, the items to be packed are rectangles, and the bins are unit squares. The game starts with a set of items arbitrarily packed in bins. The cost of an item is defined as the ratio between its area and the total occupied area of the respective bin. Each item is a selfish player that wants to minimize its cost. A migration of an item to another bin is allowed only when its cost is decreased. We show that this game always converges to a Nash equilibrium (a stable packing where no single item can decrease its cost by migrating to another bin). We show that the pure price of anarchy of this game is unbounded, so we address the particular case where all items are squares. We show that the pure price of anarchy of the selfish square packing game is at least 2.3634 and at most 2.6875. We also present analogous results for the strong Nash equilibrium (a stable packing where no nonempty set of items can simultaneously migrate to another common bin and decrease the cost of each item in the set). We show that the strong price of anarchy when all items are squares is at least 2.0747 and at most 2.3605.
rate research
Read More
This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin-destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials), the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the networks cost functions are polynomials.
We consider an atomic congestion game in which each player participates in the game with an exogenous and known probability $p_{i}in[0,1]$, independently of everybody else, or stays out and incurs no cost. We first prove that the resulting game is potential. Then, we compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior. It turns out that the price of anarchy as a function of the maximum participation probability $p=max_{i} p_{i}$ is a nondecreasing function. The worst case is attained when players have the same participation probabilities $p_{i}equiv p$. For the case of affine costs, we provide an analytic expression for the parameterized price of anarchy as a function of $p$. This function is continuous on $(0,1]$, is equal to $4/3$ for $0<pleq 1/4$, and increases towards $5/2$ when $pto 1$. Our work can be interpreted as providing a continuous transition between the price of anarchy of nonatomic and atomic games, which are the extremes of the price of anarchy function we characterize. We show that these bounds are tight and are attained on routing games -- as opposed to general congestion games -- with purely linear costs (i.e., with no constant terms).
The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.
In this paper, we analyze a transportation game first introduced by Fotakis, Gourv`es, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, in order to achieve this goal, they have to choose one of the available buses. We introduce a sequential version of this game and provide bounds for the Sequential Price of Stability and the Sequential Price of Anarchy in both metric and non-metric instances, considering three social cost functions: the total traveled distance by all buses, the maximum distance traveled by a bus, and the sum of the distances traveled by all players (a new social cost function that we introduce). Finally, we analyze the Price of Stability and the Price of Anarchy for this new function in simultaneous transportation games.
The bin-packing problem continues to remain relevant in numerous application areas. This technical report discusses the empirical performance of different bin-packing heuristics for certain test problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
