โ Scribed by P. W. Goldberg; J. Rothe
No coin nor oath required. For personal study only.
This special issue is devoted to topics within computational social choice, a new research field at the interface of social choice theory, computer science, economics, game theory, political science, and mathematics. It is an interdisciplinary field that, on the one hand, applies the notions and methods from computer science (especially those developed in artificial intelligence, algorithmics, computational complexity, and logic) to the notions and mechanisms of (classical) social choice theory, such as voting procedures, fair division mechanisms, social welfare orderings, and methods for collective decision-making. On the other hand, computational social choice integrates fundamental concepts and ideas from (classical) social choice theory into computer science. For example, fair division algorithms as well as election systems were designed for human societies originally, yet have also numerous applications in multiagent systems (within distributed artificial intelligence), in network design, for multiagent resource allocation, and other tasks.
The focus of this special issue is on logic and complexity within computational social choice. For example, while it is known from (classical) social choice theory that essentially all natural voting systems are manipulable in principle, recent research results have shown that computational complexity can be used to protect, to some extent, certain election systems against attempts to change an election's outcome, i.e., these systems can be shown to be resistant to (various types of) manipulation, procedural control, or bribery. As two examples regarding the use of logic within computational social choice, we mention the logic-based specification and verification of social procedures and the compact representation of preferences via logic-based languages.
The seven articles contained in this special issue contribute to various of the above-mentioned lines of research. The first three contributions study how to succinctly represent utility functions (i.e., cardinal preferences) over a set of alternatives with a combinatorial structure via languages based on weighted propositional formulas, explore the use of read-once marginal contribution nets for compactly representing coalitional games and their application to computing network flow games on series-parallel networks, and investigate "effort games", a game-theoretic model of cooperation in open environments. The last four contributions are concerned with election systems and certain natural solution concepts of social choice rules, and study their computational and social choice properties. Most of the articles collected here analyze the problems they study with respect to their computational complexity.
We thank all authors for submitting their fine work to this special issue, and we are grateful to the many referees for their help in the reviewing process (each submitted paper received at least two reviews), to the MLQ staff for the wonderful collaboration, and last but not least to the MLQ managing editor, Armin Hemmerling, for inviting this special issue on logic and complexity within computational social choice.
๐ SIMILAR VOLUMES
## Indestructibility and stationary reflection If ฮบ < ฮป are such that ฮบ is a strong cardinal whose strongness is indestructible under ฮบ-strategically closed forcing and ฮป is weakly compact, then we show that A = {ฮด < ฮบ | ฮด is a non-weakly compact Mahlo cardinal reflecting stationary sets} must be
In this work we introduce a class of commutative rings whose defining condition is that its lattice of ideals, augmented with the ideal product, the semi-ring of ideals, is isomorphic to an MV-algebra. This class of rings coincides with the class of commutative rings which are direct sums of local A