\section{Introduction}
  \label{sec:intro}

Algorithms that estimate relevance of online content to users
  are at the core of how social media platforms
  shape which information they show to their users.
A major part of the platforms' value comes from their
  ability to deliver content in a personalized way --
  by choosing which organic content from a user's connections
  or which promoted content from advertisers should be shown.
Popular platforms driven by relevance optimization algorithms
include Facebook, Instagram, Twitter and TikTok.
While the platforms do not publicly disclose in detail
  the specific algorithms and inputs to the algorithms they use
  to rank content by relevance,
  they acknowledge they do leverage
  sophisticated machine learning algorithms that harvest the extensive data they have on
  users~\cite{TweeterTimeline2017, FacebookTimeline, InstagramTimeline2021, TiktokTimeline}.

Social media platforms promise to provide a more
  meaningful experience for users, increasing
  user-engagement, and, therefore, platform revenue.
Platforms consider such optimization proprietary.
The combination of opaque algorithms that select what is shared
  with their operation at large scale
  has created increasing concern that
  relevance algorithms can produce outcomes that are harmful to individuals or society.
Examples of harms include biased or
  discriminatory ad targeting and delivery~\cite{Lecuyer2015, Ali2019a,Imana2021, Asplund2020},
  amplification of hateful content~\cite{WsjFBFilesHateful2021},
  political polarization~\cite{WsjFBPolarization2021, TwitterAlgAmplification, Ribeiro2020, Haroon2022, papakyriakopoulos2022algorithms},
  and promotion of addictive behavior in teens~\cite{WsjFBFilesTeens2021}.

Audits have shown that some of the hypothesized algorithmic harms
  are not merely theoretical by
  providing evidence of the side-effects of relevance optimization
  on how both organic content and promoted content (ads) are delivered.
For example, several studies have shown
  relevance optimization algorithms used in delivering ads can result
  in biased, and even discriminatory, outcomes in contexts such as
  politics~\cite{gelauff2020advertising, Ali2019b},
  housing~\cite{Ali2019a},
  and employment~\cite{Lambrecht2016, Ali2019a, Imana2021}.
For organic content, studies have looked at how the shift
  from a reverse-chronological news feed to one that is curated by a relevance algorithm
  distorts information to which users are exposed~\cite{Hargreaves2018, Bartley2021}.
An internal audit by Twitter also showed its algorithmic newsfeed
  amplifies organic political content non-uniformly across
  the political spectrum~\cite{TwitterAlgAmplification}.
These findings show
  greater transparency is needed for platforms to
  continue to innovate while staying
  accountable and building societal trust in their systems.

The importance of these risks has prompted
  policy or legal efforts aimed to
  increase transparency in social media platforms.
Of many such proposals~\cite{Pata2021, Sdaa2021, Aaa2019, Ajopta2021, Aia2021, dsa2021},
  the U.S.~Platform Accountability and Transparency Act (PATA~\cite{Pata2021, Persily2021})
  and the E.U.~Digital Services Act (DSA~\cite{dsa2021})
  are the most comprehensive, addressing broad algorithmic risks and platforms~\cite{Nonnecke2022}.
PATA has bipartisan support, but has not yet been debated in the U.S. Congress.
On the other hand, the E.U.~passed DSA and
  plans to start enforcement in 2024~\cite{DsaApproved, DsaPassed}.
Both proposals mandate that platforms
  make data available to vetted, external researchers,
  who will conduct studies
  to audit platforms' algorithms and evaluate
  their alignment with societal and legal
  expectations.
We call such proposals
  \emph{platform-supported auditing},
  and discuss how they extend existing auditing taxonomies
  in~\autoref{sec:overview_framework}.

A critical concern outlined in both legislative proposals is the need to protect
  the privacy of a platform's users \emph{and} its proprietary algorithms.
While a desirable policy goal,
  prior research has shown increasing transparency
  without violating the privacy of users and the business interests of
  platforms presents technical challenges~\cite{Bogen2020, metatech, austin2021race, TwitterAlgAmplification, Nonnecke2022, Andrus2021}.
Platforms such as Facebook have also cited
  privacy as a constraint on increasing their transparency
  efforts~\cite{FacebookBlockedNYU, Vermeulen2021}.
Until now, no actionable proposals
  have been put forth for how to address the privacy concerns
  and implement the auditing policies practically and at scale.

Our first contribution is to enumerate limitations of existing
  auditing methods for implementing
  platform-supported auditing at scale (\autoref{sec:problem_statement}).
We start with an overview of what DSA and PATA
  compel social media platforms to make available to external auditors,
  and the scope of the target platforms the proposals cover.
We then enumerate the significant limitations and
  non-generalizability of existing external auditing methods to study
  algorithmic harms on these platforms.
Specifically, although existing methods have been crucial to
  detecting how various social media platforms harm different demographic
  groups and our society at large, they
  do not generalize well to study multiple
  types of harms, demographic groups or platforms.

Our second contribution is to suggest that
  transparency of \emph{relevance estimators} is the key
  to enabling a generalizable and actionable framework
  for platform-supported auditing (\autoref{sec:why_relevance}).
Our proposal provides a plausible, practical approach to
  platform-supported auditing.
While the DSA and PATA require auditing legislatively,
  they do not specify a mechanism;
  our approach is the first to meet this need.
We show the importance of auditing relevance estimators
  by examining platforms' documentations that show
  they are the ``brains'' that shape
  delivery of every piece of  organic and promoted content
  on social media.
Despite being the core drivers,
  these algorithms are used across multiple social-media platforms
  with little transparency
  into their definitions of relevance or the specific inputs they use to optimize for it.
We survey prior audits that indirectly measured
  how use of relevance estimators' can result in harmful outcomes
  to show a means to directly query and audit these
  algorithms is the key to increasing transparency and providing a meaningful path to verifying alignment with societal and legal expectations.

Our third contribution is to show platform-supported auditing
  need not risk user privacy nor disclosure of platforms' business interests.
In \autoref{sec:platform_supported},
  we propose an auditing framework that protects against
  these risks.
\reviewfix{}
Our framework uses the rigorous definition of Differential Privacy (DP) to
  protect private information about \emph{audit participants} that may leak to the \emph{auditor}.
\reviewfix{}
It also protects the platform by not exposing details
  of the ranking algorithm---the platform shares with the auditor only
  the privatized scores of the relevance estimator, not proprietary source code, models, training data
  or weights.
At a high level (\autoref{fig:auditing_overview}),
  an auditor queries the algorithm with a trial content and a list of users
  whose sensitive demographic attributes are known to the auditor.
The platform then calculates how relevant the content is to each user,
  applies a differentially private mechanism to protect information
  that the relevance scores may leak about the users,
  and returns a distribution of noisy scores to the auditor.
Finally, the auditor uses the noisy scores
  and an applicable fairness metric
  to test for disparity
  between the distributions of relevance scores
  the algorithm assigns to different demographic groups.
The auditor chooses the specific type of content, attribute of users and metric of
  fairness to use
  depending on the specific scenario and the type of bias or
  harm they are studying.

We show that the privacy guarantees in our framework
  increase the number of samples required for an accurate audit
  by only a small constant factor (\autoref{sec:privacy_tradeoffs}).
We theoretically analyze the trade-off between
  guaranteeing privacy and the minimum sample size required for auditing
  in one concrete scenario -- bias in delivery of employment ads.
For the specific fairness metric we studied,
  we find that the noise that the platform adds
  to guarantee DP increases
  the required sample size by only approximately a factor of 4
  for reasonable auditing parameters,
  and with a strict upper bound of 6.34.
\reviewfix{}
Our contribution is application of standard DP algorithm to ad relevance estimators,
  a new application where DP enables viable privacy-utility trade-offs.

\reviewfix{}
Overall, our technical contributions show a path exists from
  the proposed legislation to a realizable auditing system.
While full implementation of our framework is future work
  and will require collaboration with a platform,
  conceptually demonstrating how to enable public oversight while
  protecting privacy is an
  important step forward.
\reviewfix{}
We summarize the limitations of our framework in \autoref{sec:model_limitations},
  but as the first proposed solution for implementing DSA- and PATA-like laws,
  it provides a useful starting point for exploring a new solution space.

\section{The Need for A Generalizable Auditing Framework}
   \label{sec:problem_statement}

 We discuss recent developments in policies
   that are pushing to increase transparency of
   digital platforms,
   the need for safeguards to protect privacy,
   and the insufficiency of existing auditing methods
   to practically implement these policies at scale.

 \subsection{Policy Pushes to Increase Transparency while Ensuring Privacy}
   \label{sec:policy_push}

As  social media platforms increasingly shape
  economic, social and political discourse,
  new policies are being proposed to regulate them.
We discuss two prominent pieces of legislation to mandate independent oversight
  and transparency research on platforms:
  Platform Accountability and Transparency Act (PATA~\cite{Pata2021, Persily2021}, proposed in the US)
  and Digital Services Act (DSA~\cite{dsa2021}, to be enforced in the EU starting in 2024).

PATA was proposed in December 2021
  to mandate platform support for independent
  research on algorithmic transparency~\cite{Pata2021}.
The proposal covers all large platforms
  with at least 25 million unique monthly users.
It mandates the platforms make
  data available to ``qualified researchers''
  who will study how
  platforms negatively impact individuals and society.
Only researchers and projects vetted
  and approved by the National Science Foundation (NSF)
  will be allowed to access platforms' data.

DSA was proposed in the EU in December 2020
  to regulate digital platforms and services~\cite{dsa2021}.
DSA covers a broader set
  of entities beyond large social media platforms,
  including online marketplaces and app stores.
While DSA has a broader in scope than PATA,
  it similarly mandates platforms to allow scrutiny
  of their algorithms by ``vetted researchers'' (Article 31~\cite{dsa2021}).
DSA was approved and passed as a law in July 2022~\cite{DsaApproved, DsaPassed}.

Both PATA and DSA recognize the need to
  ensure safeguards to protect privacy during platform auditing.
PATA emphasizes user privacy, with the necessity to
  ``establish reasonable privacy and cybersecurity safeguards''
   for user data, and to ensure the data platforms provide is
   ``proportionate to the needs of the [\ldots] researchers to
   complete the qualified research project''~\cite{Pata2021}.
DSA acknowledges platform's desire for ``protection of confidential information,
  in particular trade secrets''~\cite{dsa2021} when
  conducting audits.
\reviewfix{}
To mitigate the risks to users and platforms,
  both proposals require vetting auditors,
  their projects, and results before
  they are published.
Prior to our work, no actionable technical proposals put forth
  methods to implement
  such auditor
  access while protecting users' privacy
  and platforms' proprietary algorithms.

Platforms themselves also often cite their need to protect user privacy as a handicap for their transparency and self-policing capabilities~\cite{austin2021race, metatech}.
For example, Facebook has argued laws such as the EU's GDPR
  constrain their efforts for making data available to
  researchers~\cite{Vermeulen2021}.
In line with this argument,
  Facebook has constrained transparency efforts
  through actions such as
  providing data without sufficient granularity and accuracy
  needed to conduct meaningful audits through its Ad Archive APIs~\cite{Edelson2019, Vermeulen2021, papakyriakopoulos2022algorithms},
  and shutting down
  accounts used for transparency research by NYU's Ad
  Observatory project~\cite{FacebookBlockedNYU}.
In a partnership Facebook made with Social Science One,
  Facebook cited GDPR concerns and agreed to share data
 only using a differentially private mechanism~\cite{SocialScienceOne}.
Other social media platforms such as Twitter have also raised
  the challenges of sharing data for auditing for societal benefit while protecting
  the privacy of users~\cite{TwitterAlgAmplification}.

Given policymakers' and platforms' concern about privacy,
  implementing PATA and DSA requires solving
  methodological challenges to increasing transparency
  while safeguarding the privacy of users.
Our auditing framework (\autoref{sec:platform_supported})
  suggests that these policy requirements can be made concrete and viable
  with our proposed methodology.

\subsection{Existing External Auditing Methods are Insufficient}
  \label{sec:improve_limitations}

Until the present, societal and individual harms of social media algorithms have mostly been merely hypothesized or, in some cases, demonstrated by journalists and researchers through audits done independent of the platforms.

However, such fully external auditing methods are reaching hard limits
  in terms of what they can reliably and provably learn about the optimization algorithms' role; increasing public-interest researchers' calls for legislation and other transparency sources that can support their efforts~\cite{Ali2019a, Ali2019b, Imana2021, datta2018discrimination, Speicher2018, edelson2021universal, papakyriakopoulos2022algorithms}.
Specifically, the fully external auditing methods face fundamental challenges
  accounting for confounding variables and
  using proxies for sensitive attributes of interest.
As a result, they are difficult to generalize and
  have high cost.
In addition, they are susceptible to platform interference (\autoref{sec:beginning-to-favor}).
We next expand on these challenges.

\textbf{Confounding variables:}
The first challenge is controlling for temporal variables
  that confound measurements.
These confounding factors are present because
  platforms' algorithms operate in an environment that is influenced
  by actions of both users and the algorithms themselves.
These hidden variables make it difficult to attribute
  measured effects to decisions made by platforms' algorithms.

Auditing for bias in ad delivery provides an illustration of
  the challenge of accounting for confounding factors.
Several factors can affect the delivery of an ad,
  such as market competition from other ads, and differences in platform's use or interaction patterns among users from various demographics.
An external auditor must control for such factors to attribute differences in
  outcomes to the decisions made by relevance estimators.
Designing auditing methods with such controls in place,
  however, is a laborious process that requires careful reasoning and creative hacks.
It took many years of research effort to get from
  Sweeney's study that gave the first evidence of
  biased ad delivery in 2013~\cite{Sweeney2013}
  to Ali and Sapiezynski et al.'s study that attributed such bias to
  the role the platform's algorithms play in 2019~\cite{Ali2019a}, and the Imana et al.'s 2021 study~\cite{Imana2021} that established that the algorithms are not merely biased, but, in fact, discriminatory.

Similar factors can confound measurements of potential harms in personalized organic content delivery.
For example, a recent study on Twitter used sock-puppet accounts to compare
  their reverse-chronological and personalized timelines,
  and showed Twitter's algorithms distort
  information that users get exposed to~\cite{Bartley2021}.
However,
  the study's authors identify the duration sock-puppet accounts stay logged-in for and the timeline scrolling capabilities as potential confounding
  factors that could possibly alter the study's conclusions~\cite{Bartley2021}.
\reviewfix{}
Even Twitter's internal audit of disparate algorithmic amplification
  of political content
   shows the limits of current methods~\cite{TwitterAlgAmplification}.
The study showed that their metric of amplification,
  which is based on number of impressions,
  demonstrates the presence of bias on Twitter,
  but that confounding factors prevent any conclusions about potential sources of this bias.

These examples demonstrate the limits of impression-based
  measurements for isolating algorithmic effects.
To increase transparency
  beyond what we have already learned through existing
  external auditing methods,
  a new level of access is needed for auditors
  (\autoref{sec:why_relevance}).

  \textbf{Reliance on proxies:}
A second challenge is the need for an auditor
  to use proxies for demographic attributes that platforms do not
  collect or report.
Auditors may be interested in studying
  the impact of a specific demographic feature on algorithmic personalization,
  but often conduct external audits
  by posing as a regular user or advertiser.
Operating as a normal user or advertiser
  is relatively easy and allows audits without a platform
  support or knowledge,
  but it also means the auditor can only use
  data points that a platform makes available to any user.
For example, in the context of ad delivery,
  some platforms may not report ad impression rates broken down
  by attributes such as gender, race or political affiliation.
Past audits have worked around this challenge by using
  proxies for demographic attributes that platforms do not report~\cite{Ali2019a, Ali2019b, Imana2021}.
However, such workarounds introduce measurement errors~\cite{Imana2021}
  and significantly limit the ability to vary the attributes.

 \textbf{Lack of generalizability:}
Another challenge is that existing external auditing methods are often
  not generalizable beyond
  the limited context which they were originally designed for.
For example,
  the study described above that built upon Ali and Sapiezynski et al.'s work
  added new controls for job qualifications across genders~\cite{Imana2021}.
The focus on job ads and gender makes the method
  not easily generalizable to other types of ads (Example: insurance ads) and
  demographic attributes (Example: race).
This lack of generalizability is also directly related to the limitations
  of confounding variables and use of proxies discussed above.
In order to work around these limitations,
  researchers often use one-off hacks that are
  experiment- or platform-specific.
Examples include use of random phone
  numbers to generate a random custom ad audience~\cite{Ali2019a},
  and use of public data sources such as
  voter data to build audiences with a specific
  demographic make up~\cite{Speicher2018, Ali2019a, Ali2019b}.
Such public data sources are extremely limited and subject individuals to participation in experiments without their knowledge.

Crowdsourced audits that rely on browser extensions
  do not generalize beyond desktop versions of platforms,
  a limitation given that the use of most social media is now primarily mobile-first.
For example, 98.3\% of Facebook users
  access the site using a phone app~\cite{GlobalSocialDataReport}.
Furthermore, such extensions need to be customized
  for each platform, and need to be regularly
  maintained to adapt to changes on platforms' websites.

\textbf{Cost of auditing:}
Existing external auditing methods can also incur high
  cost  in terms of time and money.
For ad delivery,
  the state-of-the-art method for auditing involves
  registering as an advertiser,
  running real ads,
  and measuring how they are delivered in real-time
  while controlling for hidden temporal factors~\cite{Ali2019a, Imana2021}.
The monetary cost for this procedure
  can easily accumulate with repeated
  assessments of a platform
  to confirm results over time,
  increase statistical confidence,
  or vary study parameters.
In addition, controlling for confounding factors
  and proxies for measuring delivery along sensitive attributes
  requires time for study design.

For studies of personalization of organic content,
  creation of sock-puppet accounts is expensive because
  it often requires separate hardware and phone number
  verification, and it takes time and effort to make a
  sock-puppet's account activity ``realistic".

These challenges motivate our approach:
   by using platform-supported auditing centered on relevance estimators,
   we directly focus on platform choices,
   side-stepping confounding variables and proxies.
Explicit platform support also avoids platform interference and minimizes cost,
  provided platforms collaborate, as we explore next.

\subsection{Platforms Beginning to Favor Platform-supported Audits?}
  \label{sec:beginning-to-favor}

Platform-supported audits, of course, require support from the platform,
  so we next look at evolution of the platforms' responses to requests for auditing.

\textbf{Pushback from platforms:}
Traditionally, a major challenge for external auditing methods has been
  pushback from platforms, often citing privacy concerns or violation of their terms of service.

External audits collect data either through interfaces
  the platforms provide or by using tools such as
  customized scrapers and browser extensions.
Regular website changes complicate long-term maintenance of
   tools that track platforms~\cite{Bartley2021}.
Facebook has resisted external auditing by explicitly blocking
   accounts used to conduct audits~\cite{FacebookBlockedNYU},
   tweaking its APIs to break auditing tools~\cite{FacebookPropublicaBlocked},
   and threatening legal actions against researchers who scrape
   data from its platform~\cite{FacebookBlockedNYULegal}.

\textbf{A change of heart?}
Recently platforms have released data or provided APIs to researchers,
  suggesting platforms themselves may be interested  in some form of platform-supported auditing.
Platform support allows them to manage auditing,
  and perhaps preempt adversarial black-box audits, lawsuits, and explicit regulation.

In a historic settlement with the US Department of Justice (DOJ),
  Facebook announced in June 2022 that it will work towards de-biasing its algorithms
  used for delivering job, housing and credit ads~\cite{FacebookvsHUD, FacebookvsHUD2}.
The settlement requires Facebook to work with a vetted external
  entity to verify the changes implemented to its algorithms are compliant with the non-discrimination goals set by the settlement,
  a compliance structure similar to platform-supported
  methods proposed in PATA and DSA.

Platforms are also establishing programs to provide vetted researchers with
  access to their data and algorithms.
In July 2022, YouTube announced ``YouTube Researcher Program'' (YRP),
  which promises to provide academic researchers with data, tools, and support
  for studying YouTube and its impact~\cite{YoutubeResearchProg}.
A year earlier,
  Facebook announced the ``Facebook Open Research \& Transparency'' (FORT) initiative,
 %
 %
 %
that provides privacy-protected datasets and APIs for researchers, so that ``the public can learn more about Facebook's impact on the world from credible and independent academic sources"~\cite{FacebookFORT}.
In 2021, Twitter held an algorithmic bias bounty challenge, through which Twitter made the code for their image salience algorithm suspected of bias~\cite{Yee2021image} available to researchers~\cite{TwitterBiasBounty}.

These steps are promising responses
  that approach legislative requirements,
  suggesting
  platforms are considering
  explicit support of methods that increase transparency of their influence on individuals and society.

However, for both YRP and FORT,
  current data available to researchers
  through the APIs is limited to public data corpora,
  such as public videos, pages, posts and comments~\cite{YoutubeResearchProg, FacebookFORT}.
While such access is an important first
  step for helping understanding how the platforms shape
  public discourse,
  we argue in~\autoref{sec:why_relevance} that it is also
  important for platforms to provide a means to studying
  their relevance estimator algorithms.
We hope our work encourages platforms to expand
  these first efforts to allow researchers to study
  how their algorithms shape access to content.

\section{Relevance Estimators are the Key to Increasing Transparency}
  \label{sec:why_relevance}

In this section, we show transparency of relevance estimators
  is the key to enabling generalizable
  auditing of platforms for potential harms.
To support this claim,
  we first document the importance of relevance
  estimators for content prioritization.
We then survey studies that have shown harmful outcomes that result
  from use of these algorithms.

\subsection{Relevance Estimators: ``Brains'' of Social Media Platforms}
  \label{sec:relevance_brain}

Relevance estimators
  are the main drivers that shape every piece of
  content shown to users.
Prior work and platforms' documentation show this importance
  and that these algorithms are opaque to external auditors.

\begin{figure}
  \centering
  \includegraphics[width=0.75\columnwidth]{FIG/relevance-narrow.pdf}
    \caption{Social media platforms use relevance estimators to score
     every content using many factors as input, only some of which are publicly documented.}
  \label{fig:relevance_score}
\end{figure}

Given the vast amount of potential content shared on social media,
    relevance estimators have become responsible for selecting which
    content is shown on a user's timeline and in what order, and which is omitted or deprioritized.
For example, for organic content, it maybe selecting and ranking posts from
    a user's friends or pages they follow, or for promoted content,
    it may be running auctions for ads that are currently competing for a particular user's attention.
Platforms may mix both organic posts
    and ads in the content stream.
Facebook's algorithmic newsfeed dates back to 2007~\cite{FacebookNewsFeedAge},
  and Twitter and Instagram deployed such personalization in 2016~\cite{AlgorithmTimeline2016}.
Before deploying these algorithms, the platforms
  used ordering that was mostly reverse chronological.

For organic content,
  these algorithms ultimately boil down to \emph{relevance scores}
  that will determine the selection and order of
  content shown at the top of users' news-feed.
For example,
  Facebook makes a number of predictions about how likely
  a user is to engage with posts,
  and will ``add these predictions up into a \emph{relevancy score}''
   to order the posts~\cite{FacebookTimeline}.
Instagram follows a similar approach~\cite{InstagramTimeline2021}.
Similarly, Twitter uses a number of ``consolidated signals to develop a
  \emph{relevancy score}''~\cite{TweeterTimeline2017}
  that it uses to determine which tweets to show on top of the feed.
LinkedIn also uses an algorithm that
 ``\emph{scores} tens of thousands of posts and ranks the most
  \emph{relevant} at the top of the feed''~\cite{LinkedInTimeline2019}.
TikTok mixes content from both followed accounts and others
  using algorithms that optimize for
  ``effective relevance'' as a ``secret sauce''~\cite{TiktokRelevance}.

Relevance estimators are used in ad auctions in addition to organic content.
Ads are selected using auctions;
  these auctions consider relevance as a factor predictive of user engagement.
These predictions are combined with other factors,
  such as the bid and budget the advertiser set for the ad,
  to determine the auction winner.
Different platforms use different terminologies to refer to these predictions.
For example, Facebook, LinkedIn and Twitter refer to them as
  ``Estimated action rates''~\cite{FacebookAdAuction},
  ``Relevancy scores''~\cite{LinkedInAdAuction},
  and ``Quality scores''~\cite{TwitterAdAuction},
  respectively.
But they all have very similar purposes in that they are applied as modifiers to bids
  to determine which ad wins an auction.
Therefore,
  an ad with the highest bid may not
  win an auction if it is given a low relevance score by the algorithmic prediction.

Platforms provide little transparency into optimization algorithms,
  neither for organic nor promoted content.
As summarized in \autoref{fig:relevance_score},
  publicly available documentation gives a high-level description
  that platforms use information about
  the content itself,
  the author of the content,
  and user's profile data.
However, the specific types of algorithms and inputs to those algorithms
  are not disclosed.
Facebook, Instagram and LinkedIn
  use thousands of factors to estimate relevance of
  posts~\cite{FacebookTimeline, InstagramTimeline2021, LinkedInTimeline2019}.
Similarly, Twitter's documentation shows they use advanced
  machine learning algorithms to predict relevance,
  where the ``list of considered features and their varied
  interactions keeps growing''~\cite{TweeterTimeline2017}.

The importance of relevance estimators to organic content and ad delivery
  lead us to place them at the center of
  our mechanism for external auditing in \autoref{sec:platform_supported}.

\subsection{Relevance Estimators Can Cause Various Forms of Algorithmic Harms}
  \label{sec:relevance_harms}

Prior studies by researchers and journalists have raised
 concerns about how relevance estimators on social media platforms
 can lead to potentially harmful outcomes.
We next show examples of audits
  where controlled experiments show
  biased or harmful outcomes that result
  from platform choices.

Ad delivery is an area where there is substantial evidence
  for relevance optimization resulting in bias and discrimination.
Starting with Sweeney's empirical study in 2013,
  researchers hypothesized that platform-driven choices
  result in discriminatory ad delivery across demographic
  groups~\cite{Sweeney2013}.
In 2019, this hypothesis was confirmed by Ali and Sapiezynski et al.~by showing Facebook's relevance algorithms skewed delivery
  of job and housing ads by gender and race,
  even when an advertiser targets a gender- and race- balanced
  audience~\cite{Ali2019a}.
A subsequent study by Imana et al.~controlled for job
  qualifications, a legally excusable source of skew, to demonstrate
  the role of Facebook's relevance algorithms may be violating
  U.S. anti-discrimination laws~\cite{Imana2021}.
These examples provide evidence
  that opaque optimization algorithms
  result in discriminatory delivery of opportunity ads
  for certain demographic groups.

Facebook's academic work~\cite{do2022online} and Facebook's public statements~\cite{FacebookvsHUD} in response to the recent settlement with the US Department of Justice~\cite{FacebookvsHUD2} both also acknowledge the need to ensure its algorithms for opportunity ads are not biased. Both of these serve as additional evidence that harms
  of relevance estimators that prior studies
  pointed out are well grounded.

Delivery of organic content is another area
  where past audits have found evidence for bias.
Twitter conducted an internal audit on its algorithms
  used to curate timelines, and found that its platform amplifies
  right-leaning political tweets more than moderate ones~\cite{TwitterAlgAmplification}.
The study suggests the difference may be attributable to Twitter's ranking models
  assigning higher relevance scores to the right-leaning tweets.
Another external audit on Twitter by Bartley et al.~also did a more general comparison
  of algorithmic and reverse chronological timelines on Twitter and
  showed the algorithmic timeline distorts information that users are shown~\cite{Bartley2021}.

 Besides such internal and external audits,
   investigations done by journalists have corroborated
   that the potential harms of algorithms used by platforms
   are not merely theoretical.
A recent prominent example is ``the Facebook files'', an investigation done by
  Wall Street Journal into leaked internal Facebook documents.
Among other findings, the investigation showed how changes in 2018
  to make ``the platform healthier'' by focusing on
  relevance and engagement caused its algorithms to promote
  objectionable content~\cite{WsjFacbookFiles2021}.
They report cases where Facebook's algorithms
  have led teenagers to harmful content~\cite{WsjFBFilesTeens2021} and
  spread hateful posts~\cite{WsjFBFilesHateful2021}.

These findings underscore the need for public oversight.
The goal of such oversight will be to ensure relevance estimators
  that optimize for business objectives take societal interests into account.
Platform-supported auditing is an important part of confirming progress towards
  this goal.

\section{Privacy-preserving Platform-Supported Auditing}
  \label{sec:platform_supported}

We next describe our approach to platform-supported auditing
  and how it addresses risks to the privacy of users and business
  interests of platforms.

\begin{figure}
  \centering
  \includegraphics[width=0.75\columnwidth]{FIG/auditing.pdf}
    \caption{Privacy-preserving platform-supported auditing framework for evaluating fairness of relevance estimators.}
  \label{fig:auditing_overview}
\end{figure}

\subsection{Overview and Context}
  \label{sec:overview_framework}

Our proposal for \emph{platform-supported auditing},
  shown in~\autoref{fig:auditing_overview}, has four high-level steps:
  \reviewfix{}
  (1) an auditor selects a trial content and an audience
  whose demographic attributes are known to the auditor,
  and uploads the content and sub-audience for each demographic group separately;
  (2) for each group, the platform calculates relevance scores that estimate
  how relevant the content is to each user in the group;
  (3) the platform then applies a privacy mechanism
  and returns to the auditor a noisy distribution of the scores
  for each demographic group;
  (4) finally, the auditor evaluates the fairness of the scores assigned
  to different demographic groups using an applicable metric of fairness.
We discuss each of these steps in more detail in~\autoref{sec:steps_details}.

\reviewfix{}
Our platform-supported auditing framework
  is a new category
  that extends the classical Sandvig taxonomy of auditing~\cite{Sandvig2014}.
Their taxonomy defines five types of audits:
  source code audit, survey-based audit, scraping audit,
  and crowdsourced audit.
Other types of audits recently proposed include
  \emph{everyday algorithm audits}~\cite{Shen2021} and \emph{cooperative audits}~\cite{wilson2021building}.
Our platform-supported auditing defines a new type of audit because,
  unlike methods that use only features or APIs publicly available to regular users and advertisers,
   it requires a privileged and auditor-specific interface.
And unlike methods that require access to
  platforms' proprietary source code,
  it only requires query-level access to the output of their algorithms.
We further discuss how platform-supported auditing
  compares to the existing taxonomy of methods in~\autoref{sec:related_work}.

\subsection{Privacy and Business Risks of Platform-Supported Auditing}
  \label{sec:why_privacy}

\reviewfix{}

Our approach is designed to minimize risks to the privacy
  of platform users and to platform's proprietary information.
As discussed in~\autoref{sec:policy_push},
  protecting against these risks is an important goal
  of PATA and DSA,
  and is also a concern that platforms identify as
  a constraint to enabling transparency and auditability.
We next discuss the potential risks of
  providing query access to relevance estimators and
  the need for ensuring rigorous privacy protection when their outputs are shared.

 Relevance scores may leak private user data
   based on which they are calculated.
As discussed in \autoref{sec:relevance_brain},
  platforms calculate relevance scores based on
  users' personal profile data and
  their historical engagements with the platform.
The relevance of each particular content to each user
  may reveal information about the user that
  the auditor otherwise would not know.
For example,
  when a platform finds content about
  disability support or insurance highly relevant to a
  given user, that result suggests the user may
  be disabled or is caring for a disabled person.
Similar real-life examples from other contexts include
  Target's predictive algorithms for sending relevant coupons
  leaking a teenager's pregnancy~\cite{TargetPregnancy},
  and Facebook's ``People You May Know''
  feature that suggest connections Facebook deems relevant
  revealing private information about a user~\cite{FBPeopleYouMayKnow}.
Even if relevance scores are aggregated in some fashion,
  prior work has shown similar aggregate outputs
  of personalization systems,
  combined with auxiliary information about users
  can leak private information~\cite{Calandrino2011, Weinsberg2012, Beigi2020}.
Therefore, our auditing method must limit the
  potential to make such inferences.

In~\autoref{sec:add_dp_noise},
  we show how our framework protects the privacy of users,
  when privacy protection is defined as ensuring a Differential Privacy (DP)
  guarantee on any \emph{data that is shared with the auditor}.
\reviewfix{}
Protection from other privacy violations,
  such as how the platform itself may violate privacy of users
  through training and deployment of personalization algorithms,
  is outside the scope of our framework.
DP is the current gold standard
  for protecting privacy of individuals,
  while providing useful statistical computations on their data~\cite{Dwork2006}.
DP provides a rigorous guarantee
  that each individual subject's participation in the audit
  has negligible impact on their privacy.
A differentially-private mechanism will specifically protect
 \emph{the privacy of the users participating in the audit},
 while providing aggregate information
 about the relevant estimator, which
 the auditor can use to asses fairness.

In addition to risks to platform users,
  platforms themselves would like
  to minimize what details of their algorithms they share.
Our framework minimizes information it requires the platforms to share about their algorithms and data
  by providing only query (rather than source-code) access to auditors,
  asking to share only aggregate relevance metrics,
  while preserving the confidentiality of the source code, how those metrics are computed and
  what inputs and training data they use.

\subsection{Steps of Platform-Supported Auditing}
  \label{sec:steps_details}

We next describe each of the four steps of platform-supported
  auditing in detail.
\subsubsection{Auditor Uploads Content and Audience}
  \label{sec:auditor_uploads}

The auditor first will select a trial content
  and a customized audience.
The content is specific to the platform under study.
  For example, a job ad for LinkedIn or a political Tweet for Twitter.
The audience is a list of users whose demographic attributes are known
  to the auditor.
The auditor selects the content and demographics based on
  the specific platform and the type of algorithmic harm
  they are studying.
The auditor then uploads the content and a
  sub-audience for each demographic group to the platform.
Major platforms already have an infrastructure
  for advertisers to upload audience and content which,
  with some modifications,
  can be used for auditing purposes.

The type of content and the demographic make up of the users depends
  on what type of harm or bias the auditor is interested in studying.
For example, one may wish to study whether LinkedIn's ad delivery algorithms
 deliver STEM job ads in a biased way that reflects
  historical under-representation of women in the field.
To perform the study,
  the auditor may use a STEM job ad as the content,
  and a sample of men and women as the audience.
The auditor will query the platform using the audience
  from each demographic group
  to evaluate whether the platforms' relevance estimators
  assign higher scores to men compared to women.

The auditor will specify the audience by uploading a custom
  list of specific people whose demographic attributes are
  known to the auditor.
One way the auditor can build such an audience is by recruiting
  volunteers for the study.
Recruiting volunteers has two main advantages over prior methods
  that use publicly available datasets, such as voter data~\cite{Ali2019a, Ali2019b, Imana2021}.
First, each participant gets the opportunity to consent the use
  of their data for auditing purposes.
 Second, participants can provide additional attributes that
  may not be present in public data but could be useful for auditing.
An example is a job qualification attribute that is useful for auditing
  delivery of employment ads.
\reviewfix{}
Existing recent studies such as The Markup's Citizen Browser~\cite{CitizenBrowser}
  and Mozilla's Rally~\cite{MozillaRally} show that users
  are willing to opt-in and provide data to reputable efforts that aim to hold platforms accountable.
 \reviewfix{}
In addition to such external efforts, platforms themselves can provide support for
  recruiting users~\cite{metatech, LinkedInSelfID}.

Having the auditor specify a custom audience is also
  advantageous over letting the platform itself pick an audience.
It helps protect the privacy of users since it does not require platforms,
  nor gives them the excuse,
  to collect sensitive demographic attributes.
This advantage also addresses the challenges around
  collecting and securing sensitive attributes of users
  that companies often identify as
  one of the major obstacles
  to auditing for fairness~\cite{Bogen2020, Andrus2021, metatech}.

Popular social media platforms
  have an infrastructure for advertisers to upload
  custom audiences.
These existing features are currently designed for use by
  advertisers to run advertisement campaigns
  that retarget their customers.
An advertiser may upload information such as
  names, email addresses and phone numbers
  of their customers and the platform tries to match
  this information with user profiles on the platform.

These existing features can serve as a starting point
  for platforms to build a similar interface that can be
  used for platform-supported auditing.
In the existing custom-audience features,
  not all people in the audience
  may match to user profiles on the platform.

In a prior work,
  we have found that such partial matches can be a
  source of error when using custom audiences for auditing~\cite{Imana2021}.

A possible modification for supporting accurate auditing is for the
  platform to allow the auditor to upload unique identifiers
  (for example: Facebook usernames)
  for the accounts of people that are participating in the audit.
The auditor can collect these identifiers when recruiting
  volunteers who will participate in the study.

\subsubsection{Platform Calculates Relevance Scores}

The platform then calculates how relevant the content is to each user
  in the custom audience.
Relevance estimation on the platform boils down to a~\emph{relevance score}
  for each user,
  which is the platform's prediction of how likely the user is to engage
  with the content.
The platform will not report the raw scores to the auditor as they may reveal
  private information about its users' past engagement history.
Instead, the platform builds statistics that
  summarizes the distribution of the scores (For example, a histogram or a CDF),
  and adds privacy protections (discussed in \autoref{sec:add_dp_noise}),
  before returning the statistics to the auditor.

Platforms use many factors for estimating relevance
  but not all are applicable for auditing context.
For example, during a normal usage of the platform,
  the estimators may use as inputs factors such as
  what time of the day it is and
  for how long a user has been logged in~\cite{FacebookTimeline}.
For such temporal variables that are only
  applicable in the context of a user
  browsing the site,
  the platform must keep them constant for all users in the audience.
This control allows the auditor to evaluate
  bias in the relevance estimators that may arise from the historical
  data that the platform has about users and not
  from temporal factors.

\subsubsection{Platform Applies Privacy Mechanism and Returns DP-protected Scores}
  \label{sec:add_dp_noise}

The platform then applies a differentially private mechanism
  to the statistics of relevance scores calculated
  and returns the noisy statistics to the auditor.
The mechanism will provide a rigorous guarantee that
  the data the auditor gets
  ensures differential privacy for
  individuals participating in the audit.
We use the following definition of DP, where
  neighboring databases are defined as differing in one person $u$'s data:
  $D_1 = D$ and $D_2 = D \cup \{u\}$ for some database $D$.
\begin{definition}[$\epsilon$-Differential Privacy\cite{Dwork2006}]\label{def:dp}
Given $\epsilon > 0$, a randomized mechanism $M$ is $\epsilon$-differentially private if
  for any two neighboring databases $D_1$ and $D_2$,
  and for any subset $S \in R$ of outputs,
$$Pr[M(D_1) \in S] \le e^{\epsilon} * Pr[M(D_2) \in S],$$
where the probability is taken over the random coin tosses of $M$.
\end{definition}

Auditors can approximate tests for group-fairness metrics using a
  binned histogram of relevance scores without access to
  individual scores.
One method to share the binned histogram while preserving privacy is
  using the Laplace Mechanism~\cite{Dwork2006}.
The platform can independently add noise drawn from the
  Laplace distribution to each of the bins
  in the histogram.
Since presence or absence of a single user changes
  each bin's count by at most one,
  adding noise from Laplace distribution $Lap(1/\epsilon)$
  independently to each bin ensures the mechanism
  is $\epsilon-$differentially private~\cite{Dwork2006}.
The platform then returns the noisy histogram counts back
  to the auditor.

Any arbitrary post-processing to
   output of a differentially private mechanism
   does not reverse the privacy protection.
Therefore, auditor can use the noisy scores to apply
   any post-processing computations to test for fairness without
   incurring additional privacy cost to the platform or its users.

\subsubsection{Auditor Evaluates Fairness of Relevance Scores}
  \label{sec:eval_fairness}

Finally, the auditor uses the noisy distribution of scores
  to test whether there is a disparity between the relevance
  scores the algorithm assigns to different demographic groups.
The specific metric of fairness depends on the type of algorithmic
  bias the auditor is interested in testing for.
For example,
  to study bias in the delivery of employment ads,
  the auditor may use Equality of Opportunity as a metric
  for fairness since the definition takes qualification
  of people into account, which is a relevant factor for the context
  of employment~\cite{Hardt2016}.
We further explore this scenario in our theoretical result in~\autoref{sec:privacy_tradeoffs}.

\subsection{Trust Model and Limitations}
	\label{sec:model_limitations}

We next discuss the trust model we use
  to evaluate the privacy and business interest risks of our approach.
The efficiency our approach assumes a legal framework in
  which both the platforms and auditors work in good faith,
  or potential tests for non-cooperation.

\textbf{Platforms:} One major assumption of our framework is
  that the platform will truthfully collaborate
  with auditors and ensure audits are done
  accurately and effectively.
The platform must provide auditors access to
  the same algorithms that are used in production,
  truthfully executing them on the audience the auditors upload
  and reporting relevance scores accurately (modulo privacy modifications).
This assumption was not stated in prior auditing methods
  that do not use a platform's support.
\reviewfix{}
Even for such methods,
  platforms have the means to know they are being
  audited as the audiences and methodologies auditors typically used
  are publicly documented.
Examples included North Carolina's voter datasets used
  as data source for demographic attributes~\cite{Speicher2018},
  Facebook ad accounts used to audit ad delivery~\cite{Ali2019a, Ali2019b, Imana2021},
  and browser extensions used
  for collecting data from Facebook~\cite{NYUAdobservatory, CitizenBrowser}.

\reviewfix{}
Assuming the platform truthfully collaborates with auditors is a strong assumption,
  but there are four reasons we think it is appropriate.
First,
  the consequences of non-compliance are significant when
  auditing is part of an official legal framework,
  as it would be in the context of a DSA- or PATA-like law
  or a legal settlement, such as Facebook's settlement with the US Department of Justice~\cite{FacebookvsHUD}.
For example,
  Volkswagen faced significant legal and financial
  repercussions as a result of their violation of emissions regulations~\cite{Jung2019}.

\reviewfix{}
Second, platforms also have the incentive to minimize
  inadvertent errors in order to avoid tarnishing their public image
  and potential legal liability.
Two cases, both involving Facebook,
  serve as an example of this.
In the first case,
  Facebook made inadvertent errors in sharing data
  to external researchers as part of its Social Science
  One program~\cite{FBSocialOneData}.
This preventable error undermined academic work
  that was based on the data~\cite{FBSocialOneData},
  tarnishing Facebook's efforts to be a leader in increasing transparency.
In the second case,
  Facebook mistakenly inflated potential reach estimates
  for ads,
  and is currently being sued as a result~\cite{FBInflatedAdMetrics}.

Third, simply formalizing auditing and involving two
  parties often adds sufficient oversight to discourage
  abuse.
For example,
  corporate financial accounting is not immune to fraud,
  but the levels of non-compliance are small enough that
  it is a very useful and powerful tool.

Finally,
  as discussed in~\autoref{sec:beginning-to-favor},
  there is evidence that the platforms themselves may be moving
  towards supporting audits through giving external
  researchers privileged access to their data and algorithms.

\reviewfix{}
\textbf{Auditors:}
The platform must also trust researchers
  doing the independent audit.
One risk for abuse is misuse of the auditing interface to harm
  a platform's business.
Both the DSA and PATA provide rules to ensure
  only vetted researchers
  will be allowed to perform audits on social
  media platforms~\cite{Pata2021, dsa2021}.
In both proposals, an assigned regulatory body will screen
  researchers and their projects before they are allowed to audit
  a platform’s system or data~\cite{Pata2021, dsa2021}.
Platform-initiated transparency efforts such as Facebook's FORT, Social Science One, and YouTube's Researcher Program also all have approaches for vetting researchers~\cite{SocialScienceOne, FacebookFORT, YoutubeResearchProg}.
Such screening processes will minimize the risk
  that comes from malicious auditors, and the platforms' implementations show that the platforms themselves believe this risk can be overcome.

\reviewfix{}
\reviewfix{}
Another risk is misuse of sensitive data that auditors collect
  from users who are participating in an audit. %
Similar to the risk for platforms discussed above,
  having only vetted researchers conduct audits
  helps reduce the risk for users.
In addition,
  under our proposed framework,
  users would be voluntarily providing their data,
  unlike prior methods that used public voter data.
In these prior methods, users were not even aware their data was being used for experiments.

\section{Sample Size Required for Auditing Relevance Estimators with Privacy}
  \label{sec:privacy_tradeoffs}

We next present the key technical result of this paper by applying our framework to one
  use-case: a study of discrimination in employment ad delivery.
We show that the addition of differential privacy
  to the auditing pipeline does not prevent an auditor from achieving
  the same statistical confidence as without privacy protections,
  provided the sample audience is increased by a small constant factor.
This result supports our claim that
  it is feasible to both audit for fairness
  \emph{and} protect user privacy and platforms' business interests.

\subsection{Setup and Assumptions: Bias in Delivery of Employment Ads}
Auditing social media platforms for fairness while preserving privacy
 is a goal that desirable in multiple scenarios.
We study one scenario: assessing discrimination in delivery of employment ads.
Our problem formulation is general,
  although specific scenarios
  place additional requirements,
  like the role of qualifications in job advertisements.
Extending our approach to other types of ads
  may require identifying similar factors reflecting allowable preferences.

We consider the case where an auditor wishes to confirm
  delivery of job ads is unbiased relative to a factor
  such as gender or race.
To evaluate this question,
  the auditor will examine a platform's relevance estimator
  for different groups with specific demographic attributes.
This scenario is motivated by prior third-party audits that have
  indirectly measured the role of relevance optimization in
  biased job ad delivery~\cite{Ali2019a, Imana2021}.

We first introduce formal notations for the scenario.
Let  $X$ represent a set of all users on a platform and
  let $A$ be the range of values for a sensitive attribute
  (For example, $A$ =  $\{$black, white, ...$\}$ for race).
Let $Q=\{0,1\}$ represent binary options for qualification of a user
  to a given job ad (1 if the user is qualified, 0 -- otherwise).
Let $R_j(x)$ be the relevance estimator that calculates the
  relevance score of the job ad $j$ to a given user $x \in X$.
We assume a specific ad $j$ and omit the subscript $j$ throughout.
And let $Y$ be a small finite set of discrete relevance scores
(we describe how to extend $Y$ to the continuous case at the end
  of this section).

In practice, the external auditor cannot have access to a complete list of all of the platform's
  users ($X$), so the auditor recruits a sample ($S$) of users to perform the audit.
The auditor uses a random sample set
  $S = \{(x_1, a_1, q_1), (x_2, a_2, q_2), ...., (x_n, a_n, q_n) \}$
  drawn i.i.d.~from $X$.
In that case each subset $S_{a,q}$ is also i.i.d.~in $X_{a,q}$,
  where $S_{a,q}$ and $X_{a,q}$ represent subsets with given values of $a$ and $q$.
We discuss implications of this assumption at the end of this section.

Following the steps in \autoref{fig:auditing_overview},
 the auditor first queries the platform's relevance estimator
  using each subset $S_a$ and $j$ (step 1).
The platform then applies $R$ to every user in $S_a$ (step 2)
  and builds a histogram $H$ of the scores,
  grouped by possible range of relevance scores in $Y$.
It then independently adds noise drawn with a
  Laplacian distribution $Lap(\frac{1}{\epsilon})$ to each of the bins in $H$,
  where $\epsilon$ represents the level of differential privacy desired.
The platform returns the noisy histogram counts back
  to the auditor (step 3).

Finally, the auditor tests for fairness of the scores assigned
  using Equality of Opportunity as a definition of fairness (step 4).
Equality of Opportunity is an established fairness notion in the algorithmic fairness literature, and is applicable to job ads
  as it allows for taking into account the qualification of users~\cite{Hardt2016}.

 \begin{definition}[derived from Equality of Opportunity~\cite{Hardt2016}]\label{def:eoo_def}
A relevance estimator function $R$ satisfies equality of opportunity:
  \begin{align*}
  & Pr_{(x, a', q) \sim\ X}[R(x) = y | a' = a \land q = 1] \\
  &= Pr_{(x, a', q) \sim\ X}[R(x) = y | q = 1]~\textrm{for all}~a \in A~\textrm{and}~y \in Y,
  \end{align*}
where the probability is taken over the choices of samples from $X$ and the random coin tosses of $R$.
\end{definition}

We modify Hardt et al.'s formulation by using
  the group of qualified people ($q=1$) to represent the ``advantaged outcome'' group~\cite{Hardt2016}.
The advantaged outcome in our case is that a person sees a job ad
  because they are qualified for the job.
In addition, in our formulation, the outcome space $Y$ is not binary but
  a finite set of discrete values.

To test for this metric, the auditor must know whether
  each user is qualified for the job being advertised.
For convenience, we introduce the following notation:
\begin{equation}\label{eq:true_P_a_r}
P_{a, y}(R) = Pr_{(x, a', q) \sim\ X} \left[  R(x) = y | a' = a  \land q = 1  \right]
\end{equation}
$P_{a, y}(R)$ represents the likelihood that a qualified individual from
  a specific demographic group $a$ receives a relevance score $y$.
The auditor expects this likelihood to be equal across demographic groups if the platform's algorithm is unbiased.

We relax strict equality of the above term since any real-world
  observation may have small noise or variation.
We will use a relaxation from prior work~\cite{Segal2021},
that allows a small additive error $\alpha$
  as maximum allowed fairness gap ($FG$) between any two demographic groups.
We change the relaxation to use $\alpha$ instead of $\epsilon$ because we use
$\epsilon$ as a privacy parameter.

\begin{definition}[$\alpha$-fairness~\cite{Segal2021}]\label{def:alpha_fair}
We define a relevance estimator function $R$ to be $\alpha$-fair if:
$$FG(R) = \max_{a_1, a_2 \in A, y \in Y} |P_{a_1, y}(R) - P_{a_2, y}(R)| \le \alpha $$
\end{definition}

Since the auditor has only access to
  an independent sample of users ($S$),
  the measure of $P_{a,y}$ the auditor gets empirically is given by:

\begin{equation}\label{eq:p_a_y}
\overline{P}_{a, y}(R,S) = \frac{1}{n_{a,q}} \sum_{i=1}^{|S|} \mathbbm{1}\{ R(x_i) = y \land a_i = a  \land q_i = 1 \}
\end{equation}

where  $\mathbbm{1}\{ .\}$ is an indicator function selecting qualified members from group $a$ that are assigned a score $y$,
and $n_{a,q}$ is the number of qualified members in S
from group $a$.
The equation requires that $n_{a,q}>0$, an assumption we discuss at the end of this section.

Let $n_{a,q,y}$ be the number of
  qualified people in $S$ from group $a$ that got assigned
  a score $y$. We can also rewrite $\overline{P}_{a, y}(R,S)$ as:

\begin{equation}\label{eq:n_a_q_y}
\overline{P}_{a, y}(R,S) = \frac{ n_{a, q, y}}{n_{a, q}}
\end{equation}

We next consider the value of $\overline{P}_{a, y}(R,S)$ after it is distorted by noise to preserve privacy.
From \autoref{eq:n_a_q_y},
  $n_{a, q}$ is already known to the auditor so the quantity the platform wishes to protect is $n_{a,q,y}$,
  which represents each bin in the histogram that the platform computes.
The platform applies Laplace mechanism by adding noise drawn from
$r ~ \sim Lap(\frac{1}{\epsilon})$
to each count $n_{a,y,q}$ to guarantee $\epsilon$-DP~\cite{Dwork2006}.
Let $P^{*}_{a, y}(R,S)$ represent the noisy value the platform calculates:

\begin{equation}\label{eq:p_a_y_noisy}
P^{*}_{a, y}(R,S,\epsilon) = \frac{ n_{a, q, y} + r}{n_{a, q}} = \overline{P}_{a, y}(R,S) + \frac{r}{n_{a, q}}
\quad \textrm{s.t.} \quad r ~ \sim Lap(\frac{1}{\epsilon})
 \end{equation}

Extending a formulation in prior work~\cite{Segal2021}
  by adding a new privacy parameter,
  the empirical fairness gap (EFG) is given below
  (we give both the private and non-private cases).
A large EFG between two demographic groups implies unfairness.
$$EFG(R, S) = \max_{a_1, a_2 \in A, y \in Y} |\overline{P}_{a_1, y}(R,S)- \overline{P}_{a_2, y}(R,S)| $$
$$EFG(R, S,\epsilon) = \max_{a_1, a_2 \in A, y \in Y} |P^{*}_{a_1, y}(R,S,\epsilon)- P^{*}_{a_2, y}(R,S,\epsilon)| $$

The auditor checks $EFG(R,S,\epsilon) \le \alpha$ to test whether a relevance estimator $R$ is fair.
To analyze the sample size needed to perform this test with high statistical confidence,
  we will use the following definition that allows a small $\delta$ probability of failure over the
  randomness in $R$ and possible choices of samples in $S$.

\begin{definition}[($\alpha, \delta)$-fairness~\cite{Segal2021}]\label{def:alpha_delta_fair}
We define $R$ to be $(\alpha, \delta)$-fair with high probability with respect to S if:
\begin{align*}
& Pr \left[EFG(R,S) \le \alpha \right] \\
&=  Pr \left[ \max_{a_1, a_2 \in A, y \in Y} |\overline{P}_{a_1, y}(R,S) - \overline{P}_{a_2, y}(R,S)| \le \alpha \right] > 1 - \delta
\end{align*}

\end{definition}

We extend this definition for the case where an $\epsilon$-DP mechanism is applied to outputs of $R$
  to protect privacy of users.

\begin{definition}[($\alpha, \delta, \epsilon)$-fairness]\label{def:alpha_delta_eps_fair}
We define $R$ to be $(\alpha, \delta, \epsilon)$-fair with respect to S
  where an $\epsilon$-DP mechanism is applied to outputs of $R$ if:
  \begin{align*}
  &Pr \left[EFG(R,S, \epsilon) \le \alpha \right] \\
  &=  Pr \left[ \max_{a_1, a_2 \in A, y \in Y} |P^{*}_{a_1, y}(R,S,\epsilon)- P^{*}_{a_2, y}(R,S,\epsilon)| \le \alpha \right] > 1 - \delta
  \end{align*}
\end{definition}

The formulation in this and the following sections assumes $Y$ is a set of discrete values.
\autoref{eq:true_P_a_r} and~\autoref{eq:p_a_y} can be extended to the case where $Y$
  is a continuous space
  by choosing a different indicator function and comparing CDFs of relevance
  scores:
  \begin{equation}\label{eq:p_a_y_continuous}
  \begin{aligned}
 &P_{a, y}(R) = Pr_{(x, a', q) \sim\ X}[R(x) > y | a' = a \land q = 1] \\
&\overline{P}_{a, y}(R,S) =  \frac{1}{n_{a,q}} \sum_{i=1}^{|S|} \mathbbm{1}\{ R(x_i) > y \land a_i = a  \land q_i = 1 \}
 \end{aligned}
\end{equation}

\textbf{Assumptions:}
Our approach makes several assumptions to avoid degenerate cases.
We describe these next so that an auditor
  can design a robust experiment and
  may verify, post-audit, that the assumptions are met.

Equality of Opportunity (EoO) metric (Definition \autoref{def:eoo_def})
  adapts to unequal numbers of qualified individuals
  from different groups, but it cannot handle cases
  when \emph{no} one or \emph{very few} in the population
  with specific attributes are qualified for the job being advertised.
The first degenerate case occurs when $n_{a,q}=0$ in the denominator in~\autoref{eq:p_a_y}.
Another case is when only a few individuals are qualified from one group,
  and very many individuals are qualified from a second group (Example: $n_{a_1,q}=1$ and $n_{a_2,q}=1$ million).
In this case, EoO requires selecting all or none of the 1 million people in $a_2$ to match
  the inclusion or exclusion of the only individual in $a_1$.
Our \autoref{thm:main_result} guarantees that, for realistic parameters,
  $n_{a,q}$ is not small and that such degenerate cases do not occur.
Moreover, the auditor may verify, post-audit, that the assumptions about $n_{a,q}$ were met.

Second, we assume samples in each demographic group
  are independent and identically distributed.
We recognize that there maybe confounding factors
  that may induce bias,
  such as the location the audience is chosen from
  or difference in how active users are on the platform.
The auditor can anticipate some of these factors and
  control for them
  but only the platform has the data to verify independence.
In our result, we assume independence only within samples in a group,
  so we do not expect this limitation to decrease
  the observable differences in fairness across groups.
This assumption is common in nearly all statistical studies,
  and is aimed to be achieved by following best practices in subject selection.

Third, we assume there is some way to randomly sample users.
This mechanism may be provided by the platform,
  or the auditor may use some external source of users
  (in which case we require that will not induce its own bias).
We recognize that sampling users from social media and
  encouraging them to share their data with the auditor may be difficult,
  but prior studies have met this requirement satisfactorily
  (for example, the work of Citizen Browser~\cite{CitizenBrowser}).
We therefore
  place this problem outside the scope of this paper.

\subsection{Result: Minimum Sample Size Required for Auditing with Privacy}
  \label{sec:main_result}

Building on the background in the prior section,
  we give the following theoretical result:
  we show that, for employment ad delivery use-case,
  auditing with differential privacy guarantee
  increases the number of samples required for auditing,
  but only by a small constant factor.

\reviewfix{}
\begin{theorem}\label{thm:main_result}
An audit relying on a differentially privatized output of a relevance estimator $R$
  is ($\alpha, \delta, \epsilon$)-fair under equality-of-opportunity
  provided that, compared to the non-private case,
  an additional factor of $S_{dp}$ samples are measured.
We show that $4 \ln(3)/\ln(2) = 6.34$ is an upper bound for $S_{dp}$ and
  that ~4 is a better estimate for $S_{dp}$ under
  typical auditing parameters.

Formally, for an auditor to verify $R$ is $(\alpha, \delta, \epsilon)$-fair with respect to a sample set $S$,
  assuming $\epsilon > \alpha/2$,
  the condition $EFG(R,S, \epsilon) \le \alpha$ and the following
  condition on the minimum number of samples must hold:
\begin{equation}
\min_{a \in A} n_{a,q} \ge  \frac{8}{\alpha^2} \ln{\frac{3 |A| |Y|}{\delta}}
\end{equation}
where $S = \{(x_1, a_1, q_1), (x_2, a_2, q_2), ...., (x_n, a_n, q_n) \} \sim X$
and $n_{a,q}$ is the number of people in $S$ with sensitive attribute $a \in A$
and who are qualified for the job being advertised.
$\alpha$ and $\delta$ are knobs that control the level of fairness and statistical
confidence, respectively.
\end{theorem}

To prove this theorem,
  we first show with the case of auditing relevance scores
  when a privacy mechanism is not used.
We then analyze by what factor the required number of samples
  increases when a differentially private mechanism is applied.

\begin{lemma}\label{lemma:n_min_a_no_priv}
Without any guarantees of privacy,
  the following minimum number of samples is required
  to verify whether $R$ is $(\alpha, \delta)$-fair with respect to a sample set $S$:
\begin{equation}
\min_{a \in A} n_{a,q} \ge  \frac{2}{\alpha^2} \ln{\frac{2 |A| |Y|}{\delta}}
\end{equation}
where $S = \{(x_1, a_1, q_1), (x_2, a_2, q_2), ...., (x_n, a_n, q_n) \} \sim X$
and $n_{a,q}$ is the number of people in $S$ with sensitive attribute $a \in A$
and who are qualified for the job being advertised.
\end{lemma}

For the non-private case, the proof directly follows from
   prior work by Segal et al.~on auditing
   machine learning models using cryptographic techniques~\cite{Segal2021}.
In \autoref{sec:non_private_proof},
  we extend their proof with consideration of qualification as an additional attribute.

We next consider sample size for the private case,
  where the auditor
  receives a noisy histogram of relevance scores because the platform applies
  a differentially-private mechanism.

\begin{lemma}\label{lemma:n_min_a_priv}
With privacy,
  the following minimum number of samples is needed
  to verify whether $R$ is $(\alpha, \delta, \epsilon)$-fair with respect to a sample set $S$,
  \begin{equation}
\min_{a \in A} n_{a,q} \ge  \frac{8}{\alpha^2} \ln{\frac{3 |A| |Y|}{\delta}}
\end{equation}
where $S = \{(x_1, a_1, q_1), (x_2, a_2, q_2), ...., (x_n, a_n, q_n) \} \sim X$
and $n_{a,q}$ is the number of people in $S$ with the sensitive attribute $a \in A$
and are qualified for the job being advertised.
\end{lemma}

\begin{proof}
At a high level, the proof works by first defining a bad event that we
  want to happen with very low probability and
  then conditioning on this event not happening to derive the sample size needed to
  guarantee $(\alpha, \delta, \epsilon)$-fairness.
The  bad event is when there is error in the value for $P_{a,y}$ that the auditor calculates
  empirically.
We have two sources of error: sampling error
  and error due to noise added to protect privacy.

Now, consider the following ``bad'' event where the error between the value the auditor
  calculates $P^{*}_{a, y}(R,S)$ and the true $P_{a, y}(R)$ is above some threshold $t > 0$:
$$\text{``Bad''}:~ \left|P^{*}_{a, y}(R,S) -  P_{a, y}(R)\right| = \left|\left(\overline{P}_{a, y}(R,S) + \frac{r}{n_{a,q}}\right)-  P_{a, y}(R)\right| > t$$

Conditioning on the event that the total error for the bad event does not exceed $t$,
  we get a lower bound
  for a sample size that satisfies
  $(\alpha, \delta)$-fairness using the following value of $t$ (see~\autoref{sec:non_private_proof}):
\begin{equation}\label{eq:t_and_alpha}
t = \frac{\alpha}{2}
\end{equation}

We bound the probability of the
  above bad event for all groups in $A$ and possible outputs in $Y$:
 $$Pr \left[\exists a\in A ~\text{and}~ y \in Y: \left|\left(\overline{P}_{a, y}(R,S) + \frac{r}{n_{a,q}}\right) -  P_{a, y}(R)\right| > t \right] \le \delta $$

By applying the triangle inequality,
  it is sufficient (but not necessary) to bound the probability that
 each of the two sources of errors exceed $t/2$:
\begin{equation}\label{eq:two_error_terms}
Pr \left[ \left|\overline{P}_{a, y}(R,S) -  P_{a, y}(R)\right| > \frac{t}{2} \right]  +  Pr \left[\left|\frac{r}{n_{a,q}}\right|  > \frac{t}{2} \right]
\end{equation}

Since we require the samples in $S$ are chosen i.i.d.,
  $\overline{P}_{a, y}(R,S)$ is unbiased estimator of ${P}_{a, y}(R)$,
  i.e, $E[\overline{P}_{a, y}(R,S)] = {P}_{a, y}(R)$ (We prove this in~\autoref{sec:hoef_with_bias}).
Therefore, we can apply Hoeffding's inequality to the first term (sampling error) to
 simplify it to $2 \exp(\frac{- n_{a,q} t^2}{2})$.

We then apply a known tail bound
  for the Laplace distribution (for $r \sim Lap(B):~ Pr[|r| \ge t] < exp(\frac{-t}{B})$)
  to the second term (privacy error) to simplify it to
$\exp(\frac{-n_{a,q} t\epsilon}{2})$.
We then take a union bound over all possible values of $a$ and $y$:

\begin{align*}
&Pr [\exists a\in A ~\text{and}~ y \in Y: \text{Bad event occurs}] \\
&\le \sum_{a \in A}\sum_{y \in Y} Pr \left[ \left|\left(\overline{P}_{a, y}(R,S) + \frac{r}{n_{a,q}}\right) -  P_{a, y}(R)\right| > t \right]  \\
&\le \sum_{a \in A}\sum_{y \in Y} Pr \left[ \left|\overline{P}_{a, y}(R,S) -  P_{a, y}(R)\right| > \frac{t}{2} \right]    +      Pr \left[\left|\frac{r}{n_{a,q}}\right|  > \frac{t}{2} \right] \\
&\le  \sum_{a \in A}\sum_{y \in Y} \left(2 \exp(\frac{- n_{a,q} t^2}{2}) + \exp(\frac{-n_{a,q} t\epsilon}{2}) \right) \\
&=  \sum_{a \in A} |Y| \left(2 \exp(\frac{- n_{a,q} t^2}{2}) + \exp(\frac{-n_{a,q} t\epsilon}{2}) \right) \\
&\le |A||Y| \left(2 \exp(\frac{- n_{min} t^2}{2}) + \exp(\frac{-n_{min} t\epsilon}{2}) \right) \\
&\le |A||Y| \left(3 \exp(\frac{- n_{min} t^2}{2}) \right) \le \delta
\end{align*}
where $n_{min}$ is the smallest $n_{a,q}$
  across all groups $S_{a,q}$.
The last step above uses the fact that  $\epsilon > t$ to simplify the term.
This fact follows from \autoref{eq:t_and_alpha}
  and uses the assumption from \autoref{thm:main_result} that $\epsilon > \frac{\alpha}{2}$.
Rearranging the term
  and then plugging in $t = \frac{\alpha}{2}$,
  we get the following lower bound for $n_{min}$:

$$\min_{a \in A} n_{a,q}  = n_{min} \ge \frac{2}{t^2} \ln{\frac{3|A||Y|}{\delta}} =  \frac{8}{\alpha^2} \ln{\frac{3|A||Y|}{\delta}}$$
\end{proof}

We next give the following upper bound on the factor
  by which number of samples increase when a privacy
  mechanism is added to conclude the proof of the theorem.
\begin{lemma}\label{eq:upper_bound}
Compared to the non-private case (\autoref{lemma:n_min_a_no_priv}),
  at most 6.34 times as many samples are needed to perform the
  audit with differential privacy guarantees (\autoref{lemma:n_min_a_priv})).
\begin{equation}
\frac{\frac{8}{\alpha^2} \ln{\frac{3 |A| |Y|}{\delta}}}{\frac{2}{\alpha^2} \ln{\frac{2 |A| |Y|}{\delta}}} \le 4*\frac{\ln(3)}{\ln(2)} \approx 6.34
\end{equation}
\end{lemma}

\begin{figure}
  \centering
  \includegraphics[width=0.6\columnwidth]{FIG/sample_size_ratios.pdf}
    \caption{Relationship between auditing parameters ($\alpha$, $\delta$, $|A|$, and $|Y|$) and  the factor of increase in sample size.}
  \label{fig:sample_size_4x_bound}
\end{figure}
We prove the above lemma in~\autoref{sec:factor_upper_bound}.
While this is a strict upper bound,
  for reasonable auditing parameters,
  the overhead is much lower, around 4.
\autoref{fig:sample_size_4x_bound} shows these relationships for the
  four parameters: $\alpha$, $\delta$, $|A|$, and $|Y|$.
For all parameters, the factor of increase stays close to 4,
  lower than the true upper bound of 6.34.
\reviewfix{}
We omit $\epsilon$ from the plots because the upper bound stays the same
  for any $\epsilon > \frac{\alpha}{2}$. Since a typical value for
  $\alpha$ will be close to $0$, this constraint allows for small values of $\epsilon$
  that provide reasonable privacy guarantees.

As an example of this more typical upper bound,
say the auditor sets the fairness gap to $\alpha=0.2$,
  a comparable parameter to the 4/5ths rule that is commonly
  applied to test for adverse impact~\cite{EEOCGuidelines}.
Assume there are 2 demographic groups ($|A| = 2$) and that relevance scores
  range from $1$ to $100$ ($|Y| = 100$), and assume the auditor would
  like to evaluate fairness with $95\%$ confidence ($\delta = 0.05$).
\reviewfix{}
Then, the auditor needs a minimum of 1,879 samples from each demographic group to do the evaluation
  with privacy guarantees, compared to 450 samples without privacy,
  which is a 4.17x increase.
Such a sample size is reasonable compared to cohorts of several thousands of
  users used in prior external audits performed on
  social media platforms~\cite{Ali2019a, Imana2021},
  and is at the same order of magnitude achieved by current opt-in crowdsourcing
  efforts~\cite{CitizenBrowser}.

This small constant factor represents the increase in number of
  samples that ensuring the protection of differential privacy requires.
More importantly, it
  demonstrates that ensuring privacy need not be a barrier
  to implementation of platform-supported auditing.

\section{Related Work}
  \label{sec:related_work}

As algorithmic decision making systems have become ubiquitous,
  there is a growing call for auditing them
  for potential harmful behavior.
We highlight below such work on methods for algorithmic auditing,
  their use on social media and their
  trade-offs with privacy.

\textbf{Methods for Algorithmic Auditing:}
Audits can be either internal, performed by employees
  of companies with direct access to their systems, or
  external, performed by independent third-party entities
  with usually only user-level access to the systems.
We highlight how the platform-supported auditing framework we propose
  compares to existing auditing methods.

Sandvig et al.~provides an overview and taxonomy
  of external algorithmic auditing methods~\cite{Sandvig2014}.
The taxonomy identifies five categories for types of audits:
  source code audit, survey-based audit, scraping audit,
  sock puppet audit, and crowdsourced audit.
Using this taxonomy,
  a recent literature review
  categorized past algorithmic audits done
  on Internet platforms~\cite{Bandy2021survey}.
Our proposal for platform-supported auditing would extend this taxonomy of audits.
It differs from source code audits because it only requires that auditors
  to have query access to algorithms' output without access to the underlying code.
It differs from the other four types of methods
  because it requires a privileged and auditor-specific query interface.

There are newer proposals for auditing that do not directly
  fit into the Sandvig taxonomy.
In \emph{everyday algorithm auditing},
  users of social media platforms identify
  problematic behavior on social media platforms through their normal,
  day-to-day interactions with the platforms~\cite{Shen2021}.
Their case studies show the power of everyday
  users to identifying problematic algorithms without
  a centralized and organized audit study.
Our proposal differs because, first, it assumes the auditor
  has the technical expertise regarding algorithmic fairness and privacy.
Second, it enables studying
  harms that users cannot identify through their day-to-day use of the platforms.
An example of such harm is discriminatory ad delivery, as
  a user cannot know which ads they were targeted with but
  were not shown.

A second recent proposal is \emph{software-supported auditing}
  for augmenting the effectiveness of crowdsourced audits by using
  automation to choose auditing parameters such as
  audit prompts, and
  sample size~\cite{Matias2021}.
While Matias' work rigorously estimates sample sizes,
  they do not analyze how adding a privacy guarantee changes
  the sample size required,
  something we add in \autoref{sec:privacy_tradeoffs}.

Reisman et al.~proposes a framework for performing
  algorithmic impact assessments and enumerates challenges
  around them~\cite{Reisman2018}.
Among other recommendations, they identify the need for
  external auditors to have meaningful
  access to periodically assess the impact of algorithms
  but they do not suggest how auditing can be done while protecting privacy.
Metaxa et al.~emphasizes the need to
  evaluate the role of personalization when auditing
  algorithmic systems~\cite{Metaxa2021}.
Our work provides a concrete proposal for how to
  implement an audit of social media platforms' personalization
  algorithms while safeguarding the privacy of users.

An audit of Pymetrics, a startup that offers a job candidate screening service, performed by external researchers in 2020 proposes
  a new \emph{cooperative audit} framework,
  where the target platform gives the auditor special access
  to its source code and data~\cite{wilson2021building}.
This framework is similar to our work in that it requires
  platform collaboration.
Our framework differs in that it requires only query access
  to the platform's algorithms, and does not require access to underlying proprietary source code and data; furthermore, it protects the privacy of the individuals participating in the audit.

\textbf{Use of Algorithm Audits on Social Media:}
Several studies have investigated the role of social
  media algorithms in biased delivery of both organic content
  and promoted ads.
Sweeney's empirical study of Google Search ads~\cite{Sweeney2013} was the first to hypothesize
  that platform-driven
  decisions can lead to discriminatory ad
  delivery; a hypothesis strengthened by evidence from subsequent works~\cite{Datta2015, gelauff2020advertising, Lambrecht2016}.
Ali and Sapiezynski et al.~confirmed this hypothesis
  by showing Facebook's algorithms skew delivery of job and housing
  ads by gender and race even when an advertiser targets a neutral audience~\cite{Ali2019a}.

  In our prior work, we

  showed how to control for job qualifications on
  Facebook and LinkedIn,
  providing evidence that skew on Facebook may be discriminatory under U.S.~law~\cite{Imana2021}.
While these studies successfully identified harms,
  each has limitations we discuss in \autoref{sec:improve_limitations}.
The new method we propose
  can be used to audit societal impacts of ad delivery algorithms
  while accounting for user privacy and other limitations.

Audits have also evaluated how social media
  algorithms bias delivery of organic content.
A sock-puppet study
  of Facebook's newsfeed, with a focus on
  content generated leading up to the Italian election in 2018,
  shows the algorithms cause ranking bias~\cite{Hargreaves2018}.
A similar sock-puppet audit compared
  reverse-chronological and algorithmic
  timelines on Twitter to show the platform's algorithms
  distort content that is shown to users~\cite{Bartley2021}.
An internal audit by Twitter also looked at the effect of
  algorithmic timelines on political content and found
  their algorithms amplify content unequally
  across the political spectrum~\cite{TwitterAlgAmplification}.
These studies quantify biases
  by comparing algorithmic and chronological timelines.
Although we do not apply our work to bias in organic content,
  our framework is generalizable to studying where
  such biases may arise from.

\textbf{Algorithmic Auditing and Privacy:}
Auditing for fairness while protecting
  privacy of users is also an active area of research
  that our work contributes to.
Segal et al.~proposed a privacy-preserving
  framework for certifying the fairness of machine learning models through
  an interactive test~\cite{Segal2021}.
Their framework protects privacy of auditors' query inputs
  by using secure computation to ensure
  the model owner does not see the data in the queries.
In contrast, our method assumes user data is
  already known to the platform,
  as is in the case of social media platforms.
Our framework focuses on protecting the information
  query outputs leak about users or the platforms'
  algorithms to the auditor.

Other studies at the intersection of auditing and privacy
  have also looked at addressing
  privacy and other challenges around
  use of demographic data.
Studies by Holstein~\cite{Holstein2019} and later by Andrus~\cite{Andrus2021}
  interviewed practitioners
  from a wide range of industries to map out such challenges
  and normative questions around collection, inference, and
  use of sensitive demographics attributes of users
  for fairness efforts~\cite{Andrus2021, Holstein2019}.
Similarly, Bogen et al.~discusses the challenges around
  access to demographic attributes that arise due
  to different laws and inconsistent practices across
  different domains such as credit, employment,
  and health~\cite{bogen2020awareness}.
Platforms like Meta are actively working to address
  these challenges with new mechanisms
  for internal studies of the impact of sensitive attributes while protecting
  privacy~\cite{metatech, austin2021race}.
 Our proposal sidesteps these challenges as it does not require platforms to collect or
   store sensitive attributes;
   they only need to be known by the external auditor.
Similar to our work, Veale et al.'s ~proposes use of a trusted third-party entity
  to collect demographic data of users of an algorithmic system
  and later used the data for auditing the system~\cite{Veale2017}.
Our proposal differs in that it does not require collection of demographic attributes
  of all users, but just enough number needed to conduct an audit.

 %

\section{Implications and Future work}
Privacy concerns have hindered
  increasing transparency into operation of social media platforms.
Our work addresses
  this challenge by showing it is feasible to audit relevance estimators,
  the ``brains'' of social media platforms,
  without violating the privacy of their users
  or revealing proprietary details of the platforms' algorithms.

Our proposal for platform-supported auditing
  gives a practical framework for implementing
  policies outlined in DSA and PATA.
Our framework focuses on these proposals as
  both are promising efforts to increasing
  transparency of social media platforms and their algorithms' role in influencing individuals and shaping societal discourse.
Compared to prior proposals in the U.S.~\cite{Sdaa2021, Aaa2019, Ajopta2021},
  PATA is the most comprehensive in terms of the large platforms it covers~\cite{Nonnecke2022}.
Even if PATA's ultimate fate is uncertain,
  the EU-centric DSA that has already been passed as law
  may influence future policies in the U.S. and beyond,
  similar to the way EU's GDPR has shaped the
  global privacy landscape~\cite{Linden2020}.
As an example, YouTube's announcement of the YouTube Researcher Program for researchers in more than 50 countries came on the heels of the passing of the DSA~\cite{YoutubeResearchProg}.

The scope of our framework has limitations that
   are potential avenues for future work.
 For example,
   DSA's proposal covers platforms and services other than social media
   that are outside the scope of our study.
\reviewfix{}
Also, within social media platforms,
  our work focuses on how organic and promoted
  content is delivered on users' newsfeed,
  a place where users consume most of their content.
However, there are other features,
  such as Trends on Twitter, chosen by platform's algorithms,
  which we do not address in our work
  but are worth studying for potential harms such as misinformation.

Another potential direction for future work
  is exploring how
  platform-supported auditing can be adopted to
  study other forms of algorithmic harms.
Our example use case focuses on
  auditing for discrimination in job ad delivery.
A potential direction is exploring
  privacy mechanisms and
  metrics of fairness that are applicable for
  performing audits in other contexts, such as political or hateful content,
  while safeguarding privacy of users.

\reviewfix{}
Our work assumes audits will be conducted under a legal framework
  that incentivizes platform to act in good faith (\autoref{sec:model_limitations}),
  but another area of future work is to relax this assumption
  and add technical methods that look for
  accidental errors or intentional non-compliance by platforms.
Correlation of data has detected lapses in the past~\cite{FBSocialOneData}.
Technical methods, combined with the legal
  incentives proposed in DSA and PATA,
  would provide even stronger guarantees that audits are
  accurate and complete.

 %

\raggedbottom
\section{Conclusion}
Auditing social media platforms for public interest is an
   active and pressing area of academic research, policy-making and legislation.
To address concerns raised by prior audits,
  legislations have been proposed to mandate auditing by external researchers
  without compromising privacy of platform users and business interest
  of platforms.
We propose a platform-supported auditing framework that has
  safeguards for protecting against these risks.
The center of our mechanism is \emph{increasing transparency of relevance
  estimators}, which are the core drivers of both organic and promoted content choice and prioritization
  on social media.
Our analysis shows privacy-preserving auditing of relevance estimators
  can be implemented with high statistical confidence,
  provided that the sample size is increased by a small constant factor.
Our findings offer a novel technical solution for how to practically
  implement public oversight of social media companies,
  a core goal the proposed legislations are pushing for.

\section{Acknowledgments}
This work was funded in part by a grant from The Rose Foundation and NSF awards \#1916153, \#1956435, and \#1943584.

\bibliographystyle{acm}