تقرير
Settling the Competition Complexity of Additive Buyers over Independent Items
| العنوان: | Settling the Competition Complexity of Additive Buyers over Independent Items |
|---|---|
| المؤلفون: | Derakhshan, Mahsa, Ryu, Emily, Weinberg, S. Matthew, Xue, Eric |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory |
| الوصف: | The competition complexity of an auction setting is the number of additional bidders needed such that the simple mechanism of selling items separately (with additional bidders) achieves greater revenue than the optimal but complex (randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the additional bidders. Our main result settles the competition complexity of $n$ bidders with additive values over $m < n$ independent items at $\Theta(\sqrt{nm})$. The $O(\sqrt{nm})$ upper bound is due to [BW19], and our main result improves the prior lower bound of $\Omega(\ln n)$ to $\Omega(\sqrt{nm})$. Our main result follows from an explicit construction of a Bayesian IC auction for $n$ bidders with additive values over $m Comment: 50 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.03937 |
| رقم الأكسشن: | edsarx.2403.03937 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |