Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRevenue Monotonicity Under Misspecified Bidders
76
0
0.0
(
0
)
Added by
Makis Arsenis
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate revenue guarantees for auction mechanisms in a model where a distribution is specified for each bidder, but only some of the distributions are correct. The subset of bidders whose distribution is correctly specified (henceforth, the green bidders) is unknown to the auctioneer. The question we address is whether the auctioneer can run a mechanism that is guaranteed to obtain at least as much revenue, in expectation, as would be obtained by running an optimal mechanism on the green bidders only. For single-parameter feasibility environments, we find that the answer depends on the feasibility constraint. For matroid environments, running the optimal mechanism using all the specified distributions (including the incorrect ones) guarantees at least as much revenue in expectation as running the optimal mechanism on the green bidders. For any feasibility constraint that is not a matroid, there exists a way of setting the specified distributions and the true distributions such that the opposite conclusion holds.
rate research
Read More
In markets such as digital advertising auctions, bidders want to maximize value rather than payoff. This is different to the utility functions typically assumed in auction theory and leads to different strategies and outcomes. We refer to bidders who maximize value as value bidders. While simple single-object auction formats are truthful, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Approximation has been used as a means to achieve truthfulness, and we study which approximation ratios we can get from truthful approximation mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with $n$ bidders and $m$ items cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio of O(sqrt(m)). We provide better ratios for environments with restricted valuations.
Classic mechanism design often assumes that a bidders action is restricted to report a type or a signal, possibly untruthfully. In todays digital economy, bidders are holding increasing amount of private information about the auctioned items. And due to legal or ethical concerns, they would demand to reveal partial but truthful information, as opposed to report untrue signal or misinformation. To accommodate such bidder behaviors in auction design, we propose and study a novel mechanism design setup where each bidder holds two kinds of information: (1) private emph{value type}, which can be misreported; (2) private emph{information variable}, which the bidder may want to conceal or partially reveal, but importantly, emph{not} to misreport. We show that in this new setup, it is still possible to design mechanisms that are both emph{Incentive and Information Compatible} (IIC). We develop two different black-box transformations, which convert any mechanism $mathcal{M}$ for classic bidders to a mechanism $mathcal{M}$ for strategically reticent bidders, based on either outcome of expectation or expectation of outcome, respectively. We identify properties of the original mechanism $mathcal{M}$ under which the transformation leads to IIC mechanisms $mathcal{M}$. Interestingly, as corollaries of these results, we show that running VCG with expected bidder values maximizes welfare whereas the mechanism using expected outcome of Myersons auction maximizes revenue. Finally, we study how regulation on the auctioneers usage of information may lead to more robust mechanisms.
We analyze the revenue loss due to market shrinkage. Specifically, consider a simple market with one item for sale and $n$ bidders whose values are drawn from some joint distribution. Suppose that the market shrinks as a single bidder retires from the market. Suppose furthermore that the value of this retiring bidder is fixed and always strictly smaller than the values of the other players. We show that even this slight decrease in competition might cause a significant fall of a multiplicative factor of $frac{1}{e+1}approx0.268$ in the revenue that can be obtained by a dominant strategy ex-post individually rational mechanism. In particular, our results imply a solution to an open question that was posed by Dobzinski, Fu, and Kleinberg [STOC11].
We study the problem of selling a good to a group of bidders with interdependent values in a prior-free setting. Each bidder has a signal that can take one of $k$ different values, and her value for the good is a weakly increasing function of all the bidders signals. The bidders are partitioned into $ell$ expertise-groups, based on how their signal can impact the values for the good, and we prove upper and lower bounds regarding the approximability of social welfare and revenue for a variety of settings, parameterized by $k$ and $ell$. Our lower bounds apply to all ex-post incentive compatible mechanisms and our upper bounds are all within a small constant of the lower bounds. Our main results take the appealing form of ascending clock auctions and provide strong incentives by admitting the desired outcomes as obvious ex-post equilibria.
Consider a monopolist selling $n$ items to an additive buyer whose item values are drawn from independent distributions $F_1,F_2,ldots,F_n$ possibly having unbounded support. Unlike in the single-item case, it is well known that the revenue-optimal selling mechanism (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. Also known is that simple mechanisms with a bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, whether an arbitrarily high fraction of the optimal revenue can be extracted via a bounded menu size remained open. We give an affirmative answer: for every $n$ and $varepsilon>0$, there exists $C=C(n,varepsilon)$ s.t. mechanisms of menu size at most $C$ suffice for obtaining $(1-varepsilon)$ of the optimal revenue from any $F_1,ldots,F_n$. We prove upper and lower bounds on the revenue-approximation complexity $C(n,varepsilon)$ and on the deterministic communication complexity required to run a mechanism achieving such an approximation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
