  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 problem of finding bids and monetary transfers
maximizing the utility 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 of the graph. Next, we switch to our original problem,
focusing on two settings that differ for the incentives they allow for.
Incentive 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 monetary 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 to solve a suitable separation
problem in polynomial time, which can be done by reducing it to a WUP instance.
