Symmetric reduced-form voting

Lang, Xu; Mishra, Debasis Article Symmetric reduced-form voting Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Lang, Xu; Mishra, Debasis (2024) : Symmetric reduced-form voting, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 19, Iss. 2, pp. 605-634, https://doi.org/10.3982/TE5400 This Version is available at: https://hdl.handle.net/10419/320248 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 19 (2024), 605–634 1555-7561/20240605 Symmetric reduced-form voting XuLang Center for Economic Research, Shandong University Debasis Mishra Economics and Planning Unit, Indian Statistical Institute, Delhi We study a model of voting with two alternatives in a symmetric environment. We characterize the interim allocation probabilities that can be implemented by a symmetric voting rule. We show that every such interim allocation probability can be implemented as a convex combination of two families of deterministic voting rules: qualified majority and qualified anti-majority. We also provide analogous results by requiring implementation by a symmetric monotone (strategy-proof) voting rule and by a symmetric unanimous voting rule. We apply our results to show that an ex ante Rawlsian rule is a convex combination of a pair of qualified majority rules. Keywords. Reduced-form voting, unanimous voting, ordinal Bayesian incentive compatibility, monotone reduced form. JEL classification.D82. 1. Introduction In many mechanism design problems, the incentive constraints and the objective function of the designer can be written in the interim allocation space. While a mechanism describes the ex post allocation of the agents, the solution to an incentive constrained optimization may describe only interim allocations. This raises a natural question, “Which interim allocations can be generated by a (ex post) mechanism?” If there is a characterization of interim allocations that can be generated by a mechanism, then it can be used as a constraint in any incentive constrained optimization. This approach to mechanism design is known as the reduced-form approach. It was pioneered in the single object auction literature by Matthews (1984)andMaskin and Riley (1984), leading to the seminal characterization in Border’s theorem (Border (1991)). We analyze reduced-form voting mechanisms in a simple model of voting with two alternatives: aand b. In our model, each agent has two possible types: (i) the a-type agent prefers afollowed by band (ii) the b-type agent prefers bfollowed by a.Weconsider a symmetric voting environment: the probability of two type profiles with the same Xu Lang: [email protected] Debasis Mishra: [email protected] We are grateful to Arunava Sen, Zaifu Yang, and two anonymous referees for their comments. Xu Lang thanks the National Natural Science Foundation of China (NSFC72033004). Debasis Mishra acknowledges financial support from the Science and Engineering Research Board (SERB Grant No. SERB/CRG/2021/003099) of India. ©2024 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE5400 606 Lang and Mishra Theoretical Economics 19 (2024) number of atypes is identical. Hence, we focus on symmetric voting rules, which choose a probability distribution over aand bfor every number of atypes. The interim allocation probability of choosing a(and b)fora-type and b-type agents can be computed from the symmetric voting rule. The reduced-form voting question is, “Given the interim allocation probabilities of choosing aand bfor a-type and b-type agents, is there a symmetric voting rule that can generate these interim allocation probabilities?” We completely characterize these interim allocation probabilities, which we call reduced-form implementable symmetric voting rules. The reduced-form implementable symmetric voting rules are characterized by a family of 2(n+1)linear inequalities, where nis the number of agents. The extreme points of these symmetric voting rules are (i) a family of (n+1)qualified majority voting rules and (ii) a family of (n+1)qualified antimajority voting rules. A qualified majority (anti-majority) voting rule is characterized by aquotaKand chooses alternative a(respectively, b) whenever at least Kagents vote for a. As a corollary, we show that every symmetric voting rule is reduced-form equivalent (i.e., generating the same interim allocation probabilities) to a convex combination of qualified majority and qualified anti-majority voting rules. Both these families contain only deterministic voting rules. We extend our characterization to monotone voting rules, i.e., voting rules that select awith higher probability as the number of a-types increases. Monotone voting rules are strategy-proof (dominant strategy incentive compatible). The reduced-form implementable symmetric monotone voting rules are characterized by a family of (n+2) linear inequalities. The extreme points of these rules are the family of (n+1)qualified majority rules and a constant rule that selects alternative bat all type profiles. We use this result to show that an ex ante Rawlsian rule (that maximizes the minimum of expected utility of a-type agents and b-type agents) is a convex combination of a pair of qualified majority rules. We also investigate the reduced-form question under a weaker notion of incentive constraints, i.e., ordinal Bayesian incentive compatibility (OBIC) (d’Aspremont and Peleg (1988), Majumdar and Sen (2004), Mishra (2016)). We show its connection to reduced-form implementation by monotone voting rules. We extend our characterizations for unanimous symmetric voting rules: a voting rule is unanimous if it chooses a(b) whenever all the agents have type a(respectively, b). Using this, we characterize the symmetric priors for which OBIC is implied by symmetry and unanimity. For independent priors, this is the case when the probability of an a type is sufficiently small or sufficiently high. If we allow for correlation (still maintaining symmetry), the set of priors where symmetry and unanimity imply OBIC contains priors where extreme type profiles with low and high numbers of atypes are chosen with high probability. We believe our results will be useful in designing optimal mechanisms in various models of voting over a pair of alternatives. Indeed, Border’s theorem is extensively used in auction theory and mechanism design for designing optimal auctions with budget constrained bidders (Pai and Vohra (2014)), for designing optimal verification mechanisms (Ben-Porath, Dekel, and Lipman (2014), Mylovanov and Zapechelnyuk (2017), Li (2020,2021)), for designing symmetric auctions (Deb and Pai (2017)), and so on. The advantage of using a reduced form approach in mechanism design problems is that it 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 607 reduces the dimensionality of such problems. For instance, in the problem we study, the reduced form is two-dimensional, but the (ex post) voting rules are n-dimensional, where nis the number of agents. Our easy derivation of the ex ante Rawlsian rule illustrates this advantage. We give a detailed review of the literature in Section 7, but relate our results to Border’s theorem here. Consider Border’s single object allocation problem, but where each agent has two types (possible values for the object), {0, 1}. This is analogous to our problem where there are two types: aand b. However, the voting problem in the current paper is a public good problem: the probability of choosing aand bisthesameacross all the agents. The single object allocation problem is a private good problem where the probability of choosing aand bmay differ across agents. This makes the feasibility constraints of allocation rules different in both problems. Goeree and Kushnir (2023) use a geometric approach (using support functions of convex sets) to study implementation in social choice problems. Their abstract formulation also captures our problem and their results can be used to describe the support functions of our reduced-form voting rules. But this neither describes the extreme points nor the necessary and sufficient conditions that characterize the reduced-form voting rules.1Indeed, it is not clear that an analogue of Border’s theorem can exist in the voting problem. In an important paper, Gopalan, Nisan, and Roughgarden (2018)show that in a simple public good model with two alternatives, no computationally tractable characterization of reduced-form allocation rules is possible. Though this negative result applies to our model, they allow reduced-form implementation via asymmetric mechanisms. By looking only at symmetric mechanisms, we overcome this impossibility: our characterization admits a computationally tractable description of reducedform probabilities by a system of (linear in number of voters) linear inequalities. The rest of the paper is organized as follows. Section 2introduces the model. Section 3provides the main result of the paper: a characterization of the reduced-form implementable voting rules. Section 4extends the main result by requiring monotone implementation and provides an application to finding a Rawlsian voting rule. The main characterization is extended with unanimity in Section 5and extended for large economies in Section 6.Section7gives a detailed literature review. The missing proofs are provided in the Appendix. 2. The model Let N={1, ,n}be a finite set of agents (voters), where n≥2. Let A={a,b}be the set of two social alternatives (for instance, a status quo and a new alternative). Each agent has a strict ranking of A. Hence, the preference of an agent can be expressed by her top ranked alternative. We call this the type of the agent. The type of agent iis denoted as ti∈{a,b}, which means that tiis the top ranked alternative of agent i.Hence,thesetof all types (type space) is Aand the set of all type profiles is An. A type profile in Anis denoted by t≡(t1,,tn). 1They further assume independent priors, which we do not assume. They use their support function characterization to rederive Border’s result. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 608 Lang and Mishra Theoretical Economics 19 (2024) Exchangeable prior Let Gbe a probability distribution over type profiles. We assume G to be exchangeable, i.e., for every type profile tand every permutation σ,G(t)=G(tσ), where tσis the permuted type profile. In this sense, the probability of a type profile is only a function of the number of agents having type a.So,foreveryk∈{0, ,n}, for any set of kagents, the probability that exactly these agents have type a(and other agents have type b)isgivenbyλ(k). By exchangeability, the probability that a type profile has exactly kagents of type ais C(n,k)λ(k),whereC(n,k)denotes the number of k combinations from a set of nelements. We denote the marginal probability of any agent having type aas πand having type bas (1−π). Voting rule Avoting rule is a map q:An→[0, 1],whereq(t)denotes the probability with which alternative ais chosen (and, hence, 1 −q(t)is the probability with which alternative bis chosen) at type profile t. We consider only symmetric or anonymous voting rules, i.e., for any permutation σ,wewillrequireq(t)=q(tσ)for all t∈An,where tσis type profile obtained by permuting tusing the permutation σ. With a slight abuse of notation, we will write qas a map q:{0, 1, ,n}→[0, 1], i.e., q(k)∈[0, 1]denotes the probability with which alternative ais chosen at any type profile with kvotes for a.2We discuss only symmetric voting rules, and whenever we refer to a voting rule from now on, we mean a symmetric voting rule. Given a voting rule q, we can compute the interim probability of each alternative being chosen. If an agent has type a, the probability that alternative ais chosen by voting rule qis denoted by Q(a). To relate Qand q, denote the probability that there are k agents of type aas B(k):=λ(k)C(n,k)∀k∈{0, ,n}. Note that n  k=0 B(k)=1and n  k=0 kB(k)=nπ. The second equality follows because both nπ and kkB(k)denote the expected number of agents who have type a. Using this, Qcan be computed from qas nπQ(a)= n  k=0 kq(k)B(k), 2We restrict ourselves to ordinal voting rules. Any cardinal voting rule in a two alternative model must be ordinal if it is incentive compatible (Majumdar and Sen (2004)). Since reduced forms are usually used along with incentive constraints, restricting attention to ordinal voting rules is without loss of generality in this sense. Even without incentive constraints, Schmitz and Tröger (2012) and Azrieli and Kim (2014)show that restricting attention to ordinal voting rules is without loss of generality if the planner is optimizing over interim utilities of agents. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 609 where both the left-hand side and the right-hand side compute the expected number of atypes who get a.Hence, Q(a)=1 nπ n  k=0 kq(k)B(k). Similarly, if an agent has type b, the probability that alternative ais chosen by voting rule qis Q(b)=1 n(1−π) n  k=0 (n−k)q(k)B(k). Of course, 1 −Q(a)and 1 −Q(b)denote the interim probabilities with which alternative bis chosen for types aand b, respectively. 3. Reduced-form implementation The interim allocation probabilities are two-dimensional. Hence, they are easy to work with. Some interim allocation probabilities are clearly not possible: for instance, Q(a)= 1andQ(b)=0 is impossible for n≥2 because any voting rule for which Q(a)=1must choose aat some profiles where other agents have type b. By symmetry, Q(b)=0. Then the reduced-form question is, “What interim allocation probabilities are possible?” Definition 1. Interim allocation probabilities Q≡(Q(a),Q(b)) ∈[0, 1]2are reducedform implementable if there exists a voting rule qsuch that 1 nπ n  k=0 kq(k)B(k)=Q(a) 1 n(1−π) n  k=0 (n−k)q(k)B(k)=Q(b) 0≤q(k)≤1∀k∈{0, ,n}. To see what kind of conditions are necessary for reduced-form implementation, consider the following setting. Suppose there is a cost j∈{0, 1, ,n}of choosing alternative abut alternative bcosts zero. For any a-type agent, suppose the value of alternative ais 1 and that of alternative bis 0. The expected value of a-types minus the cost of choosing an alternative from a voting rule qis n  k=0 (k−j)q(k)B(k)=1 n(n−j) n  k=0 kq(k)B(k)−j n  k=0 (n−k)q(k)B(k) =(n−j)πQ(a)−j(1−π)Q(b).(1) The left-hand side of (1) is maximized by setting q(k)=0ifk<jand q(k)=1if k≥j. Hence, an upper bound for the left-hand side of (1)isn k=j(k−j)B(k). Similarly, 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 610 Lang and Mishra Theoretical Economics 19 (2024) the left-hand side of (1) is minimized by setting q(k)=1ifk<jand q(k)=0ifk≥j. Hence, a lower bound for the left-hand side of (1)isj k=0(k−j)B(k).Thus,forany j∈{0, 1, ,n}, n  k=j (k−j)B(k)≥(n−j)πQ(a)−j(1−π)Q(b)≥ j  k=0 (k−j)B(k).(2) So the inequalities (2) are necessary for reduced-form implementation. Our main result says they are sufficient. Theorem 1. Interim allocation probabilities Qare reduced-form implementable if and only if j(1−π)Q(b)−(n−j)πQ(a)+ n  k=j (k−j)B(k)≥0∀j∈{0, ,n}(3) (n−j)πQ(a)−j(1−π)Q(b)+ j  k=0 (j−k)B(k)≥0∀j∈{0, ,n}.(4) The sufficiency part of the proof of Theorem 1and other results are provided in Appendix. It is proved by first describing the extreme points of all reduced-form implementable voting rules (Theorem 2) and then showing that the extreme points of the system (3)and(4) correspond to exactly the same voting rules. The reduced-form implementable voting rules are described by 2(n+1)inequalities, out of which four correspond to nonnegativity of Q(a)and Q(b), and upper bounding of Q(a)and Q(b)by 1. The rest of the 2(n−1)inequalities restrict the space of interim allocation probabilities in the unit square. To see this, consider the uniform prior (independent prior) with π=1 2and n=3. In this case, (Q(a),Q(b)) is reduced-form implementable if and only if 2Q(a)−Q(b)≤5 4,Q(a)−2Q(b)≤1 4,Q(b)−2Q(a)≤1 4, 2Q(b)−Q(a)≤5 4,Q(a),Q(b)∈[0, 1]. The polytope enclosed by these inequalities is shown in Figure 1. There are eight extreme points of this polytope, two of which correspond to the constant allocation rules ((0, 0)correspond to balways chosen and (1, 1)correspond to aalways chosen). The rest of them belong to a family of voting rules that we call qualified majority and qualified anti-majority. We establish this result next. This allows us to show that any reducedform implementable voting rule is “equivalent” to a convex combination of voting rules from this set. Definition 2. Two voting rules qand ˆ qare reduced-form equivalent if they generate the same interim allocation probabilities: Q(a)= Q(a)and Q(b)= Q(b). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 611 Figure 1. Polytope of reduced-form implementable voting rules. We now introduce two classes of voting rules that are useful to describe the extreme points of reduced-form implementable voting rules. Definition 3. A voting rule q+is a qualified majority if there exists j∈{0, ,n}such that for all k∈{0, ,n}, q+(k)=1ifk≥j 0otherwise. We call such a voting rule a qualified majority with quota j. A voting rule q−is qualified anti-majority if there exists j∈{0, ,n}such that for all k∈{0, ,n}, q−(k)=1ifk<j 0otherwise. We call such a voting rule a qualified anti-majority with quota j. The definition of qualified majority is similar to Azrieli and Kim (2014). The only difference is that if the quota is j, they allow q+(j)to take any value in [0, 1],butwe break the tie deterministically. If qjis a qualified majority with quota j, then its reduced-form probabilities are Qj(a)=1 nπ n  k=0 kqj(k)B(k)=1 nπ n  k=j kB(k) Qj(b)=1 n(1−π) n  k=0 (n−k)qj(k)B(k)=1 n(1−π) n  k=j (n−k)B(k). Notice that when j=0, we have Q0(a)=Q0(b)=1. This corresponds to the constant voting rule where ais chosen at every type profile. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 612 Lang and Mishra Theoretical Economics 19 (2024) If ¯ qjis a qualified anti-majority with quota j, then its reduced-form probabilities are Qj(a)=1 nπ n  k=0 k¯ qj(k)B(k)=1 nπ j−1  k=0 kB(k) Qj(b)=1 n(1−π) n  k=0 (n−k)¯ qj(k)B(k)=1 n(1−π) j−1  k=0 (n−k)B(k). Denote the set of all qualified majority voting rules by Q+and denote the set of all qualified anti-majority voting rules by Q−. Notice that when j=0, we have Q0(a)= Q0(b)=0. This corresponds to the constant voting rule where bis chosen at every type profile. Hence, Q+∪Q−contains the two constant voting rules. Theorem 2. Every symmetric voting rule is reduced-form equivalent to a convex combination of voting rules in Q+∪Q−. We compare our results to some of the results in Azrieli and Kim (2014). They consider a cardinal voting model with two alternatives, where the type of an agent (a one-dimensional number with finite support) gives cardinal utilities of two alternatives. They consider cardinal voting rules and Bayesian incentive compatibility (BIC). They have two main results with symmetric cardinal voting rules: (a) a utilitarian maximizer in the class of symmetric BIC rules is a qualified majority; (b) an interim efficient and symmetric BIC rule is a qualified majority.3 While related, their results and our results are not comparable. First, we consider only ordinal voting rules, while they allow for cardinal rules. Second, the types of agents in their model are independent, while we allow for correlated types; exchangeable distributions allow for correlation. Third, Theorem 2says that the extreme points of the set of reduced-form implementable voting rules consist of qualified majority and qualified anti-majority rules. We do not require incentive compatibility or any additional axiom (like interim efficiency) for this result. In the next section, we impose monotonicity (equivalent to dominant strategy incentive compatibility) of voting rules, and show that the the extreme points of the set of monotone reduced-form implementable voting rules consist of qualified majority rules and a constant rule. As we discuss in Section 4.1, our results are useful in settings where the objective function of the planner is not linear. Finally, we explore the consequences of imposing unanimity on the reduced-form implementation in Section 5. Unanimity is a much weaker axiom than interim efficiency used in Azrieli and Kim (2014). Theorem 5describes the extreme points of reduced-form implementable rules satisfying unanimity and this contains rules that are not qualified majority. 3They have analogues of these results without symmetry too. A weighted majority rule is interim efficient and BIC. Similarly, a weighted majority rule is a utilitarian maximizer in the class of BIC rules. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 619 Proposition 2. Every unanimous and symmetric voting rule is OBIC if and only if λ(j)≤minλ(1)+λ(n) C(n−1, j−1),λ(0)+λ(n−1) C(n−1, j)∀j∈{1, ,n−1}. (12) Further, if the prior is independent, every unanimous and symmetric voting rule is OBIC if and only if C(n−1, j−1)≤ π 1−πn−j +π 1−π1−j∀j∈{1, ,n−1}. (13) Using Corollary 1, we can argue that when (13) holds and the prior is independent, every unanimous voting rule is reduced-form equivalent to a strategy-proof voting rule. An immediate corollary of the above result is that when there is a small number of agents, every unanimous voting rule is OBIC if the prior is independent. Corollary 2. If the prior is independent and n=3, every unanimous and symmetric voting rule is OBIC. Proof. Since π∈(0, 1),j∗=3π≤2. If j∗=1, we get B(1)=3π(1−π)2≤3ππ2+(1−π)2. If j∗=2, we get B(2)=3π2(1−π)=3π 22π(1−π)≤3π 2π2+(1−π)2. Hence, by Proposition 2, every unanimous voting rule is OBIC. To illustrate Proposition 2, suppose n=4. The condition (12)isgivenby 3λ(2)≤λ(1)+λ(4) 3λ(3)≤λ(1)+λ(4) 3λ(1)≤λ(0)+λ(3) 3λ(2)≤λ(0)+λ(3). Notice that for independent uniform priors, λ(k)=(1 2)4, the belief conditions fail. For sufficiently positively correlated beliefs where λ(0)and λ(4)are large, the belief conditions hold. This is in general true. If λ(0)and λ(n)are sufficiently large, (12)holds. Similarly, if λ(0)and λ(1)(or, λ(n−1)and λ(n)) are sufficiently large, (12)holds. 6. Large economies In this section, we apply our results to large economies. For this, we assume independent and identically distributed types. So πdenotes the probability that an agent is a type. Let μ:=nπ denote the mean of the binomial distribution. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 620 Lang and Mishra Theoretical Economics 19 (2024) There are two ways in which we increase the value of n. First, we fix the value of πand increase n. This implies that the expected number of atypes (μ) also increases. Second, we fix the expected number of atypes at μand increase n. This implies that the value of πdecreases with increasing n. We show the implication of large non the set of reduced-form implementable voting rules in both the cases. Since nis variable in this section, for an arbitrary voting rule, we denote the interim allocation probabilities as (Q(a;n),Q(b;n)).Forafixedπand n, the interim allocation probabilities corresponding to qualified majority and anti-qualified majority voting rules will be useful for our analysis. In particular, pick a qualified majority voting rule with quota j>0.5For such a qualified majority, the interim allocation probabilities satisfy Qj(a;n)−Qj(b;n)=1 nπ n  k=j kB(k)−1 n(1−π) n  k=j (n−k)B(k) =1 nπ n  k=j kC(n,k)πk(1−π)(n−k) −1 n(1−π) n  k=j (n−k)C(n,k)πk(1−π)(n−k) = n  k=j C(n−1, k−1)πk−1(1−π)(n−k) − n  k=j C(n−1, k)πk(1−π)(n−k−1) =C(n−1, j−1)πj−1(1−π)(n−j). (14) Similarly, for a qualified anti-majority with quota j>0, the interim allocation probabilities satisfy Qj(b;n)−Qj(a;n)=C(n−1, j−1)πj−1(1−π)(n−j). (15) This can also be seen from the fact that for a fixed quota j, the qualified majority and the qualified anti-majority interim allocation probabilities are related as Qj(a;n)=1− Qj(a;n)and Qj(b;n)=1−Qj(b;n). Depending on whether we increase nfor a fixed πor fixed μ, the right-hand side of (14)(and(15)) behaves differently. In the former case, it is approximately equal to a normal distribution with vanishing values of density. In the latter case, it is related to the Poisson distribution. This leads to different convergence results in these cases. 5Qualified majority with quota j=0 corresponds to the constant voting rule where ais chosen at every type profile. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 621 Proposition 3. Suppose πis fixed and π∈(0, 1).Then,forevery>0,thereexistsn0 such that for every n-agent economy with n>n 0, if interim allocation (Q(a,n),Q(b,n)) is reduced-form implementable, then Q(a;n)−Q(b;n)<. Proposition 3says that in large economies, the only reduced-form implementable probabilities are those where Q(a;n)=Q(b;n).6If the number of agents is large, the interim allocation probabilities (for any voting rule) are less sensitive to the type of the agent. Hence, both atypes and btypes get the same interim allocation probabilities with large n. However, this is not the case if the economies become large with a fixed μ.Ifμ is fixed, increasing ndecreases π, so the probability of atypes decreases, i.e., btypes dominate the economy. As a result, depending on how sensitive a voting rule is to the number of btypes (or atypes), we may get quite different interim allocation probabilities Q(a;n)and Q(b;n). For instance, consider the simple rule that chooses bwhen all agents have btype and chooses aotherwise. Then, if an agent has atype, the rule must choose Q(a;n)=1, but if an agent has btype, the rule chooses bif all other (n−1)agents have btype. For a fixed μ, the probability that a given agent has btype is 1 −(μ/n),so the probability that (n−1)agents have btype is (1−(μ/n))n−1, which converges to e−μ for large n.So,forlargen,wehaveQ(b;n)=1−e−μand Q(a;n)−Q(b;n)=e−μ>0. The proposition below uses a slightly more sophisticated voting rule to come up with an improved bound on Q(a;n)−Q(b;n). Proposition 4. Suppose μis fixed. Then there is a positive constant M(μ)such that for every >0,thereexistsn0such that for every n-agent economy with n>n 0, the following statements hold: (i) Interim allocation probabilities (Q(a,n),Q(b,n)) exist that are reduced-form implementable and Q(a;n)−Q(b;n)>M(μ)−. (ii) Interim allocation probabilities ( Q(a;n), Q(b;n)) exist that are reduced-form implementable and  Q(b;n)− Q(a;n)>M(μ)−. Combining Propositions 3and 4, and Corollary 1, we conclude that every reducedform implementable rule is strategy-proof in a large economy for the fixed π, but this is not the case if μis fixed. 6For correlated priors, it is well known that the central limit theorem does not hold in general. However, we conjecture that Proposition 3continues to hold for the case of infinite exchangeable priors, where we say an infinite sequence X1,X2,X3, of random variables is exchangeable if for any finite n,thejoint probability distribution of (X1,X2,,Xn)isthesameasthatof(Xσ(1),Xσ(2),,Xσ(n))for any permutation σ. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 622 Lang and Mishra Theoretical Economics 19 (2024) 7. Relation to the literature Border’s theorem for single object allocation problem was formulated in Matthews (1984)andMaskin and Riley (1984). The reduced-form characterization for this problem was developed in Border (1991). The symmetric version of Border’s theorem with an elegant proof using the Farkas lemma wass developed in Border (2007). There are other approaches to proving Border’s theorem (which also makes it applicable in some constrained environment): the network flow approach in Che, Kim, and Mierendorff (2013) and the geometric approach in Goeree and Kushnir (2023). Hart and Reny (2015)provide an equivalence characterization of Border’s theorem using second-order stochastic dominance. Kleiner, Moldovanu, and Strack (2021) further develop the majorization approach and apply it to a variety of problems in economics. Border’s theorem applies to private values single object auctions, but Goeree and Kushnir (2016)extendBorder’s theorem to allow for value interdependencies. Zheng (2024) generalizes reducedform characterizations to allocation of multiple objects with paramodular constraints. Lang and Yang (2023) study a universal implementation for allocation of multiple objects. Yang (2021) considers the consequences of incorporating fairness constraints in the reduced-form problem. Lang (2022) considers a public good allocation problem but with only two agents (but multiple alternatives). He provides an extension of Border’s theorem to his two-agent problem. Our ordinal voting model over two alternatives is a public good model with a specific type space, which is not covered in these papers. Vohra (2011) studies the combinatorial structure of reduced-form auctions by the polymatroid theory; see also Che, Kim, and Mierendorff (2013), Alaei, Fu, Haghpanah, Hartline, and Malekian (2019), and Zheng (2024). Our characterization condition shares some similarity with a polymatroid as it requires only integer-valued coefficients in linear inequalities. At the same time, it differs from a polymatroid in that the inequalities contain not only 0, 1 coefficients but more general integer coefficients. The two alternatives voting model has received attention in the literature in social choice theory—from May’s theorem (May (1952)) to its extensions, including a recent extension by Bartholdi, Hann-Caruthers, Josyula, Tamuz, and Yariv (2021). Schmitz and Tröger (2012)identify qualified majority rules as ex ante welfare maximizing in the class of dominant strategy voting rules. The results in Azrieli and Kim (2014) (which we discussed earlier) show that focusing attention to ordinal rules in this model is without loss of generality in a certain sense; see Nehring (2004)also. Appendix:Missing proofs We first prove Theorem 2and then Theorem 1. A.1 Proof of Theorem 2 Reduced-form probabilities (Q(a),Q(b)) are implementable if 1 nπ n  k=0 kq(k)B(k)=Q(a)(16) 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 623 1 n(1−π) n  k=0 (n−k)q(k)B(k)=Q(b)(17) 0≤q(k)≤1∀k∈{0, 1, ,n}. (18) Let Pbe the projection of this polytope onto the (Q(a),Q(b)) space. Clearly, Pis a polytope. Consider the linear program max QμaQ(a)+μbQ(b) subject to Q(a),Q(b)∈P.(LP-Q) As we vary μaand μb, the solutions to the linear program program (LP-Q)characterize the boundary points of P. Since each point in Pis equivalent to finding a voting rule q that satisfies (16), (17), and (18), we can rewrite the linear program (LP-Q) in the space of qas max qμa nπ n  k=0 kq(k)B(k)+μb n(1−π) n  k=0 (n−k)q(k)B(k) subject to 0 ≤q(k)≤1∀k∈{0, 1, ,n}. (LP-q) Hence, the set of boundary points of Pcan be described by the interim allocation probabilities of the voting rules obtained as a solution to the linear program (LP-q)aswevary μaand μb. We now do the proof in two steps. Step 1. We first show that every extreme point of Pis implemented by either a qualified majority voting rule or a qualified anti-majority voting rule, i.e., every element of P can be written as a convex combination of qualified (anti-) majority voting rules. It is sufficient to show that for every μaand μb, there is a solution to (LP-Q)thatis implemented by either a qualified majority or a qualified anti-majority voting rule. To show this, we show that for every μaand μb, some qualified (anti-) majority voting rule is a solution to (LP-q). By denoting ˆμa:=μa/(nπ)and ˆμb:=μb/(n(1−π)), we see that the objective function of (LP-q)is n  k=0nˆμb+k(ˆμa−ˆμb)q(k)B(k). We show that nˆμb+k(ˆμa−ˆμb)is either weakly increasing, in which case some qualified majority voting rule is optimal, or weakly decreasing, in which case some qualified antimajority voting rule is optimal. If nˆμb+k(ˆμa−ˆμb)>0forallk, then a solution to (LP-q)istosetq(k)=1forall k. This is the qualified majority with quota 0. If nˆμb+k(ˆμa−ˆμb)<0forallk,thena solution to (LP-q)istosetq(k)=0forallk. This is the qualified anti-majority with quota 0. If nˆμb+k(ˆμa−ˆμb)=0forallk, then every voting rule qis a solution. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 624 Lang and Mishra Theoretical Economics 19 (2024) If the sign of nˆμb+k(ˆμa−ˆμb)changes with k, then we consider two cases. If ˆμa>ˆμb, then there is a cutoff k∗such that nˆμb+k(ˆμa−ˆμb)>0forallk≥k∗and nˆμb+k(ˆμa− ˆμb)<0forallk<k ∗. Then the qualified majority with quota k∗is a solution to (LP-q). On the other hand, if ˆμa<ˆμb, then there is a cutoff k∗such that nˆμb+k(ˆμa−ˆμb)>0for all k≤k∗and nˆμb+k(ˆμa−ˆμb)<0forallk>k ∗. Then the qualified anti-majority with quota k∗is a solution of (LP-q).7Note that in both cases above, if nˆμb+k(ˆμa−ˆμb)=0 for k=k∗, the (anti-) qualified majority with quota k∗is a solution to (LP-q). Step 2. We now show that every qualified (anti-) majority voting rule implements a distinct extreme point of P. Every extreme point in Pis obtained by considering values of μaand μbthat generate a unique optimal solution to the linear program (LP-Q). It is sufficient to show that every qualified (anti-) majority voting rule is unique optimal solution to (LP-q)forsomeμaand μb. This is easily seen from our analysis above that for almost all μaand μb,incaseanoptimalsolutionto(LP-q) exists, it is unique and corresponds to a qualified majority or a qualified anti-majority voting rule. Combining Steps 1 and 2, we see that the set of extreme points of Pis the set of qualified majority voting rules and the set of qualified anti-majority voting rules. A.2 Proof of Theorem 1 We know that the necessary conditions for reduced-form implementation are (3)and (4). Let P∗denote the polytope described by (3)and(4). We show that the extreme points of P∗correspond to the qualified majority and the qualified anti-majority voting rules. From Theorem 2, we know that the extreme points of Palso correspond to the qualified majority and the qualified anti-majority voting rules. Hence, P=P∗. To show that the extreme points of P∗correspond to the qualified majority and the qualified anti-majority voting rules, we follow two steps. Step 1: Every q∈Q+∪Q−is an extreme point. Consider any qualified majority voting rule with quota j∈{1, ,n}. Using nπQj(a)= n  k=j kB(k)and n(1−π)Qj(b)= n  k=j (n−k)B(k), it is easy to verify that Qjsatisfies all inequalities in (3)and(4), and inequality (3)is binding for jand (j−1)at Qj. Since Qj∈P∗and Qjis the intersection of two linearly independent hyperplanes, it gives an extreme point of P∗. Since the qualified majority voting rule with quota 0 corresponds to a constant voting rule, it is also an extreme point. An analogous argument shows that the interim allocation probability of every qualified anti-majority voting rule with a quota j∈{0, ,n}is an extreme point. Step 2: No extreme point outside Q+∪Q−. Consider an extreme point of P∗that is not a qualified (anti-) majority rule. Then two non-adjacent constraints must be binding, i.e., 7When ˆμa=ˆμb,thesignofnˆμb+k(ˆμa−ˆμb)does not change with k. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 625 either (3)bindsforsomejand j+with >1, or (4)bindsforsomejand j+with >1, or (3) binds for some jand (4)bindsforsome. Assume first that (3)bindsforjand j+,where>1. The equality corresponding to (j+)is 0=(j+)(1−π)Q(b)−(n−j−)πQ(a)+ n  k=j++1 (k−j−)B(k) =πQ(a)+(1−π)Q(b)+j(1−π)Q(b)−(n−j)πQ(a) + n  k=j++1 (k−j)B(k)− n  k=j++1 B(k). Since inequality (3)bindsforj, substitute the equality into (3)forj+1, πQ(a)+(1−π)Q(b)≥ n  k=j+1 B(k). We get 0≥ n  k=j+1 B(k)− n  k=j++1 B(k)+ n  k=j++1 (k−j)B(k)− n  k=j+1 (k−j)B(k) = j+  k=j+1 B(k)− j+  k=j+1 (k−j)B(k)= j+  k=j+1 (j+−k)B(k)>0, which is a contradiction. Hence, (3) cannot bind for jand (j+)for >1. An analogous proof shows that (4) cannot bind for jand (j+)for >1. Now assume (3) binds for jand (4) binds for . Hence, adding those two equalities, we get 0=(j−)(1−π)Q(b)+(j−)πQ(a)+ −1  k=0 (−k)B(k)+ n  k=j+1 (k−j)B(k). If j≥and (j,)= (n,0 ), the right-hand side is positive, giving us a contradiction. If j<and (j,)=(0, n), using πQ(a)+(1−π)Q(b)≤1, we get 0=(j−)(1−π)Q(b)+πQ(a)+ −1  k=0 (−k)B(k)+ n  k=j+1 (k−j)B(k) ≥j−+ −1  k=0 (−k)B(k)+ n  k=j+1 (k−j)B(k) 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 626 Lang and Mishra Theoretical Economics 19 (2024) =j1− n  k=j+1 B(k)−1− −1  k=0 B(k)+n  k= kB(k)−nπ+nπ − j  k=0 kB(k) = j  k=0 (j−k)B(k)+ n  k= (k−)B(k)>0, which also gives us a contradiction. If (j,)=(n,0 )or (0, n), the two equalities determine (Q(a),Q(b)) =(0, 0)or (1, 1), which correspond to the two constant voting rules, which are in Q+∩Q−. A.3 Proof of Theorem 3 (i) ⇒(ii). Since Qis reduced-form monotone implementable, it is reduced-form implementable by a monotone voting rule q. Hence, we can write nπ(1−π)Q(a)−Q(b)= n  k=0k(1−π)−(n−k)πq(k)B(k)= n  k=0 (k−nπ)q(k)B(k) ≥qnπn  k=0 (k−nπ)B(k)=0, where we use monotonicity of qfor the inequality. This shows Q(a)≥Q(b). (ii) ⇒(iii). If Qis reduced-form implementable, by Theorem 2, it can be expressed as a convex combination of interim allocation probabilities of qualified majority and qualified anti-majority voting rules. Consider any qualified anti-majority with quota j∈{0, ,n}(qualified anti-majority with quota 0 corresponds to a constant voting rule). For each j∈{0, ,n}, define δ(j):=Qj(a)−Qj(b)=1 nπ j−1  k=0 kB(k)−1 n(1−π) j−1  k=0 (n−k)B(k) =1 nπ(1−π) j−1  k=0 (k−nπ)B(k). Note that δ(0)=0andδ(n)=−n(1−π)B(n)<0. For all j∈{0, ,n−1},weget δ(j+1)−δ(j)=1 nπ(1−π)(j−nπ)B(j), which is nonnegative if j≥nπ and negative if j<nπ. Hence, the value of δ(j)decreases with jfor all j<nπand increases after that until j=n. Since δ(0)=0andδ(n)<0, we conclude that δ(j)=Qj(a)−Qj(b)<0forallj∈{1, ,n}and δ(0)=0. On the other hand, for any qualified majority with quota j,wehaveQj(a)≥Qj(b). The qualified anti-majority with quota zero corresponds to a constant voting rule that 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Symmetric reduced-form voting 627 generates interim allocation probabilities Q(a)=Q(b)=0. Hence, if Q(a)≥Q(b),then Qis reduced-form implementable by convex combination of qualified majority voting rules and a constant voting rule that selects bat all type profiles. (iii) ⇒(iv). Every qualified majority and qualified anti-majority with quota zero generates interim allocation probabilities Qthat satisfy Q(a)≥Q(b). Hence, their convex combination also satisfies Q(a)≥Q(b).ByTheorem1,ifQis reduced-form implementable, then it satisfies (5). (iv) ⇒(i). The proof of Theorem 1shows that the set of extreme points of (5)is the set of qualified majority voting rules. The line Q(a)=Q(b)connects two constant voting rules and all the qualified majority voting rules satisfy Q(a)≥Q(b).Asaresult, any Qsatisfying (5)and(6) must be reduced-form equivalent to a convex combination of qualified majority voting rules and the two constant voting rules. Hence, it is reducedform monotone implementable. A.4 Proof of Proposition 1 By Theorem 3, the ex ante Rawlsian rule solves the optimization problem max Qmin(πQ(a),(1−π)1−Q(b) subject to Q(a)≥Q(b)(19) j(1−π)Q(b)−(n−j)πQ(a)+ n  k=j (k−j)B(k)≥0∀j∈{0, ,n}. (20) Consider the relaxed problem where we drop the inequalities in (19). Further, change the variables as follows: x:=πQ(a)and y:=(1−π)(1−Q(b)). So the relaxed problem (with inequalities (19)intermsofx,y)is max x,ymin(x,y) subject to jy +(n−j)x≤j(1−π)+ n  k=j (k−j)B(k)∀j∈{0, ,n}. (21) Notice that for any feasible solution (x,y)to the above problem, the solution ˆ x=ˆ y= min(x,y)is also a feasible solution with the same objective function value. Hence, it is without loss of generality to assume x=y. Hence, substituting x=yon the left-hand side of (21), we get nx, and the problem simplifies to max xx subject to nx ≤j(1−π)+ n  k=j (k−j)B(k)∀j∈{0, ,n}. (22) 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 628 Lang and Mishra Theoretical Economics 19 (2024) For every j∈{0, ,n},letH(j):=j(1−π)+n k=j(k−j)B(k). Hence, the optimal solution is given by x=y=1 nmin j∈{0,,n}H(j). For j∈{1, ,n},wesee H(j)−H(j−1)=1−π− n  k=j B(k). Let j∗:=max{j∈{0, ,n}:n k=jB(k)≥1−π}.ThenHis decreasing until j∗and increasing after that. So x=y=(1/n)H(j∗)is an optimal solution to the relaxed problem. This optimal solution corresponds to Q(a)=1 nπ j∗(1−π)+ n  k=j∗k−j∗B(k) Q(b)=1 n(1−π)n−j∗(1−π)− n  k=j∗k−j∗B(k). This corresponds to satisfying inequality (22)forj∗. Now define α:=1 Bj∗1−π− n  k=j∗+1 B(k). By definition of j∗,α∈[0, 1]. Using the expressions for Qj∗(a)and Qj∗+1(a),itcanbe easily verified that Q(a)=αQj∗(a)+(1−α)Qj∗+1(a) Q(b)=αQj∗(b)+(1−α)Qj∗+1(b). This shows that the optimal Qis a convex combination of two qualified majority voting rules with quotas j∗and j∗+1. Since each qualified majority is monotone, Qis also monotone. Hence, the optimum of the relaxed problem is a monotone voting rule. A.5 Proof of Proposition 2 By Theorem 5, every unanimous voting rule is reduced-form equivalent to a convex combination of u-qualified majority and u-qualified anti-majority rules. Since a convex combination preserves OBIC, every unanimous voting rule is OBIC if and only if every u-qualified majority and u-qualified anti-majority rule is OBIC. We know that every u-qualified majority is OBIC (since they are strategy-proof). Hence, every unanimous voting rule is OBIC if and only if every u-qualified anti-majority rule is OBIC. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5400 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License