Many societal decision problems lie in high-dimensional continuous spaces not
amenable to the voting techniques common for their discrete or
single-dimensional counterparts. These problems are typically discretized
before running an election or decided upon through negotiation by
representatives. We propose a algorithm called {\sc Iterative Local Voting} for
collective decision-making in this setting. In this algorithm, 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,
with the size of the ball shrinking at a specified rate.
We first prove the convergence of this algorithm under appropriate choices of
neighborhoods to Pareto optimal solutions with desirable fairness properties 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 2,000 workers,
employing neighborhoods defined by $\mathcal{L}^1, \mathcal{L}^2$ and
$\mathcal{L}^\infty$ balls. We make several observations that inform future
implementations of such a procedure.
A major challenge in obtaining large-scale evaluations, e.g., product or
service reviews on online platforms, labeling images, grading in online
courses, etc., is that of eliciting honest responses from agents in the absence
of verifiability. We propose a new reward mechanism with strong incentive
properties applicable in a wide variety of such settings. This mechanism has a
simple and intuitive output agreement structure: an agent gets a reward only if
her response for an evaluation matches that of her peer. But instead of the
reward being the same across different answers, it is inversely proportional to
a popularity index of each answer. This index is a second order population
statistic that captures how frequently two agents performing the same
evaluation agree on the particular answer. Rare agreements thus earn a higher
reward than agreements that are relatively more common.
In the regime where there are a large number of evaluation tasks, we show
that truthful behavior is a strict Bayes-Nash equilibrium of the game induced
by the mechanism. Further, we show that the truthful equilibrium is
approximately optimal in terms of expected payoffs to the agents across all
symmetric equilibria, where the approximation error vanishes in the number of
evaluation tasks. Moreover, under a mild condition on strategy space, we show
that any symmetric equilibrium that gives a higher expected payoff than the
truthful equilibrium must be close to being fully informative if the number of
evaluations is large. These last two results are driven by a new notion of an
agreement measure that is shown to be monotonic in information loss. This
notion and its properties are of independent interest.