Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFairness and Utilization in Allocating Resources with Uncertain Demand
630
0
0.0
(
0
)
Added by
Kate Donahue
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Resource allocation problems are a fundamental domain in which to evaluate the fairness properties of algorithms. The trade-offs between fairness and utilization have a long history in this domain. A recent line of work has considered fairness questions for resource allocation when the demands for the resource are distributed across multiple groups and drawn from probability distributions. In such cases, a natural fairness requirement is that individuals from different groups should have (approximately) equal probabilities of receiving the resource. A largely open question in this area has been to bound the gap between the maximum possible utilization of the resource and the maximum possible utilization subject to this fairness condition. Here, we obtain some of the first provable upper bounds on this gap. We obtain an upper bound for arbitrary distributions, as well as much stronger upper bounds for specific families of distributions that are typically used to model levels of demand. In particular, we find - somewhat surprisingly - that there are natural families of distributions (including Exponential and Weibull) for which the gap is non-existent: it is possible to simultaneously achieve maximum utilization and the given notion of fairness. Finally, we show that for power-law distributions, there is a non-trivial gap between the solutions, but this gap can be bounded by a constant factor independent of the parameters of the distribution.
rate research
Read More
Cloud computing delivers value to users by facilitating their access to computing capacity in periods when their need arises. An approach is to provide both on-demand and spot services on shared servers. The former allows users to access servers on demand at a fixed price and users occupy different periods of servers. The latter allows users to bid for the remaining unoccupied periods via dynamic pricing; however, without appropriate design, such periods may be arbitrarily small since on-demand users arrive randomly. This is also the current service model adopted by Amazon Elastic Cloud Compute. In this paper, we provide the first integral framework for sharing the time of servers between on-demand and spot services while optimally pricing spot instances. It guarantees that on-demand users can get served quickly while spot users can stably utilize servers for a properly long period once accepted, which is a key feature to make both on-demand and spot services accessible. Simulation results show that, by complementing the on-demand market with a spot market, a cloud provider can improve revenue by up to 464.7%. The framework is designed under assumptions which are met in real environments. It is a new tool that cloud operators can use to quantify the advantage of a hybrid spot and on-demand service, eventually making the case for operating such service model in their own infrastructures.
We investigate online scheduling with commitment for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. As soon as a job has been submitted, the commitment constraint forces us to decide immediately whether we accept or reject the job. Upon acceptance of a job, we must complete it before its deadline $d$ that satisfies $d geq (1+epsilon)cdot p + r$, with $p$ and $r$ being the processing time and the submission time of the job, respectively while $epsilon>0$ is the slack of the system. Since the hard case typically arises for near-tight deadlines, we consider $varepsilonleq 1$. We use competitive analysis to evaluate our algorithms. Our first main contribution is a deterministic preemptive online algorithm with an almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound $frac{1+epsilon}{epsilon}$ of the greedy acceptance policy. Then the competitive ratio improves with an increasing number of machines and approaches $(1+epsilon)cdotln frac{1+epsilon}{epsilon}$ as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small $epsilon$. In the non-preemptive case, we present a deterministic algorithm on $m$ machines with a competitive ratio of $1+mcdot left(frac{1+epsilon}{epsilon}right)^{frac{1}{m}}$. This matches the optimal bound of $2+frac{1}{epsilon}$ of the greedy acceptance policy for a single machine while it again guarantees an exponential improvement over the greedy acceptance policy for small $epsilon$ and large $m$. In addition, we determine an almost tight lower bound that approaches $mcdot left(frac{1}{epsilon}right)^{frac{1}{m}}$ for large $m$ and small $epsilon$.
From skipped exercise classes to last-minute cancellation of dentist appointments, underutilization of reserved resources abounds. Likely reasons include uncertainty about the future, further exacerbated by present bias. In this paper, we unite resource allocation and commitment devices through the design of contingent payment mechanisms, and propose the two-bid penalty-bidding mechanism. This extends an earlier mechanism proposed by Ma et al. (2019), assigning the resources based on willingness to accept a no-show penalty, while also allowing each participant to increase her own penalty in order to counter present bias. We establish a simple dominant strategy equilibrium, regardless of an agents level of present bias or degree of sophistication. Via simulations, we show that the proposed mechanism substantially improves utilization and achieves higher welfare and better equity in comparison with mechanisms used in practice and mechanisms that optimize welfare in the absence of present bias.
332 -
Vineeth S. Varma
, Samson Lasaulce
, Julien Mounthanyvong andn Irinel-Constantin Morarescu
2020
In this paper, we consider a network of consumers who are under the combined influence of their neighbors and external influencing entities (the marketers). The consumers opinion follows a hybrid dynamics whose opinion jumps are due to the marketing campaigns. By using the relevant static game model proposed recently in [1], we prove that although the marketers are in competition and therefore create tension in the network, the network reaches a consensus. Exploiting this key result, we propose a coopetition marketing strategy which combines the one-shot Nash equilibrium actions and a policy of no advertising. Under reasonable sufficient conditions, it is proved that the proposed coopetition strategy profile Pareto-dominates the one-shot Nash equilibrium strategy. This is a very encouraging result to tackle the much more challenging problem of designing Pareto-optimal and equilibrium strategies for the considered dynamical marketing game.
We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC 01, SODA 03, FOCS 18) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time -- namely $O(log P), O(log D)$ and $O(log W)$, where $P,D,W$ are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
