研究领域：微观经济学或数理经济
占优战略完全实施的社会选择规则
姚海祥1 易建新2
(1.广东外语外贸大学信息科学技术学院 广州 510420)
(2. 华南师范大学数学科学学院 广州510631)
摘要
Gibbard-Satterthwaite定理（Osborne and Rubinstein, 1994）是实施理论中最著名的定理之一，该定理表明了如果一个社会选择规则可被占优战略完全实施的，则它一定是独裁的，然而，什么样的社会选择规则才能被占优战略完全实施呢？进一步是社会选择规则可被占优战略完全实施的等价条件是什么呢？这是个有趣的问题！本文的目的就是回答这些问题！本文首先给出了社会选择规则完全独裁的概念，证明了在一些条件下社会选择规则可被占优战略完全实施等价于社会选择规则是完全独裁的，并且给出了社会选择规则可被占优战略完全实施的另外几个等价条件！
关键词：社会选择规则；占优战略完全实施；半严格正向响应；单调的；完全独裁
Abstract.
Gibbard-Satterthwaite theorem is one of most important result in implementation theory, which tell us that the social choice correspondences fully implemented in dominant strategies must be dictatorial. But under what conditions the social choice correspondences can be fully implemented in dominant strategies? Or what are the sufficient and necessary conditions of full implementation in dominant strategies for social choice correspondences? In this paper, we provide several sufficient and necessary conditions of full implementation in dominant strategies for social choice correspondences.
Keywords: Social choice correspondences, fully implemented in dominant strategies, semi-strictly monotonic; monotonic; Complete dictatorship
The full implementation in dominant strategies of
social choice correspondences
Haixiang Yao1，Jianxin Yi2
Faculty of Information Science and Technology, Guangdong University of Foreign Studies, Guang Zhou 510420, China
of Mathematical Sciences, South China Normal University, Guangzhou 510631,China
Abstract.
Gibbard-Satterthwaite theorem is one of most important result in implementation theory, which tell us that the social choice correspondences fully implemented in dominant strategies must be dictatorial. But under what conditions the social choice correspondences can be fully implemented in dominant strategies? Or what are the sufficient and necessary conditions of full implementation in dominant strategies for social choice correspondences? In this paper, we provide several sufficient and necessary conditions of full implementation in dominant strategies for social choice correspondences.
Keywords: Social choice correspondences, fully implemented in dominant strategies, semi-strictly monotonic; monotonic; Complete dictatorship
Introduction
In implementation theory, One of most important result is following Gibbard-Satterthwaite theorem which tell us that the social choice correspondences fully implemented in dominant strategies must be dictatorial. It is interesting to further explore the complete characterization of full implementation in dominant strategies for social choice correspondences. In this note, we offer several sufficient and necessary conditions of full implementation in dominant strategies.
Definitions
Let denotes the set of individuals and the set of alternatives。 be the set of all linear preferences (complete, transitive and antisymmetric binary relation) on . Let be the set of preferences (complete, transitive binary relation) on and . ={| EMBED EMBED }. =. For any preference , we denote by the binary relation that holds but does not. Let denotes the restriction of to the set . =∣, }. A social choice correspondences (SCC) is a mapping ： EMBED EMBED .
A SCC satisfies the weak Pareto property if for any profile in and any pair and in , if for all , then EMBED 。
A SCC is independent if for any pair of profiles and in and any pair , if , and for all , then .
A SCC is dictatorial if there exists a fixed individuals such that for all preferences profiles in and any ，we have for all , that is . EMBED EMBED . is complete dictatorial if there exists a fixed individuals such that for all preferences profiles in ，we have =.
A SCC is monotonic if for any two profiles and in and , { EMBED ∣,}{ EMBED ∣} for all implies . is semi-strictly monotonic if for any two preferences profiles and in and , { EMBED ∣, }{ EMBED ∣} for any implies .
A game form or mechanism (associated with and ) is a pair (, ), where is individuals ’s strategy set and : is a function. For given game (,,) where , a pure strategy is dominant strategy for individual if for all . A strategies profile is a dominant strategy equilibrium to game (,,) if is dominant strategy for every individual . Denote the set of all dominant strategies equilibrium to the game (,,)}. A game form (, ) is said to fully implement a SCC in dominant strategies if for all EMBED , we have =. is fully implemented in dominant strategies if there exists a game form (, ) which fully implement in dominant strategies.
3. Main theorems.
Gibbard-Satterthwaite Theorem (Osborne and Rubinstein, 1994). Suppose that contains at least three alternatives and for any ，there is a preferences profile in ，such that =. Then SCC is dictatorial if is fully implemented in dominant strategies.
Proposition: Suppose that SCC is fully implemented in dominant strategies, then following are equivalent.
(A) For any ，there is a preferences profile in , such that =.
(B) For any ，there is a preferences profile in , such that EMBED .
Proof : we only need to verify that (B) implies (A). For any , let us consider profiles in with the property that = for any . Then is dictatorial implies =. To see this, let EMBED and . Let game form (, ) fully implement in dominant strategies. Note that there is a EMBED , such that EMBED .
Suppose is the dominant strategies equilibrium to the game (,,)} and = and is the dominant strategies equilibrium to the game (,,)} and =. Then EMBED EMBED implies =. Similar, EMBED EMBED implies =. Continuing the process, we have =. Contradiction.
Corollary : Suppose that contains at least three alternatives and for any ，there is a preferences profile ，such that EMBED . Then SCC is dictatorial if is fully implemented in dominant strategies.
Lemma 1. Suppose Social choice function is monotonic, and , then satisfies the weak Pareto property.
Proof : follows from P. Dasgupta, P. Hammond and E. Maskin (1979).
Lemma 2. Suppose that contains at least three alternatives, and Social choice function is monotonic and satisfies the weak Pareto property, then is dictatorial.
Proof : follows from P. Dasgupta, P. Hammond and E. Maskin (1979).
Theorem: Suppose that contains at least three alternatives and for any ，there is a preferences profile ，such that EMBED . The following are equivalent.
(1) is fully implemented in dominant strategies;
(2) is complete dictatorial;
(3) is monotonic and dictatorial;
(4) is monotonic and independent and satisfies the weak Pareto property;
(5) is monotonic and semi-strictly monotonic.
Proof : (1)(2). By Corollary, is dictatorial. Let is the dictator. So we need only prove EMBED EMBED . Let game form (, ) fully implement in dominant strategies. For any preferences profile and EMBED . Suppose is such that for all and =, By is dictatorial, . Since game form (, ) fully implement in dominant strategies, so there is a dominant strategies equilibrium of the game (,,) such that =. For any EMBED , we have EMBED EMBED . If , by the definition of , , then =implies that EMBED EMBED . If , note that EMBED , so EMBED EMBED . Hence is also the dominant strategies equilibrium of the game (,,. Therefore = EMBED .
(2)(1): Let is the dictator. Choose game form (, ), where and for any and : EMBED is such that . We can prove that the game form (, ) fully implements SCC in dominant strategies. To see this, suppose is the dominant strategies equilibrium to the game (,,)}, then for implies . And suppose , then EMBED for any implies is the dominant strategies equilibrium to the game (,,)}, hence . Therefore the game form (, ) fully implements SCC in dominant strategies.
(3)(2): Let is the dictator. For any preferences profile and EMBED . Choose a where for all . Then is the dictator implies that =. Note that { EMBED ∣} EMBED ={ EMBED ∣}, thus EMBED . Therefore is completely dictatorial.
(4)(3) follows from Denicolo (1985).
(5)(3) For any EMBED , is one-point set. To see this, suppose two different alternatives and are in , now choose EMBED , such that = and , for all and . By semi-strict monotonousness, . Contradiction. Let . We can prove that . To see this, EMBED ，there exists a preferences profile ，such that EMBED , choose EMBED , with the property that for all . By semi-strict monotonousness, . By Lemma 1 is monotonic implies satisfies the weak Pareto property, then by lemma 2 is dictatorial. Let is the dictator of . Now, we show is the dictator of . For any EMBED and , if there is a, such that . Choose EMBED , such that for all and for all . By semi-strict monotonousness, . Meanwhile, because is dictatorial, we have , Contradiction. Therefore is dictatorial.
(2)(4): Let is the dictator. First, for any two preference profiles , and , if { EMBED ∣}{ EMBED ∣}, then by complete dictatorship , thus =. Therefore is monotonic. Next, for any two preference profiles , and any pair , if , and for all , then but , implies. By , we have . Hence =. Therefore is independent. It is easy to verify that satisfies the weak Pareto property.
(2)(5) Suppose is the dictator. For any two preferences profiles , and , for any , if { EMBED ∣, }{ EMBED ∣}, then ={ EMBED ∣, }{ EMBED ∣} implies for any ,. Therefore .
References
[1] Denicolo V. Independent social choice correspondences are dictatorial[J]. Economics Letters, 1985, 19:9-12.
[2] Gibbard A. Manipulation of voting schemes: A general result[J]. Econometrica , 1973, 41:587-601.
[3] Maskin E. The theory of implementation in Nash equilibrium;a survey. In: Hurwicz L, Schmeidler D, Sonnenschein H(eds) Social goals and social organization: Essays in honor of Elisha A. Pazner[M]. Combridge: Combridge University Press, 1985.
[3] Osborne M J, Rubinstein A. A course in game theory[M]. Massachusetts: MIT Press, 1994.
[4] Satterthwaite M. Strategy-proofness and Arrow’s conditions:Existence and correspondence theorems for voting procedures and social welfare functions[J]. J Econ Theory, 1975, 10: 187-217.
[5] P. Dasgupta, P. Hammond and E. Maskin. The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility[J]. Review of Economic Studies, 1979, 46: 185-216.
联系作者：姚海祥
单位：广东外语外贸大学信息科学技术学院
通信地址：广州市广东外语外贸大学信息科学技术学院
邮政编码：510420
电话：013560373627，02039329261
电子邮件：yhaixiang@
yaohaixiang@
PAGE
PAGE 8
