skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


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 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.  more » « less
Award ID(s):
1814152
PAR ID:
10358321
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Journal of Artificial Intelligence Research
Volume:
72
ISSN:
1076-9757
Page Range / eLocation ID:
137 to 183
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Advances in neural information processing systems)
    Oh, A; Naumann, T; Globerson, A; Saenko, K; Hardt, M; Levine, S (Ed.)
    Liquid democracy with ranked delegations is a novel voting scheme that unites the practicability of representative democracy with the idealistic appeal of direct democracy: Every voter decides between casting their vote on a question at hand or delegating their voting weight to some other, trusted agent. Delegations are transitive, and since voters may end up in a delegation cycle, they are encouraged to indicate not only a single delegate, but a set of potential delegates and a ranking among them. Based on the delegation preferences of all voters, a delegation rule selects one representative per voter. Previous work has revealed a trade-off between two properties of delegation rules called anonymity and copy-robustness. To overcome this issue we study two fractional delegation rules: Mixed Borda branching, which generalizes a rule satisfying copy-robustness, and the random walk rule, which satisfies anonymity. Using the Markov chain tree theorem, we show that the two rules are in fact equivalent, and simultaneously satisfy generalized versions of the two properties. Combining the same theorem with Fulkerson's algorithm, we develop a polynomial-time algorithm for computing the outcome of the studied delegation rule. This algorithm is of independent interest, having applications in semi-supervised learning and graph theory. 
    more » « less
  2. ; (, Operations Research)
    We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly polynomial Duan–Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges—that is, pairs of agents and goods that must correspond to the best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges or, if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time. 
    more » « less
  3. ; (, Computation + Journalism Symposium)
    This paper presents a crowdsourced auditing framework for news aggregators and applies it to the trending section of Apple News. The framework audits the aggregator algorithm, determining the refresh interval and detecting the presence of "adaptation" (an aggregator presenting different headlines based on a user's location or individual preferences). It is also used for a content audit which tabulates the distribution of news sources found in the aggregator. We deploy this framework on the trending stories section of Apple News, observing (1) a refresh interval of approximately 60 minutes, (2) adaptation at the user level, and (3) a unique distribution of news sources that prompts further investigation. 
    more » « less
  4. ; ; ; (, 2018 IEEE Conference on Control Technology and Applications (CCTA))
    This paper considers optimization problems of energy demand networks including aggregators and investigates strategic behavior of the aggregators. The participants of the network are a utility company, who plays a role of energy supply source, aggregators and a large number of consumers. We suppose that the network will be optimized by price response based or, in other words, market based optimization processes. We also suppose that the aggregator has a strategic parameter in its cost function and, by choosing the parameter strategically, the aggregator will try to pursue its own benefit. This general problem formulation will apply to a specific problem setting, where the aggregator possess battery storage with different specifications: The one is high-performance and expensive and the other is low-performance and cheap. The aggregator will choose total capacity of storage to be installed and a ratio of high-performance storage to low-performance storage as the strategic parameters and try to increase its own benefit. By using numerical examples, we show that the strategic decision making by the aggregator could provide useful insights in qualitative analysis of energy demand networks. 
    more » « less
  5. ; (, Advanced Nonlinear Studies)
    Abstract Let u u be a nontrivial harmonic function in a domain D ⊂ R d D\subset {{\mathbb{R}}}^{d} , which vanishes on an open set of the boundary. In a recent article, we showed that if D D is a C 1 {C}^{1} -Dini domain, then, within the open set, the singular set of u u , defined as { X ∈ D ¯ : u ( X ) = 0 = ∣ ∇ u ( X ) ∣ } \left\{X\in \overline{D}:u\left(X)=0=| \nabla u\left(X)| \right\} , has finite ( d − 2 ) \left(d-2) -dimensional Hausdorff measure. In this article, we show that the assumption of C 1 {C}^{1} -Dini domains is sharp, by constructing a large class of non-Dini (but almost Dini) domains whose singular sets have infinite ℋ d − 2 {{\mathcal{ {\mathcal H} }}}^{d-2} -measures. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email