Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTruthfulness with Value-Maximizing Bidders
273
0
0.0
(
0
)
Added by
Martin Bichler
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 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.
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.
We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non-trivial approximation ratio of $O(log^2 m)$ [STOC06], where $m$ is the number of items. This was subsequently improved to $O(log mlog log m)$ [Dobzinski, APPROX07] and then to $O(log m)$ [Krysta and Vocking, ICALP12]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of $O(sqrt {log m})$. Similarly to previous constructions, our mechanism uses polynomially many value and demand queries, and in fact provides the same approximation ratio for the larger class of XOS (a.k.a. fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although in general computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive.
Course assignment is a wide-spread problem in education and beyond. Often students have preferences for bundles of course seats or course schedules over the week, which need to be considered. The problem is a challenging distributed scheduling task requiring decision support. First-Come First-Served (FCFS) is simple and the most widely used assignment rule in practice, but it leads to inefficient outcomes and envy in the allocation. Recent theoretical results suggest alternatives with attractive economic and computational properties. Bundled Probabilistic Serial (BPS) is a randomized mechanism satisfying ordinal efficiency, envy-freeness, and weak strategy-proofness. This mechanism also runs in polynomial time, which is important for the large problem instances in the field. We report empirical results from a first implementation of BPS at the Technical University of Munich, which allows us to provide important empirical metrics such as the size of the resulting matching, the average rank, the profile, and the popularity of the assignments. These metrics were central for the adoption of BPS. In particular, we compare these metrics to Random Serial Dictatorship with bundle bids (BRSD). The BRSD mechanism is used to simulate the wide-spread First-Come First-Served (FCFS) mechanism and it allows us to compare FCFS (BRSD) and BPS. While theoretically appealing, preference elicitation is a major challenge when considering preferences over exponentially many packages. We introduce tools to elicit preferences which reduce the number of parameters a student needs to a manageable set. The approach together with BPS yields a computationally effective tool to solve course assignment problems with thousands of students, and possibly provides an approach for other distributed scheduling tasks in organizations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
