THE BOUND OF PRICE OF ANARCHY FOR MULTI-CLASS AND MULTI-CRITERIA TRAFFIC EQUILIBRIUM PROBLEM

In this paper, we use the variational method to study the efficiency loss of user equilibrium for the multi-class, multi-criterion traffic equilibrium with general tolls and a discrete set of value of. time. By introducing three important parameters k1, k2, k3, we derive several bounds of price of anarchy for this problem when tolls are considered and not considered as part of the system cost, with the cost-based criterion.

Computation of PoA for Selfish Node Detection and Resource Allocation Using Game Theory

The introduction of new technologies has increased communication network coverage and the number of associating nodes in dynamic communication networks(DCN).As the network has the characteristics like decentralized and dynamic,few nodes in the network may not associate with other nodes.These uncooperative nodes also known as selfish nodes corrupt the performance of the cooperative nodes.Namely,the nodes cause congestion,high delay,security concerns,and resource depletion.This study presents an effective selfish node detection method to address these problems.The Price of Anarchy(PoA)and the Price of Stability(PoS)in Game Theory with the Presence of Nash Equilibrium(NE)are discussed for the Selfish Node Detection.This is a novel experiment to detect selfish nodes in a network using PoA.Moreover,the least response dynamic-based Capacitated Selfish Resource Allocation(CSRA)game is introduced to improve resource usage among the nodes.The suggested strategy is simulated using the Solar Winds simulator,and the simulation results show that,when compared to earlier methods,the new scheme offers promising performance in terms of delivery rate,delay,and throughput.

The Power Allocation Game on A Network:A Paradox

The well-known Braess paradox in congestion games states that adding an additional road to a transportation network may increase the total travel time, and consequently decrease the overall efficiency. This paper presents a paradox in a similar spirit and involves a distributed resource allocation game on networks, namely the power allocation game between countries developed in Li and Morse(2017). The paradox is that by having additional friends may actually decrease a country's total welfare in equilibrium. Conditions for this paradox to occur as well as the price of anarchy results are also derived.

Equilibrium Arrivals to Preemptive Queueing System with Fixed and Random Population Size

A single-server queueing system with preemptive access is considered.Each customer has one attempt to enter the system at its working interval[0,T].As soon as the customer request enters the system,the server immediately starts the service.But when the next request arrives in the system,the previous one leaves the system even he has not finished his service yet.We study a non-cooperative game in which the customers wish to maximize their probability of obtaining service within a certain period of time.We characterize the Nash equilibrium and the price of anarchy,which is defined as the ratio between the optimal and equilibrium social utility.Two models are considered.In the first model the number of players is fixed,while in the second it is random and obeys the Poisson distribution.We demonstrate that there exists a unique symmetric equilibrium for both models.Finally,we calculate the price of anarchy for both models and show that the price of anarchy is not monotone with respect to the number of customers.

How does trip frequency distort time value to impact congestion charging schemes?

A notable feature of a city or region with close economic and social connections with its neighbours is its highly mixed local and external traffic,and in some cases the external traffic volume is almost as high as that of local traffic.Whilst local traffic volume may be largely made up of the same regular local commuters making frequent trips,external traffic from outside of the city(region)may not be the same people making regular trips to/from the city.However,from a large pool of people making infrequent trips to/from the city,the existence of external traffic is proven by data from the licence plate recognition system of road vehicles in Changde,China.The function of value of time correlated with the income/wage rate and trip frequency is exploited and verified statistically.The time value distorted by trip frequency is defined as perceived time value(PTV),which also influences the way travellers perceive any travel impedance such as congestion delay and toll charges.This paper analyses the price of anarchy(POA)when explicitly considering the travel frequency of the trip-makers and their PTV,and compares with previous analysis without considering travel frequency.We show that when travel frequency is considered,the optimal toll of congested road pricing schemes which converts road traffic flow from user equilibrium into system optimization is much lower than that without considering travel frequency.The cost of licence plate auction cannot be treated as a congestion toll,which is only a threshold of vehicle ownership.That travellers choose routes by PTV rather than TV(time value)is proven by an example of Heishipu Bridge in Changsha,Hunan Province,China.

The Shortest First Coordination Mechanism for a Scheduling Game with Parallel-Batching Machines

This paper deals with a scheduling problem with parallel-batching machines from a game theoretic perspective.There are m parallel-batching machines,each of which can handle up to b jobs simultaneously as a batch.The processing time of a batch is the time required for processing the longest job in the batch,and all the jobs in a batch start and complete at the same time.There are n jobs.Each job is owned by a rational and selfish agent.The agent of a job chooses a machine for processing its own job.The aim of each agent is to minimize the completion time of its job while the system tries tominimize the maximal completion time over all jobs,the makespan.We design a coordination mechanism for the scheduling game problem.We discuss the existence of Nash equilibria of the mechanism and showthat it has a price of anarchy 2.

A SELFISH ROUTING BASED NETWORK IMPROVEMENT PROBLEM

This paper considers a selfish routing based network improvement problem, in which the authors would like to find a modified latency function that results in a new Nash equilibrium flow satisfying all traffic demands subject to the target capacity, while the total modification cost on edge latency is minimized. By using the reduction from the 3-Satisfiability （3-SAT） problem to our problem, the authors show that this problem is strongly NP-hard, even for the single commodity network.

Worst-Case Nash Equilibria in Restricted Routing

We study the network routing problem with restricted and related links. There are parallel links with possibly different speeds, between a source and a sink. Also there are users, and each user has a traffic of some weight to assign to one of the links from a subset of all the links, named his/her allowable set. The users choosing the same link suffer the same delay, which is equal to the total weight assigned to that link over its speed. A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link. To measure the performance degradation of the system due to the selfish behavior of all the users, Koutsoupias and Papadimitriou proposed the notion Price of Anarchy （denoted by PoA）, which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution. The PoA for this restricted related model has been studied, and a linear lower bound was obtained. However in their bad instance, some users can only use extremely slow links. This is a little artificial and unlikely to appear in a real world. So in order to better understand this model, we introduce a parameter for the system, and prove a better Price of Anarchy in terms of the parameter. We also show an important application of our result in coordination mechanism design for task scheduling game. We propose a new coordination mechanism, Group-Makespan, for unrelated selfish task scheduling game with improved price of anarchy.