Motivated by a radically new peer review system that the National Science Foundation recently experimented with, we study peer review systems in which proposals are reviewed by PIs who have submitted proposals themselves. An (m,k)-selection mechanism asks each PI to review m proposals, and uses these reviews to select (at most) k proposals. We are interested in impartial mechanisms, which guarantee that the ratings given by a PI to others' proposals do not affect the likelihood of the PI's own proposal being selected. We design an impartial mechanism that selects a k-subset of proposals that is nearly as highly rated as the one selected by the non-impartial (abstract version of) the NSF pilot mechanism, even when the latter mechanism has the "unfair" advantage of eliciting honest reviews.

We study voting games on binary issues, where voters might hold an objective over some issues at stake, while willing to strike deals on the remaining ones, and can influence one another’s voting decision before the vote takes place. We analyse voters’ rational behaviour in the resulting two-phase game, showing under what conditions undesirable equilibria can be removed as an effect of the pre-vote phase.

The Gibbard-Satterthwaite theorem implies the ubiquity of manipulators — voters who could change the election outcome in their favor by unilaterally modifying their vote. In this paper, we ask what happens if a given profile admits several such voters. We model strategic interactions among Gibbard–Satterthwaite manipulators as a normal-form game. We classify the 2-by-2 games that can arise in this setting for two simple voting rules, namely Plurality and Borda, and study the complexity of determining whether a given manipulative vote weakly dominates truth-telling, as well as existence of Nash equilibria.

Recent work has shown that the quality of work produced in a crowdsourcing working session can be influenced by the presence of performance-contingent financial incentives, such as bonuses for exceptional performance, in the session. We take an algorithmic approach to decide when to offer bonuses in a working session to improve the overall utility that a requester derives from the session. Specifically, we propose and train an input-output hidden Markov model to learn the impact of bonuses on work quality and then use this model to dynamically decide whether to offer a bonus on each task in a working session to maximize a requester’s utility. Experiments on Amazon Mechanical Turk show that our approach leads to higher utility for the requester than fixed and random bonus schemes do. Simulations on synthesized data sets further demonstrate the robustness of our approach against different worker population and worker behavior in improving requester utility.

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. While finding successful manipulations or agenda controls is tractable for both procedures, our real-world experimental results indicate that most elections cannot be manipulated by a few voters and agenda control is typically impossible. If the voter preferences are incomplete, then finding possible winners is NP-hard for both procedures. Whereas finding necessary winners is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive one.

Unfair rating attacks happen in existing trust and reputation systems, lowering the quality of the systems. There exists a formal model that measures the maximum impact of independent attackers [Wang et al., 2015] — based on information theory. We improve on these results in multiple ways: (1) we alter the methodology to be able to reason about colluding attackers as well, and (2) we extend the method to be able to measure the strength of any attacks (rather than just the strongest attack). Using (1), we identify the strongest collusion attacks, helping construct robust trust system. Using (2), we identify the strength of (classes of) attacks that we found in the literature. Based on this, we help to overcome a shortcoming of current research into collusion-resistance — specific (types of) attacks are used in simulations, disallowing direct comparisons between analyses of systems.

Voting rules are powerful tools that allow multiple agents to aggregate their preferences in order to reach joint decisions. A common flaw of some voting rules, known as the no-show paradox, is that agents may obtain a more preferred outcome by abstaining from an election. We study strategic abstention for set-valued voting rules based on Kelly's and Fishburn's preference extensions. Our contribution is twofold. First, we show that, whenever there are at least five alternatives, every Pareto-optimal majoritarian voting rule suffers from the no-show paradox with respect to Fishburn's extension. This is achieved by reducing the statement to a finite---yet very large---problem, which is encoded as a formula in propositional logic and then shown to be unsatisfiable by a SAT solver. We also provide a human-readable proof which we extracted from a minimal unsatisfiable core of the formula. Secondly, we prove that every voting rule that satisfies two natural conditions cannot be manipulated by strategic abstention with respect to Kelly's extension. We conclude by giving examples of well-known Pareto-optimal majoritarian voting rules that meet these requirements.

List of committee members on the program committees of the IJCAI 2015 conference.

What does it mean for an algorithm to be biased? In U.S. law, unintentional bias is encoded via disparate impact, which occurs when a selection process has widely different outcomes for different groups, even as it appears to be neutral. This legal determination hinges on a definition of a protected class (ethnicity, gender, religious practice) and an explicit description of the process. When the process is implemented using computers, determining disparate impact (and hence bias) is harder. It might not be possible to disclose the process. In addition, even if the process is open, it might be hard to elucidate in a legal setting how the algorithm makes its decisions. Instead of requiring access to the algorithm, we propose making inferences based on the data the algorithm uses. We make four contributions to this problem. First, we link the legal notion of disparate impact to a measure of classification accuracy that while known, has received relatively little attention. Second, we propose a test for disparate impact based on analyzing the information leakage of the protected class from the other data attributes. Third, we describe methods by which data might be made unbiased. Finally, we present empirical evidence supporting the effectiveness of our test for disparate impact and our approach for both masking bias and preserving relevant information in the data. Interestingly, our approach resembles some actual selection practices that have recently received legal scrutiny.

The Boltzmann machine provides a useful framework to learn highly complex, multimodal and multiscale data distributions that occur in the real world. The default method to learn its parameters consists of minimizing the Kullback-Leibler (KL) divergence from training samples to the Boltzmann model. We propose in this work a novel approach for Boltzmann training which assumes that a meaningful metric between observations is given. This metric can be represented by the Wasserstein distance between distributions, for which we derive a gradient with respect to the model parameters. Minimization of this new Wasserstein objective leads to generative models that are better when considering the metric and that have a cluster-like structure. We demonstrate the practical potential of these models for data completion and denoising, for which the metric between observations plays a crucial role.