\up Markets are Dead, Long Live Markets
phvr at 12pt
Researchers have long proposed using economic approaches to resource allocation in computer systems. However, few of these proposals became operational, let alone commercial. Questions persist about the economic approach regarding its assumptions, value, applicability, and relevance to system design. The goal of this paper is to answer these questions. We find that market-based resource allocation is useful, and more importantly, that mechanism design and system design should be integrated to produce systems that are both economically and computationally efficient.
abstract.tex
\begin{abstract}
\small
Researchers have long proposed using economic approaches to resource
allocation in computer systems. However, few of these proposals became
operational, let alone commercial. Questions persist about the
economic approach regarding its assumptions, value, applicability, and
relevance to system design. The goal of this paper is to answer these
questions. We find that market-based resource allocation \emph{is}
useful, and more importantly, that mechanism design and system design
should be integrated to produce systems that are both economically and
computationally efficient.

\end{abstract}



economics.tex
\section{Resource Allocation Markets}
\label{sec:economics}

In this section, we examine some questions about market-based resource
allocation.

%% \subsection{Do users behave strategically?}
%% \label{sec:strategic_behavior}
%% In particular, do users consume resources that others would benefit
%% more from, thus leading to low overall economic inefficiency? If this
%% is false, a market is unnecessary. 

%% Hardin~\cite{hardin1968} named this effect the ``Tragedy of the
%% Commons''.  It is a basic assumption of economics, game theory, and
%% businesses such as EBay, so this it is likely to have at least some
%% general validity. The question is whether it applies specifically to
%% computer systems. In fact, there are currently several examples from
%% systems. Adar and Huberman~\cite{adar2000} showed that free-riding (a
%% form of strategic behavior) on the peer-to-peer file sharing system
%% Gnutella was widespread. Spam, denial-of-service attacks, and spyware
%% are all examples where even a few highly strategic users can consume
%% resources that would otherwise benefit other users and wreak havoc on
%% the system. On PlanetLab, strategic behavior manifests as users who
%% continuously consume resources (even during very high demand periods)
%% even though they would receive nearly as much benefit by running at
%% low demand periods.

%% These are examples of overt strategic behavior, but more covert
%% strategic behavior is also harmful. Suppose that Alice has coded her
%% program so that it meets her performance goals with the resources
%% available to her.  However, she could code it to use fewer resources.
%% Meanwhile, Bob needs more resources than are available to him.  If the
%% cost for Alice to optimize her program is less than the benefit that
%% Bob would receive from the extra resources, then this is an
%% inefficient situation.  Without an economic mechanism, Alice does not
%% have an incentive to fix her program.

%% % XXX Can cut this para
%% This is not to say that all users are highly strategic and attempt to
%% cheat each other at every opportunity. Neither are they completely
%% obedient. Instead, most are moderately strategic, where the desire for
%% more resources is balanced by attention to the more traditional
%% systems metrics of computational efficiency, reliability, security,
%% complexity, and ease-of-use. Similarly, the attention of system
%% designers, especially those designing scalable systems, should also be
%% balanced with equal concern given to strategic behavior.

%% \subsection{Are markets useful for systems with low utilization?}
%% \label{sec:utilization}
%% Given that most systems, whether they are servers or network links,
%% have low mean utilization, this is an important question. This is
%% related to the question of whether resource allocation in general is
%% useful for low utilization systems. 

%% If a system has uniformly low utilization, then it is unlikely that
%% resource allocation is going to improve things. However, many systems
%% have a bursty load. Examples are web servers, databases, and
%% routers. In this case, there will be periods of contention when the
%% performance of the system is dependent on resource allocation
%% decisions. Although uncommon, these busy periods are important from a
%% reliability perspective because it is when requests time out, have to
%% be dropped, etc.

%% In addition, many systems have low utilization because they are not
%% being shared. Applications are frequently isolated on their own
%% private platforms. This results in some systems being completely
%% loaded and most others sitting idle. Experience with the Internet and
%% PlanetLab suggests that when applications are moved from isolated systems
%% to a shared-resource system, the resources become more utilized.

\subsection{What benefits do markets provide over long-term PS?} 
\label{sec:fixed_pricing}

In long-term Proportional Share, user $i$'s share of the resources is
$w_i / \sum w$ over a longer time period (e.g., a week or year) than
the $10$ milliseconds of a typical CPU scheduler. This provides some
of the flexibility of a market-based system. 

However, long-term PS is not sufficient to reach economic
efficiency. It does not encourage users to shift usage from high
demand periods to low demand periods. It also does not encourage users
to shift usage from high demand resources to low demand resources. For
example, a system could have high demand for CPU cycles, but low
demand for physical memory. In a typical application of PS, the CPU
and memory would be allocated separately and applications would have
no incentive to use more memory and fewer CPU cycles \cite{sullivan2000}. 

\begin{figure}[htb]
\includegraphics[width=8cm]{figures/pricing/pricing}
\caption{\small {\bf Fixed and Variable Pricing.} This figure shows a
  variable demand curve over time and how its efficiency compares to a
  fixed pricing curve.}
\label{fig:pricing}
\end{figure}

A related solution is to use fixed pricing. For example, each CPU
cycle costs \$10 and each memory page costs \$1. A user in this
example has a strong incentive to use more memory to save CPU cycles,
so this begins to address the multi-resource problem. Pricing also
provides a way for applications to express quality-of-service needs.
For example, an application may not need many cycles, but instead
needs them quickly after an interrupt has occurred
\cite{duda1999}. Time slices could be priced differently based on how
quickly they are scheduled.

The problem is how these prices should be
set. Figure~\ref{fig:pricing} shows that no fixed price is as
efficient as a variable price, assuming variable demand.  In the left
regime, the demand is below the fixed price, so the buyer is unwilling
to buy the resource and the utility that the buyer would have gained
by using the resource is unrealized (indicated by the striped area
under the demand curve). In the middle regime, someone is willing the
pay the fixed price, so that buyer is able to use the resource and
gains some utility (indicated by the gray area under the demand
curve). Assuming that the seller chooses the optimally efficient buyer
(i.e., the one willing to pay the most), then the difference between
the demand curve and the fixed price is unrealized profit for the
seller (indicated by the striped gray area).  Unrealized profit
contributes to overall inefficiency in some cases (see
\Section~\ref{sec:money}). However, without a covert channel, a fixed
price seller cannot distinguish among the demand curves of potential
buyers, so the actual buyer's demand curve will probably be lower than
the optimal buyer's and the area between them is more unrealized
utility. In general, the more variable the demand, the worse the
efficiency loss of fixed prices.

One definition of a market is a way to set prices so that they follow
the demand. As a result, most, if not all of the utility under the
demand curve in Figure~\ref{fig:pricing} would be realized. 

\subsection{Are markets fair?}
\label{sec:fairness}

Markets allow users to save currency. Could this allow a user to save
enough currency to starve out other users? Are markets unfair in some
other way?

Whether markets are fair depends on the market and the definition of
fair. One definition is that all users receive resources in proportion
to an exogenously determined weighting system. For example, if Alice
has a weight of $2$ and Bob has a weight of $1$, Alice should get
twice the resources of Bob over an arbitrarily long time interval.
Assuming that Alice and Bob have demand curves that equally correlated
with the overall demand, the market described in
\Section~\ref{sec:example} is fair by this definition. 

%% One definition is that all users of a fair system receive the
%% same amount of resources all the time. According to this, markets are
%% not fair. However, this results in a very inefficient allocation
%% because users have less incentive to reduce resource usage, move usage
%% to periods of low demand, etc. than in a market system.

One variation of this definition is to restrict the timescale used to
measure the resource usage. For example, within an hour interval, if
Alice and Bob want resources, she should always get twice the
resources that he gets, even though he saved up his credits and she
spent hers. This is useful to prevent starvation by those who
mis-manage their resources. Another possibility is that Bob saves up
credits over a long period of time and then spends them all at once,
thus starving out Alice. In both cases, the system can monitor Alice
and Bob's credits and redistribute credits from the wealthy to the
poor. This reduces the degree of unfairness, but also reduces
efficiency because Alice and Bob have a reduced incentive manage
resource usage carefully.

The conclusion is that markets are not inherently unfair. System
designers can tune a market-based system to make the tradeoff between
efficiency and fairness that is appropriate for their users. 

\subsection{Are markets useful when real money is not involved?}
\label{sec:money}
Economic mechanisms provide an intuitive mapping between resource
allocation and a business model for selling resources. However, in
some cases, the resources are just being shared and not sold (e.g.,
employees sharing machines in their company's data center). 

Markets are still useful in these situation. The simplest
configuration is an open-loop economy, where the resource owner issues
credits to users who can then spend them on resources. The main
efficiency gain results from users having an incentive to truthfully
reveal the value of their tasks (as shown in \Section~\ref{sec:simulation}). 

Another alternative is a closed loop economy where users both consume
and provide resources. PlanetLab could be run this way. A closed loop
economy provides more incentives for efficiency than an open loop
one: as prices rise, so does providers' profit, which increases
the incentive to provide resources. This raises competition and
eventually causes prices to fall. At no point in this cycle is real
money necessarily involved. 

\subsection{Are markets predictable?}
\label{sec:predictability}

Markets may allocate resources efficiently on average, but prices for
resources fluctuate, so how can users predict the cost of the
resources that they need? 

In this context, we define predictability (i.e., performance
isolation or quality-of-service) as the ability to provide a fixed amount
of resources over a period of time with high probability,
regardless of the demand put on the system. An example of an
application needing predictability is a web server that needs to serve
$n$ requests per second with $99\%$ of requests served within $d$
seconds. 

The market from \Section~\ref{sec:example} can provide this capability
by adding the ability to reserve fixed shares, where a share is a
fixed percentage of a resource (e.g., $.1\%$ of a $1$ GHz CPU = $1$
MHz). These shares have a fixed duration and are sold using an
auction. The operator of the example web server calculates the
resources necessary to meet his needs and bids for those
resources. The cost of this approach is that resource may be
under-utilized because some resources may be reserved, but go unused.

%% It is possible that the operator does not have sufficient
%% credits because of some combination of wasteful resource usage and
%% changes in the needs of other applications. In the former case, the
%% market can do nothing but prevent the operator's poor resource
%% management from affecting other users. In the latter case, the system
%% has become under-provisioned and no resource allocation system can
%% compensate for a lack of capacity. 

Although similar to techniques used in non-market systems
\cite{stoica1997} \cite{sullivan2000} \cite{duda1999}, the market
allows the predictability mechanism to be used more efficiently. The
problem with these systems is the difficulty in deciding how much of
the resource should be devoted to best-effort service and how much to
reserved service. The optimal split will likely vary significantly
over time.  Users would prefer reserved service if the cost to them is
equal, but reserved resource are less efficient than best-effort
because of the potential for under-utilization. The benefit of the
market is in forcing users to consider whether they really require
reserved resources and in helping the system determine
reserved/best-effort split. High bids for reserved service 
will cause users who can tolerate best-effort to do so and indicate to
the system to reserve more resources. Low bids will do the opposite.

%% If
%% this were the case, then users would have abandoned congestion
%% control, but, in fact, congestion-controlled TCP still constitutes
%% more than 90\% of the traffic on the Internet. The amount of resource
%% available is just one contributor to the overall value of an
%% application. In the case of TCP, the cost of installing a new
%% transport protocol outweighs any marginal improvement in throughput.
%% However, strategic behavior did push the adoption of later versions of
%% TCP like Reno \cite{jacobson1988} and SACK \cite{fall1996} because
%% they offered significantly better performance. It also blocked the
%% deployment of TCP Vegas\cite{brakmo1994} because unilateral deployment
%% of Vegas actually decreased performance of the unfortunate early
%% adopter.


example.tex
\section{An Example}
\label{sec:example}

In this section, we examine Proportional Share (PS) scheduling as an
example of the problem that market-based resource allocation seeks to
solve. PS gives user $i$ with weight $w_i$ a $w_i / \sum w$ share of
the resources. Using PS hierarchically, the user can assign these
resources to his tasks. For example, if Alice has weight $2$ and Bob
has a weight of $1$, then Alice has two-thirds of the total resources
for her tasks and Bob has one third. Suppose that this is necessary
because Alice must process twice as many queries as Bob. This works
well if Alice is always doing something more important than Bob, but
sometimes Bob will have an important task (e.g., serving a client
query) while Alice has a much less important task (e.g.,
non-time-critical background jobs like garbage collection). In this
case, Alice's task will still get most of the resources. This is an
economically inefficient situation because although Alice receives
some small benefit, Bob receives much less than he could, and the
total benefit is much less than if Bob received most of the current
resources.  This is a common situation because for most users and
their applications, the arrival process of important work is highly
bursty (e.g., a web/email/file server).

One solution is to rely on Alice to yield resources (e.g., using
\texttt{nice} or other means to set lower weights on tasks) when doing
less important tasks. Unfortunately, Alice has an incentive to deny
Bob the resources and use them herself.  This is an example ``Tragedy
of the Commons''~\cite{hardin1968} where optimizing for individual
utility results in low overall utility. On the other hand, optimizing
for overall utility depends on knowing the relative values of every
task being run. Unfortunately, users cannot be relied on to accurately
report these values without an honesty incentive. Some users may
behave \emph{obediently} by yielding resources or honestly reporting
task values, but those that do not (\emph{strategic} users) lower the
efficiency of the system, and, worse, provide an incentive for
obedient users to become strategic.

Another solution is to have a system administrator monitor the system
and dynamically change the weights of the users to maintain high
efficiency. However, this is expensive, time-consuming, and
error-prone, and it is does not scale to large numbers of users and
resources. 

Market-based resource allocation addresses this problem. For example,
Alice and Bob are issued a currency with income rates in the ratio $2$
to $1$. They use these credits to bid for resources in a market where
user $i$ with bid $b_i$ receives a $w_i / \sum w$ share of the
resources.  When a user has used her share, then her bid is deducted
from her balance of credits. Since Alice is aware that garbage
collection is a less critical task than serving client queries, she
will spend fewer credits when doing the former and more doing the
latter. The mechanism provides an incentive for users to truthfully
reveal how much they value resources. This allows Bob to get more
resources than Alice when he is processing queries and she is doing
garbage collection. Over the long-term, Alice can still process twice
as many queries as Bob (assuming similar workloads).

integration.tex
\section{Integrated Mechanism and System Design}
\label{sec:integration}

Mechanism design is traditionally part of economics while system
design is part of computer science. Why should they be done in
concert? How much benefit would be provided by adding an existing
mechanism, such as bartering or EBay, to a separately designed
system?

A long-standing principle \cite{levin1975} in system design is to
separate policy and the computational mechanism used to implement the
policy (not the economic mechanism in the mechanism design
sense). However, as Clark, et al. \cite{clark2002} point out, policy
and computational mechanism cannot truly be separated because the
mechanism defines what policies are possible. 

This would not be a problem if computational mechanism designers
provided interfaces for efficient and scalable policies, but this has
not been the case. For example, the market from
\Section~\ref{sec:example} requires statistics on resource usage (e.g., CPU
cycles, memory pages, disk blocks) and dynamic control over
allocation. However, many systems do not export detailed information
on usage or allow dynamic control of allocations
\cite{waldspurger2002}. Another example is that several computational
mechanisms assume a bartering policy. However, bartering economies
have very little fluidity. It is difficult to find a mutually
satisfying partner for each transaction and the complexity of
determining the exchange rates of $n$ resources is $O(n^2)$.

Even using an efficient economic mechanism from other contexts can
result in poor efficiency in a computational environment. Unlike many
other resources, the latency to access a computational resource is
critical because changes in demand are unpredictable. For example,
one possible economic mechanism for computational resources is to
auction them on EBay. Auctions on EBay are tuned for human bidding so
they typically take hours to close. The problem is that a web server's
demand may be spiking right now. By the time the auction closes, the
high load will have dissipated. The web server's operator could try to
anticipate load and purchase capacity in advance, but this results in
unused capacity.

In general, a pure mechanism designer is likely to design an economic
mechanism with high economic efficiency, but with little concern for
traditional systems metrics of computational efficiency, reliability,
security, complexity, and ease-of-use. Pure systems designers have
generally done the inverse. This is a direct consequence of a strict
interpretation of the policy/mechanism separation principle. Instead,
we advocate that systems designers embrace mechanism design as a
first-order concern to eventually produce systems than can be both
economically and computationally efficient.


introduction.tex
\section{Introduction}
\label{sec:introduction}
% Why shared clusters are useful
A key advantage of the Internet, peer-to-peer file sharing networks,
and systems like PlanetLab \cite{planetlab2003} is the sharing of
computational resources. This provides a variety of benefits,
including higher utilization, increased throughput, lower delay (due
to dispersion of resources in the network), and higher reliability.
However, resource allocation remains an issue. The problem is how to
allocate a shared resource fairly, with economic efficiency (where
efficiency is the ratio of the total actual benefit to all users to
the optimal benefit), and at low cost.

Scheduling algorithms like Proportional Share are a partial
solution. The problem with PS is determining how to set the
weights. Assuming that the values of tasks varies over time, no single
set of weights will suffice. Setting of weights cannot be left to
users because they have a strong incentive to always ask for the
highest possible weight. Having the system administrator set weights
is error-prone and time-consuming. 

Economics and game theory offer an alternative. The area of
\emph{mechanism design} is concerned with algorithms where individuals
optimizing their own utility results in high overall utility. A market
(or auction) is an example. In the resource allocation context, as users
optimize the benefit that they receive from their applications, the
mechanism optimizes the overall efficiency of the resource allocation,
without the intervention of an administrator.

%\cite{feigenbaum2002} \cite{wellman2001}
This is not a novel idea. Researchers \cite{ferguson1988}
\cite{malone1988} proposed this approach as early as 1988, and there
were likely earlier ones. Since then, several researchers
\cite{waldspurger1992} \cite{regev1998} \cite{stratford1999}
\cite{chun2000} \cite{ng2003}
have pursued it. Unfortunately, there have been few implementations
\cite{waldspurger1992} \cite{chun2000} \cite{coleman2004}.  Given $17$
years of research, it is surprising that there is not even one
commercially or freely available system for market-based resource
allocation. Given the impact of poor resource allocation on systems
like PlanetLab, this appealing approach and a large body of
enthusiastic publications, why have so few systems been built?  We
believe the lack of operational systems is because questions persist
in the minds of system designers about the value of the economic
approach, its applicability, and its relevance to system design.

In this paper, we examine some of these questions using a combination
of qualitative arguments and simulation. We do not claim to have
conclusive answer. Instead, we hope to provide sufficient affirmative
evidence that more real systems should be built, deployed, and
evaluated.

%% The remainder of the paper is organized as follows. In
%% \Section~\ref{sec:economics} we qualitatively address some questions
%% regarding markets and resource allocation. In
%% \Section~\ref{sec:simulation}, we present simulations of a basic market
%% and use the results to address further questions. In
%% \Section~\ref{sec:integration}, we address the larger question of
%% whether mechanism design should be integrated with system
%% design. 

%% \begin{itemize}

%% \item {\bf Do users behave strategically?} 

%% \item {\bf Are markets useful for systems with low utilization?}

%% \item {\bf Do markets provide an advantage over long-term 
%% Proportional Share (or fixed pricing)?} 

%% \item {\bf Are markets fair?}

%% \item {\bf Are markets useful when real money is not involved?}

%% \item {\bf How much of a benefit do markets provide and what does the
%% benefit depend on?} 

%% \item {\bf Can markets provide predictable performance?} 

%% \item {\bf Should mechanism design be integrated with system design?}

%% \end{itemize}

%% high level


%% Several non-economic algorithms have been proposed. In Proportional
%% Share (PS) (or Weighted Fair Queueing in a networking context), each
%% user $i$ has a weight $w_i$, and $i$'s share $s_i$ of the resources is
%% $w_i / \sum w$. The works well if the relative importance of $i$'s
%% actions are always $s_i$. The inefficiency arises when the importance
%% of $i$'s actions are uneven. For example, a database may serve
%% critical queries for an enterprise, but only do so rarely. The
%% remainder of the time, it performs optional housekeeping operations
%% like optimizing its data structures, pre-fetching from disk, etc. If
%% it receives a small share, then it will not have enough resources to
%% serve its critical queries. If it receives a large share, then it will
%% consume resource during housekeeping that could be otherwise used by
%% another application performing more important operations. Either the
%% application's own performance or the overall system's performance
%% suffers (in economic terms, individual and social welfare,
%% respectively). 

%% One solution is to rely on the database administrator to cut down
%% resource usage (e.g. by using \texttt{nice}) during
%% housekeeping. Unfortunately, it is unrealistic to 


%% Fair Queueing (FQ)
%% gives each of $n$ users a $1/n$ share of the resources. Unfortunately,
%% some users 

%% possibility is to give every user the same 
%%  but these
%% typically require an administrator to decide how much each user should
%% get. 

%% An example of a non-economic allocation algorithm is Proportional
%% Share (PS) (its name in the context of processor scheduling) or
%% Weighted Fair Queueing (WFQ) (in the context of packet
%% scheduling). Each process or flow $i$ in PS has a weight $w_i$, and
%% $i$'s share $s_i$ of the resources is $w_i / \sum w$. The share $s_i$
%% is 

%% The main challenge is \emph{strategic}
%% users who act 
%% in their own interests.


%% current solutions
%% *) everyone same
%% *) admin sets weights
%% *) infer importance from jobs

%% % Why current solutions are not good.
%% % introduce market approach
%% % Justify market approach
%% Several non-economic allocation algorithms have been proposed, but
%% these typically assume that task values (i.e., their
%% importance) are the same, or are inversely proportional to the
%% resources required, or are set by an omniscient administrator.
%% However, in many cases, task values vary significantly, are not
%% correlated to resource requirements, and are difficult and
%% time-consuming for an administrator to set. Instead, we examine a
%% market-based resource allocation system (others are described
%% in~\cite{ferguson1988, waldspurger1992, regev1998, chun2000,
%% wellman2001, auyoung2004}) that allows users to express their
%% preferences for resources through a bidding mechanism.

%% % Justify proportional share model
%% % differentiate this analysis
%% In particular, we consider a \emph{price-anticipating} scheme in which
%% a user bids for a resource and receives the ratio of his
%% bid to the sum of bids for that resource.  This proportional scheme is
%% simpler, more scalable, and more responsive~\cite{lai2004-2} than
%% auction-based schemes~\cite{ferguson1988, waldspurger1992, regev1998}.
%% Previous work has analyzed price-anticipating schemes in the context
%% of allocating network capacity for flows for users with unlimited
%% budgets. In this work, we examine a price-anticipating scheme in the
%% context of allocation computational capacity for users with private
%% preferences and limited budgets, resulting in a qualitatively
%% different game (as discussed in Section~\ref{sec:relatedwork}).

%% In this paper, we formulate the \emph{fixed budget} resource
%% allocation game and study the existence and performance of the Nash
%% equilibria of this game.  For evaluating the Nash equilibria, we
%% consider both their efficiency, measuring how close the social welfare
%% at equilibrium is to the social optimum, and fairness, measuring how
%% different the users' utilities are. Although rarely considered in
%% previous game theoretical study, we believe fairness is a critical
%% metric for a resource allocation schemes because the perception of
%% unfairness will cause some users to reject a system with more
%% efficient, but less fair resource allocation in favor of one with less
%% efficient, more fair resource allocation. We use both \emph{utility
%% uniformity} and \emph{envy-freeness} to measure fairness. Utility
%% uniformity, which is common in Computer Science work, measures the
%% closeness of utilities of different users. Envy-freeness, which is
%% more from the Economic perspective, measures the happiness of users
%% with their own resources compared to the resources of others.

%% Our contributions are as follows:

%% {$\bullet$ \bf We analyze the existence and performance of Nash
%% equilibria.} Using analysis, we show that that there is always a Nash
%% equilibrium in the fixed budget game if the utility functions satisfy
%% a fairly weak and natural condition of \emph{strong competitiveness}.
%% We also show the worst case performance bounds: for $m$ players the efficiency at
%% equilibrium is $\Omega(1/\sqrt{m})$, the utility uniformity is $\geq
%% 1/m$, and the envy-freeness $\geq 2\sqrt{2}-2 \approx 0.83$. Although
%% these bounds are quite low, the simulations described below indicate
%% these bounds are overly pessimistic.

%% {$\bullet$ \bf We describe algorithms that allow strategic users to
%% optimize their utility.} As part of the fixed budget game analysis, we
%% show that strategic users with linear utility functions can calculate
%% their bids using a \emph{best response} algorithm that quickly results
%% in an allocation with high efficiency with little
%% computational and communication overhead. We present variations of
%% the best response algorithm for both finite and infinite parallelism
%% tasks. In addition, we present a \emph{local greedy adjustment}
%% algorithm that converges more slowly than best response, but allows
%% for non-linear or unformulatable utility functions.

%% {$\bullet$ \bf We show that the price-anticipating resource allocation
%% mechanism achieves a high degree of efficiency and fairness.} Using
%% simulation, we find that although the socially optimal allocation
%% results in perfect efficiency, it also results in very poor
%% fairness. Likewise, allocating according to only users' preference
%% weights results in a high fairness, but a mediocre
%% efficiency. Intuition would suggest that efficiency and fairness are
%% exclusive. Surprisingly, the Nash equilibrium, reached by each user
%% iteratively applying the best response algorithm to adapt his bids,
%% achieves nearly the efficiency of the social optimum and nearly the
%% fairness of the weight-proportional allocation: the efficiency is
%% $\geq 0.90$, the utility uniformity is $\geq 0.65$, and the
%% envy-freeness is $\geq 0.97$, independent of the number of users in
%% the system. In addition, the time to converge to the equilibrium is
%% $\leq 5$ iterations when all users use the best response strategy. The
%% local adjustment algorithm performs similarly when there is sufficient
%% competitiveness, but takes $25$ to $90$ iterations to stabilize.

%% As a result, we believe that shared distributed systems based on the
%% fixed budget game can be highly decentralized, yet achieve a high
%% degree of efficiency and fairness.

%% The rest of the paper is organized as follows. We describe the model
%% in Section~\ref{sec:model} and derive the performance at the Nash
%% equilibria for the infinite parallelism model in Section~\ref{sec:results}. In
%% Section~\ref{sec:algorithms}, we describe algorithms for users to
%% optimize their own utility in the fixed budget game. In
%% Section~\ref{sec:simulation_results}, we describe our simulator and
%% simulation results. We describe related work in
%% Section~\ref{sec:relatedwork} and conclude in
%% Section~\ref{sec:conclusions}. 


main.tex
%\documentclass[]{sig-alternate}
%\documentclass[]{acm_proc_article-sp}
\documentclass[twocolumn]{article}
\usepackage{amsmath,epsfig,latexsym,psfig,url,graphicx}
\usepackage[top=.9in,bottom=.1in,left=.9in,right=.9in]{geometry} 

\renewcommand{\footnotesize}{\small}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\def\up{\vspace*{-1cm}}

% Refine section to use the funny section symbol
\def\Section {\S}

% Compact itemize and enumerate.  Note that they use the same counters and
% symbols as the usual itemize and enumerate environments.
\def\compactify{\itemsep=0pt \topsep=0pt \partopsep=0pt \parsep=0pt}
 \let\latexusecounter=\usecounter
 \newenvironment{CompactItemize}
   {\def\usecounter{\compactify\latexusecounter}
    \begin{itemize}}
   {\end{itemize}\let\usecounter=\latexusecounter}
 \newenvironment{CompactEnumerate}
   {\def\usecounter{\compactify\latexusecounter}
    \begin{enumerate}}
   {\end{enumerate}\let\usecounter=\latexusecounter}

\title{\up Markets are Dead, Long Live Markets}

\newcount\aucount
\newcount\originalaucount
\newdimen\auwidth
\auwidth=8in
\newdimen\auskip
\newcount\auskipcount
\newdimen\auskip
\global\auskip=1pc
\newdimen\allauboxes
\allauboxes=\auwidth
\newtoks\addauthors
\newcount\addauflag
\global\addauflag=0 %Haven't shown additional authors yet

\gdef\numberofauthors#1{\global\aucount=#1
\ifnum\aucount>4\global\originalaucount=\aucount \global\aucount=4\fi %g}
\global\auskipcount=\aucount\global\advance\auskipcount by 1
\global\multiply\auskipcount by 2
\global\multiply\auskip by \auskipcount
\global\advance\auwidth by -\auskip
\global\divide\auwidth by \aucount}

\newfont{\affname}{phvr at 10pt}
\newfont{\eaddrfnt}{phvr at 8pt}
\newfont{\authorfont}{phvr at 12pt}
\def\email#1{{{\eaddrfnt{\vskip 4pt#1}}}}

\def\alignauthor{%                  % \begin{tabular}
\end{tabular}%
  \begin{tabular}[t]{p{\auwidth}}\centering}%

\def\alignaffiliation{%                  % \begin{tabular}
\end{tabular}%
  \begin{tabular}[t]{p{2.0in}}\centering}%

\def\newauthorrow{%
\end{tabular}
\begin{tabular}{c}}

\numberofauthors{4}


% Three authors sharing the same affiliation.
\author{
      \alignauthor \authorfont{Kevin Lai}\thanks{kevin.lai@hp.com, Information Dynamics Laboratory, HP Labs, Palo Alto, CA 94304}
%      \email{kevin.lai@hp.com}
%
%      \newauthorrow
%      \alignaffiliation $^1$\affname{School of Information Management and Systems}\\
%      \affname{U.C. Berkeley}
%
%      \newauthorrow
%     \alignaffiliation $^2$\affname{HP Labs}\\
%      \affname{Palo-Alto}
          }

\date{}

\begin{document}

\maketitle

\input{abstract}

\input{introduction}

\input{example}

\input{economics}

\input{simulation}

\input{integration}

%\input{conclusions}

{\footnotesize
\bibliographystyle{abbrv}
\bibliography{../bibliographies/resource_allocation,../bibliographies/economics,../bibliographies/networking,../bibliographies/overlay,../bibliographies/network_performance,../bibliographies/peer-to-peer,../bibliographies/security,../bibliographies/reputation,../bibliographies/network_architecture,../bibliographies/grid,../bibliographies/scheduling,../bibliographies/virtualization,../bibliographies/game_theory,../bibliographies/algorithms,../bibliographies/transport_protocols}
}

\end{document}

simulation.tex
\section{Simulation Results}
\label{sec:simulation}

In this section, we present preliminary simulation results quantifying
the efficiency gains of a market. The basic idea is to simulate a
single CPU server running the CPU-intensive tasks of several users. We
examine different resource allocation algorithms and different user
behaviors.

\begin{table}
\small
\begin{center}
\begin{tabular}{|c|c|}
\hline
Parameter & Value  \\
\hline
\hline
Users & 10 \\
\hline
Running Time & 1000s \\
\hline
Task Interarrival & Gaussian, $\mu$: [1s, 120s], $\sigma$: $\mu/2$ \\
\hline
Task Size & Gaussian, $\mu$: 10, $\sigma$: 5 \\
\hline
Task Deadline & Gaussian, $\mu$: 75, $\sigma$: 37.5 \\
\hline
Task Value & Uniform, range: (0, 1] \\
\hline
\end{tabular}
\end{center}
\label{tab:parameters}
\caption{Simulation parameters}
\end{table}

The simulation parameters are summarized in
Table~\ref{tab:parameters}.  A user may have more than one pending
task, but users only run one task at a time. If a task completes by
the deadline, then the user receives $value * size$ utility, otherwise
There is one server providing resources for tasks. A task finishes
when it accumulates resources equal to its size. A user can run one
task, switch to a new task, and then switch back to the first task
without cost. 

The server uses one of two resource allocation schemes: Proportional
Share or Market Proportional Share. With Proportional Share, the
server allocates its resources to tasks according to the weight
assigned by the task's owner. With Market Proportional Share, users
have an income of \$$1$ credit per second. If Alice spends $1$ credit
and Bob spends $2$, then Alice's task gets $.66$ resources, while
Bob's task gets $.33$. The income can be saved.

We simulate three different user behaviors: obedient, strategic
without a market, and strategic with a market. Obedient users assign a
weight to their tasks equal to the task's value. Non-market strategic
users assign the maximum possible weight to all of their tasks. Market
strategic users budget their credits according to the task. The idea
is to spend more credits on more valuable tasks and to apportion the
credits over the lifetime of the task. Market strategic users assign
the following credits per second to run their most valuable task:
$(balance * value)/ (deadline - now)$.  $balance$ is the user's
current credit balance, $value$ is the value of the user's most
current valuable task, $deadline$ is the deadline of that task, and
$now$ is the current time.

\begin{figure}[htb]
\hspace*{-.6cm}
\includegraphics[angle=270,width=9cm]{figures/market/market_no_market}
\caption{\small The utility of different user behaviors 
and mechanism as a function of system load. }
\label{fig:market_no_market}
\end{figure}

Figure~\ref{fig:market_no_market} shows the simulation results. The
y-axis is the mean utility per host per time unit. The x-axis shows
the mean task arrival rate in the system and is a measure of overall
system load. Each point in the graph is a run of the simulator.

As the load increases to the right, the obedient users without a
market are able to maintain a high level of utility. However, users
have no incentive to be unilaterally obedient. Instead, their
incentive is to strategically give a high weight to all their tasks.
The plot of the non-market strategic users shows that they are able to
maintain a high level of utility when the system is lightly loaded
(from 0.0 to 0.0125), but as the load saturates the system, utility
drops to zero. At this point the system wastes resources running tasks
that never meet their deadlines and therefore provide no utility.  In
a system without a mechanism or significant social pressure, some
users inevitably become strategic. To counter this, we use the market
mechanism. The strategic users are forced to truthfully reveal the
value of their tasks and the system can maintain the same high level
of utility as when all users were obedient.

%% Of course, this simplified simulation model omits many real-world
%% metrics like computational efficiency, reliability, security, and
%% ease-of-use. The point of this simulation in simply to show the
%% potential economic efficiency gain of market-based resource
%% allocation. 


main.bbl
\begin{thebibliography}{10}

\bibitem{planetlab2003}
http://planet-lab.org.

\bibitem{chun2000}
B.~N. Chun and D.~E. Culler.
\newblock {Market-based Proportional Resource Sharing for Clusters}.
\newblock Technical Report CSD-1092, University of California at Berkeley,
  Computer Science Division, January 2000.

\bibitem{clark2002}
D.~D. Clark, J.~Wroclawski, K.~R. Sollins, and R.~Braden.
\newblock {Tussle in Cyberspace: Defining Tomorrow's Internet}.
\newblock In {\em {ACM SIGCOMM}}, 2002.

\bibitem{coleman2004}
K.~Coleman, J.~Norris, G.~Candea, and A.~Fox.
\newblock {OnCall: Defeating Spikes With a Free-Market Application Cluster}.
\newblock In {\em {Proceedings of the IEEE Conference on Autonomic Computing}},
  2004.

\bibitem{duda1999}
K.~J. Duda and D.~R. Cheriton.
\newblock {Borrowed-Virtual-Time ({BVT}) scheduling: supporting
  latency-sensitive threads in a general-purpose schedular}.
\newblock In {\em Symposium on Operating Systems Principles}, pages 261--276,
  1999.

\bibitem{ferguson1988}
D.~Ferguson, Y.~Yemimi, and C.~Nikolaou.
\newblock {Microeconomic Algorithms for Load Balancing in Distributed Computer
  Systems}.
\newblock In {\em International Conference on Distributed Computer Systems},
  pages 491--499, 1988.

\bibitem{hardin1968}
G.~Hardin.
\newblock {The Tragedy of the Commons}.
\newblock {\em Science}, 162:1243--1248, 1968.

\bibitem{levin1975}
R.~Levin, E.~Cohen, W.~Corwin, F.~Pollack, and W.~Wulf.
\newblock {Policy/Mechanism Separation in Hydra}.
\newblock In {\em {ACM Symposium on Operating Systems Principles}}, 1975.

\bibitem{malone1988}
T.~W. Malone, R.~E. Fikes, K.~R. Grant, and M.~T. Howard.
\newblock {Enterprise: A Market-like Task Scheduler for Distributed Computing
  Environments}.
\newblock In B.~A. Huberman, editor, {\em The Ecology of Computation}, number~2
  in Studies in Computer Science and Artificial Intelligence, pages 177--205.
  Elsevier Science Publishers B.V., 1988.

\bibitem{ng2003}
C.~Ng, D.~Parkes, and M.~Seltzer.
\newblock {Strategyproof Computing: Systems Infrastructures for Self-Interested
  Parties}.
\newblock In {\em Workshop on Economics of Peer-to-Peer Systems}, June 2003.

\bibitem{regev1998}
O.~Regev and N.~Nisan.
\newblock {The Popcorn Market: Online Markets for Computational Resources}.
\newblock In {\em Proceedings of 1st International Conference on Information
  and Computation Economies}, pages 148--157, 1998.

\bibitem{stoica1997}
I.~Stoica, H.~Abdel-Wahab, and K.~Jeffay.
\newblock {On the Duality between Resource Reservation and Proportional Share
  Resource Allocation}.
\newblock In {\em Multimedia Computing and Networking}, volume 3020 of {\em
  SPIE Proceedings Series}, pages 207--214, February 1997.

\bibitem{stratford1999}
N.~Stratford and R.~Mortier.
\newblock {An Economic Approach to Adaptive Resource Management}.
\newblock In {\em {Workshop on Hot Topics in Operating Systems}}, pages
  142--147, 1999.

\bibitem{sullivan2000}
D.~G. Sullivan and M.~I. Seltzer.
\newblock {Isolation with Flexibility: a Resource Management Framework for
  Central Servers}.
\newblock In {\em Proceedings of the USENIX Annual Technical Conference}, pages
  337--350, 2000.

\bibitem{waldspurger2002}
C.~A. Waldspurger.
\newblock {Memory Resource Management in VMware ESX Server}.
\newblock In {\em {Proceedings of the Symposium on Operating Systems Design and
  Implementation}}, 2002.

\bibitem{waldspurger1992}
C.~A. Waldspurger, T.~Hogg, B.~A. Huberman, J.~O. Kephart, and W.~S. Stornetta.
\newblock {Spawn: A Distributed Computational Economy}.
\newblock {\em Software Engineering}, 18(2):103--117, 1992.

\end{thebibliography}
