|
Strategyproof
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. A SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes every member better off. In a strong group strategyproof mechanism, no group of people can col ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gibbard's Theorem
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold: # The process is Dictatorship mechanism, dictatorial, i.e. there is a single voter whose vote chooses the outcome. # The process limits the possible outcomes to two options only. # The process is not straightforward; the optimal ballot for a voter "requires strategic voting", i.e. it depends on their beliefs about other voters' ballots. A corollary of this theorem is the Gibbard–Satterthwaite theorem about voting rules. The key difference between the two theorems is that Gibbard–Satterthwaite applies only to ranked voting. Because of its broader scope, Gibbard's theorem makes no claim about whether voters need to reverse their ranking of candidates, only that their optimal ballots depend on the other voters' ballots. Gib ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monotonicity (mechanism Design)
In mechanism design, monotonicity is a property of a social choice function. It is a necessary condition for being able to implement such a function using a strategyproof mechanism. Its verbal description is: In other words: Notation There is a set X of possible outcomes. There are n agents which have different valuations for each outcome. The valuation of agent i is represented as a function:v_i : X \longrightarrow R_+which expresses the value it assigns to each alternative. The vector of all value-functions is denoted by v. For every agent i, the vector of all value-functions of the ''other'' agents is denoted by v_. So v \equiv (v_i,v_). A social choice function is a function that takes as input the value-vector v and returns an outcome x\in X. It is denoted by \text(v) or \text(v_i,v_). In mechanisms without money A social choice function satisfies the strong monotonicity property (SMON) if for every agent i and every v_i,v_i',v_, if:x = \text(v_i, v_)x' = \text(v' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Second-price Auction
A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. Bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins but the price paid is the second-highest bid. This type of auction is strategically similar to an English auction and gives bidders an incentive to bid their true value. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893. In 1797 Johann Wolfgang von Goethe sold a manuscript using a sealed-bid, second-price auction. Vickrey's original paper mainly considered auctions where only a single, indivisible good is being sold. The terms ''Vickrey auction'' and ''second-price sealed-bid auction'' are, in this case only, equivalent and used interchangeably. In the case of multiple identical goods, the bidders submit inverse demand curves and pay the opportunity cost. Vickrey auctions ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Majority Voting
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] |
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] |
Implementability (mechanism Design)
Implementation theory is an area of research in game theory concerned with whether a class of Mechanism design, mechanisms (or institutions) can be designed whose equilibrium outcomes implement a given set of normative goals or Welfare economics, welfare criteria.Palfrey, Thomas R. "Chapter 61 Implementation Theory." Handbook of Game Theory with Economic Applications, 2002. . There are two general types of implementation problems: the economic problem of Production (economics), producing and Resource allocation, allocating Public good (economics), public and private goods and choosing over a finite set of alternatives.Maskin, Eric and Sjöström, Tomas. "Implementation Theory." Handbook of Social Choice and Welfare, 2002. . In the case of producing and allocating public/private goods, solution concepts are focused on finding Dominant Strategy, dominant strategies. In his paper "Counterspeculation, Auctions, and Competitive Sealed Tenders", William Vickrey showed that if preferences ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Incentive Compatibility
In game theory and economics, a mechanism is called incentive-compatible (IC) if every participant can achieve their own best outcome by reporting their true preferences. For example, there is incentive compatibility if high-risk clients are better off in identifying themselves as high-risk to insurance firms, who only sell discounted insurance to high-risk clients. Likewise, they would be worse off if they pretend to be low-risk. Low-risk clients who pretend to be high-risk would also be worse off. The concept is attributed to the Russian-born American economist Leonid Hurwicz. Typology There are several different degrees of incentive-compatibility: * The stronger degree is dominant-strategy incentive-compatibility (DSIC). This means that truth-telling is a weakly-dominant strategy, i.e. you fare best or at least not worse by being truthful, regardless of what the others do. In a DSIC mechanism, strategic considerations cannot help any agent achieve better outcomes than the tru ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Participation Criterion
The participation criterion is a voting system criterion that says candidates should never lose an election as a result of receiving too many votes in support. More formally, it says that adding more voters who prefer ''Alice'' to ''Bob'' should not cause ''Alice'' to lose the election to ''Bob''. Voting systems that fail the participation criterion exhibit the no-show paradox, where a voter is effectively disenfranchised by the electoral system because turning out to vote could make the result worse for them; such voters are sometimes referred to as having negative vote weights, particularly in the context of German constitutional law, where courts have ruled such a possibility violates the principle of one man, one vote. Positional methods and score voting satisfy the participation criterion. All deterministic voting rules that satisfy pairwise majority-rule can fail in situations involving four-way cyclic ties, though such scenarios are empirically rare, and the random ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Incentive Compatibility
In game theory and economics, a mechanism is called incentive-compatible (IC) if every participant can achieve their own best outcome by reporting their true preferences. For example, there is incentive compatibility if high-risk clients are better off in identifying themselves as high-risk to insurance firms, who only sell discounted insurance to high-risk clients. Likewise, they would be worse off if they pretend to be low-risk. Low-risk clients who pretend to be high-risk would also be worse off. The concept is attributed to the Russian-born American economist Leonid Hurwicz. Typology There are several different degrees of incentive-compatibility: * The stronger degree is dominant-strategy incentive-compatibility (DSIC). This means that truth-telling is a weakly-dominant strategy, i.e. you fare best or at least not worse by being truthful, regardless of what the others do. In a DSIC mechanism, strategic considerations cannot help any agent achieve better outcomes than the tru ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lexicographic Dominance
Lexicographic dominance is a total order between random variables. It is a form of stochastic ordering. It is defined as follows. Random variable A has lexicographic dominance over random variable B (denoted A \succ_ B) if one of the following holds: * A has a higher probability than B of receiving the best outcome. * A and B have an equal probability of receiving the best outcome, but A has a higher probability of receiving the 2nd-best outcome. * A and B have an equal probability of receiving the best and 2nd-best outcomes, but A has a higher probability of receiving the 3rd-best outcome. In other words: let ''k'' be the first index for which the probability of receiving the k-th best outcome is different for A and B. Then this probability should be higher for A. Variants Upward lexicographic dominance is defined as follows. Random variable A has upward lexicographic dominance over random variable B (denoted A \succ_ B) if one of the following holds: * A has a ''lower'' probabi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mechanism Design
Mechanism design (sometimes implementation theory or institution design) is a branch of economics and game theory. It studies how to construct rules—called Game form, mechanisms or institutions—that produce good outcomes according to Social welfare function, some predefined metric, even when the designer does not know the players' true preferences or what information they have. Mechanism design thus focuses on the study of solution concepts for a class of private-information games. Mechanism design has broad applications, including traditional domains of economics such as market design, but also political science (through voting theory). It is a foundational component in the operation of the internet, being used in networked systems (such as inter-domain routing), e-commerce, and Sponsored search auction, advertisement auctions by Facebook and Google. Because it starts with the end of the game (a particular result), then works backwards to find a game that implements it, it ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Game Theory
Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed two-person zero-sum games, in which a participant's gains or losses are exactly balanced by the losses and gains of the other participant. In the 1950s, it was extended to the study of non zero-sum games, and was eventually applied to a wide range of Human behavior, behavioral relations. It is now an umbrella term for the science of rational Decision-making, decision making in humans, animals, and computers. Modern game theory began with the idea of mixed-strategy equilibria in two-person zero-sum games and its proof by John von Neumann. Von Neumann's original proof used the Brouwer fixed-point theorem on continuous mappings into compact convex sets, which became a standard method in game theory and mathematical economics. His paper was f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
