Benchmark design and prior-independent optimization

Jason Hartline, Aleck Johnsen, Yingkai Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper compares two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i.e., agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. This paper gives a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark is equal to the prior-independent optimal algorithm/mechanism. We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. and regularly distributed values. We use this solution to solve the corresponding benchmark design problem. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a.k.a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program.11For the full version of this work, see https://arxiv.org/abs/2001.10157.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Pages294-305
Number of pages12
ISBN (Electronic)9781728196213
DOIs
StatePublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN (Print)0272-5428

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
CountryUnited States
CityVirtual, Durham
Period11/16/2011/19/20

Keywords

  • n/a

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Benchmark design and prior-independent optimization'. Together they form a unique fingerprint.

Cite this