On asymptotic strategy-proofness of the plurality and the run-off rules

In this paper we prove that the plurality rule and the run-off procedure are asymptotically strategy-proof for any number of alternatives and that the proportion of profiles, at which a successful attempt to manipulate might take place, is in both cases bounded from above by , where n is the number of participating agents and K does not depend on n. We also prove that for the plurality rule the proportion of manipulable profiles is asymptotically bounded from below by , where k also does not depend on n. Received: 10 February 2000/Accepted: 19 October 2000     

On Asymptotic Strategy-Proofness of Classical Social Choice Rules

We show that, when the number of participating agents n tends to infinity, all classical social choice rules are asymptotically strategy-proof with the proportion of manipulable profiles being of order O (1/n).     

On the Average Minimum Size of a Manipulating Coalition

We study the asymptotic average minimum manipulating coalition size as a characteristic of quality of a voting rule and show its serious drawback. We suggest using the asymptotic average threshold coalition size instead. We prove that, in large electorates, the asymptotic average threshold coalition size is maximised among all scoring rules by the Borda rule when the number m of alternatives is 3 or 4, and by -approval voting when m ≥ 5.     

Rationalizations of Condorcet-consistent rules via distances of hamming type

In voting, the main idea of the distance rationalizability framework is to view the voters’ preferences as an imperfect approximation to some kind of consensus. This approach, which is deeply rooted in the social choice literature, allows one to define (“rationalize”) voting rules via a consensus class of elections and a distance: a candidate is said to be an election winner if she is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be distance-rationalized. In this article, we provide new results on distance rationalizability of several Condorcet-consistent voting rules. In particular, we distance-rationalize the Young rule and Maximin using distances similar to the Hamming distance. It has been claimed that the Young rule can be rationalized by the Condorcet consensus class and the Hamming distance; we show that this claim is incorrect and, in fact, this consensus class and distance yield a new rule, which has not been studied before. We prove that, similarly to the Young rule, this new rule has a computationally hard winner determination problem.     

Optimal superimposed codes and designs for Renyi''s search model

Renyi (Bull. Amer. Math. Soc. 71 (6) (1965) 809) suggested a combinatorial group testing model, in which the size of a testing group was restricted. In this model, Renyi considered the search of one defective element (significant factor) from the finite set of elements (factors). The corresponding optimal search designs were obtained by Katona (J. Combin. Theory 1 (2) (1966) 174). In the present work, we study Renyi's search model of several significant factors. This problem is closely related to the concept of binary superimposed codes, which were introduced by Kautz and Singleton (IEEE Trans. Inform Theory 10 (4) (1964) 363) and were investigated by D'yachkov and Rykov (Problems Control Inform. Theory 12 (4) (1983) 229), Erdos et al. (Israel J. Math. 51 (1–2) (1985) 75), Ruszinko (J. Combin. Theory Ser. A 66 (1994) 302) and Furedi (J. Combin. Theory Ser. A 73 (1996) 172). Our goal is to prove a lower bound on the search length and to construct the optimal superimposed codes and search designs. The preliminary results have been published by D'yachkov and Rykov (Conference on Computer Science & Engineering Technology, Yerevan, Armenia, September 1997, p. 242).     

Self-selective social choice functions

It is not uncommon that a society facing a choice problem has also to choose the choice rule itself. In such situations, when information about voters’ preferences is complete, the voters’ preferences on alternatives induce voters’ preferences over the set of available voting rules. Such a setting immediately gives rise to a natural question concerning consistency between these two levels of choice. If a choice rule employed to resolve the society’s original choice problem does not choose itself, when it is also used for choosing the choice rule, then this phenomenon can be regarded as inconsistency of this choice rule as it rejects itself according to its own rationale. Koray (Econometrica 68: 981–995, 2000) proved that the only neutral, unanimous universally self-selective social choice functions are the dictatorial ones. Here we introduce to our society a constitution, which rules out inefficient social choice rules. When inefficient social choice rules become unavailable for comparison, the property of self-selectivity becomes more interesting and we show that some non-trivial self-selective social choice functions do exist. Under certain assumptions on the constitution we describe all of them.     

Is it ever safe to vote strategically?

There are many situations in which mis-coordinated strategic voting can leave strategic voters worse off than they would have been had they not tried to strategise. We analyse the simplest of such scenarios, in which a set of strategic voters all have the same sincere preferences and all contemplate casting the same strategic vote, while all other voters are not strategic. Most mis-coordinations in this framework can be classified as instances of either strategic overshooting (too many voted strategically) or strategic undershooting (too few). If mis-coordination can result in strategic voters ending up worse off than they would have been had they all just voted sincerely, we call the strategic vote unsafe. We show that under every onto and non-dictatorial social choice rule there exist circumstances where a voter has an incentive to cast a safe strategic vote. We extend the Gibbard–Satterthwaite Theorem by proving that every onto and non-dictatorial social choice rule can be individually manipulated by a voter casting a safe strategic vote.     

Exordium for DNA Codes

We describe how deletion-correcting codes may be enhanced to yield codes with double-strand DNA-sequence codewords. This enhancement involves abstractions of the pertinent aspects of DNA; it nevertheless ensures specificity of binding for all pairs of single strands derived from its codewords—the key desideratum of DNA codes– i.e. with binding feasible only between reverse complementary strands. We defer discussing the combinatorial-optimization superincumbencies of code construction. Generalization of deletion similarity to an optimal sequence-alignment score could readily effect advantageous improvements (Kaderali, Master's Thesis, Informatics, U. Köln, 2001) but would render the combinatorics opaque. We mention motivating applications of DNA codes.     

Approximability of Dodgson’s rule

It is known that Dodgson’s rule is computationally very demanding. Tideman (Soc Choice Welf 4:185–206, 1987) suggested an approximation to it but did not investigate how often his approximation selects the Dodgson winner. We show that under the Impartial Culture assumption the probability that the Tideman winner is the Dodgson winner converges to 1 as the number of voters increase. However we show that this convergence is not exponentially fast. We suggest another approximation—we call it Dodgson Quick—for which this convergence is exponentially fast. Also we show that the Simpson and Dodgson rules are asymptotically different.