skip to main content

Title: 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 » domain, that is, whether X admits an aggregator that is non-dictatorial even when restricted to any two positions for each issue. As in the case of possibility domains, the algorithm also constructs in polynomial time a uniform non-dictatorial aggregator, if one exists. Then, we turn our attention to the case where X is given implicitly, either as the set of assignments satisfying a propositional formula, or as a set of consistent evaluations of a sequence of propositional formulas. In both cases, we provide bounds to the complexity of deciding if X is a (uniform) possibility domain. Finally, we extend our results to four types of aggregators that have appeared in the literature: generalized dictatorships, whose outcome is always an element of their input, anonymous aggregators, whose outcome is not affected by permutations of their input, monotone, whose outcome does not change if more individuals agree with it and systematic, which aggregate every issue in the same way. « less
; ;
Award ID(s):
Publication Date:
Journal Name:
Journal of Artificial Intelligence Research
Page Range or eLocation-ID:
137 to 183
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract
    Site description. This data package consists of data obtained from sampling surface soil (the 0-7.6 cm depth profile) in black mangrove (Avicennia germinans) dominated forest and black needlerush (Juncus roemerianus) saltmarsh along the Gulf of Mexico coastline in peninsular west-central Florida, USA. This location has a subtropical climate with mean daily temperatures ranging from 15.4 °C in January to 27.8 °C in August, and annual precipitation of 1336 mm. Precipitation falls as rain primarily between June and September. Tides are semi-diurnal, with 0.57 m median amplitudes during the year preceding sampling (U.S. NOAA National Ocean Service, Clearwater Beach, Florida, station 8726724). Sea-level rise is 4.0 ± 0.6 mm per year (1973-2020 trend, mean ± 95 % confidence interval, NOAA NOS Clearwater Beach station). The A. germinans mangrove zone is either adjacent to water or fringed on the seaward side by a narrow band of red mangrove (Rhizophora mangle). A near-monoculture of J. roemerianus is often adjacent to and immediately landward of the A. germinans zone. The transition from the mangrove to the J. roemerianus zone is variable in our study area. An abrupt edge between closed-canopy mangrove and J. roemerianus monoculture may extend for up to several hundred metersMore>>
  2. 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 »to maintaining average-case time polynomial in $n\log \max_i d_i$ when $F$ has more terms.« less
  3. 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 »no protocol gets O(δ)-close to Q. The main challenge to such a result is determining explicit (computable) convergence bounds on the number n of samples that need to be drawn from P(x, y) to get δ-close to Q. We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.« less
  4. 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 »Stoll by giving new examples of good reduction of $Y_{1}(n)$ for several primes dividing $D_{n}$ when $n=7,8,11$ , and $f_{c}(x)=x^{2}+c$ . The proofs involve a blend of arithmetic and complex dynamics, reduction theory for curves, ramification theory, and the combinatorics of the Mandelbrot set.« less
  5. 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 »procedure over sets of agents consistent with these optimal marginal probabilities; the optimal private mechanism then asks the sampled set of agents to move and the rest to stay. 2) For public signaling, we first show the welfare-maximizing equilibrium given any common belief has a threshold structure. Using this, we show that the optimal public mechanism with respect to the sender-preferred equilibrium can be computed in polynomial time. 3) We support our analytical results with numerical computations that show the optimal private and public signaling mechanisms achieve substantially higher social welfare when compared with no-information and full-information benchmarks.« less