License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.84
URN: urn:nbn:de:0030-drops-136230
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13623/
Go to the corresponding LIPIcs Volume Portal

Babaioff, Moshe ; Cole, Richard ; Hartline, Jason ; Immorlica, Nicole ; Lucier, Brendan

Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)

pdf-format:
LIPIcs-ITCS-2021-84.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{babaioff_et_al:LIPIcs.ITCS.2021.84,
  author =	{Moshe Babaioff and Richard Cole and Jason Hartline and Nicole Immorlica and Brendan Lucier},
  title =	{{Non-Quasi-Linear Agents in Quasi-Linear Mechanisms}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{84:1--84:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13623},
  URN =		{urn:nbn:de:0030-drops-136230},
  doi =		{10.4230/LIPIcs.ITCS.2021.84},
  annote =	{Keywords: Return on investment, Non-quasi-linear agents, Transferable Welfare, Simultaneous Second-Price Auctions}
}

Keywords: Return on investment, Non-quasi-linear agents, Transferable Welfare, Simultaneous Second-Price Auctions
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI