Fair Division Flashcards
Pareto Efficiency
An agreement is Pareto efficient/optimal if there is no other feasible agreement that would make at least one agent strictly better off while not making the others worse off
=> there exists no other feasible agreement A’ such that A is Pareto dominated by A’
no intensity about preferences needed, just simple preference orderings
Pareto Dominance
PARETO DOMINANCE: Agreement A is Pareto dominated by agreement A’ if ui(A)
Welfarist Approach
> To judge fairness, the only information we should use are the utility levels of the individual agents.
> Rather than looking at allocations and assessing their relative fairness, we only need to look at and compare the utility vectors 〈u_1,…,u_n 〉∈R^n they induce.
Social Welfare Orderings
A binary relation ≼ over utility vectors
> transitive
reflexive
complete
Collective Utility Functions
SWO: u ≼ v ⟺ SW(u) ≤ SW(u)
1) UTILITARIAN SOCIAL WELFARE (SW):
Mapping each utility vector to the sum of individual utilities
> Satisfies ZI
2) EGALITARIAN SW:
mapping each utility vector to the minimum individual utility*
5) NASH SW:
mapping to the product
> combines efficiency and fairness
> Scale Independent
6) LEXIMIN ORDERING:
Natural refinement of egalitarian SW
> satisfies pigou dalton
Social Welfare Ordering AXIOMS
- ANONYMITY / Symmetry
States that It states that all agents should be treated equally. All SWOs listed satisfy anonymity - UNANIMITY
All listed SWOS are unanimous - PIGOU-DALTON PRINCIPLE
- Central intuition about fairness
> Satisfied by Leximin and Utaltarian ordering - SCALE INDEPENDENCE
SWO is independent by the individually used utility scales
> Satisfied by Nash Product - ZERO INDEPENDENCE
u Satisfied by Utilitarian SWO - Seperability
social welfare judgments should be independent of non-concerned agents. An SWO ≼ is separable if u ≼ v entails (u + w) ≼ (v + w)
Additive Utility Function
The utility of a bundle is the sum of the utilities of the parts of the bundle.
The function is additive only if it is both, subadditive and superadditive.
Subadditive Utility Function
The sum of utilities of two disjoint bundles will be less or equal to the utility assigned to their union.
Superadditive Utility Function
The sum of utilities of two disjoint bundles will be more or equal to the utility assigned to their union.
Envy Freeness
An allocation is envy-free if no agent STRICTLY prefers one of the bundles assigned to another agent to their own bundle.
If an allocation is complete (=every good needs to be allocated to some agent), then envy-free allocations do not exist for some combinations of utility functions
Cut-and-choose
One player cuts (a divisible good) in to two parts he considers to be of equal value
The other one chooses the piece
> Envy free
Pareto efficient
Proportional
Steinhaus Procedure (3 Players)
1) Player 1 cuts into three equal (as judged by her) pieces
2) Player 2 passes (or labels two of them as bad.)
Players 3,2,1 choose –> we are done
3) If players did not pass then player 3 can choose between passing and labelling
Then choosing in 2,3,1
4) If neither 2 or 3 passes then player 1 has to take the piece that the other players labelled as bad
> Ensures proportional outcomes > No guarantee for envy-freeness > No referee required > Pieces may not be contiguous > Algorithm
Operational Properties in the cake cutting procedure
Contigous procedures (minimizes cuts and preference for contigous slice)
minimal cuts
complexity
active referee needed?
algorithm (clearly defined sequence of queries
Banach-Knaster Procedure (last diminisher)
1) player 1 cuts one piece off (she considers as 1/n)
2) That piece is passed around the players
- -> option to pass or trim down further
3) After that the last player has to cut something off (the last diminished)
4) The remaining including trimmings is divided amongst the rest of the players
> Proportional
not envy-free
no external referee
can be made a contiguous procedure
Dubins-Spanier Procedure (moving knife procedure)
1) The referee moves the knife slowly across the cake until any players shouts stop
- -> that player receives the pieces
2) Continueing with rest
