Over a quarter of the global population remains without access to the Internet in 2026, primarily due to cost and limited infrastructure in developing regions. This gap is becoming more consequential as access to information increasingly depends on AI systems that presume reliable, high-bandwidth connectivity. In response, we present WebFM, a low-cost, scalable Web and AI access solution that builds on widely deployed infrastructure in developing regions: FM radio for downlink broadcasting and SMS for personalized uplink. Prior work on web-over-FM is limited to simulations, short-range experiments, and lossless links, leaving the effects of geographically induced signal variability largely unexplored. WebFM addresses this gap through several system-level innovations to effectively transmit Web content and enable LLM interactions over sound over FM radio, in a reliable and compressed form. For example, we introduce a loss-resilient file format for encoding webpages and modify Android to leverage built-in FM tuners, allowing deployment across a wide range of devices without requiring root access. We enable ChatGPT interactions by allowing users to submit prompts over SMS and receive model responses via FM broadcast. Finally, we preemptively transmit popular pages and a subset of their internal pages while the server is idle, improving user experience during peak hours. We deployed WebFM at an FM radio station in Cameroon for six weeks with 30 participants. Our evaluation shows a sustained downlink throughput of 10 kbps, less than 20% loss for most transmissions with signal strength above -90 dBm, and strong user engagement across both web browsing and ChatGPT interactions.

It has been argued that human social and economic interactions depend on the perception of mind of the interacting partner. Minds are perceived along two dimensions: experience, i.e., the ability to feel, and agency, i.e., the ability to act and take responsibility for one’s actions. Here, we pair participants with bots in a dictator game (to measure altruism) and a trust game (to measure trust) while varying the bots’ perceived experience and agency. Here, we pair participants with bots in a dictator game (to measure altruism) and a trust game (to measure trust) while varying the bots' perceived experience and agency. Results demonstrate that the perception of experience influences altruism, while the perception of agency influences trust.

Advanced Persistent Threats (APTs) are sophisticated, targeted cyberattacks designed to gain unauthorized access to systems and remain undetected for extended periods. To evade detection, APT cyberattacks deceive defense layers with breaches and exploits, thereby complicating exposure by traditional anomaly detection-based security methods. The challenge of detecting APTs with machine learning is compounded by the rarity of relevant datasets and the significant imbalance in the data, which makes the detection process highly burdensome. We present AE-APT, a deep learning-based tool for APT detection that features a family of AutoEncoder methods ranging from a basic one to a Transformer-based one. We evaluated our tool on a suite of provenance trace databases produced by the DARPA Transparent Computing program, where APT-like attacks constitute as little as 0.004% of the data. The datasets span multiple operating systems, including Android, Linux, BSD, and Windows, and cover two attack scenarios. The outcomes showed that AE-APT has significantly higher detection rates compared to its competitors, indicating superior performance in detecting and ranking anomalies. Data and code: https://github.com/ae-apt/AE-APT.

The technological and online experiences of billions worldwide are dominated by a handful of companies known as “Big Tech.” Despite this being a cause for concern in governmental, economic, and ethical spheres, the literature lacks a study exploring the impact of public scandals on, and the global sentiment toward, Big Tech. Here, we quantify the power of Big Tech by analyzing their acquisitions, market capitalization, and number of monthly active users. Moreover, we utilize the synthetic control method to estimate the effect of public scandals on the stock price of two Big Tech companies, and find that they had no lasting effect. We also analyze the number of tweets mentioning these scandals, and find that they quickly fade from the spotlight. To explore public sentiment, we survey 5300 participants across 25 countries, and find that those from countries with lower digital literacy and more authoritarian regimes are more trusting of Big Tech. Furthermore, we find that one in three feels they lack control over the data collected about them, and one in four feels that Big Tech knows what they are thinking, knows more about them than their best friend, and may even be secretly listening to their conversations. Additionally, one in four feels addicted to Big Tech products, have no choice but to use them, and wishes there were more companies to choose from. These findings highlight the adverse effect of the oligopolistic nature of Big Tech on consumer choice and help inform policy-makers aiming to curb their dominance.

Random Walks-based Anomaly Detection (RWAD) is commonly used to identify anomalous patterns in various applications. An intriguing characteristic of RWAD is that the input graph can either be pre-existing graphs or feature-derived graphs constructed from raw features. Consequently, there are two potential attack surfaces against RWAD: graph-space attacks and feature-space attacks. In this paper, we explore this vulnerability by designing practical coupled-space (interdependent feature-space and graph-space) attacks, investigating the interplay between graph-space and feature-space attacks. To this end, we conduct a thorough complexity analysis, proving that attacking RWAD is NP-hard. Then, we proceed to formulate the graph-space attack as a bi-level optimization problem and propose two strategies to solve it: alternative iteration (alterI-attack) or utilizing the closed-form solution of the random walk model (cf-attack). Finally, we utilize the results from the graph-space attacks as guidance to design more powerful feature-space attacks (i.e., graph-guided attacks). Comprehensive experiments demonstrate that our proposed attacks are effective in enabling the target nodes to evade the detection from RWAD with a limited attack budget. In addition, we conduct transfer attack experiments in a black-box setting, which show that our feature attack significantly decreases the anomaly scores of target nodes. Our study opens the door to studying the coupled-space attack against graph anomaly detection in which the graph space relies on the feature space.

Centrality measures can rank nodes in a social network according to their importance. However, in many cases, a node may want to avoid being highly ranked by such measures, e.g., as is the case with terrorist networks. In this work, we study a confrontation between the seeker—the party analyzing a social network using centrality measures—and the evader—a node attempting to decrease its ranking according to such measures. We analyze the possible outcomes of modifying, i.e., adding or removing, a single edge by the evader, showing that even without complete knowledge about the network, the effects of the modification on the evader's ranking can often be predicted. We study the computational complexity of finding a set of modifications that reduce the evader's centrality ranking in an optimal way, proving that these decision problems are NP-complete. Moreover, we provide a 2-approximation for the degree centrality, and logarithmic approximation boundaries for the closeness and betweenness centralities. Finally, we define and investigate a Stackelberg game between the seeker and the evader, providing a Mixed Integer Linear Programming formulation of finding an equilibrium. Altogether, we provide a thorough analysis of the strategic aspects of hiding from centrality measures in social networks.

Centrality measures are the most commonly advocated social network analysis tools for identifying leaders of covert organizations. While the literature has predominantly focused on studying the effectiveness of existing centrality measures or developing new ones, we study the problem from the opposite perspective, by focusing on how a group of leaders can avoid being identified by centrality measures as key members of a covert network. More specifically, we analyze the problem of choosing a set of edges to be added to a network to decrease the leaders’ ranking according to three fundamental centrality measures, namely, degree, closeness, and betweenness. We prove that this problem is NP-complete for each measure. Moreover, we study how the leaders can construct a network from scratch, designed specifically to keep them hidden from centrality measures. We identify a network structure that not only guarantees to hide the leaders to a certain extent but also allows them to spread their influence across the network.

The amount of JavaScript used in web pages has substantially grown in the past decade, leading to large and complex pages that are computationally intensive for handheld mobile devices. Due to the increasing usage of these devices to access today’s web, and to accommodate the needs of a large number of mobile web users who solely rely on low-end devices, we propose “JSAnalyzer,” an easy-to-use tool that enables web developers to quickly optimize JavaScript usage in their pages and to generate simpler versions of these pages for mobile web users. JSAnalyzer is motivated by the widespread use of non-critical JavaScript elements, i.e., those that have negligible (if any) impact on the page’s visual content and interactive functionality. JSAnalyzer allows the developer to selectively enable or disable JavaScript elements in any given page while visually observing their impact on the page to (1) accurately identify any non-critical JavaScript elements and (2) create a simplified page with these elements removed. Our quantitative evaluation shows that, given a low-end mobile phone, JSAnalyzer achieves an increase of nearly 90% in Google’s lighthouse performance score while reducing the page load time by 30%. A qualitative study of 22 users shows that the lighter pages produced by JSAnalyzer maintain more than 90% visual similarity compared to the original pages. Moreover, JSAnalyzer was evaluated by 69 developers, showing that it scores nearly 90% in terms of usefulness and usability while retaining the page’s content and functionality. Finally, we show that JSAnalyzer outperforms state-of-the-art solutions in terms of timing speedups and resource savings.

In this paper, we present a computational analysis of the problem of attacking sign prediction, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. The problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction. We propose a heuristic algorithm and test its effectiveness on several real-life and synthetic datasets.

Multilayer networks allow for modeling complex relationships, where individuals are embedded in multiple social networks at the same time. Given the ubiquity of such relationships, these networks have been increasingly gaining attention in the literature. This paper presents the first analysis of the robustness of centrality measures against strategic manipulation in multilayer networks. More specifically, we consider an “evader” who strategically chooses which connections to form in a multilayer network in order to obtain a low centrality-based ranking—thereby reducing the chance of being highlighted as a key figure in the network—while ensuring that she remains connected to a certain group of people. We prove that determining an optimal way to “hide” is NP-complete and hard to approximate for most centrality measures considered in our study. Moreover, we empirically evaluate a number of heuristics that the evader can use. Our results suggest that the centrality measures that are functions of the entire network topology are more robust to such a strategic evader than their counterparts which consider each layer separately.

We propose a new centrality measure, called the Random Walk Decay centrality. While most centralities in the literature are based on the notion of shortest paths, this new centrality measure stems from the random walk on the network. We provide an axiomatic characterization and show that the new centrality is closely related to PageRank. More in detail, we show that replacing only one axiom, called Lack of Self-Impact, with another one, called Edge Swap, results in the new axiomatization of PageRank. Finally, we argue that Lack of Self-Impact is desirable in various settings and explain why violating Edge Swap may be beneficial and may contribute to promoting diversity in the centrality measure.

The intuitive notion of added value in groups represents a fundamental property of biological, physical, and economic systems: how the interaction or cooperation of multiple entities, substances, or other agents can produce synergistic effects. However, despite the ubiquity of group formation, a well-founded measure of added value has remained elusive. Here, we propose such a measure inspired by the Shapley value —a fundamental solution concept from Cooperative Game Theory. To this end, we start by developing a solution concept that measures the average impact of each player in a coalitional game and show how this measure uniquely satisfies a set of intuitive properties. Then, building upon our solution concept, we propose a measure of added value that not only analyzes the interactions of players inside their group, but also outside it, thereby reflecting otherwise-hidden information about how these individuals typically perform in various groups of the population.

The reliable operation of the power distribution system is a matter of national security. Increasingly, urban distribution systems rely on communications between customers and the utility to implement consumer-centric programs such as demand response that enhance the grid resilience. This paper reports an unconventional and previously unexamined mode of malicious attack on the power distribution infrastructure of cities. It demonstrates that consumer behaviors in such a system could be manipulated by an attacker using false communications, which could significantly impact the system reliability. Using a novel decision-making model for consumer response, possible network impacts of such an attack are examined, which include reduction in system reserves, increase in peak demand, lower voltage profiles, and potential system blackouts. These detrimental effects are shown to worsen in the future as more consumers join such programs and adopt flexible high-power loads. Furthermore, though the system is resilient to random errors or failures, it remains highly vulnerable to strategic attacks such as those demonstrated here. These results recommend urgency in developing solutions to detect and tackle possible injection of fake information into such critical systems, which, as shown here, can have a very real impact on the energy infrastructure reliability.

At the heart of multi-agent systems is the ability to cooperate to improve the performance of individual agents and/or the system as a whole. While a widespread assumption in the literature is that such cooperation is essentially unrestricted, in many realistic settings this assumption does not hold. A highly influential approach for modelling such scenarios are graph-restricted games introduced by Myerson [36]. In this approach, agents are represented by nodes in a graph, edges represent communication channels, and a group can generate an arbitrary value only if there exists a direct or indirect communication channel between every pair of agents within the group. Two fundamental solution-concepts that were proposed for such games are the Myerson value and the Shapley value . While an algorithm has been developed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has been developed for the Myerson value to date. With this in mind, we set out to develop for such games a general-purpose algorithm to compute the Myerson value, and a more efficient algorithm to compute the Shapley value. Since the computation of either value involves enumerating all connected induced subgraphs of the game’s underlying graph, we start by developing an algorithm dedicated to this enumeration, and then we show empirically that it is faster than the state of the art in the literature. Finally, we present a sample application of both algorithms, in which we test the Myerson value and the Shapley value as advanced measures of node centrality in networks.

Research has shown that a person's financial success is more dependent on the ability to deal with people than on professional knowledge. Sage advice, such as "if you can't say something nice, don't say anything at all" and principles articulated in Carnegie's classic "How to Win Friends and Influence People," offer trusted rules-of-thumb for how people can successfully deal with each other. However, alternative philosophies for dealing with people have also emerged. The success of an AI system is likewise contingent on its ability to win friends and influence people. In this paper, we study how AI systems should be designed to win friends and influence people in repeated games with cheap talk (RGCTs). We create several algorithms for playing RGCTs by combining existing behavioral strategies (what the AI does) with signaling strategies (what the AI says) derived from several competing philosophies. Via user study, we evaluate these algorithms in four RGCTs. Our results suggest sufficient properties for AIs to win friends and influence people in RGCTs.

Assessing the progress made in AI and contributions to the state of the art is of major concern to the community. Recently, Frechette et al. [2016] advocated performing such analysis via the Shapley value, a concept from coalitional game theory. In this paper, we argue that while this general idea is sound, it unfairly penalizes older algorithms that advanced the state of the art when introduced, but were then outperformed by modern counterparts. Driven by this observation, we introduce the temporal Shapley value, a measure that addresses this problem while maintaining the desirable properties of the (classical) Shapley value. We use the tempo- ral Shapley value to analyze the progress made in (i) the different versions of the Quicksort algorithm; (ii) the annual SAT competitions 2007–2014; (iii) an annual competition of Constraint Programming, namely the MiniZinc challenge 2014–2016. Our analysis reveals novel insights into the development made in these important areas of research over time.

One of the fundamental research challenges in network science is centrality analysis, i.e., identifying the nodes that play the most important roles in the network. In this article, we focus on the game-theoretic approach to centrality analysis. While various centrality indices have been recently proposed based on this approach, it is still unknown how general is the game-theoretic approach to centrality and what distinguishes some game-theoretic centralities from others. In this article, we attempt to answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every possible centrality measure can be obtained following the game-theoretic approach. Furthermore, we study three natural classes of game-theoretic centrality, and prove that they can be characterized by certain intuitive properties pertaining to the well-known notion of Fairness due to Myerson.

How can individuals and communities protect their privacy against social network analysis tools? How do criminals or terrorists organizations evade detection by such tools? Under which conditions can these tools be made strategy proof? These fundamental questions have attracted little attention in the literature to date, as most social network analysis tools are built around the assumption that individuals or groups in a network do not act strategically to evade such tools. With this in mind, we outline in this paper a new paradigm for social network analysis, whereby the strategic behaviour of network actors is explicitly modeled. Addressing this research challenge has various implications. For instance, it may allow two individuals to keep their relationship secret or private. It may also allow members of an activist group to conceal their membership, or even conceal the existence of their group from authoritarian regimes. Furthermore, it may assist security agencies and counter terrorism units in understanding the strategies that covert organizations use to escape detection, and give rise to new strategy-proof countermeasures.

One of the fundamental research challenges in network science is the centrality analysis, i.e., identifying the nodes that play the most important roles in the network. In this paper, we focus on the game-theoretic approach to centrality analysis. While various centrality indices have been proposed based on this approach, it is still unknown what distinguishes this family of indices from the more classical ones. In this paper, we answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every centrality can be obtained following the game-theoretic approach, and show that two natural classes of game-theoretic centrality can be characterized by two intuitive properties pertaining to Myerson's notion of Fairness.

Algorithms for NP-complete problems often have different strengths andweaknesses, and thus algorithm portfolios often outperform individualalgorithms. It is surprisingly difficult to quantify a component algorithm's contributionto such a portfolio. Reporting a component's standalone performance wronglyrewards near-clones while penalizing algorithms that have small but distinctareas of strength. Measuring a component's marginal contribution to an existingportfolio is better, but penalizes sets of strongly correlated algorithms,thereby obscuring situations in which it is essential to have at least onealgorithm from such a set. This paper argues for analyzing component algorithmcontributions via a measure drawn from coalitional game theory---the Shapleyvalue---and yields insight into a research community's progress over time. Weconclude with an application of the analysis we advocate to SAT competitions,yielding novel insights into the behaviour of algorithm portfolios, theircomponents, and the state of SAT solving technology.

Certain real-life networks have a community structure in which communities overlap. For example, a typical bus network includes bus stops (nodes), which belong to one or more bus lines (communities) that often overlap. Clearly, it is important to take this information into account when measuring the centrality of a bus stop - how important it is to the functioning of the network. For example, if a certain stop becomes inaccessible, the impact will depend in part on the bus lines that visit it. However, existing centrality measures do not take such information into account. Our aim is to bridge this gap. We begin by developing a new game-theoretic solution concept, which we call the Configuration semivalue, in order to have greater flexibility in modelling the community structure compared to previous solution concepts from cooperative game theory. We then use the new concept as a building block to construct the first extension of Closeness centrality to networks with community structure (overlapping or otherwise). Despite the computational complexity inherited from the Configuration semivalue, we show that the corresponding extension of Closeness centrality can be computed in polynomial time. We empirically evaluate this measure and our algorithm that computes it by analysing the Warsaw public transportation network.

The coalition structure generation problem is one of the key challenges in multi-agent coalition formation. It involves partitioning a set of agents into coalitions so that system performance is optimized. To date, the multi-agent systems literature has focused exclusively on the utilitarian version of this problem which seeks to maximize the sum of the values of the coalitions involved. However, there are many examples of situations in which other performance metrics are of interest. In particular, in games with non-transferable utility, we may be more interested in an egalitarian optimal coalition structure, or in minimizing the difference between the utilities of the most affluent and poorest agents. In this paper, we present a number of exact algorithms to solve such non-utilitarian formulations of the coalition structure generation problem.

Link prediction is a key problem in social network analysis: it involves making suggestions about where to add new links in a network, based solely on the structure of the network. We address a special case of this problem, whereby the new links are supposed to connect different communities in the network; we call it the interlinks prediction problem. This is particularly challenging as there are typically very few links between different communities. To solve this problem, we propose a local node-similarity measure, inspired by the Owen-value interaction index—a concept developed in cooperative game theory and fuzzy systems. Although this index requires an exponential number of operations in the general case, we show that our local node-similarity measure is computable in polynomial time. We apply our measure to solve the inter-links prediction problem in a number of real-life networks, and show that it outperforms all other local similarity measures in the literature.

Betweenness centrality measures the ability of different nodes to control the flow of information in a network. In this article, we extend the standard definition of betweenness centrality using Semivalues—a family of solution concepts from cooperative game theory that includes, among others, the Shapley value and the Banzhaf power index. Any Semivalue-based betweenness centrality measure (such as, for example, the Shapley value-based betweenness centrality measure) has the advantage of evaluating the importance of individual nodes by considering the roles they each play in different groups of nodes. Our key result is the development of a general polynomial-time algorithm to compute the Semivalue-based betweenness centrality measure, and an even faster algorithm to compute the Shapley value-based betweenness centrality measure, both for weighted and unweighted networks. Interestingly, for the unweighted case, our algorithm for computing the Shapley value-based centrality has the same complexity as the best known algorithm for computing the standard betweenness centrality due to Brandes [15]. We empirically evaluate our measures in a simulated scenario where nodes fail simultaneously. We show that, compared to the standard measure, the ranking obtained by our measures reflects more accurately the influence that different nodes have on the functionality of the network.

The current state-of-the-art algorithm for optimal coalition structure generation is IDP-IP — an algorithm that combines IDP (a dynamic programming algorithm due to Rahwan and Jennings, AAAI'08) with IP (a tree-search algorithm due to Rahwan et al., JAIR'09). In this paper we analyse IDP-IP, highlight its limitations, and then develop a new approach for combining IDP with IP that overcomes these limitations.

The conventional model of coalition formation considers every possible subset of agents as a potential coalition. However, in many real-world applications, there are inherent constraints on feasible coalitions: for instance, certain agents may be prohibited from being in the same coalition, or the coalition structure may be required to consist of coalitions of the same size. In this paper, we present the first systematic study of constrained coalition formation (CCF). We propose a general framework for this problem, and identify an important class of CCF settings, where the constraints specify which groups of agents should/should not work together. We describe a procedure that transforms such constraints into a structured input that allows coalition formation algorithms to identify, without any redundant computations, all the feasible coalitions. We then use this procedure to develop an algorithm for generating an optimal (welfare-maximizing) constrained coalition structure, and show that it outperforms existing state-of-the-art approaches by several orders of magnitude.

Coalition formation is a fundamental research topic in multi-agent systems. In this context, while it is desirable to generate a coalition structure that maximizes the sum of the values of the coalitions, the space of possible solutions is often too large to allow exhaustive search. Thus, a fundamental open question in this area is the following: Can we search through only a subset of coalition structures, and be guaranteed to find a solution that is within a desirable bound (beta) from optimum? If so, what is the minimum such subset? To date, the above question has only been partially answered by Sandholm et al. in their seminal work on anytime coalition structure generation [Sandholm et al., 1999]. More specifically, they identified minimum subsets to be searched for two particular bounds: β = n and β = [n/2]. Nevertheless, the question remained open for other values of β. In this paper, we provide the complete answer to this question.

In this paper we propose a novel approach to represent coalitional games, called a Coalition-Flow Network (CF-NET), that builds upon a generalization of the network flow literature. Specifically, this representation is based on our observation that the coalition formation process can be viewed as the problem of directing the flow through a network where every edge has certain capacity constraints.

We consider the issue of representing coalitional games in multi-agent systems with externalities (i.e., in systems where the performance of one coalition may be affected by other co-existing coalitions). In addition to the conventional partition function game representation (PFG), we propose a number of new representations based on a new notion of externalities. In contrast to conventional game theory, our new concept is not related to the process by which the coalitions are formed, but rather to the effect that each coalition may have on the entire system and vice versa. We show that the new representations are fully expressive and, for many classes of games, more concise than the conventional PFG. Building upon these new representations, we propose a number of approaches to solve the coalition structure generation problem in systems with externalities. We show that, if externalities are characterised by various degrees of regularity, the new representations allow us to adapt coalition structure generation algorithms that were originally designed for domains with no externalities, so that they can be used when externalities are present. Finally, building upon Rahwan et al. [16] and Michalak et al. [9], we present a unified method to solve the coalition structure generation problem in any system, with or without externalities, provided sufficient information is available.

Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques ranging from dynamic programming, to integer programming, to stochastic search all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0.175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.