ﻻ يوجد ملخص باللغة العربية
The Competition Complexity of an auction setting refers to the number of additional bidders necessary in order for the (deterministic, prior-independent, dominant strategy truthful) Vickrey-Clarke-Groves mechanism to achieve greater revenue than the (randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the additional bidders. We prove that the competition complexity of $n$ bidders with additive valuations over $m$ independent items is at most $n(ln(1+m/n)+2)$, and also at most $9sqrt{nm}$. When $n leq m$, the first bound is optimal up to constant factors, even when the items are i.i.d. and regular. When $n geq m$, the second bound is optimal for the benchmark introduced in [EFFTW17a] up to constant factors, even when the items are i.i.d. and regular. We further show that, while the Eden et al. benchmark is not necessarily tight in the $n geq m$ regime, the competition complexity of $n$ bidders with additive valuations over even $2$ i.i.d. regular items is indeed $omega(1)$. Our main technical contribution is a reduction from analyzing the Eden et al. benchmark to proving stochastic dominance of certain random variables.
We study revenue maximization by deterministic mechanisms for the simplest case for which Myersons characterization does not hold: a single seller selling two items, with independently distributed values, to a single additive buyer. We prove that opt
We consider the problem of posting prices for unit-demand buyers if all $n$ buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can b
We study competition among contests in a general model that allows for an arbitrary and heterogeneous space of contest design, where the goal of the contest designers is to maximize the contestants sum of efforts. Our main result shows that optimal c
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 pr
We consider a model where an agent has a repeated decision to make and wishes to maximize their total payoff. Payoffs are influenced by an action taken by the agent, but also an unknown state of the world that evolves over time. Before choosing an ac