est destinée au dépôt


Nicolas Verrier

Dario Donnarumma

Daniel Alexandre

Gilles Tessier

Michel Gross
email: michel.gross@univ-montp2.fr

Digital holographic microscopy with high numerical aperture: wide z range reconstruction

A holographic microscopy algorithm is proposed enabling to deal with high numerical aperture holograms. Hologram reconstruction kernel performs under afocal conditions, which allows keeping the full NA over wide defocus range.

Introduction

Digital holography aims at recording, on a CCD or CMOS sensor, the interference pattern between an object field wavefront (amplitude and phase of the wave scattered by the investigated object) and a reference wavefront. Three dimensional information about the investigated scene is further retrieved considering light back-propagation techniques [START_REF] Schnars | Direct recording of holograms by a CCD target and numerical reconstruction[END_REF]. Methods have been proposed for the specific case of digital holographic microscopy [START_REF] Ferraro | Compensation of the inherent wave front curvature in digital holographic coherent microscopy for quantitative phase-contrast imaging[END_REF][START_REF] Colomb | Automatic procedure for aberration compensation in digital holographic microscopy and applications to specimen shape compensation[END_REF], but these allow optimal amplitude and phase reconstruction only in the plane where the correction is calculated. These are therefore limited to 2D samples. Recently, we proposed a reconstruction method allowing a distortion-less reconstruction in both object and image half spaces [START_REF] Verrier | Holographic microscopy reconstruction in both object and image half-spaces with an undistorted three-dimensional grid[END_REF]. In the following, we discuss of its extension to high numerical aperture (NA up to 1.4) [START_REF] Verrier | High numerical aperture holographic microscopy reconstruction with extended z range[END_REF]. BS1 and BS2, beam splitters. C, P, and U respectively denote the camera, the pupil (optimal plane of the MO), and the USAF image planes. The "X ′ " planes are the images of the aforemensioned planes through the MO.

Principles of the holographic reconstruction with high numerical aperture objectives

The arrangement for high NA holographic reconstruction is proposed Fig. 1. It consists of a classical off-axis holography arrangement with an immersion Microscope Objective (MO). In classical microscopic imaging, both the object and the sensor have to be positioned in the optimal planes of the objective, i.e. planes P and P ′ (see Fig. 1 for details). As a matter of fact, these planes are, by design, the ones for which the optical aberrations are minimal. Thus, optimal imaging is achieved when camera planes (C and C ′ ), object planes (U and U ′ ), and optimal planes (P and P ′ ) coincides (U = P = C and U ′ = P ′ = C ′ ). Holographic imaging is less restrictive and only needs the object to be in the optimal plane to optimally operate (U = P and U ′ = P ′ ). Indeed, the field in the camera plane (C ̸ = U) can be digitally propagated from camera C to optimal plane U = P by using standard reconstruction method with quadratic kernel. We propose here to go further and to conserve optimal resolution for an object not located in the optimal plane i.e. U ′ ̸ = P ′ [START_REF] Verrier | High numerical aperture holographic microscopy reconstruction with extended z range[END_REF].

The proposed method, which apply for high NA hologram reconstruction, is composed of two main steps:

1. Field reconstruction (with a quadratic kernel) in the optimal plane P ′ that allows retrieving the corrected amplitude and phase in plane.

2. Field propagation from P ′ to U ′ . The complete propagation kernel has to be used to account for the immersion medium and the large illumination angles.

We also need to have a precise knowledge of the location of the optimal plane P ′ , the phase correction to be applied in plane P ′ , and the imaging magnification G of the optical system, which can be obtained by imaging a calibrated object such as an USAF target, to operate under optimal conditions. The hologram recorded in the camera plane C is given by

Optimal holographic reconstruction

H C = |E + E R | 2 = |E| 2 + |E R | 2 + EE * R + E * E R , (1)
where E and E R are both the signal and reference field in the camera plane C. Here, two cases have to be distinguished: the object is in optimal plane P ′ or the object is outside P ′ . The hologram H P ′ in plane P ′ can be calculated considering the method proposed in [START_REF] Verrier | Holographic microscopy reconstruction in both object and image half-spaces with an undistorted three-dimensional grid[END_REF]. We here recall the main aspects of this procedure, which are illustrated by Fig. 2.

Reconstruction for U ′ = P ′

The first step of the reconstruction consists in multiplying the hologram H C (see Fig. 2(a)) by a complex matrix C RM which compensate for wave front curvature and off-axis tilt of the reference. The curvature and tilt compensated hologram H 1 can therefore be calculated considering

H 1 (x, y) = H C (x, y)C RM = H C (x,
y)e jk(x 2 +y 2 )/2r ′ e j(dk x x+dk y y) .

(2)

The MO-induced wave front curvature is considered as a second step. This is done by multiplying hologram H 1 by a numerical lens (NL) C NL located in the camera plane C. The hologram H 2 is such that

H 2 (x, y) = H 1 (x, y)C NL (x, y) = H 1 (x, y) e -jk(x 2 +y 2 )/2r , ( 3
)
where r is the focal of the NL that is adjusted such as the MO+NL optical system is afocal. FFT of H 2 , denoted H2 is proposed Fig. 2(b) for dk x = dk y = 0. From H2 the selection of the +1 grating order is performed by applying a circle crop of radius k max and adjusting dk x,y to bring the +1 order in the center of the k space. This consists of the hologram H3 illustrated Fig. 2(c) and obtained with dk x = 255, dk y = -244.52, and k max = 162 pixels. Finally, as shown in Ref. [START_REF] Verrier | High numerical aperture holographic microscopy reconstruction with extended z range[END_REF], knowing the optical magnification G makes it possible to reconstruct the hologram H P ′ from H3 by

H P ′ ( x/G, y/G, z ′ P ′ ) = FFT -1 [ e j(G 2 k 2 x +G 2 k 2 y )z ′ P ′ /2k m H3 (Gk x , Gk y ) ] , (4)
where k m = n m k is the wave vector in oil. This result is proposed Fig. 2(d).

Reconstruction for U ′ ̸ = P ′

The hologram H ′ U in the plane U ′ can be obtained from hologram H ′ P (see the derivations in the previous section and in Refs. [START_REF] Verrier | Holographic microscopy reconstruction in both object and image half-spaces with an undistorted three-dimensional grid[END_REF][START_REF] Verrier | High numerical aperture holographic microscopy reconstruction with extended z range[END_REF]). However, the propagation between U ′ and P ′ occurs in the oil, and numerical apertures can be large. It is therefore mandatory to deal with this propagation using the exact propagation kernel e -jk ′ z z ′ . Here k ′ z is defined as

k ′ z = √ k 2 m -k ′2 x -k ′2 y ,
where k m = n m 2π/λ , and k ′ x,y = Gk x,y . The hologram in the plane is is finally given by

H U ′ ( x ′ , y ′ , z ′ ) = FFT -1 [ e jk ′ z (z ′ -z ′ p ) FFT [ H P ′ ( x ′ , y ′ , z ′ P ′ )] ] . ( 5
)
Illustration of the method benefits is provided by Fig. 3. Here from the optimal hologram Fig. that our method allow to keep a good resolution with defocus up to -50µm. The same result is obtained for positive defocus but is not represented here. Therefore we are possible to keep an high resolution reconstruction over a large defocus range.

Conclusion

We proposed a two step reconstruction method operating with high numerical aperture holograms (up to NA = 1.4). The benefits of the methods have been demonstrated through the reconstruction of holograms recorded with a ×60 NA = 1.4 oil immersion MO, proving the ability to keep almost full resolution in a [-50 µm; 50 µm] defocus range. This work has benefited from a French State grant managed by the French National Research Agency under an Investments for the Future program (reference n.ANR-10-LABX-20).

Fig. 1 .

 1 Fig. 1. (Color online) Typical holographic microscopy set-up for (a) recording, (b) reconstructing.BS1 and BS2, beam splitters. C, P, and U respectively denote the camera, the pupil (optimal plane of the MO), and the USAF image planes. The "X ′ " planes are the images of the aforemensioned planes through the MO.

Fig. 2 .

 2 Fig. 2. (Color online) Principles of reconstruction. (a) Hologram H C (carrier fringes shown in inset). (b) Hologram H2 for dk x = dk y = 0(in arbitrary log scale). (c) Hologram H3 (details about the filtering are in the main text. (d) Hologram H 3 reconstructed phase is associated with the RGB LUT.

Fig. 3 .

 3 Fig. 3. Reconstruction of high NA holograms for various defocus. (a) z ′z ′ p = -47.69 µm. (b) z ′z ′ p = -23.39 µm. (c) z ′z ′ p = 0.8 µm. (d) z ′z ′ p = 12.84 µm. Scale bar is 3 µm.


Eduardo Hargreaves
email: eduardo@hargreaves.tech

Claudio Agosti
email: claudio.agosti@tracking.exposed

Daniel Menasché

Giovanni Neglia
email: giovanni.neglia@inria.fr

Alexandre Reiffers-Masson
email: reiffers.alexandre@gmail.com

Eitan Altman
email: eitan.altman@inria.fr

Fairness in Online Social Network Timelines: Measurements, Models and Mechanism Design

Keywords: Facebook, measurements, social networks, timelines, bias, fairness

Facebook News Feed personalization algorithm has a significant impact, on a daily basis, on the lifestyle, mood and opinion of millions of Internet users. Nonetheless, the behavior of such algorithm lacks transparency, motivating measurements, modeling and analysis in order to understand and improve its properties. In this paper, we propose a reproducible methodology encompassing measurements, an analytical model and a fairness-based News Feed design. The model leverages the versatility and analytical tractability of time-to-live (TTL) counters to capture the visibility and occupancy of publishers over a News Feed. Measurements are used to parameterize and to validate the expressive power of the proposed model. Then, we conduct a what-if analysis to assess the visibility and occupancy bias incurred by users against a baseline derived from the model. Our results indicate that a significant bias exists and it is more prominent at the top position of the News Feed. In addition, we find that the bias is non-negligible even for users that are deliberately set as neutral with respect to their political views, motivating the proposal of a novel and more transparent fairness-based News Feed design.

Introduction

Background. Online social networks (OSNs) have an increasingly important influence in the life of millions of Internet users, shaping their mood, tastes and political views [START_REF] Robert | A 61-millionperson experiment in social influence and political mobilization[END_REF][START_REF] Jones | Social influence and political mobilization: Further evidence from a randomized experiment in the 2012 US presidential election[END_REF]. In essence, the goal of OSNs is to allow users to connect and to efficiently share meaningful information. To this aim, one of the key building blocks of OSNs is their filtering algorithm, which personalizes content made available to each user of the system. Facebook, for instance, developed the News Feed algorithm for that purpose [START_REF]Facebook now has 2 billion monthly users[END_REF][START_REF] Facebook | Controlling What You See in News Feed[END_REF].

Challenges. The News Feed algorithm is a recommendation system that shows posts to users based on inferred users' preferences, trading among possibly conflicting factors while prioritizing posts [START_REF] Lua | Decoding the Facebook Algorithm: A Fully Up-to-Date List of the Algorithm Factors and Changes[END_REF][START_REF] Mosseri | News Feed Ranking in Three Minutes Flat[END_REF][START_REF] Krishnasamy | Detecting Sponsored Recommendations[END_REF]. Hence, the News Feed algorithm shares common features with traditional recommender systems, such as those used by Netflix and Spotify, to recommend movies and music. For instance, in all such systems users typically do not provide explicit feedback about recommendations. Nonetheless, due to the nature of OSNs, the News Feed algorithm also poses its own set of challenges, related to the measurement, modeling and control of publishers' visibilities.

Facebook users may be unaware of the influence of the filtering they are subject to [START_REF] Eslami | I always assumed that I wasn't really that close to [her[END_REF]. Such lack of awareness favors the creation of a filter bubble that reinforces users' opinions by selecting the users information diets [START_REF] Pariser | The Filter Bubble: What the Internet Is Hiding from You[END_REF][START_REF] Kulshrestha | Characterizing Information Diets of Social Media Users[END_REF]. While researchers are willing to understand the influence of Facebook through users' News Feed [START_REF] Eslami | First I like it, then I hide it: Folk theories of social feeds[END_REF], the News Feed algorithm uses sensitive data about preferences, which precludes the sharing of datasets. Public datasets, in turn, are needed in order to parameterize models to reason about how the News Feed is populated.

Models are instrumental to perform what-if analysis, e.g., to understand how the News Feed would behave in the presence of different filtering algorithms. In addition, analytical models can also serve as building blocks towards novel mechanisms to design News Feed algorithms. Such foundational development of principled mechanisms to populate the News Feed is key to build transparency into the system.

Prior art. The literature on the News Feed algorithm includes measurements [START_REF] Cheng | Do Diffusion Protocols Govern Cascade Growth? Icwsm[END_REF][START_REF] Bessi | Personality traits and echo chambers on Facebook[END_REF][START_REF] Bessi | Users polarization on Facebook and Youtube[END_REF][START_REF] Bucher | Want to be on the top? Algorithmic power and the threat of invisibility on Facebook[END_REF], models [START_REF] Altman | Competition over timeline in social networks[END_REF][START_REF] Dhounchak | A Viral Timeline Branching Process to study a Social Network[END_REF] and user awareness surveys [START_REF] Eslami | Feedvis: A path for exploring news feed curation algorithms[END_REF]. Nonetheless, most of the prior work that quantifies the effect of OSNs on information diffusion with large datasets [START_REF] Bakshy | The role of social networks in information diffusion[END_REF][START_REF] Bakshy | Exposure to ideologically diverse news and opinion on Facebook[END_REF][START_REF] Guillory Adam | Experimental evidence of massive-scale emotional contagion through social networks[END_REF][START_REF] Sun | Gesundheit ! Modeling Contagion through Facebook News Feed Mechanics of Facebook Page Diffusion[END_REF] relies on measurements obtained through restrictive non-disclosure agreements that are not made publicly available to other researchers and practitioners. As the data analyzed in such studies is very sensitive, and their sources are not audited, there are multiple potential factors and confounding variables that are unreachable to the general public.

Goals. Our goal is to provide insights on the filtering that occurs in OSNs through a reproducible methodology and a dataset made publicly available. 1Given such measurements, we pose the following questions:

1. what would be the occupancies of the various sources under alternative scenarios wherein different filtering algorithms are in place? 2. how to design mechanisms to populate timelines in a principled fashion, accounting for users preferences and providing content diversity, e.g., under a fairness-based framework?

To address the first question above, we propose an analytical model for the News Feed. The model allows us to derive the occupancy and visibility of each publisher at users' timelines, as a function of the considered filtering process. Using the model, we conduct what-if analysis, e.g., to assess publishers' visibilities in a scenario without filters.

Then, we use the proposed model to build fairness-driven mechanisms to populate timelines. Utilities are used to capture the preferences of users with respect to the exposure to posts from different publishers. The mechanism leverages results on utility-based cache design [START_REF] Dehghan | A utility optimization approach to network cache design[END_REF], and accounts for fairness among publishers through utility functions.

Contributions. In this paper we take important steps towards measuring, modeling, auditing and designing timelines. Our key contributions are summarized as follows.

A measurement methodology is introduced to publicly and transparently audit the OSN ecosystem, focusing on the Facebook News Feed algorithm. The methodology encompasses an Internet browser extension to autonomously and independently collect information on the posts presented to users by the News Feed algorithm (Section 2). Such information is not available through the Facebook API.

Empirical findings are reported using data collected from a measurement campaign conducted during the 2018 Italian elections. We observed that a) the filtering algorithm is impacted by the profile of pages that a user "likes", b) this effect is more prominent at the topmost News Feed position and c) neutral users are also exposed to non-uniform filtering (Section 3).

An analytical model is proposed to quantify the visibility and occupancy of publishers in the users' News Feeds. The model allows us to conduct a what-if analysis, to assess the metrics of interest under different filtering mechanisms and is validated using data from the Italian election experiment (Sections 4 and 5).

A fairness-driven mechanism design is proposed, leveraging the proposed model and measurements (Section 6). Given a user profile, that "likes" a certain subset of publishers, the measurements are used to parameterize a simple instance of the model. Then, a family of α-fair utility functions are used to allocate resources to publishers subject to users preferences under a utility maximization framework.

A model-based bias assessment is conducted where the News Feed occupancies are contrasted against an unfiltered resource allocation baseline to quantify the bias, i.e., how publishers' occupancies are affected by the News Feed algorithm (Section 6.5).

Measurement methodology

The goal of our experiments is to assess the bias experienced by OSN users through a reproducible method. To this aim, we created controlled virtual users that have no social ties and that follow the same set of publishers. By considering minimalistic user profiles, we can assess how preferences towards publishers affect posts presented to users removing, for instance, the effect of social connections.

Terminology

Next, we introduce some basic terminology. Publishers produce posts that are fed into users' News Feeds. Each user consumes posts from his/her News Feed. A News Feed is an ordered list of posts, also referred to as a timeline, presented to a given user. News Feed may refer to the algorithm used by Facebook to fill the timeline, or to the timeline itself.

Users follow publishers that they are interested in. The News Feed of a user is filled up with posts from publishers that they follow. A user may follow a publisher to have posts from that publisher in the user's News Feed. A user who likes a publisher automatically follows that publisher. A user likes a publisher to show general support for its posts. In our work, users orientations are established by letting them like a subset of the preselected publishers.

Data collection methodology

Next, we present our measurement methodology. Although this methodology is general, for concreteness our description is based on the 2018 Italian Parliament election, which constitutes the key case study considered in this paper. The Italian election was held on March 4, 2018, and our experiment was conducted between January 10, 2018 and March 6, 2018, encompassing the preparation for the election campaign and the reactions to its outcome.

We asked some Italian voters to select a set of thirty representative public Facebook pages, six for each of the following five political orientations: centerleft, far-right, left, five-star movement (M5S) and right. Appendix Appendix A contains the selection of representative pages and their respective political orientations mapping. The classification of publishers into political categories is debatable, but our focus in this paper is on the methodology rather than on specific political conclusions. Moreover, most of our results are detailed on a per-publisher basis, as a measurement-based political orientation classification is out of scope of this paper(see, e.g [START_REF] Ribeiro | Media Bias Monitor: Quantifying Biases of Social Media News Outlets at Large-Scale[END_REF]). Then, we created six virtual Facebook users, henceforth also referred to as bots. Each bot followed all the thirty selected pages. We gave to five bots a specific political orientation, by making each of them "like" pages from the corresponding publishers. The sixth bot does not "like" any page, i.e., it has no political orientation. We call it undecided.

Each bot kept open an Internet browser window (Firefox or Chrome) accessing the Facebook page. The bots were instrumented to collect data on the posts to which they were exposed. To that aim, a browser extension named Facebook Tracking Exposed [START_REF] Agosti | Facebook tracking exposed[END_REF] was developed. The extension auto-scrolls the Facebook window at pre-established instants of the day. Every auto-scroll produces a set of posts which are stored at a local database. Each set of posts is referred to as a snapshot. Each bot was scheduled to collect thirteen snapshots per day. Snapshots were collected once every hour, from 7 am to 7 pm (Italian local time). Each post appearing in a snapshot counts as a post impression. At each bot, the developed browser extension collects all impressions and records their corresponding publisher, publication time, impression time, content, number of "likes" and number of shares. We also have a second dataset which contains the set of all posts published by the thirty pages during the interval of interest, as provided by the Facebook API. This dataset is used to study what users would experience in the absence of filters, or in the presence of alternative filters.

Information about impressions used to be available in 2015, in a deprecated version of the Facebook API. In any case, that information was not necessarily reliable as recognized by Facebook itself [START_REF] Facebook | Graph API Reference[END_REF]. For such reasons, we believe that the developed browser extension and the methodology described in this section constitute important building blocks to promote transparency in the Facebook ecosystem.

Measurement challenges

Gaps in measurements: During our measurement campaign, we experienced measurement gaps due to two reasons: 1) the computer running a bot went down, due to unforeseen glitches such as lack of power and 2) at random points in time, either Facebook or related applications, such as the browser itself, solicit human interaction (e.g., by showing a pop-up requiring users to answer simple questions before proceeding). We denote by S i the number of snapshots collected by the i-th bot. In our experiments, the bots are indexed from 1 to 6, denoting center-left, far-right, left, M5S, right and undecided orientations. The values of S i equal 577, 504, 623, 674, 655, 576, for i = 1, . . . , 6. To account for the different number of snapshots, all the reported results rely on values averaged across snapshots rather than quantities that depend on the absolute number of snapshots.

Small number of bots: we use six bots to capture different perspectives on the Facebook dynamics. Each bot provides a personal perspective on the system, which is well aligned with our goals. Although we considered a small population size, we believe that the limited points of view provided by the six bots already shed important insights on the biases introduced by Facebook. In particular, the consistent biases observed in our dataset, reported in the sections that follow, indicates that the collected sample is representative.

Metrics of interest

We define our key metrics of interest that will be obtained from the dataset generated by the experiment. We consider the top K positions of the News Feed of each user. Definition 1 (visibility). Let π ij be the fraction of snapshots from user i that contain at least one post from publisher j. Definition 2 (occupancy). Let N ij be the average number of posts of publisher j in the News Feed of user i.

We refer to π ij and N ij as the visibility and the occupancy of publisher j at News Feed i, respectively. The normalized occupancy is given by N ij /K. The visibility and the (normalized) occupancy are two metrics of exposure of publishers to users [START_REF] Bakshy | Exposure to ideologically diverse news and opinion on Facebook[END_REF].

Definition 3 (hit probability). Let h ij be the probability that user i sees (or clicks) on a post of publisher j.

We refer to h ij as the hit probability of publisher j at user i. Then, h ij = N ij /K if user i goes through all the top posts in the News Feed, and h ij = π ij if he/she picks uniformly at random a single post in the News Feed.

Empirical findings

In the following two sections, we report our empirical findings from the perspective of publishers and users.

The effects of filtering on publishers

Next, we report findings on the behavior of the publishers and their general effect on users' News Feeds. Figure 1(a) shows the number of unique posts per publisher. We denote by C j the number of posts of publisher j. This information was collected directly from the Facebook API. A few publishers generated thousands of posts during the considered time frame, whereas the majority generated tens of posts.

Figure 1(b) shows the number of impressions per publisher. This information was collected from our Facebook extension. Publishers are ordered based on the number of posts generated and seen in Figures 1(a) and 1(b), respectively. It is worth noting that the distinct order at which publishers appear in those figures is fruit of the filtering experienced by the users. In what follows, such filtering is further analyzed through measurements (Section 3.2), models (Section 4) and a combination of the two (Sections 5 and 6).

The effects of filtering on users

The effect of filtering is stronger at the topmost News Feed position. Figures 2(a) and 2(b) show the normalized publisher occupancy, as a function of the News Feed size (the corresponding visibilities are reported in Appendix Appendix B). The publishers are colored according to their political orientation (Fig. 2(a)) and user preferences (Fig. 2(b)). Figure 2(a) shows that the occupancy distribution over the five orientations changes with the considered News Feed size.

In Figure 2(b), a publisher is colored in blue (resp., red) at a given bot if the bot "likes" (resp., does not "like") the corresponding publisher. Note that, except for the right and far-right bots, the normalized occupancy of publishers that users "like" is maximum at the topmost position, achieving more than 70% at the center-left oriented bot. The right-oriented bot achieved a similar normalized occupancy when K = 10. The noteworthy bias on the topmost position must be placed under scrutiny, as there is a strong correlation between post positions and click rates [START_REF] Bakshy | Exposure to ideologically diverse news and opinion on Facebook[END_REF][START_REF] Tufekci | How Facebook's Algorithm Suppresses Content Diversity (Modestly) and How the Newsfeed Rules Your Clicks[END_REF]. These figures also reveal that the amount of exposure to cross-cutting contents depends on the size of the News Feed.

Occupancy is impacted by orientation. cupancies are impacted by the orientation of the bots. For instance, the News Feed of the bot with a center-left orientation was occupied mostly by center-left (red) publishers. As a notable exception, center-left posts were prevalent in the News Feed of the bot with a far-right orientation, where far-right posts are responsible for roughly 25% of the normalized occupancy. Nonetheless, the occupancy of far-right posts in that bot was still the highest among all bots. Noticeable publishers selection. The bars in Figure 3 show the total number of impressions per publisher in the topmost position of the News Feed of each bot (the color of the bars indicates orientation). For the sake of readability, only publishers that achieved a normalized occupancy larger than 5% are represented in this figure. The black dots correspond to the number of posts created by each publisher (the publishers are ordered by the number of posts generated). Figure 3 shows that only a small subset of publishers are represented in topmost positions. For example, the center-left bot sees primarily posts from two of the publishers that it "likes". Moreover, the number of impressions per publisher is not proportional to the number of posts the publisher generated, a further indication of a filtering effect from News Feed algorithm.

Neutral users are also exposed to non-uniform filtering. It is worth noting that filtering affects also the "undecided" bot, with some publishers overrepresented in the News feed.

News Feed model

Next, we present the proposed News Feed model to derive occupancy and visibility metrics. We start by presenting the basic rationale behind the model in Section 4.1. Then, the model is introduced in Section 4.2.

Insights on News Feed modeling

Next, we introduce some of the key ideas that inspire the analytical model introduced in the following section.

Queues, caches and the News Feed

In the simplest setting, posts are organized at each News Feed in a first in, first out (FIFO) fashion. Then, the personalization algorithm at the News Feed of user i filters posts from each of the publishers. Given the rate Λ j at which publisher j creates posts, we denote by λ ij the corresponding effective arrival rate at which posts from publisher j are published at the News Feed of user i.

We assume that a News Feed has K slots. Under the FIFO approximation described above, new posts are inserted at the top of the News Feed and each new arrival shifts older posts one position lower. A post is evicted from the News Feed when it is shifted from position K. Although this is a preliminary step to capture the real News Feed operation, it cannot capture the stronger filtering at the topmost News Feed positions that we observed in Section 3.

In the remainder of this paper, we consider a generalization of the FIFO model, which accommodates different residence times for different posts using time-to-live (TTL) counters [START_REF] Dehghan | A utility optimization approach to network cache design[END_REF][START_REF] Kelly | Charging and rate control for elastic traffic[END_REF][START_REF] Reiffers-Masson | Timelines Are Publisher-Driven Caches: Analyzing and Shaping Timeline Networks[END_REF]. Under the TTL model, every time a post is inserted into a News Feed, it is associated to a timer (TTL), and the content remains in the News Feed until its timer expires. In what follows, we further detail the similarities and differences between TTL caches and the News Feed.

The News Feed is a publisher-driven cache

Next, we leverage a recently established connection between timelines in OSNs and caches [START_REF] Reiffers-Masson | Timelines Are Publisher-Driven Caches: Analyzing and Shaping Timeline Networks[END_REF], as summarized in Table 1.

Triggering events In the News Feed, the insertion of new posts is triggered by their creation. In caches, in contrast, user requests typically lead to content insertion and eviction. When proactive caching and prefetching of content is considered, the proactive caching is still usually fruit of content requests [START_REF] Tadrous | On optimal proactive caching for mobile networks with demand uncertainties[END_REF][START_REF] Bastug | Living on the edge: The role of proactive caching in 5G wireless networks[END_REF][START_REF] Golrezaei | Femtocaching and device-to-device collaboration: A new architecture for wireless video distribution[END_REF].

Nature of contents and requests When News Feed users search for usergenerated content, they are typically interested in a class of items related to a given category. The demand for News Feeds posts is elastic. Consider, for instance, a user interested in the latest headlines from his favorite newspaper, or a college student willing to learn about the latest developments of his football team. There may be multiple posts that satisfy the demands of such users. The literature of caches, in contrast, presumes that each of the cached items is uniquely identified and non-substitutable, and that demand is inelastic.

Classes of items The occupancy of caches is given by the items that it stores, where each item is uniquely identified. Caches do not store repeated items. For the purposes of this work, in contrast, posts stored in a News Feed are distinguished solely by their publisher, and the News Feed may store multiple posts from the same publisher. Whereas the News Feed behaves as a cache that can store multiple copies of items of the same class, in traditional caches each item corresponds to its own class.

Capacity For all practical purposes, the News Feed can be assumed to be infinite in size, i.e., the News Feed can admit all the published posts. Nonetheless, it is well known that the topmost positions of the News Feed receive higher visibility. This, in turn, motivates our study of the (average) topmost K positions of the News Feed.

TTL News Feed model

Next, we introduce the proposed News Feed model. To each content posted in a News Feed we associate a time-to-live (TTL) timer. The timer is set to T when the content is inserted, and is decremented at fixed time intervals. Once the timer reaches zero, it expires and the associated content is removed from the News Feed.

Why TTL model?

It is well known that Facebook uses recency as a parameter to show posts to users [START_REF]How Facebook News Feed Works[END_REF][START_REF] Facebook | [END_REF]. TTL counters are a natural way to capture the perishable nature of posts. Furthermore, TTL counters are a flexible way to extend FIFO schemes. In general, TTL-based models are well-suited to represent objects with expiration times [START_REF] Jung | Modeling TTLbased Internet caches[END_REF].

While proposing the TTL model of a News Feed, our aim is not to argue whether Facebook deploys TTL counters, which is out of the scope of this paper. Instead, our goal is to show that a simple model can already capture the dynamics of Facebook News Feed. Then, we leverage the flexibility of TTL counters to propose novel News Feed algorithms.

Model description

Let I be the set of I users, and let J be the set of J publishers: J i denotes the set of publishers followed by user i ∈ I. Publisher j ∈ J publishes posts according to a Poisson process with rate Λ j . The total publishing rate is Λ = J j=1 Λ j . Whenever a content is generated, it is immediately sent to the News Feed of all users. In what follows, we provide further details about how user i reacts to the content arrival.

Content and publisher classes We consider C content classes. Each content class corresponds to a set of posts published at a given user News Feed. In the most general case, each user-publisher pair is associated to a given content class. In that case, the class associated to the i-th user and j-publisher is denoted by the ordered pair (i, j).

Alternatively, we associate each user-publisher pair to one of two classes. Class l i (resp., l i ) is the class of contents generated by publishers that the i-th user "likes" (resp., does not "like"). We denote by L(i, j) the indicator variable which characterizes the set of publishers that a user likes,

L(i, j) = 1, if user i "likes" publisher j 0, otherwise (1)
Order of posts The simplest instance of the proposed model corresponds to a FIFO queue, wherein contents are ordered in the News Feed based on the instant at which they are posted, and new arrivals shift older posts (Section 4.1.1). The TTL model, in contrast, does not presume any pre-established ordering of posts in the News Feed. In particular, it is flexible to account for eventual rearrangements of posts. Note that the TTL model can be parameterized to capture the behavior illustrated in Figure 2, wherein the bias present in the topmost positions is different from that seen in the remainder of the News Feed. This occurs, for instance, if posts with larger TTL are placed on the top of the News Feed, producing different biases at different News Feed positions.

Timer classes We consider per-class content dynamics. For concreteness, except otherwise noted we let L(i, j) be the class of contents generated by publisher j at the News Feed of the i-th user.

Whenever a content from class L(i, j) is generated, it is inserted in the News Feed of the i-th user and a timer with value T L(i,j) is associated to that content. Even though we assume, for simplicity, that the initial timer values are set to a fixed constant, our analysis also holds if the initial values of the timers are sampled from a probability distribution with mean T L(i,j) .

We expect that T 1 ≥ T 0 , i.e., contents generated by publishers that the user "likes" remain longer in the News Feed, when compared against those that the user does not "like". Nonetheless, we do not explicitly assume any relationship between T 1 and T 0 . Instead, we perform simple consistency checks using the collected measurement data (Section 5).

Metrics of interest

Next, we derive the metrics of interest corresponding to an infinite capacity News Feed. Recall that we assume that users scroll up to an average of K News Feed positions, i.e., we study the visibility and occupancy of an average of K topmost positions. To simplify notation we drop the explicit dependence of metrics and corresponding variables on the value of K, e.g., denoting N ij (K) and T L(i,j) (K) simply as N ij and T L(i,j) .

The occupancy of the j-th publisher at the i-th News Feed, N ij , follows from Little's Law and is given by

N ij = Λ j T L(i,j) (2)
The expected number of slots occupied in a News Feed is given by the sum of N ij , for all j,

j∈J N ij = K. (3)
The visibility of publisher j at the News Feed of user i, π ij , is given by

π ij = 1 -e -Nij . (4)
The equation above follows from the observation that the dynamics of posts by the j-th publisher at the News Feed of user i are given by an M/G/∞ queue. Arrivals of posts occur with rate Λ j , and each arrival remains in the News Feed for an average of T L(i,j) time units. The probability that there is at least one customer in the M/G/∞ equals the probability that there is at least one post from publisher j at the News Feed of user i, and is given by (4).

Special case: FIFO News Feed

When all posts are associated to the same TTL T , and contents are inserted in the News Feed in the order that they are created, the TTL model behaves as a FIFO queue, as described in Section 4.1.1. If we further allow posts to be filtered, we refer to the resulting model as a filtered FIFO model. Let p ij be the filtering probability. In a filtered FIFO model, we let T = 0 with probability 1 -p ij , and T = T otherwise, where T is a fixed and given constant, T > 0.

As before, we assume that publisher j ∈ J publishes posts according to a Poisson process with rate Λ j . Recall that the total publishing rate is given by Λ = J j=1 Λ j . In the filtered model, let λ ij ≤ Λ j be the effective arrival rate of posts published by j in the News Feed of user i. Then,

λ ij = p ij Λ j .
Under the filtered FIFO model, (2) together with (3) imply that

T = K k λ ik . (5)
The visibility π ij is given by ( 4), where

N ij = λ ij K l λ il . (6)
If we further assume that p ij = p for all user-publisher pairs, we obtain the uniformly filtered FIFO model, where

N j = Λ j K Λ . (7)
As we assume that all users follow the same set of sources, under the uniformly filtered FIFO model the expected occupancy of publisher j at user i, N ij , is the same for all users. Therefore, in this case we denote it simply as N j .

Finite size FIFO News Feed

The analysis presented above assumes an infinite size News Feed, wherein users are interested, on average, at the topmost K positions. Alternatively, consider a finite size FIFO News Feed, which can accommodate up to K posts. We assume that a News Feed has K slots, new posts are inserted at the top of the News Feed and each new arrival shifts older posts one position lower. A post is evicted from the News Feed when it is shifted from position K.

We denote by λ i the aggregate rate of posts published in the News Feed of user i, λ i = J j=1 λ ij . We further let λ i,-j be the arrival rate of posts in the News Feed of user i from all publishers other than j, λ i,-j = λ i -λ ij .

The occupancy of contents of publisher j follows from Little's law and is given by

N ij = λ ij K/λ i . (8)
The visibility of publisher j is given by

π ij = 1 - λ i,-j λ i K = 1 -1 - N ij K K , (9)
and the rationale goes as follows. After every new arrival, with probability λ i,-j /λ i the topmost post of publisher j will be shifted down by one unit. After K consecutive shifts, which occur with probability (λ i,-j /λ i ) K , publisher j will not be visible at the News Feed of user i. When K = 1 we have N ij = π ij . For large values of K, (9) can be approximated by [START_REF] Altman | Competition over timeline in social networks[END_REF].

Under the FIFO instances of the model presented above, posts are filtered uniformly at random. For this reason, such instances yield simple baselines against which the filtering effects introduced by the News Feed algorithm can be compared. In Section 6 we revisit the FIFO model under this perspective.

A Model-based perspective at the measurement findings

In this section, we take a model-based perspective at the measurement findings. First, we implicitly account for user "likes" through their impact on the effective arrival rates in Section 5.1. Then, we explicitly account for "likes" in Section 5.2.

Indirectly accounting for "likes": a multi-class perspective on measurements

We validate the proposed model using data from the 2018 Italian elections, through a multi-class perspective on the measurements. Each user-publisher pair is associated to a class. Class (i, j) is associated to the i-th user and the j-th publisher, and corresponds to an effective arrival rate of λ ij posts per snapshot.

Variable description j j-th publisher i i-th News Feed user Λ j post creation rate by publisher j λ ij arrival rate of posts from j at user i λ i total arrival rate of posts at user i L(i, j)

1 if user i likes publisher j, 0 otherwise TTL model variables T l expected TTL for posts from class l, l = L(i, j) T (l) i expected TTL for posts from class l, with user discrimination, l = L(i, j) T ij expected TTL for posts from publisher j at user i w L(i,j)

weight associated to class-L(i, j) We start by introducing some additional notation regarding our measurements. The notation is summarized in Table 2. Let Q ij be the measured numbered of unique posts from publisher j at user i. Let S i be the number of snapshots taken by user i. Then, the measured effective arrival rate is given by λij

= Q ij S i . ( 10
)
Note that λij is modulated through "likes". In this section, at each bot i we assume that the same timer is used for all the publishers. Then, the TTL model is equivalent to FIFO (see Section 4.2.4). Publishers' presence in the News Feed is discriminated upstream by filtering their posts before they arrive to the News Feed, i.e., through rates λ ij . For this reason, in this section we use model equations ( 4)-( 6) with the arrival rate at a bot, λ ij , set to the measured one, λij . "Likes" are indirectly taken into account through rates. Figure 4(a) compares measured occupancies against model predictions at the News Feed topmost position (K = 1). Each point corresponds to a userpublisher pair. A point (x = N ij , y = Ñij ) indicates that, for the given pair, an occupancy N ij estimated by the proposed model using eq. ( 6) corresponds to a measured occupancy Ñij . Most of the points are close to the Ñij = N ij line, indicating the expressive power of the model. Appendix Appendix C.1 contains results for K > 1, accounting for visibility in addition to occupancy as the target metric.

Next, our goal is to quantitatively assess the expressive power of the multiclass model. To this aim, we conduct a linear regression followed by an hypothesis test on the coefficients produced by the linear regression. Let the measured occupancy be given as a function of the model-based occupancy as follows,

Ñij = β 1 N ij + β 0 . (11)
The null and alternative hypotheses are given by • H 0 : there is no relationship between Ñij and N ij , i.e., β 1 = 0;

• H a : there is relationship between Ñij and N ij , i.e., β 1 = 0

The p-value for β 1 = 0 is less than 2 -16 , allowing us to reject the null hypothesis. We repeated the test for all values of K ranging from 1 to 30, and obtained similar results as indicated in Table 3.

Directly accounting for "likes": a two-class measurement analysis

In this section, we explicitly account for user "likes" in the News Feed occupancies. To this aim, we divide the publisher-user pairs into two classes, and show the expressive power of the model through a simple parameterization which involves only two parameters, T 1 and T 0 , corresponding to the TTL of posts from publishers that users "like" and do not "like", respectively. Let I ij be the number of impressions from publisher j at user i. Let I 1 be the number of impressions at News Feeds of users who "like" the publishers of the corresponding impressions (I 0 is similarly defined). Then,

Occupancy

I l = ∀(i,j)|L(i,j)=l I i,j . (12)
Correspondingly, let G l (resp. G 0 ) be the number of posts generated, counted as many times as the number of users who "like" (do not "like") the publishers who generated these posts. Recall that C j is the number of unique posts created by publisher j. Then,

G l = ∀(i,j)|L(i,j)=l C j . (13)
The estimate of the TTL associated to class l is given by

Tl = I l /G l , l ∈ {0, 1}. (14)
In Figure 4(b) each point corresponds to a user-publisher pair. As in Figure 4(a), we let K = 1 (results for K = 30 are presented in Appendix Appendix C.1). In Figure 4(b), a point (x = N ij , y = Ñij ) indicates that, for the given pair, an occupancy N ij estimated by the proposed model using eq. ( 2) corresponds to a measured occupancy of Ñij . We also resort to the same sort of hypothesis tests described in the previous section, and reject the null hypothesis according to which there is no relationship between the model and the measurements. A summary of the measurement results, for K = 1 and K = 30, is presented in Table 3.

The accuracy of the model can also be assessed through the R 2 score, which ranges between 1 and 0. An R 2 score of 1 indicates that the variance in the target variable is fully explained by the model. As expected, the R 2 scores (resp., p-values) of the two-class model are smaller (resp., larger) than those of the multi-class model. In addition, we observe that the predictive power of the two-class model when applied to the topmost position (K = 1) is significantly lower when compared against its application to the remainder of the News Feed (K = 30). This is partly explained by the fact that the bias is stronger at the topmost position (Section 3.2). We leave a more detailed analysis of simple models for the topmost position as subject for future work.

Summary In this section, we evaluated the explanatory power of the model in light of the measurements collected during the Italian 2018 elections. In particular, we have shown that a very simple instance of the model with two parameters is already able to capture the occupancies experienced by users (Section 5.2). In addition, we indicated that a multi-class instance of the model, wherein the number of parameter equals the number of publishers times the number of bots (180 in the experiment), produces occupancy estimates with higher accuracy, at the expense of additional complexity (Section 5.1). In the sections that follow, we leverage the proposed model for mechanism design purposes.

A fairness-based News Feed mechanism

Next, we leverage the proposed News Feed model to derive a fairness-based mechanism to design News Feeds. We present the problem formulation (Section 6.1), followed by its general solution (Section 6.2) and by an analysis of α-fair utility functions (Section 6.3). Then, we bridge the utility maximization framework and measurements to illustrate the applicability of the mechanism (Section 6.5).

Utility maximization formulation

We associate to each user-publisher pair a utility function U ij (h ij ) which is an increasing, strictly concave and continuously differentiable function of h ij over the range 0 ≤ h ij ≤ 1. Recall from Section 2.4 that h ij denotes the hit probability of publisher j at user i, where the hit probability captures the exposure of publishers to users.

We further assume that utilities are additive. Then, the goal is to maximize the sum of the utilities for each of the individual publishers [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF][START_REF] Dehghan | A utility optimization approach to network cache design[END_REF]. The optimization problem is posed as follows, max

J j=1 U ij (h ij ) (15) s.t. J j=1 N ij = K, N ij ≥ 0 ( 16
)
where h ij are concave and non-decreasing functions of N ij . As discussed in Section 2.4, we consider two possible instantiations of the hit probability, corresponding to the normalized occupancy, given by N ij /K, and the visibility π ij , given by ( 4) and ( 9) under the TTL and finite capacity FIFO models, respectively. In summary,

h ij (N ij ) =      N ij /K, for normalized occupancy, 1 -e -Nij ,
for visibility (TTL model),

1 -(1 -N ij /K) K ,
for visibility (finite FIFO).

In all cases above, h ij (N ij ) is an increasing and concave function of

N ij . Let Ũij (N ij ) = U ij (h ij (N ij )). It follows that • Ũij (N ij
) is non-decreasiing, as U ij and h ij are so;

• Ũij (N ij ) is concave, as U ij is concave and non-decreasing and h ij is concave.

Therefore, the objective function ( 15) is equivalent to

max J j=1 Ũij (N ij ). ( 18
)
The general solution to the unified problem formulation introduced above is presented in the sequel.

Problem solution

To solve the convex optimization problem posed above, we introduce its corresponding Lagrangian,

L(N, β) = j Ũij (N ij ) -β j (N ij -K) ( 19
)
where N is the vector of N ij values, and β is the Lagrange multiplier. Taking the derivative of the Lagrangian with respect to N ij ,

∂L ∂N ij = Ũ ij (N ij ) -β. (20)
An allocation N ij is a global optimizer if and only if there exists β such that N is feasible and

Ũ ij (N ij ) -β = 0, if N ij > 0, Ũ ij (N ij ) -β ≤ 0, if N ij = 0. ( 21
)
At the optimum, all the publishers that appear in the News Feed have assigned a space that equalize their marginal utilities (i.e. N ij > 0 and

N ik > 0 imply that Ũ ij (N ij ) = Ũ ik (N ik )
). The publishers that not appear have smaller marginal utility (i.e., Ũ

il (N il ) ≤ Ũ ij (N ij ) if N ij > 0 and N il = 0). Remark that if Ũ (0) = +∞ (e.g. if U ij (h) ∝ log(h)), then necessarily N ij > 0 for each j.
The solution can be found by a water-filling type algorithm: we start from the null vector where no publisher appears in the timeline (N ij = 0 for all j) and we gradually allocate space to the publisher(s) with largest marginal utility(ies).

Occupancy vs rate-based fairness

In the problem formulation and solution presented above, we accounted for occupancy-based rather than rate-based fairness [START_REF] Richard | Weighted Fair Caching: Occupancy-Centric Allocation for Space-Shared Resources[END_REF]. To appreciate the distinction between the two sorts of fairness, consider the problem of setting the same average space to different publishers. Such occupancy-based allocation will penalize prolific publishers more strongly than a rate-based allocation where publisher rates are uniformly multiplied by a constant factor. In Section 6.5 we numerically contrast the effect of occupancy-based fairness against a baseline wherein occupancies are proportional to content generating rates.

News Feed fairness: α-fair utilities

The optimal allocation of News Feed space to publishers through problem (15) depends on the shape of the utility functions. The use of a given family of utility functions corresponds to the selection of a fairness criterion. In this section we characterize the optimal allocation under the usual concept of α-fairness as it is considered in communication networks [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF][START_REF] Kelly | Charging and rate control for elastic traffic[END_REF][START_REF] Destounis | Alpha fair coded caching[END_REF][START_REF] Dehghan | A utility optimization approach to network cache design[END_REF].

U ij (h ij ) = w ij h 1-α ij 1-α , α ≤ 0, α = 1. w ij log(h ij ), α = 1. (22)
In what follows we will consider the case where the hit probability coincides with the normalized occupancy.

Proportional fairness

Choosing α = 1 yields proportional fairness. In this case Ũij (h ij ) = w ij log(N ij /K), implying that N ij > 0 for each publisher. From the first equation in [START_REF] Destounis | Alpha fair coded caching[END_REF], it follows that

Ũ ij N ij = w ij /N ij = β . (23)
Imposing the constraint ( 16) we obtain

β = J j=1 w ij /K.
Once the value of β is known, it can be substituted in [START_REF] Diakopoulos | Algorithmic accountability reporting: On the investigation of black boxes[END_REF] to yield

N ij = w ij K k w ik , T ij = w ij K Λ j k w ik . (24)

Potential delay fairness

If α = 2, U ij (h ij ) = -w ij /h ij , U (h ij ) = w ij /h 2 ij
and in a similar way we obtain

N ij = K √ w ij J j=1 √ w ij , T ij = K Λ j √ w ij J j=1 √ w ij . (25)

Max-min fairness

Max-min fairness is the limiting case of α-fairness in the limit when α diverges [START_REF] Boudec | Rate adaptation, congestion control and fairness: A tutorial[END_REF]. In our case a max-min fair allocation corresponds to provide the same occupancy to each publisher. Then, we have:

N ij = K/J, T ij = K/(Λ j J). (26)
Note that the max-min fairness allocation is independent of the weights w ij .

Summary

In this section, we presented expressions for publishers occupancy and visibility, under three fairness criteria. In the following section we show how to extend the obtained expressions to account for class-based metrics, and in Section 6.5 we compare the derived class-based metrics against baselines, illustrating a way to quantify biases from real measurements.

Class-based optimization

The framework introduced in the previous section for per-publisher optimization can be easily adapted to a per-class optimization. In this case we divide the user-publisher pairs into classes, and parameters are set in a per-class basis.

To simplify presentation, we specialize the presentation to classes determined by user's "likes", where for each user i, we distinguish the class of publishers i likes (identified by L(i, j) = 1 in (1)), and the class of publishers that i follows without expressing likes (identified by L(i, j) = 0). We denote by λ (l) i (resp., N (l) ij ) the aggregate arrival rate (resp., occupancy) of posts of class l in the News Feed of user i, λ

(l) i = j|L(i,j)=l Λ j , N (l) i = j|L(i,j)=l
N ij . (27) Let T (l) i
denote the TTL of posts of class l in the News Feed of user i. Then,

N ij = Λ j T (l)
i , where l = L(i, j).

The expression of T (l) i for the three special fairness criteira considered in the previous section can be similarly derived, leading to:

T (l) i =                          K λ (l) i w (l) i 1 k=0 w (k) i , proportional fairness, (29a) K λ (l) i w (l) i 1 k=0 w (k) i
, potential delay fairness,

, max-min fairness. (29c)

Class-based vs publisher-based allocation

In a class-based fair allocation, space is allocated fairly across classes: class occupancies are determined by the specific fairness criteria, while, inside while inside a given class publisher occupancies are proportional to publishing rates as indicated by [START_REF] Eslami | Feedvis: A path for exploring news feed curation algorithms[END_REF]. Consider, for instance, a max-min fairness allocation. Then the class of "liked" publishers is posed to have the same average occupancy as the remaining publishers, but this does not translate into equal publisher occupancies. For example, in our experimental setting, each of the 6 publishers "liked" by bot i will on average occupy 1/12-th of bot-i timeline, while any of the other 24 publishers will on average get 1/48-th of it. Hence, the "liked publishers" are overall advantaged under max-min fairness allocation.

Italian election case study

Next, we illustrate how the proposed utility-based framework can shed further insights into the Italian election dataset. Throughout this section, we consider a proportional fairness allocation for the two-class model (Section 6.4).

In particular here we show results for the topmost position and w (l) i = 1 for each i and l, while in Appendix Appendix E we report results for a broader set of weights and values of K.As discussed in Section 6.4.1, in this case the "liked" publishers get collectively as much timeline space as all the others.

Figure 5 shows different publishers' occupancies at the 6 bots when K = 1: occupancies measured at the bots (crosses and lines), occupancies computed by our model to maximize 2-class proportional fairness (bars) and publishers' posting rates (circles).

At the undecided bot, all publishers belong to the same class. Then, an allocation under proportional fairness yields occupancies proportional to publishing rates. In our measurements, in contrast, we observed that occupancies aren't proportional to rates (Sec 3.2), which indicates that the filtering effects are non-trivial even for neutral users. For all the other bots (except the rightoriented one), we observe that the "liked publishers" are favored under the 2-class fairness model. This is due to the fact that the 6 "liked" publishers get collectively as much space as all other 24 bots. Under each class, occupancies are split proportionally to publishing rates. Therefore, the "liked" publishers end up having less competition for space than other "non-liked" publishers with similar publishing rates. The situation is different at the right bot. Among the 6 right-oriented publishers "liked" by the right-oriented bot, we find some of the most prolific publishers in our dataset: their aggregate rate is almost equal to the aggregate rate of all the other 24 publishers. As a consequence, all the publishers get occupancies almost proportional to their publishing rate.

We observe that our simple 2-class model already qualitatively predicts some of the results observed in our traces: most of the "liked" publishers indeed also have larger measured occupancies (crosses and lines in Fig. 5). Nonetheless, there are still a number of exceptions. For example, "La Repubblica" exhibits a quite large occupancy independently of the orientation of the corresponding bot. This may be justified by the fact that "La Repubblica" is a newspaper, rather than a party or a candidate, and Facebook News Feed algorithm may be filtering less news. The same, however, does not hold for other newspapers appearing in the list. The occupancy of "Il Giornale" at the different News Feeds, for instance, is quite small (except at the right bot), even though it is the source with the largest publishing rate.

In order to quantify the discrimination among different providers introduced by our utility maximization allocation or by Facebook News Feed filtering algorithm we introduce a new metric. We define the (occupancy) bias as the difference between a given normalized occupancy estimate and the normalized occupancy that would have been obtained if timelines were operated according to the FIFO model without content filtering. We denote by b (m) ij the occupancy bias of publisher j at user i. The symbol m refers to the scenario against which the FIFO baseline model is compared. It equals Face, PropF, MaxMinF and PotentF respectively when referring to the occupancies derived from raw Facebook measurements, proportional fairness, max-min fairness and potential fairness models. Definition 4 (bias). The bias incurred by posts of publisher j at the News Feed of user i is given by b

(m) ij = N (m) ij -N j K . (30)
In the definition above, N j is the baseline occupancy under FIFO as given by [START_REF] Bakshy | The role of social networks in information diffusion[END_REF] and does not depend on the specific bot. We observe that j b (m) ij = 0, as the sum of occupancies at a given bot equals K. Note that the definition of bias is general, and can be coupled with different baseline models for occupancy (see Appendix Appendix D).

Discussion Statistical bias is a systemic deviation, e.g., of an estimator, with respect to the true value of a parameter. In this paper we use the term bias with a different, albeit intuitively related, meaning. We assume that users explicitly express their preferences by selecting which publishers they follow and like. Any deviation from the unfiltered occupancy, as estimated by the proposed model, is attributed to bias. This kind of bias is called social bias [START_REF] Baeza-Yates | Bias on the web[END_REF]. Note that our definition of bias does not necessarily entail a negative connotation, as biasing users towards their interests might be a desired feature.

(PropF) ij = b (MaxMinF) ij = b (PotentF) ij
as in this section we assume w (l) i = 1, and see Appendix Appendix D for additional results). Figure 6 supports the observations reported from Fig. 5. In particular we observe that b (PropF) ij is null or almost null for the undecided bot and for the right bot, while for the others there are significant positive (resp., negative) biases for the "liked" (resp., "nonliked") contents. Facebook biases b (Face) ij appear to be qualitatively aligned with those estimated through the 2-class proportional fairness model, , particularly at the center-left and left bots. Nonetheless, there are a number of exceptions, as discussed above.

We observe that the Facebook News Feed algorithm produces high biases even at the undecided bot. In addition, the bias at the topmost position does not reflect user preferences, specially at the far-right, right and undecided bots. Our analysis sheds light on some peculiar choices of Facebook that are difficult to explain even taking into account users' preferences as expressed through "likes."

Practical implications

The proposed mechanisms evidence the challenges involved in building a fair News Feed. Any fair solution must trade between conflicting goals such as 1) giving more exposure to favorite publishers, 2) reserving space for non-preferred publishers, 3) penalizing publishers that produce irrelevant content at high rates (e.g., spam) and 4) avoiding bias towards publishers that produce at low rates. We believe that the proposed mechanisms constitute a principled way to cope with such conflicting goals, through the use of utility functions.

Ultimately, users should be aware of the filtering that they are exposed to, and tune their utilities based on their needs. By promoting user awareness, the risk of amplifying filter bubbles should be mitigated. A brief discussion of the compliance of the proposed methodology to Facebook policies is presented in a short preliminary version of this work [START_REF] Hargreaves | Biases in the Facebook News Feed: a Case Study on the Italian Elections[END_REF].

One way to implement the proposed mechanisms is through tools such as MIT Gobo [START_REF]GOBO[END_REF] or FeedVis [START_REF] Eslami | I always assumed that I wasn't really that close to [her[END_REF]. Such social media aggregators can be fed by posts from different sources, e.g., Facebook, Twitter and Youtube, providing filters that users can control. Therefore, users can explicitly set mechanisms to decide what is edited out of their News Feed. We envision that these tools can be coupled with variants of the News Feed control mechanisms proposed in this paper. Then, A/B tests may be used to select which mechanisms are best suited to different users based on their explicit and implicit feedback, e.g., obtained through questionnaires and click-rates.

Related work

The literature on Facebook News Feed includes topological aspects related to cascading structures and growth [START_REF] Gjoka | Walking in facebook: A case study of unbiased sampling of OSNs[END_REF][START_REF] Ugander | The Anatomy of the Facebook Social Graph[END_REF][START_REF] Cheng | Do Diffusion Protocols Govern Cascade Growth? Icwsm[END_REF] and its effects on the creation of echo chambers and polarization [START_REF] Bessi | Personality traits and echo chambers on Facebook[END_REF][START_REF] Bessi | Users polarization on Facebook and Youtube[END_REF].

Social networks, TTL-counters and utility-based allocation

The proposed News Feed model relies on TTL counters. TTL-based caching mechanisms are versatile and flexible, and can be used to reproduce the behavior of traditional caching policies such as LRU and FIFO [START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Tortelli | ModelGraft: Accurate, scalable, and flexible performance evaluation of general cache networks[END_REF][START_REF] Dehghan | A utility optimization approach to network cache design[END_REF][START_REF] Ferragut | Optimizing TTL caches under heavy-tailed demands[END_REF][START_REF] Neglia | Cache policies for linear utility maximization[END_REF]. In this paper, we leverage the analytical tractability of TTL-based caches, showing how to adapt them for the purposes of modeling and optimization of the News Feed.

The implications of the limited budget of attention of users in OSNs have been previously studied by Reiffers-Masson et al. [START_REF] Reiffers-Masson | Posting Behavior Dynamics and Active Filtering for Content Diversity in Social Networks[END_REF] and Jiang et al. [START_REF] Jiang | How to optimally allocate your budget of attention in social networks[END_REF]. In these two papers, the authors consider the problem of optimally deciding what to post and to read, respectively. Such works are complementary to ours. To the best of our knowledge, none of the previous works considered the problem of inferring the visibility of publishers from News Feed measurements, and using such measurements to parameterize models and propose utility-based mechanisms for News Feed design.

Fairness, accountability and transparency

The literature on fairness, accountability and transparency (FAT) is rapidly growing [START_REF]Conference on Fairness, Accountability, and Transparency (FAT*)[END_REF][START_REF]FATE: Fairness, Accountability, Transparency, and Ethics in AI[END_REF][START_REF] Wing | Data for Good: Scary AI and the Dangers of Big Data[END_REF], accounting for its implications on social networks [START_REF] Valenzuela | Is there social capital in a social network site?: Facebook use and college students' life satisfaction, trust, and participation[END_REF], risk score estimation [START_REF] Kleinberg | Inherent Trade-Offs in the Fair Determination of Risk Scores[END_REF][START_REF] Barabas | Interventions over Predictions: Reframing the Ethical Debate for Actuarial Risk Assessment[END_REF], recommender system [START_REF] Krishnasamy | Detecting Sponsored Recommendations[END_REF][START_REF] Zehlike | FA*IR: A Fair Topk Ranking Algorithm[END_REF], resource allocation [START_REF] Lan | An Axiomatic Theory of Fairness in Network Resource Allocation[END_REF], individuals classification in order to prevent discrimination [START_REF] Dwork | Fairness through awareness[END_REF] and computational policy [74,[START_REF] Gilbert | Computational Modelling of Public Policy: Reflections on Practice[END_REF], using tools such as causal analysis [START_REF] Zhang | Fairness in Decision-Making: The Causal Explanation Formula[END_REF], quantitative input influence [START_REF] Datta | Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems[END_REF] and machine learning [START_REF] Bilal Zafar | Learning fair classifiers[END_REF][START_REF] Pleiss | On fairness and calibration[END_REF].

Surveys and books on notions of fairness include those by Moulin [START_REF] Moulin | Fair Division and Collective Welfare[END_REF], Zliobaite [START_REF] Indrė | Measuring discrimination in algorithmic decision making[END_REF], Rmoei and Ruggieri [START_REF] Romei | A multidisciplinary survey on discrimination analysis[END_REF], Narayanan [START_REF] Narayanan | Tutorial: 21 Fairness Definitions and Their Politics[END_REF] and Drosou et al. [START_REF] Drosou | Diversity in big data: A review[END_REF]. The later is a survey about diversity concepts from the information retrieval literature [START_REF] Wang | Milking the Cache Cow With Fairness in Mind[END_REF]. The mechanism design proposed in this paper is both a diversityaware and fairness-aware allocation scheme, taking users' and publishers' perspectives, respectively.

ACM [START_REF] Garfinkel | Toward algorithmic transparency and accountability[END_REF] introduces a set of principles intended to ensure fairness in the evolving policy and technology ecosystem: awareness, access and redness, accountability, explanation, data provenance, auditability, and validation and testing. We particularly focus on awareness, explanation and auditability, as we do not rely on the Facebook API to collect impressions. Algorithmic transparency is one of the cornerstones of the General Data Protection Regulation (GDPR), which stresses the importance of providing explanations for automatic recommendations [START_REF] Goodman | EU regulations on algorithmic decision-making and a "right to explanation[END_REF]. The measurements, models and mechanisms proposed in this paper contribute to the development of GDPR-compliant policies, as the allocations derived from the proposed model-based mechanism are built on top of first principles.

Most of the previous literature on social fairness assumes that utility functions are non-parametric [START_REF] Zhang | Fairness in Decision-Making: The Causal Explanation Formula[END_REF][START_REF] Abebe | Fair division via social comparison[END_REF][START_REF] Hal R Varian | Non-parametric tests of consumer behaviour[END_REF] or, in classification problems, that cost functions are linear combinations of false positive and false negative rates [START_REF] Pleiss | On fairness and calibration[END_REF][START_REF] Kleinberg | Inherent Trade-Offs in the Fair Determination of Risk Scores[END_REF][START_REF] Corbett-Davies | Algorithmic decision making and the cost of fairness[END_REF]. Convex utility functions, such as the α-fair family of utilities, are prevalent in the literature of networking and computer systems [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF][START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Multiple Resource Types[END_REF][START_REF] Kelly | Charging and rate control for elastic traffic[END_REF][START_REF] Dehghan | A utility optimization approach to network cache design[END_REF][START_REF] Shakkottai | Network optimization and control[END_REF][START_REF] Pérez | A tutorial on decomposition methods for network utility maximization[END_REF][START_REF] Bonald | Impact of fairness on Internet performance[END_REF]. In this paper, we identify how parameterized utilities can be applicable to the analysis of social networks. We believe that such connection is a step towards promoting more dialogue between the networking and the online social network communities on the issue of fairness.

Algorithmic bias and forms to audit it were investigated in [START_REF] Baeza-Yates | Bias on the web[END_REF][START_REF] Diakopoulos | Algorithmic accountability reporting: On the investigation of black boxes[END_REF][START_REF] Sandvig | Auditing Algorithms : Research Methods for Detecting Discrimination on Internet Platforms[END_REF]. In [START_REF] Epstein | The search engine manipulation effect (SEME) and its possible impact on the outcomes of elections[END_REF][START_REF] Kulshrestha | Quantifying Search Bias: Investigating Sources of Bias for Political Searches in Social Media[END_REF] it was shown that search engine rank manipulation can influence the vote of undecided citizens. The models proposed in this paper further foster accountability, by quantifying bias in the Facebook News Feed.

Public datasets and reproducible methodologies

The behavior of users searching for visibility was studied in [START_REF] Eslami | First I like it, then I hide it: Folk theories of social feeds[END_REF][START_REF] Bucher | Want to be on the top? Algorithmic power and the threat of invisibility on Facebook[END_REF][START_REF] Sleeper | The post that wasn't: exploring self-censorship on facebook[END_REF]. Such studies are primarily based on small datasets. A notable exception is [START_REF] Bakshy | The role of social networks in information diffusion[END_REF][START_REF] Bakshy | Exposure to ideologically diverse news and opinion on Facebook[END_REF][START_REF] Guillory Adam | Experimental evidence of massive-scale emotional contagion through social networks[END_REF][START_REF] Sun | Gesundheit ! Modeling Contagion through Facebook News Feed Mechanics of Facebook Page Diffusion[END_REF], who considered a massive dataset provided by Facebook through restrictive nondisclosure agreements. Datasets to assess Facebook publishers' visibilities are usually not made publicly available. Our work aims to contribute by filling that gap.

It is out of the scope of this paper to present a nuts-and-bolts perspective on how Facebook News Feed works. Instead, our goal is to provide a simple model that can explain the occupancy and visibility of different publishers, given a reproducible measurement framework. We profile Facebook, which is taken as a black box to be scientifically analyzed. This approach dates back to Skinner tests [START_REF] Epstein | Closing the AI Knowledge Gap[END_REF], and has been gaining significant attention in the literature of social networks [START_REF] Tan | Detecting Bias in Black-Box Models Using Transparent Model Distillation[END_REF].

Conclusion

We presented a framework encompassing reproducible measurements, analytical models and utility-based mechanisms for the analysis of Facebook News Feed algorithm. The analytical enables quantitative what-if analysis to assess the bias introduced by the News Feed algorithm. The utility-based mechanisms shed light into novel directions towards the control of the News Feed.

Our measurements indicate that the News Feed algorithm currently tends to reinforce the orientation indicated by users about the pages they "like", by filtering posts and creating biases among the set of followed publishers. The effects of filtering are stronger at the topmost position where only a fraction of the set of publishers followed by the users was represented. We observed that a neutral user that did not "like" any page was also exposed to a noticeable bias.

Facebook mission is to "give people the power to build community." We believe that the measurements, model and tools presented in this work are one step further towards that goal, as they help evaluating algorithms' transparency and promote user awareness about the filtering process they are submitted to. Ultimately, such awareness is key to protect and empower Facebook users, communities, society and democracy as a whole [START_REF] Lichfield | Technology is threatening our democracy. How do we save it[END_REF].

Figure 1 :

 1 Figure 1: (a) Posts per publisher, (b) posts per publisher that were seen by at least one of our bots.

Figure 2 (

 2 a) also shows that the oc-

Figure 2 :

 2 Figure 2: Normalized occupancy as a function of K, classified by (a) publisher orientations and (b) user preferences.

Figure 3 :

 3 Figure 3: Publishers impressions at the six bots (bars colored by preferences) and number of created posts (black dots). The number of created posts is represented when at least one impression from the corresponding publisher was observed.

Figure 4 :

 4 Figure 4: Model validation of occupancies for K = 1: (a) multi-class and (b) two-class.

Figure 5 :

 5 Figure 5: Publishers' occupancies under proportional fairness (bars colored by preferences),Facebook measured occupancies (crosses and lines) and publishing rates (circles), for the topmost position, at the six bots. At the undecided bot, proportional fairness occupancies decrease with respect to publishing rates, but measured occupancies deviate from baseline.

Figure 6 :

 6 Figure 6: Proportional fairness bias (bars) and Facebook News Feed bias (crosses), for the six bots

right-oriented bot undecided bot far-right-oriented bot left-oriented bot M5S-oriented bot center-left-oriented bot Il Giornale Il Fatto Quoti Lega Salvini Noi con Salvini La Repubblica M5S news W IL M5S M5S Democratica Luigi Di Maio Il manifesto M. RenziNs L.Borgonzoni Giorgia Meloni P. Democratico Adesso ti inf CasaPound Forza Nuova Beppe Grillo Ordine Futuro Sinistra Italiana Roberto Fiore Matteo Renzi Giuseppe Civati Articolo UNO Possibile Laura Boldrini Fascisti uniti Il Giornale Il Fatto Quoti Lega Salvini Noi con Salvini La Repubblica M5S news W IL M5S M5S Democratica Luigi Di Maio Il manifesto M. RenziNs L.Borgonzoni Giorgia Meloni P. Democratico Adesso ti inf CasaPound Forza Nuova Beppe Grillo Ordine Futuro Sinistra Italiana Roberto Fiore Matteo Renzi Giuseppe Civati Articolo UNO Possibile Laura Boldrini

Table 1 :

 1 Comparison between News Feed and caches

		News Feed	Cache
	Trigger event	post publishing	content request
	Insertions and	after a post creation	after a miss
	evictions	or user engagement
		Nature of contents and requests
	Cache stores	multiple items of content	at most one copy
		from given class	of a specific item
	Requests for	general content classes	specific content items
		Classes of items
	Control	of items by	of specific content
	occupancy	given publisher	items
		Capacity
	Capacity	infinite (average K topmost	finite
		positions more relevant)

Table 2 :

 2 Table of notation

		Metrics of interest as estimated by the model
	h ij	hit probability of publisher j at user i
	π ij	visibility of publisher j at user i
	N ij	occupancy of publisher j at user i
		Metrics of interest as obtained from measurements
	πij	measured visibility of j at i
	Ñij	measured occupancy of j at i
		Measurements
	I ij	number of impressions from publisher j at user i
		(counting repeated posts multiple times)
	Q ij	number of unique posts from publisher j at user i
	S i	number of snapshots collected by user i
	C j	number of unique posts created by publisher j
	G l	number of user-publisher-post tuples
		corresponding to user-publisher pairs in class l
	I l	number of impressions with user-publisher in class l

Table 3 :

 3 Summary of hypotheses test results

Table A .

 A 4: Lists of the publishers followed in the Italian experiment with their respective labels.

	Orientation Page URL	Publisher Name
	Right	NoiconSalviniUfficiale	Noi con Salvini
	Right	ilpopulista.it	Il Populista
	Right	ilGiornale	Il Giornale
	Right	legasalvinipremier	Lega -Salvini Premier
	Right	rivogliobologna	Lucia Borgonzoni
	Right	giorgiameloni.paginaufficiale	Giorgia Meloni
	Far-right	Fascisti-uniti-per-Litalia-411675765615435 Fascisti uniti per L'italia
	Far-right	Lotta-Studentesca-257153365332	Lotta Studentesca
	Far-right	OrdineFuturo	Ordine Futuro
	Far-right	ilprimatonatsionale	Il Primato Nazionale
	Far-right	ForzaNuovaPaginaUfficiale	Forza Nuova
	Far-right	casapounditalia	CasaPound Italia
	Far-right	RobertoFiorePaginaUfficiale	Roberto Fiore
	Left	Articolo1Modempro	Articolo UNO
	Left	sinistraitalianaSI	Sinistra Italiana
	Left	ilmanifesto	il manifesto
	Left	Possibile.it	Possibile
	Left	giuseppecivati	Giuseppe Civati
	Left	Laura-Boldrini-325228170920721	Laura Boldrini
	Center-left	Adessotiinformo	Adesso ti informo
	Center-left	matteorenzinews	Matteo Renzi News
	Center-left	Repubblica	la Repubblica
	Center-left	democratica	Democratica
	Center-left	matteorenziufficiale	Matteo Renzi
	Center-left	partitodemocratico.it	Partito Democratico
	M5S	news.m5s	M5S news
	M5S	WIlM5s	W IL M5S
	M5S	ilFattoQuotidiano	Il Fatto Quotidiano
	M5S	movimentocinquestelle	MoVimento 5 Stelle
	M5S	LuigiDiMaio	Luigi Di Maio
	M5S	beppegrillo.it	Beppe Grillo

https://github.com/EduardoHargreaves/Effect-of-the-OSN-on-the-elections

https://github.com/EduardoHargreaves/Effect-of-the-OSN-on-the-elections

Acknowledgements

This work was partially funded by the Brazilian-French project THANES (co-sponsored by FAPERJ and INRIA). D. Menasché was sponsored by a JCNE fellowship (FAPERJ), CNPq and in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior -Brasil (CAPES) -Finance Code 001. This work has also been supported by the French government, through the UCA JEDI "Investments in the Future" project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01.

Appendix A. List of publishers used in the experiment

Table A.4 contains a list of publishers followed in the Italian experiment with their respective orientations. During the experiments, the page entitled Fasciti uniti per L'italia was shutdown by Facebook and it was replaced by Lotta Studentesca.

Appendix B. Publishers' visibilities

In what follows we complement results presented in Section 3.2. Whereas in Section 3.2 we showed how occupancies varied as a function of the rate at which publishers create posts, in this appendix we focus on visibilities. Figure B.7 shows the visibility for the top publishers, at the topmost News Feed position (K = 1), under the six considered bots. It indicates, for instance, that even at the undecided bot, visibilities do not vary monotonically with respect to publishers' post creation rates. Figure B.8 considers the case K = 30. As expected, the visibilities increase as K grows from 1 to 30. Nonetheless, when K = 30 we still find some top publishers that have almost negligible visibility at a number of bots. In particular, eight out of the thirty top publishers have negligible visibility at the undecided bot. 2) (resp., ( 4)) corresponds to a measured occupancy of Ñij (resp., measured visibility of πij ). The two-class model has two parameters, while the number of parameters in the multi-class model is equal to the number of publishers times the number of bots (180 in the experiment). For this reason, the accuracy of the former is significantly lower than the later. with no friends, and they all followed the same group of 13 pages in a addition to a number of random pages. We adopted the multi-class approach (Section 5. [START_REF] Robert | A 61-millionperson experiment in social influence and political mobilization[END_REF] shows the occupancy for the top publishers, for K = 1, under the Facebook measurements, potential fairness, max-min fairness and proportional fairness. Note that the general trends of proportional fairness, potential delay fairness and max-min fairness are similar. Potential delay fairness tends to favor publishers that bots "like" more than the other fairness functions, while max-min tends to favor less. Facebook occupancies, in contrast, do not reflect any of the two considered fairness criteria. At the undecided bot, all fairness criteria yields the same occupancies and biases, reflecting the lack of preferences of this bot.

Figures D. 14 and D.15 show the biases of the considered fairness criteria using the Facebook as baseline, for K = 30 and K = 1. In both cases, we note

= 1 for all users, at the six bots. Potential delay fairness (green tringles) tends to favor "liked" publishers more than proportional fairness (blue squares).

that potential delay fairness (green triangles) tends to favor "liked" publishers more than proportional fairness (blue squares). When K = 1, Facebook tends to penalize the publishers that produced more posts at the undecided bot. Note also that there is a positive negative bias towards M5S posts at the undecided bot, meaning that Facebook allocated far more occupancy to M5S posts than the proposed methods would allocate.

Appendix E. Sensitivity analysis with respect of weights and News

Feed size

In Section 6.5 we assumed w

i ) correspond to publishers that a bot does not "like" (resp., "likes").

In (1) i from 1 to 10 to show the impact of the weights on the occupancies. We consider proportional fairness allocations, with K = 30. Figure E. [START_REF] Corbett-Davies | Algorithmic decision making and the cost of fairness[END_REF] shows that a ten-fold increase in w [START_REF] Abebe | Fair division via social comparison[END_REF] i , from 1 to 10, may lead to an up to two-fold increase in the occupancies of publishers that bots "like". This is the case, for instance, with "Il Fatto Quotidiano", which was classified as a M5S source, and which significantly benefited from the increase of w (1) i at the M5S-oriented bot. Next, we consider the impact of K on our results. We observe that our utility optimization framework produces occupancies that are directly proportional to K (see, for example, ( 24)), and the corresponding biases are independent from K. For this reason b (PropF) ij does not change between Figures E.17 , are substantially different for K = 1 and K = 30, with stronger biases for K = 1 (in agreement with the empirical findings reported in Section 3.2).