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.     

考虑质量偏好的两阶段服务供应链质量控制策略

研究了一个集成商和一个提供商所组成的服务供应链的质量控制问题。考虑集成商的质量缺陷承诺和提供商的质量偏好,并将提供商的质量活动区分为质量改进和质量保持两个阶段,分别建立了服务供应链成员的效用函数,同时考虑服务供应链成员的竞争与合作,运用博弈理论,优化得到单阶段与两阶段时,集成商的最优服务价格和质量缺陷承诺,以及提供商的最优服务质量改进程度。最后,通过对比分析及数值仿真发现,考虑两阶段质量控制较单阶段情形,更有利于服务供应链较长期限内获得更多效用。其次,服务提供商质量偏好对服务供应链单阶段与两阶段下的最优效用和质量控制策略均产生一定影响。     

Infrastructure topology optimization under competition through cross-entropy

In this article, we study a two-level non-cooperative game between providers acting on the same geographic area. Each provider has the opportunity to set up a network of stations so as to capture as many consumers as possible. Its deployment being costly, the provider has to optimize both the number of settled stations as well as their locations. In the first level each provider optimizes independently his infrastructure topology while in the second level they price dynamically the access to their network of stations. The consumers’ choices depend on the perception (in terms of price, congestion and distances to the nearest stations) that they have of the service proposed by each provider. Each providers' market share is then obtained as the solution of a fixed point equation since the congestion level is supposed to depend on the market share of the provider, which increases with the number of consumers choosing the same provider. We prove that the two-stage game admits a unique equilibrium in price at any time instant. An algorithm based on the cross-entropy method is proposed to optimize the providers' infrastructure topology and it is tested on numerical examples providing economic interpretations.     

An Ergodic Algorithm for the Power-Control Games for CDMA Data Networks

In this paper, we consider power control for the uplink of a direct-sequence code-division multiple-access data network. In the uplink, the purpose of power control is for each user to transmit enough power so that it can achieve the required quality of service without causing unnecessary interference to other users in the system. One method that has been very successful in solving this purpose for power control is the game-theoretic approach. The problem for power control is modified as a Nash equilibrium problem in which each user can choose its transmit power in order to maximize its own utility, and a Nash equilibrium is an ideal solution of the power-control game. We present a noncooperative power-control game in which each user can choose the transmit power in a way that it gets the sufficient signal-to-interference-plus-noise ratio and maximizes its own utility. To ensure the existence of a solution, we also propose the variational inequality problem which is connected with the proposed game. On a linear receiver, we deal with the matched filter receiver. Next we present a new ergodic algorithm for the proposed power control because the existing iterative algorithms can not be applied effectively to the proposed power control. We also present convergence analysis for the proposed algorithm. In addition, applying the proposed algorithm to the proposed power control, we provide numerical examples for the transmit power, the signal-to-interference-plus-noise ratio and so on. Numerical results for the proposed algorithm shall show that as compared with the existing power-control game and its method, all users in the network can enjoy the sufficient signal-to-interference-plus-noise ratio and achieve the required quality of service.      

Stochastic Networks: Admission and Routing Using Penalty Functions

We propose an admission and routing control policy for a network of service facilities in a stochastic setting in order to maximize a long run average reward. Queueing and reneging before entering the network is allowed; we introduce orbiting as an approximation to the queueing. Once a customer has entered the network, it incurs no more waiting. Our control policy is easy to implement and we prove that it performs well in steady state as long as the capacity request sizes are relatively small compared to the capacity of the service facilities. The policy is a target tracking policy: a linear program provides a target operating point and an exponential penalty function is used to translate the optimal deterministic point into a feasible admission and routing policy. This translation essentially transforms the admission and routing control problem into a problem of load balancing via the construction of fictitious systems. Simulation studies are included to illustrate that our policy also performs well when request sizes are moderate or large with respect to the capacity.     

多用户类多准则交通分配的势博弈与拥挤定价

交通管理者在解决路网拥挤问题时,并不知道出行者的出行效用,同时管理者难以对出行者的路径选择行为做出准确的观测.运用势博弈理论分析多用户类多准则交通行为的演化过程,得到了固定需求和弹性需求情形下的可容许动态(一种刻画出行者通过转换路径增加当前效用的近似调整行为的演化动态),证明当路段时间函数和逆需求函数为严格单调、连续、可微时,所对应的交通分配是势博弈问题的惟一Nash均衡点.进一步研究了固定需求下的可变拥挤道路收费问题,得到了在当前系统状态下实现系统最优交通分配的拥挤收费水平.     

An auction model arising from an Internet search service provider

Most search service providers such as Lycos and Google either produce irrelevant search results or unstructured company listings to the consumers. To overcome these two shortcomings, search service providers such as GoTo.com have developed mechanisms for firms to advertise their services and for consumers to search for the right services. To provide relevant search results, each firm who wishes to advertise at the GoTo site must specify a set of keywords. To develop structured company listings, each firm bids for priority listing in the search results that appear on the GoTo site. Since the search results appear in descending order of bid price, each firm has some control over the order in which the firm appears on the list resulting from the search. In this paper, we present a one-stage game for two firms that captures the advertising mechanism of a search service provider (such as GoTo). This model enables us to examine the firm’s optimal bidding strategy and evaluate the impact of various parameters on the firm’s strategy. Moreover, we analyze the conditions under which all firms would increase their bids at the equilibrium. These conditions could be helpful to the service provider when developing mechanisms to entice firms to submit higher bids.     

A traffic shaping model for optimizing network operations

The management of technology in multi-service computer networks, such as university networks, has become a challenge with the explosive growth of entertainment oriented peer-to-peer (P2P) traffic. Traffic shaping is one of the tools used to manage bandwidth to improve system performance by allocating bandwidth between P2P and non-peer-to-peer (NP2P) traffic. We present a model for traffic shaping and bandwidth management that considers the trade-offs from allocating different amounts of bandwidths for different application categories and use data from a university network. The current policy allocates varying bandwidths over the day to P2P and NP2P traffic to reflect the importance of not letting entertainment based traffic choke the network during the day time at the expense of the more important traffic, such as Web traffic. We highlight the difficulties in obtaining data in the form required for analysis, and the need to estimate demand for allocations not covered by current policy. We present a goal programming model for this estimation task. We also model the traffic shaping problem as a Markov decision process and develop an algorithm for determining the optimal bandwidth allocation to maximize the utility of all users. Finally we use a numerical example to illustrate our approach.     

Top percentile network pricing and the economics of multi-homing

Top-Percentile pricing is a relatively new and increasingly popular pricing policy used by network providers to charge service providers. In contrast to fixed cost pricing and to pure per-usage pricing, top-percentile pricing has not been studied. Thus the efficient design and operation of networks under top-percentile pricing is not well understood yet. This work studies top-percentile pricing and provides an analysis of the expected costs it inflicts on a service provider. In particular we use our analysis framework to investigate the popular multi-homing architecture in which an Internet Service Provider (ISP) connects to the Internet via multiplicity of network providers. An ISP that uses multi-homing is subject to extra charges due to the use of multiple networks. Important questions that are faced by such an ISP are what is an efficient routing strategy (as to reduce costs) and how large the costs are. We provide a general formulation of this problem as well as its probabilistic analysis, and derive the expected cost faced by the ISP. We numerically examine several typical scenarios and demonstrate that despite the fact that this pricing aims at the peak traffic of the ISP (similarly to fixed cost), the expected bandwidth cost of multi-homing is not much higher than that of single-homing. Part of the results of this work was reported in Levy, Levy, and Kahana (2003). The work was done while J.Levy and Y. Kahana were with Comgates Ltd. and H. Levy was partially with Comgates Ltd.     

A Cournot–Nash–Bertrand game theory model of a service-oriented Internet with price and quality competition among network transport providers

This paper develops a game theory model of a service-oriented Internet in which profit-maximizing service providers provide substitutable (but not identical) services and compete with the quantities of services in a Cournot–Nash manner, whereas the network transport providers, which transport the services to the users at the demand markets, and are also profit-maximizers, compete with prices in Bertrand fashion and on quality. The consumers respond to the composition of service and network provision through the demand price functions, which are both quantity and quality dependent. We derive the governing equilibrium conditions of the integrated game and show that it satisfies a variational inequality problem. We then describe the underlying dynamics, and provide some qualitative properties, including stability analysis. The proposed algorithmic scheme tracks, in discrete-time, the dynamic evolution of the service volumes, quality levels, and the prices until an approximation of a stationary point (within the desired convergence tolerance) is achieved. Numerical examples demonstrate the modeling and computational framework.     

Microeconomics-based resource allocation in overlay networks by using non-strategic behavior modeling

Behavior modeling has recently been investigated for designing self-organizing mechanisms in the context of communication networks in order to exploit the natural selfishness of the users with the goal of maximizing the overall utility. In strategic behavior modeling, the users of the network are assumed to be game players who seek to maximize their utility with taking into account the decisions that the other players might make. The essential difference between the aforementioned researches and this work is that it incorporates the non-strategic decisions in order to design the mechanism for the overlay network. In this solution concept, the decisions that a peer might make does not affect the actions of the other peers at all. The theory of consumer-firm developed in microeconomics is a model of the non-strategic behavior that we have adopted in our research. Based on it, we have presented distributed algorithms for peers’ “joining” and “leaving” operations. We have modeled the overlay network as a competitive economy in which the content provided by an origin server can be viewed as commodity and the origin server and the peers who multicast the content to their downside are considered as the firms. On the other hand, due to the dual role of the peers in the overlay network, they can be considered as the consumers as well. On joining to the overlay economy, each peer is provided with an income and tries to get hold of the service regardless to the behavior of the other peers. We have designed the scalable algorithms in such a way that the existence of equilibrium price (known as Walrasian equilibrium price) is guaranteed.     

Dynamic overbooking scheduling system to improve patient access

Patient no-show has long been a recognized problem in modern outpatient health-care delivery systems. The common impacts are reduced clinic efficiency and provider productivity, wasted medical resources, increased health-care cost and limited patient access to care. The main goal of this research is to develop an effective dynamic overbooking policy into any scheduling system that accounts for the predictive probability of no-shows for any given patient. This policy increases the quality of patient care in terms of wait time and access to care while minimizing the clinic's costs. This proposed model is also illustrated to be more cost-effective than overbooking patients evenly throughout a clinic session. This paper also suggests that overbooking should be performed at better patient flow and higher no-show rate so that the costs are minimized. Consequently, this research improves the outpatient experience for both patients and medical providers.     

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     

Alliance or no alliance—Bargaining power in competing reverse supply chains

This work investigates how bargaining power affects negotiations between manufacturers and reverse logistics providers in reverse supply chains under government intervention using a novel three-stage reverse supply chain model for two scenarios, a reverse logistics provider alliance and no reverse logistics provider alliance. Utilizing the asymmetric Nash bargaining game, this work seeks equilibrium negotiation solutions. Analytical results indicate that the reverse logistics provider alliance increases the bargaining power of reverse logistics providers when negotiating with a manufacturer for a profitable recycled-component supply contract; however, manufacturer profits are often reduced. Particularly in the case of an recycled-component vender-dominated market, a reverse logistics alliance with extreme bargaining power may cause a counter-profit effect that results in the decreases of profits for all players involved, including buyers (i.e., manufacturers) and allied recycled-component venders (i.e., reverse logistics providers). Additional managerial insights are provided for discussion.     

Competition among providers in loss networks

Communication networks are becoming ubiquitous and more and more competitive among revenue-maximizing providers, operating on potentially different technologies. In this paper, we propose to analyze thanks to game theory the competition of providers playing with access prices and fighting for customers. Considering a slotted-time model, the part of demand exceeding capacity is lost and has to be resent. We consider an access price for submitted packets, thus inducing a congestion pricing through losses. Customers therefore choose the provider with the cheapest average price per correctly transmitted unit of traffic. The model is a two-level game, the lower level for the distribution of customers among providers, and the upper level for the competition on prices among providers, taking into account what the subsequent repartition at the lower level will be. We prove that the upper level has a unique Nash equilibrium, for which the user repartition among different available providers is also unique, and, remarkably, efficient in the sense of social welfare (with a so-called price of anarchy equal to one). Moreover, even when adding a higher level game on capacity disclosure with a possibility of lying for providers, providers are better off being truthful, and the unique Nash equilibrium is thus unchanged.     

Platform modelling and scheduling game with multiple intelligent cloud-computing pools for big data

We develop a generic game platform that can be used to model various real-world systems with multiple intelligent cloud-computing pools and parallel-queues for resources-competing users. Inside the platform, the software structure is modelled as Blockchain. All the users are associated with Big Data arrival streams whose random dynamics is modelled by triply stochastic renewal reward processes (TSRRPs). Each user may be served simultaneously by multiple pools while each pool with parallel-servers may also serve multi-users at the same time via smart policies in the Blockchain, e.g. a Nash equilibrium point myopically at each fixed time to a game-theoretic scheduling problem. To illustrate the effectiveness of our game platform, we model the performance measures of its internal data flow dynamics (queue length and workload processes) as reflecting diffusion with regime-switchings (RDRSs) under our scheduling policies. By RDRS models, we can prove our myopic game-theoretic policy to be an asymptotic Pareto minimal-dual-cost Nash equilibrium one globally over the whole time horizon to a randomly evolving dynamic game problem. Iterative schemes for simulating our multi-dimensional RDRS models are also developed with the support of numerical comparisons.     

产品服务化供应链核心企业的服务模式决策研究

在以系统集成商为主导的产品服务化供应链中,考虑顾客效用的情况下,将服务提供商单独提供服务和系统集成商与服务提供商共同提供服务这两种情形下的最优决策进行比较,发现当服务提供商单独提供服务时,随着服务成本的增加,服务提供商的服务水平会降低,从而导致顾客需求、顾客的总效用、服务提供商的收益、系统集成商的收益和供应链总收益均会降低。当系统集成商与服务提供商共同提供服务时,可以增加顾客需求,提高系统集成商的收益、供应链的总收益和顾客的总效用,但降低了服务提供商的收益。     

A stackelberg game approach to distributed spectrum management

We consider a cognitive radio system with one primary (licensed) user and multiple secondary (unlicensed) users. Given the interference temperature constraint, the secondary users compete for the available spectrum to fulfill their own communication need. Borrowing the concept of price from market theory, we develop a decentralized Stackelberg game formulation for power allocation. In this scheme, the primary user (leader) announces prices for the available tones such that a system utility is maximized. Using the announced prices, secondary users (followers) compete for the available bandwidth to maximize their own utilities. We show that this Stackelberg game is polynomial time solvable under certain channel conditions. When the individual power constraints of secondary users are inactive (due to strict interference temperature constraint), the proposed distributed power control method is decomposable across the tones and unlike normal water-filling it respects the interference temperature constraints of the primary user. When individual power constraints are active, we propose a distributed approach that solves the problem under an aggregate interference temperature constraint. Moreover, we propose a dual decomposition based power control method and show that it solves the Stackelberg game asymptotically when the number of tones becomes large.     

Application of duopoly multi-periodical game with bounded rationality in power supply market based on information asymmetry

In the power market, each entity is not completely rational when generate strategy, and the market information held by each entity is not exactly the same. In this paper, duopoly power providers with different selling adjustment structures are simplified from the actual grid background, where one provider can sell part of its power to another at contract price to store the power. Each provider is trying to maximize its profit by adjusting its power selling strategy. The process of evolutionary game with multi-periods bounded rational is established. One provider adjusts its selling strategy through the multi-periods market price and another through its multi-periods marginal profit. The quantity of power sold by each provider will tend to Nash equilibrium and how information asymmetry affects the stability of Nash equilibrium is analyzed through comparing dynamic power selling with and without information asymmetry. Information asymmetry has a great impact on one provider but not another. The numerical simulations also show that the information asymmetry will increase the stability region of the system. Different adjustment suggestions are proposed for different providers when information asymmetry occurs.     

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.