We study cost-sharing games in real-time scheduling systems where the server’s activation cost in every time slot is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive congestion effect for the jobs) and when it is greater than one (inducing negative congestion effect for the jobs). For the former case, we provide tight bounds on the price of anarchy, and show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then turn to analyze payment mechanism with arbitrary cost-sharing, that is, when the strategy of a player includes also its payment. We show that our mechanism reduces the price of anarchy of games with n jobs and unit server costs from $\mathsf{\Theta }\left(\sqrt{n}\right)$ to 2. We also show that, for a restricted class of instances, a similar improvement is achieved for monomial server costs. This is not the case, however, for unrestricted instances of monomial costs, for which we prove that the price of anarchy remains super-constant for our mechanism. For systems with load-independent activation costs, we show that our mechanism can produce an optimal solution which is stable against coordinated deviations.

Generating alternative routes in road networks is an application of significant interest for online navigation systems. A high quality set of diverse alternate routes offers two functionalities - (a) support multiple (unknown) preferences that the user may have; and (b) robust changes in network conditions. We formulate a new quantification of the latter in this paper, and propose a novel method to produce alternative routes based on concepts from electrical flows and their decompositions. Our method is fundamentally different from the main techniques that produce alternative routes in road networks, which are the penalty and the plateau methods, with the former providing high quality results but being too slow for practical use and the latter being fast but suffering in terms of quality. We evaluate our method against the penalty and plateau methods, showing that it is as fast as the plateau method while also recovering much of the headroom towards the quality of the penalty method. The metrics we use to evaluate performance include the stretch (the average cost of the routes), the diversity , and the robustness (the connectivity between the origin and destination) of the induced set of routes.

Historically, much of machine learning research has focused on the performance of the algorithm alone, but recently more attention has been focused on optimizing joint human-algorithm performance. Here, we analyze a specific type of human-algorithm collaboration where the algorithm has access to a set of n items, and presents a subset of size k to the human, who selects a final item from among those k. This scenario could model content recommendation, route planning, or any type of labeling task. Because both the human and algorithm have imperfect, noisy information about the true ordering of items, the key question is: which value of k maximizes the probability that the best item will be ultimately selected? For k=1, performance is optimized by the algorithm acting alone, and for k=n it is optimized by the human acting alone. Surprisingly, we show that for multiple of noise models, it is optimal to set k in [2, n-1] - that is, there are strict benefits to collaborating, even when the human and algorithm have equal accuracy separately. We demonstrate this theoretically for the Mallows model and experimentally for the Random Utilities models of noisy permutations. However, we show this pattern is *reversed* when the human is anchored on the algorithm's presented ordering - the joint system always has strictly worse performance. We extend these results to the case where the human and algorithm differ in their accuracy levels, showing that there always exist regimes where a more accurate agent would strictly benefit from collaborating with a less accurate one, but these regimes are asymmetric between the human and the algorithm's accuracy.

In this paper we present and evaluate the performance of a routing and link scheduling algorithm for millimeter wave backhaul networks. The proposed algorithm models the access point behavior as being selfish by considering access points always aiming to maximize their individual utility, rather than the global optimization objective. Our system utilizes popular concepts from the economics and fairness literature. Specifically, in order to forward packets between the access points that comprise the backhaul network, the Shapley value method is applied, which is shown to induce solutions with reduced latency. The performance of the proposed algorithm is evaluated in terms of total delay and price of anarchy, which represents the inefficiency of a scheduling policy when users are allowed to adapt their rates in a selfish manner and reach an equilibrium. A relaxed version of the problem is also presented, providing a lower bound on the value of the optimal solution. According to simulation results, the system that employs the proposed algorithm outperforms in terms of delay and price of anarchy a system that considers a First-In-First-Out packet forwarding policy, and a system that employs local search global optimization, under which users aim at optimizing the overall network delay.