現代民主政治，植基於地方自治；而地方自治之推行，則自選舉始。故朝野如何善事 地方選舉，使確屬賢能之士，出主庶政，為民服務；發言議壇，為民立法，民治成敗 ，關係至巨。 台省實施地方選舉，為國史上之首創，又時當日本專制統治五十一年之後，中央政府 甫行遷台，國難嚴重之際，其成敗得失，影響深遠，實不待言。著者之決心研究此問 題者，蓋亦在此。 考現代民主政治雖已成為家喻戶曉之名，詞，然為最難採行之政制。因其施行前必備 之先決條件，屈指難數。諸如：言論、集會、結社與宗教信仰等等之自由已否存在， 司法審判之獨立能否維持；國民之基本教育是否普及；國民之公共道德已否於相當水 準；國民之守法精神已否養成；國民之生活必需是否不虞匱乏；國民之氣質是否溫和 、服從理性；與乎以正義為基礎之社會平等是否存在；政黨活動是否正常等等，不一 而足。依 國父孫中山先生之遺教，民治之施行，猶需「以全縣人口，調查清楚。全 縣土地，測量完畢。全縣警衛，辦妥善。四境縱橫之道路，修築成功。而其人民曾受 四檯之訓練，而完畢其國民之義務，誓行革命之主義者，得選舉縣官，以執行一縣之 政事，得選舉議員，以議立一縣之法律，始成完全自治之縣」。 由於上列條件之未易俱備，且其每一條件又屬重要，台省如今是否已達水準可行普選 ﹖此一問題之答案，吾人雖已於書刊所述，報章所載，與日常生活體驗中，多所發現 ，然欲深求瞭解，猶有待於從民治基礎加以探討，故研究台省實施地方選舉之歷史背 景，思想淵源、社會環境、實不可缺。 誠然，縱使已具普選之條件，未必保証選舉之成功；蓋選舉之本身，猶備多種複雜難 行之條件也。而台省舉辦地方選舉，時值人心惶惶，國脈如縷之秋，益增問題之複雜 化，有待細心探索者多。 從辦理選務言，遠徵外史，歐美民主先進國家所示範於吾人者，即為選舉之公正與合 法欲求選公正，則平等之競選，公平之監察；公開之選務；與秘密之投票，似不可缺 。考選務之辦理與選舉之監察，在歐美民主先進國家，以美國為例，全國性與地方性 選舉，習慣上俱由民主、共和兩大政黨與地方政府共同負責；故選舉之結果如何，純 憑選民之決定，甚難發生公正與否之疑慮，輿論對此，自無懷疑。台省之政黨分野， 雖有國、民、青三黨之存在，但民、青兩黨在地方上之勢力如何，尚難知曉，是否定 以擔當共同監察選舉，辦理選務之能力，時論亦有所疑；尤有甚者，國人對黨派素乏 認識，所謂「群而不黨」，「吾聞君子不黨」，與「無偏無黨」之古訓，更予人以黨 派非善之觀念，故縱令採行美制，以國、民、青三黨參與辦理選務，共同監察選舉， 是否足以使無黨無派之競選者，信任選舉之公平，亦不無問題。如何抉擇，有待斟酌 。至秘密投票之施行，因憲法本無此一規定，原則上雖無問題，但執行時之如何確保 其貫徹，觀念上與技術上俱有困難。於公平之競選，主持選政者與選務人員是否能「 秉天下為公」之觀念，對待黨內同志與黨外人士一視同仁，似亦有待考驗；因法定雖 公，而執法在人也。另一方面，欲求選舉之合法，則需舉辦選舉之有據。憲法明定省 縣自治法之制定，須依中央制定之省縣自治通則，而該一通則，迄未頒布，則台省之 舉辦地方選舉，究何所據，亦為煞費思索之問題。

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.