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.

This paper discusses the design of a parallel genetic algorithm to generate solutions to multi-objective problems. The algorithm uses multiple optimization criteria, independent cross-pollinating populations, and handles multiple hard constraints. Individuals in the population consist of multiple chromosomes. The complexity of the algorithm is the number of generations processed times O(N²) where N is the total number of individuals used for path generation on any of the optimizations. The results of initial empirical studies on the effects of pollination and recommendations for possible future work are presented.

We consider a game-theoretic bin packing problem with identical items, and we study the convergence time to a Nash equilibrium. In the model proposed, users choose their strategy simultaneously. We deal with two bins and multiple bins cases. We consider the case when users know the load of all bins and cases with less information. We consider two approaches, depending if the system can undo movements that lead to infeasible states. Let n and m be, respectively, the number of items and bins. In the two bins case, we show an O(log log n) and an O(n) bounds when undo movements are allowed and when they are not allowed, resp. In multiple bins case, we show an O(log n) and an O(nm) bounds when undo movements are allowed and when they are not allowed, resp. In the case with less information, we show an O(m log n) and an O(n³m) bounds when undo movements are allowed and when they are not allowed, resp. Also, in the case with less information where the information about completely filled/empty bins is not available, we show an O(m²log n) and an O(n³m³) bounds when undo movements are allowed and when they are not allowed, resp.

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

Service quality preference behaviors of both members are considered in service supply chain (SSC) including a service integrator and a service provider with stochastic demand. Through analysis of service quality cost and revenue, the utility functions are established on service quality effort degree and service quality preference level in integrated and decentralized SSC. Nash equilibrium and quantum game are used to optimize the models. By comparing the different solutions, the optimal strategies are obtained in SSC with quality preference. Then some numerical examples are studied and the changing trend of service quality effort is further analyzed by the influence of the entanglement operator and quality preferences.

We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of minimizing their latency. However, in doing so, they face the challenge of lack of precise information on the capacity of the network links. This uncertainty is modeled via a set of probability distributions over all the possibilities, one for each user. The resulting model is an amalgamation of the KP-model of [14] and the congestion games with user-specific functions of [22]. We embark on a study of Nash equilibria and the price of anarchy in this new model. In particular, we propose polynomial-time algorithms (w.r.t. our model's parameters) for computing some special cases of pure Nash equilibria and we show that negative results of [22], for the non-existence of pure Nash equilibria in the case of three users, do not apply to our model. Consequently, we propose an interesting open problem, that of the existence of pure Nash equilibria in the general case of our model. Furthermore, we consider appropriate notions for the social cost and the price of anarchy and obtain upper bounds for the latter. With respect to fully mixed Nash equilibria, we show that when they exist, they are unique. Finally, we prove that the fully mixed Nash equilibrium is the worst equilibrium.

This study aims to investigate how various forms of social control, namely selective incentive and behavioral conformity, collectively rationalize participation in collective action, through indirect network connections. To address it, we use a public game model and analyze the equilibrium conditions of the emergence of collective action on centralized, star-shaped networks and on decentralized, loop-shaped networks. The results show that social control is effective in motivating contribution towards a public good; however, the effect is highly dependent on the ratio of the benefits derived from selective incentive versus behavioral conformity as well as on the structure of social networks. Moreover, we find that indirect network connections can be an important route through which social control can improve the emergence of collective action. These findings have important implications for collective action theory and for intervention in collective actions.

This paper, analyzes the allocation problem of customers in a discrete-time multi-server queueing system and considers two criteria for routing customers' selections: equilibrium and social optimization. As far as we know, there is no literature concerning the discrete-time multi-server models on the subject of equilibrium behaviors of customers and servers. Comparing the results of customers' distribution at the servers under the two criteria, we show that the servers used in equilibrium are no more than those used in the socially optimal outcome, that is, the individual's decision deviates from the socially preferred one. Furthermore, we also clearly show the mutative trend of several important performance measures for various values of arrival rate numerically to verify the theoretical results.

In this paper, we first present a discrete fixed point theorem for contraction mappings from the product set of integer intervals into itself, which is an extension of Robert's discrete fixed point theorem. Next, we derive an existence theorem of a pure-strategy Nash equilibrium for a noncooperative n-person game from our fixed point theorem. Finally, we show that Kuhn's theorem for a game in expansive form can be explained by our existence theorem.

We look at a Cournot model in which each firm may be unreliable with random capacity, so the total quantity brought into market is uncertain. The Cournot model has a unique pure strategy Nash equilibrium (NE), in which the number of active firms is determined by each firm's production cost and reliability. Our results indicate the following effects of unreliability: the number of active firms in the NE is more than that each firm is completely reliable and the expected total quantity brought into market is less than that each firm is completely reliable. Whether a given firm joins in the game is independent of its reliability, but any given firm always hopes that the less-expensive firms' capacities are random and stochastically smaller.

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.

We use the capacity allocation as a demand management tool to optimize the patient flow distribution on a hierarchical healthcare delivery system, which is a mixture of patient choice and gatekeeping. Capacity allocation for such service system can be challenging because of the inherent stochastic referral process and patients’ heterogeneous delay sensitivities. In this research, a stochastic queueing-based model is proposed to find the optimal allocation of the limited service capacity of the second level of experts. Considering the impact of the deficiency of the skill level and the amount of gatekeepers, the stochastic referral process is modeled with a tandem queue. By solving a fixed-point problem, we show that there is an unique optimal allocation and corresponding equilibrium demand. We carry out numerical studies and find that providing two alternatives for patients can be better than gatekeeper system, when the capacity of the gatekeeper is moderate compared to patients’ potential demand. Results also indicate that the optimal allocation is robust in terms of the referral rate and the mistreatment rate when two rates are less than corresponding thresholds.

The Taguchi robust design concept is combined with the multi-objective deterministic optimization method to overcome single point design problems in Aerodynamics. Starting from a statistical definition of stability, the method finds, Nash equilibrium solutions for performance and its stability simultaneously.

The Vehicular Ad hoc NETworks (VANETs) are of high mobile and dynamic in nature. They are highly prone to network discontinuity, thereby the applications running on the vehicles get degraded in its service. The network selection for VANETs is done based on network attributes and user Quality of Service (QoS) demands. In this work, a two-phase access network selection scheme is proposed for VANETs. In the first phase, the available networks are ranked based on QoS demands using Weighted Sum Method (WSM). During the second phase, based on availability of resources, handoff decision and access network selection are carried out using game theory approach. Here, the vehicle and network play the game by adopting different strategies, thereby the optimum Nash Equilibrium (NE) is obtained. The simulation results validate that the proposed scheme outperforms the conventional Multiple Attribute Decision Making (MADM) schemes.

With the rapid development of technologies and applications, extending from trusted environments to untrusted environments is the development trend of Internet of Things (IoT) applications. Due to the limited resources of nodes and the rise of edge computing, more and more IoT applications are required to have task delegation functions. Delegating IoT tasks in untrusted environments has to solve two problems: First, how to evaluate the trustworthiness of nodes so that requesters can delegate tasks to trusted providers; the second is how to ensure the successful implementation of the task delegation between the requester and the provider. While trust models are often used to solve the first problem, the lack of ability to describe transactions between the requester and the provider makes them unsuitable for solving the second problem. In recent years, game theory has been more applied to task delegation. By setting appropriate utility functions, game theory can ensure the successful implementation of task delegation. However, since it is unable to evaluate the trustworthiness of nodes, game theory cannot solve the first problem. This paper combines the advantages of trust models and game theory to construct a game of three-party task delegation based on trust to explore a solution to problems of IoT task delegation in an untrusted environment. Finally, aiming at the problem that setting essential parameter values of trust models is empirical and experimental, this paper theoretically discusses how to set these values in an untrusted environment.

In this paper, a real estate game model with nonlinear demand function is proposed. And an analysis of the game's local stability is carried out. It is shown that the stability of Nash equilibrium point is lost through period-doubling bifurcation as some parameters are varied. With numerical simulations method, the results of bifurcation diagrams, maximal Lyapunov exponents and strange attractors are presented. It is found that the chaotic behavior of the model has been stabilized on the Nash equilibrium point by using of nonlinear feedback control method.

This paper investigates the dynamical behaviors of a duopoly model with two content providers (CPs). Competition between two CPs is assumed to take place in terms of their pricing decisions and the credibility of content they offer. According to the CPs’ rationality level, we consider a scenario where both CPs are bounded rational. Each CP in any period uses the marginal profit observed from the previous period to choose its strategies. We compute explicitly the steady states of the dynamical system induced by bounded rationality, and establish a necessary and sufficient condition for stability of its Nash equilibrium (NE). Numerical simulations show that if some parameters of the model are varied, the stability of the NE point is lost and the complex (periodic or chaotic) behavior occurs. The chaotic behavior of the system is stabilized on the NE point by applying control.

This paper considers a mean field game model inspired by crowd motion where agents want to leave a given bounded domain through a part of its boundary in minimal time. Each agent is free to move in any direction, but their maximal speed is bounded in terms of the average density of agents around their position in order to take into account congestion phenomena. After a preliminary study of the corresponding minimal-time optimal control problem, we formulate the mean field game in a Lagrangian setting and prove existence of Lagrangian equilibria using a fixed point strategy. We provide a further study of equilibria under the assumption that agents may leave the domain through the whole boundary, in which case equilibria are described through a system of a continuity equation on the distribution of agents coupled with a Hamilton–Jacobi equation on the value function of the optimal control problem solved by each agent. This is possible thanks to the semiconcavity of the value function, which follows from some further regularity properties of optimal trajectories obtained through Pontryagin Maximum Principle. Simulations illustrate the behavior of equilibria in some particular situations.

Discovering different groups, or called classes, is useful for pattern recognition, data preprocessing, association analysis, query optimization, etc. To make every object satisfied as much as possible, the groups are generated by the associations or behaviors among participating objects other than the attributes owned by themselves. By mainly considering the mutual associations among the given objects and based on the game theory, in this paper we study the multi-objective oriented categorization. Based on the idea of Shapley value in the coalitional game, we first propose the concept of priority groups and give the efficient algorithm for computing the satisfaction degree of players in a group. Based on the idea of strategic games and Nash equilibrium, we then give the algorithm for computing an approximate equilibrium to solve the conflicts between the strategies of players, and consequently achieve the ultimate multi-objective oriented groups. Preliminary experiments and performance studies verify the efficiency and effectiveness of our methods.

Data clustering is the unsupervised classification of a set of objects into groups (clusters), according to their similarities. This can be seen as a form of equilibrium, which is the motivation that led to recent formulations of the data clustering task using game theoretic models. In this context, we propose a novel game-theoretic clustering approach reducing the clustering task to that of searching for a pure Nash equilibrium of a potential game, which corresponds to a stable clustering. Interestingly, the existence and the convergence towards such equilibrium are established, and we experimentally prove that such stability is not always guaranteed by the classical k-means algorithm. We also propose an iterative best-response algorithm for solving this potential clustering game. This algorithm is implemented and tested on several real-world and artificial datasets. Considering most of clustering quality measures, the obtained results are compared to those provided by both the classical k-means and by an hybridization of these two algorithms.