Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Limits of an Information Intermediary in Auction Design
151
0
0.0
(
0
)
Added by
Kangning Wang
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the limits of an information intermediary in Bayesian auctions. Formally, we consider the standard single-item auction, with a revenue-maximizing seller and $n$ buyers with independent private values; in addition, we now have an intermediary who knows the buyers true values, and can map these to a public signal so as to try to increase buyer surplus. This model was proposed by Bergemann et al., who present a signaling scheme for the single-buyer setting that raises the optimal consumer surplus, by guaranteeing the item is always sold while ensuring the seller gets the same revenue as without signaling. Our work aims to understand how this result ports to the setting with multiple buyers. Our first result is an impossibility: We show that such a signaling scheme need not exist even for $n=2$ buyers with $2$-point valuation distributions. Indeed, no signaling scheme can always allocate the item to the highest-valued buyer while preserving any non-trivial fraction of the original consumer surplus; further, no signaling scheme can achieve consumer surplus better than a factor of $frac{1}{2}$ compared to the maximum achievable. These results are existential (and not computational) impossibilities, and thus provide a sharp separation between the single and multi-buyer settings. On the positive side, for discrete valuation distributions, we develop signaling schemes with good approximation guarantees for the consumer surplus compared to the maximum achievable, in settings where either the number of agents, or the support size of valuations, is small. Formally, for i.i.d. buyers, we present an $O(min(log n, K))$-approximation where $K$ is the support size of the valuations. Moreover, for general distributions, we present an $O(min(n log n, K^2))$-approximation. Our signaling schemes are conceptually simple and computable in polynomial (in $n$ and $K$) time.
rate research
Read More
This paper introduces the targeted sampling model in optimal auction design. In this model, the seller may specify a quantile interval and sample from a buyers prior restricted to the interval. This can be interpreted as allowing the seller to, for example, examine the top $40$ percents bids from previous buyers with the same characteristics. The targeting power is quantified with a parameter $Delta in [0, 1]$ which lower bounds how small the quantile intervals could be. When $Delta = 1$, it degenerates to Cole and Roughgardens model of i.i.d. samples; when it is the idealized case of $Delta = 0$, it degenerates to the model studied by Chen et al. (2018). For instance, for $n$ buyers with bounded values in $[0, 1]$, $tilde{O}(epsilon^{-1})$ targeted samples suffice while it is known that at least $tilde{Omega}(n epsilon^{-2})$ i.i.d. samples are needed. In other words, targeted sampling with sufficient targeting power allows us to remove the linear dependence in $n$, and to improve the quadratic dependence in $epsilon^{-1}$ to linear. In this work, we introduce new technical ingredients and show that the number of targeted samples sufficient for learning an $epsilon$-optimal auction is substantially smaller than the sample complexity of i.i.d. samples for the full spectrum of $Delta in [0, 1)$. Even with only mild targeting power, i.e., whenever $Delta = o(1)$, our targeted sample complexity upper bounds are strictly smaller than the optimal sample complexity of i.i.d. samples.
This letter considers the design of an auction mechanism to sell the object of a seller when the buyers quantize their private value estimates regarding the object prior to communicating them to the seller. The designed auction mechanism maximizes the utility of the seller (i.e., the auction is optimal), prevents buyers from communicating falsified quantized bids (i.e., the auction is incentive-compatible), and ensures that buyers will participate in the auction (i.e., the auction is individually-rational). The letter also investigates the design of the optimal quantization thresholds using which buyers quantize their private value estimates. Numerical results provide insights regarding the influence of the quantization thresholds on the auction mechanism.
Edge computing as a promising technology provides lower latency, more efficient transmission, and faster speed of data processing since the edge servers are closer to the user devices. Each edge server with limited resources can offload latency-sensitive and computation-intensive tasks from nearby user devices. However, edge computing faces challenges such as resource allocation, energy consumption, security and privacy issues, etc. Auction mechanisms can well characterize bidirectional interactions between edge servers and user devices under the above constraints in edge computing. As demonstrated by the existing works, auction and mechanism design approaches are outstanding on achieving optimal allocation strategy while guaranteeing mutual satisfaction among edge servers and user devices, especially for scenarios with scarce resources. In this paper, we introduce a comprehensive survey of recent researches that apply auction approaches in edge computing. Firstly, a brief overview of edge computing including three common edge computing paradigms, i.e., cloudlet, fog computing and mobile edge computing, is presented. Then, we introduce fundamentals and backgrounds of auction schemes commonly used in edge computing systems. After then, a comprehensive survey of applications of auction-based approaches applied for edge computing is provided, which is categorized by different auction approaches. Finally, several open challenges and promising research directions are discussed.
The design of optimal auctions is a problem of interest in economics, game theory and computer science. Despite decades of effort, strategyproof, revenue-maximizing auction designs are still not known outside of restricted settings. However, recent methods using deep learning have shown some success in approximating optimal auctions, recovering several known solutions and outperforming strong baselines when optimal auctions are not known. In addition to maximizing revenue, auction mechanisms may also seek to encourage socially desirable constraints such as allocation fairness or diversity. However, these philosophical notions neither have standardization nor do they have widely accepted formal definitions. In this paper, we propose PreferenceNet, an extension of existing neural-network-based auction mechanisms to encode constraints using (potentially human-provided) exemplars of desirable allocations. In addition, we introduce a new metric to evaluate an auction allocations adherence to such socially desirable constraints and demonstrate that our proposed method is competitive with current state-of-the-art neural-network based auction designs. We validate our approach through human subject research and show that we are able to effectively capture real human preferences. Our code is available at https://github.com/neeharperi/PreferenceNet
As mobile devices have been ubiquitous, participatory sensing emerges as a powerful tool to solve many contemporary real life problems. Here, we contemplate the participatory sensing in online double auction environment by considering the location information of the participating agents. In this paper, we propose a truthful mechanism in this setting and the mechanism also satisfies the other economic properties such as budget balance and individual rationality.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
