COMSOC-2008 Accepted papers

We study the complexity of rationalizing choice behavior. We do so by analyzing two polar cases, and a number of intermediate ones. In our most structured case, that is where choice behavior is defined in universal choice domains and satisfies the weak axiom of revealed preference, finding the complete preorder rationalizing choice behavior is a simple matter. In the polar case, where no restric- tion whatsoever is imposed, either on choice behavior or on choice domain, finding the complete preorders that rationalize behavior turns out to be intractable. We show that the task of finding the rationalizing complete preorders is equivalent to a graph problem. This allows the search for existing algorithms in the graph theory literature, for the rationalization of choice.

Voting trees describe an iterative procedure for selecting a single vertex from a tournament. It has long been known that there is no voting tree that always singles out a vertex with maximum degree. In this paper, we study the power of voting trees in approximating the maximum degree. We give upper and lower bounds on the worst-case ratio between the degree of the vertex chosen by a tree and the maximum degree, both for the deterministic model concerned with a single fixed tree, and for randomizations over arbitrary sets of trees. Our main positive result is a randomization over surjective trees of polynomial size that provides an approximation ratio of at least 1/2. The proof is based on a connection between a randomization over caterpillar trees and a rapidly mixing Markov chain.

The paper discusses the interaction properties between preference and choice of coalitions in a strategic interaction. A language is presented to talk about the conflict between coalitionally optimal and socially optimal choices. Norms are seen as social constructions that enable to enforce socially desirable outcomes.

Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Constructive control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate's victory. An election system in which an agent can affect the result and in which recognizing the inputs on which the agent can succeed is NP-hard (respectively, polynomial-time solvable) is said to be resistant (respectively, vulnerable) to the given type of control. Aside from election systems with an NP-hard winner problem, the only systems previously known to be resistant to all the standard control types are highly artificial election systems created by hybridization.

We study a parameterized version of Copeland voting, denoted by Copeland^α, where the parameter α is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. In every previously studied constructive or destructive control scenario, we determine which of resistance or vulnerability holds for Copeland^α for each rational α, 0 ≤ α ≤ 1. In particular, we prove that Copeland^0.5, the system commonly referred to as ``Copeland voting,'' provides full resistance to constructive control. Among the systems with a polynomial-time winner problem, this is the first natural election system proven to have full resistance to constructive control. In addition, we prove that both Copeland⁰ and Copeland¹ (interestingly, the latter is an election system developed by the thirteenth-century mystic Ramon Llull) are resistant to all the standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational \α, 0 ≤ α ≤ 1, Copeland^α voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^α.

We also study Copeland^α elections under more flexible models such as microbribery and extended control, we integrate the potential irrationality of voter preferences into many of our results, and we prove our results in both the unique-winner and the nonunique-winner model. Our vulnerability results for microbribery are proven via a technique involving min-cost network flow.

Electronic communities are relying increasingly on the results of continuous polls to rate the effectiveness of their members and offerings. Sites such as eBay and Amazon solicit feedback about merchants and products, with prior feedback and results-to-date available to participants before they register their approval ratings. In such a setting, participants are understandably prone to exaggerate their approval or disapproval, so as to move the average rating in a favored direction.

We explore several protocols that solicit approval ratings and report a consensus outcome without rewarding insincerity. One such system is rationally optimal while still reporting an outcome based on the the usual notion of averaging. That system allows all participants to manipulate the outcome in turn. Although multiple equilibria exist for that system, they all report the same average approval rating as their outcome. We generalize our results to obtain a range of declared-strategy voting systems suitable for approval-rating polls.

In studies of multi-agent interaction, especially in game theory, the notion of equilibrium often plays a prominent role. A typical scenario for the belief merging problem is one in which several agents pool their beliefs together to form a consistent ``group'' picture of the world. The aim of this paper is to define and study new notions of equilibria in belief merging. To do so, we assume the agents arrive at consistency via the use of a social belief removal function, in which each agent, using his own individual removal function, removes some belief from his stock of beliefs. We examine several notions of equilibria in this setting, assuming a general framework for individual belief removal due to Booth et al. We look at their inter-relations as well as prove their existence or otherwise. We also show how our equilibria can be seen as a generalisation of the idea of taking maximal consistent subsets of agents.

The needed amount of information to make a social choice is the cost of information processing, and it is a practically important feature of social choice rules. We introduce informational aspects into the analysis of social choice rules and prove that (i) if an anonymous, neutral, and monotonic social choice rule operates on minimal informational requirements, then it is a supercorrespondence of either the plurality rule or the antiplurality rule, and (ii) if the social choice rule is furthermore Pareto efficient, then it is a supercorrespondence of the plurality rule.

The problem of the manipulability of known social choice rules in the case of multiple choice is considered. Several concepts of expanded preferences (preferences over the sets of alternatives)are elaborated. As a result of this analysis ordinal and nonordinal methods of preferences expanding are de?fined. The notions of the degree of manipulability are extended to the case under study. Using the results of theoretical investigation, 22 known social choice rules are studied via computational experiments to reveal their degree of manipulability.

In this paper, we study the computational complexity of the unweighted coalitional manipulation (UCM) problem under some common voting rules. We show that the UCM problem under maximin is NP-complete. We also show that the UCM problem under ranked pairs is NP-complete, even if there is only one manipulator. Finally, we present a polynomial-time algorithm for the UCM problem under Bucklin.

We consider the case of self-interested agents that are willing to form coalitions for increasing their individual rewards. We assume that each agent gets an individual payoff which depends on the coalition structure (CS) formed. We consider a CS to be stable if no agent has an incentive to change coalition from this CS. Stability is a desirable property of a CS: if agents form a stable CS, they do not spend further time and effort in selecting or changing CSs. When no stable CSs exist, rational agents will be changing coalitions forever unless some agents accept suboptimal results. When stable CSs exist, they may not be unique, and choosing one over the other will give an unfair advantage to some agents. In addition, it may not be possible to reach a stable CS from any CS using a sequence of myopic rational actions. We provide a payoff distribution scheme that is based on the expected utility of a rational myopic agent (an agent that changes coalitions to maximize immediate reward) given a probability distribution over the initial CS. Agents share the utility from a social welfare maximizing CS proportionally to the expected utility of the agents, which guarantees that agents receives at least as much as their expected utility from myopic behavior. This ensures sufficient incentives for the agents to use our protocol.

The negative conclusions of the Gibbard-Satterthwaite theorem—that only dictatorial social choice functions are non-manipulable—can be overcome by restricting the class of admissible preference profiles. A common approach is to assume that the preferences of the agents can be represented by quasilinear utility functions. This restriction allows for the positive results of the Vickrey auction and the Vickrey-Clarke-Groves mechanism. Quasilinear preferences, however, involve the controversial assumption that there is some commonly desired commodity or numeraire—money, shells, beads, etcetera—the utility of which is commensurable with the utility of the other alternatives in question. We propose a generalization of the Vickrey auction, which does not assume the agents' preferences being quasilinear but still has some of its desirable properties. In this auction a bid can be any alternative, rather than just a monetary bid. Such an auction is also applicable to situations where no numeraire is available, when there is a fixed budget, or when money is no issue. In the presence of quasilinear preferences, however, the traditional Vickrey turns out to be a special case. In order to sidestep the Gibbard-Satterthwaite theorem, we restrict the preferences of the bidders. We show that this qualitative Vickrey auctions always has a dominant strategy equilibrium, which moreover invariably yields a weakly Pareto efficient outcome.

In many practical situations where agents vote for making a common decision, the votes do not come all together at the same time (for instance, when voting about a date for a meeting, it often happens that one or two participants express their preferences later than others). In such situations, we might want to preprocess the information given by the subelectorate (consisting of those voters who have expressed their votes) so as to ``compile'' the known votes for the time when the latecomers will have expressed their votes. We study the amount of space necessary to such a compilation, in function of the voting rule used, the number of candidates, the number of voters who have already expressed their votes and the number of remaining voters. We position our results with respect to existing work, noticeably on vote elicitation and communication complexity.

The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of truthful implementations in which truth-telling is always the best response of the players. The Revelation Principle says that one can focus on truthful implementations without loss of generality (if there is no truthful implementation then there is no implementation at all). Green and Laffont (1986) showed that, in the scenario in which players' responses can be partially verified, the revelation principle holds only in some particular cases.

When the Revelation Principle does not hold, non-truthful implementations become interesting since they might be the only way to implement a social choice function of interest. In this work we show that, although non-truthful implementations may exist, they are hard to find. Namely, it is NP-hard to decide if a given social choice function can be implemented in a non-truthful manner, or even if it can be implemented at all. This is in contrast to the fact that truthful implementability can be recognized efficiently, even when partial verification of the agents is allowed. Our results also show that there is no ``simple'' characterization of those social choice functions for which it is worth looking for non-truthful implementations.

The computation of Kemeny scores is central to many applications in the context of rank aggregation. Unfortunately, the problem is NP-hard. Extending our previous work (AAIM08), we show that the Kemeny score of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter "average pairwise Kendall-Tau distance d_a". We describe a fixed-parameter algorithm with running time O^*(4^d_a).

This paper presents a quantitative solution to the problem of aggregating referee scores for documents submitted to peer-reviewed conferences or scientific journals. The proposed approach is a particular application of the Dempster-Shafer theory to a very restricted setting, from which an interesting algebraic framework results. The paper investigates the algebraic properties of this framework and shows how to apply it to the score aggregation and document ranking problems.

Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his weight, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al.~\cite{eggw} studied the complexity of stability-related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result. In this paper, we solve an open problem posed in~\cite{eggw} by showing that the nucleolus can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players $n$ and the maximum weight W.

A social welfare function (SWF) takes a set of votes (linear orders over a set of alternatives) as input, and produces one or more rankings (also linear orders over the alternatives) as output. Such functions have many applications, for example, aggregating the preferences of multiple agents, or merging rankings (of, say, webpages) into a single ranking. The key issue is choosing an SWF to use. One natural and previously studied approach is to assume that there is an unobserved ``correct'' ranking, and the votes are noisy estimates of this. Then, we can use the SWF that always chooses the maximum likelihood estimate (MLE) of the correct ranking. In this paper, we define simple ranking scoring functions (SRSFs) and show that the class of neutral SRSFs is exactly the class of neutral SWFs that are MLEs for some noise model. We also define extended ranking scoring functions (ERSFs) and show a condition under which these coincide with SRSFs. We study key properties such as consistency and continuity, and consider some example SWFs. In particular, we study Single Transferable Vote (STV), a commonly used SWF, showing that it is an ERSF but not an SRSF, thereby clarifying the extent to which it is an MLE function. This also gives a new perspective on how ties should be broken under STV. We leave some open questions.

In judgment aggregation, unlike preference aggregation, not much is known about domain restrictions that guarantee consistent majority outcomes. We introduce several conditions on individual judgments sufficient for consistent majority judgments. Some are based on global orders of propositions or individuals, others on local orders, still others not on orders at all. Some generalize classic social-choice- theoretic domain conditions, others have no counterpart. Our most general condition generalizes Seni's triplewise value-restriction, itself the most general classic condition. We also give a new characterization theorem: for a large class of domains, if there exists any aggregation function satisfying some democratic conditions, then majority voting is the unique such function. Taken together, our results provide new support for the robustness of majority rule.