In Arrow’s General Possibility Theorem (GPT), social choice should be defined over allpairs of alternatives. In this paper, we generalize Arrow’s GPT to situations where choice over pairs ofalternatives may not be p...In Arrow’s General Possibility Theorem (GPT), social choice should be defined over allpairs of alternatives. In this paper, we generalize Arrow’s GPT to situations where choice over pairs ofalternatives may not be possible. This shows that Arrow’s GPT and related impossibility results canbe established without binariness of social choice.展开更多
This paper firstly analyzed and researched the individual strategic behavior in social choice in the view of games. Then, a player’s voting strategic solution was probled into. Some solving methods were given and som...This paper firstly analyzed and researched the individual strategic behavior in social choice in the view of games. Then, a player’s voting strategic solution was probled into. Some solving methods were given and some relevant conclusions were obtained.展开更多
We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice ...We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.展开更多
Rationality condition is imposed in Arrow's General Possibility Theorem in order for social choice to be independent of the path of choice. In this Paper, emphasis is laid on the analysis of the relevance of path ...Rationality condition is imposed in Arrow's General Possibility Theorem in order for social choice to be independent of the path of choice. In this Paper, emphasis is laid on the analysis of the relevance of path independence and rationality condition. Two kinds of Path independence, i.e., Plott's path independence and Bandyopadhyay's sequential path independence, are shown, and their meanings with respect to the problem are investigated.展开更多
We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve d...We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve desirable properties based on the strategic agents'locations.The agents might have incentives to misreport their private locations,in order to minimize the costs(i.e.,the distance from the closest facility).We study the setting with limited locations,that is,the facilities can only be built on a given finite set of candidate locations,rather than the whole space.For locating a single facility and two facilities on a real line,we propose strategyproof mechanisms with tight approximation ratios,under the objectives of minimizing the total cost and the maximum cost.Further,we consider the problem of locating an obnoxious facility from which the agents want to stay as far away as possible,and derive tight bounds on the approximation ratio of strategyproof mechanisms.展开更多
文摘In Arrow’s General Possibility Theorem (GPT), social choice should be defined over allpairs of alternatives. In this paper, we generalize Arrow’s GPT to situations where choice over pairs ofalternatives may not be possible. This shows that Arrow’s GPT and related impossibility results canbe established without binariness of social choice.
文摘This paper firstly analyzed and researched the individual strategic behavior in social choice in the view of games. Then, a player’s voting strategic solution was probled into. Some solving methods were given and some relevant conclusions were obtained.
基金supported by a GermanNorwegian PPP grantsupported by the Indo-German Max Planck Center for Computer Science (IMPECS)
文摘We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.
文摘Rationality condition is imposed in Arrow's General Possibility Theorem in order for social choice to be independent of the path of choice. In this Paper, emphasis is laid on the analysis of the relevance of path independence and rationality condition. Two kinds of Path independence, i.e., Plott's path independence and Bandyopadhyay's sequential path independence, are shown, and their meanings with respect to the problem are investigated.
基金the National Natural Science Foundation of China(No.12101069)Innovation Foundation of BUPT for Youth(No.500421358)Ying-Chao Zhao was partially supported by the Research Grants Council of the HKSAR,China(No.UGC/FDS11/E03/21).
文摘We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve desirable properties based on the strategic agents'locations.The agents might have incentives to misreport their private locations,in order to minimize the costs(i.e.,the distance from the closest facility).We study the setting with limited locations,that is,the facilities can only be built on a given finite set of candidate locations,rather than the whole space.For locating a single facility and two facilities on a real line,we propose strategyproof mechanisms with tight approximation ratios,under the objectives of minimizing the total cost and the maximum cost.Further,we consider the problem of locating an obnoxious facility from which the agents want to stay as far away as possible,and derive tight bounds on the approximation ratio of strategyproof mechanisms.
