Many ethical issues in machine learning are connected to the training data. Online data markets are an important source of training data, facilitating both production and distribution. Recently, a trend has emerged of for-profit ''ethical'' participants in online data markets. This trend raises a fascinating question: Can online data markets sustainably and efficiently address ethical issues in the broader machine-learning economy? In this work, we study this question in a stylized model of an online data market. We investigate the effects of intervening in the data market to achieve balanced training-data production. The model reveals the crucial role of market conditions. In small and emerging markets, an intervention can drive the data producers out of the market, so that the cost of fairness is maximal. Yet, in large and established markets, the cost of fairness can vanish (as a fraction of overall welfare) as the market grows. Our results suggest that ''ethical'' online data markets can be economically feasible under favorable market conditions, and motivate more models to consider the role of data production and distribution in mediating the impacts of ethical interventions.

In this paper, we investigate the conditions under which link analysis algorithms prevent minority groups from reaching high ranking slots. We find that the most common link-based algorithms using centrality metrics, such as PageRank and HITS, can reproduce and even amplify bias against minority groups in networks. Yet, their behavior differs: one one hand, we empirically show that PageRank mirrors the degree distribution for most of the ranking positions and it can equalize representation of minorities among the top ranked nodes; on the other hand, we find that HITS amplifies pre-existing bias in homophilic networks through a novel theoretical analysis, supported by empirical results. We find the root cause of bias amplification in HITS to be the level of homophily present in the network, modeled through an evolving network model with two communities. We illustrate our theoretical analysis on both synthetic and real datasets and we present directions for future work.

Why do biased algorithmic predictions arise, and what interventions can prevent them? We examine this topic with a field experiment about using machine learning to predict human capital. We randomly assign approximately 400 AI engineers to develop software under different experimental conditions to predict standardized test scores of OECD residents. We then assess the resulting predictive algorithms using the realized test performances, and through randomized audit-like manipulations of algorithmic inputs. We also used the diversity of our subject population to measure whether demographically non-traditional engineers were more likely to notice and reduce algorithmic bias, and whether algorithmic prediction errors are correlated within programmer demographic groups. This document describes our experimental design and motivation; the full results of our experiment are available at https://ssrn.com/abstract=3615404.

The problem of social influence maximization is widely applicable in designing viral campaigns, news dissemination, or medical aid. State-of-the-art algorithms often select “early adopters” that are most central in a network unfortunately mirroring or exacerbating historical biases and leaving under-represented communities out of the loop. Through a theoretical model of biased networks, we characterize the intricate relationship between diversity and efficiency, which sometimes may be at odds but may also reinforce each other. Most importantly, we find a mathematically proven analytical condition under which more equitable choices of early adopters lead simultaneously to fairer outcomes and larger outreach. Analysis of data on the DBLP network confirms that our condition is often met in real networks. We design and test a set of algorithms leveraging the network structure to optimize the diffusion of a message while avoiding to create disparate impact among participants based on their demographics, such as gender or race.

We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e., independent sets in the conflict graph G^- =(V,E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously, in such a way that they all strictly increase their utilities (number of friends i.e., the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O(|V|alpha(G^-)) for k <= 2 and O(|V|^3) for k=3, with alpha(G^-) being the independence number of G^-. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k <= 2 the tight upper-bound O(|V| min {alpha(G^-), sqrt{|V|}}) and, when G^- is the empty graph, the exact value of order ((2|V|)^{3/2})/3. The time of convergence, for any fixed k >= 4, was conjectured to be polynomial [Escoffier et al., 2012][Kleinberg and Ligett, 2013]. In this paper we disprove this. Specifically, we prove that for any k >= 4, the maximum time of convergence is an Omega(|V|^{Theta(log{|V|})}).

As social recommendations such as friend suggestions and people to follow become increasingly popular and influential on the growth of social media, we find that prominent social recommendation algorithms can exacerbate the under-representation of certain demographic groups at the top of the social hierarchy. To study this imbalance in online equal opportunities, we leverage new Instagram data and offer for the first time an analysis that studies the effect of gender, homophily and growth dynamics under social recommendations. Our mathematical analysis demonstrates the existence of an algorithmic glass ceiling that exhibits all the properties of the metaphorical social barrier that hinders groups like women or people of color from attaining equal representation. What raises concern is that our proof shows that under fixed minority and homophily parameters the algorithmic effect is systematically larger than the glass ceiling generated by the spontaneous growth of social networks. We discuss ways to address this concern in future design.

Online news domains increasingly rely on social media to drive traffic to their websites. Yet we know surprisingly little about how a social media conversation mentioning an online article actually generates clicks. Sharing behaviors, in contrast, have been fully or partially available and scrutinized over the years. While this has led to multiple assumptions on the diffusion of information, each assumption was designed or validated while ignoring actual clicks. We present a large scale, unbiased study of social clicks---that is also the first data of its kind---gathering a month of web visits to online resources that are located in 5 leading news domains and that are mentioned in the third largest social media by web referral (Twitter). Our dataset amounts to 2.8 million shares, together responsible for 75 billion potential views on this social media, and 9.6 million actual clicks to 59,088 unique resources. We design a reproducible methodology and carefully correct its biases. As we prove, properties of clicks impact multiple aspects of information diffusion, all previously unknown:(i) Secondary resources, that are not promoted through headlines and are responsible for the long tail of content popularity, generate more clicks both in absolute and relative terms; (ii) Social media attention is actually long-lived, in contrast with temporal evolution estimated from shares or receptions; (iii) The actual influence of an intermediary or a resource is poorly predicted by their share count, but we show how that prediction can be made more precise.

Due to emerging applications such as cloud computing and big data analytics, modern information processing systems are growing increasingly large and complex. A critical issue concerns the throughput performance as the system grows in size. This paper models distributed information processing systems as fork and join queueing networks with blocking. We identify necessary and sufficient conditions for throughput scalability of such fork and join networks as they grow in size. Previous studies have either focused on special structured networks such as tandem or tree networks, or provided only necessary conditions for throughput scalability. In this paper, we show that such necessary conditions are not sufficient. We present a key topological concept called ``minimum level" of the underlying graph, and develop lower and upper bounds for the throughput of arbitrary FJQN/Bs. The bounds depend on network degree, minimum level, deterministic cycle time, buffer sizes, and service time distributions, but not on network size. We show that level-boundedness and degree-boundedness are necessary and sufficient conditions to guarantee that the throughput of an FJQN/B is bounded away from zero as network size goes to infinity.

Linking accounts of the same user across datasets -- even when personally identifying information is removed or unavailable -- is an important open problem studied in many contexts. Beyond many practical applications, (such as cross domain analysis, recommendation, and link prediction), understanding this problem more generally informs us on the privacy implications of data disclosure. Previous work has typically addressed this question using either different portions of the same dataset or observing the same behavior across thematically similar domains. In contrast, the general cross-domain case where users have different profiles independently generated from a common but unknown pattern raises new challenges, including difficulties in validation, and remains under-explored.

We present Sunlight, a system that detects the causes of targeting phenomena on the web -- such as personalized advertisements, recommendations, or content -- at large scale and with solid statistical confidence. Today's web is growing increasingly complex and impenetrable as myriad of services collect, analyze, use, and exchange users' personal information. No one can tell who has what data, for what purposes they are using it, and how those uses affect the users. The few studies that exist reveal problematic effects -- such as discriminatory pricing and advertising -- but they are either too small-scale to generalize or lack formal assessments of confidence in the results, making them difficult to trust or interpret. Sunlight brings a principled and scalable methodology to personal data measurements by adapting well-established methods from statistics for the specific problem of targeting detection. Our methodology formally separates different operations into four key phases: scalable hypothesis generation, interpretable hypothesis formation, statistical significance testing, and multiple testing correction. Each phase bears instantiations from multiple mechanisms from statistics, each making different assumptions and tradeoffs. Sunlight offers a modular design that allows exploration of this vast design space. We explore a portion of this space, thoroughly evaluating the tradeoffs both analytically and experimentally. Our exploration reveals subtle tensions between scalability and confidence. Sunlight's default functioning strikes a balance to provide the first system that can diagnose targeting at fine granularity, at scale, and with solid statistical justification of its results.

Big Data promises important societal progress but exacerbates the need for due process and accountability. Companies and institutions can now discriminate between users at an individual level using collected data or past behavior. Worse, today they can do so in near perfect opacity. The nascent field of web transparency aims to develop the tools and methods necessary to reveal how information is used, however today it lacks robust tools that let users and investigators identify targeting using multiple inputs.

The impact of blogs and microblogging on the consumption of news is dramatic, as every day users rely more on these sources to decide what content to pay attention to. In this work, we empirically and theoretically analyze the dynamics of bloggers serving as intermediaries between the mass media and the general public.

The large-scale collection and exploitation of personal information to drive targeted online advertisements has raised privacy concerns. As a step towards understanding these concerns, we study the relationship between how much information is collected and how valuable it is for advertising. We use HTTP traces consisting of millions of users to aid our study and also present the first comparative study between aggregators. We develop a simple model that captures the various parameters of today's advertising revenues, whose values are estimated via the traces. Our results show that per aggregator revenue is skewed (5% accounting for 90% of revenues), while the contribution of users to advertising revenue is much less skewed (20% accounting for 80% of revenue). Google is dominant in terms of revenue and reach (presence on 80% of publishers). We also show that if all 5% of the top users in terms of revenue were to install privacy protection, with no corresponding reaction from the publishers, then the revenue can drop by 30%.

No abstract available.

Monetizing personal information is a key economic driver of online industry. End-users are becoming more concerned about their privacy, as evidenced by increased media attention. This paper proposes a mechanism called 'transactional' privacy that can be applied to personal information of users. Users decide what personal information about themselves is released and put on sale while receiving compensation for it. Aggregators purchase access to exploit this information when serving ads to a user. Truthfulness and efficiency, attained through an unlimited supply auction, ensure that the interests of all parties in this transaction are aligned. We demonstrate the effectiveness of transactional privacy for web-browsing using a large mobile trace from a major European capital. We integrate transactional privacy in a privacy-preserving system that curbs leakage of information. These mechanisms combine to form a market of personal information that can be managed by a trusted third party.

The increase in data consumed by smartphones is becoming a huge problem for mobile operators. In three years, mobile data traffic in AT&T's network rose 5000%. The US operators invest $50 billion in the data networks every year and the technology upgrades and innovation still fail to keep up with the demand. In this paper we design two algorithms for delay-tolerant offloading of bulky, socially recommended content from 3G networks. The first one, called "MixZones", uses opportunistic, ad hoc transfers between users, and is assisted by predictions made by the network operator. The second one, called "HotZones", exploits delay tolerance and tries to download contents when users are close to Wi-Fi access points; it is also assisted by predictions made by the operator. We evaluate both algorithms using a large data set, obtained from a major mobile operator and a realistic application similar to Apple's Ping music social network. The metrics address the amount of offloading, delay and mobile energy efficiency. We find that both solutions succeed in offloading a significant amount of traffic, with a positive impact on user battery lifetime. Surprisingly, we also find that all the benefit obtained from the operator with the MixZones algorithm (i.e with ad hoc exchanges between users) can be achieved with the HotZones algorithm and a small investment in Wi-Fi access points. Note that the latter is considerably less complex to deploy than the former.

Recommender systems predict user preferences based on a range of available information. For systems in which users generate streams of content (e.g., blogs, periodically-updated newsfeeds), users may rate the produced content that they read, and be given accurate predictions about future content they are most likely to prefer. We design a distributed mechanism for predicting user ratings that avoids the disclosure of information to a centralized authority or an untrusted third party: users disclose the rating they give to certain content only to the user that produced this content.

Sharing content over a mobile network through opportunistic contacts has recently received considerable attention.

A new generation of content delivery networks for live streaming, video on demand, and software updates takes advantage of a peer-to-peer architecture to reduce their operating cost. In contrast with previous uncoordinated peer-to-peer schemes, users opt-in to dedicate part of the resources they own to help the content delivery, in exchange for receiving the same service at a reduced price. Such incentive mechanisms are appealing, as they simplify coordination and accounting. However, they also increase a user's expectation that she will receive a fair price for the resources she provides. Addressing this issue carefully is critical in ensuring that all interested parties--including the provider--are willing to participate in such a system, thereby guaranteeing its stability.

Multimedia content dissemination in mobile settings requires significant bandwidth. Centralized infrastructure is often either inadequate or overly expensive to fill the demand. Here, we study an alternative P2P content dissemination scheme for mobile devices (e.g., smart-phones), which leverages local dedicated caches on these devices to opportunistically fulfill user requests. In our model, the allocation of content in the global distributed cache comprising the union of all local caches, determines the pattern of demand fulfillment. By selectively replicating local content at node meetings, the global cache can be driven towards a more efficient allocation. However, the allocation's efficiency itself is determined by a previously overlooked factor - the impatience of content requesters. By describing user impatience in the form of any monotonically decreasing delay-utility functions, we show that an optimal allocation can be efficient computed or approximated. As users become increasingly impatient, the optimal allocation varies steadily between uniform and highly-skewed towards popular content.

We study the dissemination of dynamic content, such as news or traffic information, over a mobile social network. In this application, mobile users subscribe to a dynamic-content distribution service, offered by their service provider. To improve coverage and increase capacity, we assume that users share any content updates they receive with other users they meet. We make two contributions. First, we determine how the service provider can allocate its bandwidth optimally to make the content at users as "fresh" as possible. More precisely, we define a global fairness objective (namely, maximizing the aggregate utility over all users) and prove that the corresponding optimization problem can be solved by gradient descent. Second, we specify a condition under which the system is highly scalable: even if the total bandwidth dedicated by the service provider remains fixed, the expected content age at each user grows slowly (as log(n)) with the number of users n. To the best of our knowledge, our work is the first to address these two aspects (optimality and scalability) of the distribution of dynamic content over a mobile social network.

Mobile opportunistic networks are characterized by unpredictable mobility, heterogeneity of contact rates and lack of global information. Successful delivery of messages at low costs and delays in such networks is thus challenging. Most forwarding algorithms avoid the cost associated with flooding the network by forwarding only to nodes that are likely to be good relays, using a quality metric associated with nodes. However it is non-trivial to decide whether an encountered node is a good relay at the moment of encounter. Thus the problem is in part one of online inference of the quality distribution of nodes from sequential samples, and has connections to optimal stopping theory. Based on these observations we develop a new strategy for forwarding, which we refer to as delegation forwarding.

We present a dynamic process for network evolution, aiming at explaining the emergence of the small world phenomenon. We prove that a local forgetting process combined with mobility produces shortcuts allowing navigability.

Portable devices have more data storage and increasing communication capabilities everyday. In addition to classic infrastructure based communication, these devices can exploit human mobility and opportunistic contacts to communicate. We analyze the characteristics of such opportunistic forwarding paths. We establish that opportunistic mobile networks in general are characterized by a small diameter, a destination device is reachable using only a small number of relays under tight delay constraint. This property is first demonstrated analytically on a family of mobile networks which follow a random graph process. We then establish a similar result empirically with four data sets capturing human mobility, using a new methodology to efficiently compute all the paths that impact the diameter of an opportunistic mobile networks. We complete our analysis of network diameter by studying the impact of intensity of contact rate and contact duration. This work is, to our knowledge, the first validation that the so called “small world ” phenomenon applies very generally to opportunistic networking between mobile nodes. 1.

Forwarding in Delay Tolerant Networks (DTNs) is a challenging problem. We focus on the specific issue of forwarding in an environment where mobile devices are carried by people in a restricted physical space (a conference) and contact patterns are not predictable. We show for the first time a path explosion phenomenon between most pairs of nodes. This means that, once the first path reaches the destination, the number of subsequent paths grows rapidly with time, so there usually exist many near-optimal paths. We study the path explosion phenomenon both analytically and empirically. Our results highlight the importance of unequal contact rates across nodes for understanding the performance of forwarding algorithms. We also find that a variety of well-known forwarding algorithms show surprisingly similar performance in our setting and we interpret this fact in light of the path explosion phenomenon.

The popularity of IEEE 802.11 WLANs has led to dense deployments in urban areas. High density leads to sub-optimal performance unless the interfering networks learn how to optimally use and share the spectrum. This paper proposes two fully distributed algorithms that allow (i) multiple interfering 802.11 access points to select their operating frequency in order to minimize interference, and (ii) users to choose the access point they attach to, in order to get their fair share of the whole network bandwidth. The proposed algorithms rely on Gibbs sampler, and do not require explicit coordination among the wireless devices. They only require the participating wireless nodes to measure local quantities such as interference and transmission delay. The algorithms are shown to lead to optimal bandwidth sharing, where optimality is defined according to the minimal potential delay. We analytically prove the convergence of the proposed algorithms, and study their performance by simulation.

No abstract available.

No abstract available.

We study data transfer opportunities between wireless devices carried by humans. We observe that the distribution of the intercontact time (the time gap separating two contacts between the same pair of devices) may be well approximated by a power law over the range [10 minutes; 1 day]. This observation is confirmed using eight distinct experimental data sets. It is at odds with the exponential decay implied by the most commonly used mobility models. In this paper, we study how this newly uncovered characteristic of human mobility impacts one class of forwarding algorithms previously proposed. We use a simplified model based on the renewal theory to study how the parameters of the distribution impact the performance in terms of the delivery delay of these algorithms. We make recommendations for the design of well-founded opportunistic forwarding algorithms in the context of human-carried devices

Pocket Switched Networking (PSN) is a new communication paradigm between mobile devices. It takes advantage of every local communication opportunity, and the physical mobility of the devices, in order to transport data.

Abstract — Studying transfer opportunities between wireless devices carried by humans, we observe that the distribution of the inter-contact time, that is the time gap separating two contacts of the same pair of devices, exhibits a heavy tail such as one of a power law, over a large range of value. This observation is confirmed on six distinct experimental data sets. It is at odds with the exponential decay implied by most mobility models. In this paper, we study how this new characteristic of human mobility impacts a class of previously proposed forwarding algorithms. We use a simplified model based on the renewal theory to study how the parameters of the distribution impact the delay performance of these algorithms. We make recommendation for the design of well founded opportunistic forwarding algorithms, in the context of human carried devices. I.

We consider reliable multicast in overlay networks where nodes have finite-size buffers and are subject to failures. We address issues of end-to-end reliability and throughput scalability in this framework. We propose a simple architecture which consists of using distinct point-to-point TCP connections between adjacent pairs of end-systems, together with a back-pressure control mechanism regulating the transfers of adjacent TCP connections, as well as a back-up buffering system handling node failures. This architecture, that we call the one-to-many TCP overlay, is a natural extension of TCP to the one-to-many case, in that it adapts the rate of the group communication to local congestion in a decentralized way via the window back-pressure mechanism. Using theoretical investigations, experimentations in the Internet, and large network simulations, we show that this architecture provides end-to-end reliability and can tolerate multiple simultaneous node failures, provided the backup buffers are sized appropriately. We also show that under random perturbations caused by cross traffic described in the paper, the throughput of this reliable group communication is always larger than a positive constant, that does not depend on the group size. This scalability result contrasts with known results about the non-scalability of IP-supported multicast for reliable group communication.

This study provides some new insights into the scalability of reliable group communication mechanisms using overlays. These mechanisms use individual TCP connections for packet transfers between end-systems. End-systems store incoming packets and forward them to downstream nodes using different unicast TCP connections. In this paper we assume that buffers in end-systems are large enough for the transfers. It is shown that the throughput of the reliable overlay group communication scales in the sense that for all multicast tree sizes and topologies, the group throughput is strictly positive under natural conditions. This is in contrast with the IP supported multicast paradigm where reliable protocols have vanishing throughput when the group size tends to infinity. The scalability of packet delay and buffer occupancy is then investigated. In the absence of additional control, the occupancy of the buffer and the latency in the end-systems explodes with time. It is then shown that proactive rate throttle mechanism implemented at the source leads to finite packet latency and buffer occupancy in any end-system of the network provided certain moment conditions are satisfied by cross traffic in the routers.

In this paper, we consider a set of HTTP flows using TCP over a common drop-tail link to download files. After each download, a flow waits for a random think time before requesting the download of another file, whose size is also random. When a flow is active its throughput is increasing with time according to the additive increase rule, but if it suffers losses created when the total transmission rate of the flows exceeds the link rate, its transmission rate is decreased. The throughput obtained by a flow, and the consecutive time to download one file are then given as the consequence of the interaction of all the flows through their total transmission rate and the link's behavior.We study the mean-field model obtained by letting the number of flows go to infinity. This mean-field limit may have two stable regimes : one without congestion in the link, in which the density of transmission rate can be explicitly described, the other one with periodic congestion epochs, where the inter-congestion time can be characterized as the solution of a fixed point equation, that we compute numerically, leading to a density of transmission rate given by as the solution of a Fredholm equation. It is shown that for certain values of the parameters (more precisely when the link capacity per user is not significantly larger than the load per user), each of these two stable regimes can be reached depending on the initial condition. This phenomenon can be seen as an analogue of turbulence in fluid dynamics: for some initial conditions, the transfers progress in a fluid and interaction-less way; for others, the connections interact and slow down because of the resulting fluctuations, which in turn perpetuates interaction forever, in spite of the fact that the load per user is less than the capacity per user. We prove that this phenomenon is present in the Tahoe case and both the numerical method that we develop and simulations suggest that it is present in the Reno case too. It translates into a bi-stability phenomenon for the finite population model within this range of parameters.

We study the impact of random queueing delays stemming from traffic variability on the performance of a multicast session. With a simple analytical model, we analyze the throughput degradation within a multicast (one-to-many) tree under TCP-like congestion and flow control. We use the (max,plus) formalism together with methods based on stochastic comparison (association and convex ordering) and on the theory of extremes to prove various properties of the throughput. We first prove that the throughput predicted by a deterministic model is systematically optimistic. In the presence of light-tailed random delays, we show that the throughput decreases according to the inverse of the logarithm of the number of receivers. We find analytically an upper and a lower bound for the throughput degradation. Within these bounds, we characterize the degradation which is obtained for various tree topologies. In particular, we observe that a class of trees commonly found in IP multicast sessions is significantly more sensitive to traffic variability than other topologies.

We study the impact of random noise (queueing delay) on the performance of a multicast session. With a simple analytical model, we analyze the throughput degradation within a multicast (one-to-many) tree under TCP-like congestion and flow control. We use the (max, plus) formalism together with methods based on stochastic comparison (association and convex ordering) and on the theory of extremes (Lai and Robbins' (1978) notion of maximal characteristics) to prove various properties of the throughput. We first prove that the throughput obtained from Golestani and Sabnani's (1999) deterministic model is systematically optimistic. In presence of light tailed random noise, we show that the throughput decreases like the inverse of the logarithm of the number of receivers. We find analytically an upper and a lower bound for the throughput degradation. Within these bounds, we characterize the degradation which is obtained for various tree topologies. In particular, we observe that a class of trees commonly found in IP multicast sessions (which we call umbrella trees) is significantly more sensitive to network noise than other topologies.