Questions tagged [social-choice-theory]
For questions regarding the formal analysis of collective decision problems.
69
questions
0
votes
0
answers
20
views
Connectedness of logics and affine subsets
Let $(\mathbf{L}, \models)$ be a logic (where $\mathbf{L}$ is a set of propositions and $\models \: \subseteq \mathcal{P}(\mathbf{L} \times \mathbf{L}$ denotes entailment) satisfying monotonicity, ...
3
votes
0
answers
47
views
Which voting algorithm to use to assign N number of people to G groups based on their ranked choice preference
I've been looking through social choice theory textbooks and videos trying to find the right sort of algorithm for this, but struggling. Basically I have N (say 21) people that I need to assign into G ...
- 31
1
vote
1
answer
40
views
How are hypergraphs related to voting games?
The Wikipedia page on hypergraphs says
In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory.
I have not ...
- 113
1
vote
1
answer
50
views
Does Borda count satisfies the participation criterion?
The Borda count, or average rank method, is said to satisfies the participation criterion.
This means that this ranking method is free from the "no show paradox".
Do you know any proof of ...
- 143
3
votes
1
answer
104
views
Improving description of vector systems and aggregation rules for social sciences
I am working on a simple individual based model that aggregates information. I am not a mathematician, but I would like to be as precise as possible with the terminology used to describe the system ...
- 83
2
votes
1
answer
104
views
Gibbard–Satterthwaite Theorem clarification
recently I read about this theorem on math websites which talked about voting systems. since I'm interested in politics and math I'm interested to understand this theorem but it requires higher level ...
- 176
1
vote
1
answer
63
views
Does this proof of a voting related lemma work? if so, how?
I'm attempting to read this PDF on Arrow's impossibility theorem and ultrafilters. I find myself unconvinced that the proof of their Lemma 13 demonstrates what they say it does. I'm hoping someone ...
- 305
4
votes
1
answer
116
views
Can we make a voting system where it is cryptographically hard to find a dictator
As Wikipedia says, Arrow's impossibility theorem states that no rank-order electoral system can be designed that always satisfies these three "fairness" criteria:
If every voter prefers ...
- 305
1
vote
2
answers
97
views
Is there a known example of a voting system that does not satify the dictator fairness criterion but does satisfy the others?
As Wikipedia says, Arrow's impossibility theorem states that no rank-order electoral system can be designed that always satisfies these three "fairness" criteria:
If every voter prefers ...
- 305
6
votes
2
answers
409
views
Arrow's impossibility theorem simple proof and explanation
I am trying to prove the Arrow's Impossibility Theorem. I was searching on the internet but there is lots of different versions. I want to prove it for this statement:
Arrow's Theorem:
Consider a set ...
- 456
0
votes
1
answer
91
views
Reference request for a generalization of the Johnston power index
Background: Recall that the Johnston power index is a variation of the more well-known Banzhaf power index. While the Banzhaf power allocates 1 point to each time a player is in a winning coalition, ...
- 1,549
3
votes
1
answer
66
views
How do I interpret the social choice function noted by Felix Brandt?
How do I read this:
Let $\mathscr{U}$ be a universe of alternatives
Let $\mathcal{F}(\mathscr{U}):\forall\mathscr{A}\in\mathcal{F}(\mathscr{U}),\mathscr{A}\subseteq\mathscr{P}_{\geq1}(\mathscr{U})$
A ...
- 193
4
votes
2
answers
66
views
Organise "all possible voting schemes"
I’m currently reading 1, 2, and 3.
Wikipedia lists some of the better-known voting schemes (Borda count, approval voting, run-offs, …), a few of which have actually been tried in reality (e.g., the ...
- 4,287
1
vote
1
answer
175
views
Invariant for Gale–Shapley algorithm (Mating Ritual Algorithm)?
I found the following invariant for Mating Ritual algorithm (Lehman, Leighton and Meyer, Mathematics for Computer Science, §6.4) while going through MIT reading material:
Definition. Let $P$ be the ...
- 165
1
vote
0
answers
14
views
Can the Borda count be used to select a distribution and not just a single choice?
Suppose I have n individuals and n unique, indivisible objects of potential value. I want to allocate those objects so as to make total welfare as great as possible, subject to the constraint that no ...
- 195
0
votes
0
answers
22
views
Rational choices payment plans
I am trying to research what a rational choice constitutes; a financially sound decision based on critically examining a set of data and concluding that the expected value for a given choice is higher ...
- 1
3
votes
1
answer
237
views
Finding the Dictator in Arrow's Impossibility Theorem
Arrow's Impossibility Theorem states that if we have at least three different social states and a finite number of individuals (voters), any social welfare function that satisfies the conditions of ...
- 41
2
votes
2
answers
215
views
Difference between Arrow and Gibbard-Satterthawite theorem
I have a question related to two very important theorems from Social Choice Theory. What is the difference between Arrow Theorem and Gibbard-Saterthwaite theorem? I mean, the obvious one is that in G-...
- 367
4
votes
2
answers
67
views
Strategy-proofness of social choice function in two dimensions
Suppose the allocation space is the unit square $A=[0,1] \times [0,1] \in \mathbb{R}^2$. The outcome is a single point $x\in A$. Assume all agents have single-peaked preferences. That is, each agent $...
- 339
1
vote
1
answer
117
views
Number of paths ending at a vertex in a functional graph
Question
Let $G=\left(V,E\right)$ be a directed graph such that all $v\in V$ have outdegree exactly 1. Let $\alpha \in \left[ 0,1\right)$. Denote by $P\left(v\right)$ the set of all paths ending at ...
- 158
0
votes
1
answer
107
views
Two Part Probability Question
Part One: 12 college students attempt the same multiple choice question once each. The multiple choice question has eight possible choices, with only one being correct. If all 12 college students make ...
0
votes
1
answer
55
views
2 people 2 goods social choice
A 2-person society in which there are 2 consumption goods $x_1,x_2$. Individual 1's utility function is $u_1(x_1^1,x_2^1)=6+0.4ln(x_1^1)+0.6ln(x_2^1)$, while individual 2's utility is $u_2(x_1^2,x_2^2)...
- 797
0
votes
1
answer
370
views
Choice rule and path independence
Let a choice function be defined as a function $C:2^X \setminus \{\emptyset\} \rightarrow 2^X$ such that $C(A) \subseteq A$ for all $A \subseteq X$. Here, $2^X$ denotes the power set of $X$. We say a ...
- 331
0
votes
1
answer
110
views
Efficiency in Mechanism Design - Myerson-Satterthwaite
I was reading some online notes on the 4 conditions that cannot all hold given the Myerson-Satterthwaite theorem and this definition of efficiency confused me:
An efficient mechanism selects the ...
- 337
1
vote
0
answers
59
views
Numerical voting algorithm
This question relates closely to other posts. See note at the bottom.
Problem:
Suppose that a committee with $n$ members needs to vote on whether to accept a proposition.
Each member in the ...
- 483
3
votes
1
answer
680
views
In Arrow's Impossibility Theorem, what's the difference between a rank vote and a cardinal vote?
Arrow's impossibility theorem states that in any rank-based voting system involving three or more candidates, at least one of the following criteria will by necessity be violated:
If every individual ...
0
votes
1
answer
184
views
Arrow's impossibility theorem and the independence of irrelevant alternatives
I have a question about the axiom of independence of irrelevant alternatives (IIA). According to the Wikipedia page on IIA, Arrow's formulation of IIA is as in here. I do not quite get this. In ...
- 5,246
2
votes
1
answer
67
views
Are there corollaries (or generalised versions) of Arrow's theorem covering obvious fixes?
For a given set of alternatives $X=\{x_1,\dots,x_n \}$, let each individual have a total and transitive preference order among the alternatives $X$. The goal would be to have a system or rule to ...
- 7,106
0
votes
1
answer
601
views
Checking choice correspondence satisfy Weak Axiom of Revealed Preferences
I have a question whether the below choice correspondence satisfies WARP or not. I know how to check a choice satisfies WARP when set X is in he form of X={x,y,z} however i cannot figure out when it ...
- 13
5
votes
0
answers
195
views
Find a functional property satisfied by union of choice functions
Consider $X$ a finite set and let $2^{X}-\emptyset$ denotes its power set (excluding the empty set).
Definition 1: A choice function is a function $c:2^{X}-\emptyset\mapsto X$ satisfying $c(A)\in ...
- 798
1
vote
1
answer
439
views
What is a good introductory book on Rational Choice Theory for a mathematician?
I'm interested in Rational Choice Theory as an approach to political science. Amongst other, related subjects, I'd like to know a thing or two about Arrow's impossibility theorem (and other aspects of ...
- 5,451
2
votes
1
answer
98
views
name of a fairness criterion
I found the following fairness criterion in the exercises of Excursions in Modern Mathematics: If a majority of the voters have candidate X ranked last, then candidate X should not be a winner of the ...
- 125
0
votes
0
answers
286
views
Show, by example, that we can find social welfare functions which satisfy any three of the four Arrow's axioms.
I want to show, by example, that we can find social welfare functions which satisfy any three of the four Arrow's axioms.
Given at least three rewards, and at least two individuals, there is no ...
- 2,021
0
votes
1
answer
930
views
Pairwise majority voting and Arrow's axioms
The following is a question on Arrow's theorem with a pairwise majority decision. The bits I was unsure about was (bi) (is the 4th condition satisfied?) and also is (bii) correct? Thanks for your help
...
- 2,021
0
votes
1
answer
166
views
Arrow's theorem, strategic thinking and utilitarianism
I have this problem as part of a course on Decision Theory, and was not sure about question a (4th condition of Arrow's theorem) and question dii (utilitarianism). I have provided the whole question ...
- 2,021
2
votes
1
answer
45
views
does individually strategy proof implies coalitionally strategy proof?
Suppose $F$ is a social choice function \begin{equation*}F:N\rightarrow A\end{equation*}
where $N=\{1,...,n\}$ is the set of agents and $A$ is a finite set of outcomes.
suppose that $F$ is ...
- 1,125
0
votes
1
answer
529
views
Rational Fuctions, Choice Correspondence, Utility, Path Independence
I'm trying to prove that path independence implies that Sen's alpha holds. Can someone guide me on how i can approach this proof?
Specifically Sen's alpha essentially states, that if for a choice ...
2
votes
1
answer
290
views
Impartiality axiom in Terry Tao's Arrow's Theorem proof
The short expository paper is here.
On page 2,
The notion of a quorum is well-defined; it is not possible for such a group to be able to force a vote some of the time and not at other times ...
- 71
0
votes
2
answers
210
views
Maximal clique problem
I understood what clique is all the nodes of the sub graph have to be connected to each other. In the following figure, it says that the maximal clique is {1,2,3,4,5}. But as per the definition of ...
- 125
4
votes
0
answers
158
views
Literature about Ultrafilters
I am in the early stages of planning my senior project and was wondering if anybody had some recommendations of literature about the applications of ultrafilters in social choice theory, along with ...
- 133
1
vote
0
answers
61
views
Theory of social choice - relation of preference
Let $X =\{ a,b,c,d\}$ be a set a of possible choices. Define a relation of preference $R$ which generates a rule of choice $C'$ such that it generates another relation $R'$ which is different from $R$ ...
- 269
2
votes
1
answer
215
views
Understanding the proof of Gibbard-Satterthwaite theorem
Let $n$ be the number of voters and $A$ be the set of alternatives. For voter $i$, we denote by $a \succ_i b$, if $i$ prefers $a$ to $b$, where $a,b \in A$. Let $L(A)$ denote the set of all strict ...
- 2,870
1
vote
1
answer
351
views
Arrow's Impossibility Theorem: example function
I am looking for a social welfare function which satisfies "unrestricted domain", "Pareto efficiency", and "independence of irrelevant alternatives". One of the known proofs for Arrow's theorem argues ...
- 197
1
vote
1
answer
37
views
Can a Condorcet winner be generally dispreferred on an individual basis?
Suppose that a Condorcet winner exists in an election. Certainly it is possible that an individual voter prefers some other candidates to the Condorcet winner. They might even prefer most, or all, ...
- 155
2
votes
1
answer
211
views
Anyone know about definition of weak dictator?
I am trying to prove arrow's impossibility theorem in case which ties are allowed in individual preference lists and so is social preference list.
It says that if $p$ is a weak dictator, then we can ...
- 59
1
vote
1
answer
82
views
quasi rationality, interesting axiom of revealed preferences
So imagine there is a notion of rationality that captures the idea of "thresholds in preference." For example, let $\mathbb{Z}$ be the integers: $\mathbb{Z} = \{\dots, -10, -9, \dots, 0, 1, 2, \dots\}$...
user181066
2
votes
1
answer
157
views
Arrow's Impossibility Theorem Using Boolean Algebra
I am currently working on a research project which involves using Boolean matrices for the proof of Arrow's Impossibility Theorem and various other lemmas and results related to quasi ordered sets. In ...
- 21
1
vote
0
answers
226
views
Game Theory - Voting
In this setup there are 4 candidates running. For a candidate to be eliminated, the candidate needs to receive less than 1/3 of the votes when paired up with another candidate. This process ...
- 288
3
votes
1
answer
90
views
Are the following two definitions of Borda winner equivalent?
The Borda count is a method used to determine the winner object where people rank objects. For instance, imagine each person ranking 3 objects. The highest ranked object gets 2 points, the second gets ...
- 1,487
2
votes
1
answer
461
views
Proofs of Arrow's Theorem
I read Philip J. Reny's paper (Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach)
What I cannot understand is step 5 of the proof of arrow's theorem.
I think figure 4 is a ...
- 21