We study higher statistical moments of Distortion for randomized social choice in a metric implicit utilitarian model. The Distortion of a social choice mechanism is the expected approximation factor with respect to the optimal utilitarian social cost (OPT). The k'th moment of Distortion is the expected approximation factor with respect to the k'th power of OPT. We consider mechanisms that elicit alternatives by randomly sampling voters for their favorite alternative. We design two families of mechanisms that provide constant (with respect to the number of voters and alternatives) k'th moment of Distortion using just k samples if all voters can then participate in a vote among the proposed alternatives, or 2k1 samples if only the sampled voters can participate. We also show that these numbers of samples are tight. Such mechanisms deviate from a constant approximation to OPT with probability that drops exponentially in the number of samples, independent of the total number of voters and alternatives. We conclude with simulations on realworld Participatory Budgeting data to qualitatively complement our theoretical insights.
more » « less Award ID(s):
 1637397
 NSFPAR ID:
 10175377
 Date Published:
 Journal Name:
 IJCAI 2020
 Page Range / eLocation ID:
 110 to 116
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize Distortion, the worst case social cost of an ordinal mechanism relative to underlying cardinal utilities. We consider two additional desiderata: Constant sample complexity and Squared Distortion. Constant sample complexity means that the mechanism (potentially randomized) only uses a constant number of ordinal queries regardless of the number of voters and alternatives. Squared Distortion is a measure of variance of the Distortion of a randomized mechanism.Our primary contribution is the first social choice mechanism with constant sample complexity and constant Squared Distortion (which also implies constant Distortion). We call the mechanism Random Referee, because it uses a random agent to compare two alternatives that are the favorites of two other random agents. We prove that the use of a comparison query is necessary: no mechanism that only elicits the topk preferred alternatives of voters (for constant k) can have Squared Distortion that is sublinear in the number of alternatives. We also prove that unlike any topk only mechanism, the Distortion of Random Referee meaningfully improves on benign metric spaces, using the Euclidean plane as a canonical example. Finally, among top1 only mechanisms, we introduce Random Oligarchy. The mechanism asks just 3 queries and is essentially optimal among the class of such mechanisms with respect to Distortion.In summary, we demonstrate the surprising power of constant sample complexity mechanisms generally, and just three random voters in particular, to provide some of the best known results in the implicit utilitarian framework.more » « less

We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worstcase distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the wellknown weightedtournament rule, achieves a distortion of at most 3 (Anshelevich et al. 2015). We disprove this conjecture by constructing a sequence of instances which shows that the worstcase distortion of Ranked Pairs is at least 5. Our lower bound on the worstcase distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worstcase distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairnessratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.more » « less

We study the problem of designing voting rules that take as input the ordinal preferences of n agents over a set of m alternatives and output a single alternative, aiming to optimize the overall happiness of the agents. The input to the voting rule is each agent’s ranking of the alternatives from most to least preferred, yet the agents have more refined (cardinal) preferences that capture the intensity with which they prefer one alternative over another. To quantify the extent to which voting rules can optimize over the cardinal preferences given access only to the ordinal ones, prior work has used the distortion measure, i.e., the worstcase approximation ratio between a voting rule’s performance and the best performance achievable given the cardinal preferences. The work on the distortion of voting rules has been largely divided into two “worlds”: utilitarian distortion and metric distortion. In the former, the cardinal preferences of the agents correspond to general utilities and the goal is to maximize a normalized social welfare. In the latter, the agents’ cardinal preferences correspond to costs given by distances in an underlying metric space and the goal is to minimize the (unnormalized) social cost. Several deterministic and randomized voting rules have been proposed and evaluated for each of these worlds separately, gradually improving the achievable distortion bounds, but none of the known voting rules perform well in both worlds simultaneously. In this work, we prove that one can in fact achieve the “best of both worlds” by designing new voting rules, both deterministic and randomized, that simultaneously achieve nearoptimal distortion guarantees in both distortion worlds. We also prove that this positive result does not generalize to the case where the voting rule is provided with the rankings of only the topt alternatives of each agent, for t < m, and study the extent to which such bestofbothworlds guarantees can be achieved.more » « less

Abstract We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gatelevel error with probability close to one. We model noise by adding a pair of weak, unital, singlequbit noise channels after each twoqubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution
and the corresponding noiseless output distribution$$p_{\text {noisy}}$$ ${p}_{\text{noisy}}$ shrink exponentially with the expected number of gatelevel errors. Specifically, the linear crossentropy benchmark$$p_{\text {ideal}}$$ ${p}_{\text{ideal}}$F that measures this correlation behaves as , where$$F=\text {exp}(2s\epsilon \pm O(s\epsilon ^2))$$ $F=\text{exp}(2s\u03f5\pm O\left(s{\u03f5}^{2}\right))$ is the probability of error per circuit location and$$\epsilon $$ $\u03f5$s is the number of twoqubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution and the uniform distribution$$p_{\text {noisy}}$$ ${p}_{\text{noisy}}$ decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {unif}}$$ ${p}_{\text{unif}}$ . In other words, although at least one local error occurs with probability$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1F)p_{\text {unif}}$$ ${p}_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1F){p}_{\text{unif}}$ , the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$1F$$ $1F$ . Thus, the “whitenoise approximation” is meaningful when$$O(F\epsilon \sqrt{s})$$ $O\left(F\u03f5\sqrt{s}\right)$ , a quadratically weaker condition than the$$\epsilon \sqrt{s} \ll 1$$ $\u03f5\sqrt{s}\ll 1$ requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$\epsilon s\ll 1$$ $\u03f5s\ll 1$ , which corresponds to only$$s \ge \Omega (n\log (n))$$ $s\ge \Omega (nlog(n\left)\right)$logarithmic depth circuits, and if, additionally, the inverse error rate satisfies , which is needed to ensure errors are scrambled faster than$$\epsilon ^{1} \ge {\tilde{\Omega }}(n)$$ ${\u03f5}^{1}\ge \stackrel{~}{\Omega}\left(n\right)$F decays. The whitenoise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexitytheoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from secondmoment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds. 
We provide an approximation algorithm for network revenue management problems. In our approximation algorithm, we construct an approximate policy using value function approximations that are expressed as linear combinations of basis functions. We use a backward recursion to compute the coefficients of the basis functions in the linear combinations. If each product uses at most L resources, then the total expected revenue obtained by our approximate policy is at least [Formula: see text] of the optimal total expected revenue. In many network revenue management settings, although the number of resources and products can become large, the number of resources used by a product remains bounded. In this case, our approximate policy provides a constantfactor performance guarantee. Our approximate policy can handle nonstationarities in the customer arrival process. To our knowledge, our approximate policy is the first approximation algorithm for network revenue management problems under nonstationary arrivals. Our approach can incorporate the customer choice behavior among the products, and allows the products to use multiple units of a resource, while still maintaining the performance guarantee. In our computational experiments, we demonstrate that our approximate policy performs quite well, providing total expected revenues that are substantially better than its theoretical performance guarantee.more » « less