Truthful Auction Mechanisms for Mixed Utility and Value Maximizers in Online Advertising

Digital advertising is a major revenue source for online platforms, and many advertisers now use auto‑bidding tools. The classic utility‑maximizer (UM) model no longer captures such advertisers, prompting the introduction of a value‑maximizer (VM) model with ROI constraints. In mixed environments where UM and VM bidders coexist, the auction design becomes a multi‑parameter mechanism design problem because advertisers can manipulate both their click value and their type.

This work proposes a truthful auction mechanism that cleverly combines the payment rules of VCG (for UM) and GSP (for VM) to handle the multi‑parameter complexity. The mechanism achieves a social‑welfare approximation ratio of 2, with a proven lower bound of 1.25. It can be seen as a natural extension of VCG for UM and GSP for VM.

The paper introduces two mechanisms:

MPU (Mechanism for bidders with PUblic classes) – for the case where type information is public. Advertisers are ranked by value, slots are allocated accordingly, and UM bidders are charged using VCG‑style payments while VM bidders pay according to GSP. MPU is shown to be incentive compatible (IC), individually rational (IR), robust, and optimal for liquid social welfare (LSW).

MPR (Mechanism for bidders with PRivate classes) – for the private‑type setting. The key idea is to set the payment for each slot as the maximum of two values: the VCG‑derived payment from the nearest lower UM and the GSP‑derived payment from the nearest lower VM. MPR first fills slots with all VMs, then iteratively assigns each UM to the slot that maximizes its utility, updating payments after each insertion. This design ensures IC, IR, robustness, and achieves an LSW approximation ratio of at most 2, which is provably optimal up to a factor of 1.25.

The paper provides formal definitions of UM and VM bidders, the notions of incentive compatibility, individual rationality, robustness, and liquid social welfare. It presents several lemmas and theorems establishing the theoretical properties of MPU and MPR, including proofs (omitted for brevity) that MPR is robust, IR, IC, and achieves the stated approximation bounds.

In conclusion, the study advances mechanism design for mixed UM/VM environments under both public and private type information, offering practical insights for auto‑bidding advertising platforms and opening future research directions on tightening the approximation gap.