Scarf’s algorithm - a pivoting procedure that finds a dominating extreme point in a down-monotone polytope - can be used to show the existence of a fractional stable matching in hypergraphs. The problem of finding a fractional stable matching in hypergraphs, however, is PPAD-complete. In this work, we study the behavior of Scarf’s algorithm on arborescence hypergraphs, the family of hypergraphs in which hyperedges correspond to the paths of an arborescence. For arborescence hypergraphs, we prove that Scarf’s algorithm can be implemented to find an integral stable matching in polynomial time. En route to our result, we uncover novel structural properties of bases and pivots for the more general family of network hypergraphs. Our work provides the first proof of polynomial-time convergence of Scarf’s algorithm on hypergraphic stable matching problems, giving hope to the possibility of polynomial-time convergence of Scarf’s algorithm for other families of polytopes.

We study Prioritized Selection Problems in which an organization is presented with a set of individuals, and must choose which subset to accept. The organization makes a selection based on a priority ranking of individuals as well as other observable characteristics. We study outcome based selection rules, which are defined by a collection of feasible selections and a greedy processing algorithm.

Consider a player who can probe a sequence of n independent random variables X1, . . . , Xn with known distributions. After observing (the realized value of) Xi, the player needs to decide whether to stop and earn reward Xi, or reject the reward and probe the next variable Xi+1. The goal is to maximize the expected reward at the stopping time. This is an instance of the optimal stopping problem, which is a fundamental problem studied from many different aspects in mathematics, statistics, and computer science, and has found a wide variety of applications in sequential decision making and mechanism design.

Assignment markets involve matching with transfers, as in labor markets and housing markets. We consider a two-sided assignment market with agent types and stochastic structure similar to models used in empirical studies, and characterize the size of the core in such markets. Each agent has a randomly drawn productivity with respect to each type of agent on the other side. The value generated from a match between a pair of agents is the sum of the two productivity terms, each of which depends only on the type but not the identity of one of the agents, and a third deterministic term driven by the pair of types. We allow the number of agents to grow, keeping the number of agent types fixed. Let n be the number of agents and K be the number of types on the side of the market with more types. We find, under reasonable assumptions, that the relative variation in utility per agent over core outcomes is bounded as O*(1/n1/K), where polylogarithmic factors have been suppressed. Further, we show that this bound is tight in worst case. We also provide a tighter bound under more restrictive assumptions.

The standard problem of rationing a single over-demanded commodity has a natural bipartite extension with multiple types of a one-dimensional commodity (e.g., stored in different locations), and each agent can only consume some types of the commodity (e.g., has only access to a subset of locations).

We consider the problem of reallocating indivisible objects amongst a set of agents when the preference ordering of each agent may contain indifferences. The same model, but with strict preferences, goes back to the seminal work of Shapley and Scarf in 1974. When preferences are strict, we now know that the Top-Trading Cycles (TTC) mechanism invented by Gale is Pareto efficient, strategy-proof, and finds a core allocation, and that it is the only mechanism satisfying these properties. In the extensive literature on this problem since then, the TTC mechanism has been characterized in multiple ways, establishing its central role within the class of all allocation mechanisms. The question motivating our work is the extent to which these results can be generalized to the setting with indifferences. Our main contribution is a general framework to design strategyproof mechanisms that find a Pareto optimal allocation in the weak-core. Along the way, we establish a sufficient condition for a mechanism (within a broad class of mechanisms) to be strategyproof and use this condition to design fast algorithms for finding a "good" reallocation. Our results generalize and unify two (different) mechanisms for the reallocation problem derived, independently of each other, by Manjunath and Jaramillo, and Alcalde-Unzu and Molis.

This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights and integer deadlines that are (weakly) increasing in their arrival times. In each integer time step, at most one packet can be sent. The objective is to maximize the sum of the weights of the packets that are sent by their deadlines. The main results include an optimal (ϕ := (1 + √ 5)/2 ≈ 1.618)-competitive deterministic online algorithm, a (4/3 ≈ 1.33)-competitive randomized online algorithm against an oblivious adversary, and a 2-speed 1-competitive deterministic online algorithm. The analysis does not use a potential function explicitly, but instead modifies the adversary's buffer and credits the adversary to account for these modifications.

We introduce a graph clustering problem motivated by a stream processing application. Input to our problem is an undirected graph with vertex and edge weights. A cluster is a subset of the vertices. The {\em size} of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. The bounded size graph clustering problem ($\GC$) is to partition the vertices into clusters of size at most a given budget and minimize the total edge-weight across the clusters. In the {\em multiway cut} version of the problem, we are also given a subset of vertices called {\em terminals}. No cluster is allowed to contain more than one terminal. Our problem differs from most of the previously studied clustering problems in that the number of clusters is not specified. We first show that the feasibility version of the multiway cut $\GC$ problem, i.e., determining if there exists a clustering with bounded-size clusters satisfying the multiway cut constraint, can be solved in polynomial time. Our algorithm is based on the min-cut subroutine and an uncrossing argument. This result is in contrast with the NP-hardness of the min-max multiway cut problem, considered by Svitkina and Tardos (2004), in which the number of clusters must equal the number of terminals. Our results for the feasibility version also generalize to any symmetric submodular function. We next show that the optimization version of $\GC$ is NP-hard by showing an approximation-preserving reduction from the $\frac 13$-balanced cut problem. Our main result is an $O(\log^2 n)$-approximation to the optimization version of the multiway cut $\GC$ problem violating the budget by an $O(\log n)$ factor, where $n$ denotes the number of vertices. Our algorithm is based on a set-cover-like greedy approach which iteratively computes bounded-size clusters to maximize the number of new vertices covered.

A variant of the multiarmed bandit problem was recently introduced by Dimitriu, Tetali, and Winkler. For this model (and a mild generalization) we propose faster algorithms to compute the Gittins index. The indexability of such models follows from earlier work of Nash on generalized bandits.

Web Search Engines employ multiple so-called crawlers to maintain local copies of web pages. But these web pages are frequently updated by their owners, and therefore the crawlers must regularly revisit the web pages to maintain the freshness of their local copies. In this paper, we propose a two-part scheme to optimize this crawling process. One goal might be the minimization of the average level of staleness over all web pages, and the scheme we propose can solve this problem. Alternatively, the same basic scheme could be used to minimize a possibly more important search engine embarrassment level metric: The frequency with which a client makes a search engine query and then clicks on a returned url only to find that the result is incorrect. The first part our scheme determines the (nearly) optimal crawling frequencies, as well as the theoretically optimal times to crawl each web page. It does so within an extremely general stochastic framework, one which supports a wide range of complex update patterns found in practice. It uses techniques from probability theory and the theory of resource allocation problems which are highly computationally efficient -- crucial for practicality because the size of the problem in the web environment is immense. The second part employs these crawling frequencies and ideal crawl times as input, and creates an optimal achievable schedule for the crawlers. Our solution, based on network flow theory, is exact as well as highly efficient. An analysis of the update patterns from a highly accessed and highly dynamic web site is used to gain some insights into the properties of page updates in practice. Then, based on this analysis, we perform a set of detailed simulation experiments to demonstrate the quality and speed of our approach.

We provide scheduling algorithms that attempt to maximize the profits of a broadcast-based electronic delivery service for digital products purchased, for example, at e-commerce sites on the World Wide Web. Examples of such products include multimedia objects such as CDs and DVDs. Other examples include software and, with increasing popularity, electronic books as well. We consider two separate alternatives, depending in part on the sophistication of the set-top box receiving the product at the customer end. The first, more restrictive option, assumes that the atomic unit of transmission of the product is the entire object, which must be transmitted in order from start to finish. We provide a solution based in part on a transportation problem formulation for this so-called noncyclic scheduling problem. The second alternative, which is less restrictive, assumes that the product may be transmitted cyclically in smaller segments, starting from an arbitrary point in the object. Three heuristics are provided for this difficult cyclic scheduling problem. Both scenarios assume that the broadcasts of the same digital product to multiple customers can be "batched." We examine the effectiveness of these algorithms via simulation experiments under varying parametric assumptions. Each of the three cyclic scheduling algorithms perform better than the noncyclic algorithm. Moreover, one of the cyclic scheduling algorithms emerges as the clear winner.

In this paper we consider the problem of scheduling different classes of customers on multiple distributed servers to minimize an objective function based on per-class mean response times.This problem arises in a wide range of distributed systems, networks and applications.Within the context of our model, we observe that the optimal sequencing strategy at each of the servers is a simple static priority policy.Using this observation, we argue that the globally optimal scheduling problem reduces to finding an optimal routing matrix under this sequencing policy.We formulate the latter problem as a nonlinear programming problem and show that any interior local minimum is a global minimum, which significantly simplifies the solution of the optimization problem.In the case of Poisson arrivals, we provide an optimal scheduling strategy that also tends to minimize a function of the per-class response time variances.Applying our analysis to various static instances of the general problem leads us to rederive many results, yielding simple approximation algorithms whose guarantees match the best known results.