2026-07-22T03:56:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13623 2024-03-06T10:52:28Z ddc:004 open_access

Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract) Babaioff, Moshe Cole, Richard Hartline, Jason Immorlica, Nicole Lucier, Brendan Return on investment Non-quasi-linear agents Transferable Welfare Simultaneous Second-Price Auctions Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moshe Babaioff and Richard Cole and Jason Hartline and Nicole Immorlica and Brendan Lucier 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.84 urn:nbn:de:0030-drops-136230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.84 eng https://creativecommons.org/licenses/by/3.0/legalcode