The problem of pricing the cloud has attracted much recent attention due to the widespread use of cloud computing and cloud services. From a theoretical perspective, several mechanisms that provide strong efficiency or fairness guarantees and desirable incentive properties have been designed. However, these mechanisms often rely on a rigid model, with several parameters needing to be precisely known in order for the guarantees to hold. In this paper, we consider a stochastic model and show that it is possible to obtain good welfare and revenue guarantees with simple mechanisms that do not make use of the information on some of these parameters. In particular, we prove that a mechanism that sets the same price per time step for jobs of any length achieves at least 50 of the welfare and revenue obtained by a mechanism that can set different prices for jobs of different lengths, and the ratio can be improved if we have more specific knowledge of some parameters. Similarly, a mechanism that sets the same price for all servers even though the servers may receive different kinds of jobs can provide a reasonable welfare and revenue approximation compared to a mechanism that is allowed to set different prices for different servers.
Our work falls into the broader area of the design and analysis of simple mechanisms, particularly posted price mechanisms. One of the motivations for studying simple mechanisms is that in practice, designers are often willing to partially give up optimality in return for simplicity. Mechanisms that simply post prices on goods have received significant attention since they reflect perhaps the most common way of selling goods in the real world, and moreover they leave no room for strategizing, making them easy for agents to participate in. A long line of work has investigated how well such mechanisms can approximate optimal mechanisms with respect to various objectives including welfare @cite_17 @cite_7 @cite_18 , revenue @cite_10 @cite_16 @cite_6 , and social costs @cite_4 . In we show that techniques from this literature can recover some of our results under relaxed assumptions.
@cite_18 @cite_4 @cite_7 @cite_6 @cite_16 @cite_10 @cite_17
2615064102 1827565498 2010377201 161187638 2077124610 2950351404
We study the power and limitations of posted prices in markets with identical items, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer's information and agents' valuations. For example, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices. We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforcable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the k-server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially. The design of optimal auctions focuses on ways to negotiate with the bidders for eliciting relevant information that they hold. Sometimes, however, decisions should be made very quickly, and the auctioneer cannot allow a costly iterative procedure of negotiation or waiting for bidders to determine their exact valuation. One solution that has been used in practice is to post prices for the bidders, without collecting any information from the bidders, and ask for their immediate take-it-or-leave-it response. Our paper compares the expected revenue in full-revelation auctions to that in posted-price auctions. We focus on single-item auctions in a Bayesian model where the values that the bidders are willing to pay for the item are independently identically distributed according to a known distribution. This paper provides an exact asymptotic characterization of the optimal expected revenue achieved by each one of the above auctions. For posted price auctions, we also present the exact prices that achieve the optimal results.Our results are given up to terms with lower asymptotic order, that is, up to factor of 1--o(1). We provide two sets of results; one for distributions on a support that is bounded from above, and a second set for distributions on unbounded supports. In the first case we require a mild assumption on the way the distribution function approaches the end of the support, called the first von Mises condition; the latter case requires a similar mild condition called the second von Mises condition. These very weak conditions are taken from works on extreme-value theory and highest-order statistics. We consider a dynamic auction model, where bidders sequentially arrive to the market. The values of the bidders for the item for sale are independently drawn from a distribution, but this distribution is unknown to the seller. The seller offers a personalized take-it-or-leave-it price for each arriving bidder and aims to maximize revenue. We study how well can such sequential posted-price mechanisms approximate the optimal revenue that would be achieved if the distribution was known to the seller. On the negative side, we show that sequential posted-price mechanisms cannot guarantee a constant fraction of this revenue when the class of candidate distributions is unrestricted. We show that this impossibility holds even for randomized mechanisms and even if the set of possible distributions is very small or when the seller has a prior distribution over the candidate distributions. On the positive side, we devise a simple posted-price mechanism that guarantees a constant fraction of the known-distribution revenue when all candidate distributions exhibit the monotone hazard rate property. We study the classic mathematical economics problem of Bayesian optimal mechanism design where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [20]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [1], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [25]. In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. We prove that these mechanisms are approximately optimal in single-dimensional settings. These posted-price mechanisms avoid many of the properties of optimal mechanisms that make the latter impractical. Furthermore, these mechanisms generalize naturally to multi-dimensional settings where they give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time. This work can be viewed as an extension and improvement of the single-agent algorithmic pricing work of [9] to the setting of multiple agents where the designer has combinatorial feasibility constraints on which agents can simultaneously obtain each service. We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In a posted price mechanism, item prices are posted, then the consumers approach the seller sequentially in an arbitrary order, each purchasing her favorite bundle from among the unsold items at the posted prices. These mechanisms are simple, transparent and trivially dominant strategy incentive compatible (DSIC). We show that when agent preferences are fractionally subadditive (which includes all submodular functions), there always exist prices that, in expectation, obtain at least half of the optimal welfare. Our result is constructive: given black-box access to a combinatorial auction algorithm A, sample access to the prior distribution, and appropriate query access to the sampled valuations, one can compute, in polytime, prices that guarantee at least half of the expected welfare of A. As a corollary, we obtain the first polytime (in n and m) constant-factor DSIC mechanism for Bayesian submodular combinatorial auctions, given access to demand query oracles. Our results also extend to valuations with complements, where the approximation factor degrades linearly with the level of complementarity.