Umberto Grandi
email: umberto.grand@irit.fr

Davide Grossi
email: d.grossi@rug.nlp.turrini@warwick.ac.uk

Paolo Turrini

We study voting games on binary issues, where voters hold an objective over the outcome of the collective decision and are allowed, before the vote takes place, to negotiate their ballots with the other participants. We analyse the voters' rational behaviour in the resulting two-phase game when ballots are aggregated via non-manipulable rules and, more specifically, quota rules. We show under what conditions undesirable equilibria can be removed and desirable ones sustained as a consequence of the pre-vote phase.

1. This research direction was given particular momentum by

Introduction

Group decision-making is a topic of increasing relevance for Artificial Intelligence (AI). Addressing the problem of how groups of self-interested, autonomous entities can take the "right" decisions together is key to achieve intelligent behaviour in systems dependent on the interaction of autonomous entities. Against this backdrop, social choice theory has by now an established place in the toolbox of AI and, especially, multi-agent systems (henceforth, MAS), see, e.g., [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations[END_REF], Brandt, Conitzer, Endriss, Lang, and Procaccia (2016). Voting in particular has been extensively studied as a prominent group decision-making paradigm in MAS. Despite this, only a recent body of literature is starting to focus on voting as a form of strategic, non-cooperative, interaction, see, e.g., [START_REF] Desmedt | Equilibria of plurality voting with abstentions[END_REF], [START_REF] Xia | Stackelberg voting games: Computational aspects and paradoxes[END_REF], [START_REF] Obraztsova | Plurality voting with truthbiased agents[END_REF], [START_REF] Meir | A local-dominance theory of voting equilibria[END_REF], [START_REF] Elkind | Gibbard-satterthwaite games[END_REF], [START_REF] Obraztsova | Trembling hand equilibria of plurality voting[END_REF]. 1 More specifically-and this is the focus of the current contribution-no work with the notable exception of the literature on iterative voting [START_REF] Meir | Iterative voting[END_REF], is a recent survey on this topic) has ever studied how voting behavior in rational agents is influenced by strategic forms of interaction that precede voting, like persuasion, or negotiation. Literature in social choice has recognised that interaction preceding voting can be an effective tool to induce opinion change and achieve compromise solutions [START_REF] Dryzek | Social choice theory and deliberative democracy: A reconciliation[END_REF][START_REF] List | Group communication and the transformation of judgments: An impossibility result[END_REF] while in game theory pre-play negotiations are known to be effective in overcoming inefficient outcomes caused by players' individual rationality [START_REF] Jackson | Endogenous games and mechanisms: Side payments among players[END_REF].

Rational, Truthful, but Inefficient Votes

Consider a multiple referendum, where a group of voters cast yes/no opinions on a number of issues, which are then aggregated independently in order to obtain the group's opinion on those issues. An instance of this situation is represented in the following table :   Issue 1 Issue 2 Issue 3

Voter 1 1 0 0 Voter 2 0 1 0 Voter 3 0 0 1 Majority 0 0 0

In the example above, three voters express their binary opinions on each of three issues (1 for acceptance, 0 for rejection), which are aggregated one by one using the majority rule. Voters typically approach such a referendum with some preference over its outcomes. So, enriching the example, let us assume that each voter i is interested in having the group accept issue i, and is indifferent about the remaining two issues. Given these goals, it is rational for each voter to cast a truthful vote, that is a vote in which each voter i accepts issue i: if the voter is not pivotal its vote will not count, but if it is pivotal, casting a truthful vote will make its own opinion become majority.

The example-which is also an instance of the so-called multiple election paradox [START_REF] Brams | The paradox of multiple elections[END_REF])-shows a situation in which truthful voting leads to an inefficient majority. That is, the outcome of the majority rule rejects all issues, and in so doing fails to meet the goal of each voter. Importantly, in the example above there are a number of profiles that would lead to an efficient majority (e.g., the profile where each voter accepts every issue). Even when sincere voting is rational, its outcome may turn out to be inefficient. As we will see, this is not a feature of the majority rule alone, but of a large class of well-behaved aggregation rules. Understanding mechanisms which can resolve such inefficiencies is, we argue, an important step towards the development of human-level group decision-making capabilities in artificial intelligence.

Contribution and Scientific Context

In this paper we study pre-vote negotiations in voting games over binary issues, where voters hold a simple type of lexicographic preference over the set of issues: they hold an objective about a subset of them while they are willing to strike deals on the remaining ones. Voters can influence one another before casting their ballots by transferring utility in order to obtain a more favourable outcome in the end. We show that this type of prevote interaction has beneficial effects on voting games by refining their set of equilibria, and in particular by guaranteeing the efficiency of truthful ones. Specifically, we isolate precise conditions under which 'bad' equilibria-i.e., truthful but inefficient ones-can be overcome, and 'good' ones can be sustained. Our work relates directly to several on-going lines of research in social choice, game theory and their applications to MAS.

Binary Aggregation Aggregation and merging of information is a long studied topic in AI [START_REF] Konieczny | Merging information under constraints: A logical framework[END_REF][START_REF] Chopra | Social choice theory, belief merging and strategyproofness[END_REF][START_REF] Everaere | The strategy-proofness landscape of merging[END_REF] and judgment aggregation has become an influential formalism in AI [START_REF] Endriss | Judgment aggregation[END_REF]. The basic setting of binary voting is also known as voting in multiple referenda [START_REF] Lacy | A problem with referendums[END_REF], and can be further enriched by imposing that individual opinions also need to satisfy a set of integrity constraints, like in binary voting with constraints [START_REF] Grandi | Lifting integrity constraints in binary aggregation[END_REF] and judgment aggregation proper (Dietrich & List, 2007a;[START_REF] Grossi | Judgment Aggregation: A Primer[END_REF]. Standard preference aggregation, which is the classical framework for voting theory, is a special case of binary voting with constraints (Dietrich & List, 2007a). The introduction of constraints will be touched upon towards the end of the paper. Research in binary voting and judgment aggregation focused on the (non-)manipulability of judgment aggregation rules [START_REF] Dietrich | Strategy-proof judgment aggregation[END_REF][START_REF] Botan | Group manipulation in judgment aggregation[END_REF] and its computational complexity [START_REF] Endriss | Complexity of judgment aggregation[END_REF][START_REF] Baumeister | Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules[END_REF], but a fully-fledged theory of non-cooperative games in this setting has not yet been developed and that is our focus here.

Election Control and Bribery

The field of computational social choice has extensively studied decision problems that capture various forms of election control (see Faliszewski and Rothe 2016, for a recent overview) such as adding and deleting candidates, lobbying and bribery, modelled from the single agent perspective of a lobbyist or briber who tries to influence voters' decisions through monetary incentives, or from the perspective of a coalition of colluders [START_REF] Bachrach | Coalitional voting manipulation[END_REF]. Here we study a form of control akin to bribery, but where any voter can 'bribe' any other voter. Our work can be seen as an effort to develop a game-theoretic model of this type of control, and given our focus on equilibrium analysis we sidestep issues of computational complexity in this paper.

Equilibrium refinement Non-cooperative models of voting are known to suffer from a multiplicity of equilibria, many of which appear counterintuitive, not least because of their inefficiency. Equilibrium selection or refinement is a vast and long-standing research program in game theory [START_REF] Meyerson | Refinements of the Nash equilibrium concept[END_REF]. Models of equilibrium refinement have been applied to voting games in the literature on economics [START_REF] Gueth | Majority voting in the Condorcet paradox as a problem of equilibrium selection[END_REF][START_REF] Kim | Equilibrium selection in n-person coordination games[END_REF] and within MAS especially within the above-mentioned iterative voting literature [START_REF] Meir | Iterative voting[END_REF], which offers a natural strategy for selecting equilibria through the process of best response dynamics that starts from a profile of truthful votes. Our model tackles the same issue of refinement of equilibria in the context of binary voting, and focusing on those equilibria that are truthful and efficient. Unlike in iterative voting, our model is a twophase model where equilibria are selected by means of an initial pre-vote negotiation phase, followed by voting.

Boolean Games We model voting strategies in binary aggregation with a model that generalises the well-known boolean games model [START_REF] Harrenstein | Boolean games[END_REF][START_REF] Wooldridge | Incentive engineering in boolean games[END_REF]: voters have control of a set of propositional variables, i.e., their ballot, and have specific goal outcomes they want to achieve. In our setting the goals of individuals are expressed over the outcome of the decision process, thus on variables that-in non-degenerate forms of voting-do not depend on their single choice only. Unlike boolean games, where each actor uniquely controls a propositional variable, in our setting the control of a variable is shared among the voters and its final truth value is determined by a voting rule. A formal relation with boolean games will be provided towards the end of the paper.

Pre-play Negotiations

We model pre-vote negotiations as a pre-play interaction phase, in the spirit of [START_REF] Jackson | Endogenous games and mechanisms: Side payments among players[END_REF]. During this phase, which precedes the play of a normal form game-the voting game-players are entitled to sacrifice part of their final utility in order to convince their opponents to play certain strategies, which in our case consist of voting ballots. In doing so we build upon the framework of endogenous boolean games [START_REF] Turrini | Endogenous games with goals: side-payments among goal-directed agents[END_REF], which enriches boolean games with a pre-play phase. We abstract away from the sequential structure of the bargaining phase, modelled in closely related frameworks [START_REF] Goranko | Two-player preplay negotiation games with conditional offers[END_REF].

The use of side-payments for equilibrium refinement is not novel in Artificial Intelligence. Notably [START_REF] Monderer | K-implementation[END_REF] k-implementation and "strong mediated equilibrium" [START_REF] Monderer | Strong mediated equilibrium[END_REF] employ side-payments by an external third party to drive the choices of self-interested agents. While both their models allow for game transformations through side-payments, the equilibrium refinement is mediated by an interested third party. Our model of side-payments and equilibrium refinement stems from Jackson and Wilkie's endogenous approach, which analyses the effect of negotiation through sidepayments without exogenous interventions.

Outline of the Paper

The paper is organised as follows. In Section 2 we present the setting of binary aggregation, defining the (issue-wise) majority rule as well as a general class of aggregation procedures, which constitute the rules of choice for the current paper. In Section 3 we define voting games for binary aggregation, specifying individual preferences by means of both a goal and a utility function, and we show how undesirable equilibria can be removed by appropriate modifications of the game matrix. In Section 4 we present a full-blown model of collective decisions as a two-phase game, with a negotiation phase preceding voting. We show how the set of equilibria can be refined by means of rational negotiations. Section 5 relaxes assumptions we make on voters' goals in the basic framework showing the robustness of our results. Section 6 discusses related work in some more detail. Finally, Section 7 concludes.

Preliminaries: Binary Aggregation

The study of binary aggregation dates back to [START_REF] Wilson | On the theory of aggregation[END_REF], and was recently revived both within economics [START_REF] Dokow | Aggregation of binary evaluations[END_REF] and AI [START_REF] Grandi | Lifting integrity constraints in binary aggregation[END_REF]. This section is a brief introduction to the key notions and definitions of the framework.

p q r A 1 0 1 B 1 1 0 C 0 0 0 maj 1 0 0
Table 1: An instance of binary aggregation

Basic Definitions

In binary aggregation a finite set of agents (to which we will also refer as voters and, later on, players) N = {1, . . . , n} express yes/no opinions on a finite set of binary issues I = {1, . . . , m}, and these opinions are then aggregated into a collective decision over each issue. This is analogous to voting over a simple (binary) combinatorial domain [START_REF] Lang | Voting over combinatorial domains[END_REF]. Issues can be seen as queries to voters in a multiple referendum [START_REF] Lacy | A problem with referendums[END_REF], or seats that need to be allocated to candidates-two per seat-in assembly composition [START_REF] Benôit | Only a dictatorship is efficient[END_REF], or candidates of which voters approve or disapprove of [START_REF] Brams | Approval voting[END_REF].

In this paper we assume that |N | ≥ 3, i.e., there are at least 3 individuals. We denote by D = {B | B : I → {0, 1}} the set of all possible binary opinions over the set of issues I and call an element B ∈ D a ballot. B(j) = 0 (respectively, B(j) = 1) indicates that the agent who submits ballot B rejects (respectively, accepts) the issue j. A profile B = (B 1 , . . . , B n ) ∈ D N is the choice of a ballot for every individual in N . Given a profile B, we use B i to denote the ballot of individual i within a profile B. We adopt the usual convention writing -i for N \ {i} and thus B -i to denote the sequence consisting of the ballots of individuals other than i. Thus, B i (j) = 1 indicates that individual i accepts issue j in profile B. Furthermore, we denote by N B j = {i ∈ N | B i (j) = 1} the set of individuals accepting issue j in profile B.

Given a set of individuals N and issues I, an aggregation rule or aggregator for N and I is a function F : D N → D, mapping every profile to a binary ballot in D, called the collective ballot. F (B)(j) ∈ {0, 1} denotes the value of issue j in the aggregation of B via aggregator F . The benchmark aggregator is the so-called issue-wise strict majority rule, which we will refer to simply as (issue-wise) majority (in symbols, maj). The rule accepts an issue if and only if a majority of voters accept it, formally maj(B)(j) = 1 if and 1 depicts a ballot profile with three agents (rows A, B and C) on three issues (columns p, q and r) and the aggregated ballot (fourth row) obtained by majority.

only if |N B j | ≥ |N |+1 2 . Table
Other examples of aggregation rules include quota rules, which we discuss below, and degenerate rules such as dictatorships, for which there exists i ∈ N such that on every issue j, and for all profile B, F (B)(j) = B i (j).

Types of Aggregators of Interest

In this paper we focus specifically on two classes of aggregators: the class of non-manipulable aggregators, an its subclass consisting of all quota rules.

Non-Manipulable Aggregators

In binary aggregation, an aggregator F is said to be non-manipulable if there exists no profile B such that for some issue j ∈ I and agent i ∈ N , B i (j) = F (B)(j) and [START_REF] Dietrich | Strategy-proof judgment aggregation[END_REF]. That is, no agent accepting (resp., rejecting) an issue while the issue is collectively rejected (resp., accepted) can change its ballot in order to force the issue to be collectively accepted (resp., rejected). 2The class of non-manipulable aggregators is the baseline class for the analysis of binary voting games developed in the paper. This is, we argue, a natural class of aggregators to focus on for our purposes, as we will be concerned with the analysis of strategic behavior that arises in a pre-vote negotiation phase. In a sense our models show how rich strategic behavior can be supported even by aggregators that make vote manipulation impossible.

B i (j) = F (B ′ , B -i )(j) for some ballot B ′ = B i
It is known (Dietrich & List, 2007c, Th. 1) that the class of non-manipulable aggregators corresponds to the class of aggregators which are independent and monotonic, so we will be referring to the two classes interchangeably. An aggregator F is said to be: independent if for all issue j ∈ I and any two profiles

B, B ′ ∈ D N , if B i (j) = B ′ (j) for all i ∈ N , then F (B)(j) = F (B ′ )(j); monotonic if for all issue j ∈ I, x ∈ {0, 1} and any two profiles B, B ′ ∈ D N , if B i (j) = x entails B ′ (j) = x for all i ∈ N , and for some ℓ ∈ N we have that B ℓ (j) = 1 -x and B ′ (j) = x, then F (B)(j) = x entails F (B ′ )(j) = x.
Intuitively, an aggregator is independent if the decision of accepting a given issue j does not depend on the judgment of the individuals on any issue other than j.3 It is monotonic if increasing (respectively, decreasing) the support on one issue when this is collectively accepted (respectively, rejected), does not modify the result.

The class of non-manipulable aggregators includes the majority rule, as well as any quota rule, to which we will turn next. The minority rule, i.e., the rule that always selects the opposite of the majority rule, satisfies independence, but fails monotonicity. Dictatorships, oligarchies, and similar non-anonymous aggregation rules4 do satisfy independence and monotonicity. Rules that fall out of the class, and that have been studied in the literature, are also the so-called distance-based rules, which output the ballot that minimises the overall distance to the profile for a suitable notion of distance.5

Quota Rules

While the core of our results are proven for independent and monotonic aggregators, we will sometimes restrict ourselves to the class of quota rules and establish stronger claims for that class. Quota rules accept an issue if the number of voters accepting it exceeds a given positive quota, possibly different for each issue. Formally, if a quota rule F q is defined via a function q : I → {1, . . . , n}, associating a quota to each issue, by stipulating F q (B) j = 1 ⇔ |N B j | ≥ q(j). 6 F q is called uniform in case q is a constant function. Issue-wise majority is a uniform quota rule with q = |N |+1 2 .

In our results we will make use of known axiomatic characterizations of quota rules. The class of quota rules corresponds to the class of independent, monotonic, responsive and anonymous aggregators [START_REF] Dietrich | Judgment aggregation by quota rules: Majority voting generalized[END_REF], Theorem 1). 7 The class of uniform quota rules corresponds to the class of aggregators that are, in addition, neutral (Endriss, 2016, Corollary 17.5). An aggregator F is said to be: neutral if for any two issues j, k ∈ I and any profile B ∈ D, if for all i ∈ N we have that B i (j) = B i (k), then F (B)(j) = F (B)(k); 8 responsive if for all issue j ∈ I there exist two profiles B and B ′ such that F (B)(j) = 1 and F (B ′ )(j) = 0; anonymous if for all two players i, j ∈ N and any two profiles

B, B ′ ∈ D N , if B i = B ′ j , B ′ i = B j and, for each k ∈ N \{i, j}, we have that B k = B ′ k , then F (B) = F (B ′ ).
Intuitively, an aggregator is responsive if it is not a constant function. It is neutral if all issues are treated in the same way, and anonymous if all voters are treated in the same way.

Winning and Veto Coalitions

Given an aggregator F , we call a set of voters C ⊆ N a winning coalition for issue j ∈ I if for every profile B we have that if B i (j) = 1 for all i ∈ C and B i (j) = 0 for all i ∈ C then F (B)(j) = 1. 9 The notion of winning coalition is closely related to the independence property defined above: 10 Fact 1. An aggregator F is independent if and only if for all j ∈ I there exists a set of subsets W j ⊆ P(N ) such that, for each ballot B, F (B) j = 1 if and only

N B j ∈ W j .
That is, F is independent if and only if it can be defined in terms of a family {W j } j∈I of sets of winning coalitions. Furthermore, we call a set of voters C ⊆ N a veto coalition for issue j ∈ I if for every profile B we have that if B i (j) = 0 for all i ∈ C and B i (j) = 1 for all i ∈ C then F (B)(j) = 0. Clearly,

C ∈ W j iff N \C ∈ V j .
(1)

Observe that by the above relation and Fact 1 an independent aggregator can equivalently be defined by a set {V j } j∈I of veto coalitions, consisting of the complements of those coalitions that do not belong to W j . Let us fix intuitions by a few examples. The sets of winning and veto coalitions for issue-wise majority are, for every issue j:

W j = C ⊆ N |C| ≥ |N |+1 2 and V j = C ⊆ N |C| ≥ |N | 2
. When |N | is odd, this is the only quota rule for which

W j = V j . 11
For a constant aggregator which always accepts all issues, that is, a quota rule 6. Note that we exclude from our definition of quota rules constant functions, that is, quota rules with quota equal to 0 or larger than n. 7. See also [START_REF] Endriss | Judgment aggregation[END_REF], Proposition 17.4. 8. Independent and neutral aggregators are often called systematic. 9. The definitions from this section are well-known from the literature, except for the notion of veto and resilient coalitions treated below. See, for instance, [START_REF] Dokow | Aggregation of binary evaluations[END_REF]. 10. This and the following facts are assumed to be well-known, for a proof in the setting of judgment aggregation we refer to [START_REF] Endriss | Judgment aggregation[END_REF], Lemma 17.1. 11. This property is known as unbiasedness.

with q = 0, the sets of winning and veto coalitions are, for each issue j: W j = 2 N , i.e., any coalition is winning, and V j = ∅, i.e., no coalition is a veto coalition.

Additional properties imposed on an independent aggregator F induce further structure on winning (and veto) coalitions: Fact 2. An independent aggregator F is monotonic if and only if for each j ∈ I and for any C ∈ W j (respectively, C ∈ V j ), if C ⊆ C ′ then C ′ ∈ W j (resp., C ′ ∈ V j ), i.e., winning (and veto) coalitions are closed under supersets. It is neutral if and only if for each j, k ∈ I we have that W j = W k (equivalently, V j = V k for all j, k ∈ I). It is anonymous if and only if for each j ∈ I we have that C ∈ W j (resp., C ∈ V j ) implies that D ∈ W j (resp., D ∈ V j ) whenever |C| = |D|, i.e., coalitions are winning (resp., veto) only depending on their cardinality.

We conclude this preliminary section with one last important definition. We call C a resilient winning coalition (respectively, a resilient veto coalition) for issue j ∈ I if C is a winning (resp., veto) coalition for j and, for every i ∈ C, C \ {i} is also a winning (resp., veto) coalition for j.12 For every issue j, the set of resilient winning (resp., veto) coalitions for j is denoted W + j (resp., V + j ). Given a neutral aggregator F , such as a uniform quota rule, we denote with W (resp., V) the set of winning (resp., veto) coalitions for F , and with W + (resp., V + ) the set of resilient winning (resp., veto) coalitions for F . In the case of the majority rule we have

W + = C ⊆ N | |C| ≥ |N |+1
2 + 1 , i.e., all winning coalitions exceeding the majority threshold of at least one element are resilient winning coalitions. For a uniform quota rule F q , the set of resilient winning coalitions is W + = {C ⊆ N | |C| ≥ q + 1}. Observe also that if F is dictatorial on every issue, then W + = ∅.

Games for Binary Aggregation

In this section we present a model of a strategic interaction played among voters involved in a collective decision-making problem on binary issues. Players' strategies consist of all binary ballots on the set of issues, and the outcome of the game is obtained by aggregating the individual ballots by means of a given aggregator. Players' preferences are expressed in the form of a simple goal that is interpreted on the outcomes of the aggregation (i.e., the collective decision), and by an explicit payoff function for each player i, yielding to player i a real number at each profile and encoding, intuitively, the utility i would receive, should that profile of votes occur. We study the existence of equilibria of these games, paying particular attention to the truthful and efficient ones.

Main Definitions

Before defining aggregation games we need a last piece of notation. To each set of issues I, we associate the set of propositional atoms PS = p 1 , . . . , p |I| containing one atom for each issue in I. We denote by L PS the propositional language constructed by closing PS under a functionally complete set of boolean connectives (e.g., {¬, ∧}).

Aggregation Games, Goals and Preferences

Definition 1. Let I and N be given. An aggregation game (for I and N ) is a tuple A = N , I, F, {γ i } i∈N , π where:

• F is an aggregator for N and I;

• each γ i is a cube, i.e. a conjunction of literals from L PS , 13 which is called a goal;

• π : N → D N → R is a payoff function assigning to each agent and each strategy profile a real number representing the utility that player i gets at that profile. For each player i, the payoff function π(i) of player i will be denoted simply by π i .

Note that a strategy profile in an aggregation game is a profile of binary ballots, and will therefore be denoted with B. In the context of aggregation games we will use the term "strategy profile" and "ballot profile", or even just "profile", interchangeably.

Goals, intuitively, represent properties of the outcome of the aggregation process that voters are not willing to compromise about. By making the assumptions that goals are cubes we assume that each voter has a simple incentive structure: she can identify a specific set of atoms that she wants to be true at the outcome, another set of atoms that she wants to be false, and she is indifferent about the value of the others. When comparing two outcomes, one of which satisfies her goal and one of which does not, a voter will choose the outcome satisfying her goal. Thus, the first degree of preference of agents is dichotomous [START_REF] Elkind | Structure in dichotomous preferences[END_REF]. If then two outcomes both satisfy her goal, or both do not, then the voter will look at the value she obtains at those outcomes through her payoff function.

This, we argue, is a very natural class of preferences for binary aggregation. They are technically known as quasi-dichotomous preferences and have been studied in the context of Boolean games [START_REF] Wooldridge | Incentive engineering in boolean games[END_REF]. Henceforth we employ the satisfaction relation |= (respectively, its negation |=) to express that a ballot satisfies (respectively, does not satisfy) a goal. The preference relation induced on ballot profiles by goals and payoff functions is defined as follows:

Definition 2 (Quasi-dichotomous preferences). Let A be an aggregation game. Ballot profile B is strictly preferred by i ∈ N over ballot profile B ′ (in symbols, B ≻ π i B ′ ) if and only if any of the two following conditions holds:

i) F (B ′ ) |= γ i and F (B) |= γ i ; ii) F (B ′ ) |= γ i if and only if F (B) |= γ i , and π i (B) > π i (B ′ ).
The two ballot profiles are equally preferred whenever

F (B ′ ) |= γ i if and only if F (B) |= γ i , and π i (B) = π i (B ′ ).
The resulting weak preference order among ballot profiles is denoted π i .

In other words, a profile B is weakly preferred by player i to B ′ if either F (B) satisfies i's goal and F (B ′ ) does not or, if both satisfy i's goal or neither do, but B yields to i at 13. Formally, each γi is equivalent to j∈K ℓj where K ⊆ I and ℓj = pj or ℓj = ¬pj for all j ∈ K.

least as good a payoff as B ′ . Individual preferences over ballot profiles are therefore induced by their goals, by their payoff functions, and by the aggregation procedure used.

Finally, goals relate in a clear way to the structure of winning and veto coalitions of an independent aggregator. One can identify for every goal which are the sets of agents that can force the acceptance of such goal: Definition 3. For an independent aggregator F and a cube γ we say that C is winning for γ if and only if C ∈ W j for each j such that γ logically entails p j , and C ∈ V j for each j such that γ logically entails ¬p j . We write W γ for the set of winning coalitions for γ. The set of resilient winning coalitions for γ (denoted W γ + ) is defined in the obvious way.

In words, a coalition is winning for a goal whenever it is winning for all the issues that need to be accepted for γ to be satisfied, and veto for all the issues that need to be rejected for γ to be true. An obvious adaptation of the definition yields the notion of veto coalition for a given goal.

Classes of Aggregation Games

A natural class of aggregation games is that of games where the individual utility only depends on the outcome of the collective decision:

Definition 4. An aggregation game A is called uniform if for all i ∈ N and profiles B it is the case that π i (B) = π i (B ′ ) whenever F (B) = F (B ′ ). A game is called constant if all π i are constant functions, i.e.
, for all i ∈ N and all profiles B we have that π

i (B) = π i (B ′ ).
Clearly, all constant aggregation games are uniform. Games with uniform payoffs are arguably the most natural examples of aggregation games. The payoff each player receives is only dependent on the outcome of the vote, and not on the ballot profile that determines it. For convenience, we assume that in uniform games the payoff function is defined directly on outcomes, i.e., π i : D → R. Constant games are games where players' preferences are fully defined by their goals, and are therefore dichotomous.

We call a strategy B i-truthful if it satisfies the individual's goal γ i . Note that in the case in which γ i is a cube that specifies in full a single binary ballot-that is, the agent's goal is a ballot-our notion of truthfulness coincides with the classic notion used in judgment aggregation and binary voting where only one ballot is truthful, and all other ballots are available for strategic voting.

Let us introduce some further terminology concerning strategy profiles:

Definition 5. Let C ⊆ N . We call a strategy profile B = (B 1 , . . . , B n ): (1) C-truthful if all B i with i ∈ C are i-truthful, i.e., B i |= γ i , for all i ∈ C; (2) C-goal-efficient (C-efficient) if F (B) |= i∈C γ i ; 14 (3) totally C-goal-inefficient (totally C-inefficient) if F (B) |= i∈C ¬γ i .
An aggregation game is called C-consistent, for C ⊆ N , if the conjunction of the goals of agents in coalition C is consistent, i.e., if the formula i∈C γ i is satisfiable.

Observe that while the notion of truthfulness is a property of the ballot itself, with goals interpreted on the individual ballots to check for truthfulness, the two notions of efficiency are instead properties of the outcome of the aggregation.

Equilibria in Aggregation Games

In this section we study Nash equilibria (NE) in aggregation games and specific classes thereof. Our focus is the existence of 'good' NE, that is, NE that are truthful and efficient.

Inexistence of Equilibria in (General) Aggregation Games

First of all, it is important to observe that aggregation games may not have, in general, (pure stragegy) NE.

Fact 3. There are aggregation games that have no NE.

Proof. Define an aggregation game as follows. Let I = {p}, N = {1, 2, 3}, and let γ 1 = γ 2 = γ 3 = ⊤. Assume also that the payoff function is defined as follows: for any ballot profile B, we have that π 1 (B) = 1 if and only if B 1 = B 2 , and 0 otherwise; π 2 (B) = 1 if and only if B 1 = B 2 , and 0 otherwise; finally, π 3 is constant. That is, agent 1 wants 1 and 2 to agree on issue p while agent 2 wants them to disagree, and agent 3 is indifferent among any two outcomes of the interaction.15 It is easy to see that the aggregation game encodes a matching-pennies type of game between 1 and 2 and, therefore, the resulting aggregation game does not have a NE.

We will come back to the issue of the inexistence of NE in Section 4.

Equilibria in Constant Aggregation Games

Recall that a strategy B i is weakly dominant for agent i if for all profiles B we have that (B -i , B i ) π i B. We begin with an important result showing that in constant aggregation games with aggregators that are non-manipulable (i.e., independent and monotonic), the truthfulness of a strategy is a sufficient condition for it to be weakly dominant.

Proposition 4. Let A be a constant aggregation game with F non-manipulable, and let i ∈ N be a player. If a strategy B i is truthful then it is weakly dominant for i. 16Proof. Let B i be a truthful strategy, i.e., B i |= γ i . We want to show that B i is weakly dominant, that is for every

B ′ ∈ D N , F (B ′ ) |= γ i implies F (B ′ -i , B i ) |= γ i .
We proceed towards a contradiction and assume that, for some profile B ′ we have that

F (B ′ ) |= γ i and F (B ′ -i , B i ) |= γ i .
Since by Definition 1 individual goals are cubes, we have that γ i = j∈I ℓ j , where ℓ j is a literal built from PS. Hence there exists a k ∈ I such that

F (B ′ -i , B i ) |= ℓ k but F (B ′ ) |= ℓ k . Assume w.l.o.g. that ℓ k is positive, i.e., ℓ k = p k . Since B i is assumed to be truthful, B i |= ℓ k (that is, B i (k) = 1). Now, F is independent so the value of issue k in the output of F depends only on the values of k in each individual ballot in the input profile. Moreover, since F (B ′ ) |= ℓ k and B i |= ℓ k , by the monotonicity of F we conclude that F (B ′ -i , B i ) |= ℓ k . Contradiction.
Intuitively the proposition tells us that independent and monotonic aggregators, as far as only the satisfaction of individual goals is concerned, guarantee that players are always better off by casting a truthful ballot. A first immediate consequence is that computing weakly dominant strategies in constant aggregation games takes a polynomial amount of time, since it boils down to finding a satisfying assignment to the individual goal, which in our model is a conjunction of literals. Other consequences are stated in the following corollary:

Corollary 5. Let A be an aggregation game with F non-manipulable:

(i) any profile B such that B i |= γ i for all i ∈ N is a NE; (ii) if for all i ∈ N the formula γ i is consistent, then A has at least one NE. i j i i i i
For the subclass of non-manipulable aggregators consisting of quota rules, the converse of Proposition 4 holds, showing that for quota rules the truthfulness of a strategy is also a necessary condition for it to be weakly dominant. Proposition 6. Let A be a constant aggregation game with F a quota rule. Then all weakly dominant strategies for i ∈ N are truthful.

Proof. Recall that quota rules correspond to the class of independent, monotonic, responsive and anonymous aggregators. Consider a weakly dominant strategy B i for i, and assume towards a contradiction that B i |= γ i , i.e., B i is not truthful. Since goals are cubes, there exists a k such that B i |= ℓ k , where γ i = j∈I ℓ j . W.l.o.g., assume that ℓ k = p k and let us argue towards the acceptance of k. By responsiveness there exist B and B ′ such that F (B)(k) = 1 and F (B ′ )(k) = 0. By anonymity, collective acceptance and rejection of k depends only on the cardinality of the set of agents accepting k in a given profile. So, by monotonicity there exists an integer q ( = 0, by responsiveness) such that F accepts k if and only if the cardinality of the set of agents accepting k is at least q. Therefore there exist B and B ′ such that F (B)(k) = 1 and F (B ′ )(k) = 0 and such that B -i = B ′ -i and B i (k) = 1 = B ′ (k). Furthermore, exploiting independence, let us assume that for any j = i and t = k, B j (t) = B ′ (t) and F (B) |= γ i . That is, there exist two profiles such that the first satisfies i's goal and the second does not, because the first meets the threshold for accepting k while the second does not. And the reason for the second not meeting the threshold is i's ballot to reject k. In other words, i is pivotal in B ′ for the acceptance of k and therefore for the acceptance of its goal. It follows that for any strategy

B ′ such that B ′ |= ℓ k we have that F (B -i , B ′ ) |= γ i , i.e., B i is dominated by B ′ , against the assumption that B i is weakly dominant in A.
So quota rules are a subclass of non-manipulable aggregators for which weak dominance and truthfulness are equivalent conditions on players' strategies: Corollary 7. Let A be a constant aggregation game with F a quota rule. A strategy B i is weakly dominant if and only if it is i truthful.

It is worth to observe that Proposition 4 ceases to hold if we allow the goals of the voters to be propositional formulas more complex than a cube:

1 1 Example 1. Let F = maj, N = {1, 2, 3} and let I = {1, 2}. Let then γ 1 = p 1 ∨ p 2 and γ 2 = γ 3 = ⊤.
That is, agent 1 is interested in having at least one of the two issues accepted, while the rest of the agents are indifferent. We show that in this game not all truthful ballots of 1 are weakly dominant. Consider the profile B = (B 1 , B 2 , B 3 ) where 1 votes the truthful ballot B 1 = (0, 1), 2 votes B 2 = (0, 0) and 3 votes B 3 = (1, 0). We have that F (B) |= γ 1 .

Clearly, 1 has a best response

B ′ = (1, 0) = B 1 in that profile as F (B ′ , B 2 , B 3 ) |= γ 1 .
Example 2. Let F = maj, N = I = {1, 2, 3} and let agent 1's goal be that of having an odd number of accepted issues, while agents 2 and 3 have no specific goals. Formally, let

γ 1 = (p 1 ∧ p 2 ∧ p 3 ) ∨ (p 1 ∧ ¬p 2 ∧ ¬p 3 ) ∨ (¬p 1 ∧ p 2 ∧ ¬p 3 ) ∨ (¬p 1 ∧ ¬p 2 ∧ p 3 ).
As above we show that not all truthful ballots of 1 are weakly dominant. Consider the profile B = (B 1 , B 2 , B 3 ) where B 2 = (1, 0, 0) and B 3 = (0, 1, 0) and where 1 votes a truthful ballot B 1 = (0, 0, 1). This profile results under the majority rule in (0, 0, 0). So the (non-truthful) ballot B ′ = (1, 0, 1) = B 1 is a better response in B for 1 and yields the collective ballot (1, 0, 0), which satisfies γ 1 . 17

In fact, cubes guarantee that players' preferences in constant aggregation games satisfy a property known as separability, 18 which has been shown in other voting frameworks to guarantee that truthful strategies are undominated [START_REF] Benôit | Only a dictatorship is efficient[END_REF]). 19

Equilibria, Truthfulness and Efficiency

Proposition 4 establishes the existence of truthful equilibria. However, as the example in the introduction has shown, truthfulness does not guarantee efficiency in constant aggregation games. We show now that this does not only hold for constant aggregation games based on majority, but for constant aggregation games based on uniform quota rules in general: Proposition 8. For every uniform quota rule, there exist constant aggregation games with truthful and totally inefficient NE in weakly dominant strategies.

Proof. Recall that uniform quota rules correspond to the class of aggregators which are independent, monotonic, neutral, anonymous and responsive. 20 The proof is by construction of a constant aggregation game A with the desired property. Let F be anonymous, systematic and monotonic, let N = I = {1, 2, 3}. First we will construct two games and show that at least one of the two admits a truthful and totally inefficient profile. We can then apply Proposition 4 to show that such profile ought to be a NE in weakly dominant strategies. The games are built on the same aggregator F and differ only on their goals. Game A Let, for each i ∈ N , γ i = p i . Each γ i is therefore, trivially, a cube. Note also 17. We are indebted to Edith Elkind for this example. 18. Cf. [START_REF] Lang | Voting over combinatorial domains[END_REF] for separability in combinatorial domains. 19. Separability is normally defined over strict orders (but cf. [START_REF] Hodge | Separable Preference Orders[END_REF] for a general treatment of the notion). In our setup separability can be defined as follows: i is separable if and only if for all j ∈ I,

if B i B ′ for two profiles such that F (B)(k) = F (B ′ )(k) for all k = j, then B ′′ i B ′′′ for all profiles such that F (B ′′ )(k) = F (B ′′′ )(k) for all k = j, F (B)(j) = F (B ′′ )(j), and F (B ′ )(j) = F (B ′′′ )(j). If
that i∈N γ i is satisfiable, so Game A is N -consistent. Game B Let, for each i ∈ N , the goal be defined as χ i = ¬p i . Each χ i is therefore, again, a trivial cube and Game B is also N -consistent. Now construct a ballot profile B in Game A and a ballot profile B ′ in Game B as follows, for i ∈ N and j ∈ I:

B i (j) = 1 if p j = γ i 0 otherwise B ′ i (j) = 0 if ¬p j = χ i 1 otherwise (2)
That is, in B each voter votes 1 only on the issues which coincides with its goal. Vice versa, in B ′ each voter votes 0 only on the issues whose rejection coincides with its goal. By construction, B and B ′ are both truthful. Now assume that B is not totally inefficient, and we prove that B ′ is totally inefficient. So there exists i ∈ N such that F (B) |= γ i and since by construction

γ i = p i , F (B)(i) = 1.

Equilibria in Uniform Aggregation Games

Since constant payoffs are special cases of uniform ones, negative results such as Proposition 8 still hold for uniform aggregation games. As to truthful voting, the positive result of Proposition 4 does not generalise to uniform aggregation games:

Proposition 9. There exist uniform aggregation games for a non-manipulable aggregator in which truthful strategies are not dominant.

Proof. Define the uniform aggregation game as follows. Let I = {p, q, t}, N = {1, 2, 3} and F = maj. Let γ 1 = ¬p ∧ q ∧ ¬t, γ 2 = ¬p ∧ ¬q ∧ ¬t, and γ 3 = ¬p ∧ ¬q ∧ t. Define the payoff functions as follows, let π i (B) = 1 for i = 3 and B = (0, 1, 0), and 0 otherwise. Take the following profiles: B 1 = ((0, 1, 0), (0, 0, 0), (0, 0, 1)) and B 2 = ((0, 1, 0), (0, 0, 0), (0, 1, 0)).

Since maj(B 1 ) = (0, 0, 0) and maj(B 2 ) = (0, 1, 0), we have B 2 ≻ B 1 and B 1 , unlike B 2 , contains a truthful strategy by 3.

The fact that truthful voting is not always a dominant strategy for aggregation games with simple goals might seem counterintuitive, especially when the payoff is required to be uniform across the profiles that lead to the same outcome. The reason for this lies in the effect of the payoff function. When a player is in the position of changing the outcome of the decision in a certain profile, this does not necessarily imply she has the power to make the collective decision satisfy her goal. She may only be able to lead the group to a decision which, even though still not satisfying her goal, yields a better payoff for her.

Γ

Despite the negative result in Proposition 9, we can still prove the existence of truthful and efficient equilibria in a uniform aggregation game if we assume the mutual consistency of the individual goals of a resilient winning coalition.

Proposition 10. Every C-consistent uniform aggregation game for non-manipulable F has a NE that is C-truthful and C-efficient, if C ∈ W + where Γ = {γ i | i ∈ C}.

Proof. Take a C-consistent uniform aggregation game. Note that since each goal γ i is a cube, also Γ is a cube, so that Definition 3 applies. There exists then a ballot B * such that B * |= Γ. Take now any ballot profile B * such that B * is the ballot of all and only the voters in C while all agents in N \C vote the inverse ballot B * (that is, for any issue

Discussion

Let us recapitulate the findings of this section. We have shown, for a well-behaved class of aggregators-the non-manipulable ones-, that aggregation games with constant payoffs have many NE, since truthful ballots are weakly dominant strategies in such games (Proposition 4) and that, for the subclass of non-manipulable aggregators known as quota rules, truthful ballots are exactly the set of weakly dominant strategies (Proposition 6).

We then showed that such results do not carry over to uniform aggregation games (Propositions 9 and 8), but that in such games, however, the existence of truthful and efficient equilibria can be guaranteed whenever a resilient winning coalition has non-conflicting goals (Proposition 10).

Finally, Proposition 8 has highlighted a key issue of aggregation games: truthful equilibria may be totally inefficient in the sense of failing to satisfy the goals of all voters, even when all such goals are consistent. The purpose of the following section is to introduce an endogenous pre-play negotiation mechanism which, in equilibrium, allows players to select truthful and efficient NE of the underlying aggregation game, thus resolving the tension between truthfulness and efficiency.

Pre-vote Negotiations

This section presents endogenous aggregation games: aggregation games augmented with a pre-vote negotiation phase. In a nutshell voters will now be allowed, before the vote takes place, to sacrifice a part of their expected gains in order to influence the other voters' decision-making. We show that allowing such negotiations: (i) guarantees the selection of efficient equilibria for all individuals when one such equilibrium exists (ii) discards all equilibria that are inefficient for the voters of any winning coalition.

Endogenous Aggregation Games

Endogenous aggregation games consist of two phases:

• A pre-vote phase, where, starting from a uniform aggregation game, players make simultaneous transfers of utility that may modify each others' payoffs in the game;

• A vote phase, where players play the aggregation game resulting from the original game after payoffs are updated according to the tranfers made in the pre-vote phase.

As usual, it is assumed that the players have common knowledge of the structure of the game (including their goals and payoffs). A key assumption is furthermore that the transfers made in the pre-vote phase be binding, for instance through a central authority. 21 The authority would, besides running the election in the vote phase, also collect and enforce the transfers announced in the pre-vote phase.

Pre-vote strategies are modelled as transfer functions of the form:

τ i : D N × N → R +
where i ∈ N . These functions encode the amount of payoff that player i commits to give to player j should a given ballot profile B be played, in symbols, τ i (B, j). The set of all transfer functions is denoted by T , and a transfer profile is a tuple of transfer functions τ ∈ T |N | . We denote by τ 0 the 'void' transfer where at every profile every player gives 0 to the other players.

The aggregation game induced by the transfer profile τ from A is denoted τ (A) = N , I, F, {γ i } i∈N , {τ (π) i } i∈N where, for any i ∈ N :

τ (π) i (B) = π i (B) + j∈N (τ j (B, i) -τ i (B, j)) (3)
So the payoff of player i at profile B once τ is played, consists of the old payoff that i was receiving at B, plus the money that i receives from the other players at B, minus what i gives to them at B. Notice that transfers do not preserve the uniformity of payoffs: even though A is always assumed to be uniform, τ (A) is not necessarily so, 22 and may lack a NE (recall Fact 3).

It is important to notice that while our pre-vote phase is based on Jackson and Wilkie's (2005) endogenous transfer functions, their effect on the resulting games, and therefore the resulting equilibria, is fundamentally different. In particular: our voting games are based on lexicographic preferences and are therefore not reducible to strategic games [START_REF] Turrini | Endogenous games with goals: side-payments among goal-directed agents[END_REF], which are instead the object of study of Jackson and Wilkie; our equilibrium analysis will moreover not rely on mixed strategies, which guarantee the existence of equilibria in the strategic games studied by Jackson and Wilkie, but are somewhat harder to interpret in a voting context.

Endogenous aggregation games are defined formally as follows:

21. The existence of such authority is a common assumption in work on election control and bribing [START_REF] Faliszewski | Control and bribery in voting[END_REF], as well as persuasion [START_REF] Hazon | How to change a group's collective decision?[END_REF]. It is often referred to as 'chair' or 'election organiser'. 22. In fact it is easy to see that there always exists a transfer that turns a uniform aggregation game into a non uniform one.

Definition 6 (Endogenous aggregation games). An endogenous aggregation game is a tuple A T = A, {T i } i∈N where A is a uniform aggregation game, and for each i ∈ N , T i = T . A constant endogenous aggregation game is an endogenous aggregation game A T where A is assumed to be constant. 23 In an endogenous aggregation game, each player i selects first a transfer τ i (pre-vote phase). The resulting transfer profile τ yields the new aggregation game τ(A). Then each player selects a ballot B i (vote phase) in τ(A). The resulting ballot profile B yields the collective ballot F (B), where F is the aggregator of A.

Equilibrium Selection via Pre-vote Negotiations

In this section we first provide the definition of the solution concept we use for analysing endogenous games as two-stage extensive form games, and we then present our main results on the selection of efficient equilibria via pre-vote negotiations.

Solving Endogenous Aggregation Games

Endogenous aggregation games are (perfect information) extensive form games with two stages of simultaneous choices. So in an endogenous aggregation game A T , a strategy of player i is a pair σ i ∈ T × D T N , that is, a choice of a transfer τ i in the pre-vote phase (first element), followed by the choice of a ballot B i in each aggregation game that results from some possible transfer profile (second element). A profile

σ = σ 1 , . . . , σ |N | ∈ T × D T N N
has the following important characteristics. First of all, it selects a unique transfer profile and a unique ballot profile-transfer-ballot profile in short-(τ, B) that will be played if σ is chosen by the players. We refer to such transfer and ballot profiles as being induced by σ. Secondly, for any transfer profile τ , a strategy profile σ uniquely determines a ballot profile, which we denote σ(τ ). We refer to such ballot profile as the ballot induced by σ after τ is played. The latter aspect of strategy profiles in endogenous aggregation games is worth stressing. Each strategy profile does not only determine a specific choice of transfers and ballots, but also a choice of ballots that would be played if other transfers were to be chosen, i.e., the counterfactual choices that would be made if other transfers were chosen by the players in the pre-vote phase of the game.

Given the above, it would seem natural to resort to (pure strategy) subgame perfect Nash equilibrium (SPE) to solve endogenous aggregation games. There is a complication however. As we observed earlier, the aggregation game resulting from a transfer profile may not be uniform and, therefore, may not necessarily have a NE. This makes SPE inapplicable as some subgames of the initial extensive game may, therefore, be unsolvable. Also notice how resorting to mixed strategy equilibria would not help addressing this issue, as lexicographic preferences are well-known for not being representable in terms of utility functions, therefore making Nash's NE existence theorem unavailable [START_REF] Rubinstein | Lecture Notes in Microeconomic Theory: The Economic Agent[END_REF].

What we do instead is to analyse endogenous aggregation games by assuming that, if the game resulting from a transfer profile does not have a NE, players play a maxmin strategy and resort to their maxmin value, or security level, 24 to evaluate the resulting aggregation 23. Constant endogenous aggregation games will be discussed in Section 5. 24. See [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations[END_REF] for an extensive exposition of the notion.

game. 25 In our quasi-dichotomous setup a maxmin strategy (ballot) is defined as:

argmax π i B i min π i B -i {F (B) | B = (B i , B -i )} , (4)
i.e., a (not necessarily unique) ballot that maximises the minimum, with respect to π i (Definition 2), outcome for i. If the maxmin strategy B i guarantees that γ i is satisfied no matter what the other players do, then we say that B i is safe for γ i . The minimum payoff guaranteed by i's maxmin strategies is i's security level.

We can now move to the definition of the solution for an endogenous aggregation game. To do that, however, we first need the following auxiliary definition: Definition 7 (Transfer game). Let A T be an endogenous aggregation game and fix a strategy profile σ. The transfer game induced by σ is the game in normal form A σ = N , {T i } i∈N , { σ i } i∈N where T i = T and each σ i ⊆ T 2 is the preference over transfer profiles defined as follows. Given a strategy profile σ, a transfer profile τ is said to satisfy goal γ i (in symbols, τ |= γ i ) if either the ballot profile σ(τ ) = (B 1 , . . . , B |N | ) induced by σ after τ is a NE of τ (A) and F (σ(τ )) |= γ i , or B i is safe for γ i in τ (A), and B i is a maxmin strategy of i. The payoff π i of profile τ is either τ (π) i (σ(τ )) if σ(τ ) is a NE of A T , or i's security level in τ (A) otherwise. Given the above, for any i ∈ N , τ ≻ σ i τ ′ if and only if any of the two following conditions hold:

26 i) F (σ(τ ′ )) |= γ i and F (σ(τ )) |= γ i ; ii) F (σ(τ ′ )) |= γ i if and only if F (σ(τ )) |= γ i , and π i (σ(τ )) > π i (σ(τ ′ )).
The two transfer profiles are equally preferred whenever F (σ(τ ′ )) |= γ i if and only if F (σ(τ )) |= γ i , and π i (σ(τ )) = π i (σ(τ ′ )). The resulting weak preference order among trasfer profiles is denoted σ i .

Observe that the preferences σ i over transfer profiles are therefore quasi-dichotomous. Intuitively, a transfer game is the game that a σ needs to solve in the negotiation phase of an endogenous aggregation game, once the continuations σ(τ ) have been fixed for any transfer profile τ . We are now in the position to state formally our definition of a solution concept for endogenous games: Definition 8 (Solutions). Let A T be an endogenous aggregation game. A strategy profile

σ ∈ T × D T N N of A T is a solution of A T if

and only if:

(1) Voting phase. The ballot profile σ(τ ) ∈ D N induced by σ after τ is a NE of the aggregation game τ (A), if such equilibrium exists, or a profile of maxmin ballots of τ (A), otherwise.

25.

A game with no NE should be seen as an unstable game, i.e., a situation in which the players do not have any reason to believe that some specific outcome will be realised. Measures such as the security level therefore compensate for this uncertainty. We could have adopted a number of alternative solutions, e.g., taking the value of the minimum outcome for each player, or considering such games never to be profitable deviations. Ultimately, all these assumption have the effect of ruling out profitable deviations to games with no NE. 26. Cf. earlier Definition 2.

(2) Negotiation phase. The first element in pair σ is a transfer profile τ , which is a NE of the transfer game A σ .

We refer to the transfer-ballot profile induced by a solution σ as the solution outcome of A T . So, intuitively, a solution outcome is obtained by constructing a profile σ through a backward induction procedure that starts with the voting phase, and then moves to the negotiation phase:

• Voting phase In the aggregation game resulting after each transfer profile, a NE is selected where at least one such equilibrium exists, or a maxmin profile is selected otherwise; the value of such NE, if it exists, or the players' security levels, otherwise, are used to evaluate transfer profiles in the next phase (negotiation phase) of the procedure.

• Negotiation phase A transfer profile is selected, such that no profitable deviation exists to another transfer profile, for any player, given the continuations that were selected in the first phase (the voting phase) of the procedure.

Surviving Equilibria

This section provides existence results for solutions of endogenous games. We actually provide stronger results, showing not only that solutions exist, but also (in the next sections) necessary and sufficient conditions for them to enjoy desirable properties in terms of the 'quality' of the equilibria that negotiation enables. In other words, we study endogenous aggregation games as endogenous mechanisms for the refinement of the equilibria of their underlying aggregation games.

Definition 9. Let A be a uniform aggregation game, and B a NE of A. B is a surviving Nash equilibrium (SNE) of A if there exists a transfer profile τ such that (τ, B) is a solution outcome of the endogenous aggregation game A T .

Intuitively, SNE identify those voting outcomes that can be rationally sustained by an appropriate pre-vote negotiation. Clearly, not all NE of the initial game will be surviving equilibria but, crucially, it can be shown that NE with good properties are of this kind, as we set out to show in this section. Let us first establish the following lemma.

Lemma 11. Let A be a uniform aggregation game for a non-manipulable aggregator F . Then, for every N -efficient and N -truthful ballot profile B of A, there exists a transfer profile τ such that B is a weakly dominant strategy equilibrium in τ (A).

Proof. Let B be an N -efficient and N -truthful ballot profile of A. We construct a transfer profile τ such that for any i ∈ N the strategy B i is a strictly dominant strategy for i in τ (A), that is: for any profile B ′ , (B i , B ′ -i ) π i B ′ and for some B ′ , (B i , B ′ -1 ) ≻ π i B ′ . The construction goes as follows.27 Consider now the quantity:

M = 1 + max z | ∃B, B ′ and i ∈ N s.t. z = π i (B) -π i (B ′ ) (5)
that is, M exceeds by one unit the maximal difference between the payoff received at any two outcomes by any agent. We are now ready to define a transfer function. For all i, j ∈ N :

τ i (B ′ , j) = 2M if B ′ i = B i 0 otherwise. (6)
In words, each player i commits to pay each other player the sum 2M in case he deviates from the ballot B i . By the definition of the preference relation π i (Definition 2), in order to prove the claim we need to show that: A For any

B ′ if F (B ′ ) |= γ i then F (B i , B ′ -i ) |= γ i , that is, under no circumstance i's goal would become falsified by playing B i . B For any B ′ if F (B ′ ) |= γ i if and only if F (B i , B ′ -i ) |= γ i (that is both profiles satisfy i's goals), then τ (π) i (B i , B ′ -i ) ≥ τ (π) i (B ′
), and for some

B ′ , τ (π) i (B i , B ′ -i ) > τ (π) i (B ′ ). Claim A Assume that F (B ′ ) |= γ i . There are two cases. First, B ′ i |= γ i . Since B is i i
N -truthful we know that B i |= γ i . Now γ i is assumed to be a cube (Definition 1) so B ′ and B i can differ only on the evaluation of issues on which the truth of γ i does not depend. By the independence of F we conclude that

F (B i , B ′ -i ) |= γ i . Second, B ′ |= γ i . But, as above, B i |= γ i . By the assumption F (B ′ ) |= γ i , so in profile (B i , B ′ -i
) voter i is changing the evaluation of at least one of the atoms that was falsifying γ i in B ′ (recall that γ i is a cube) to the evaluation given by F (B ′ ). By the monotonicity of F we can therefore conclude that

F (B i , B ′ -i ) |= γ i . Claim B
Given the definition of payoffs in endogenous games (3), the claim follows directly from the construction of τ. This completes the proof.

Intuitively, the lemma establishes that whenever a truthful profile exists that satisfies all players' goals, that profile can be turned into a dominant strategy equilibrium by means of a suitable combination of pre-vote transfers which, in essence, make the players' commitment to that equilibrium credible.

We finally give two examples of what happens if the assumptions behind the lemma are not satisfied. First, we describe a uniform aggregation game A for a non-manipulable F , and ballot profiles B that are either not N -efficient or not N -truthful, for which there exists no transfer profile τ such that B is a weakly dominant strategy equilibrium in τ(A).

Example 3. Let A be such that N = {1, 2, 3}, I = {p}, γ i = p, for each i ∈ N , and let F = maj. Let π be arbitrary. Consider now any profile B where for at least one agent i, B i (p) = 1. Each such profile is not N -truthful, and note that all profiles that are not N -efficient are among those. It is easy to see that, no matter the utility function π, there is no transfer τ which would make the profile a weakly dominant strategy equilibrium of τ(A).

Second, we show a uniform aggregation game A for an aggregator that is manipulablespecifically, that is not monotonic-, and an N -efficient and N -truthful ballot profile B for which there exists no transfer profile τ such that B is a weakly dominant strategy equilibrium in τ(A).

Example 4. Let A be such that N = {1, 2, 3}, I = {p}, γ i = p, for each i ∈ N and let π be arbitrary. Let F be such that F (B)(p) = 1 whenever B i (p) = 1 for all i ∈ N , or whenever B i (p) = 0, for all i ∈ N , and let F (B) = maj(B), otherwise. Observe that in such a i game, for no agent a truthful ballot is also a weakly dominant strategy. Independently of the choice of π, there is no transfer profile τ such that the N -efficient and N -truthful profile B = (1, 1, 1) becomes a weakly dominant strategy equilibrium in τ(A).

Good Equilibria Survive

Lemma 11 establishes the existence of a suitable transfer profile sustaining 'good'-that is, truthful and efficient-equilibria. We now show that endogenous aggregation games have solutions which require precisely the transfer profile constructed in the proof of Lemma 11 to be played in the negotiation phase of the game, and which therefore lead the voters to play 'good' equilibria in the voting phase.

Theorem 12. Let A be a uniform aggregation game for a non-manipulable aggregator F . Every N -efficient and N -truthful NE of A is a SNE.

Proof. Let B be a N -efficient and N -truthful NE of A. By the assumptions on the aggregator and Lemma 11, we can construct a transfer profile τ according to formula ( 6) such that B is a weakly dominant strategy equilibrium of τ(A). We have to show that (τ, B) is a solution outcome of A T . Suppose towards a contradiction that this is not the case, that is, that there exists a profitable deviation by player i from the strategy profile that induces the transfer-ballot profile (τ, B). Since B is a dominant strategy equilibrium in τ(A) such deviation has to involve a different transfer τ * by player i in the pre-vote phase. We identify two cases:

Case 1 The deviation induces a new transfer profile τ ′ = (τ * i , τ -i ) such that τ ′ (A) has no NE. By Definition 7 a deviation to τ * i would yield i his security level in τ ′ (A). We show that τ π i τ ′ , and hence the deviation cannot be profitable for i. Since B |= γ i we have, by Definition 8, that if τ ′ |= γ i then τ |= γ i , that is, it cannot be the case that τ ′ leads i to satisfy its goal while τ does not. As to the payoffs, observe that π i (τ ) is the payoff yielded by the NE B of τ (A), and that given the construction of τ ′ no agent transfers any utility to i in τ ′ : for all j ∈ N \ {i}, τ ′ j (B ′ , i) = 0 whenever B ′ j = B j . It follows that for every ballot profile B ′ in τ ′ (A) i's payoff is at most as much as what it obtains from B in τ (A). Hence, τ π i τ ′ . Case 2 The deviation induces a new transfer profile τ ′ = (τ * i , τ -i ) such that the game τ ′ (A) has a NE. We show that τ * i cannot be a profitable deviation for i. Since the strategy profile inducing (τ, B) is assumed to be a solution, i's deviation determines a transfer-ballot profile (τ ′ , B ′ ) where B ′ may or may not be a NE. However, if i's deviation toward (τ ′ , B ′ ) where B ′ is not a NE is profitable, i must have another at least as profitable deviation determining the transfer-ballot profile (τ ′ , (

B * i , B ′ -i )), where (B * i , B ′ -i ) is a NE of τ ′ (A)
. This, notice, has to be the case, as τ ′ (A) has a NE and thus the other players are necessarily playing in equilibrium. We therefore assume w.l.o.g., that the transfer-ballot profile (τ ′ , B ′ ) determined by i's deviation is such that B ′ is a NE of τ (A). Observe now that in order for (τ ′ , B ′ ) to be profitable for i there must exist a j = i such that B ′ j = B j , that is, there exists at least another agent j besides i who contributes to deviating from B to B ′ . This is because B is an N efficient NE and by construction of τ ′ ,we have that τ ′ j (B ′ , i) = 0 j j whenever B ′ = B j . So let there be k ≥ 1 players j = i for which B ′ = B and consider some such j. We have two subcases:

Case 2a B ′ |= γ j . Note that since B ′ is a NE, we have that no B ′′ j is such that F (B ′′ j , B ′ -j ) |= γ j , so B ′ j is a best response only by virtue of j's payoff. By the construction of τ ′ , playing B ′ j gives j the following payoff:

τ ′ (π) j (B ′ ) = π j (B ′ ) -(|N | -1)2M + 2M (k -1) + τ ′ i (B ′ , j).
If j plays B j instead, then j's payoff is:

τ ′ (π) j (B j , B ′ -j ) = π j (B j , B ′ -j ) + 2M (k -1) + τ ′ i (B j , B ′ -j , j).
Now since B ′ is a NE by assumption and j does not have a better response that can satisfy her goal, we have that τ ′ (π) j (B ′ ) ≥ τ ′ (π) j (B j , B ′ -j ) and therefore:

τ ′ i (B ′ , j) -τ ′ i (B j , B ′ -j , j) ≥ π j (B j , B ′ -j ) -π j (B ′ ) + (|N | -1)2M.
Now we use this inequality to compare i's payoff in (τ, B) vs. (τ ′ , B ′ ). Given the definition of M in Formula ( 5) and given the fact that

|N | -1 ≥ 2 it follows that τ ′ i (B ′ , j) - τ ′ i (B j , B ′ -j , j) ≥ 3M , which in turn implies that τ ′ i (B ′ , j) ≥ 3M . Therefore i's payoff τ ′ (π) i (B ′ ) in the new NE B ′ is at most: π i (B ′ ) -k3M + k2M.
In contrast, by the construction of τ in formula ( 6

), τ (π) i (B) = π i (B). So from the fact that k ≥ 1 it follows that π i (B ′ )-k3M +k2M ≤ π i (B) and therefore that τ ′ (π) i (B ′ ) ≤ τ (π) i (B).
Since B is N -efficient, by Definition 8, τ π i τ ′ and the constructed deviation τ * i cannot be profitable.

Case 2b F (B ′ ) |= γ j . Notice that from this it follows that F (B j , B ′ -j ) |= γ j , for otherwise there would be a ballot profile (i.e., (B j , B ′ -j )) where B ′ j is a better response for j making γ j true. From this we would conclude that B in τ (A) would not be a dominant strategy equilibrium, against our assumption. We can then proceed as in Case 2a, showing that τ ′ (π) i (B ′ ) ≤ τ (π) i (B). Since, as just noticed, both B and B ′ satisfy γ j , by Definition 8, τ π i τ ′ and the constructed deviation τ * i cannot be profitable. This completes the proof.

By combining Theorem 12 with Proposition 10, we also get the following corollary:

Corollary 13. Let F be a non-manipulable aggregator. Every N -consistent uniform aggregation game for F , where

N ∈ W + Γ with Γ = {γ i | i ∈ N }, has a SNE that is N -truthful and N -efficient.
That is, in constant aggregation games where the grand coalition is resilient, there exists a SNE in which every agent votes truthfully and all goals are satisfied.

Finally, we show that the assumption of non-manipulability of the aggregator F in Theorem 12 is necessary. Proposition 14. There exist uniform aggregation games with F manipulable, for which there exists an N -efficient and N -truthful NE that is not a SNE.

Proof. The proof is by construction. Let A be a uniform aggregation game with N = {1, 2, 3}, I = {1, 2}, γ i = p 1 , for each i ∈ N . Let moreover, for each i ∈ N , π i (B) = 1 whenever F (B) = (1, 1), and π i (B) = 0 otherwise. Let now F be such that F (B) = (1, 1) whenever B i = (0, 0), for each i ∈ N , and F (B) = (maj(B)(1), 0), otherwise. That is, F always rejects issue p 2 except when everybody rejects it, and accepts p 1 whenever either there is a majority accepting it or everybody rejects it. This game is clearly uniform and goals are cubes, F is independent but it is not monotonic and is therefore manipulable.

Consider now the profile B * such that B * i = (1, 1), for each i ∈ N . This profile is an N -efficient and N -truthful NE of A. However it is not a SNE. To see this, we proceed towards a contradiction and assume that B * is a SNE. So there exists a solution outcome (τ * , B * ) of the endogenous aggregation game. By the way we defined π, for all j we have that π j (B * ) < π i (B ′ ), where B ′ is the profile at which B ′ j = (0, 0), for each j ∈ N . By the definition of transfer function, for any transfer function τ and any profile B, j∈N π j (B) = j∈N π τ j (B). From these two facts we conclude that for some player i we have that π τ * i (B * ) < π τ * i (B ′ ). Observe that in B ′ i's goal is still satisfied. We show that i can deviate from τ * in such a way that the resulting voting game after such deviation, i) B ′ is a NE, and ii) it is unique. This would be a profitable deviation for i thereby showing that (τ * , B * ) cannot be a solution outcome. So we show how to construct a deviation from τ * which satisfies the two above constraints. i) To make sure that B ′ remains a NE in the voting game after the new transfer profile it suffices for the deviation τ i of i to be such that (τ i , τ *

-i )(B ′ ) = τ * (B ′ ).
That is payoffs for B ′ remain as in the original game A.

ii) Now we have to show how the deviation τ i of i can be constructed so that no other profile exists which is a NE in (τ i , τ * -i )(A) and which satisfies i's goal (as otherwise the deviation we are trying to construct would not be profitable for i). To do this we set i's transfer deviation to guarantee that, in any profile that satisfies his goal, but where any agent's ballot is different from (0, 0), some agent has an incentive to deviate from his current ballot to another one, that is, has a better response. Such deviation τ i can be built as follows. W.l.o.g., below we assume i = 1. 28 (1) Profiles in which p 1 is satisfied and 1 is not pivotal to p 1 being satisfied (i.e., 2 and 3 both accept p 1 ). Transfer strategy τ 1 should be set so that: (τ 1 , τ * -1 )(B ′ ) = τ * (B ′ ); and for any B ′′ and B ′′′ , π

(τ 1 ,τ * -1 ) 1 (B ′′ ) > π (τ 1 ,τ * -1
) 1 (B ′′′ ) whenever, by interpreting the ballot profiles as two-bits binary numbers, B ′′ 1 < B ′′′ 1 , that is according to the ordering, (0, 0) < (0, 1) < (1, 0) < (1, 1). Observe that such transfer strategy commits 1 to always play (0, 0) whenever his goal is satisfied and he is not pivotal for the goal to be satisfied.

28. The construction we propose bears similarities with the concept of hard equilibrium induction studied in Harrenstein, Turrini, andWooldridge (2014, 2017).

(2) Profiles in which p 1 is satisfied, 1 is not pivotal and B 1 = (0, 0). Transfer strategy τ 1 should be set so that:

π (τ 1 ,τ * -1 ) 2 ((0, 0), (1, 1), (1, 1)) < π (τ 1 ,τ * -1 ) 2 ((0, 0), (1, 0), (1, 1)) π (τ 1 ,τ * -1 ) 3 ((0, 0), (1, 1), (1, 0)) < π (τ 1 ,τ * -1 ) 3 ((0, 0), (1, 1), (1, 1)) π (τ 1 ,τ * -1 ) 2 ((0, 0), (1, 0), (1, 0)) < π (τ 1 ,τ * -1 ) 2 ((0, 0), (1, 1), (1, 0)) π (τ 1 ,τ * -1 ) 3 ((0, 0), (1, 0), (1, 1)) < π (τ 1 ,τ * -1 ) 3 ((0, 0), (1, 0), (1, 0))
Observe that such transfer strategy guarantees that whenever 1 plays (0, 0) and he is not pivotal for his goal to be satisfied, 2 and 3 always have better responses (preserving the satisfaction of their goal, but guaranteeing a higher payoff) to voting strategies which are different from (0, 0).

(3) Profiles in which p 1 is not satisfied, no player is pivotal and B 1 = (0, 0). Transfer strategy τ 1 should be set so that:

π (τ 1 ,τ * -1 ) 3 ((0, 0), (0, 1), (0, 1)) < π (τ 1 ,τ * -1 ) 3 ((0, 0), (0, 1), (0, 0)) π (τ 1 ,τ * -1 ) 2 ((0, 0), (0, 1), (0, 0)) < π (τ 1 ,τ * -1 ) 2 ((0, 0), (0, 0), (0, 0)) π (τ 1 ,τ * -1 ) 3 ((0, 0), (0, 0), (0, 1)) < π (τ 1 ,τ * -1 ) 3 ((0, 0), (0, 0), (0, 0))
Observe again that such transfer strategy guarantees that whenever 1 plays (0, 0) and no player is pivotal for his goal to be satisfied, 2 and 3 always have better responses (not reaching the goal, but guaranteeing a higher payoff) to voting strategies which are different from (0, 0).

(4) Profiles in which p 1 is satisfied, 1 is pivotal and B 1 = (1, 0). Transfer strategy τ 1 should be set so that:

π (τ 1 ,τ * -1 ) 2 ((1, 0), (0, 0), (1, 0)) < π (τ 1 ,τ * -1 ) 2 ((1, 0), (0, 1), (1, 0)) π (τ 1 ,τ * -1 ) 3 ((1, 0), (0, 1), (1, 0)) < π (τ 1 ,τ * -1 ) 3 ((1, 0), (0, 1), (1, 1)) π (τ 1 ,τ * -1 ) 2 ((1, 0), (0, 1), (1, 1)) < π (τ 1 ,τ * -1 ) 2 ((1, 0), (1, 1), (1, 1)) π (τ 1 ,τ * -1 ) 3 ((1, 0), (1, 0), (0, 0)) < π (τ 1 ,τ * -1 ) 3 ((1, 0), (1, 0), (0, 1)) π (τ 1 ,τ * -1 ) 2 ((1, 0), (1, 0), (0, 1)) < π (τ 1 ,τ * -1 ) 2 ((1, 0), (1, 1), (0, 1)) π (τ 1 ,τ * -1 ) 3
((1, 0), (1, 1), (0, 1)) < π (τ 1 ,τ * -1 ) 3

((1, 0), (1, 1), (1, 1))

Observe that such transfer strategy guarantees that whenever 1 plays (1, 0) and he is pivotal for his goal to be satisfied, 2 and 3 always have better responses (preserving the satisfaction of their goal, but guaranteeing a higher payoff) to voting strategies which are different from (0, 0).

π i u
It should be clear that the above four cases cover all profiles of relevance for the construction, and that constructing a transfer that meets the above constraints is easy: since the goals of all players remain unchanged throughout, and players can always transfer enough incentives, it suffices for i to transfer ǫ to the agent he wants to sway from her current strategy. After (τ 1 , τ - * 1 ), B ′ is therefore the only NE of the resulting game. The transfer strategy τ i is therefore a profitable deviation for i, from which follows that B * is not a SNE. Contradiction.

Only Good Equilibria Survive

We now turn to necessary conditions for equilibria to survive, and observe that for an equilibrium to survive, it has to be efficient. This can be regarded as a converse statement of Theorem 12, and it holds true in a general form concerning winning coalitions (and not just the coalition N ) with internally consistent goals: Theorem 15. Let A be a C-consistent uniform aggregation game for a non-manipulable aggregator F , and such that C ∈ W Γ where Γ = {γ i | i ∈ C}. Then, every SNE of A is C-efficient.

Proof. We proceed by contraposition. Let B be a NE that is not C-efficient, i.e., such that F (B) |= γ i for some individual i ∈ C, and assume towards a contradiction that B is a SNE. Therefore there exists a transfer profile τ such that (τ, B) is a solution outcome of the endogenous game A T . We proceed towards a contradiction and construct a profitable deviation for a player i from τ, that is a τ ′ such that τ ′ ≻ i τ. By C-consistency of A there exists a ballot B ′ such that B ′ |= Γ, hence in particular B ′ |= γ i . Let now i deviate to any transfer profile τ ′ = (τ ′ , τ -i ) s ch that she offers to all other players in C more than their payoff difference if they switch to vote for ballot B ′ while everybody else in C does so, i.e., ) does

τ ′ i ((B ′ C , B ′′ -C ), j) > τ (π) j (B ′ C-{j} , B ′′ j , B ′′ -C ) -τ (π) j (B ′ C , B ′′ -C ) for each j ∈ C, each B ′′ j ,
The proof of Theorem 12 provides every agent with a simple algorithm to compute a negotiation strategy that will guarantee the emergence of an efficient equilibrium in the resulting game. Note that the use of cubes sidesteps the intractability of the satisfiability problem for the conjunction of the goals.

Observe also that Theorem 15 implies the existence of uniform aggregation games where no equilibrium is surviving, which in turn implies that Theorem 12 cannot be weakened from N -efficiency to C-efficiency. This is the case when distinct but overlapping coalitions have incompatible goals, as the following example shows:

Example 5. Let there be five players in N , and let F be the majority rule. Let γ 1 = p ∧ ¬r, γ 2 = γ 3 = γ 4 = ⊤ and let γ 5 = r ∧ ¬p. Both coalitions C 1 = {1, 2, 3, 4} and C 2 = {2, 3, 4, 5} are resilient winning coalitions, and the game is both C 1 -consistent and C 2 -consistent. Hence, by Theorem 15 any surviving equilibria must be both C 1 -efficient and C 2 -efficient, which is impossible given that the conjunction of the goals of the two coalitions is inconsistent.

Summary

Results such as Theorems 12 and 15 suggest that pre-vote negotiations are a powerful tool players have to overcome the inefficiencies of aggregation rules. More specifically, when the goals of all players can be satisfied at the same time, pre-vote negotiations allow players to engineer side-payments-essentially as devices for credible commitments-leading to equilibrium outcomes that satisfy them, and ruling out all the others. We stress that in solving endogenous aggregation games, even when the game ends up sustaining efficient outcomes, players' strategies are individually rational and the game remains non-cooperative throughout. This differentiates our work from approaches to equilibrium selection with coalitional games, such as the one developed by [START_REF] Bachrach | Coalitional voting manipulation[END_REF].

Lifting the Cube Assumption on Goals

An inspection of our main results of Section 4 should make it immediately clear that we have crucially relied on the assumption that agents' goals are propositional formulas known as cubes (Definition 1). Cubes guarantee a clear relation between truthfulness and weak dominance in aggregation games (recall Examples 1 and 2). While a direct generalisation of our main results is out of reach, in this section we show that a larger class of goals still support useful, albeit weaker, conclusions in the form of guaranteeing the existence of at least one surviving "good" equilibrium.

Monotonic Goals

As shown in Examples 1 and 2, when goals are not cubes it is possible to construct constant aggregation games in which truthful strategies are not dominant. In this section we find sufficient conditions on the class of goals for which there exists a truthful strategy that is weakly dominant, and we build further on this result by showing that, in constant aggregation games where players' goals are 'aligned' in a precise sense, we can still construct a truthful SNE that is also efficient (Theorem 18). Up until now we referred to aggregation games assuming players' goals were cubes (Definition 1). In this section we need to drop such constraint in the definition and, when referring to aggregation games, we make explicit what type of goal formulas we are considering.

We first need some additional notation and a definition. Let B be a valuation over PS, denote by B -j the restriction of B to PS \ {p j }. A formula ϕ is monotonic if for every p j occurring in ϕ, it is either positively or negatively monotonic in p j .

Let us mention a few examples. Formulas that are satisfied by only one model are monotonic. Similarly, cubes (i.e., conjunctions of literals) are monotonic. Not all monotonic formulas are, however, cubes: disjunctions of literals, which were used to construct Example 1, are monotonic but are not cubes in general. Again, Example 2 provides a good example of formulas which are not monotonic in the above sense. When viewed as characteristic functions, monotonic constraints correspond to the widely studied class of unate boolean functions [START_REF] Mcnaughton | Unate truth functions[END_REF].

Existence of Truthful and Efficient SNE

We have shown (Proposition 4) that when goals are cubes, every truthful strategy in a constant aggregation game is weakly dominant. Although this fails to be true when goals are monotonic (Example 1 offers a counterexample to such claim), we can still establish the following weaker result: Lemma 16. Let A be a constant aggregation game with monotonic goals, defined for a non-manipulable aggregator F . For each player i ∈ N , if γ i is consistent then there exists a truthful strategy for i that is weakly dominant in A.

Proof. The proof is by construction. Recall Definition 2. We build a ballot B i such that B i |= γ i and show that for any ballot B ′ = B i and profile B, we have that if

F (B -i , B ′ ) |= γ i then F (B -i , B i ) |= γ i .
Let ballot B i be as follows. For any variable p j occurring in γ i , let:

B i (j) =    1 if γ i is
positively monotonic in p j 0 if γ i is negatively monotonic in p j 0 if p j does not occur in γ By the assumption of monotonicity of γ i , together with its consistency, the above construction guarantees that B i |= γ i . To simplify the proof, since variables not occurring in γ i do not play a role in its satisfaction, we can safely assume that all variables p j for j ∈ I occur in γ i . We now show that for any

B ′ i = B i we have that if F (B -i , B ′ i ) |= γ i then F (B -i , B i ) |= γ i
as well, for any ballot profile B, thereby establishing the claim. So take such a ballot B ′ i and assume that F (B -i , B ′ i ) |= γ i . Now let n be the Hamming distance29 between B ′ i and B i and consider the sequence

B ′ i = B 0 i , . . . , B n i = B i such that for all 1 ≤ k ≤ n, B k+1 i is equal to B k
i except for the value of one of the issues (that is, the sequence consisting of a minimal number of value swaps to turn B ′ i into B i ). By construction of B i , each B k i is the result of swaps 0 → 1 for issues in which γ i is positively monotonic, and 1 → 0 for issues in which γ i is negatively monotonic, and possibly other swaps on variables not occurring in γ i .

We now prove that F (B -i , B k i ) |= γ i for all 0 ≤ k ≤ n. We proceed by induction over k. For k = 0 the claim is true by assumption. Assume the claim is true for k (IH), i.e., F (B -i , B k i ) |= γ i . By the observation above, B k+1 i can be obtained from B k i in only two ways: a by a swap 0 → 1 for some issue j in which γ i is positively monotonic; or b by a swap 1 → 0 for some issue j in which γ i is negatively monotonic. If a is the case then in profile (B -i , B k+1 i ) there is one more voter, namely i, who supports p j . We distiguish two cases: a1 If F (B -i , B k i ) |= p j , by independence and monotonicity of F , we can infer that also ) |= p j . We now need to observe that by the assumption we have that γ i is positively monotonic in p j to conclude that, also in this case, maj(B -i , B k+1 i

F (B -i , B k+1 i ) |= p j and therefore F (B -i , B k+1 i ) = F (B -i , B k i ) |= γ i by IH. a2 If F (B -i , B k i ) |= p j ,
) |= γ i .
This proves the claim for the first case. If b is the case, we reason in a symmetric fashion to conclude that that F (B -i , B i ) |= γ i , as claimed.

A direct consequence of Lemma 16 is the existence of a truthful NE in weakly dominant strategies for constant aggregation games with monotonic goals. However, in order to obtain results analogous to Theorem 12 in the context of monotonic goals we need first to establish sufficient conditions for the existence of truthful and efficient NE.

Let us first introduce some auxiliary terminology. Two monotonic goals γ 1 and γ 2 are aligned if they are positively monotonic on the same set of issues and negatively monotonic on the same set of issues. We establish the following result: Lemma 17. Let A be a constant aggregation game with monotonic goals, for a nonmanipulable aggregator F . Assume moreover that A is C-consistent, that C ∈ W Γ where Γ = {γ i | i ∈ C}, and that all goals of agents i ∈ C are aligned. Then, A has a truthful and C-efficient NE (in weakly dominant strategies).

Proof. Let B ′′ be a ballot such that B ′′ |= i∈C γ i . B ′′ exists by assumption of Cconsistency. B ′′ can be used in the proof of Lemma 16 to construct a truthful NE in weakly dominant strategies. Now observe that, since all goals of agents in C are aligned, the weakly dominant equilibrium so constructed is composed by a unanimous ballot choice for individuals in C, which we shall call B * . Since C is a winning coalition for i∈C γ i , we have that F (B) |= i∈C γ i and the equilibrium is therefore also C-efficient as claimed.

Everything is now in place to prove a variant of Theorem 12 for constant aggregation games where players hold monotonic goals.

Theorem 18. Let A be a constant N -consistent aggregation game with monotonic goals, for a non-manipulable aggregator F . Assume that all individual goals are aligned, and that N ∈ W Γ for Γ = {γ i | i ∈ N }. Then, there exists an N -truthful and N -efficient NE of A which is also a SNE of A.

Sketch of proof.

Let B be an N -truthful and N -efficient NE of A, which exists by Lemma 17. We can therefore construct a transfer profile τ such that B is a weakly dominant strategy equilibrium of τ(A T ). The construction proceeds in the same way as the construction, for a transfer profile of the same type, given in the proof of Lemma 11. We then have to show that B is a SNE of A T . To do so we proceed towards a contradiction and suppose that there exists a profitable deviation τ * i for some player i in A T . The argument used in the proof of Theorem 12 to the effect that no such profitable deviation exists can be applied directly, thereby establishing the claim.

The assumption of monotonicity cannot be further weakened. If goals are allowed to be non-monotonic, then it is possible to construct (constant) aggregation games where, for some player, no truthful strategy is weakly dominant as witnessed by Example 1.

Discussion and Related Work

In this section we discuss our results from two points of view. First, we show how our results can be applied to the preservation of logical consistency when aggregation occurs on logically interconnected issues, which is the key problem of judgment aggregation. Second, we relate aggregation games to the influential notion of boolean game.

Pre-vote Negotiations and Collective Consistency

We showcase an application of endogenous aggregation games to binary aggregation with constraints, or judgment aggregation [START_REF] Endriss | Judgment aggregation[END_REF][START_REF] Grossi | Judgment Aggregation: A Primer[END_REF], where individual ballots need to satisfy a logical formula, the integrity constraint, in order to be considered feasible or admissible. In case each individual provides an admissible ballot, the obvious question is whether the outcome of a given aggregation rule will be admissible, as well. Here is an instance of this problem.

Example 6. Consider the scenario in Table 1. Suppose we impose the integrity constraint p → (q ∨ r), making ballot (1, 0, 0) inadmissible. All individual ballots in the example satisfy this requirement but the majority ballot does not.

Paradoxical situations as those in Example 6 can be viewed as undesirable outcomes of aggregation games. Building on the example, assume that each agent has the following goals:

γ ′ A = p, γ ′ B = q, γ ′ C = ¬r. Let π A = π B = π C be constant payoff functions.
Observe that parties' goals are all consistent with the integrity constraint r → (p ∨ q), and that the admissible ballot (1, 1, 0) satisfies all of them. Given these goals, the profile in Table 1 shows a truthful NE that, however, does not satisfy neither the goal of party B nor the integrity constraint p → (q ∨ r). However, this equilibrium is not surviving because, intuitively, party B could transfer enough utility to party C for it to vote for q.

But the key question is whether we can guarantee that inadmissible equilibria do not survive. 30 It is easy to see that if the integrity constraint is implied by some player's goal-intuitively, the player internalises consistency itself as a goal-then N -truthful and N -efficient equilibria will satisfy the integrity constraint and, by our results, they will be surviving in games with well-behaved aggregators (Theorem 12). Vice versa, since only equilibria survive which are efficient for some winning coalition, with some extra assumptions on the aggregator (Theorem 15), only collectively consistent outcomes are generated by the aggregation.

Boolean Games

Boolean games [START_REF] Harrenstein | Boolean games[END_REF]) are a logic-based representation of strategic interaction, where a set of individuals A = {1, 2, . . . , m} is assigned control of a set of propositional variables P = {p 1 , p 2 , . . . , p k }. Specifically, propositions are partitioned among the agents, i.e., each agent is assigned unique control over a subset of them, and each agent can decide to set the propositional variables he or she controls to true or false, in such a way that the final outcome of the boolean game is determined by the agents' truth value assignment on the variables each of them controls. Finally, each agent is equipped with a goal formula, i.e., a formula of propositional logic over the set of variables P . Typically, although agents have control over some propositional variables, they might not be able to realise their goal formula on their own. Boolean games as aggregation games Boolean games can be seen as a special case of aggregation games, where each indiviudal is a dictator for the variables he or she controls. That is, a boolean game B, defined over A and P S, can be seen as an aggregation game of the following form:

A B = N B , I B , F B , γ B i i∈N , π B i i∈N
where: N B = A is the set of players, I B = P S is the set of issues, F B is a dictatorship on issue j by i, for any issue j ∈ I controlled by i ∈ N , i.e., F B (B)(j) = B i (j), γ B i is the goal formula for i in B, and each π B i is constant. Thanks to the above reduction we are able to import the following complexity bounds from the boolean games literature: Proposition 19. Let A be an aggregation game with arbitrary goals γ i for each i ∈ N and B a ballot profile.

(1) The problem of verifying whether, for some transfer profile τ , B is a NE of τ (A) is co-NP-hard;

(2) The problem of verifying whether there exists a transfer function τ and a ballot profile B ′ that is a Nash equilibrium of τ (A) and such that F (B ′ ) |= i∈N γ i is Σ 2 p -hard;

(3) The problem of verifying whether there exists a transfer function τ such that for all ballot profiles B ′ that are a Nash equilibrium of τ (A) we have that F (B ′ ) |= i∈N γ i is Σ 2 p -hard.

Proof. The results follow from [START_REF] Wooldridge | Incentive engineering in boolean games[END_REF], Proposition 1), (Wooldridge et al., 2013, Proposition 6) and (Wooldridge et al., 2013, Proposition 14) respectively, together with the translation given above.

Boolean games have been extended in a number of ways, some of which will be dealt with next. It is however worth mentioning the extension by [START_REF] Gerbrandy | Logics of propositional control[END_REF] and [START_REF] Belardinelli | Relaxing exclusive control in boolean games[END_REF] to structures where coalitions are able to share the control of a propositional variable. Although the purpose is to study the logical properties of shared control and not the property of social choice functions, [START_REF] Gerbrandy | Logics of propositional control[END_REF] basically works with aggregation games with arbitrary aggregators, but without goals and without payoff function. The work of [START_REF] Belardinelli | Relaxing exclusive control in boolean games[END_REF] takes instead a verification approach, showing that games with shared control can be simulated by classical boolean games for what concern the model-checking of alternating-time temporal logic formulas. They do not, however, study the game-theoretic structure of these models.

Boolean games and incentive engineering A class of boolean games that is relevant to our framework is boolean games with arbitrary payoffs, i.e., aggregation games of the form A B = N B , I B , F B , γ B i i∈N , π B i i∈N where the payoff is not necessarily constant. These boolean games have been introduced to account for efforts (or costs) in performing actions [START_REF] Grant | Manipulating boolean games through communication[END_REF][START_REF] Wooldridge | Incentive engineering in boolean games[END_REF][START_REF] Turrini | Endogenous games with goals: side-payments among goal-directed agents[END_REF][START_REF] Harrenstein | Hard and soft equilibria in boolean games[END_REF]. When comparing two outcomes, a player will prefer the ones satisfying the goal, but will otherwise look at minimising the effort. This amounts to the same idea of having a payoff that is taken into account only in case goal satisfaction cannot discriminate between outcomes.

Boolean games with costs have been looked at from the point of view of incentive engineering, allowing payoffs to be manipulable, either by exogenous taxation mechanisms as in the work of [START_REF] Wooldridge | Incentive engineering in boolean games[END_REF] and [START_REF] Harrenstein | Hard and soft equilibria in boolean games[END_REF], or by endogenous negotiation as in the work of [START_REF] Turrini | Endogenous games with goals: side-payments among goal-directed agents[END_REF]. In the exogenous setting, an external system designer can impose taxes on players' actions, by effectively influencing their decision-making towards the realisation of her own goal formula. In the endogenous setting, individuals undergo a pre-play negotiation phase and try to improve upon their final payoff using side-payments. This has lead to the discovery of the existence of hard equilibria [START_REF] Harrenstein | Hard and soft equilibria in boolean games[END_REF], i.e., pure Nash-equilibria that cannot be removed by external incentives. Note that their presence is even more frequent in endogenous settings, due to the fact that side-payments are a weaker form of manipulation than external intervention, as observed by [START_REF] Turrini | Endogenous games with goals: side-payments among goal-directed agents[END_REF]. Endogenous boolean games are essentially endogenous aggregation games applied to a restricted setting. However the idea of hard equilibrium does carry over to aggregation games in general. Think for instance of a situation in which there is only one issue, p, and only one winning coalition, N . If everyone wants p to be true, then the profile in which everyone votes for p is an equilibrium that is impossible to remove by manipulating payoffs.

Conclusions

The paper has proposed a model of pre-vote negotiation for games of binary aggregation. Although a number of papers in the literature on voting games have focused on the problem of avoiding undesirable equilibria, no model studying strategic behaviour in a pre-vote negotiation phase has so far been proposed. We used our model to show how pre-vote negotiations can restore the efficiency of truthful voting in such games. More specifically we established the following main results. In uniform aggregation games for non-manipulable (i.e., independent and monotonic) aggregators where voters' goals are cubes, if an equilibrium is truthful and efficient it will be selected by equilibrium behaviour in the pre-vote negotiation phase (Theorem 12). We also showed that the 'only if' variant of this claim holds with respect to the efficiency alone of the equilibria (Theorem 15). For larger classes of goals we were able to show the existence of a truthful and efficient equilibrium that will be selected by equilibrium behaviour in the pre-vote negotiation phase (Theorem 18, for monotonic goals) and that this assumption cannot be further relaxed (Example 1).

Our work is a first step towards the development of a body of theoretical results on how strategic interaction preceding voting influences the outcomes of group decision-making. While classical social choice theory analyses individual preferences as independent inputs for an aggregation problem, we have shown how the introduction of an explicit negotiation phase preceding the vote has a fundamental impact in equilibrium selection. In particular, we have seen how the mere possibility of pre-vote negotiation rules out the selection of unintuitive and undesirable equilibria in which voters have aligned motives but choose to go against them together. A number of directions are possible to further enrich our framework, with two main ones. First, the analysis of further co-dependence among individuals, by for instance studying interactions constrained in a social network [START_REF] Jackson | Social and Economic Networks[END_REF], where individuals can actively incentivise their connections only. Second, the elaboration of an even more realistic model of pre-vote negotiation, studying resource-bounded individuals that have an upper bound, in the form of an endowment, on the amounts they can transfer in order to influence each other's behaviour.

  j, B * (j) = 1 if and only if B * (j) = 0). Since C ∈ W Γ (by the assumption that C ∈ W + Γ ) we have that F (B * ) satisfies the conjunction of the goals of the individuals in C, and each individual in C votes truthfully. We show that B * is a NE, by showing that (a) no agent in N \C has a profitable deviation, and (b) no agent in C has a profitable deviation. As to (a), since F is monotonic, any change in the ballot B * (j) by some voter in N \C does not change the outcome F (B * ) = B * . As to (b), any change in the ballot B * by some voter in C does not change the outcome because C ∈ W + Γ .

  and each B ′′ -C , and where B ′ C = (B ′ j ) j∈C . By the fact that B ′ is C-efficient, F independent and monotonic, and C is a winning coalition for Γ, this j ny π transfer makes each B ′ , with j ∈ C a best response in profiles (B ′ C ,

Definition 10 .

 10 A formula ϕ ∈ L PS is: positively monotonic in p j , where p j occurs in ϕ, if for all B, B ′ ∈ D such that B |= ϕ, B -j = B ′ -j , and B ′ |= p j then B ′ |= ϕ. negatively monotonic in p j if for all B, B ′ ∈ D such that B |= ϕ, B -j = B ′ -j , and B ′ |= p j then B ′ |= ϕ.

  then either i is not pivotal on issue j, and therefore F (B -i , B k+1 |= γ i by IH. Or i is pivotal at step k, and then F (B -i , B k+1 i

	F (B -i , B k i )	i	) =

This notion of non-manipulability is a preference-free variant of the one used in the preference aggregation literature.

When the aggregator is independent, the process of aggregation is also referred to as proposition-wise voting in the literature on multiple referrenda[START_REF] Ozkai-Sanver | Ensuring Pareto optimality by referendum voting[END_REF], or seat-by-seat voting in the literature on assembly composition[START_REF] Benôit | Only a dictatorship is efficient[END_REF], or as simultaneous voting in the literature on voting over combinatorial domains[START_REF] Lang | Voting over combinatorial domains[END_REF].

See definition of anonymity below.

See Grossi and Pigozzi (2014) and[START_REF] Endriss | Judgment aggregation[END_REF] for a more detailed exposition of aggregation rules.

This definition adapts the notion of resiliency of equilibria studied by[START_REF] Halpern | Beyond Nash-equilibrium: Solution concepts for the 21st century[END_REF] to the notion of winning and veto coalition proper of binary aggregation.

Note that this game is not uniform.

This proposition can also be obtained as corollary of a result by[START_REF] Dietrich | Strategy-proof judgment aggregation[END_REF]. We are indebted to Ulle Endriss for this observation.

i is a dichotomous preference induced by a cube (i.e., a conjunction of literals), then i is separable under the above definition. 20. Responsiveness does not play a role in the proof and could be dispensed with. Concretely, this means that the claim holds also for trivial quota rules, that is, constant aggregators.

Our construction is an adaptation of the one in[START_REF] Jackson | Endogenous games and mechanisms: Side payments among players[END_REF], Theorem 4. We however point out once more how our proofs do not rely on the existence of NE in each aggregation game.

We recall that the hamming distance H(B, B ′ ) between two valuations (vectors) B and B ′ is defined as follows: H(B, B ′ ) = j |B(j) -B ′ (j)|.

That voting paradoxes can be studied from an equilibrium refinement perspective is an old but rather underexplored idea[START_REF] Gueth | Majority voting in the Condorcet paradox as a problem of equilibrium selection[END_REF].

Acknowledgments

This paper improves and extends work previously presented at the 24th International Joint Conference on Artificial Intelligence, IJCAI'15 (Grandi, Grossi, & Turrini, 2015). The paper has benefited from the feedback of the anonymous reviewers at IJCAI'15, COMSOC'14 and LOFT'14. The authors are greatly indebted to Edith Elkind, Ulle Endriss and the anonymous reviewers of JAIR for valuable comments on earlier versions of this work. The authors also wish to thank the participants of the 2nd International Workshop on Norms, Actions and Games (NAG'2016) in Toulouse, the 2015 LABEX CIMI Pluridisciplinary Workshop on Game Theory in Toulouse, the 5th International Workshop on Computational Social Choice (COMSOC'2014) in Pittsburgh, the 11th Conference on Logic and the Foundations of Game and Decision Theory (LOFT'2014) in Bergen, the 12th Meeting of the Social Choice and Welfare Society held in Boston in 2014, and the Workshop on Fair Division, Voting and Computational Complexity held in Graz in 2014, where this work has been presented. Davide Grossi acknowledges partial support for this research by EPSRC under grant EP/M015815/1. Paolo Turrini acknowledges support from Imperial College London under the Imperial College Research Fellowship "Designing negotiation spaces for collective decision-making" (DoC AI1048).