Narrow Results

This paper studies the inefficiency of Nash equilibria (NE) for scheduling games on hierarchical machines with quadratic social cost. There is a set of hierarchical machines and a set of jobs. Each job can choose one machine from the set of machines that are permitted to process it, and the cost associated with the job is equal to the load of the selected machine. A schedule is an NE if no job can reduce its cost by ultimately moving to a different eligible machine. The social cost is the sum of squares of the loads of all the machines. We show that the Price of Anarchy for two, three and four machines is $\frac{3+\sqrt{5}}{4}$, $\frac{2+\sqrt{2}}{2}$ and $\frac{2+\sqrt{2}}{2}$, respectively.

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$.

In the model of restricted parallel links, n users must be routed on m parallel links under the restriction that the link for each user be chosen from a certain set of allowed links for the user. In a (pure) Nash equilibrium, no user may improve its own Individual Cost (latency) by unilaterally switching to another link from its set of allowed links. The Price of Anarchy is a widely adopted measure of the worst-case loss (relative to optimum) in system performance (maximum latency) incurred in a Nash equilibrium.

In this work, we present a comprehensive collection of bounds on Price of Anarchy for the model of restricted parallel links and for the special case of pure Nash equilibria. Specifically, we prove:

• For the case of identical users and identical links, the Price of Anarchy is .

• For the case of identical users, the Price of Anarchy is .

• For the case of identical links, the Price of Anarchy is , which is asymptotically tight.

• For the most general case of arbitrary users and related links, the Price of Anarchy is at least m – 1 and less than m.

The shown bounds reveal the dependence of the Price of Anarchy on n and m for all possible assumptions on users and links.

This paper concerns the asymmetric atomic selfish routing game for load balancing in ring networks. In the selfish routing, each player selects a path in the ring network to route one unit traffic between its source and destination nodes, aiming at a minimum maximum link load along its own path. The selfish path selections by individuals ignore the system objective of minimizing the maximum load over all network links. This selfish ring load (SRL) game arises in a wide variety of applications in decentralized network routing, where network performance is often measured by the price of anarchy (PoA), the worst-case ratio between the maximum link loads in an equilibrium routing and an optimal routing. It has been known that the PoA of SRL with respect to classical Nash Equilibrium (NE) cannot be upper bounded by any constant, showing large loss of efficiency at some NE outcome.

In an effort to improve the network performance in the SRL game, we generalize the model to so-called SRL with collusion (SRLC) which allows coordination within any coalition of up to k selfish players on the condition that every player of the coalition benefits from the coordination. We prove that, for m-player game on n-node ring, the PoA of SRLC is n - 1 when k ≤ 2, drops to 2 when k = 3 and is at least 1 + 2/m for k ≥ 4. Our study shows that on one hand, the performance of ring networks, in terms of maximum load, benefits significantly from coordination of self-interested players within small-sized coalitions; on the other hand, the equilibrium routing in SRL might not reach global optimum even if any number of players can coordinate.

In this paper, we consider a scheduling problem with $m$ uniform parallel-batching machines $\{M_1,M_2,\dots ,M_m\}$ under game situation. There are $n$ jobs, each of which is associated with a load. Each machine $M_i(1\le i\le m)$ has a speed $s_i$ and can handle up to $b$ jobs simultaneously as a batch. The load of a batch is the load of the longest job in the batch. All the jobs in a batch start and complete at the same time. Each job is owned by an agent and its individual cost is the completion time of the job. The social cost is the largest completion time over all jobs, i.e., the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of Nash Equilibrium and offer an upper bound on the price of anarchy (POA) of the coordination mechanism. We present a greedy algorithm and show that: (i) under the coordination mechanism, any instance of the scheduling game problem has a unique Nash Equilibrium and it is precisely the schedule returned by the greedy algorithm; (ii) the mechanism has a POA no more than $1+\frac{s_{max}}{\bar{s}}\left(\right.1-\frac{1}{max\{m,b\}}\left)\right.+\delta$, where $s_{max}=max\{s_1,s_2,\dots ,s_m\}$, $\bar{s}=(s_1+s_2+\cdots +s_m)/m$, and $\delta$ is a small positive number that tends to 0.

In this paper, we have studied the impact of customer confusion on the decision-making strategies of Internet service providers (ISP) in the network and telecommunications market. This confusion may come from several factors, e.g. incomplete information on the offer, non-transparent advertising, the ability of the analysis, etc.; but that sure varies over time since yesterday’s customer is no longer today’s.

In this work, we have developed a simple oligopolistic model, using non-cooperative game theory, to formalize the interactions between service providers and end-users by considering that the rationality of customers varies over time. We assessed the impact of the dynamics of consumer confusion on the competition and profitability of service providers who are considered rational and competitive with one another to maximize their respective gains in the face of a confused fraction of consumers while others are not confused. We have shown the existence and uniqueness of the Nash equilibrium. We used the best response dynamic algorithm for learning Nash equilibrium. On the one hand, we have shown that when the number of confused customers is large, the ISP is interested in that and they offer moderately high prices with low quality of service. On the other hand, over time, rationality increases, forcing the ISPs to change their strategies by offering better services so that their demand increases. We also add that when customer behavior changes quickly, the ISPs follow clearer strategies with customer satisfactory services.

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$.