|
Agreeable Subset
An agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. Finding a small agreeable subset is a problem in computational social choice. An example situation in which this problem arises is when a family goes on a trip and has to decide which items to take. Since their car is limited in size, they cannot pick all items, so they have to agree on a subset of items which are most important. If they manage to find a subset of items such that all family members agree that it is at least as good as the subset of items remaining at home, then this subset is called ''agreeable''. Another use case is when the citizens in some city want to elect a committee from a given pool of candidates, such that all citizens agree that the subset of elected candidates is at least as good as the subset of non-elected ones. Subject to that, the committee size should be as small as possible. Definitions Agreeable subset The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Social Choice
Computational social choice is a field at the intersection of social choice theory, theoretical computer science, and the analysis of multi-agent systems. It consists of the analysis of problems arising from the aggregation of preferences of a group of agents from a computational perspective. In particular, computational social choice is concerned with the efficient computation of outcomes of voting rules, with the computational complexity of various forms of manipulation, and issues arising from the problem of representing and eliciting preferences in combinatorial settings. Winner determination The usefulness of a particular voting system can be severely limited if it takes a very long time to calculate the winner of an election. Therefore, it is important to design fast algorithms that can evaluate a voting rule when given ballots as input. As is common in computational complexity theory, an algorithm is thought to be efficient if it takes polynomial time. Many popular votin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Partition Problem
In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset ''S'' of positive integers can be partitioned into two subsets ''S''1 and ''S''2 such that the sum of the numbers in ''S''1 equals the sum of the numbers in ''S''2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem". There is an optimization version of the partition problem, which is to partition the multiset ''S'' into two subsets ''S''1, ''S''2 such that the difference between the sum of elements in ''S''1 and the sum of elements in ''S''2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice. The partition problem is a special case of two related problems: * In the subset sum problem, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Item Allocation
Fair item allocation is a kind of a fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios: * Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings. * Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses. *White elephant gift exchange parties The indivisibility of the items implies that a fair division may not be possible. As an extreme example, if there is only a single item (e.g. a house), it must be given to a single partner, but this is not fair to the other partners. This is in contrast to the fair cake-cutting problem, where the dividend is divisible and a fair division always exists. In some cases, the indivisibility pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Division Among Groups
Fair division among groups (or families) is a class of fair division problems, in which the resources are allocated among ''groups'' of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are: * Several siblings inherited some houses from their parents and have to divide them. Each sibling has a family, whose members may have different opinions regarding which house is better. * A partnership is dissolved, and its assets should be divided among the partners. The partners are firms; each firm has several stockholders, who might disagree regarding which asset is more important. *The university management wants to allocate some meeting-rooms among its departments. In each department there are several faculty members, with differing opi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiwinner Elections
Multiwinner voting, also called multiple-winner elections or committee voting or committee elections, is an electoral system in which multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee. 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, each voter is an expert, and each vote expresses his/her opinion about which candidate/s is "better" for a certain task. The goal is to find the "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 other candidates. If two candidates are simila ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Participatory Budgeting Algorithm
A participatory budgeting (PB) algorithm is an algorithm for implementing participatory budgeting. The inputs to a PB algorithm are: a list of possible ''projects'' that require funding, the total available ''budget'' for funding the projects, and the ''preferences of voters'' over the project. The output of a PB algorithm is a partition of budget among the projects - determining how much money to allocate to each project. A PB algorithm can treat the projects as either ''divisible'' or ''indivisible'': * A ''divisible'' PB algorithm may allocate any amount of money to any project, as long as the sum of allocations equals the budget. It is suited for projects in which each additional dollar can be used effectively, such as charity donations. * An ''indivisible'' PB algorithm takes, as additional inputs, the costs of the projects. It returns a subset of the projects, such that the total cost of the selected projects does not exceed the budget. Each selected project is allocated its ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Item Allocation
Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent. Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. One way to attain fairness is to use monetary transfers; see Fair allocation of items and money. When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations. Finding an envy-free allocation whenever it exists Preference-orderings on bundles: envy-freeness The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice. Matroid theory borrows extensively from the terminology of both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory. Definition There are many equivalent ( cryptomorphic) ways to define a (finite) matroid.A standard source for basic definitions and results about matroids is Oxley (1992). An older standard source is Welsh (1976). See Brylawsk ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Utility
In economics, additive utility is a cardinal utility function with the sigma additivity property. Additivity (also called ''linearity'' or ''modularity'') means that "the whole is equal to the sum of its parts." That is, the utility of a set of items is the sum of the utilities of each item separately. Let S be a finite set of items. A cardinal utility function u:2^S\to\R, where 2^S is the power set of S, is additive if for any A, B\subseteq S, :u(A)+u(B)=u(A\cup B)-u(A\cap B). It follows that for any A\subseteq S, :u(A)=u(\emptyset)+\sum_\big(u(\)-u(\emptyset)\big). An additive utility function is characteristic of independent goods. For example, an apple and a hat are considered independent: the utility a person receives from having an apple is the same whether or not he has a hat, and vice versa. A typical utility function for this case is given at the right. Notes * As mentioned above, additivity is a property of cardinal utility functions. An analogous property of ordinal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monotone Preferences
In economics, an agent's preferences are said to be weakly monotonic if, given a consumption bundle x, the agent prefers all consumption bundles y that have more of all goods. That is, y \gg x implies y\succ x. An agent's preferences are said to be strongly monotonic if, given a consumption bundle x, the agent prefers all consumption bundles y that have more of at least one good, and not less in any other good. That is, y\geq x and y\neq x imply y\succ x. This definition defines monotonic increasing preferences. Monotonic decreasing preferences can often be defined to be compatible with this definition. For instance, an agent's preferences for pollution may be monotonic decreasing (less pollution is better). In this case, the agent's preferences for lack of pollution are monotonic increasing. Much of consumer theory relies on a weaker assumption, local nonsatiation. An example of preferences which are weakly monotonic but not strongly monotonic are those represented by a Leontief ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Randomized Algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. One has to distinguish between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithms, for example Quicksort), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem. In common practice, randomized algor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrepancy Of Permutations
Discrepancy of permutations is a sub-field of discrepancy theory, that deals with balancing intervals induced by permutations of elements. There is a set of ''n'' elements, and there are m different permutations on this set. The general research question is: can we color each element in one of two different colors (e.g. black and white), such that in each permutation, every interval contains roughly the same number of elements of each color? Formally, the ''discrepancy'' of an interval is defined as the difference between the number of white elements and the number of black elements in that interval; the objective is to color the elements such that the maximum discrepancy of an interval in each of the permutations is as small as possible. Definitions Let ''p''1, ...,''pm'' be permutations of 'n'' The ''interval set'' of a permutation is the set of all subsets of 'n'' that are adjacent to each other in the permutation. For example, if ''n''=4 and one of the permutations is (1, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
