Skip to main content

Questions tagged [social-choice-theory]

For questions regarding the formal analysis of collective decision problems.

Filter by
Sorted by
Tagged with
1 vote
1 answer
55 views

How to say these two distinct functions have the same structure?

Yesterday, I posted this question, which remains unanswered. In this related question, I ask a different yet more precise question that may help me solve the other question. Let $N=\{1,2\}$ be a two-...
EoDmnFOr3q's user avatar
  • 1,226
2 votes
0 answers
41 views

How to change this definition of a voting rule?

I am working on a social choice problem that must allow for alternative sets of different sizes. In the paper I'm struggling to write, the environment is a $5$-tuple $(N,A_\tau,\mathcal{P}(A_\tau),\...
EoDmnFOr3q's user avatar
  • 1,226
-1 votes
0 answers
60 views

Can someone inductively prove this recursion formula? [duplicate]

This is admittedly directly related to this other question but it's a little different. Let: $$ a_n = \Big\lfloor (e-1)n! \Big\rfloor - 1 \qquad n \in \mathbb{Z} > 1 $$ where $e \approx$ 2....
robert bristow-johnson's user avatar
1 vote
0 answers
44 views

maximal/best element of a set of natural numbers where $x\mathbin{\mathrm{R}}y$ defined as “$x$ is a multiple of $y$”

I am doing a mock exam in social choice theory our teacher gave us and one question is: Let $X = \{1, 2, 3, \dots\,\}$ be the set of natural numbers and define $x\mathbin{\mathrm{R}}y$ as “$x$ is a ...
ELBO's user avatar
  • 11
1 vote
1 answer
50 views

Finding weights for the Borda count to elect any given candidate

Suppose three candidates A, B, and C run for office and voters submit their preference orders. The typical Borda count awards 2 points for a first-place vote, 1 point for a second-place vote, and 0 ...
Jared's user avatar
  • 31.7k
1 vote
1 answer
25 views

Properties of rules of preference

I am working on aggregation of preferences and something is unclear concerning one property of rules of preference namely the monotonicity. A $\mathcal{W}$ rule of preference is a function $F$ from $\...
G2MWF's user avatar
  • 1,381
3 votes
0 answers
119 views

Condorcet paradox in Wikipedia

Can someone please explain to me the steps for the calculation of the Condorcet paradox probability $q$ in the impartial culture model? I don't understand how does the Cauchy distribution arises from ...
yosh's user avatar
  • 73
1 vote
0 answers
43 views

Truthful budget partitioning

Suppose there is a budget $M$ that needs to be partitioned into two projects $A$ and $B$. There are two players, where the first player prefers to allocate $pM$ to A and $(1-p)M$ to $B$ (i.e., it ...
Doron's user avatar
  • 23
2 votes
0 answers
144 views

What properties of a voting method is best for deciding what movie to watch among a small group of people? [closed]

Almost every night me and my friends get together to watch a movie. Current Method: Each person (<10) picks 5 movies they want to watch and we vote on them. Each person gets around 7 votes which ...
Jacob Edie's user avatar
3 votes
0 answers
255 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 ...
Culi's user avatar
  • 31
1 vote
1 answer
61 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 ...
dfrankow's user avatar
  • 115
1 vote
1 answer
76 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 ...
Adrien Pavao's user avatar
3 votes
1 answer
118 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 ...
pyring's user avatar
  • 83
1 vote
2 answers
128 views

The number of distinct piles of ranked ballots in Ranked-Choice Voting.

This is about Ranked-Choice Voting (RCV) where the ballot has $C$ candidates, and there are $C$ levels of ranking of preference. Equal ranking of candidates is not allowed and no voter is required to ...
robert bristow-johnson's user avatar
2 votes
1 answer
196 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 ...
infinite's user avatar
  • 176
1 vote
1 answer
68 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 ...
Ryan1729's user avatar
  • 335
4 votes
1 answer
152 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 ...
Ryan1729's user avatar
  • 335
1 vote
2 answers
225 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 ...
Ryan1729's user avatar
  • 335
8 votes
2 answers
1k 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 ...
EvaMGG's user avatar
  • 486
0 votes
1 answer
119 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, ...
JoshuaZ's user avatar
  • 1,772
3 votes
1 answer
86 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 ...
John Moser's user avatar
4 votes
2 answers
85 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 ...
isomorphismes's user avatar
1 vote
1 answer
276 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 ...
fluty's user avatar
  • 135
1 vote
0 answers
15 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 ...
andrewH's user avatar
  • 229
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 ...
Peter's user avatar
  • 1
3 votes
1 answer
295 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 ...
nodim's user avatar
  • 41
2 votes
2 answers
264 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-...
ltrd's user avatar
  • 367
4 votes
2 answers
97 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 $...
user3727610's user avatar
1 vote
1 answer
125 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 ...
user401346's user avatar
0 votes
1 answer
121 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 ...
learning from brighter people's user avatar
0 votes
1 answer
72 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)...
Bob's user avatar
  • 817
0 votes
1 answer
548 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 ...
TeTs's user avatar
  • 331
0 votes
1 answer
134 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 ...
guy's user avatar
  • 387
1 vote
0 answers
62 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 ...
OO_SE's user avatar
  • 503
4 votes
1 answer
883 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 ...
TheEnvironmentalist's user avatar
0 votes
1 answer
212 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 ...
Calculon's user avatar
  • 5,775
2 votes
1 answer
86 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 ...
Thomas Klimpel's user avatar
0 votes
1 answer
780 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 ...
D.S's user avatar
  • 13
5 votes
0 answers
211 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 ...
Chazz's user avatar
  • 837
1 vote
1 answer
554 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 ...
Max Muller's user avatar
  • 7,148
2 votes
1 answer
108 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 ...
Dan's user avatar
  • 135
0 votes
0 answers
333 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 ...
thinker's user avatar
  • 2,179
0 votes
1 answer
1k 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 ...
thinker's user avatar
  • 2,179
0 votes
1 answer
211 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 ...
thinker's user avatar
  • 2,179
2 votes
1 answer
57 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 ...
Nathan Sikora's user avatar
0 votes
1 answer
567 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 ...
Saad Hirani's user avatar
1 vote
1 answer
369 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 ...
tmnet's user avatar
  • 61
0 votes
2 answers
248 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 ...
Ankur Bhatia's user avatar
4 votes
0 answers
207 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 ...
Marcus Dupree's user avatar
1 vote
0 answers
67 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$ ...
Pasato's user avatar
  • 269