Jeffrey K. MacKie-Mason

Price Prediction Strategies for Market-Based Scheduling (Download full paper)

MacKie-Mason, Jeffrey K. Osepayshvili, Anna Reeves, Daniel M. Wellman, Michael P.

Published on: June, 2004

Abstract: In a market-based scheduling mechanism, the allocation of time-specific resources to tasks is governed by a competitive bidding process. Agents bidding for multiple, separately allocated time slots face the risk that they will succeed in obtaining only part of their requirement, incurring expenses for potentially worthless slots. We investigate the use of price prediction strategies to manage such risk. Given an uncertain price forecast, agents follow simple rules for choosing whether and on which time slots to bid. We find that employing price predictions can indeed improve performance over a straightforward baseline in some settings. Using an empirical game-theoretic methodology, we establish Nash equilibrium profiles for restricted strategy sets. This allows us to con- firm the stability of price-predicting strategies, and measure overall efficiency. We further experiment with variant strategies to analyze the source of prediction's power, demonstrate the existence of self-confirming predictions, and compare the performance of alternative prediction methods.

The Case for Market-based Push Caching (Download full paper)

MacKie-Mason, Jeffrey K. Chan, Yee Man Womer, Jonathan Jamin, Sugih

Published on: November, 1999

Biased Replacement Policies for Web Caches: Differential Quality-of-Service and Aggregate User Value (Download full paper)

MacKie-Mason, Jeffrey K. Kelly, Terence P. Chan, Yee Man Jamin, Sugih

Published on: January, 1999

Abstract: Disk space in shared Web caches can be diverted to serve some system users at the expense of others. Cache hits reduce server loads, and if servers desire load reduction to different degrees, a replacement policy which prioritizes cache space across servers can provide differential quality-of-service (QoS). We present a simple generalization of least-frequently-used (LFU) replacement that is sensitive to varying levels of server valuation for cache hits. Through trace-driven simulation we show that under a particular assumption about server valuations our algorithm delivers a reasonable QoS relationship: higher byte hit rates for servers that value hits more. We furthermore adopt the economic perspective that value received by system users is a more appropriate performance metric than hit rate or byte hit rate, and demonstrate that our algorithm delivers higher "social welfare" (aggregate value to servers) than LRU or LFU.

Some Economics of Market-Based Distributed Scheduling (Download full paper)

MacKie-Mason, Jeffrey K. Walsh, William E. Wellman, Michael P. Wurman, Peter

Published on: May, 1998

Abstract: Market mechanisms solve distributed scheduling problems by allocating the scheduled resources according to market prices. We model distributed scheduling as a discrete resource allocation problem, and demonstrate the applicability of economic analysis to this framework. Drawing on results from the literature, we discuss the existence of equilibrium prices for some general classes of scheduling problems, and the quality of equilibrium solutions. We then present two protocols for implementing market solutions, and analyze their computational and economic properties.

Pricing Congestible Resources (Download full paper)

MacKie-Mason, Jeffrey K. and Hal Varian

Published on: September, 1995

Abstract: We describe the basic economic theory of pricing a congestible resource such as an ftp server, a router, a Web site, etc. In particular, we examine the implications of "congestion pricing" as a way to encourage efficient use of network resources. We explore the implications of flat pricing and congestion pricing for capacity expansion in centrally planned, competitive, and monopolistic environments

Generalized Vickrey Auctions (Download full paper)

Varian, Hal R. and Jeffrey K. MacKie-Mason

Published on: July, 1994

Abstract: We describe a generalization of the Vickrey auction. Our mechanism extends the auction to implement efficient allocations for problems with more than one good, multiple units for the goods, and externalities. The primary restriction on preferences is that they must be quasilinear.

A Smart Market for Resource Reservation in a Multiple Quality of Service Information Network (Download full paper)

MacKie-Mason, Jeffrey K.

Abstract: The technology is nearly available to offer remarkably powerful new communications services: multiple streams, from multiple users, composed of different applications that require different qualities of service (QoS), all travelling over a single interconnected physical infrastructure. Society will benefit from integrated applications (video conferencing with interactive demos and shared whiteboards; computer-integrated telephony, etc.). However, we are a long way from from free, broadband, "anytime, anywhere" integrated services networks. Allocation of scarce resources in a multiple quality of service network may be the single greatest barrier to communications anytime, anywhere. In this paper I present a fairly general model of the problem, and, after showing that a decentralized open market will fail, I propose a "smart market" mechanism for solving the problem. The smart market implements simultaneously efficient routing and bandwidth allocation for reservations made in advance. As computing speed improves, the length of the advance reservation interval can be shortened.

Feedback And Efficiency In ATM Networks (Download full paper)

Murphy, Liam, John Murphy, and Jeffrey K. MacKie-Mason

Abstract: Admission control and congestion control can provide performance guarantees in ATM networks. However some users may not be able to describe their traffic accurately enough for the network to provide these guarantees. By sending a dynamic feedback signal about the current utilization of network resources, the network could provide some guarantees to adaptive users who respond appropriately: this is the basis of ABR service. We outline a user-oriented framework for network operation and control, explicitly defining how such feedback is generated by the network and what form it takes. We show through simulations that it is possible to simultaneously gain both network and economic efficiency by using a form of feedback we call responsive pricing, which is compatible with current ATM Forum UNI specifications.

The Role of Responsive Pricing in the Internet (Download full paper)

MacKie-Mason, Jeffrey K., Liam Murphy and John Murphy

Abstract: The recent introduction of user-friendly navigation and retrieval tools for the World Wide Web has triggered an unprecedented level of interest in the Internet among the media and the general public, as well as in the technical community. It seems inevitable that some changes or additions are needed in the control mechanisms used to allocate usage of Internet resources. We argue that a feedback signal in the form of a variable price for network service is a workable tool to aid network operators in controlling Internet traffic. We suggest that these prices should vary dynamically based on the current utilization of network resources. We show how this responsive pricing puts control of network service back where it belongs: with the users.

Some Economics of the Internet (Download full paper)

MacKie-Mason, Jeffrey K. and Hal Varian

Abstract: This paper overlaps substantially with the paper Pricing the Internet. We describe the history, technology and costs of the Internet (at greater length than in "Pricing"). We describe a "smart market" for pricing Internet congestion. There is more attention to the smart market, and less to other pricing considerations, than in "Pricing."

Economic FAQs About the Internet (Download full paper)

MacKie-Mason, Jeffrey K. and Hal Varian

Abstract: We present some economic FAQs about the Internet in question-and-answer format. Updated, Summer 1995.

Pricing the Internet (Download full paper)

MacKie-Mason, Jeffrey K. and Hal Varian

Abstract: We describe the technology and costs of the Internet, then discuss how to design efficient pricing in order to allocate scarce Internet resources. We offer a "smart market" as a device to efficiently price congestion.

Some FAQs about Usage-Based Pricing (Download full paper)

MacKie-Mason, Jeffrey K. and Hal Varian

Abstract: Written for WWW '94 (Chicago). We answer some frequently asked questions about usage-sensitive pricing for Internet resources.