 NSFPAR ID:
 10101069
 Date Published:
 Journal Name:
 Journal of Artificial Intelligence Research
 Volume:
 64
 ISSN:
 10769757
 Page Range / eLocation ID:
 315 to 355
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Many societal decision problems lie in highdimensional continuous spaces not amenable to the voting techniques common for their discrete or singledimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a metaalgorithm called Iterative Local Voting for collective decisionmaking in this setting, in which voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm. In general, such schemes do not converge, or, when they do, the resulting solution does not have a natural description. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to plausible solutions in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution. We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 4,000 workers, employing neighborhoods defined by §L1, §L2 and §L∞ balls. We make several observations that inform future implementations of such a procedure.more » « less

null (Ed.)We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to betterinformed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a nonlocal delegation mechanism that does provably outperform direct voting under mild assumptions about voters.more » « less

We consider an underdetermined noisy linear regression model where the minimumnorm interpolating predictor is known to be consistent, and ask: can uniform convergence in a norm ball, or at least (following Nagarajan and Kolter) the subset of a norm ball that the algorithm selects on a typical input set, explain this success? We show that uniformly bounding the difference between empirical and population errors cannot show any learning in the norm ball, and cannot show consistency for any set, even one depending on the exact algorithm and distribution. But we argue we can explain the consistency of the minimalnorm interpolator with a slightly weaker, yet standard, notion: uniform convergence of zeroerror predictors in a norm ball. We use this to bound the generalization error of low (but not minimal) norm interpolating predictors.more » « less

Debates over racial voting, and over policies to combat vote dilution, turn on the extent to which groups’ voting preferences differ and vary across geography. We present the first study of racial voting patterns in every congressional district (CD) in the United States. Using largesample surveys combined with aggregate demographic and election data, we find that nationallevel differences across racial groups explain 60% of the variation in districtlevel voting patterns, whereas geography explains 30%. Black voters consistently choose Democratic candidates across districts, whereas Hispanic and white voters’ preferences vary considerably across geography. Districts with the highest racial polarization are concentrated in the parts of the South and Midwest. Importantly, multiracial coalitions have become the norm: in most CDs, the winning majority requires support from nonwhite voters. In arriving at these conclusions, we make methodological innovations that improve the precision and accuracy when modeling sparse survey data.

We develop a convex analytic approach to analyze finite width twolayer ReLU networks. We first prove that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set, where simple solutions are encouraged via its convex geometrical properties. We then leverage this characterization to show that an optimal set of parameters yield linear spline interpolation for regression problems involving one dimensional or rankone data. We also characterize the classification decision regions in terms of a kernel matrix and minimum `1norm solutions. This is in contrast to Neural Tangent Kernel which is unable to explain predictions of finite width networks. Our convex geometric characterization also provides intuitive explanations of hidden neurons as autoencoders. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints. Then, we apply certain convex relaxations and introduce a cuttingplane algorithm to globally optimize the network. We further analyze the exactness of the relaxations to provide conditions for the convergence to a global optimum. Our analysis also shows that optimal network parameters can be also characterized as interpretable closedform formulas in some practically relevant special cases.more » « less