A Stackelberg Network Game with a Large Number of Followers

We consider a hierarchical network game with multiple links, a single service provider, and a large number of users with multiple classes, where different classes of users enter the network and exit it at different nodes. Each user is charged by the service provider a fixed price per unit of bandwidth used on each link in its route, and chooses the level of its flow by maximizing an objective function that shows a tradeoff between the disutility of the payment to the service provider and congestion cost on the link the user uses, and the utility of its flow. The service provider, on the other hand, wishes to maximize the total revenue it collects. We formulate this problem as a leader-follower (Stackelberg) game, with a single leader (the service provider, who sets the price) and a large number of Nash followers (the users, who decide on their flow rates). We show that the game admits a unique equilibrium, and obtain the solution in analytic form. A detailed study of the limiting case where the number of followers is large reveals a number of interesting and intuitive properties of the equilibrium, and answers the question of whether and when the service provider has the incentive to add additional capacity to the network in response to an increase in the number of users on a particular link.     

Braess's Paradox in large random graphs

Braess's Paradox is the counterintuitive fact that removing edges from a network with “selfish routing” can decreasethe latency incurred by traffic in an equilibrium flow. We prove that Braess's Paradox is likely to occur in a natural random network model: with high probability, there is a traffic rate and a set of edges whose removal improves the latency of traffic in an equilibrium flow by a constant factor. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

An N-path user equilibrium for transportation networks

The traditional trip-based approach to transportation modeling has been employed for the past decade. The last step of the trip-based modeling approach is traffic assignment, which has been typically formulated as a user equilibrium (UE) problem. In the conventional perspective, the definition of UE traffic assignment is the condition that no road user can unilaterally change routes to reduce their travel time. An equivalent definition is that the travel times of all the used paths between any given origin–destination pair are equal and less than those of the unused paths. The underlying assumption of the UE definition is that road users have full information on the available transportation paths and can potentially use any path if the currently used path is overly congested. However, a more practical scenario is that each road user has a limited path set within which she/he can choose routes from. In this new scenario, we call the resulting user equilibrium an N-path user equilibrium (NPUE), in which each road user has only N paths to select from when making route choices in the network. We introduce a new formulation of the NPUE and derive optimality conditions based on this formulation. Different from traditional modeling framework, the constraints of the proposed model are of linear form, which makes it possible to solve the problem with conventional convex programming techniques. We also show that the traditional UE is a special case of an NPUE and prove the uniqueness of the resulting flow pattern of the NPUE. To efficiently solve this problem, we devise path-based and link-based solution algorithms. The proposed solution algorithms are empirically applied to networks of various sizes to examine the impact of constrained user path sets. Numerical results demonstrate that NPUE results can differ significantly from UE results depending on the number of paths available to road users. In addition, we observed an interesting phenomenon, where increasing the number of paths available to road users can sometimes decrease the overall system performance due to their selfish routing behaviors. This paradox demonstrates that network information should be provided with caution, as such information can do more harm than good in certain transportation systems.     

Bottleneck routing with elastic demands

Bottleneck routing games are a well-studied model to investigate the impact of selfish behavior in communication networks. In this model, each user selects a path in a network for routing her fixed demand. The disutility of a user only depends on the most congested link visited. We extend this model by allowing users to continuously vary the demand rate at which data is sent along the chosen path. As our main result we establish tight conditions for the existence of pure strategy Nash equilibria.     

Chaos in a dynamic model of urban transportation network flow based on user equilibrium states

In this study, we investigate the dynamical behavior of network traffic flow. We first build a two-stage mathematical model to analyze the complex behavior of network flow, a dynamical model, which is based on the dynamical gravity model proposed by Dendrinos and Sonis [Dendrinos DS, Sonis M. Chaos and social-spatial dynamic. Berlin: Springer-Verlag; 1990] is used to estimate the number of trips. Considering the fact that the Origin–Destination (O–D) trip cost in the traffic network is hard to express as a functional form, in the second stage, the user equilibrium network assignment model was used to estimate the trip cost, which is the minimum cost of used path when user equilibrium (UE) conditions are satisfied. It is important to use UE to estimate the O–D cost, since a connection is built among link flow, path flow, and O–D flow. The dynamical model describes the variations of O–D flows over discrete time periods, such as each day and each week. It is shown that even in a system with dimensions equal to two, chaos phenomenon still exists. A “Chaos Propagation” phenomenon is found in the given model.     

Turning restriction design in traffic networks with a budget constraint

The restriction (prohibition) of certain turns at intersections is a very common task employed by the managers of urban traffic networks. Surprisingly, this approach has received little attention in the research literature. The turning restriction design problem (TRDP) involves finding a set of turning restrictions at intersections to promote flow in a congested urban traffic network. This article uses a successive linear approximation (SLA) method for identifying approximate solutions to a nonlinear model of the TRDP. It aims to adjust the current turning restriction regime in a given network in order to minimize total user travel cost when route choice is driven by user equilibrium principles. Novel features of the method include the facts that it is based on link capacity-based arc travel costs and there is a budget constraint on the total cost of all turning restriction alterations. It has been tested using standard network examples from the literature. One of the tests utilized a multi-start approach which improved the solutions produced by the SLA method. The method was also employed to identify turning restrictions for an actual medium-sized urban traffic network in Brazil. Computational experience with the proposed method is promising.     

The concert queueing game: strategic arrivals with waiting and tardiness costs

We consider the noncooperative choice of arrival times by individual users, who seek service at a first-come first-served queueing system that opens up at a given time. Each user wishes to obtain service as early as possible, while minimizing the expected wait in the queue. This problem was recently studied within a simplified fluid-scale model. Here, we address the unscaled stochastic system, assuming a finite (possibly random) number of homogeneous users, exponential service times, and linear cost functions. In this setting, we establish that there exists a unique Nash equilibrium, which is symmetric across users, and characterize the equilibrium arrival-time distribution of each user in terms of a corresponding set of differential equations. We further establish convergence of the Nash equilibrium solution to that of the associated fluid model as the number of users is increased. We finally consider the price of anarchy in our system and show that it exceeds 2, but converges to this value for a large population size.     

Capacitated transit assignment with loading priorities

In a transit network involving vehicles with rigid capacities, we advocate the use of strategies for describing consumer behavior. At each boarding node, a user sorts the transit lines in decreasing order of preference, and boards the first vehicle in this list whose residual capacity is nonzero. Since a users position in the queue varies from day to day, the delay experienced is stochastic. This leads to an equilibrium problem where, at a solution, users are assigned to strategies that minimize their expected delay. This situation is formulated as a variational inequality, whose cost mapping is discontinuous and strongly asymmetric, due to the priority of current passengers over incoming users. We prove that the solution set is nonempty and provide numerical results obtained by an efficient solution algorithm.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) and by the Fonds pour la formation de chercheurs et laide à la recherche (FCAR).Mathematics Subject Classification (2000):20E28, 20G40, 20C20Accepted: December 20, 2003     

交通网络建设序列的动态规划方法

交通网络建设序列优化是交通规划中一个重要问题。文章对交通网络设计及其建设序列问题的研究现状进行了分析。按照网络建设中规划者和用户间的关系,以交通网络建设序列下的各阶段系统总费用作为上层规划,以各阶段的交通流用户平衡模型作为下层规划,建立了双层规划模型。并依照问题的特点,采用动态规划的求解方法进行探讨,而下层模型则采用了基于路径搜索的GP算法进行求解。并针对网络规划算例进行了计算,针对固定和变动客流OD两种情况下的结果进行了分析。计算的结果表明,问题的双层规划模型和动态规划求解算法能够为路网规划决策提供支持。     

On Cost Allocation in Hub-Like Networks

We consider telecommunication network design in which each pair of nodes can communicate via a direct link and the communication flow can be delivered through any path in the network. The cost of flow through each link is discounted if and only if the amount of flow exceeds a certain threshold. This exploitation of economies of scale encourages the concentration of flows and use of relatively small number of links. We will call such networks hub-like networks. The cost of services delivered through a hub-like network is distributed among its users who may be individuals or organizations with possibly conflicting interests. The cooperation of these users is essential for the exploitation of economies of scale. Consequently, there is a need to find a fair distribution of the cost of providing the service among users of such network. In order to describe this cost allocation problem we formulate the associated cooperative game, to be referred to as the hub-like game. Special attention is paid to users' contribution to economies of scale. We then demonstrate that certain cost allocation solutions (the core and the nucleolus of the hub-like game), which provide users with the incentive to cooperate, can be efficiently characterized.     

不确定性自私路由模型的理论和应用

为了更加准确地描述现实生活中的交通情况,以经典的自私路由模型为基础,在边的费用函数上引入不确定性,从而定义了具有不确定性的自私路由模型.对于不确定性自私路由模型,采用三种费用衡量标准,风险厌恶型（保守型）、风险折衷型（理智型）、风险偏好型（乐观型）,分别对应着不同人群在现实中的选择.进而定义了在不同衡量标准下所形成的稳定策略,即纳什均衡策略,并且证明了在任何一种衡量标准下,纳什均衡策略总是存在并且本质是唯一的.接着对三种费用衡量标准下的纳什均衡费用进行了比较,发现了一种反直观的现象：风险厌恶型（保守型）衡量标准下的纳什均衡费用可能严格低于风险偏好型（乐观型）衡量标准下的纳什均衡费用,即有可能会出现高风险低回报,低风险高回报的情况,这与经济学中高风险高回报,低风险低回报的原则是相违背的.以此为基础,进而提出了一种自私路由风险性悖论,并证明了这种自私路由风险回报悖论本质上是传统布雷斯悖论的推广.最后,刻画出了不会发生自私路由风险回报悖论的网络结构,证明了一个单对始终点网络不会发生自私路由风险回报悖论当且仅当它是序列-平行网络.     

考虑平台影响因素的虚拟社区知识共享演化博弈研究

知识共享是虚拟社区用户学习和传播知识的重要途径。本文考虑到虚拟社区平台对参与用户知识共享行为的激励作用,引入平台的奖励和不分享知识所产生的机会成本,以及知识共享收益因素,构建考虑虚拟社区平台影响因素的虚拟社区知识共享演化博弈支付矩阵,并求得演化均衡解。通过小米社区的案例引入,仿真模拟平台对用户知识共享的奖励、机会成本、收益分配系数以及参与用户共享程度等因素对参与用户知识共享行为意愿的影响。研究发现:虚拟社区参与用户的知识共享意愿对因为知识共享所产生新知识的收益系数变化较为敏感;平台的奖励以及不分享知识所产生的机会成本对用户知识共享意愿影响巨大;同时,不同参与用户因为知识水平层次不同,参与知识共享的目的也不相同,这会影响到他们的知识共享策略选择。     

EXISTENCE OF STRONGLY VALID TOLLS FOR MULTICLASS NETWORK EQUILIBRIUM PROBLEMS＊

In this article,we consider the multiclass network equilibrium problems.A so called strongly valid toll can support any multiclass user equilibrium flow pattern as a system minimum when the system obje...     

Short-term and long-term competition between providers of shrink-wrap software and software as a service

Software as a service (SaaS) has moved quickly from a peripheral idea to a mainstream phenomenon. By bundling a software product with delivery and maintenance service, SaaS providers can effectively differentiate their products with traditional shrink-wrap software (SWS). This research uses a game theoretical approach to examine short- and long-term competition between SaaS and SWS providers. We analyze the factors that affect equilibrium outcomes, including user implementation costs, SaaS provider’s operation efficiency, and quality improvement over time. Bundling software with service lowers software implementation cost for users, and our results suggest that it increases equilibrium prices. In providing software services, SaaS providers have to incur significant operation cost. In the long run, service operation cost may significantly affect SaaS firm’s ability to improve its software quality.     

Integrating link-based discrete credit charging scheme into discrete network design problem

In this paper, we present an optimization model for integrating link-based discrete credit charging scheme into the discrete network design problem, to improve the transport performance from the perspectives of both transport network planning and travel demand management. The proposed model is a mixed-integer nonlinear bilevel programming problem, which includes an upper level problem for the transport authority and a lower level problem for the network users. The lower level sub-model is the traffic network user equilibrium (UE) formulation for a given network design strategy determined by the upper level problem. The network user at the lower level tries to minimize his/her own generalized travel cost (including both the travel time and the value of the credit charged for using the link) by choosing his/her route. While the transport authority at the upper level tries to find the optimal number of lanes and credit charging level with their locations to minimize the total system travel time (or maximize the transportation system performance). A genetic algorithm is used to solve the proposed mixed-integer nonlinear bilevel programming problem. Numerical experiments show the efficiency of the proposed model for traffic congestion mitigation, reveal that interaction effects across the tradable credit scheme and the discrete network design problem which amplify their individual effects. Moreover, the integrated model can achieve better performance than the sequential decision problems.     

Random queues and risk averse users

We analyze Nash equilibrium in time of use of a congested facility. Users are risk averse with general concave utility. Queues are subject to varying degrees of random sorting, ranging from strict queue priority to a completely random queue. We define the key “no residual queue” property, which holds when there is no queue at the time the last user arrives at the queue, and prove that this property holds in equilibrium under all queueing regimes considered. The no residual queue property leads to simple results concerning the equilibrium utility of users and the timing of the queue.     

带参量的非合作装箱博弈

带参量的非合作装箱博弈是指:每个物品的尺寸都介于0和参量x(0相似文献   

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

The Downs-Thomson Paradox: Existence, Uniqueness and Stability of User Equilibria

Consider a network where two routes are available for users wishing to travel from a source to a destination. On one route (which could be viewed as private transport) service slows as traffic increases. On the other (which could be viewed as public transport) the service frequency increases with demand. The Downs-Thomson paradox occurs when improvements in service produce an overall decline in performance as user equilibria adjust. Using the model proposed by Calvert [10], with a ⋅|M|1 queue corresponding to the private transport route, and a bulk-service infinite server queue modelling the public transport route, we give a complete analysis of this system in the setting of probabilistic routing. We obtain the user equilibria (which are not always unique), and determine their stability.AMS subject classification: 60K30, 90B15, 90B20, 91A10, 91A13This revised version was published online in June 2005 with corrected coverdate     

The Problem of Capacity Addition in Multi-user Elastic Demand Communication Networks

In this paper we consider some properties on prices under flow control in a network that is to be shared by noncooperative users. Each user is faced with an optimization problem which is formulated as the minimization of its own criterion subject to constraint on the flows of the other users. The operating points of the network are the Nash equilibria of the underlying routing game. Our objective is to study the behavior of prices of all users when the network designer needs to allocate capacities to network links. For parallel links topologies, we show that degradation of the performances such as prices will not take place, as well as the users may find it beneficial to improve their requests