  The paper designs revenue-maximizing auction mechanisms for agents who aim to
maximize their total obtained values rather than the classical quasi-linear
utilities. Several models have been proposed to capture the behaviors of such
agents in the literature. In the paper, we consider the model where agents are
subject to budget and return-on-spend constraints. The budget constraint of an
agent limits the maximum payment she can afford, while the return-on-spend
constraint means that the ratio of the total obtained value (return) to the
total payment (spend) cannot be lower than the targeted bar set by the agent.
The problem was first coined by [Balseiro et al., EC 2022]. In their work, only
Bayesian mechanisms were considered. We initiate the study of the problem in
the worst-case model and compare the revenue of our mechanisms to an offline
optimal solution, the most ambitious benchmark. The paper distinguishes two
main auction settings based on the accessibility of agents' information: fully
private and partially private. In the fully private setting, an agent's
valuation, budget, and target bar are all private. We show that if agents are
unit-demand, constant approximation mechanisms can be obtained; while for
additive agents, there exists a mechanism that achieves a constant
approximation ratio under a large market assumption. The partially private
setting is the setting considered in the previous work [Balseiro et al., EC
2022] where only the agents' target bars are private. We show that in this
setting, the approximation ratio of the single-item auction can be further
improved, and a $\Omega(1/\sqrt{n})$-approximation mechanism can be derived for
additive agents.
