The Condorcet Jury Theorem justifies the wisdom of crowds and lays the foundations of the ideology of the democratic regime. However, the Jury Theorem and most of its extensions focus on two alternatives and none of them quantitatively evaluate the effect of agents’ strategic behavior on the mechanism’s truth-revealing power. We initiate a research agenda of quantitatively extend- ing the Jury Theorem with strategic agents by characterizing the price of anarchy (PoA) and the price of stability (PoS) of the common interest Bayesian voting games for three classes of mechanisms: plurality, MAPs, and the mechanisms that satisfy anonymity, neutrality, and strategy-proofness (w.r.t. a set of natural probabil- ity models). We show that while plurality and MAPs have better best-case truth-revealing power (lower PoS), the third class of mechanisms are more robust against agents’ strategic behavior (lower PoA).

We introduce a class of extensive form games whereplayers might not be able to foresee the possible consequences of their decisions and form a model of theiropponents which they exploit to achieve a more profitable outcome. We improve upon existing models ofgames with limited foresight, endowing players with theability of higher order reasoning and proposing a novelsolution concept to address intuitions coming from realgame play. We analyse the resulting equilibria, devisingan effective procedure to compute them.

Hedonic games are a well-studied model of coalition formation, in which selfish agents are partitioned into disjoint sets and agents care about the make-up of the coalition they end up in. The computational problems of finding stable, optimal, or fair outcomes tend to be computationally intractable in even severely restricted instances of hedonic games. We introduce the notion of a graphical hedonic game and show that, in contrast, on classes of graphical hedonic games whose underlying graphs are of bounded treewidth and degree, such problems become easy. In particular, problems that can be specified through quantification over agents, coalitions, and (connected) partitions can be decided in linear time. The proof is by reduction to monadic second order logic. We also provide faster algorithms in special cases, and show that the extra condition of the degree bound cannot be dropped. Finally, we note that the problem of allocating indivisible goods can be modelled as a hedonic game, so that our results imply tractability of finding fair and efficient allocations on appropriately restricted instances.

Hedonic games provide a model of coalition formation in which a set of agents is partitioned into coalitions and the agents have preferences over which set they belong to. Recently, Aziz et. al. (2014) have initiated the study of hedonic games with dichotomous preferences, where each agent either approves or disapproves of a given coalition. In this work, we study the computational complexity of questions related to finding optimal and stable partitions in dichotomous hedonic games under various ways of restricting and representing the collection of approved coalitions. Encouragingly, many of these problems turn out to be polynomial-time solvable. In particular, we show that an individually stable outcome always exists and can be found in polynomial time. We also provide efficient algorithms for cases in which agents approve only few coalitions, in which they only approve intervals, and in which they only approve sets of size 2 (the roommates case). These algorithms are complemented by NP-hardness results, especially for representations that are very expressive, such as in the case when agents' goals are given by propositional formulas.

Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. A recent body of work, however, has shown that many of the NP-hardness shields, previously obtained, vanish when the electorate has single-peaked or nearly single-peaked preferences. In light of these results, we investigate whether it is possible to reimpose NP-hardness shields for such electorates by allowing the voters to specify partial preferences instead of insisting they cast complete ballots. In particular, we show that in single-peaked and nearly single-peaked electorates, if voters are allowed to submit top-truncated ballots, then the complexity of manipulation and bribery for many voting rules increases from being in P to being NP-complete.

m CP-nets are an expressive and intuitive formalism based on CP-nets to reason about preferences of groups of agents. The dominance semantics of mCP-nets is based on the concept of voting, and different voting schemes give rise to different dominance semantics for the group. Unlike CP-nets, which received an extensive complexity analysis, m CP-nets, as reported multiple times in the literature, lack a precise study of the voting tasks' complexity. Prior to this work, only a complexity analysis of brute-force algorithms for these tasks was available, and this analysis only gave EXPTIME upper bounds for most of those problems. In this paper, we start to fill this gap by carrying out a precise computational complexity analysis of voting tasks on acyclic binary polynomially connected m CP-nets whose constituents are standard CP-nets. Interestingly, all these problems actually belong to various levels of the polynomial hierarchy, and some of them even belong to PTIME or LOGSPACE. Furthermore, for most of these problems, we provide completeness results, which show tight lower bounds for problems that (up to date) did not have any explicit non-obvious lower bound.

Over the past two decades, water markets have been successfully fielded in countries such as Australia, the United states, Chile, China, etc. Water users, mainly irrigators, have benefited immensely from water markets. However, the current water market design also faces certain serious barriers. It has been pointed out that transaction costs, which exists in most markets, induce great welfare loss. For example, for water markets in western China discussed in this paper, the influence of transaction costs is significant. Another important barrier is the locality of trades due to geographical constraints. Based on the water market at Xiying Irrigation, one of the most successful water market in western China, we model the water market as a graph with minimum transaction thresholds on edges. Our goal is to maximize the transaction volume or welfare. We prove that the existence of transaction costs results in no polynomial time approximation scheme (PTAS) to maximize social welfare (MAX SNP-hard). The complexities on special graphs are also presented. From a practical point of view, however, optimal social welfare can be obtained via a well-designed mixed integer linear program and can be approximated near optimally at a large scale via a heuristic algorithm. Both algorithms are tested on data sets generated from real historical trading data. Our study also suggests the importance of reducing transaction costs, for example, institutional costs in water market design. Our work opens a potentially important avenue of market design within the agenda of computational sustainability.

The fairness notion of maximin share (MMS) guarantee underlies a deployed algorithm for allocating indivisible goods under additive valuations. Our goal is to understand when we can expect to be able to give each player his MMS guarantee. Previous work has shown that such an MMS allocation may not exist, but the counterexample requires a number of goods that is exponential in the number of players; we give a new construction that uses only a linear number of goods. On the positive side, we formalize the intuition that these counterexamples are very delicate by designing an algorithm that provably finds an MMS allocation with high probability when valuations are drawn at random.

In this paper we expand the standard Hotelling-Downs model of spatial competition to a setting where clients do not necessarily choose their closest candidate (retail product or political). Specifically, we consider a setting where clients may disavow all candidates if there is no candidate that is sufficiently close to the client preferences. Moreover, if there are multiple candidates that are sufficiently close, the client may choose amongst them at random. We show the existence of Nash Equilibria for some such models, and study the price of anarchy and stability in such scenarios.

We introduce a new family of judgment aggregation rules, called the binomial rules, designed to account for hidden dependencies between some of the issues being judged. To place them within the landscape of judgment aggregation rules, we analyse both their axiomatic properties and their computational complexity, and we show that they contain both the well-known distance-based rule and the basic rule returning the most frequent overall judgment as special cases. To evaluate the performance of our rules empirically, we apply them to a dataset of crowdsourced judgments regarding the quality of hotels extracted from the travel website TripAdvisor. In our experiments we distinguish between the full dataset and a subset of highly polarised judgments, and we develop a new notion of polarisation for profiles of judgments for this purpose, which may also be of independent interest.