# marketbased_explanations_of_collective_decisions__f6a082a8.pdf

Market-Based Explanations of Collective Decisions

Dominik Peters, 1 Grzegorz Pierczy nski, 2 Nisarg Shah, 3 Piotr Skowron 2

1Harvard University 2University of Warsaw 3University of Toronto dominikp@cs.cmu.edu, g.pierczynski@mimuw.edu.pl, nisarg@cs.toronto.edu, p.skowron@mimuw.edu.pl

We consider approval-based committee elections, in which a size-k subset of available candidates must be selected given approval sets for each voter, indicating the candidates approved by the voter. A number of axioms capturing ideas of fairness and proportionality have been proposed for this framework. We argue that even the strongest of them, such as priceability and the core, only rule out certain undesirable committees, but fail to ensure that the selected committee is fair in all cases. We propose two new solution concepts, stable priceability and balanced stable priceability, and show that they select arguably fair committees. Our solution concepts come with a non-trivial-to-construct but easy-to-understand marketbased explanation for why the chosen committee is fair. We show that stable priceability is closely related to the notion of Lindahl equilibrium from economics.

Introduction A committee election is a scenario where a group of individuals called voters collectively selects a size-k subset of available candidates, for a given k. The model of committee elections describes real-life situations such as selecting political representatives for a group of voters, selecting finalists or laureates in a contest (where voters correspond to judges or experts who collectively select a subset of contestants), deciding on locations of public facilities (Farahani and Hekmatfar 2009; Skowron, Faliszewski, and Lang 2016), and selecting validators in the blockchain protocol (Amoussou Guenou et al. 2020a,b). A committee election rule is a function specifying how voters preferences map to the collective decision on which candidates should be selected. We focus on the model of approval preferences, in which each voter approves a subset of the candidates. A number of different committee election rules have been proposed for this model (Faliszewski et al. 2017; Lackner and Skowron 2020). In order to choose the right rule for a given scenario, one needs to be able to reason about these rules in a principled way. Various approaches have been proposed for this purpose. A compelling one is the axiomatic approach, in which one formulates desirable mathematical properties and asks which voting rules satisfy them.

Copyright 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

For approval-based committee elections, axioms that capture how well minorities of voters with common interests are represented have received considerable attention in recent years (Aziz et al. 2017; Brill et al. 2017; S anchez-Fern andez et al. 2017; Lackner and Skowron 2018; Peters and Skowron 2020). The starting point of our discussion is that even the strongest of these axioms fail to ensure that the selected committee is intuitively fair or proportionally representative on all instances. We explain this via the example of the core (Aziz et al. 2017; Fain, Munagala, and Shah 2018; Cheng et al. 2019; Jiang, Munagala, and Wang 2019; Peters and Skowron 2020).

Outcomes in the Core do not Have to be Fair Assume that there are n voters. Each voter i specified a subset of candidates Ai that she approves, and the goal is to select a committee of exactly k candidates. The high-level idea behind the core is that a group of voters S should be able to decide on at least |S|/n k candidates in the elected committee. Formally, we say that a committee W is in the core if there exists no group of voters S and no subset of candidates T such that |T| |S|/n k and each voter from S prefers T over W (i.e. approves more candidates in T than in W). The core is a very strong concept. It implies a number of weaker properties, such as extended justified representation (EJR) (Aziz et al. 2017), proportional justified representation (PJR) (S anchez-Fern andez et al. 2017), and justified representation (JR) (Aziz et al. 2017). In fact, the core is so strong that, for the time being, it is not known whether there always exists a committee in the core for approval-based elections. However, even this strong property can sometimes allow dramatically unfair committees, as the example below illustrates. Example 1. Fix an integer L. Consider the following instance with n = k L voters. Voters 1, . . . L approve candidates c1, . . . , ck. For each i {1, 2, . . . , k 1} voters i L + 1, . . . , i L + L 1 approve candidate ck+i. The remaining k 1 voters approve candidates c2k, . . . , c3k 2, each voter approving a different candidate. This instance is depicted in Figure 1. The candidates correspond to the boxes; each candidate is approved by the voters who are below the corresponding box. For this instance, the committee W1 = {c1, . . . , ck} (the committee marked green) is in the core. In fact this committee

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

c2k ck+1 c2k 1 v1 v2 v L v L+1 v2L v(k 1)L+1 vk L

L voters L 1 voters L 1 voters

Figure 1: The illustration of Example 1.

would be uniquely selected by the following natural rule: among all committees in the core (assuming it is non-empty), select the one that maximizes the total number of approvals . This committee gives zero satisfaction to a majority of the voters. One can argue that a committee that consists of the blue candidates, along with one green candidate, e.g., W2 = {c1, ck+1, . . . , c2k 1}, is a much fairer choice.

Similar observations have been made by Bredereck et al. (2019) for the axiom of extended justified representation (EJR). They observe that in practice many very different committees satisfy EJR, and concluded that EJR on its own does not guarantee a sensible selection of committees.

Priceability and Evidence of Fairness

The problem illustrated in Example 1 is that properties like the core (and also EJR, PJR and JR) prevent specific pathological situations, but beyond their definitions, do not provide intuitive justifications for why a committee they allow should be selected. In this paper, we take a different approach and aim for solution concepts that provide explicit and intuitive explanations for why the chosen committee is fair. In their recent paper, Peters and Skowron (2020) introduced the concept of priceability. Intuitively, it decides on a fixed price that it will cost to add a candidate, endows each voter with a fixed amount of virtual money, and allows voters to spend money on buying candidates they like. Candidates are added to the committee when voters collectively pay the price. Priceability seeks committees which can be explained via this process, and under which no group of voters have so much money left over so that they could collectively buy one more candidate. The latter condition ensures that voters were able to spend a large chunk of their money, and may thus already have derived sufficient satisfaction from the candidates they purchased. This is a step in the right direction: the individual payments that voters make towards buying approved candidates constitute an intuitive explanation and serve as evidence that the chosen committee is fair. However, this explanation is weak: it only requires that voters have limited leftover money, but not that their money is spent wisely. We add a stability condition: informally, voters should not want to change how their money is spent. We borrow the idea of making payments stable from the classic economic concept of Lindahl equilibrium for public economies (Foley 1970), which ensures fair outcomes in a model with divisible goods (Fain, Goel, and Munagala 2016). In fact, we show that one of the two

notions we propose is closely related to (a discrete version of) Lindahl equilibrium.

Our Contribution We introduce two solution concepts: stable priceability (SP) and balanced stable priceability (BSP). SP strengthens the concept of priceability by Peters and Skowron (2020). We show that it is a strong fairness notion. It logically implies both the core and priceability, and also guarantees a higher proportionality degree (Skowron 2018) than both. In contrast to the core, whether a committee satisfies SP can be checked in polynomial time. We also present a compact integer linear program for finding SP committees. We show that, unfortunately, SP committees do not always exist. However, through a series of extensive experiments, we argue that almost SP committees often do (specifically ones whose size is very close to k); see Appendix D for details. Finally, we adapt the notion of Lindahl equilibrium to the committee election context, and show that SP is closely related to it. One potential source of unfairness under stable priceability is that two voters may be paying different amounts of virtual money for the same candidate that they both approve. Our notion of balanced stable priceability (BSP) addresses this by requiring that any two voters paying for a candidate must pay the same amount. We uniquely characterize BSP committees as those returned by a variant of the recently introduced Rule X (Peters and Skowron 2020). Similarly to SP, we show that BSP committees do not always exist, but almost BSP committees often do. Due to space constraints, we must defer almost all proofs to the supplementary material.

Preliminaries For t N, let [t] = {1, 2, . . . , t}. An election is a tuple (C, N, {Ai}i N, k), where: 1. C = {c1, . . . , cm} and N = [n] are sets of m candidates and n voters, respectively; 2. For each voter i N, Ai C denotes the set of candidates approved by i. Conversely, for a candidate c C, we denote by N(c) the set of voters who approve c: N(c) = {i N : c Ai}. For clarity of presentation, we define the utility function of each voter i N as ui(T) = |Ai T| for all subsets of candidates (also referred to as committees) T C. For simplicity, for each c C, we write ui(c) {0, 1} instead of ui({c}); 3. k [m] is the number of candidates to be selected. We say that committee W C is feasible if |W| = k.

Proportionality of Election Rules An election rule, or in short a rule, is a function that for each election returns a nonempty set of feasible committees, called winning committees.1 This paper studies group-fairness of election rules in the approval-based model. One such concept of fairness is the core.

1Typically, a rule selects a single winning committee; however, we allow the possibility of ties.

Definition 1 (The Core). Given an election, we say that a committee W C is in the core, if for each S N and T C with |T |/k |S|/n, there exists i S such that ui(W) ui(T). We say that an election rule R satisfies the core property if for every election E, each winning committee W R(E) is in the core. Two other well-established properties in the literature the proportionality degree (S anchez-Fern andez et al. 2017; Aziz et al. 2018; Skowron 2018) and extended justified representation (EJR) (Aziz et al. 2017, 2018) provide guarantees for cohesive groups of voters. A group S N is ℓ-cohesive if it is large enough (|S| ℓ n/k) and if its members approve at least ℓcommon candidates (| T i S Ai| ℓ). Definition 2 (Extended Justified Representation). A rule R satisfies extended justified representation (EJR) if for every election E, each winning committee W R(E), and each ℓ-cohesive group of voters S, there exists a voter i S who approves at least ℓmembers of W. Definition 3 (Proportionality Degree). Let f : N R. We say that a rule R has the proportionality degree of f, if for every election E, each winning committee W R(E), and each ℓ-cohesive group of voters S, the average number of committee members a voter from S approves is at least f(ℓ), that is., (1/|S|) P i S ui(W) f(ℓ). It is known that EJR implies a proportionality degree of at least f(ℓ) = ℓ 1

2 , and that a proportionality degree of more than f(ℓ) = ℓ 1 implies EJR (Aziz et al. 2018).

Priceability Peters and Skowron (2020) define the concept of price systems and the related property of priceablity. A price system is a pair ps = (p, {pi}i N), where p R+ is the price of electing one candidate, and for each voter i N, pi : C [0, p] is a payment function that specifies the amount of money a particular voter pays for the elected candidates. Formally, a committee W is supported by a price system ps = (p, {pi}i N) if the following conditions hold: (C1). A voter only pays for candidates she approves, so that pi(c) = 0 for each i N and c / Ai. (C2). Each voter has the same initial budget of 1 unit of a virtual currency: P c C pi(c) 1 for each i N. (C3). Each elected candidate gathers a total payment of p: P

i N pi(c) = p for each c W. (C4). Voters do not pay for non-elected candidates: P i N pi(c) = 0 for each c / W. (C5). For each unelected candidate, her supporters have an unspent budget of at most p: formally, P i N(c) ri p for each c / W, where for each i N: ri = 1 P c W pi(c ). (1)

Given a payment function pi, it will be useful to write pi(W) = P c W pi(c) for sets W C. A committee W is said to be priceable if there exists a price system ps = (p, {pi}i N) that supports W (i.e., that satisfies conditions (C1) (C5)). For each k N, a feasible priceable committee always exists; for example, Phragm en s sequential rule always returns one (Peters and Skowron 2020).

Note that two voters might pay different amounts of money for the same candidate. Further, we will consider so called balanced price systems where this is not allowed.

Stable Price Systems While priceability is an intuitively appealing property, on its own it does not imply other desired fairness-related properties (except for the rather weak PJR property, see Peters and Skowron 2020). For example, consider what we will call the Utilitarian Priceable Rule (UPR) which picks, among priceable committees, those that maximize the utilitarian social welfare, i.e., total number of approvals from voters. UPR fails EJR. In fact, as we show in Proposition 1, the proportional degree of UPR is at most 2, which means that UPR does not even approximate EJR up to a sublinear factor.2 Intuitively, this means priceability provides a very weak proportionality guarantee for cohesive groups of voters. Because the core implies EJR, UPR also violates the core.

Proposition 1. The proportionality degree of Utilitarian Priceable Rule is at most 2.

Corollary 1. In the approval-based committee-election model, the Utilitarian Priceable Rule violates EJR; in fact, it does not approximate EJR by a factor better than ℓ/4.

The price system constructed in the priceability definition serves as some evidence that the committee selected is fair to groups: no group of voters can use their leftover money to buy a new candidate, and hence that group must already have used most of their money to buy approved candidates. However, this is weak evidence because the definition does not require that the money already spent by the voters is spent wisely. This is why priceability, on its own, does not imply strong fairness guarantees. In this paper, we enhance the definition of priceability by replacing (C5) with a stronger condition which requires that voters money be spent wisely. Later, we show that this is strong enough to imply a high proportionality degree and the core (and therefore EJR too). Let be a linear order over N R+ defined as follows:

(x, p) (y, q) x > y or (x = y and p < q). (2)

We will use (x, p) (y, q) to model a voter who prefers to pay p dollars for a committee where she approves x candidates than pay q dollars for committee with y approved members. Thus, under this linear order, the voter prefers to maximize her utility for the committee, and only in case of a tie, prefers to pay less. We note that these are not the true preferences of the voters, but rather an artificial relation that helps us formulate our definition of stable priceability. We say that a price system ps = (p, {pi}i N) is stable if it satisfies (C1) (C4), and:

(S5). Condition for Stability: There exists no coalition of voters S N, no subset W C \ W, and no collections {p i}i S (p i : W [0, 1]) and {Ri}i S (with Ri W for all i S) such that all the following conditions hold:

2See the work of Skowron (2018) for more on EJR approximation.

1. For each c W : P i S p i(S) > p. 2. For each i S: pi(W \ Ri) + p i(W ) 1. 3. For each i S: ui(W \ Ri W ),pi(W \ Ri) + p i(W ) ui(W),pi(W) .

A committee W is said to be stable priceable if there exists a stable price system ps = (p, {pi}i N) that supports W (i.e., that satisfies conditions (C1) (C4) and (S5)). In order to better understand the condition, assume (S5) is not satisfied. Then, each voter i S can find a set Ri of currently approved candidates such that she would prefer to stop paying for Ri and to pay for W instead (i.e. she would be at least as happy , according to , with (W \ Ri) W and the new payments than with W and the old payments). In addition, the total amount paid by the voters from S to each candidate in W would exceed the price p of a candidate. Let us explain why we require a strict inequality in the first condition of (S5). This way, our definition is consistent with the standard definition of priceability; this also allows us to deal with tie-breaking issues that lead to nonexistence of stable priceable committees in very small symmetric instances (see Theorem 2). We note that we can use other possible linear orders in the definition of stable priceability; we discuss one such alternative in Appendix B.

A Simpler Formulation of SP Condition (S5) can be formulated in a simpler and rather more concise form. Consider the following inequality:

i N(c) max max a W (pi(a)) , ri

Here, ri is as defined in (1). Condition (3) is similar to (S5), but only prevents a group of voters from paying for a single new candidate. For example, we can easily observe that (S5) for |W | = 1 implies (3). Indeed, assume (S5), take c / W, let W = {c}, and consider i N(c). If ri maxa W (pi(a)), then set Ri = and p i(c) = ri; otherwise, let c = argmaxa W (pi(a)), set Ri = {c } and p i(c) = pi(c ). In both cases, voter i weakly prefers to replace Ri with W , and i can exchange Ri for W within her budget. Thus, by (S5) we to have that p P

i S p i(c):

i S p i(c) X

i N(c) max max a W (pi(a)) , ri

We show the other implication in the proof of Theorem 1. At first, it might seem that restricting to |W | = 1 makes the condition weaker. For example, inequality (3) does not imply (C1), as taking W = is no longer possible. However, surprisingly, it turns out that this is the only difference: allowing |W | > 1 does not increase the strength of the condition. We will show that (3) together with (C1) is equivalent to (S5). Thus, every price system satisfying (3) is SP.

Theorem 1. Inequality (3) together with condition (C1) is equivalent to condition (S5).

An important consequence of Theorem 1 is that (C1) (C4) and (3) can be formulated as a linear program, and thus, we can efficiently check whether a given committee is SP. Corollary 2. Given election and a committee W, it can be checked in polynomial-time whether there exists a stable price system supporting W. This is in contrast to many other group fairness properties, which are co NP-hard to check (Aziz et al. 2018). Further, one can formulate a compact integer linear program for finding SP committees (see Appendix C.1). The most pressing question is whether SP committees exist for all elections. The answer is negative. The counterexample is provided in Appendix A. Theorem 2. There exists an election for which no feasible commitee is supported by a stable price system. In Appendix D we describe the results of experiments that we conducted for synthetic distributions of voters preferences and for real datasets. There, we assumed that we are allowed to return committees that are slightly smaller or slightly larger than k. We found that it is almost always possible to find a committee, large part of which is SP (thus, even if an SP committee does not exist we have means to find a committee which is almost SP). Conversly, our experiments suggest it is possible to select an SP committee that exceeds the desired size k only by a small magnitude.

SP versus Priceability and the Core Stable priceability obviously implies priceability. The following result shows that it also implies the core, and therefore, in turn, EJR. Theorem 3. A feasible SP committee is in the core. Corollary 3. SP implies EJR. The core on its own is already a formidable axiom, and not known to be achievable in all elections. Are there any advantages to considering an axiom that further strengthens the core, and also strengthens priceability? We argue that there are several advantages. As already mentioned, a first advantage that SP has over the core is that whether a committee is SP can be checked in polynomial time (Corollary 2), whereas the same question is known to be difficult for the core (see, e.g., the proof of Theorem 2 of Aziz and Monnot 2020). Additionally, in elections like Example 1 presented in the introduction, the core allows apparently unfair solutions (such as the committee of all green candidates), while SP rules them out and allows only fairer solutions (such as the committee of all blue candidates and one green candidate). Moreover, an advantage that SP has over priceability is that SP implies the core, and in turn, EJR (Theorem 3), whereas priceability does not even imply EJR (Corollary 1). Finally, one advantage that SP has over both the core and priceability is that SP implies a high proportionality degree, as the following result shows. Theorem 4. SP implies a proportionality degree of ℓ 1. In contrast, it is known that EJR only implies a proportionality degree of ℓ 1

2 (Skowron 2018), and priceability does not imply a proportionality degree better than 2 (see Proposition 1).

SP and Lindahl Equilibrium

The concept of (stable) priceability suggests there might exist a relation between our voting model and classic market models for economies with public goods. In this section we explain this relation in more detail, focusing on the most influential equilibrium concept from the literature on public goods the Lindahl equilibrium, which was formalized by Foley (1970). The relation that we explain in this section: (i) gives additional insights into the concept of SP, and (ii) explains the key differences that prohibit one to use the concepts from the public economics directly for designing voting systems. The public economics (PE) model for committee elections (CE), adapted from Foley (1970), is set up as follows. Each voter is endowed with 1 dollar; thus, the total endowment is n dollars. We imagine that there is a producer who will set up the committee in exchange for money. The production function π: 2C R+ assigns to each committee W C the cost to the producer of producing W.3 We assume the cost of producing a candidate is the same for all candidates, so we use π(W) = |W| p for some p R+ and all W C. A PE price system is a collection {γi}i N, where each γi is a payment function (see the definitions at the beginning of this section). PE price systems differ from the previously considered price systems which we now call CE price systems. In PE price systems, the endowments are fixed, while in CE price systems they are allowed to vary. To avoid confusion we use different symbols to denote PE and CE price system (γi and pi, respectively). A committee W is in Lindahl equilibrium if there is a price system {γi}i N such that the following conditions hold:

(Lin-PM). Profit maximization: For each W C it holds that: X

| {z } total payments for the produced public goods

| {z } total cost of production

i N γi(c) π(W ).

Note that since π( ) = 0 the above condition implies a feasibility condition: P c W P i N γi(c) π(W) (the total payments payed to W are sufficient to produce W).

(Lin-UM). Utility maximization: voters spend their money to maximise their utility. For each voter i we have that:

(a) P c W γi(c) 1 (feasibility), and

3In Foley s model (Foley 1970), the production function specifies how private goods can be transformed into public goods. In our case, we assume there is only one private good, money (which represents voting power); the candidates are the public goods. Thus, as in Foley s model, the production function describes how private goods can be transformed into public goods. A crucial difference to Foley s model is that we use an indivisible model, where each candidate can be either bought (elected) or not, and there are no intermediate states. Due to indivisibilities, Foley s existence proof does not apply. Further, in our model each candidate is available in a single copy, which can affect decisions of the producers, and thus the prices.

(b) there is no committee W with P c W γi(c) 1 and:

In the definition above, the relation can be defined arbitrarily however, we further assume that it is equivalent to the one defined in (2). In the divisible PE model (where we can elect candidates fractionally) the conditions (Lin-PM) and (Lin-UM) are always satisfiable, and the resulting committee is guaranteed to be in the core (Foley 1970). For us, neither is true. We start by providing an example of a profile where a Lindahl equilibrium is not Pareto optimal. Example 2. There are 3 candidates C = {a, b1, b2}, and 2 voters:

A(1) = {a, b1} A(2) = {a, b2}.

Assume the price for each candidate is p = 2/3 (as each voter has 1 dollar, we can buy at most 3 candidates). Consider the following price system:

γ1(a) = 2/3 3/1000 γ2(a) = 2/3 3/1000 γ1(b1) = 2/3 2/1000 γ2(b1) = 1/1000 γ1(b2) = 1/1000 γ2(b2) = 2/3 2/1000.

This price system witnesses that {a} is a Lindahl equilibrium. Intuitively, the producer wants to produce a and does not want to produce b1 nor b2. Also, each voter prefers to spend her money on a than on b1 or b2, and cannot buy both. Yet, {a} is Pareto-dominated by {a, b1, b2}.

The problem underlying Example 2 is that the producer gets paid less than the cost of b1 and b2 if the producer chooses to produce these candidates. In contrast, the producer receives a payment of almost double the cost of a for producing a. Thus, in this equilibrium, the producer is better off at the cost of consumers. In the divisible model this issue never appears: in every Lindahl equilibrium the total payment to the producer for producing a unit of candidate c is always equal to the cost of producing that unit. (Otherwise, the producer would want to produce an unlimited amount of c.) Since this equality is implied in the divisible model, it is natural to add it as an additional property to our definition of Lindahl equilibrium in the indivisible model. We say that a committee W is a cost-efficient Lindahl equilibrium (CELE) if there exists a price system {γi}i N that satisfies (Lin-PM), (Lin-UM), and:

(Lin-CE). Cost-Efficiency: P c W P i N γi(c) π(W).

By (Lin-PM), the condition in (Lin-CE) could also be written as an equality. Further, by (Lin-PM) and (Lin-CE) we can infer a seemingly stronger condition, that for each c W: P i N γi(c) = π(c).

Theorem 5, below, shows a close relationship between stable priceability and Lindahl equilibrium. Let us slightly adapt condition (S5), by making the first inequality weak, and the third inequality strict. We refer to this condition as (S5*) and call the resulting solution concept strict SP.

Proposition 2. Every strict SP committee is SP.

We chose SP based on (S5) as our official definition, because strict SP does not exist even on very simple instances, as illustrated in Example 3 below.

Example 3. Consider an election with two voters and two candidates, a and b, both approved by one voter. The goal is to select a committee of size k = 1. It is straighforward to check that the only strict SP committees are and {a, b}, both of which are not feasible.

As one of our main results, we can prove that strict SP coincides with cost-efficient Lindahl equilibrium.

Theorem 5. Cost-efficient Lindahl equilibrium results in the same fairness notion as strict SP for the same price p.

Based on this equivalence, we can immediately deduce several other properties of cost-efficient Lindahl equilibria.

Corollary 4. Cost-efficient Lindahl Equilibria are SP.

Corollary 5. Every feasible committee that is in a costefficient Lindahl equilibrium is in the core.

The latter result mirrors Foley s theorem in the classical model (Foley 1970). Summarizing, the idea of SP is very close to the idea of Lindahl equilibrium. The key conceptional difference is that in the public economics model, the price of the candidates is a fixed element of the model. In our case, the price is an adjustable part of price systems the voters do not truly have money, they only have preferences, and money is a virtual concept that we use to ensure that public decisions are fair.

Balanced Price Systems

So far we have considered priceability notions where two voters could face significantly different prices for the same candidate. This can seem unnatural why does one voter need to pay much more for the same thing as another? and might thereby limit the usefulness of using these price systems as explanations. Here, we will study what happens if we insist that all voters pay the same price. As before, we assume that in order to be selected, a candidate needs to collect a total payment of some value p that is identical across candidates. Previously, we implicitly assumed that whenever a candidate c is picked, all the voters obtain utility from c s election. Now, we will assume that voters only appreciate candidates when they had to pay for them. More concretely, in this section we consider price systems where for each candidate c there is one individual price ρc. A voter i, in order to be able to derive utility from the elected candidate c, needs to pay ρc dollars.

As we have argued in the previous section, there is convincing evidence that stable priceability gives strong fairness guarantees. However, as we just noted, when voters pay different prices for the same candidate, there can be cases where even stable priceable committees can be argued to not be entirely fair.

v1 v2 v3 v4 v5 v6 v7 v8 v9

c1 c2 c3 c4 c5 c6

c10 c11 c12

v1 v2 v3 v4 v5 v6 v7 v8 v9

c1 c2 c3 c4 c5 c6

c10 c11 c12

Figure 2: The illustration of Example 4

Example 4. Consider an election with 12 candidates and 9 voters. The voters have the following approval sets. All 9 voters approve candidates c1, c2, and c3. Further, voters v1, v2, v3 approve c4, c5, and c6; voters v4, v5, v6 approve c7, c8, and c9; and voters v7, v8, v9 approve c10, c11, and c12. The committee size is k = 9. The election is depicted in Figure 2. Here, the committee marked green in the left-hand side of the figure is SP. The corresponding price system can be the following: The price is p = 1

3. Each from the last three voters (v7, v8 and v9) pays 1/3 for each commonly approved candidate (c1, c2 and c3). The voters v1, v2, v3 pay 1/3 for candidates c4, c5, and c6; the voters v4, v5, v6 pay 1/3 for candidates c7, c8, and c9. However, the committee is arguably not fair. A much better choice would be to pick the committee marked blue in the right-hand side part of the figure.

The reason why the SP solution from Example 4 is not fair is that the candidates who are approved by all the voters (candidates c1, c2, and c3), are paid for by only a small subset of them. Example 4 shows that the properties of committees supported by stable price systems very much depend on the structure of payment functions. Specifically, in Example 4 the payment functions were very unbalanced. Even though all voters approved c1, only v7, v8, and v9 payed for it. In a way, the mechanism stole money from v7, v8, and v9, depriving them the possibility of paying for other candidates. This example suggests that in an ideally-fair price system, all voters who enjoy the same utility from the same candidate should pay the same amount of money for it. We call such price systems balanced.

Formal Definition

The notion of balanced stable priceability differs from the notion of stable priceability in two main aspects. First, we require that any two voters, i and j, who decide to pay for a given candidate c must pay the same price, i.e., pi(c) = pj(c). Second, we allow a voter not to pay for some elected candidates but then the voter takes no utility from an approved candidate, even if the candidate is elected. This affects how we represent the committees. Now, a committee is a pair (W, {ui}i N), where ui : W {0, 1} is a binary utility function denoting whether voter i can use candidate c. We assume that, for each i N and c W, c / Ai = ui(c) = 0 (voters are never interested in using

candidates they do not approve). For convenience, we extend the utility function to sets: for each i N and X W, we set ui(X) = P c X ui(c). We say that a committee (W, {ui}i N) is supported by a balanced stable price system (BSP) ps = (p, {pi}i N) if ps satisfies conditions (C2) (C4), and:

(E1). Balanced payments: For each c W, there exists a value ρc such that either pi(c) = ρc, or ui(c) = 0. Equivalently, pi(c) = ui(c) ρc.

(E5). Condition for Stability: There exists no coalition of voters S N, no committee (W , {u i}i N) (W C \ W) and no collections {p i}i S (p i : W [0, 1]) and {Ri}i N , (with Ri W for each i N) such that all the following conditions hold:

1. For each c W , there exists a value ρc such that p i(c) = u i(c) ρc 2. For each c W : P i S p i(c) > p. 3. For each i S: pi(W \ Ri) + p i(W ) 1. 4. For each i S: ui(W \ Ri) + u i(W ),pi(W \ Ri) + p i(W ) ui(W),pi(W) .

Intuitively, (E1) implies (C1) and requires that all the voters using a candidate c pay the same for c. (E5) is similar to (S5) with the additional requirement that the new payments that witness breaking the stability must also be balanced. The green committee in Example 4 is not BSP. The price system given in the example violates condition (E5): all the voters would prefer to share the cost of candidate c1 (W = {c1} and ρ (c1) = 1/9). The first three voters would prefer to pay for c1 instead of c4 (W i = {c1}, Ri = {c4}), since then the number of their representatives would not change recall that according to our definition of stability, a voter cannot be represented by a candidate for whom she does not pay but they would need to pay for them a smaller amount of money (they would need to pay 1/9 dollars for c1 versus 1/3 dollars for c4). Similarly, voters v4, v5, and v6 would prefer to pay for c1 instead of c7 (W i = {c1}, Ri = {c7}). Finally, the last 3 voters would be happy with the change (W i = {c1}, Ri = {c1}) since the individual price they would need to pay for c1 would be lower (1/9 instead of 1/3). Besides being an intuitively appealing property, BSP also implies some other well-known fairness properties, like EJR.

Proposition 3. Every feasible BSP committee satisfies EJR.

A Characterization of BSP Committees Like in the case of SP, imposing |W | 1 in the definition of BSP does not reduce the strength of the notion. Indeed, below we present the analogue of Theorem 1 for (E5), (E1) and a suitably modified inequality (3):

c/ W S N(c)|S| min i S max max c W (pi(c )) , ri

Theorem 6. Inequality (4) together with condition (E1) is equivalent to condition (E5).

This result allows us to prove that BSP committees can be found and verified in polynomial time, as stated in the following theorem: Theorem 7. It can be verified in polynomial time whether a given committee is BSP. Besides, for given election instance and price p, a BSP committee can be found in polynomial time. We discuss this issue in detail in Appendix A.10 intuituvely, we design a voting rule computable in polynomial time characterizing the set of BSP committees. This rule is a slight modification of a rule that was recently proposed by Peters and Skowron (2020) under the name of Rule X. Basing on the characterization, in Appendix C.2 we describe a polynomial-time heuristic algorithm for finding BSP committees of a specified size k.

Existence Like for SP, one could wonder whether BSP committees always exist, that is exist for every size k. The answer again is negative. Theorem 8. There exists an election for which no feasible committee is supported by an BSP price system. Using heuristic algorithms, we can show that in practice, committees which are almost BSP exist. In Appendix D we describe experiments that provide quantive arguments for the viability of this approach.

Conclusion In this paper we have introduced two market-based solution concepts that allow to reason about, explain, and justify fairness of the outcome of an election to voters. We specifically focussed on approval-based committee elections, though our concepts generalize to participatory budgeting with cardinal utilities (we discuss this generalization in Appendix E). We have shown relations between our notions of stable priceability and known concepts of fairness and stability from the literature, such as EJR, core, proportionality degree, and Lindahl equilibrium. We have characterized the stable-priceable outcomes using simpler formulas, which allowed us to obtain more efficient algorithms for finding stable-priceable outcomes. As a consequence, we have characterized a close variant of Rule X as the only rule that returns BSP committees. Although SP/BSP committees do not always exist, our algorithms allow to find committees which are close to being SP/BSP through extensive experiments we have shown that these algorithms can effectively find stable-priceable committees which are almost feasible.

Acknowledgments Grzegorz Pierczy nski and Piotr Skowron were supported by Poland s National Science Center grant UMO2019/35/B/ST6/02215. Nisarg Shah was partially supported by an NSERC Discovery Grant.

References Amoussou-Guenou, Y.; Biais, B.; Potop-Butucaru, M.; and Tucci Piergiovanni, S. 2020a. Rational Behavior in

Committee-Based Blockchains. IACR Cryptol. e Print Arch. 2020: 710. URL https://eprint.iacr.org/2020/710.

Amoussou-Guenou, Y.; Biais, B.; Potop-Butucaru, M.; and Tucci Piergiovanni, S. 2020b. Rational vs Byzantine Players in Consensus-based Blockchains. In Seghrouchni, A. E. F.; Sukthankar, G.; An, B.; and Yorke-Smith, N., eds., Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 20, Auckland, New Zealand, May 9-13, 2020, 43 51. International Foundation for Autonomous Agents and Multiagent Systems. URL https://dl.acm.org/doi/abs/10.5555/3398761.3398772.

Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified Representation in Approval Based Committee Voting. Social Choice and Welfare 48(2): 461 485.

Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, L.; and Skowron, P. 2018. On the Complexity of Extended and Proportional Justified Representation. In Proceedings of the 32nd Conference on Artificial Intelligence (AAAI-2018).

Aziz, H.; and Monnot, J. 2020. Computing and testing Pareto optimal committees. Autonomous Agents and Multi-Agent Systems 34(1): 1 20.

Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; and Niedermeier, R. 2019. An Experimental View on Committees Providing Justified Representation. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2019), 109 115.

Brill, M.; Freeman, R.; Janson, S.; and Lackner, M. 2017. Phragm en s Voting Methods and Justified Representation. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI-2017), 406 413.

Cheng, Y.; Jiang, Z.; Munagala, K.; and Wang, K. 2019. Group Fairness in Committee Selection. In Proceedings of the 2019 ACM Conference on Economics and Computation, 263 279. ACM.

Fain, B.; Goel, A.; and Munagala, K. 2016. The core of the participatory budgeting problem. In Proceedings of the 12th Workshop on Internet & Network Economics (WINE), 384 399.

Fain, B.; Munagala, K.; and Shah, N. 2018. Fair allocation of indivisible public goods. In Proceedings of the 2018 ACM Conference on Economics and Computation, 575 592. ACM. Extended version ar Xiv:1805.03164.

Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner Voting: A New Challenge for Social Choice Theory. In Endriss, U., ed., Trends in Computational Social Choice. AI Access.

Farahani, F. Z.; and Hekmatfar, M., eds. 2009. Facility Location: Concepts, Models, and Case Studies. Springer.

Foley, D. K. 1970. Lindahl s Solution and the Core of an Economy with Public Goods. Econometrica 38(1): 66 72.

Jiang, Z.; Munagala, K.; and Wang, K. 2019. Approximately Stable Committee Selection. ar Xiv:1910.14008.

Lackner, M.; and Skowron, P. 2018. Consistent Approval Based Multi-Winner Rules. In Proceedings of the 19th ACM Conference on Economics and Computation (EC-2018), 47 48. Lackner, M.; and Skowron, P. 2020. Approval-Based Committee Voting: Axioms, Algorithms, and Applications. Technical Report ar Xiv:2007.01795 [cs.GT], ar Xiv.org. Peters, D.; and Skowron, P. 2020. Proportionality and the Limits of Welfarism. In Proceedings of the 2020 ACM Conference on Economics and Computation, 793 794. Extended version ar Xiv:1911.11747.

S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017. Proportional justified representation. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI-2017), 670 676. Skowron, P. 2018. Proportionality Degree of Multiwinner Rules. Technical Report ar Xiv:1810.08799 [cs.GT], ar Xiv.org. Skowron, P.; Faliszewski, P.; and Lang, J. 2016. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence 241: 191 216.