  Existing work in fairness auditing assumes that each audit is performed
independently. In this paper, we consider multiple agents working together,
each auditing the same platform for different tasks. Agents have two levers:
their collaboration strategy, with or without coordination beforehand, and
their strategy for sampling appropriate data points. We theoretically compare
the interplay of these levers. Our main findings are that (i) collaboration is
generally beneficial for accurate audits, (ii) basic sampling methods often
prove to be effective, and (iii) counter-intuitively, extensive coordination on
queries often deteriorates audits accuracy as the number of agents increases.
Experiments on three large datasets confirm our theoretical results. Our
findings motivate collaboration during fairness audits of platforms that use ML
models for decision-making.
