Re: [EM] Compromise allocation of fair share
On Wed, May 18, 2011 at 5:26 PM, wrote: > > > Forrest, > > > > I'm trying to make sure I understand exactly what the "Ultimate > > Lottery"methods are. > > > > So the "Ultimate Lottery" singlewinner method is: > > > > 1. Voters submit homogeneous functions of p1,p2,...,pn > > 2. Choose the configuration (p1,p2,...,pn) which maximizes the > > product of > > all voters' functions > > 3. Use a lottery that elects candidate i with probability pi. > > (Ideally we would solve the maximization problem over the space > > of all > > possible p1,p2,...,pn which sum to 1. If that's not possible we > > can allow > > people to submit possible outcomes and just choose the maximum > > one out of > > all the submissions.) > > > > And the "Ultimate Lottery" multiwinner method is: > > > > 1. Voters submit homogeneous functions of p1,p2,...,pn > > 2. Choose the configuration (p1,p2,...,pn) which maximizes the > > product of > > all voters' functions > > 3. Entity i gets voting power pi in the parliament. > > (We can restrict the space we're considering so no more than M > > entities get > > seated, or we can just consider the whole space and seat anyone with > > positive voting power.) > > > > Is this correct? > > > > Andy > > > > Yes, with the understanding that all of the homogeneous functions are of > the same degree and non- > decreasing in each of the arguments. > Oh yeah. I forgot about the non-decreasing-in-each-argument constraint. That would translate into a more complicated constraint if voters were allowed to specify a function on the simplex, then. Andy Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Compromise allocation of fair share
- Original Message - From: Andy Jennings Date: Wednesday, May 18, 2011 2:02 pm Subject: Re: [EM] Compromise allocation of fair share To: fsimm...@pcc.edu Cc: election-methods@lists.electorama.com > Forrest, > > I'm trying to make sure I understand exactly what the "Ultimate > Lottery"methods are. > > So the "Ultimate Lottery" singlewinner method is: > > 1. Voters submit homogeneous functions of p1,p2,...,pn > 2. Choose the configuration (p1,p2,...,pn) which maximizes the > product of > all voters' functions > 3. Use a lottery that elects candidate i with probability pi. > (Ideally we would solve the maximization problem over the space > of all > possible p1,p2,...,pn which sum to 1. If that's not possible we > can allow > people to submit possible outcomes and just choose the maximum > one out of > all the submissions.) > > And the "Ultimate Lottery" multiwinner method is: > > 1. Voters submit homogeneous functions of p1,p2,...,pn > 2. Choose the configuration (p1,p2,...,pn) which maximizes the > product of > all voters' functions > 3. Entity i gets voting power pi in the parliament. > (We can restrict the space we're considering so no more than M > entities get > seated, or we can just consider the whole space and seat anyone with > positive voting power.) > > Is this correct? > > Andy > Yes, with the understanding that all of the homogeneous functions are of the same degree and non- decreasing in each of the arguments. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Compromise allocation of fair share
Forrest, I'm trying to make sure I understand exactly what the "Ultimate Lottery" methods are. So the "Ultimate Lottery" singlewinner method is: 1. Voters submit homogeneous functions of p1,p2,...,pn 2. Choose the configuration (p1,p2,...,pn) which maximizes the product of all voters' functions 3. Use a lottery that elects candidate i with probability pi. (Ideally we would solve the maximization problem over the space of all possible p1,p2,...,pn which sum to 1. If that's not possible we can allow people to submit possible outcomes and just choose the maximum one out of all the submissions.) And the "Ultimate Lottery" multiwinner method is: 1. Voters submit homogeneous functions of p1,p2,...,pn 2. Choose the configuration (p1,p2,...,pn) which maximizes the product of all voters' functions 3. Entity i gets voting power pi in the parliament. (We can restrict the space we're considering so no more than M entities get seated, or we can just consider the whole space and seat anyone with positive voting power.) Is this correct? Andy On Wed, May 18, 2011 at 11:51 AM, wrote: > - Original Message - > From: Andy Jennings > Date: Wednesday, May 18, 2011 7:14 am > Subject: Re: [EM] Compromise allocation of fair share > To: fsimm...@pcc.edu > Cc: election-methods@lists.electorama.com > > > Forrest, > > > > On Wed, Dec 15, 2010 at 4:39 PM, wrote: > > > > > I would like to modify my proposal for a new kind of list PR method. > > > > > > 1. Voters submit ballots indicating their favorite parties. > > These ballots > > > are used to find the standard list PR allocation of N seats by > > some standard > > > method. We call this allocation the Fallback allocation. > > > > > > 2. All interested entities submit as many allocation > > nominations as > > > desired. We require that these allocate whole numbers of > > seats to the > > > parties, with the total number of seats equal to the same > > number N in all > > > cases. Let the letter S represent the set of these nominated > > allocations,> with the Fallback allocation included, > > > > > > 3. Voters also submit ballots indicating their criteria for > > ordering the > > > members of the set S. Let Beta be the set of these ballots. > > For example one > > > voter could say that of any two allocations she prefers the > > one which gives > > > the least number of seats to party P7. > > > > > > 4. Voters also submit ballots in the form of functions that are > > > homogeneous of degree one for the purpose of contrilling their > > share of the > > > allocation in the optimization step below. Call this set of > > ballots H, for > > > "homogeneous." > > > > > > 5. Eliminate all of the members of S that do not Pareto > > dominate the > > > Fallback allocation according to the ballots in the set Beta. > > Let S' be the > > > subset of non-eliminated members of S. > > > > > > 6. Let S'' be the set of all members of S' that are not > > Pareto dominated > > > by some other member of S'. > > > > > > 7. Allocate the seats to the various parties P1, P2, ... etc. > > in accord > > > with the allocation p=(p1, p2, ...) from S'' that maximizes > > > > > > the product (over f in H) of f(p) . > > > > > > > > > > Is this still your current proposal for a Ultimate Lottery-based > > PR method? > > Not "proposal" so much as an example of where you end up if you take > fairness, > expressivity, and manipulation resistance to their logical conclusion in > one > grand method. > > > I have some questions about it. > > > > 1. Is it really necessary for voters to choose a "homogeneous of > > degree one" > > function to broker their evaluation of S* in step 7? Wouldn't > > the voters' > > functions be evaluated (in step 7) only on the simplex > > p1+p2+...+pn=1? Why > > not let each voter specify an arbitrary function on the simplex? > > If a > > homogeneous function is needed for proofs, then you can use the unique > > homogeneous function generated by the values on the simplex. > > Good point! > > > > > 2. Why must the voters give two different schemes for evaluating the > > outcomes? Shouldn't each voter's function, f, be enough to > > create their > > ordering of the ballots in step 2? > > Two reasons: (1) The functions in H might not be capable of enoug
Re: [EM] Compromise allocation of fair share
- Original Message - From: Andy Jennings Date: Wednesday, May 18, 2011 7:14 am Subject: Re: [EM] Compromise allocation of fair share To: fsimm...@pcc.edu Cc: election-methods@lists.electorama.com > Forrest, > > On Wed, Dec 15, 2010 at 4:39 PM, wrote: > > > I would like to modify my proposal for a new kind of list PR method. > > > > 1. Voters submit ballots indicating their favorite parties. > These ballots > > are used to find the standard list PR allocation of N seats by > some standard > > method. We call this allocation the Fallback allocation. > > > > 2. All interested entities submit as many allocation > nominations as > > desired. We require that these allocate whole numbers of > seats to the > > parties, with the total number of seats equal to the same > number N in all > > cases. Let the letter S represent the set of these nominated > allocations,> with the Fallback allocation included, > > > > 3. Voters also submit ballots indicating their criteria for > ordering the > > members of the set S. Let Beta be the set of these ballots. > For example one > > voter could say that of any two allocations she prefers the > one which gives > > the least number of seats to party P7. > > > > 4. Voters also submit ballots in the form of functions that are > > homogeneous of degree one for the purpose of contrilling their > share of the > > allocation in the optimization step below. Call this set of > ballots H, for > > "homogeneous." > > > > 5. Eliminate all of the members of S that do not Pareto > dominate the > > Fallback allocation according to the ballots in the set Beta. > Let S' be the > > subset of non-eliminated members of S. > > > > 6. Let S'' be the set of all members of S' that are not > Pareto dominated > > by some other member of S'. > > > > 7. Allocate the seats to the various parties P1, P2, ... etc. > in accord > > with the allocation p=(p1, p2, ...) from S'' that maximizes > > > > the product (over f in H) of f(p) . > > > > > > Is this still your current proposal for a Ultimate Lottery-based > PR method? Not "proposal" so much as an example of where you end up if you take fairness, expressivity, and manipulation resistance to their logical conclusion in one grand method. > I have some questions about it. > > 1. Is it really necessary for voters to choose a "homogeneous of > degree one" > function to broker their evaluation of S* in step 7? Wouldn't > the voters' > functions be evaluated (in step 7) only on the simplex > p1+p2+...+pn=1? Why > not let each voter specify an arbitrary function on the simplex? > If a > homogeneous function is needed for proofs, then you can use the unique > homogeneous function generated by the values on the simplex. Good point! > > 2. Why must the voters give two different schemes for evaluating the > outcomes? Shouldn't each voter's function, f, be enough to > create their > ordering of the ballots in step 2? Two reasons: (1) The functions in H might not be capable of enough expression for some voters, and (2) if the ballots of Beta were used for anything beyond the Pareto (i.e. unanimous) decisions, there would be incentives for insincere ranking. Essentially, all of the allocations in S'' are Pareto tied improvements on the fallback allocation, and the Ultimate Lottery step based on the ballots in H is used to break the tie. > > 3. Are the Pareto elimination steps in 5 and 6 necessary? It > seems that > Pareto domination would be very rare so steps 5 and 6 would > hardly ever do > anything. Even if a Pareto dominated option made it through > steps 5 and 6, > it seems like it could never win in step 7. (Assuming each > voter's f > function is compatible with their rank-ordering scheme.) > > I'm really starting to like the simpler system where every voter > submits a > linear utility function and we choose the allocation that > maximizes the > product of the utilities. It is completely invariant to any voter > re-scaling their utility function (though not to translation), [this is a property that is preserved by homogeneous functions] > and it does > seem very likely to "do the right thing" without rewarding > strategy very > much. As in range voting the method has no need for insincere strategy, but it is not strategy proof. Use of max and min functions (which are also homogeneous) makes for easier, more robust strategy. If we wanted to restrict to some subset of H, instead of linear combinations of the p_i , I would take combinations generated b
Re: [EM] Compromise allocation of fair share
Forrest, On Wed, Dec 15, 2010 at 4:39 PM, wrote: > I would like to modify my proposal for a new kind of list PR method. > > 1. Voters submit ballots indicating their favorite parties. These ballots > are used to find the standard list PR allocation of N seats by some standard > method. We call this allocation the Fallback allocation. > > 2. All interested entities submit as many allocation nominations as > desired. We require that these allocate whole numbers of seats to the > parties, with the total number of seats equal to the same number N in all > cases. Let the letter S represent the set of these nominated allocations, > with the Fallback allocation included, > > 3. Voters also submit ballots indicating their criteria for ordering the > members of the set S. Let Beta be the set of these ballots. For example one > voter could say that of any two allocations she prefers the one which gives > the least number of seats to party P7. > > 4. Voters also submit ballots in the form of functions that are > homogeneous of degree one for the purpose of contrilling their share of the > allocation in the optimization step below. Call this set of ballots H, for > "homogeneous." > > 5. Eliminate all of the members of S that do not Pareto dominate the > Fallback allocation according to the ballots in the set Beta. Let S' be the > subset of non-eliminated members of S. > > 6. Let S'' be the set of all members of S' that are not Pareto dominated > by some other member of S'. > > 7. Allocate the seats to the various parties P1, P2, ... etc. in accord > with the allocation p=(p1, p2, ...) from S'' that maximizes > > the product (over f in H) of f(p) . > > Is this still your current proposal for a Ultimate Lottery-based PR method? I have some questions about it. 1. Is it really necessary for voters to choose a "homogeneous of degree one" function to broker their evaluation of S* in step 7? Wouldn't the voters' functions be evaluated (in step 7) only on the simplex p1+p2+...+pn=1? Why not let each voter specify an arbitrary function on the simplex? If a homogeneous function is needed for proofs, then you can use the unique homogeneous function generated by the values on the simplex. 2. Why must the voters give two different schemes for evaluating the outcomes? Shouldn't each voter's function, f, be enough to create their ordering of the ballots in step 2? 3. Are the Pareto elimination steps in 5 and 6 necessary? It seems that Pareto domination would be very rare so steps 5 and 6 would hardly ever do anything. Even if a Pareto dominated option made it through steps 5 and 6, it seems like it could never win in step 7. (Assuming each voter's f function is compatible with their rank-ordering scheme.) I'm really starting to like the simpler system where every voter submits a linear utility function and we choose the allocation that maximizes the product of the utilities. It is completely invariant to any voter re-scaling their utility function (though not to translation), and it does seem very likely to "do the right thing" without rewarding strategy very much. I'm still trying to understand the extra layers of complexity, including the consequences of allowing non-linear utility functions, and why they are necessary. Andy Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Compromise allocation of fair share
I would like to modify my proposal for a new kind of list PR method. 1. Voters submit ballots indicating their favorite parties. These ballots are used to find the standard list PR allocation of N seats by some standard method. We call this allocation the Fallback allocation. 2. All interested entities submit as many allocation nominations as desired. We require that these allocate whole numbers of seats to the parties, with the total number of seats equal to the same number N in all cases. Let the letter S represent the set of these nominated allocations, with the Fallback allocation included, 3. Voters also submit ballots indicating their criteria for ordering the members of the set S. Let Beta be the set of these ballots. For example one voter could say that of any two allocations she prefers the one which gives the least number of seats to party P7. 4. Voters also submit ballots in the form of functions that are homogeneous of degree one for the purpose of contrilling their share of the allocation in the optimization step below. Call this set of ballots H, for "homogeneous." 5. Eliminate all of the members of S that do not Pareto dominate the Fallback allocation according to the ballots in the set Beta. Let S' be the subset of non-eliminated members of S. 6. Let S'' be the set of all members of S' that are not Pareto dominated by some other member of S'. 7. Allocate the seats to the various parties P1, P2, ... etc. in accord with the allocation p=(p1, p2, ...) from S'' that maximizes the product (over f in H) of f(p) . Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Compromise allocation of fair share
How to use your homogeneous degree one function ballot to control the distribution of your share of the allocation (whether of number of seats or probability): 1. As proved in the last post, if you want 100% to go to P1, then vote f(p)=p1. 2. If you want 10%, 20%, 30%, and 40% , respectively of your share to go to P1, P2, P3, and P4, then vote f(p)=p1^.1*p2^.2*p3^.3*p4^.4, and your vote will contribute tot the values of p1, p2, p3, and p4 in the perecise proportion p1:p2:p3:p4::10:20:30:40 If, on the other hand, you want to move p maximally towards that proportion, you should vote f(p)=min(p1,p2/2,p3/3,p4/4) . To be continued... Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Compromise allocation of fair share
The purpose of this message is to show the "proportionality" of allocation when it is determined by maximizing the product of ballots in the form of functions that are homogeneous of degree one in the proportion vector p. Let p = (p1, p2, ...) represent the proportion vector for allocation of seats to the respective parties P1, P2, etc. In other words, if there are N seats distributed according to p, then the respective parties get N*p1, N*p2, etc. seats. Hypothesis: Suppose that p is chosen by maximizing the product (over f in some set Beta of ballots) of f(p), subject to p being an allocation vector (i.e. having non-negative components summing to 100%). We assume that each function f in Beta is positive homogeneous of degree one in p, which means that for all positive t, the equation f(t*p)=t*f(p) obtains, and furthermore that f is positive when all of the components of p are positive, and also that f is non-decreasing in the components of p. Conclusion: If a party P1 has a fraction n/M of the voters, and these voters vote in solidarity the same ballot function f(p)=p1, then the above product maximization will allocate to party P1 the share N*n/M of seats (up to rounding), where N is the total number of seats. To prove this we will make use of Euler's theorem on homogeneous functions that says if F is homogeneous of degree m, then dot(grad(F(p)),p)=m*F(p). This theorem is easily proved by differentiating both sides of the equation that defines homogeneity of degree m, F(t*p)=F(p)*t^m, with respect to t, and then setting t=1. Now assuming that there are n+m=M voters total, and that n of these vote the function f(p)=p1, then the product to be maximized is F(p)*p1^n where F is the product of the ballots of the other m voters, and hence is a homogeneous function of degree m. To maximize we set up the Lagrangian L = ln(F(p)*p1^n)/M - lambda(p1+p2+...) which simplifies to L = (ln(F(p)) +ln(p1)*n)/M - lambda(p1+p2+..) Taking partial derivatives w.r.t. the components of p and setting to zero, and then taking the dot product with p we get (dot(grad(F(p)),p)/F(p)+n)/M - lambda = 0 . By Euler this simplifies to (m+n)/M - lambda = 0 from which it follows that the Lagrange multiplier has a value of lambda=1. Now that we know the value of lambda, let's go back and look at the partial derivative of L w.r.t. p1 multiplied by p1, i.e. the first term in the dot product: F1(p)*p1/F(p)/M + n/M -p1=0 , where F1 is the partial of F w.r.t. p1. Adding p1 to both sides (and switching sides) gives p1= n/M +F1(p)*p1/(F(p)*M), which is at least n/M, since, by hypothesis, the neglected term is a quotient of products of non-negative values. So the method says that party P1 should get at least n/M of the seats, i.e. n*N/M seats up to rounding, which is what we set out to prove in the first place. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Compromise allocation of fair share (was Fair and Democratic versus Majority Rules)
I just changed the thread name to reflect the current thrust more accurately. Here's my best elaboration of the compromise allocation idea in the Party list PR setting: 1. Anybody and everybody (corporations included, since the supreme court wants it that way) can nominate seat allocations to their hearts' content. Let S be the set of all such nominated seat allocations. 2. Each voter submits a ballot that either directly ranks all of the members of S, or else gives a well defined set of criteria for ordering them. Call this set of ballots Beta. 3. Each voter submits a function of the allocation percentages f(p1, p2, ...)=f(p) which (like a linear combination a1*p1+a2*p2+...) is homogeneous of degree one. This just means that f(t*p)=t*f(p). Call this set of of functions Phi 4. Use the members of Beta to eliminate all of the Pareto dominated allocations from S. Let S' be the set of remaining nominatated allocations. 5. The winning allocation is determined by the member p of S' that maximizes the product (over f in Phi) of f(p) . In other words, the respective parties P1, P2, ...get respective proportions p1 : p2 : ... of the seats. With this method it turns out that each faction of size large enough to merit k seats can guarantee their favorite party P_j that many seats by submitting identical bullet ballots f(p)=p_j. I'll outline a proof and give some examples in subsequent posts. Forest > So far we have established a formal analogy between lotteries > (i.e. allocations > of probability among the alternatives) in stochastic single > winner methods and > allocations of seats to parties in deterministic list PR methods. > > We left off with the promise that Jobst's solutions to the > defection problem in > the single winner lottery setting, when transferred (mutatis > mutandis) to the > multi-winner setting, would (without sacrificing determinism) > revolutionize the > world of list PR methods. > > All of Jobst's recent lottery solutions are based on this > fundamental insight: > We should take the random favorite lottery F as a basic > benchmark of democratic > fairness, and consider any lottery C unanimously preferred (even > if only > "weakly") to F as a frosting-on-the-cake improvement. In the > context of the > example of our previous installement F is the 60%A+40%B > lottery, and C is the > 100% C lottery. As in this example, so in general; because C > is (at least > weakly) preferred to F by 100% of the voters it is considered a > consensuscompromise. > > How do we take advantage of the relation between F and C? > Simply put, we use > the threat of "fall back to F" as an incentive to prevent > defection from C. > > The question is put to the voters. Do you prefer the fall back > F strictly above > the proposed compromise C? If even one voter responds > affirmatively, then the > fall back allocation is used. > > In the in the lottery context F is the random ballot lottery. > In the list PR > context F is the standard list PR method (whether based on > Webster, Jefferson, > or Hamilton, etc.) > > This idea is so simple, it's like post-it notes; everybody is > sure to say, "Why > didn't I think of that?" > > But, as they say, "The devil is in the details." The technical > difficultiesare all in how (in general) to automatically find a > good compromise allocation > (of probabilities or seats, as the case may be) by a process > that is immune to > manipulation. In the simple example given in our previous post, > 100%C is the > obvious compromise. > > In the following example > > 50 A 100, C1 90, C2 40, B 0 > 50 B 100, C2 90, C1 40, A 0 > > it is likewise obvious that the best compromise allocation is > 50%C1+50%C2. > How do we find these allocations automatically? > > Jobst has proposed many nice ways of doing this. One of the more > recent ones is > this (slightly adapted to the list PR setting to get whole > numbers of seats): > > (1) Each voter rates the competing parties on a range style ballot. > > (2) Each voter (optionally) nominates an allocation of the > seats. This could > well be done by choosing from a published list of such allocations. > > (3) Each of the nominated allocations is tested against the fall > back allocation > F on each of the ballots. Whenever the fall back allocation F > is strictly > preferred over a nominated allocation on even one ballot, that > nominatedallocation is eliminated. > > (4) If no nomination survives the previous step, then the fall > back allocation F > is used. Else ... > > (5) Calculate the compromise allocation C by averaging all of > the remaining > (i.e. uneliminated) nominations together and converting to whole > numbersaccording to Jefferson, Webster, or Hamilton (consistent > with the fall back > allocation F). > > (6) Pit the compromise allocation C head-to-head against F to > make sure the > conversion to whole numbers has not destroyed the
