On the Computational Complexity of Non-Dictatorial Aggregation
We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial 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 non-dictatorial, operates separately on each issue, and returns values among those cast by the society on each issue. We design a polynomial-time 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 non-dictatorial 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 polynomial-time algorithm that decides whether X is a uniform possibility more »
- Award ID(s):
- 1814152
- Publication Date:
- NSF-PAR ID:
- 10358321
- Journal Name:
- Journal of Artificial Intelligence Research
- Volume:
- 72
- Page Range or eLocation-ID:
- 137 to 183
- ISSN:
- 1076-9757
- 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 average-case polynomial-time 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 sub-class of “non-interactive” simulation problems, a well-studied class of problems in information theory. A non-interactive 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 non-interactive simulation problem is decidable: specifically, given δ > 0 the algorithm runs in time bounded by some function of P and δ and either gives a non-interactive 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 one-dimensional 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 co-located 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 welfare-maximizing 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 two-step 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 »