Mobile data traffic has been steadily rising in the past years. This has generated a significant interest in the deployment of incentive mechanisms to reduce peak-time congestion. Typically, the design of these mechanisms requires information about user demand and sensitivity to prices. Such information is naturally imperfect. In this paper, we propose a fixed-budget rebate mechanism that gives each user a reward proportional to his percentage contribution to the aggregate reduction in peak-time demand. For comparison, we also study a time-of-day pricing mechanism that gives each user a fixed reward per unit reduction of his peak-time demand. To evaluate the two mechanisms, we introduce a game-theoretic model that captures the public good nature of decongestion. For each mechanism, we demonstrate that the socially optimal level of decongestion is achievable for a specific choice of the mechanism's parameter. We then investigate how imperfect information about user demand affects the mechanisms' effectiveness. From our results, the fixed-budget rebate pricing is more robust when the users' sensitivity to congestion is "sufficiently" convex. This feature of the fixed-budget rebate mechanism is attractive for many situations of interest and is driven by its closed-loop property, i.e., the unit reward decreases as the peak-time demand decreases.
A few papers have proposed mechanisms with prices dependent on congestion levels. In @cite_11 , Paschalidis and Tsitsiklis propose a congestion-based pricing mechanism in the context of loss networks (i.e., phone). They provide a dynamic programming formulation of the revenue maximization problem and of the welfare maximization problem. Then, they show that this dynamic congestion pricing mechanism can be well approximated by a simpler static time-of-day pricing. An alternative mechanism called Trade & Cap'', was recently proposed by Londo n o, Bestavros and Laoutaris @cite_3 . It works in two phases. First, users engage in a trading game where they choose an amount of bandwidth slots to buy for hard-constraints traffic. In the second phase, the remaining bandwidth is allocated to users as bandwidth, in proportion of their remaining buying power''. They show that this mechanism smoothes the aggregate demand to a certain level. In their model, users have a cost function that increases linearly with the total demand in a given slot. In this paper, we consider simpler one-phase pricing mechanisms with fixed parameters. Our model also differ from these papers in that users have elastic demand and their utility is an arbitrary function of the congestion level.
@cite_3 @cite_11
2264445763 2123120471 2614461528 2253280018
Dynamic forms of resource pricing have recently been introduced by cloud providers that offer Infrastructure as a Service (IaaS) capabilities in order to maximize profits and balance resource supply and demand. The design of a mechanism that efficiently prices perishable cloud resources in line with a provider’s profit maximization goal remains an open research challenge, however. In this article, we propose the Online Extended Consensus Revenue Estimate mechanism in the setting of a recurrent, multiunit and single price auction for IaaS cloud resources. The mechanism is envy-free, has a high probability of being truthful, and generates a near optimal profit for the provider. We combine the proposed auction design with a scheme for dynamically calculating reserve prices based on data center Power Usage Effectiveness (PUE) and electricity costs. Our simulation-based evaluation of the mechanism demonstrates its effectiveness under a broad variety of market conditions. In particular, we show how it improves on the classical uniform price auction, and we investigate the value of prior knowledge on the execution time of virtual machines for maximizing profit. We also developed a system prototype and conducted a small-scale experimental study with a group of 10 users that confirms the truthfulness property of the mechanism in a real test environment. We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users initiate calls that belong to a set of diverse service classes, differing in resource requirements, demand pattern, and call duration. The SP charges a fee per call, which can depend on the current congestion level, and which affects users' demand for calls. We provide a dynamic programming formulation of the problems of revenue and welfare maximization, and derive some qualitative properties of the optimal solution. We also provide a number of approximate approaches, together with an analysis that indicates that near-optimality is obtained for the case of many, relatively small, users. In particular, we show analytically as well as computationally, that the performance of an optimal pricing strategy is closely matched by a suitably chosen static price, which does not depend on instantaneous congestion. This indicates that the easily implementable time-of-day pricing will often suffice. Throughout, we compare the alternative formulations involving revenue or welfare maximization, respectively, and draw some qualitative conclusions. Optimizing shared vehicle systems (bike-sharing car-sharing ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of complex network externalities. In particular, changes in the demand supply at any location (via dynamic pricing, rebalancing of empty vehicles, etc.) affect future supply throughout the system within short timescales. Such externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze and design shared vehicle systems. However, using such models to design pricing control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex. To this end, we develop a general approximation framework for designing pricing policies in shared vehicle systems, based on a novel convex relaxation which we term elevated flow relaxation. Our approach provides the first efficient algorithms with rigorous approximation guarantees for a wide range of objective functions (throughput, revenue, welfare). For any shared vehicle system with @math stations and m vehicles, our framework provides a pricing policy with an approximation ratio of 1+(n-1) m. This guarantee is particularly meaningful when m n, the average number of vehicles per station is large, as is often the case in practice. Further, the simplicity of our approach allows us to extend it to more complex settings. Apart from pricing, shared vehicle systems enable other control levers for modulating demand and supply, e.g. rebalancing empty vehicles, redirecting riders to nearby vehicles, etc. Our approach yields efficient algorithms with the same approximation guarantees for all these problems, and in the process, obtains as special cases several existing heuristics and asymptotic guarantees. We also extend our approach to obtain bi-criterion guarantees in multi-objective settings; we illustrate this with the example of Ramsey pricing. From a technical perspective, our work develops a new approach for obtaining control policies with approximation guarantees in steady-state Markovian models. Our approach can be distilled into the following three-step program: (i) construct an upper bound via a relaxation to the original problem that encodes essential conservation laws of the system, (ii) identify a family of control policies inducing known steady-state distributions that achieve the value of the relaxed solution in an appropriate scaling limit (in our case, state-independent policies in the limit m++), and (iii) characterize the performance loss between the finite system (i.e. fixed m) and the scaling limit. This technique may be of independent interest for other settings. We study a stylized revenue maximization problem for a provider of cloud computing services, where the service provider (SP) operates an infinite capacity system in a market with heterogeneous customers with respect to their valuation and congestion sensitivity. The SP offers two service options: one with guaranteed service availability, and one where users bid for resource availability and only the “winning” bids at any point in time get access to the service. We show that even though capacity is unlimited, in several settings, depending on the relation between valuation and congestion sensitivity, the revenue maximizing service provider will choose to make the spot service option stochastically unavailable. This form of intentional service degradation is optimal in settings where user valuation per unit time increases sub-linearly with respect to their congestion sensitivity (i.e., their disutility per unit time when the service is unavailable) – this is a form of “damaged goods.” We provide some data evidence based on the analysis of price traces from the biggest cloud service provider, Amazon Web Services.