In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the minmax version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the minmax problem is to order the common elements to minimize the maximum objective of all agentsthus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.
more » « less NSFPAR ID:
 10416066
 Publisher / Repository:
 Annual AAAI Conference on Artificial Intelligence
 Date Published:
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 37
 Issue:
 6
 ISSN:
 21595399
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We study the maxmin fairness of multitask jobs in distributed computing platforms. We consider a setting where each job consists of a set of parallel tasks that need to be processed on different servers, and the job is completed once all its tasks finish processing. Each job is associated with a utility which is a decreasing function of its completion time, and captures how sensitive it is to latency. The objective is to schedule tasks in a way that achieves maxmin fairness for jobsβ utilities, i.e., an optimal schedule in which any attempt to improve the utility of a job necessarily results in hurting the utility of some other job with smaller or equal utility.We first show a strong result regarding NPhardness of finding the maxmin fair vector of job utilities. The implication of this result is that achieving maxmin fairness in many other distributed scheduling problems (e.g., coflow scheduling) is NPhard. We then proceed to define two notions of approximation solutions: one based on finding a certain number of elements of the maxmin fair vector, and the other based on a singleobjective optimization whose solution gives the maxmin fair vector. We develop scheduling algorithms that provide guarantees under these approximation notions, using dynamic programming and random perturbation of tasksβ processing times. We verify the performance of our algorithms through extensive simulations, using a real traffic trace from a large Google cluster.more » « less

We study the maxmin fairness of multitask jobs in distributed computing platforms. We consider a setting where each job consists of a set of parallel tasks that need to be processed on different servers, and the job is completed once all its tasks finish processing. Each job is associated with a utility which is a decreasing function of its completion time, and captures how sensitive it is to latency. The objective is to schedule tasks in a way that achieves maxmin fairness for jobs' utilities, i.e., an optimal schedule in which any attempt to improve the utility of a job necessarily results in hurting the utility of some other job with smaller or equal utility. We first show a strong result regarding NPhardness of finding the maxmin fair vector of job utilities. The implication of this result is that achieving maxmin fairness in many other distributed scheduling problems (e.g., coflow scheduling) is NPhard. We then proceed to define two notions of approximation solutions: one based on finding a certain number of elements of the maxmin fair vector, and the other based on a singleobjective optimization whose solution gives the maxmin fair vector. We develop scheduling algorithms that provide guarantees under these approximation notions, using dynamic programming and random perturbation of tasks' processing times. We verify the performance of our algorithms through extensive simulations, using a real traffic trace from a large Google cluster.more » « less

null (Ed.)In this work we consider the problem of online submodular maximization under a cardinality constraint with differential privacy (DP). A stream of T submodular functions over a common finite ground set U arrives online, and at each timestep the decision maker must choose at most k elements of U before observing the function. The decision maker obtains a profit equal to the function evaluated on the chosen set and aims to learn a sequence of sets that achieves low expected regret. In the fullinformation setting, we develop an (π,πΏ)DP algorithm with expected (11/e)regret bound of π(π2logππlogπ/πΏβπ). This algorithm contains k ordered experts that learn the best marginal increments for each item over the whole time horizon while maintaining privacy of the functions. In the bandit setting, we provide an (π,πΏ+π(πβπ1/3))DP algorithm with expected (11/e)regret bound of π(logπ/πΏβπ(π(πlogπ)1/3)2π2/3). One challenge for privacy in this setting is that the payoff and feedback of expert i depends on the actions taken by her i1 predecessors. This particular type of information leakage is not covered by postprocessing, and new analysis is required. Our techniques for maintaining privacy with feedforward may be of independent interest.more » « less

MultiAgent Path Finding (MAPF) computes a set of collisionfree paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MAPF called MultiAgent Teamwise Cooperative Path Finding (MATCPF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MATCPF is thus a multiobjective planning problem with the goal of finding the entire Paretooptimal front that represents all possible tradeoffs among the objectives of the teams. To solve MATCPF, we propose two algorithms TCCBS and TCM*, which leverage the existing CBS and M* for conventional MAPF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Paretooptimal front. We present numerical results for several types of MATCPF problems.more » « less

We prove that, for a generic set of smooth prescription functions h on a closed ambient manifold, there always exists a nontrivial, smooth, closed hypersurface of prescribed mean curvature h. The solution is either an embedded minimal hypersurface with integer multiplicity, or a nonminimal almost embedded hypersurface of multiplicity one. More precisely, we show that our previous minmax theory, developed for constant mean curvature hypersurfaces, can be extended to construct minmax prescribed mean curvature hypersurfaces for certain classes of prescription function, including a generic set of smooth functions, and all nonzero analytic functions. In particular we do not need to assume that h has a sign.more » « less