Competitive Analysis via Benchmark Decomposition

Ning Chen, Nikolai Gravin, Pinyan Lu

Abstract

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. Multi-unit auctions. Given a β-competitive unlimited supply auction, the best previously known multi-unit auction is 2β-competitive. We design a (1+β)-competitive auction reducing the ratio from 4.84 to 3.24. These results carry over to matroid and position auctions. General downward-closed environments. We design a 6.5-competitive auction improving upon the ratio of 7.5. Our auction is noticeably simpler than the previous best one. Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of 4.12, which significantly narrows the margin of [4, 4.84] previously known for this problem.A particularly important tool in our analysis is a simple decomposition lemma, which allows us to bound the competitive ratio against a sum of benchmark functions. We use this lemma in a "divide and conquer" fashion by dividing the target benchmark into the sum of simpler functions.
BibTeX
@inproceedings{chen2015competitive,
  author = {Ning Chen and Nikolai Gravin and Pinyan Lu},
  title = {{Competitive Analysis via Benchmark Decomposition}},
  booktitle = {EC},
  year = {2015},
  url = {https://openreview.net/forum?id=AxzSPn6gE1},
}
Figure