|
Participatory Budgeting Rule
Combinatorial participatory budgeting, also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate ''projects'', each of which has a fixed costs. There is a fixed ''budget'', that cannot cover all these projects. Each voter has different ''preferences'' regarding these projects. The goal is to find a ''budget-allocation'' - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting. Combinatorial PB can be seen as a generalization of committee voting: committee voting is a special case of PB in which the "cost" of each candidate is 1, and the "budget" is the committee size. This assumption is often called the ''unit-cost assumption''. The setting in which the projects are divisible (can receive any amount of money) is called portioning, fractional social choice, or budget-proposal aggregation. PB ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Social Choice
Social choice theory is a branch of welfare economics that extends the theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures ( social welfare functions) used to combine individual preferences into a coherent whole.Amartya Sen (2008). "Social Choice". ''The New Palgrave Dictionary of Economics'', 2nd EditionAbstract & TOC./ref> It contrasts with political science in that it is a normative field that studies how a society can make good decisions, whereas political science is a descriptive field that observes how societies actually do make decisions. While social choice began as a branch of economics and decision theory, it has since received substantial contributions from mathematics, philosophy, political science, and game theory. Real-world examples of social choice rules include constitutions and parliamentary procedures for voting on laws, as well as electoral systems; as such, the field is occasionall ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
CoNP-hard
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly. Each co-NP-complete problem is the complement of an NP-complete problem. There are some problems in both NP and co-NP, for example all problems in P or integer factorization. However, it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete for more details. Fortune showed in 1979 that if any sparse language is co-NP-complete (or even just co-NP-hard), then , a critical foundation for Mahaney's theorem. Formal definition A decision prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subset Sum Problem
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: * The variant in which all inputs are positive. * The variant in which inputs may be positive or negative, and T=0. For example, given the set \, the answer is ''yes'' because the subset \ sums to zero. * The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., T = \frac(a_1+\dots+a_n) . This special case of SSP is known as the partition problem. SSP can also be regarded as an optimization problem: find a subset whose sum is at most ''T'', and subject to that, as close as possible to ''T''. It is NP-hard, but there are several algorithms that can solve it reasonably q ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Justified Representation
Justified representation (JR) is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting. Background Proportional representation (PR) is an important consideration in designing electoral systems. It means that the various groups and sectors in the population should be represented in the parliament in proportion to their size. The most common system for ensuring proportional representation is the party-list system. In this system, the candidates are partitioned into parties, and each citizen votes for a single party. Each party receives a number of seats proportional to the number of citizens who voted for it. For example, for a parliament with 10 seats, if exactly 50% of the citizens vote for party A, exactly 30% vote for party B, and exactly 20% vote for party C, then proportional representation requires that the parliament contains exactly 5 candidates from party A, exactly 3 can ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Majority Rule
In social choice theory, the majority rule (MR) is a social choice rule which says that, when comparing two options (such as bills or candidates), the option preferred by more than half of the voters (a ''majority'') should win. In political philosophy, the ''majority rule'' is one of two major competing notions of democracy. The most common alternative is given by the utilitarian rule (or other welfarist rules), which identify the spirit of liberal democracy with the equal consideration of interests.Ball, Terence and Antis Loizides"James Mill" The Stanford Encyclopedia of Philosophy (Winter 2020 Edition), Edward N. Zalta (ed.). Although the two rules can disagree in theory, political philosophers beginning with James Mill have argued the two can be reconciled in practice, with majority rule being a valid approximation to the utilitarian rule whenever voters share similarly-strong preferences. This position has found strong support in many social choice models, where the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Expanding Approvals Rule
An expanding approvals rule (EAR) is a rule for multi-winner elections, which allows agents to express weak ordinal preferences (i.e., ranking with indifferences), and guarantees a form of proportional representation called proportionality for solid coalitions. The family of EAR was presented by Aziz and Lee. In general, the EAR algorithm works as follows. Let ''n'' denote the number of voters, and ''k'' the number of seats to be filled. Initially, each voter is given 1 unit of virtual money. Groups of voters can use their virtual money to "buy" candidates, where the "price" of each candidate is n/k (though the divisor can be slightly different; see highest averages method). The EAR goes rank by rank, starting at rank 1 which corresponds to the top candidates of the voters, and increasing the rank in each iteration. (This is where the term "expanding approvals" comes from: as the rank increases, the number of approved candidates expands.) For each rank ''r'': # EAR checks if th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Single Transferable Vote
The single transferable vote (STV) or proportional-ranked choice voting (P-RCV) is a multi-winner electoral system in which each voter casts a single vote in the form of a ranked ballot. Voters have the option to rank candidates, and their vote may be transferred according to alternative preferences if their preferred candidate is eliminated or elected with surplus votes, so that their vote is used to elect someone they prefer over others in the running. STV aims to approach proportional representation based on votes cast in the district where it is used, so that each vote is worth about the same as another. STV is a family of multi-winner proportional representation electoral systems. The proportionality of its results and the proportion of votes actually used to elect someone are equivalent to those produced by proportional representation election systems based on lists. STV systems can be thought of as a variation on the largest remainders method that uses candidate-based so ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schwartz Set
The Smith set, sometimes called the top-cycle or Condorcet winning set, generalizes the idea of a Condorcet winner to cases where no such winner exists. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner. Voting systems that always elect a candidate from the Smith set pass the Smith criterion. The Smith set and Smith criterion are both named for mathematician John H. Smith. The Smith set provides one standard of optimal choice for an election outcome. An alternative, stricter criterion is given by the Landau set. Definition The Smith set is formally defined as the smallest set such that every candidate inside the set ''S'' pairwise defeats every candidate outside ''S''. Alternatively, it can be defined as the set of all candidates with a (non-strict) beatpath to any candidate who defeats them. A set of candidates each of whose members pairwise defeats every candidate outside the set is known as a ''dominating set'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Condorcet Criterion
A Condorcet winner (, ) is a candidate who would receive the support of more than half of the electorate in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the Condorcet winner criterion. The Condorcet winner criterion extends the principle of majority rule to elections with multiple candidates. Named after Nicolas de Condorcet, it is also called a majority winner, a majority-preferred candidate, a beats-all winner, or tournament winner (by analogy with round-robin tournaments). A Condorcet winner may not necessarily always exist in a given electorate: it is possible to have a rock, paper, scissors-style cycle, when multiple candidates defeat each other (Rock < Paper < Scissors < Rock). This is called , and is analogous to the counterintuitive [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Method Of Equal Shares
The method of equal shares is a proportional method of counting ballots that applies to participatory budgeting, to committee elections, and to simultaneous public decisions. It can be used when the voters vote via approval ballots, ranked ballots or cardinal ballots. It works by dividing the available budget into equal parts that are assigned to each voter. The method is only allowed to use the budget share of a voter to implement projects that the voter voted for. It then repeatedly finds projects that can be afforded using the budget shares of the supporting voters. In contexts other than participatory budgeting, the method works by equally dividing an abstract budget of "voting power". In 2023, the method of equal shares was being used in a participatory budgeting program in the Polish city of Wieliczka. The program, known as Green Million (''Zielony Milion''), was set to distribute 1 million złoty to ecological projects proposed by residents of the city. It was also used ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiwinner Voting
Multiwinner or committee voting refers to electoral systems that elect several candidates at once. Such methods can be used to elect parliaments or committees. Goals There are many scenarios in which multiwinner voting is useful. They can be broadly classified into three classes, based on the main objective in electing the committee: # Excellence. Here, voters judge the quality of each candidate individually. The goal is to find the "objectively" best candidates. An example application is shortlisting: selecting, from a list of candidate employees, a small set of finalists, who will proceed to the final stage of evaluation (e.g. using an interview). Here, each candidate is evaluated independently of the others. If two candidates are similar, then probably both will be elected or both will be rejected. # Diversity. Here, the elected candidates should be as ''different'' as possible. For example, suppose the contest is about choosing locations for two fire stations or other fac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
