  In this work we are concerned with the design of efficient mechanisms while
eliciting limited information from the agents. First, we study the performance
of sampling approximations in facility location games. Our key result is to
show that for any $\epsilon > 0$, a sample of size $c(\epsilon) =
\Theta(1/\epsilon^2)$ yields in expectation a $1 + \epsilon$ approximation with
respect to the optimal social cost of the generalized median mechanism on the
metric space $(\mathbb{R}^d, \| \cdot \|_1)$, while the number of agents $n \to
\infty$. Moreover, we study a series of exemplar environments from auction
theory through a communication complexity framework, measuring the expected
number of bits elicited from the agents; we posit that any valuation can be
expressed with $k$ bits, and we mainly assume that $k$ is independent of the
number of agents $n$. In this context, we show that Vickrey's rule can be
implemented with an expected communication of $1 + \epsilon$ bits from an
average bidder, for any $\epsilon > 0$, asymptotically matching the trivial
lower bound. As a corollary, we provide a compelling method to increment the
price in an English auction. We also leverage our single-item format with an
efficient encoding scheme to prove that the same communication bound can be
recovered in the domain of additive valuations through simultaneous ascending
auctions, assuming that the number of items is a constant. Finally, we propose
an ascending-type multi-unit auction under unit demand bidders; our mechanism
announces at every round two separate prices and is based on a sampling
algorithm that performs approximate selection with limited communication,
leading again to asymptotically optimal communication. Our results do not
require any prior knowledge on the agents' valuations, and mainly follow from
natural sampling techniques.
