## COMSOC-2008 list of submissions

Shortcuts to papers: 2, 3, 5, 6, 7, 8, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 62

2: Somdeb Lahiri. Consistency and the Competitive Outcome Function submission information
Abstract. In this paper we are interested in the social choice theory of package assignment problems (i.e. allocating resources, which are available and can be consumed in integer units only). Since goods are available in integer units only, the social choice theory for such problems cannot exploit any smoothness property, which may otherwise have been embedded in the preferences of the agents. This makes the outcome function approach for the study of such problems quite compelling. Our purpose here is to study outcome functions, which are efficient and consistent. We provide an example to show that the competitive social choice function may not be converse consistent. The competitive outcome function is easily observed to be efficient, consistent and converse consistent. What we are able to show here is that any efficient and consistent outcome function which is “reasonably well-behaved” for two-agent problems, must be a sub-correspondence of the competitive outcome function. Our proof of this result requires the converse consistency of the competitive outcome function. |

3: Pierre Lescanne. (Mechanical) Reasoning on Infinite Extensive Games submission information
Abstract. In order to better understand reasoning involved in analyzing infinite games in extensive form, we performed the experiments in proof assistant \Coq{} that are reported here. |

5: Haris Aziz. Complexity of comparison of influence of players in simple games submission information
Abstract. Coalitional voting games appear in different forms in multi-agent systems, social choice and threshold logic. In this paper, the complexity of comparison of influence between players in coalitional voting games is characterized. The possible representations of simple games considered are simple games represented by winning coalitions, minimal winning coalitions, weighted voting game or a multiple weighted voting game. The influence of players is gauged from the viewpoint of basic player types, desirability relations and classical power indices such as Shapley-Shubik index, Banzhaf index, Holler index, Deegan-Packel index and Chow parameters. Among other results, it is shown that for a simple game represented by minimal winning coalitions, although it is easy to verify whether a player has zero or one voting power, computing the Banzhaf value of the player is $\#$P-complete. Moreover, it is proved that multiple weighted voting games are the only representations for which it is NP-hard to verify whether the game is linear or not. For a simple game with a set $W^m$ of minimal winning coalitions and $n$ players, a $O(n.|W^m|+n^2log(n))$ algorithm is presented which returns no if the game is non-linear and returns the strict desirability ordering otherwise. The complexity of transforming simple games into compact representations is also examined. |

6: Mostapha DISS, Ahmed LOUICHI, Vincent MERLIN and Hatem SMAOUI. On the stability of a scoring rules set under the IAC hypothesis submission information
Abstract. A society facing a choice problem has also to choose the voting rule itself among a menu of different possible voting rules. In such situations consequentialism property allows us to induce voters' preferences on voting rules from preferences over alternatives. A voting rule employed to resolve the society’s choice problem is self-selective if it chooses itself when it is also used in choosing the voting rule. A menu of voting rules is said to be stable if it contains at least one self-selective voting rule at each profile of preferences on voting rules. We consider in this paper a society which will make choice among a menu constituted by three alternatives {a, b, c} and a set of the three well-known scoring voting rules {Borda, Plurality, Antiplurality}. Under the Impartial Anonymous Culture Assumption (IAC), we will derive a probability for the stability of this triplet of voting rules. For mathematical tools, we use Ehrhart polynomials in order to solve our problems. This method counts the number of lattice points inside a convex bounded polyhedron (polytope). We discuss briefly recent algorithmic solutions to this method and conclude with a look at what happens when trying to solve our problems. |

7: Jose Apesteguia and Miguel A. Ballester. On the Complexity of Rationalizing Behavior submission information
Abstract. 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. |

8: Abraham Othman and Tuomas Sandholm. The Cost and Windfall of Manipulability submission information
Abstract. A mechanism is manipulable if it is in agents’ best interest to misrepresent their private information (lie) to the center. We provide the first formal treatment of the windfall of manipulability, the seemingly paradoxical quality by which the failure of any agent to play their best manipulation yields a strictly better result than an optimal truthful mechanism. We dub such mechanisms manipulation optimal. We prove that any manipulation-optimal mechanism can have at most one manipulable type per agent. We show the existence of manipulation-optimal multiagent mechanisms with the goal of social welfare maximization, but not in dominant strategies when agents are anonymous and the mechanism is symmetric, the most common setting. For this setting, we show the existence of manipulation-optimal mechanisms when the goal is affine welfare maximization. |

12: Felix Fischer, Ariel Procaccia and Alex Samorodnitsky. On Voting Caterpillars: Approximating Maximum Degree in a Tournament by Binary Trees submission information
Abstract. 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. |

13: Georgios Chalkiadakis, Edith Elkind and Nick Jennings. Coalition Structures in Weighted Voting Games submission information
Abstract. Weighted voting games are a popular model of collaboration in multiagent systems. In such games, each agent has a weight (intuitively corresponding to resources he can contribute), and a coalition of agents wins if its total weight meets or exceeds a given threshold. Even though coalitional stability in such games is important, existing research has nonetheless only considered the stability of the grand coalition. In this paper, we introduce a model for weighted voting games with coalition structures. This is a natural extension in the context of multiagent systems, as several groups of agents may be simultaneously at work, each serving a different task. We then proceed to study stability in this context. First, we define the CS-core, a notion of the core for such settings, discuss its non-emptiness, and relate it to the traditional notion of the core in weighted voting games. We then investigate its computational properties. We show that, in contrast with the traditional setting, it is computationally hard to decide whether a game has a non-empty CS-core, or whether a given outcome is in the CS-core. However, we then provide an efficient algorithm that verifies whether an outcome is in the CS-core if all weights are small (polynomially bounded). Finally, we also suggest heuristic algorithms for checking the non-emptiness of the CS-core. |

14: Jan Broersen, Rosja Mastop, John-Jules Meyer and Paolo Turrini. A Deontic Logic for Socially Optimal Norms submission information
Abstract. 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. |

15: Ismat Beg and Nabeel Butt. BELIEF MERGING AND JUDGMENT AGGREGATION IN FUZZY SETTING submission information
Abstract. We explore how judgment aggregation and belief merging in the framework of fuzzy logic can help resolve the “Doctrinal Paradox”. We also illustrate the use of fuzzy aggregation functions in social choice theory. |

16: Noam Hazon, Paul E. Dunne, Sarit Kraus and Michael Wooldridge. How to Rig Elections and Competitions submission information
Abstract. We investigate the extent to which it is possible to rig the agenda of an election or competition so as to favor a particular candidate in the presence of imperfect information about the preferences of the electorate. We assume that what is known about an electorate is the probability that any given candidate will beat another. As well as presenting some analytical results relating to the complexity of finding and verifying agenda, we develop heuristics for agenda rigging, and investigate the performance of these heuristics for both randomly generated data and real-world data from tennis and basketball competitions. |

17: Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra and Jörg Rothe. Llull and Copeland Voting Computationally Resist Bribery and Control submission information
Abstract. 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^{alpha}, where the parameter alpha 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^{alpha} for each rational alpha, 0 \leq alpha \leq 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^0 and Copeland^1 (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 \alpha, 0 \leq alpha \leq 1, Copeland^{alpha} voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^{alpha}. We also study Copeland^{alpha} 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. |

18: Kenryo Indo. Profile Sequence Formation in the Social Choice Logic Programming submission information
Abstract. The SCLP (Social Choice Logic Programming) approach aims to model the axioms of collective decision making and to prove the classical results on preference aggregation computationally, such as Arrow's social welfare function and its variants, by using PROLOG, albeit for the smallest case. This paper aims to extend and improve the SCLP approach in two directions. First, the Cube-First Method (CFM) is proposed to improve the computational efficiency. By using the minimal set of profiles which is sufficient to prove the dictatorial result earlier in the recursion over the set of all profiles, the computation is prominently accelerated. Second, the Profile Sequence Formation (PSF) based on decisiveness-strengthen connection is argued and it is shown that it can partly simulate acceleration under the CFM. |

19: Samir SBABOU and Hatem SMAOUI. Nash equilibrium in congestion games, simplifying proofs and reducing complexity. submission information
Abstract. In recent years, several economists have had a growing interest in the study of the existence and the identification of Nash equilibrium in congestion games and potential games. Rosenthal (1973) introduced the class of symmetric congestion games and proved that they always possess a pure-strategy Nash equilibrium. Monderer and Shapley (1991) contributed to the treatment of the class of potential games and showed the relation between potential functions and Nash equilibria: the existence of an exact potential function implies the finite improvement property (FIP).Milchtaich (1996) proved Rosenthal’s result without invoking the potential function, but by using the FIP property. The aim of this work is to provide new, short and simple proof establishing the existence of Nash equilibrium in singleton congestion games and to show how to compute this equilibrium in a simple formula that allows to reduce calculation complexity. |

20: Kate Larson and Iyad Rahwan. Welfare properties of argumentation-based semantics submission information
Abstract. Since its introduction in the mid-nineties, Dung's theory of abstract argumentation frameworks has been influential in artificial intelligence. Dung viewed arguments as abstract entities with a binary defeat relation among them. This enabled extensive analysis of different (semantic) argument acceptance criteria. However, little attention was given to comparing such criteria in relation to the preferences of self-interested agents who may have conflicting preferences over the final status of arguments. In this paper, we define a number of agent preference relations over argumentation outcomes. We then analyse different argument evaluation rules taking into account the preferences of individual agents. Our framework and results inform the mediator (e.g. judge) to decide which argument evaluation rule (i.e. semantics) to use given the type of agent population involved. |

21: Amel Ben Yaghlane, Zohra Ayari, Khaled Mellouli and Thierry Denoeux. Generating "Collective" Belief Functions from Qualitative Expert Opinions using Concepts from Social Choice Theory submission information
Abstract. This paper presents a new method for constructing "collective" belief functions from qualitative expert opinions in situations where several experts are involved. Expert opinions are elicited in terms of preference relations that are aggregated using concepts from Social Choice theory, where experts stand for voters and propositions stand for candidates. Ben Yaghlane et al.' method is then used for generating "collective" belief functions from the derived collective preference profiles. This method allows the construction of the least informative belief functions in the sense of an uncertainty measure. The derived belief functions fully or partially agree with the elicited expert preference relations. |

22: Rob LeGrand and Ron K. Cytron. Approval-rating systems that never reward insincerity submission information
Abstract. 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. |

23: Mike Fellows, Frances Rosamond and Arkadii Slinko. A Protocol for Achieving a Consensus Based on the Generalised Dodgson's Rule submission information
Abstract. One of the goals of Artificial Intelligence is to create autonomous software agents which exhibit social intelligence, i.e are capable to act as a group member in various groups and, in particular, to participate in group decision making. For such agents to be programmed we need protocols which are formalizable. In this paper we are suggesting such a protocol based on one of the most famous and controversial social choice rules - Dodgson's rule. We prove that the problem of implementation of this protocol is fixed parameter tractable by proving that the corresponding language kernalizable. |

24: Arkadii Slinko and Shaun White. Extending the Theorem of Gibbard and Satterthwaite submission information
Abstract. We extend the Gibbard-Satterthwaite theorem in the following way. We prove that an onto, non-dictatorial social choice rule which is employed to choose one of at least three alternatives is safely manipulable by a single voter. This means that on occasion a voter will have an incentive to make a strategic vote and know that he will not be worse off regardless of how other voters with similar preferences would vote, sincerely or not. |

25: Fabrice Barthélémy, Mathieu Martin and Fabrice Barthélémy. Configurations study for the Banzhaf and the Shapley-Shubik indices of power submission information
Abstract. How can we count and list all the Banzhaf or Shapley-Shubik index of power configurations for a given number of players? There is no formula in the literature that may give the cardinal of such a set, and moreover, even if this formula had existed, there is no formula which gives the configuration vectors. Even if we do not present such a formula, we present a methodology which enables to determine the set of configurations and its cardinality. |

26: Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable and Toby Walsh. The complexity of manipulating stable marriage procedures submission information
Abstract. The stable marriage problem is a well-known problem of matching n men to n women to achieve a certain type of stability. Such a problem has a wide variety of practical applications, from matching resident doctors to hospitals, to matching students to schools. It has been proven that stable marriage procedures can always be manipulated. Here we study the computational complexity for this manipulation. We prove that there exist stable marriage procedures and classes of preferences which are NP-hard to manipulate. To illustrate this complexity result in more detail, we propose a modified version of the Gale-Shapley algorithm which exploits voting theory: given any voting rule, we show how to generate a corresponding stable marriage procedure. One of the attractions of this approach is that the complexity of manipulating the voting rules is maintained when passing to the stable marriage procedure: for voting rules that are computationally hard to manipulate, like STV, the corresponding stable marriage procedure is also computationally hard to manipulate. |

27: Richard Booth and Thomas Meyer. Equilibria in Social Belief Removal submission information
Abstract. In studies of multi-agent interaction, especially in game theory, the notion of {\em equilibrium} often plays a prominent role. A typical scenario for the {\em 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 {\em social belief removal} function, in which each agent, using his own {\em 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. |

28: Javier Murillo, Victor Muñoz, Dídac Busquets and Beatriz López. Egalitarian Auctions for Coordinating Agents Schedules submission information
Abstract. When selfish industries are competing for limited and shared resources, they need to coordinate their activities to handle possible conflicting situations. One way of doing such coordination is through the use of auction mechanisms to mediate between the agents. With this approach, auctions are repeatedly applied each time a resource conflict arises. However, when clearing the auction, the use of an utilitarian view can cause some problems, such as bidders dropping out of the market. To avoid that, we have introduced a priority mechanism to add fairness to the coordination process, so that the access to the resources is evenly distributed among all the agents. We have applied the proposed coordination mechanism to a waste water treatment system scenario, where different industries need to discharge their waste, according to its manufacturing plan. We have simulated the behavior of the system, and the results show that using our coordination mechanism, the plant can successfully treat most of the discharges and the industries are not affected by slight changes in their original schedules. |

29: John McCabe-Dansted. Dodgson's Rule: Approximations and Absurdity submission information
Abstract. With the Dodgson rule, cloning the electorate can change the winner, which Young (1977) considers an "absurdity". We show that removing this absurdity results in a new rule (DC) for which we can compute the winner in Polynomial time, unlike the traditional Dodgson rule. We introduce two related rules (DR and D&). Dodgson did not explicitly propose the "Dodgson rule" (Tideman, 1987); we argue that DC and DR are better realizations of the principle behind the Dodgson rule than the traditional Dodgson rule. These rules, especially D&, are also effective approxima- tions to the traditional Dodgson's rule. We show that, unlike the rules we have considered previously, the DC, DR and D& scores differ from the Dodgson score by no more than a fixed amount, and thus these new rules converge to Dodgson under any reasonable assumption on voter behaviour. |

30: chattrakul sombattheera. A Best-First Anytime Algorithm for Computing Optimal Coalition Structures submission information
Abstract. This work presents a best-first anytime algorithm for computing optimal coalition structures. The approach is novel in that it generates coalition structures based on coalition values, while existing algorithms base their generation on the structure (members and configurations) of coalitions. With our algorithm, coalition structures are generated by repeatedly choosing the best coalition, as determined using a novel metric called agent's contribution to coalition structure that we define. We have compared the performance of our algorithm against that of Rahwan et al. [5] using 20 data distributions. Our results show that our algorithm always converges on an optimal coalition structure faster. Although our algorithm terminates later (because of a simple prune mechanism being used) in half the cases, our algorithm always yields a better, or, at least, as good solution as the algorithm of Rahwan et al. |

31: Shin Sato. Informational requirements of social choice rules submission information
Abstract. 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. |

32: Felix Brandt, Felix Fischer, Paul Harrenstein and Maximilian Mair. A Computational Analysis of the Tournament Equilibrium Set submission information
Abstract. A recurring theme in the mathematical social sciences is how to select the "most desirable" elements given a binary dominance relation on a set of alternatives. Schwartz's tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions proposed so far in this context. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive solution concept refining both the Banks set and Dutta's minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard. Furthermore, we propose a heuristic that significantly outperforms the naive algorithm for computing TEQ. Early experimental results support the conjecture that TEQ is indeed monotonic. |

33: Fuad Aleskerov, Daniel Karabekyan, Remzi Sanver and Vyacheslav Yakuba. Computing the Degree of Manipulability in the Case of Multiple Choice submission information
Abstract. 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. |

34: Sébastien Konieczny and Ramon Pino Perez. Negotiation as Pointwise Merging submission information
Abstract. In the logic based framework of knowledge representation and reasoning many operators have been defined in order to capture different kinds of change: revision, update, merging and many others. There are close links between revision, update, and merging. Merging operators can be considered as extensions of revision operators to multiple belief bases. And update operators can be considered as pointwise revision, looking at each model of the base, instead of taking the base as a whole. Thus, a natural question is the following one: Are there natural operators that are pointwise merging, just as update are pointwise revision? The goal of this work is to give a positive answer to this question. In order to do that, we introduce a new class of operators: the confluence operators. These new operators can be useful for modelling negotiation processes. |

35: Lirong Xia, Vincent Conitzer, Ariel Procaccia and Jeffrey Rosenschein. Complexity of Unweighted Coalitional Manipulation Under Some Common Voting Rules submission information
Abstract. 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. |

36: Edith Elkind and Yoram Bachrach. Divide and Conquer: False-Name Manipulations in Weighted Voting Games submission information
Abstract. Weighted voting is a well-known model of cooperation among agents in decision-making domains. In such games, each of the players has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. In such games, the player's ability to influence the outcome of the game is related to its weight, but not always directly proportional to it. Usually, the agents' power is measured using a {\em power index}, such as e.g., Shapley--Shubik index. In this paper, we study how the agent can manipulate its voting power (as measured by Shapley--Shubik power index) by distributing his weight among several false identities. We call this behavior a {\em false-name manipulation}. We show that such manipulations can indeed increase an agent's power and provide upper and lower bounds on the effects of such manipulations. We then study this issue from the computational perspective, and show that checking whether a beneficial split exists is NP-hard. We also discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. |

37: Stéphane Airiau and Sandip Sen. A fair payoff distribution for myopic rational agents submission information
Abstract. 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. |

38: Christian Klamler and Daniel Eckert. A geometric approach to judgment aggregation submission information
Abstract. Don Saari developed a geometric approach to the analysis of voting paradoxes such as the Condorcet paradox or Arrow's general possibility theorem. In this paper we want to extend this approach to judgment aggregation. In particular we will use Saari's representation cubes to provide a geometric presentation of profiles and majority rule outcomes. We will then show how profile decompositions can be used to derive restrictions on the set of profiles that guarantee consistent majority outcomes. Finally, the geometric approach is used to determine the likelihood of inconsistencies. |

39: Paul Harrenstein, Tamas Mahr and Mathijs de Weerdt. A Qualitative Vickrey Auction submission information
Abstract. 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 \emph{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. |

40: Peter Biro and Eric McDermid. Three-sided stable matchings with cyclic preferences and the kidney exchange problem submission information
Abstract. Knuth (1976) asked whether the stable matching problem can be generalised to three dimensions i. e., for families containing a man, a woman and a dog. Subsequently, several authors considered the three-sided stable matching problem with cyclic preferences, where men care only about women, women only about dogs, and dogs only about men. In this paper we prove that if the preference lists may be incomplete, then the problem of deciding whether a stable matching exists, given an instance of three-sided stable matching problem with cyclic preferences is NP-complete. Considering an alternative stability criterion, strong stability, we show that the problem is NP-complete even for complete lists. These problems can be regarded as special types of stable exchange problems, therefore these results have relevance in some real applications, such as kidney exchange programs. |

41: Michael Benisch, Norman Sadeh-Koniecpol and Tuomas Sandholm. A theory of expressiveness in mechanisms submission information
Abstract. A key trend in (electronic) commerce is a demand for higher levels of expressiveness in the mechanisms that mediate interactions. We develop a theory that ties the expressiveness of mechanisms to their efficiency in a domain-independent manner. We introduce two new expressiveness measures, 1) maximum impact dimension, which captures the number of ways that an agent can impact the outcome, and 2) shatterable outcome dimension, which is based on the concept of shattering from computational learning theory. We derive an upper bound on the expected efficiency of any mechanism under its most efficient Nash equilibrium. Remarkably, it depends only on the mechanism’s expressiveness. We prove that the bound increases strictly as we allow more expressiveness. We also show that in some cases a small increase in expressiveness yields an arbitrarily large increase in the bound. Finally, we study channel-based mechanisms, which subsume most combinatorial auctions, multi-attribute mechanisms, and the Vickrey-Clarke-Groves scheme. We show that our domain-independent measures of expressiveness appropriately relate to the natural measure of expressiveness of channel-based mechanisms: the number of channels allowed. Using this bridge, our general results yield interesting implications. For example, any (channel-based) multi-item auction that does not allow rich combinatorial bids can be arbitrarily inefficient—unless agents have no private information. |

42: benamara farah, Souhila Kaci and Gabriella Pigozzi. Judgment aggregation with individual confidence scores in the decision rule submission information
Abstract. Judgment aggregation is a recent formal discipline that studies how to aggregate individual judgments to form collective decisions. Examples are expert panels, legal courts, boards, and councils. The problems investigated in this new field are relevant and common to many situations. Nevertheless, the existing procedures are idealized and, likewise the related problems of preference aggregation in social choice theory, the field is plagued by impossibility theorems. In order to escape the impossibility results, a more realistic framework is needed. The goal of this paper is to extend standard judgment aggregation to take into account the judgment status and the confidence a group member may have in the decision rule. We propose to distinguish between abstainers and neutral judgment as well as to model the notion of confidence by assigning to each criterion a normalized weight. We then show how this additional information may help us to avoid indecision in most of cases. |

43: Yann Chevaleyre, Jérôme Lang, Nicolas Maudet and Guillaume Ravilly-Abadie. Compiling the votes of a subelectorate submission information
Abstract. 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. |

44: Eric Brelsford, Piotr Faliszewski, Edith Hemaspaandra, Henning Schnoor and Ilka Schnoor. Approximability of Manipulating Elections submission information
Abstract. In this paper, we set up a framework to study approximation of manipulation, control, and bribery in elections. We show existence of approximation algorithms (even fully polynomial time approximation schemes) as well as obtain inapproximability results. In particular, we show that a large subclass of scoring protocols admits fully-polynomial time approximation schemes for the coalitional weighted manipulation problem and that if certain families of scoring protocols (e.g., veto) admitted such approximation schemes then P = NP. We also show that bribery for Borda count is NP-complete and that there is no approximation algorithm that achieves even a polynomial approximation ratio for bribery in Borda count for the case where voters have prices. |

45: Vincenzo Auletta, Paolo Penna, Giuseppe Persiano and Carmine Ventre. Alternatives to Truthfulness are Hard to Recognize submission information
Abstract. The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of \emph{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 \emph{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. |

46: Andreas Darmann, Christian Klamler and Ulrich Pferschy. Computing Spanning Trees in a Social Choice Context submission information
Abstract. This paper combines social choice theory with discrete optimization. We assume that individuals have preferences over edges of a graph that need to be aggregated. The goal is to find the socially best spanning tree. As ranking all spanning trees is becoming infeasible even for small numbers of vertices and/or edges of a graph, our interest lies in finding algorithms that determine a socially "best" spanning tree in a simple manner. This problem is closely related to the minimum (or maximum) spanning tree problem. The main result in this paper shows that for the various underlying set ranking rules discussed in this paper, using a greedy algorithm to determine the maximal spanning tree based on such a group ranking will always provide the "best" spanning tree. |

47: Nadja Betzler, Michael Fellows, Jiong Guo, Rolf Niedermeier and Frances A. Rosamond. Computing Kemeny Rankings, Parameterized by the Average KT-Distance submission information
Abstract. 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). |

48: Szymon Klarman. Judgment Aggregation as Maximization of Epistemic and Social Utility submission information
Abstract. In the paper we restate the discursive dilemma and relate it to another well-known problem regarding the rational acceptance of logically connected propositions --- the lottery paradox. We recall how the latter has been tackled by I. Levi in the decision-theoretic framework and consider the possibility of applying a similar approach to the judgment aggregation problem. Finally, we propose a method of aggregation built on the concepts of epistemic and social utility of accepting a collective judgment, which accounts for such parameters --- arguably of importance for aggregation tasks --- as the factual truth of the propositions, reliability of agents, information content (completeness) of possible collective judgments and the level of agreement between the agents. We claim that the expected utility of accepting a collective judgment depends on the degree to which all those objectives are satisfied and that groups of rational agents aim at maximizing it, while solving a judgment aggregation problems. |

49: Rolf Haenni. Aggregating Referee Scores: an Algebraic Approach submission information
Abstract. 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. |

50: Davide Grossi. From Preferences to Judgments and Back submission information
Abstract. The paper studies the interrelationships of the Preference Aggregation and Judgment Aggregation problems from the point of view of logical semantics. The result of the paper is twofold. On the one hand, the Preference Aggregation problem is viewed as a special case of the Judgment Aggregation one. On the other hand, the Judgment Aggregation problem is viewed as a special case of the Preference Aggregation one. As an example, it is shown how to import an impossibility result from each framework to the other. This shows how the aggregation of preferences and judgments can be viewed as two faces of a same coin. |

51: Dmitrii Pasechnik and Edith Elkind. Computing the nucleolus of weighted voting games submission information
Abstract. Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his {\it 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$. |

52: Victoriano Ramírez. A new proportional and impartial method for Social Choice submission information
Abstract. In this paper a new method of social choice is presented. To apply this method is necessary that the electors cast a preferential vote (total or partial). From the preferential voting an agenda (or order) is obtained to compare the alternatives and, the method chooses, secessively, the alternatives that constitute the social choice. When this method is used for an individual choice it verifies the properties of unanimity (Pareto) and Condorcet. On other hand, in multipersonal choices, it is a proportional and impartial method in front of certain behavior of the electors (that is frequent in political elections). |

53: Sami AL-MAQTARI and Habib Abdulrab. Implementation and use of Controller-Agents based prototype for Constraints Solving submission information
Abstract. We aim in this paper to present a model called Controller-Agents for Constraints Solving or CACS for short. This model is intended to be used for solving Distributed Constraint Satisfaction Problem (DCSP) which is an emerged field from the integration between two paradigms of different nature: Multi-Agent Systems (MAS) that is characterized by the autonomy and the distribution of its entities and the Constraint Satisfaction Problem paradigm (CSP) where all constraints are treated in central manner as a black-box. CACS is based on special kind of agents called Controllers. A controller role is to encapsulate and verify some constraints assigned to it. This model allows grouping constraints to form a subset that will be treated together as a local problem inside the controller. Using this model allows also handling non-binary constraints easily and directly so that no translating of constraints into binary ones is needed. Based on CACS, a prototype of DCSP solver is built. This paper presents the implementation outlines of that prototype and its usage methodology. The prototype is built in Java using general interfaces of both MAS and CSP platforms. These interfaces allow users to use the platforms of their choice providing that they implement these interfaces with the chosen platforms. |

54: Daniel Eckert. Guilbaud's Theorem: An early contribution to computational social choice? submission information
Abstract. In a paper on "the logical problem of aggregation", the French mathematician G. Th. Guilbaud (1952) has provided a logical analysis of aggregation problems antedating the recent literature on judgment aggregation. In particular he showed, how the logical structure of the agenda translates into the social structure of the decisive sets of coalitions, thereby also initiating the use of ultrafilters in social choice theory. In this note we provide a reconstruction and formal proof of what deserves to be called Guilbaud's Theorem. |

55: Antonio Palomares. Borda winner and Condorcet loser. A basic approach. submission information
Abstract. It is known that in the Borda method with standard scores, a Borda winner can not be the Condorcet loser. A very simple proof of this is given. For any other scores, examples are included in which the Borda winner is the Condorcet loser. That turn out in a characterization of the standard scores for the Borda methods. |

56: Gabor Erdelyi, Markus Nowak and Jörg Rothe. Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control submission information
Abstract. We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters' preference rankings with their approvals of candidates, and we adapt it here so as to keep its useful features with respect to approval strategies even in the presence of control actions. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control, by three, than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al. [AAIM-2008, Springer LNCS 5034, pp. 165-176, 2008]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control. |

57: Vincent Conitzer, Matthew Rognlie and Lirong Xia. Social Welfare Functions That Score Rankings and Maximum Likelihood Estimation submission information
Abstract. 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. |

58: Thuc Vu, Alon Altman and Yoav Shoham. On the Agenda Control Problem for Knockout Tournaments submission information
Abstract. Knockout tournaments are very common in practice for various settings such as sport events and sequential pairwise elimination elections. In this paper, we investigate the computational aspect of tournament agenda control, i.e., finding the agenda that maximizes the chances of a target player winning the tournament. We consider several modelings of the problem based on different constraints that can be placed on the structure of the tournament or the model of the players. In each setting, we analyze the complexity of finding the solution and show how it varies depending on the modelings of the problem. In general, constraints on the tournament structure make the problem become harder. |

59: Cedric Degremont and Lena Kurzen. Expressive Power and Complexity of Modal Logics for Cooperation: A Survey submission information
Abstract. This paper gives a survey of expressivity and complexity of normal modal logics for reasoning about cooperation and preferences. We identify a class of notions expressing local and global properties relevant for reasoning about cooperative situations involving agents that have preferences. Many of these notions correspond to game- and social choice-theoretic concepts. We specify what expressive power is required for expressing these notions. This is done by determining whether they are invariant under certain relevant operations on different classes of Kripke models and frames. A large class of known extended modal languages is specified and we show how the chosen notions can be expressed in fragments of this class. In order to determine how demanding reasoning about cooperation is in terms of computational complexity, we use known complexity results for extended modal logics and obtain for each local notion an upper bound on the complexity of modal logics expressing it. |

62: Franz Dietrich and Christian List. Majority voting on restricted domains: a summary submission information
Abstract. 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. |