On the Computational Complexity of NonDictatorial Aggregation
We investigate when nondictatorial aggregation is possible from an algorithmic perspective, where nondictatorial aggregation means that the votes cast by the members of a society can be aggregated in such a way that there is no single member of the society that always dictates the collective outcome. We consider the setting in which the members of a society take a position on a fixed collection of issues, where for each issue several different alternatives are possible, but the combination of choices must belong to a given set X of allowable voting patterns. Such a set X is called a possibility domain if there is an aggregator that is nondictatorial, operates separately on each issue, and returns values among those cast by the society on each issue. We design a polynomialtime algorithm that decides, given a set X of voting patterns, whether or not X is a possibility domain. Furthermore, if X is a possibility domain, then the algorithm constructs in polynomial time a nondictatorial aggregator for X. Furthermore, we show that the question of whether a Boolean domain X is a possibility domain is in NLOGSPACE. We also design a polynomialtime algorithm that decides whether X is a uniform possibility more »
 Award ID(s):
 1814152
 Publication Date:
 NSFPAR ID:
 10358321
 Journal Name:
 Journal of Artificial Intelligence Research
 Volume:
 72
 Page Range or eLocationID:
 137 to 183
 ISSN:
 10769757
 Sponsoring Org:
 National Science Foundation
More Like this


Suppose $F:=(f_1,\ldots,f_n)$ is a system of random $n$variate polynomials with $f_i$ having degree $\leq\!d_i$ and the coefficient of $x^{a_1}_1\cdots x^{a_n}_n$ in $f_i$ being an independent complex Gaussian of mean $0$ and variance $\frac{d_i!}{a_1!\cdots a_n!\left(d_i\sum^n_{j=1}a_j \right)!}$. Recent progress on Smale's 17$\thth$ Problem by Lairez  building upon seminal work of Shub, Beltran, Pardo, B\"{u}rgisser, and Cucker  has resulted in a deterministic algorithm that finds a single (complex) approximate root of $F$ using just $N^{O(1)}$ arithmetic operations on average, where $N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$ ($=n(n+\max_i d_i)^{O(\min\{n,\max_i d_i)\}}$) is the maximum possible total number of monomial terms for such an $F$. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain averagecase polynomialtime with more general probability measures? We show the answer is yes when $F$ is instead a binomial system  a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just $O(n^3\log^2(n\max_i d_i))$ arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructionsmore »

We present decidability results for a subclass of “noninteractive” simulation problems, a wellstudied class of problems in information theory. A noninteractive simulation problem is specified by two distributions P(x, y) and Q(u, v): The goal is to determine if two players, Alice and Bob, that observe sequences Xn and Y n respectively where {(Xi, Yi)}n i=1 are drawn i.i.d. from P(x, y) can generate pairs U and V respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to Q(u, v). Even when P and Q are extremely simple: e.g., P is uniform on the triples {(0, 0), (0, 1), (1, 0)} and Q is a “doubly symmetric binary source”, i.e., U and V are uniform ±1 variables with correlation say 0.49, it is open if P can simulate Q. In this work, we show that whenever P is a distribution on a finite domain and Q is a 2 × 2 distribution, then the noninteractive simulation problem is decidable: specifically, given δ > 0 the algorithm runs in time bounded by some function of P and δ and either gives a noninteractive simulation protocol that is δclose to Q or asserts thatmore »

In this paper, we make partial progress on a function field version of the dynamical uniform boundedness conjecture for certain onedimensional families ${\mathcal{F}}$ of polynomial maps, such as the family $f_{c}(x)=x^{m}+c$ , where $m\geq 2$ . We do this by making use of the dynatomic modular curves $Y_{1}(n)$ (respectively $Y_{0}(n)$ ) which parametrize maps $f$ in ${\mathcal{F}}$ together with a point (respectively orbit) of period $n$ for $f$ . The key point in our strategy is to study the set of primes $p$ for which the reduction of $Y_{1}(n)$ modulo $p$ fails to be smooth or irreducible. Morton gave an algorithm to construct, for each $n$ , a discriminant $D_{n}$ whose list of prime factors contains all the primes of bad reduction for $Y_{1}(n)$ . In this paper, we refine and strengthen Morton’s results. Specifically, we exhibit two criteria on a prime $p$ dividing $D_{n}$ : one guarantees that $p$ is in fact a prime of bad reduction for $Y_{1}(n)$ , yet this same criterion implies that $Y_{0}(n)$ is geometrically irreducible. The other guarantees that the reduction of $Y_{1}(n)$ modulo $p$ is actually smooth. As an application of the second criterion, we extend results of Morton, Flynn, Poonen, Schaefer, andmore »

We consider information design in spatial resource competition, motivated by ride sharing platforms sharing information with drivers about rider demand. Each of N colocated agents (drivers) decides whether to move to another location with an uncertain and possibly higher resource level (rider demand), where the utility for moving increases in the resource level and decreases in the number of other agents that move. A principal who can observe the resource level wishes to share this information in a way that ensures a welfaremaximizing number of agents move. Analyzing the principal’s information design problem using the Bayesian persuasion framework, we study both private signaling mechanisms, where the principal sends personalized signals to each agent, and public signaling mechanisms, where the principal sends the same information to all agents. We show: 1) For private signaling, computing the optimal mechanism using the standard approach leads to a linear program with 2 N variables, rendering the computation challenging. We instead describe a computationally efficient twostep approach to finding the optimal private signaling mechanism. First, we perform a change of variables to solve a linear program with O(N^2) variables that provides the marginal probabilities of recommending each agent move. Second, we describe an efficient samplingmore »