On the structure and complexity of worst-case equilibria

In the resource allocation game introduced by Koutsoupias and Papadimitriou, n$n$ jobs of different weights are assigned to m$m$ identical machines by selfish agents. For this game, it has been conjectured by several authors that the fully mixed Nash equilibrium (FMNE) is the worst possible w.r.t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial, and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE by applying a known FPRAS.     

Hierarchies and Space Measures for Pointer Machines

We present two definitions of space complexity for Schönhage′s pointer machine (PM): a uniform measure, mass, and a logarithmic measure, capacity. We consider how each space measure affects the time and space relationships between pointer machines and the more classical models of computation. For example, we show that a Turing machine of space complexity s can be simulated by a pointer machine of mass complexity O(s/log s) in real time. This is an improvement of a result of van Emde Boas. We show that space compression is possible for pointer machines, and we show that the time and space hierarchies for pointer machines are tight. We also present a simulation of an alternating pointer machine of time complexity t by a deterministic pointer machine of mass complexity O(t/log t).     

Semi-online Machine Covering on Two Uniform Machines with Known Total Size

This paper investigates semi-online scheduling problem with known total size on two uniform machines for maximizing the minimum machine completion time. Lower bounds and optimal algorithms for every s≥1 are given, where s is the speed ratio of two machines. Both the overall competitive ratio and the competitive ratio for are strictly smaller than those of the optimal algorithms of the corresponding semi-online scheduling problem with known optimal value. It indicates that two related semi-online problems are different.     

Competitive ratio of List Scheduling on uniform machines and randomized heuristics

We study online scheduling on m uniform machines, where m−1 of them have a reference speed 1 and the last one a speed s with 0≤s≤1. The competitive ratio of the well-known List Scheduling (LS) algorithm is determined. For some values of s and m=3, LS is proven to be the best deterministic algorithm. We describe a randomized heuristic for m machines. Finally, for the case m=3, we develop and analyze the competitive ratio of a randomized algorithm which outperforms LS for any s.     

Worst-Case Nash Equilibria in Restricted Routing

We study the network routing problem with restricted and related links.There are parallel links with possibly different speeds,between a source and a sink.Also there are users,and each user has a traffic of some weight to assign to one of the links from a subset of all the links,named his/her allowable set.The users choosing the same link suffer the same delay,which is equal to the total weight assigned to that link over its speed.A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link.To measure the performance degradation of the system due to the selfish behavior of all the users,Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA),which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution.The PoA for this restricted related model has been studied,and a linear lower bound was obtained.However in their bad instance,some users can only use extremely slow links.This is a little artificial and unlikely to appear in a real world.So in order to better understand this model,we introduce a parameter for the system,and prove a better Price of Anarchy in terms of the parameter.We also show an important application of our result in coordination mechanism design for task scheduling game.We propose a new coordination mechanism,Group-Makespan,for unrelated selfish task scheduling game with improved price of anarchy.     

A note on MULTIFIT scheduling for uniform machines

In this note, we derive the tight worst case bound √6/2+(1/2) ^k for scheduling with the MULTIFIT heuristic on two parallel uniform machines withk calls of FFD within MULTIFIT. When MULTIFIT is combined with LPT as an incumbent algorithm the worst case bound decreases to √2+1/2+(1/2) ^k . Partially supported by SFB F003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung and by the National Natural Science Foundation of China, Grant 19701028.     

Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.     

Cost Sharing Mechanisms for Fair Pricing of Resource Usage

We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource it chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove:

Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy

We investigate the effect of linear independence in the strategies of congestion games on the convergence time of best improvement sequences and on the pure Price of Anarchy. In particular, we consider symmetric congestion games on extension-parallel networks, an interesting class of networks with linearly independent paths, and establish two remarkable properties previously known only for parallel-link games. We show that for arbitrary (non-negative and non-decreasing) latency functions, any best improvement sequence reaches a pure Nash equilibrium in at most as many steps as the number of players, and that for latency functions in class $\mathcal{D}$ , the pure Price of Anarchy is at most $\rho(\mathcal{D})$ , i.e. it is bounded by the Price of Anarchy for non-atomic congestion games. As a by-product of our analysis, we obtain that for symmetric network congestion games with latency functions in class $\mathcal{D}$ , the Price of Stability is at most $\rho(\mathcal{D})$ .     

A new algorithm for online uniform-machine scheduling to minimize the makespan

We consider the online scheduling problem with m−1, m?2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1?s?2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s=2. In this note we present a 2.45-competitive algorithm for m?4 and any s, 1?s?2.     

Preemptive stochastic online scheduling on two uniform machines

This paper addresses a stochastic online scheduling problem in which a set of independent jobs are to be processed by two uniform machines whose speeds are 1 and s(s?1). Each job has a processing time, which is a random variable with an arbitrary distribution, and all the jobs are arriving overtime, which means that no information of the job is known in advance before its arrival. During the processing, jobs are allowed to be preempted and resumed later. The objective is to minimize the sum of expected weighted completion times. In this paper, the optimal policy, named SMPR, is designed for the single-machine preemptive stochastic scheduling problem where jobs have a common arriving time. Based on SMPR, the online approximative policy-UMPR, is devised for the preemptive stochastic online scheduling on two uniform machines. Then, UMPR is proved to have an approximation factor of 2. Furthermore, it is concluded that UMPR could not have a smaller approximation factor than 2, which means 2 is the approximation ratio of UMPR for the two-uniform-machine scheduling problem.     

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints

Abstract. Modern computer systems distribute computation among several machines to speed up the execution of programs. Yet, setup and communication costs, as well as parallelism constraints, bound the number of machines that can share the execution of a given application, and the number of machines by which it can be processed simultaneously . We study the resulting scheduling problem, stated as follows. Given a set of n jobs and m uniform machines, assign the jobs to the machines subject to parallelism and machine allotment constraints, such that the overall completion time of the schedule (or makespan ) is minimized. Indeed, the multiprocessor scheduling problem (where each job can be processed by a single machine) is a special case of our problem; thus, our problem is strongly NP-hard. We present a (1+ α) -approximation algorithm for this problem, where α ∈ (0,1] depends on the minimal number of machine allotments and the minimal parallelism allowed for any job. Also, we show that when the maximal number of machines that can share the execution of a job is some fixed constant, our problem has a polynomial time approximation scheme ; for other special cases we give optimal polynomial time algorithms. Finally, through the relation of our problem to the classic preemptive scheduling problem on multiple machines, we shed some fresh light on what is known in scheduling folklore as the power of preemption.     

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou’s network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if ? _e (x) is the latency function of an edge e, we replace it by $\hat{\ell}_{e}(x)$ with $\ell_{e}(x) \le \hat{\ell}_{e}(x)$ for all x. Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if $\hat{C}_{N} (r)$ denotes the cost of the worst Nash flow in the modified network for rate r and C _opt (r) denotes the cost of the optimal flow in the original network for the same rate then $$\mathit{ePoA} = \max_{r \ge 0} \frac{\hat{C}_N(r)}{C_{\mathit{opt}}(r)}. $$ We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4=1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.     

On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

We study the efficiency of the proportional allocation mechanism that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents’ valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4/3 bound for pure equilibria Johari and Tsitsiklis (Math. Oper. Res. 29(3), 407–435 2004). Next, we upper bound the PoA over Bayesian equilibria by 2 when agents’ valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by any simple or scale-free mechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.     

Pareto-optimal Nash equilibrium in capacity allocation game for self-managed networks

In this paper we introduce a capacity allocation game which models the problem of maximizing network utility from the perspective of distributed noncooperative agents. Motivated by the idea of self-managed networks, in the developed framework the decision-making entities are associated with individual transmission links, deciding on the way they split capacity among concurrent flows. An efficient decentralized algorithm is given for computing a strongly Pareto-optimal strategies, constituting a pure Nash equilibrium. Subsequently, we discuss the properties of the introduced game related to the Price of Anarchy and Price of Stability. The paper is concluded with an experimental study.     

Approximation for scheduling on uniform nonsimultaneous parallel machines

We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.     

List scheduling for jobs with arbitrary release times and similar lengths

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time and length in [1,r] with r≥1 on m parallel identical machines. For the list scheduling algorithm, we give an upper bound of the competitive ratio for any m≥1 and show that the upper bound is tight when m=1. When m=2, we present a tight bound for r≥4. For r<4, we give a lower bound and show that 2 provides an upper bound. Li’s work was supported in part by the National Natural Science Foundation of China (No. 10771060).     

Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l_p norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾ 1. For minimizing the l_p norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p.     

A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem

This note considers the longest processing time heuristic for scheduling n independent jobs on two uniform parallel machines to minimize the makespan. A posterior worst-case performance ratio, by depending on the index of the latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.     

Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal.