Flexible Procurement of Services with Uncertain Durations using Redundancy

1 Introduction

Increasingly, participants in large distributed systems are able to discover and automatically procure the services of others. This allows service consumers to complete complex computational tasks on demand, but without the need to invest in and maintain expensive hardware. Already, such a serviceoriented approach is gaining popularity in a large range of application areas, including Grids, peer-to-peer systems, cloud and utility computing [Singh and Huhns, 2005].

Despite its benefits, flexible service procurement poses new challenges that have not been addressed satisfactorily by current research. In particular, services offered by external providers are beyond the consumer's direct control and may therefore display uncertainty in their behaviour. Thus, the execution time of services can be highly uncertain, due to concurrent access by other consumers, hardware or network problems and the provider's scheduling policies. This is particularly problematic when services take a long time to complete, as is common for many computationally-intensive tasks, and when consumers need to obtain their results by a certain deadline. Furthermore, in large systems, many different providers may offer functionally equivalent services that are heterogeneous in their quality and costs. This requires consumers to make appropriate decisions about which services to procure, balancing the probability of success with the overall cost. It also necessitates the design of appropriate economic mechanisms that incentivise providers to truthfully reveal their private information, such as their costs and the estimated execution time, thus resulting in good procurement decisions and removing the need for strategic behaviour.

Related to this work is the literature on task allocation under execution uncertainty such as [Porter et al., 2008]. Here, researchers have studied problems where providers have private information about both their costs for executing tasks, as well as the probability that they will successfully complete their tasks. However, this and similar works do not consider redundancy to increase the overall success probability of a task. Now, there is some work that employs redundancy, combining several unreliable services to achieve a higher probability of success. This includes deployed systems, such as Google's MapReduce [Dean and Ghemawat, 2008], but the techniques used for determining how many services to procure are typically ad hoc, and they also do not consider costs. A decision-theoretic approach for addressing the latter is described in [Stein et al., 2008], but this work assumes that costs are known and focusses on heuristic techniques for complex workflow scenarios. A slightly different approach is taken by work on restarting Web queries, which examines when such queries should be timed out and re-issued (possibly to a different provider) to ensure timely completion [Chalasani et al., 1998]. However, such work typically assumes that only one query is active at any time and the costs of multiple queries are not explicitly balanced with the resulting benefit.

To address these shortcomings, we present an abstract model of a procurement scenario for services with uncertain durations. We begin by outlining a generic approach for finding an optimal procurement strategy when service costs and duration distributions are known. This approach is the first to employ redundancy in a flexible and optimal manner as to balance the probability of completing within its deadline and the costs for doing so. More specifically, our approach allows a consumer to invoke multiple services in parallel for executing the same task, and it can dynamically procure further services during execution as the deadline draws closer. To find the optimal strategy, we combine analytical expressions with computational search methods. As brute force is computationally intractable, we present a novel branch-and-bound algorithm that reduces the search, on average, by over 99.9%. We also discuss a heuristic algorithm capable of handling problems with thousands of heterogeneous service providers, and we show that its solutions are, on average, within 0.12% of the optimal. For a range of settings we then experimentally demonstrate that dynamic redundancy achieves an improvement of up to 130% over current approaches.

Next, we examine settings where service costs are private and known only by the providers. For this scenario, we propose a VCG-like mechanism that is incentive-compatible, i.e., that incentivises rational, self-interested participants to reveal their true costs. In this context, it is the first such mechanism that allows consumers to procure multiple, redundant services to increase its probability of success. Moreover, we show that this mechanism can achieve an average 95% efficiency when some prior information about service cost distributions is known to the consumer. To address settings where this is not available, we propose two further novel mechanisms, which have lower information requirements, but still achieve an average 86% efficiency.

In the remainder of this paper, we first present the procurement problem (Section 2) and discuss its optimal solution (Section 3). This is followed by our mechanisms (Section 4) and an empirical evaluation (Section 5). Section 6 concludes.

2 Problem Specification

We consider a single service consumer A, which needs to complete a task T . The consumer derives a utility V ∈ R+ if the task is successfully completed within a given deadline D ∈ R+, and 0 otherwise. Furthermore, there are m service providers, given by the set M = {1, . . . ,m}, which can complete the task on the consumer's behalf. A consumer can invoke a provider i ∈ M at any time in the interval [0, D]. We assume that, once invoked, the provider remains committed to the task until it is completed (possibly beyond the deadline), and incurs an (expected) cost ci, where this cost may represent both the running costs of its computational resources and opportunity costs from not being able to use these resources for other tasks. To compensate for these costs, the consumer pays the provider a transfer τi ∈ R+ on invocation of i, which is paid regardless of whether the task is completed by the deadline D. Although a provider will always successfully complete the task, the execution time is uncertain, and is given by a continuous cumulative distribution function Fi(t). This denotes the probability that provider i completes the task within time t, and we assume this includes any time needed for pre-/post-processing, queueing and data transfers. We also assume that the execution times of different service providers are independently drawn.

Although we only consider a single task in this paper, crucially we allow multiple providers to execute it concurrently and independently. In this case, the task is considered successful if at least one provider completes it by time D. We assume that all participants are expected utility maximisers.

Now, the key problem is to find an optimal procurement strategy that determines which providers should be invoked and when, such that the consumer's utility is maximised. We compactly represent such a strategy as a vector ρ = ((s1, t1), . . . , (sn, tn)) with n ≤ m, where each element represents the invocation time ti ∈ [0,D] of a provider si ∈ M. A provider i is then only invoked at time ti (and only receives τi) if no provider has so far completed the task. Without loss of generality, we assume that ti ≤ ti+1, and si ̸= sj if i ̸= j. For example, assume there are four providers and ρ = ((2, 0), (3, 0), (1, 2.5)), i.e., providers 2 and 3 are invoked immediately. Then, if the task has not been completed by t = 2.5, provider 1 is also invoked, causing the three providers to run concurrently. Provider 4 is never invoked.

Given a strategy ρ, the consumer's expected utility is the difference between the expected value of completing the task and the expected total transfers to the invoked providers:

Furthermore, the expected utility of each provider si is:

if si is included in ρ, and zero otherwise. Furthermore, although our main concern is maximising the consumer's utility, as a measure of how well the available services are utilised, we define the overall efficiency, also referred to as the social welfare, of a procurement strategy as:

This measures the overall quality of a strategy for all participants and therefore ignores any transfers, as these only re-distribute utility between the agents.

3 Optimal Service Procurement

We now consider the problem of finding the optimal procurement strategy that maximises the consumer's expected utility, given that the consumer has full information about both the providers' costs ci and the duration distributions Fi. This corresponds to a service-oriented system where providers advertise their services at a fixed price, and thus ci denotes the advertised price. In this case, we set the transfers to the providers so that they equal these prices, i.e., τi = ci.

More formally, let ρ∗ = argmaxρ UA(ρ). Finding the optimum, ρ∗ , is non-trivial since it involves selecting an appropriate subset of providers, ordering them and then determining invocation times. To solve this, we initially assume that the optimal subset of providers and their ordering is given. That is, we are given an ordered set of providers ρ∗s = (s1, . . . , sn) where si is invoked before si+1. To compute the optimal procurement schedule, we must determine ρ∗t = (t1, . . . , tn), where ti is the invocation time of si. To this end, we compute the gradient of the expected welfare, ∇U(ρ∗t ), and find its root, i.e., ∇U(ρ∗t ) = 0. This results in a system of n simultaneous equations, with one equation for each ti, with constraints, ∀i : 0 ≤ ti ≤ D, and ∀i, j : i ≤ j ↔ ti ≤ tj. Solving these equations (and checking the appropriate second order conditions) depends on the family of duration distributions and can be done either analytically or numerically using standard optimisation software. In what follows, we focus on the exponential distribution as this is commonly used for modelling uncertain service durations [Trivedi, 2001].

3.1 Exponentially Distributed Durations

We now derive analytical expressions for the invocation times ρ∗t , given ρ∗s and given that the duration distributions of providers i ∈ M are given by Fi(t) = 1 - e-λit , where λi > 0 is a rate parameter. Re-writing Equation 1 with these distributions, and computing the gradient, allows us to compute the optimal invocation time ti of provider si by solving:

Here, we note that ti is independent of any tj, j < i, i.e., the invocation time of a provider does not depend on the invocation time of those already running. This is a result of the exponential function being memoryless, i.e., the probability of completing the task within the next time interval Δt is independent of when it was invoked. Hence, we can calculate each ti by backward induction, starting with the last provider, n. The invocation time of this can be obtained directly by taking the derivative with respect to tn (as in Equation 4):

Furthermore, we can obtain a simpler closed-form solution for the remaining invocation times by combining and manipulating the partial derivatives for ti and ti+1, resulting in:

Then, using algebraic manipulations, we isolate ti, and derive an expression that is based solely on ti+1:

Note that Equation 6 is not well defined for t1, and the optimal here is to set t1 = 0. This is because the cost will be incurred in any case and any delays would only reduce its probability of success by the deadline. Furthermore, we note that the equations can yield negative values for some ti, indicating that the optimal values lie outside the constraints of the problem (i.e., before the task can be started). In this case, as ti does not influence the procurement times of later providers, the optimal choice is to set ti = 0, i.e., the provider is invoked at the earliest possible time. Furthermore, the equations can sometimes yield inconsistent values, i.e., ti > D or ti > ti+1 for some i, but this only occurs when the ordering and/or the set of providers was non-optimal in the first place. Finally, we also note that the partial second derivatives are always negative, and since each variable is found uniquely one at a time using backward induction, the final result is optimal.

So far, Equations 5 and 6 allow us to efficiently calculate the optimal procurement times for a given, optimal ordered sequence of service providers ρ∗s . However, it is not obvious how to find this order. Related work on economic search, such as [Weitzman, 1979], does not apply to this case, due to the overlap of concurrently invoked providers. Furthermore, our problem includes a fixed time constraint, by which the task has to be completed. Other greedy approaches that order services by increasing costs, decreasing rate parameters, the ratio of these, or approaches that first select providers who individually yield a higher expected utility, also do not always find optimal solutions. This is because it is often best to select cheaper, slower providers first and only invoke the more expensive and faster ones later, to ensure that the task is completed successfully. However, when the deadline of the task is particularly short, the consumer may be forced to immediately invoke the faster, expensive providers.

As a simple example of this, we consider a set of two providers, M = {1, 2}. The first is cheap and slow with c1 = 0.2 and λ1 = 0.1, while the second is expensive and fast with c2 = 5 and λ2 = 10. If we then assume that a consumer has a task T with deadline D = 1.5 and utility V = 100, the optimal procurement strategy is ρ∗ = ((1, 0), (2, 0.75)). However, if we decrease the deadline slightly to D = 1, the optimal strategy becomes ρ∗ = ((2, 0), (1, 0.84)), thereby reversing the order of invoked providers.

This observation suggests that a simple greedy search for the optimal strategy is insufficient. Hence, in the following sections, we present an optimal branch-and-bound algorithm. As this becomes slow when there are dozens of providers, we also discuss a fast heuristic algorithm.

3.2 The Branch-And-Bound Algorithm

Finding an optimal subset and ordering of providers ρ∗s using a brute-force search is clearly infeasible 1 when the number of

1 More generally, we believe that this problem is NP-hard due to its similarity to the well-known Stochastic Integer Packing and the

Algorithm 1 Branch-And-Bound Algorithm.

providers rises beyond a handful, as the number of possible orderings for m providers is ∑mi=0 (mi ) · i! = ∑mi=0 m! (m-i)! .

Now, it is possible to significantly reduce the number of provider orderings that need to be searched by noting that we can use information about some examined orderings to exclude others. For example, assume we have three providers, and we have just considered the ordering ρs = (2, 1). This already promises a high utility, and, in fact, we note it is higher than what could possibly be achieved by invoking provider 3 first (e.g., if V - c3 is low). Hence, we can immediately discard all five orderings starting with 3.

This intuition is generalised in our branch-and-bound technique given by Algorithm1. Inmore detail, we begin with an empty ordering ρ∗s = () (line 1), and then repeatedly consider any new ordering that can be created by appending a single provider to the end of an existing ordering. This is implemented by keeping a set of orderings, Q in line 3, that have not yet been expanded in this manner. During each iteration of the main loop of the algorithm (lines 4-17), we then remove one 2 ordering ρs from Q (lines 5 and 6) and expand it. Here, EXPAND in line 7 takes an ordering ρs and returns the set of all orderings that can be obtained by appending a single remaining service provider fromM to ρs. From this set of new orderings, we then remove any that include providers that are dominated by others not currently in the ordering (line 8). 3

For each new ordering ρ′s, we now find both a lower bound and an upper bound for the expected utility that is achievable by any procurement strategy beginning with the providers in ρ′s (lines 10 and 11). Finding these allows us to exclude any orderings starting with ρ′s if the associated upper bound is less than the best lower bound found so far. This pruning and

Stochastic Knapsack problems, but we leave a formal proof of this conjecture for future work.

2 We remove the ordering that promises the highest lower bound on the expected utility. This allows us to quickly increase the best lower bound, thereby pruning the search space more effectively.

3 A provider i dominates j if and only if (ci ≤ cj ∧ λi > λj) ∨ (ci < cj ∧ λi ≥ λj). Clearly, it is suboptimal to invoke j before i.

updating of the lower bound is performed in lines 12-16.

We now describe LOWER(ρ′s) and UPPER(ρ′s). To find the lower bound, we simply restrict ourselves to the providers in ρ′s , and find the optimal times ρ′t for this ordering and return the associated utility, i.e., UA(FINDTIMES(ρ′s))), where FINDTIMES returns the optimal procurement strategy using the Equations from Section 3.1. Calculating an upper bound is less obvious, because we may be able to derive significantly higher utility by invoking further services. To this end, we let M ′ be the remaining service providers that are not in ρ′s . If M ′ = ∅, then the upper bound is equal to the lower bound discussed above. Otherwise, we create a virtual service provider sρ with csρ = mini∈M′ ci and λsρ = ∑i∈M′ λi. This is based on the rationale that if any providers fromM ′ are invoked in any order, their cost is bound to be at least csρ and their combined probability of success within any given time interval after invocation will never be higher than when immediately invoking all in parallel. With this reasoning, we obtain a new ordering ρ′′ s by appending sρ to ρ′s and then calculate the upper bound as U(FINDTIMES(ρ′′ s )). If that is less than the lower bound, this indicates that it is not possible to achieve a higher utility by invoking further providers, and we can set the upper bound equal to the lower bound.

At the end of each iteration, only unexpanded orderings with an upper bound that is higher than the currently highest lower bound are retained (line 17). This limits the size of Q (which we implemented using a priority queue), and also ensures that it is empty when all necessary orderings have been searched. When this happens, the best ordering and associated optimal times are returned (line 18). This final procurement strategy is optimal, because the algorithm searches all orderings, except for those that are known to have a lower expected utility than those already considered. Hence, the optimal ordering will never be discarded from the search.

However, while significantly reducing the search space in most realistic settings, this algorithm still searches for the optimal solution and may sometimes consider a large proportion of the entire search space. This may be the case, for example, when there are large numbers of highly similar providers and when the value of the task is very large in relation to the service costs. To address such scenarios, we introduce a fast heuristic approach in the following section.

3.3 The Heuristic Algorithm

Although we argued in Section 3.1 that a greedy approach does not generally result in an optimal strategy, it can still achieve good results in practice and is more scalable than exhaustive approaches. Hence, we present such an algorithm that starts with an empty ordering and then greedily adds, removes or switches providers until a local optimum is reached. Intuitively, this algorithm benefits from selecting providers that offer a good trade-off between performance and cost.

In more detail, given a current ordering ρs and a set of providers M ′ that are currently not in ρs, the greedy approach picks one of the following three actions, in order to maximise the expected utility of its next ordering: (1) it selects a provider x ∈ M ′ and adds it to ρs at position i ∈ {1, 2, . . . , n + 1} (shifting other providers as necessary), (2) it selects a provider si in ρs and removes it, or (3) it selects two providers si and sj in ρs and swaps their positions. This continues until the algorithm cannot find another better ordering. In this case, the current best is returned.

4 Mechanisms for Eliciting Costs

Whereas so far we have assumed that the consumer, A, has complete information about both the costs and the duration distributions of the providers, here we consider a setting where the cost information is private and unknown to the consumer. Instead, the consumer has to provide incentives so as to induce the providers to reveal this information truthfully. Note that we still assume that the providers' duration distributions are known by the consumer, as this information may be obtained from past and shared experiences, e.g using a trust or reputation system, or simply given by the provider. 4

4.1 (k +1)th Price Mechanism

Typically, when mechanism design is applied to task allocation problems, the well-known Vickrey-Clarke-Groves (VCG) mechanism is used. Providers are asked to reveal their private information (called their type) and in exchange are paid a transfer equal to their marginal contribution to the system. This payment structure provides the correct incentives so that each provider willingly reveals their type truthfully [Mas-Colell et al., 1995]. Unfortunately, however, the VCG mechanism is not applicable in our setting, since it is only suited for situations where the types (i.e. the costs) of the providers are independent. In our domain, this property does not hold, since the expected cost incurred by a provider depends significantly on which other providers are selected in the procurement strategy. Thus, our problem falls into the class of interdependent valuations, and it is well known from the literature that providers no longer have an incentive to reveal their private information truthfully if the VCG mechanism is used [Mas-Colell et al., 1995]. Moreover, in such a setting there exists no general mechanism which is both truthful and efficient [Jehiel and Moldovanu, 2001].

Our first mechanism is the (k + 1)th mechanism which works as follows. First, the consumer, A, announces k, 1 ≤ k < m. Then, each of the m providers reports a cost, ˆ ci, which may differ from their true cost ci. We assume that providers are ordered so that ˆ ci ≤ ˆ ci+1, and we define K = {i | i ∈ M and ˆ ci < ˆ ck+1}. That is, K is the set of k providers with the lowest reported costs. These form the candidate providers for the procurement strategy. After finding the set K, the payment value τi of each candidate provider is set to τi = ˆ ck+1. Now, the procurement strategy used by A is calculated by finding ρ′ = argmaxρ|si∈K UA(ρ) where only providers in K are (potentially) selected to be part of the strategy. It is important to notice that the payment τi for i ∈ K is conditional. That is, a payment or transfer to agent i ∈ K only occurs if the candidate provider is both selected as part of the procurement strategy ρ′ , and is subsequently invoked. Otherwise, it receives no payment (and incurs no cost).

4 To verify these distributions in the latter case, a payment scheme based on scoring rules could be used in conjunction with our mechanism, see [Zohar and Rosenschein, 2008], but we leave a more detailed investigation of this issue for future work.

Theorem 1. Let M be the set of service providers, |M| = m. For any k such that 1 ≤ k < m, the (k + 1)th mechanism is incentive compatible in dominant strategies (i.e., truthtelling is optimal, irrespective of what other agents do) and (ex-post) individually rational (i.e., the providers always receive zero or positive utility).

Proof. Individual rationality holds when ci = ˆ ci since τi = ˆ ck+1 ≥ ci for i ∈ K, and thus τi - ci ≥ 0, and furthermore τi = 0 for i /∈ K. As a result, the provider's expected utility (Equation 2) when ci = ˆ ci is always positive, irrespective of the reports of others. To show incentive compatibility, we first note that the selection of providers in K as part of the procurement strategy and their invocation time (if selected) are indendependent of their reported costs. Therefore, if i ∈ K, the probability of being invoked and the payment, and thus the expected utility, are independent of a provider's report. A provider's report thus only affects whether or not it will be selected as one of the candidate providers in K. Now, by overreporting, a provider can only reduce the likelihood of being selected and thus potentially foregoes a positive expected utility. By underreporting, a provider can increase this likelihood, but this will only result in a change (compared to reporting truthfully) when ˆ ci < ˆ ck+1 and ci > ˆ ck+1. In this case, however, if the provider is invoked its expected utility is strictly negative since τi - ci < 0.

While this mechanism has desirable properties, it also suffers from some key limitations. First, it selects providers based solely on their cost information, ignoring the duration distributions, leading to the possibility that expensive providers with fast completion times are excluded. Second, the parameter k must be announced before providers reveal their costs. To set k optimally requires a priori information about the distribution of the costs, and expensive calculations and/or simulations (as done in Section 5). To address this last problem, we now introduce two variations of our mechanism.

4.2 GroupingMechanisms

We introduce two new mechanisms: Pairing and Halving. These mechanisms differ from the (k + 1)th mechanism in both the provider-selection process and the calculation of the (conditional) payment, τ .

In the Pairing mechanism, every provider i ∈ M reports a cost, ˆ ci. Then, all providers are randomly paired with another provider (if |M| = m is odd, then a single triplet is formed). For each pair, the provider with the lower announced cost is placed in the set K and the conditional payment is set equal to the announced cost of the other provider (in the case of a triplet, the provider with the lowest announced cost is placed in K and the conditional payment is equal to the second lowest announced cost in the triplet). All providers not in K are not selected and therefore receive no payment. This results in |K| = ⌊m/2⌋ and ρ′ = argmaxρ|si∈K UA(ρ) as before.

In the Halving mechanism all providers in M announce costs as is done in the Pairing mechanism. Then, ⌊m/2⌋ providers are randomly selected and placed into a set G. All other providers are randomly paired and are then treated identically to those in the Pairing mechanism. For members of G, the provider with the lowest announced cost is placed in K

and its conditional payment is equal to the cost of the second lowest announced cost from G, while all other providers are discarded. The procurement strategy is computed as before.

Theorem2. The Pairing andHalvingmechanisms are incentive compatible and (ex post) individually rational.

Proof. Since the pairs and G are formed independently of the providers' reports, the proof follows from Theorem 1.

We note that there are many possible variations of these mechanisms, but all would share some key features. First, the size of K is solely determined by the number of providers, and thus does not rely on the consumer choosing an appropriate value. Second, the mechanisms require no a priori information about the cost distributions. Finally, they implement discriminatory pricing (i.e., different providers receive different payments), information which is then used to form the optimal procurement strategy (given K). On the other hand, the payments are always based on the higher costs (except in the Halving mechanism), and it is therefore not clear whether these variations offer any real benefits in practice. To this end, we experimentally evaluate them in the next section.

5 Evaluation

We now evaluate our proposed approaches in a variety of simulated environments, to determine if they provide benefits over existing techniques, and to investigate the cost of incentivising providers to reveal their private information. Throughout this section, we randomly generate each provider i by drawing its cost ci and duration rate λi independently and uniformly at random from [0, 1]. To consider a range of settings, tasks have either a low (Vlow = 2) or a high value (Vhigh = 8) and their deadline is either normal (Dnormal = 2) or urgent (Durgent = 0.5). Furthermore, we repeat experiments 1000 times and use ANOVA and t-tests to ensure statistical significance at the p < 0.05 level. As the associated confidence intervals are small, we omit these here for clarity.

5.1 Optimal Service Procurement

First, we consider environments where providers charge their true costs, i.e., τk = ck, and compare the average utility obtained by the optimal procurement strategy 5 described in Section 3 (Optimal) to a strategy that always selects the single provider that individually maximises the consumer's expected utility (Single). This latter strategy represents current task allocation approaches that do not include redundancy.

The results are shown in Figure 1. Here, we vary the number of providers in the system and plot the average expected consumer's utility, which is equal to the overall efficiency in this setting, as a proportion of V . Observing these trends, it is obvious that using redundancy can significantly improve the consumer's utility and does so in almost all settings considered. In fact, when averaging over all cases considered, the Optimal approach achieves more than a 35% improvement over the Single approach. In particular, when the deadline is small (Durgent) and the task value high (Vhigh), the Optimal strategy is able to employ high redundancy to ensure the task is completed within the deadline, while the higher task utility justifies the additional investment. For example, when there are 50 providers, the Single approach achieves 35.87% of V , while the Optimal achieves 82.65%- a 130% improvement.

5 This is found using our branch-and-bound algorithmwhen there are up to ten providers. We then use the heuristic algorithm to obtain a lower bound for the optimal when there are more providers. However, as we show later, the heuristic obtains near-optimal results.

Next, we note that when solving the above problems, our branch-and-bound approach significantly reduces the computational time required when compared to a brute-force algorithm. For example, when there are 12 providers and we consider Vhigh and Durgent, a brute force approach searches over 1.3 billion provider orderings, which takes an average 3.3 hours (using a Java implementation on a Windows-based Intel 2.2 GHz laptop with 4 GB RAM). By contrast, the branch-and-bound algorithm searches an average 42000 orderings (0.003% of the total search space), finding the optimal in half a second. While the latter still finds solutions for 18-23 providers in minutes (where the brute-force would take over 2 · 1010 years - longer than the age of the universe), our heuristic approach is better suited for larger settings with hundreds or thousands of providers. To investigate how its performance compares to the optimal, we have applied both to all settings described above with ten or less providers. Here, the heuristic achieved 99.88% of the optimal on average.

5.2 Incentive Compatible Mechanisms

Now we consider the mechanisms described in Section 4 and investigate how close the resulting procurement decisions are to the optimal (both in terms of the consumer's utility and the overall efficiency). To this end, Figure 2 compares the performance of a range of (k+1)th price mechanisms with varying k, and our Halving and Pairing mechanisms to the optimal (for brevity, we consider only two representative scenarios here, but similar results are obtained in other settings).

It is immediately obvious here that all mechanisms suffer from a loss in utility for the consumer - a cost that results from incentivising providers to report truthfully. More specifically, the best (k + 1)th price mechanism in each case achieves an average 85% of the optimal, while Pairing and Halving both achieve over 70%. We also note that the performance of the (k + 1)th depends heavily on the choice of k and can be as low as 25% of the optimal if the wrong parameter is chosen. Furthermore, the best parameter depends on the scenario. For example, for the task with Vlow, k = 3 is the best choice, achieving over 83% of the optimal. However, for Vhigh, it is one of the worst, achieving only 58%. Hence, these results indicate that a consumer can achieve a good utility by using appropriate k parameters. However, when insufficient information is available to set k, it can obtain good results by using a Pairing or Halving mechanism.

Next, we consider the overall efficiency, or social welfare. This ignores utility transfers between the consumer and the providers, and therefore gives a better indication of how effectively the available services are used to complete the task at hand. Here, we note that the mechanisms consistently achieve a good overall efficiency. The best (k + 1)th mechanism now reaches, on average, over 95% of the optimal efficiency while the Pairing and Halving mechanisms achieve 86% and 84%, respectively.

6 Conclusions

In this paper, we considered a setting where multiple providers can be redundantly procured to perform a single task which has to be completed within a given deadline. The providers have uncertain execution times, which are given by probability distributions, and incur different costs for executing the task. We first considered the setting with known costs and introduced an algorithm for calculating the optimal procurement strategy, as well as a near-optimal heuristic algorithm for settings with a large number of providers. We then introduced several incentive-compatiblemechanisms for eliciting the costs when these are unknown, and we evaluated our approaches empirically. The results showed that redundancy significantly outperforms the standard approach where only a single provider is selected for each task, and it continues to performwell in the incomplete information setting.

In future work, we are interested in investigating a setting where the execution duration distributions are also privately known, and need to be elicited by a consumer. Furthermore, we intend to apply this approach to larger settings with multiple, interdependent tasks.

Acknowledgments

This research was undertaken as part of the ALADDIN (Autonomous Learning Agents for Decentralised Data and Information Systems) project which is jointly funded by BAE Systems and EPSRC (EP/C548051/1), and as part of the EPSRC funded project on Market-Based Control (GR/T10664/01).