The Power of Media Agencies in Ad Auctions: Improving Utility through Coordinated Bidding

The increasing competition in digital advertising induced a proliferation of media agencies playing the role of intermediaries between advertisers and platforms selling ad slots. When a group of competing advertisers is managed by a common agency, many forms of collusion, such as bid rigging, can be implemented by coordinating bidding strategies, dramatically increasing advertisers' value. We study the computational problem faced by a media agency that has to coordinate the bids of a group of colluders, under GSP and VCG mechanisms. First, we introduce an abstract bid optimization problem, called weighted utility problem (WUP), which is useful in proving our results. We show that the utilities of bidding strategies are related to the length of paths in a directed acyclic weighted graph, whose structure and weights depend on the mechanism under study. This allows us to solve WUP in polynomial time by finding a shortest path in the graph. Next, we switch to our original problem, focusing on two settings that differ for the individual rationality constraints they require. Such constraints ensure that colluders do not leave the agency, and they can be enforced by implementing monetary transfers between the agency and the advertisers. In particular, we study the arbitrary transfers setting, where any kind of transfer to and from the advertisers is allowed, and the more realistic limited liability setting, in which no advertiser can be paid by the agency. In the former, we cast the problem as a WUP instance and solve it by our graph-based algorithm, while, in the latter, we formulate it as a linear program with exponentially-many variables efficiently solvable by applying the ellipsoid algorithm to its dual. This requires solving a suitable separation problem in polynomial time, which can be done by reducing it to a WUP instance.