A canonical setting for non-monetary online resource allocation is one where agents compete over multiple rounds for a single item per round, with i.i.d. valuations and additive utilities across rounds. With $n$ symmetric agents, a natural benchmark for each agent is the utility realized by her favorite $1/n$-fraction of rounds; a line of work has demonstrated one can robustly guarantee each agent a constant fraction of this ideal utility, irrespective of how other agents behave. In particular, several mechanisms have been shown to be $1/2$-robust, and recent work established that repeated first-price auctions based on artificial credits have a robustness factor of $0.59$, which cannot be improved beyond $0.6$ using first-price and simple strategies. In contrast, even without strategic considerations, the best achievable factor is $1-1/e\approx 0.63$. In this work, we break the $0.6$ first-price barrier to get a new $0.625$-robust mechanism, which almost closes the gap to the non-strategic robustness bound. Surprisingly, we do so via a simple auction, where in each round, bidders decide if they ask for the item, and we allocate uniformly at random among those who ask. The main new ingredient is the idea of competitive subsidies, wherein we charge the winning agent an amount in artificial credits that decreases when fewer agents are bidding (specifically, when $k$ agents bid, then the winner pays proportional to $k/(k+1)$, varying the payment by a factor of 2 depending on the competition). Moreover, we show how it can be modified to get an equilibrium strategy with a slightly weaker robust guarantee of $5/(3e) \approx 0.61$ (and the optimal $1-1/e$ factor at equilibrium). Finally, we show that our mechanism gives the best possible bound under a wide class of auction-based mechanisms.

We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: (\(i\)) (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and (\(ii\)) simple distribution-agnostic mechanisms with robust utility guarantees for each individual agent, which are worse than the Nash outcome, but hold irrespective of how others behave (including possibly collusive behavior). Recent work has hinted at barriers to achieving both simultaneously. Our work however establishes this is not the case, by proposing the first mechanism in which each agent has a natural strategy that is both a Bayes-Nash equilibrium and also comes with strong robust guarantees for individual agent utilities. Our mechanism comes out of a surprising connection between the online shared resource allocation problem and implementation theory, and uses a surprising strengthening of Border’s theorem. In particular, we show that establishing robust equilibria in this setting reduces to showing that a particular subset of the Border polytope is non-empty. We establish this via a novel joint Schurconvexity argument. This strengthening of Border’s criterion for obtaining a stronger conclusion is of independent technical interest, as it may prove useful in other settings.

In many decision-making scenarios, individuals strategically choose what information to disclose to optimize their own outcomes. It is unclear whether such strategic information disclosure can lead to good societal outcomes. To address this question, we consider a competitive Bayesian persuasion model in which multiple agents selectively disclose information about their qualities to a principal, who aims to choose the candidates with the highest qualities. Using the price-of-anarchy framework, we quantify the inefficiency of such strategic disclosure. We show that the price of anarchy is at most a constant when the agents have independent quality distributions, even if their utility functions are heterogeneous. This result provides the first theoretical guarantee on the limits of inefficiency in Bayesian persuasion with competitive information disclosure.

We study the problem of fair online resource allocation via non-monetary mechanisms, where multiple agents repeatedly share a resource without monetary transfers. Previous work has shown that every agent can guarantee 1/2 of their ideal utility (the highest achievable utility given their fair share of resources) robustly, i.e., under arbitrary behavior by the other agents. While this 1/2-robustness guarantee has now been established under very different mechanisms, including pseudo-markets and dynamic max-min allocation, improving on it has appeared difficult. In this work, we obtain the first significant improvement on the robustness of online resource sharing. In more detail, we consider the widely-studied repeated first-price auction with artificial currencies. Our main contribution is to show that a simple randomized bidding strategy can guarantee each agent a 2 - √2 ≈ 0.59 fraction of her ideal utility, irrespective of others' bids. Specifically, our strategy requires each agent with fair share α to use a uniformly distributed bid whenever her value is in the top α-quantile of her value distribution. Our work almost closes the gap to the known 1 - 1/e ≈ 0.63 hardness for robust resource sharing; we also show that any static (i.e., budget independent) bidding policy cannot guarantee more than a 0.6-fraction of the ideal utility, showing our technique is almost tight.

We consider the classical Dynamic Max-min fair (DMMF) mechanism for allocating an indivisible resource without money over multiple agents and T rounds. We show that under mild assumption on value distributions, it guarantees every agent close to optimal utility in large markets.

We address the fundamental problem of selection under uncertainty by modeling it from the perspective of Bayesian persuasion. In our model, a decision maker with imperfect information always selects the option with the highest expected value. We seek to achieve fairness among the options by revealing additional information to the decision maker and hence influencing its subsequent selection. To measure fairness, we adopt the notion of majorization, aiming at simultaneously approximately maximizing all symmetric, monotone, concave functions over the utilities of the options. As our main result, we design a novel information revelation policy that achieves a logarithmic-approximation to majorization in polynomial time. On the other hand, no policy, regardless of its running time, can achieve a constant-approximation to majorization. Our work is the first non-trivial majorization result in the Bayesian persuasion literature with multidimensional information sets.

We devise an online learning algorithm – titled Switching via Monotone Adapted Regret Traces (SMART) – that adapts to the data and achieves regret that is instance optimal, i.e., simultaneously competitive on every input sequence compared to the performance of the follow-the-leader (FTL) policy and the worst case guarantee of any other input policy. We show that the regret of the SMART policy on any input sequence is within a multiplicative factor e/(e-1), approximately 1.58, of the smaller of: 1) the regret obtained by FTL on the sequence, and 2) the upper bound on regret guaranteed by the given worst-case policy. This implies a strictly stronger guarantee than typical ‘best-of-both-worlds’ bounds as the guarantee holds for every input sequence regardless of how it is generated. SMART is simple to implement as it begins by playing FTL and switches at most once during the time horizon to the worst-case algorithm. Our approach and results follow from a reduction of instance optimal online learning to competitive analysis for the ski-rental problem. We complement our competitive ratio upper bounds with a fundamental lower bound showing that over all input sequences, no algorithm can get better than a 1.43-fraction of the minimum regret achieved by FTL and the minimax-optimal policy. We present a modification of SMART that combines FTL with a “small-loss" algorithm to achieve instance optimality between the regret of FTL and the small loss regret bound.

A seller is pricing identical copies of a good to a stream of unit-demand buyers. Each buyer has a value on the good as his private information. The seller only knows the empirical value distribution of the buyer population and chooses the revenue-optimal price. We consider a widely studied third-degree price discrimination model where an information intermediary with perfect knowledge of the arriving buyer's value sends a signal to the seller, hence changing the seller's posterior and inducing the seller to set a personalized posted price. Prior work of Bergemann, Brooks, and Morris (American Economic Review, 2015) has shown the existence of a signaling scheme that preserves seller revenue, while always selling the item, hence maximizing consumer surplus. In a departure from prior work, we ask whether the consumer surplus generated is fairly distributed among buyers with different values. To this end, we aim to maximize functions of buyers’ welfare that reward more balanced surplus allocations.

We design online algorithms for fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent’s total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N,L)T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.

In many applications such as rationing medical care and supplies, university admissions, and the assignment of public housing, the decision of who receives an allocation can be justified by various normative criteria (ethical, financial, legal, etc.). Such settings have motivated the following priority-respecting allocation problem: several categories, each with a quota of interchangeable items, wish to allocate the items among a set of agents. Each category has a list of eligible agents and a priority ordering over these agents; agents may be eligible in multiple categories. The goal is to select a valid allocation: one that respects quotas, eligibility, and priorities and ensures Pareto efficiency.

We study non-monetary mechanisms for the fair and efficient allocation of reusable public resources. We consider settings where a limited resource is repeatedly shared among a set of agents, each of whom may request to use the resource over multiple consecutive rounds, receiving some utility only if they get to use the resource for the full duration of their request. Such settings are of particular significance in scientific research where large-scale instruments such as electron microscopes, particle colliders, or telescopes are shared between multiple research groups; this model also subsumes and extends existing models of repeated non-monetary allocation where the resource is demanded only for a single round.

We study the problem of designing dynamic intervention policies for minimizing cascading failures in online financial networks, as well we more general demand-supply networks. Formally, we consider a dynamic version of the celebrated Eisenberg-Noe model of financial network liabilities, and use this to study the design of external intervention policies. Our controller has a fixed resource budget in each round, and can use this to minimize the effect of demand/supply shocks in the network. We formulate the optimal intervention problem as a Markov Decision Process, and show how we can leverage the problem structure to efficiently compute optimal intervention policies with continuous interventions, and give approximation algorithms in the case of discrete interventions. Going beyond financial networks, we argue that our model captures dynamic network intervention in a much broader class of dynamic demand/supply settings with networked inter-dependencies. To demonstrate this, we apply our intervention algorithms to a wide variety of Web-related application domains, including ridesharing, online transaction platforms, and financial networks with agent mobility; in each case, we study the relationship between node centrality and intervention strength, as well as fairness properties of the optimal interventions.

We study the limits of an information intermediary in the classical Bayesian auction, where a revenue-maximizing seller sells one item to n buyers with independent private values. In addition, we have an intermediary who knows the buyers' private values, and can map these to a public signal so as to increase consumer surplus. This model generalizes the single-buyer setting proposed by Bergemann, Brooks, and Morris, who present a signaling scheme that raises the optimal consumer surplus, by guaranteeing that the item is always sold and the seller gets the same revenue as without signaling. Our work aims to understand how this result ports to the setting with multiple buyers.

We consider the problem of allocating a set of divisible goods to N agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of T periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial O(N), unless it is given additional information about the agents' values. Then, in line with the emerging area of “algorithms with predictions”, we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the T periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of O(log N) and O(log T) if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of O(log1–∊ N) or O(log1–∊ T) for any constant ∊ > 0.

With the growing capabilities of intelligent systems, the integration of robots in our everyday life is increasing. However, when interacting in such complex human environments, the occasional failure of robotic systems is inevitable. The field of explainable AI has sought to make complex-decision making systems more interpretable but most existing techniques target domain experts. On the contrary, in many failure cases, robots will require recovery assistance from non-expert users. In this work, we introduce a new type of explanation, εerr, that explains the cause of an unexpected failure during an agent's plan execution to non-experts. In order for error explanations to be meaningful, we investigate what types of information within a set of hand-scripted explanations are most helpful to non-experts for failure and solution identification. Additionally, we investigate how such explanations can be autonomously generated, extending an existing encoder-decoder model, and generalized across environments. We investigate such questions in the context of a robot performing a pick-and-place manipulation task in the home environment. Our results show that explanations capturing the context of a failure and history of past actions, are the most effective for failure and solution identification among non-experts. Furthermore, through a second user evaluation, we verify that our model-generated explanations can generalize to an unseen office environment, and are just as effective as the hand-scripted explanations.

In many settings, resources are allocated among agents repeatedly over time without the use of monetary transfers: consider, for example, allocating server-time to company employees, rooms to students, or food among food banks. Here, the central challenge is to allocate resources efficiently despite the absence of payments. In this work we study a simple online variant of the standard Fisher market, where we endow all agents with a budget of artificial credits, and then repeatedly run simultaneous first-price auctions for each item in each period. Owing to their simplicity, such mechanisms have been gaining in popularity, with several recent successful implementations, most notably, by Feeding America for US food banks. Our goal in this paper is to understand the incentive and efficiency properties of these mechanisms.

We introduce the technique of adaptive discretization to design an efficient model-based episodic reinforcement learning algorithm in large (potentially continuous) state-action spaces. Our algorithm is based on optimistic one-step value iteration extended to maintain an adaptive discretization of the space. From a theoretical perspective we provide worst-case regret bounds for our algorithm which are competitive compared to the state-of-the-art model-based algorithms. Moreover, our bounds are obtained via a modular proof technique which can potentially extend to incorporate additional structure on the problem. From an implementation standpoint, our algorithm has much lower storage and computational requirements due to maintaining a more efficient partition of the state and action spaces. We illustrate this via experiments on several canonical control problems, which shows that our algorithm empirically performs significantly better than fixed discretization in terms of both faster convergence and lower memory usage. Interestingly, we observe empirically that while fixed discretization model-based algorithms vastly outperform their model-free counterparts, the two achieve comparable performance with adaptive discretization.

Robots operating without close human supervision might need to rely on a remote call center of operators for assistance in the event of a failure. In this work, we investigate the effects of providing decision support through diagnosis suggestions, as feedback, and action recommendations, as feedforward, to the human operators. We conduct a 10-condition user study involving 200 participants on Amazon Mechanical Turk to evaluate the effects of providing noisy and noise-free diagnosis suggestions and/or action recommendations to operators. We find that although action recommendations (feedforward) have a greater effect on successful error resolution than diagnosis information (feedback), the feedback likely helps ameliorate the deleterious effects of noise. Therefore, we find that error recovery interfaces should display both diagnosis and action recommendations for maximum effectiveness.

Multi-Label Hierarchical Text Classification (MLHTC) is the task of categorizing documents into one or more topics organized in an hierarchical taxonomy.MLHTC can be formulated by combining multiple binary classification problems with an independent classifier for each category.We propose a novel transfer learning based strategy, HTrans, where binary classifiers at lower levels in the hierarchy are initialized using parameters of the parent classifier and fine-tuned on the child category classification task.In HTrans, we use a Gated Recurrent Unit (GRU)-based deep learning architecture coupled with attention.Compared to binary classifiers trained from scratch, our HTrans approach results in significant improvements of 1% on micro-F1 and 3% on macro-F1 on the RCV1 dataset.Our experiments also show that binary classifiers trained from scratch are significantly better than single multi-label models.

As robots become increasingly prevalent in human environments, there will inevitably be times when the robot needs to interrupt a human to initiate an interaction. Our work introduces the first interruptibility-aware mobile-robot system, which uses social and contextual cues online to accurately determine when to interrupt a person. We evaluate multiple non-temporal and temporal models on the interruptibility classification task, and show that a variant of Conditional Random Fields (CRFs), the Latent-Dynamic CRF, is the most robust, accurate, and appropriate model for use on our system. Additionally, we evaluate different classification features and show that the observed demeanor of a person can help in interruptibility classification; but in the presence of detection noise, robust detection of object labels as a visual cue to the interruption context can improve interruptibility estimates. Finally, we deploy our system in a large-scale user study to understand the effects of interruptibility-awareness on human-task performance, robot-task performance, and on human interpretation of the robot’s social aptitude. Our results show that while participants are able to maintain task performance, even in the presence of interruptions, interruptibility-awareness improves the robot’s task performance and improves participant social perceptions of the robot.

Optimizing shared vehicle systems (bike-sharing/car-sharing/ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of complex network externalities. In particular, changes in the demand/supply at any location (via dynamic pricing, rebalancing of empty vehicles, etc.) affect future supply throughout the system within short timescales. Such externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze and design shared vehicle systems. However, using such models to design pricing/control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex.

Non-monetary mechanisms for repeated resource allocation are gaining widespread use in many real-world settings. Our aim in this work is to study the allocative efficiency and incentive properties of simple repeated mechanisms based on artificial currencies. Within this framework, we make three main contributions:

Recent years have witnessed the rise of many successful e-commerce marketplace platforms like the Amazon marketplace, AirBnB, Uber/Lyft, and Upwork, where a central platform mediates economic transactions between buyers and sellers. A common feature of many of these two-sided marketplaces is that the platform has full control over search and discovery, but prices are determined by the buyers and sellers. Motivated by this, we study the algorithmic aspects of market segmentation via directed discovery in two-sided markets with endogenous prices. We consider a model where an online platform knows each buyer/seller's characteristics, and associated demand/supply elasticities. Moreover, the platform can use discovery mechanisms (search, recommendation, etc.) to control which buyers/sellers are visible to each other. We develop efficient algorithms for throughput (i.e. volume of trade) and welfare maximization with provable guarantees under a variety of assumptions on the demand and supply functions. We also test the validity of our assumptions on demand curves inferred from NYC taxicab log-data, as well as show the performance of our algorithms on synthetic experiments.

In the study of human learning, there is broad evidence that our ability to retain information improves with repeated exposure and decays with delay since last exposure. This plays a crucial role in the design of educational software, leading to a trade-off between teaching new material and reviewing what has already been taught. A common way to balance this trade-off is spaced repetition, which uses periodic review of content to improve long-term retention. Though spaced repetition is widely used in practice, e.g., in electronic flashcard software, there is little formal understanding of the design of these systems. Our paper addresses this gap in three ways. First, we mine log data from spaced repetition software to establish the functional dependence of retention on reinforcement and delay. Second, we use this memory model to develop a stochastic model for spaced repetition systems. We propose a queueing network model of the Leitner system for reviewing flashcards, along with a heuristic approximation that admits a tractable optimization problem for review scheduling. Finally, we empirically evaluate our queueing model through a Mechanical Turk experiment, verifying a key qualitative prediction of our model: the existence of a sharp phase transition in learning outcomes upon increasing the rate of new item introductions.

Flashcards are a popular study tool for exploiting the spacing effect -- the phenomenon in which periodic, spaced review of educational content improves long-term retention. The Leitner system is a simple heuristic algorithm for scheduling reviews such that forgotten items are reviewed more frequently than recalled items. We propose a formalization of the Leitner system as a queueing network model, and formulate optimal review scheduling as a throughput-maximization problem. Through simulations and theoretical analysis, we find that the Leitner Queue Network (LQN) model has desirable properties and gives insight into general principles for spaced repetition.

We present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source distribution to a target node, we present a new bidirectional estimator with simple yet strong guarantees on correctness and performance, and 3x to 8x speedup over existing estimators in experiments on a diverse set of networks. Moreover, it has a clean algebraic structure which enables it to be used as a primitive for the Personalized PageRank Search problem: Given a network like Facebook, a query like "people named John," and a searching user, return the top nodes in the network ranked by PPR from the perspective of the searching user. Previous solutions either score all nodes or score candidate nodes one at a time, which is prohibitively slow for large candidate sets. We develop a new algorithm based on our bidirectional PPR estimator which identifies the most relevant results by sampling candidates based on their PPR; this is the first solution to PPR search that can find the best results without iterating through the set of all candidate results. Finally, by combining PPR sampling with sequential PPR estimation and Monte Carlo, we develop practical algorithms for PPR search, and we show via experiments that our algorithms are efficient on networks with billions of edges.

Siddhartha Banerjee, Prasenjit Mitra. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2015.

The availability of only a limited number of contributors on Wikipedia cannot ensure consistent growth and improvement of the online encyclopedia. With information being scattered on the web, our goal is to automate the process of generation of content for Wikipedia. In this work, we propose a technique of improving stubs on Wikipedia that do not contain comprehensive information. A classifier learns features from the existing comprehensive articles on Wikipedia and recommends content that can be added to the stubs to improve the completeness of such stubs. We conduct experiments using several classifiers - Latent Dirichlet Allocation (LDA) based model, a deep learning based architecture (Deep belief network) and TFIDF based classifier. Our experiments reveal that the LDA based model outperforms the other models (~6% F-score). Our generation approach shows that this technique is capable of generating comprehensive articles. ROUGE-2 scores of the articles generated by our system outperform the articles generated using the baseline. Content generated by our system has been appended to several stubs and successfully retained in Wikipedia.

Summaries of meetings are very important as they convey the essential content of discussions in a concise form. Both participants and non-participants are interested in the summaries of meetings to plan for their future work. Generally, it is time consuming to read and understand the whole documents. Therefore, summaries play an important role as the readers are interested in only the important context of discussions. In this work, we address the task of meeting document summarization. Automatic summarization systems on meeting conversations developed so far have been primarily extractive, resulting in unacceptable summaries that are hard to read. The extracted utterances contain disfluencies that affect the quality of the extractive summaries. To make summaries much more readable, we propose an approach to generating abstractive summaries by fusing important content from several utterances. We first separate meeting transcripts into various topic segments, and then identify the important utterances in each segment using a supervised learning approach.

We develop a new bidirectional algorithm for estimating Markov chain multi-step transition probabilities: given a Markov chain, we want to estimate the probability of hitting a given target state in $\ell$ steps after starting from a given source distribution. Given the target state $t$, we use a (reverse) local power iteration to construct an `expanded target distribution', which has the same mean as the quantity we want to estimate, but a smaller variance -- this can then be sampled efficiently by a Monte Carlo algorithm. Our method extends to any Markov chain on a discrete (finite or countable) state-space, and can be extended to compute functions of multi-step transition probabilities such as PageRank, graph diffusions, hitting/return times, etc. Our main result is that in `sparse' Markov Chains -- wherein the number of transitions between states is comparable to the number of states -- the running time of our algorithm for a uniform-random target node is order-wise smaller than Monte Carlo and power iteration based algorithms; in particular, our method can estimate a probability $p$ using only $O(1/\sqrt{p})$ running time.

We study optimal pricing strategies for ride-sharing platforms, using a queueing-theoretic economic model. Analysis of pricing in such settings is complex: On one hand these platforms are two-sided - this requires economic models that capture the incentives of both drivers and passengers. On the other hand, these platforms support very high temporal-resolution for data collection and pricing - this requires stochastic models that capture the dynamics of drivers and passengers in the system.

In this work, we aim to create Wikipedia pages on plays automatically by extracting relevant information from various web sources. Our approach involves building an efficient classifier that can classify web documents as play scripts. From the set of correctly classified instances of play scripts, we extract relevant play-related information from the documents and use it to obtain additional information from various sources on the web. This information is aggregated and human-readable Wikipedia pages are created using a bot. The results of our experiments show that classifiers trained by combining our designed features along with "bag-of-words" (bow) features outperform classifiers trained using only bow features. Our approach further shows that good quality human-readable pages can be created using our bot. Such automatic page generation process can eventually ensure a more complete Wikipedia.

We study the effect of external infection sources on phase transitions in epidemic processes. In particular, we consider an epidemic spreading on a network via the SIS/SIR dynamics, which in addition is aided by external agents - sources unconstrained by the graph, but possessing a limited infection rate or virulence. Such a model captures many existing models of externally aided epidemics, and finds use in many settings - epidemiology, marketing and advertising, network robustness, etc. We provide a detailed characterization of the impact of external agents on epidemic thresholds. In particular, for the SIS model, we show that any external infection strategy with constant virulence either fails to significantly affect the lifetime of an epidemic, or at best, sustains the epidemic for a lifetime which is polynomial in the number of nodes. On the other hand, a random external-infection strategy, with rate increasing linearly in the number of infected nodes, succeeds under some conditions to sustain an exponential epidemic lifetime. We obtain similar sharp thresholds for the SIR model, and discuss the relevance of our results in a variety of settings.

We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from s to t, guaranteeing that the relative error is small as long πs(t) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved.

An essential primitive for an efficient research ecosystem is partial-progress sharing (PPS) -- whereby a researcher shares information immediately upon making a breakthrough. This helps prevent duplication of work; however there is evidence that existing reward structures in research discourage partial-progress sharing. Ensuring PPS is especially important for new online collaborative-research platforms, which involve many researchers working on large, multi-stage problems.

We investigate the sensitivity of epidemic behavior to a bounded susceptibility constraint -- susceptible nodes are infected by their neighbors via the regular SI/SIS dynamics, but subject to a cap on the infection rate. Such a constraint is motivated by modern social networks, wherein messages are broadcast to all neighbors, but attention spans are limited. Bounded susceptibility also arises in distributed computing applications with download bandwidth constraints, and in human epidemics under quarantine policies.

We study epidemic spreading processes in large networks, when the spread is assisted by a small number of external agents: infection sources with bounded spreading power, but whose movement is unrestricted vis-à-vis the underlying network topology. For networks, which are spatially constrained, we show that the spread of infection can be significantly speeded up even by a few such external agents infecting randomly. Moreover, for general networks, we derive upper bounds on the order of the spreading time achieved by certain simple (random/greedy) external-spreading policies. Conversely, for certain common classes of networks such as line graphs, grids, and random geometric graphs, we also derive lower bounds on the order of the spreading time over all (potentially network-state aware and adversarial) external-spreading policies; these adversarial lower bounds match (up to logarithmic factors) the spreading time achieved by an external agent with a random spreading policy. This demonstrates that random, state-oblivious infection-spreading by an external agent is in fact order-wise optimal for spreading in such spatially constrained networks.

We consider the problem of linear network coding over communication networks, representable by directed acyclic graphs, with multiple groupcast sessions: the network comprises of multiple destination nodes, each desiring messages from multiple sources. We adopt an interference alignment perspective, providing new insights into designing practical network coding schemes as well as the impact of network topology on the complexity of the alignment scheme. In particular, we show that under certain (polynomial-time checkable) constraints on networks with K sources, it is possible to achieve a rate of 1/(L+d+1) per source using linear network coding coupled with interference alignment, where each destination receives messages from L sources (L <; K), and d is a parameter, solely dependent on the network topology, that satisfies 0 ≤ d <; K - L.

We study infection spreading on large static networks when the spread is assisted by a small number of additional virtually mobile agents. For networks which are “spatially constrained”, we show that the spread of infection can be significantly sped up even by a few virtually mobile agents acting randomly. More specifically, for general networks with bounded virulence (e.g., a single or finite number of random virtually mobile agents), we derive upper bounds on the order of the time taken (as a function of network size) for infection to spread. Conversely, for certain common classes of networks such as linear graphs, grids and random geometric graphs, we also derive lower bounds on the order of the spreading time over all (potentially network-state aware and adversarial) virtual mobility strategies. We show that up to a logarithmic factor, these lower bounds for adversarial virtual mobility match the upper bounds on spreading via an agent with random virtual mobility. This demonstrates that random, state-oblivious virtual mobility is in fact order-wise optimal for dissemination in such spatially constrained networks.

We seek to develop joint aggregation, routing, and scheduling algorithms that, for any graph topology and a large class of functions, have analytically provable performance benefits due to in-network computation as compared to simple data forwarding. To this end, we define a class of functions, the Fully-Multiplexible functions, which includes several functions such as parity, k-th order statistic and range, and for which we can exactly characterize the maximum achievable refresh rate of the network in terms of an underlying graph primitive, the min-mincut. In wireline networks, we show that the maximum refresh rate is achievable by a simple algorithm that is dynamic, distributed, and only dependent on local information. In the case of wireless networks, we provide a MaxWeight-like algorithm with dynamic flow splitting that is shown to be throughput-optimal.