Resource Allocation
COMP4418 Knowledge Representation and Reasoning
Haris Aziz1
1School of Computer Science and Engineering, UNSW Australia
1
How to assign donated kidneys?
2
How to allocate tasks to drones?
3
How to match employers to employees?
4
Outline
Allocation setting
Efficiency concepts
Fairness concepts
Other properties of mechanisms
Allocation of indivisible items under ordinal preferences Allocation of indivisible items with priorities
Allocation of indivisible items with endowments Allocation of divisible items
5
Allocation setting
Allocation Setting
Basic Allocation Setting
• Agents N = {1,…,n}
• Items O = {o1,…,om}
• Preferences (of agents) = {1, . . . , n}; preferences can be encoded by utility function u = (u1, . . . , un) over bundles of items.
An allocation X = (X1,…,Xn) assigns Xi ⊆ O to agent i.
• We will assume that Xi ∩ Xj = ∅ for all i , j ∈ N such that i ̸= j .
• We will focus on allocations that allocate all the items: i∈N Xi = O.
6
Some notation: Preferences
•
•
•
A i B (agent i prefers A at least as much as B)
A ≻i B ⇐⇒ A i B and B ̸i A (agent i strictly prefers A over B)
A ∼i B ⇐⇒ A i B and B i A (agent i is indifferent between A and B).
7
Some notation
ui : 2O −→ R+ specifies the utility function of each agent i for bundles of items.
ui(A)≥ui(B) ⇐⇒ Ai B.
8
Allocation setting: Additive Utilities
Unless specified otherwise, we assume additive utilities:
• ui : O −→ R+ specifies the utility function of each agent i. • ui(O′) = o∈O′ ui(o) for any O′ ⊆ O.
9
Allocation setting: Additive Utilities
Example
o1 o2 o3 o4 16321
24123 u1(o1) = 6; u1(o2) = 3; u1(o3) = 2; u1(o4) = 1.
u1({o1, o2}) > u1({o2, o3}). {o1, o2} ≻1 {o2, o3}.
10
Efficiency concepts
Pareto optimality
An allocation X is Pareto optimal if there exists no allocation Y suchthatYi i Xi foralli∈NandYi ≻i Xi forsomei∈N.
An allocation X is Pareto optimal if there exists no allocation Y such that ui(Yi) ≥ ui(Xi) for all i ∈ N and ui(Yi) > ui(Xi) for some i ∈ N.
11
Pareto optimality
An allocation X is Pareto optimal if there exists no allocation Y suchthatYi i Xi foralli∈NandYi ≻i Xi forsomei∈N. Example (Not Pareto optimal)
o1 o2 o3 o4 16231
24123 X1 = {o1, o3, o4}, X2 = {o2}.
12
Pareto optimality
Example (Pareto optimal)
o1 o2 o3 o4 16231
24123 X1 = {o1, o2, o3}, X2 = {o4}.
13
Utilitarian Social Welfare
An allocation X’s utilitarian social welfare is ui(Xi)
i∈N
Example (utilitarian welfare maximizing allocation)
o1 o2 o3 o4 16321
24123 X1 = {o1, o2, o3}, X2 = {o4}.
14
Egalitarian Social Welfare
An allocation X’s egalitarian social welfare is min{ui (Xi )}
i∈N
Example (egalitarian welfare maximizing allocation)
o1 o2 o3 o4 16231
24123 X1 = {o1}, X2 = {o2, o3, o4}.
15
Lexmin Welfare
For any allocation X , let f (X ) be the vector that orders the utilities achieved by the agents in non-decreasing order.
An allocation X maximizes lexmin welfare if it lexicographically maximizes f (X ).
Example (lexicographic comparison)
(6,6)>lex (5,8).
16
Lexmin Welfare
Example (lexmin welfare maximizing allocation)
o1 o2 o3 o4 16231
24123 X1 = {o1}, X2 = {o2, o3, o4}.
17
Nash Product Social Welfare
An allocation X’s Nash product welfare is ui(Xi)
i∈N
Example (Nash product welfare maximizing allocation)
o1 o2 o3 o4 16231
24123 X1 = {o1, o2}, X2 = {o3, o4}.
18
Nash Product Welfare
o1 o2 o3 o4 16231
24123
Table 1: Utilitarian welfare maximizing allocation
o1 o2 o3 o4 16231
24123
Table 2: Nash welfare maximizing allocation
o1 o2 o3 o4 16231
24123
Table 3: Egalitarian welfare maximizing allocation 19
Welfare-Pareto optimality
Fact
If an allocation maximizes utilitarian welfare or Nash product welfare or is a lexmin allocation, then it is Pareto optimal.
Proof.
• Assume the allocation is not Pareto optimal.
• Then there exists another allocation in which each agent gets
at least as much utility and one agents strictly more utility. • But then the allocation does not maximize welfare.
20
Fairness concepts
Envy-freeness
An allocation X satisfies envy-freeness if for all i , j ∈ N Xi i Xj
ui(Xi) ≥ ui(Xj) Example (Not envy-free)
o1 o2 o3 o4 16231
24123 X1 = {o1, o2, o3}, X2 = {o4}.
21
Proportional
An allocation X satisfies proportionality if for all i , j ∈ N ui(Xi) ≥ ui(O)
n
Example (Not proportional)
o1 o2 o3 o4 16231
24123 X1 = {o1, o2, o3}, X2 = {o4}.
22
Envy-freeness implies proportionality
Fact
If an allocation is complete and utilities are additive, envy-freeness implies proportionality.
Assume that an allocation X is envy-free. Then for each i ∈ N,
Thus,
Hence
ui(Xi) ≥ ui(Xj) for all j ∈ N.
n · ui(Xi) ≥ ui(Xj) = ui(O).
j∈N
ui(Xi) ≥ ui(O)/n.
23
Non-existence of envy-free or proportional allocation
Example
o1 o2
191 291
24
Allocation of indivisible items
Theorem (Demko and Hill [1988])
For additive utilities, checking whether there exists an envy-free or proportional allocation is NP-complete.
25
Allocation of indivisible items
Proof.
We present a reduction from the following NP-complete problem.
IntegerPartition
Input: A set of integers S = {w1,…,wm} such that
w∈S w = 2W.
Question: Does there exist a partiton (S′,S′′) of S such that w∈S′ w = w∈S′′ w = W?
• Consider the setting in which two agents have identical utilities over the m items with the utility for the j-th item being wj and the total utility of each agents over the items being 2W .
• Then, there exists a proportional allocation iff there is a integer partition of the integers corresponding to the weights so that each partition has total weight W .
26
Maxmin Fair Share (MmS) Fairness
Definition (Maxmin Fair Share Fairness)
Given an instance I = (N, O, u), let Πn denote the space of all partitions of O into n sets. The maximin share guarantee of an agent i ∈ N is
MmSi(I) = max min (P1,…,Pn)∈Πn j∈{1,…,n}
ui(Pj).
An allocation X is a maximin share (MmS) fair allocation if we have ui(Xi) ≥ MmSi(I) for each agent i ∈ N.
27
Maxmin Fair Share (MmS) Fairness
Example (Satisfies MmS Fairness)
o1 o2 o3 o4 12116
21135
MmS1(I) = 4; MmS2(I) = 5
Hint for computing MmS value for an agent: pretend all the agents have the same utility func tion and compute the maximum egalitarian welfare.
28
Proportionality implies MmS fairness
Fact
A proportional allocation satisfies MmS fairness.
Suppose an agent i does not get her MmS value in allocation X.
Then
Then there exists an allocation Y = (Y1, . . . , Yn) such that
Hence, Hence
MmSi(I) ≤ ui(Yj) ∀j ∈ [n]. MmSi (I ) ≤ ui (O)/n.
ui(Xi) < MmSi(I) ≤ ui(O)/n.
ui(Xi) < MmSi(I).
29
Pareto optimality and Fairness
Fact
Pareto improvement over a proportional allocation is proportional.
Fact
Pareto improvement over a MmS fair allocation is MmS fair.
Fact
Pareto improvement over an envy-free allocation may not be envy-free.
30
EF1 Fairness
Definition (EF1 Fairness)
Given an instance I = (N, O, u), an allocation X satisfies EF1 (envy-freeness up to 1 item) if for each i,j ∈ N, either Xi i Xj or there exists some item o ∈ Xj such that
Xi i Xj \{o}.
31
EF1 Fairness
Example (Satisfies EF1 Fairness)
o1 o2 o3 o4 12116
21135 X1 = {o1, o2, o3}, X2 = {o4}.
32
Algorithm for EF1 fairness (Lipton et al. (2004) )
Input : n agents, m items, and valuations ui (oj ) ≥ 0 for each i ∈ [n] and j ∈ O.
Output: EF1 allocation X
1:
2: 3:
4: 5: 6:
Initialize allocation X = (X1, X2, . . . , Xn) with Xi = ∅ for all i ∈ [n].
forj=1tomdo
Construct an envy-graph G(X) = (N,E) where (i,j) ∈ E if i is envious of j’s allocation wrt allocation X.
Pick a vertex i that has no incoming edges in G(X) UpdateXi ←Xi ∪{oj}.
while the G(X) contains a cycle do
33
Algorithm for EF1 fairness (Lipton et al. (2004) )
7: Implement an exchange in which if i points to j in the cycle, then i gets j’s allocation.
8: end while
9: end for 10: Return X.
34
Algorithm for EF1 fairness (Lipton et al. (2004) )
Algorithm by Lipton et al. [2004].
24
3
15
35
Algorithm for EF1 fairness (Lipton et al. (2004) )
Envy graph (an agent points to another agent if she envies her). Suppose the graph is for a partial allocation that is EF1 fair.
Agent 5 has no incoming arc so if she gets a new item, the allocation is still EF1 fair.
36
Algorithm for EF1 fairness (Lipton et al. (2004) )
24
3
15
A new item is given to agent 5 who has no incoming arc. This may make some other agent envious (in this case agent 3 is now envious of agent 5).
37
Algorithm for EF1 fairness (Lipton et al. (2004) )
24
3
15
We enable an exchange of allocations along the cycle which removes the cycle.
38
Algorithm for EF1 fairness (Lipton et al. (2004) )
24
3
15
We enable an exchange of allocations along the cycle which removes the cycle.
39
Fairness Overview
• EF implies proportionality which implies MmS fairness.
• EF implies EF1 fairness.
• EF, Proportional, and MmS fair allocations may not exist and are computationally hard to compute even if they exist.
• An EF1 allocation always exists and can be computed in polynomial time.
40
Other properties of mechanisms
Strategyproofness
An allocation rule f is strategyproof if there exists no preference profile such that
f(1,...,i−1,′i,i+1,...,n) ≻i f(). Example (Leximin Mechanism is not strategyproof)
o1 o2 o3 o4 16221
24123 o1 o2 o3 o4
14232 24123
41
Computational complexity
• We want that the solution concept should be efficiently computable
• Even if the algorithm computing the solution is manipulable, we may prefer that the algorithm is computationally hard to manipulate [Bartholdi, III et al., 1989].
42
Desirable properties of mechanisms: a summary
• welfare: utilitarian/egalitarian/Nash; Pareto optimality
• fairness: envy-freeness; proportionality; egalitarian
equivalence; MmS; and EF1.
• resistance to manipulation: strategyproof; computationally hard to manipulate; rarely manipulable
• computationally efficient We will also look at stability.
43
Allocation of indivisible items under ordinal preferences
House Allocation
Consider the house allocation setting (N, O, ≻) where |N| = |O| and agents have strict and ordinal preferences over individual items. Each agent gets one item.
We use comma separated lists to denote the preference lists in strictly decreasing order of preferences.
Example
≻1, ≻2: o1, o2, o3, o4 ≻3, ≻4: o2, o1, o4, o3
44
Serial Dictatorship
For a house allocation problem (N, O, ≻) where |N| = |O|, Serial Dictatorship with respect to permutation π over N: agents get one turn each in the order of the permutation. They sequentially take their most preferred item that has not yet been allocated.
Example
≻1, ≻2: o1, o2, o3, o4 ≻3, ≻4: o2, o1, o4, o3 π = 1234.
SerialDictator((N, O, ≻), π) = ({o1}, {o2}, {o4}, {o3}).
45
Serial Dictatorship
Non-bossiness: an agent cannot change her preference so that she gets the same allocation but some other agent gets a different allocation.
Neutral: the allocation does not depend on the names of the items.
Theorem (Svensson [1999])
For housing allocation problems, a mechanism is strategyproof, non-bossy and neutral if and only if it is a serial dictatorship.
Theorem (Abdulkadiro ̆glu and S ̈onmez [1998])
For housing allocation problems, an allocation is Pareto optimal iff it is a result of serial dictatorship.
46
Sequential Allocation where |O| can be greater than |N|
For an assignment problem (N, O, ≻), sequential allocation with respect to policy π over N: agents come in the order the policy π and sequentially take their most preferred item that has not yet been allocated.
47
Sequential Allocation where |O| can be greater than |N|
Example
For policy: π = 1212
• 1 takes a • 2 takes b • 1 takes c • 2 takes d
≻1: a,b,c,d ≻2: b,c,d,a
48
Sequential Allocation where |O| can be greater than |N|
Fact (Kohler and Chandrasekaran [1971])
Sequential allocation is not strategyproof in general.
Idea: If an agent can always get a highly preferred item because no one likes it, she can take it later and first go for the highly demanded lesser preferred item.
49
Sequential Allocation where |O| can be greater than |N|
Example
Policy: 1212
1 takes a; 2 takes b; 1 takes c; 2 takes d
≻ ′1 : b , a , c , d ≻2: b,c,d,a
1 takes b; 2 takes c; 1 takes a; 2 takes d
≻1: a,b,c,d ≻2: b,c,d,a
50
Allocation of indivisible items with priorities
School Choice
• N = {1,...,n} set of of students/agents.
• Set of schools C = {c1,...,ck}
• Each school c ∈ C has q(c) seats
• ≻= (≻1, . . . , ≻n) preferences of agents. Each agent i ∈ N has strict preferences over the schools.
• Each school c has a strict priority ≻c order over the students. Agents are students; school seats are items.
51
Student Proposing DA (Deferred Acceptance)
Agents (students) with strict preferences over schools; items (school seats with each school containing certain quota)
1: 2: 3:
while some student has not been rejected from all the schools do
All the unmatched students apply to their most preferred acceptable school that has not rejected them.
For each school c ∈ C, let Sc be the set of students who are matched to c or who now apply to c. School c selects a maximum of q(c) acceptable students from among Sc and rejects the rest.
end while
return Matching X that represents the current matches.
4: 5:
52
Student Proposing DA (Deferred Acceptance)
The quota of each school a, b, c is 1.
1 : b,a,c 2 : a,b,c 3 : a,b,c
• 2and3applytoa;1appliestob • a rejects 2 in favour of 3
• 2 applies to b
• b rejects 1 in favour of 2
• 1 applies to a
a : 1,3,2 b : 2,1,3 c : 2,1,3
{{1, b}, {3, a}} {{2, b}, {3, a}}
53
Student Proposing DA (Deferred Acceptance)
• a rejects 3 in favour of 1 {{2, b}, {1, a}} • 3 applies to b
• b rejects it in favour of 2
• 3 applies to c and gets accepted. {{3, c}, {2, b}, {1, a}}.
54
Student Proposing DA (Deferred Acceptance)
Student Proposing DA algorithm terminates in time linear in the size of the preference profile.
• In each step, the agents’ potential school matches decreases (if it does not decrease each agent is matched)
• School’s tentative matches keep improving (if they do not improve, it means there are no new proposals)
55
Student Proposing DA (Deferred Acceptance)
Justified envy-freeness: there exists no agent i who prefers another school s over her match and s admits j a lower priority agent than i.
Theorem (Roth and Sotomayor [1990])
Student Proposing DA returns an allocation that satisfies justified envy-freeness.
Suppose for contradiction that i has justified envy for j with respect to school s.
Then i is matched to a less preferred school than s. Then i got rejected by s.
56
Student Proposing DA (Deferred Acceptance)
Case 1: If j had proposed to s at or before this time point, she would have been rejected by s as well.
Case 2: If j proposed to s after this time point, it would have been rejected as well since s has enough proposals by higher priority agents.
57
Student Proposing DA (Deferred Acceptance)
Justified envy-freeness: there exists no agent i who prefers another school s over her match and s had admitted j a lower priority agent than i.
Theorem (Roth and Sotomayor [1990])
Student Proposing DA is strategyproof. The resultant allocation Pareto dominates (wrt to students) all allocations that satisfy justified envy-freeness.
58
Two-sided matching
For details on two-sided matching, see books by Roth and Sotomayor [1990], Gusfield and Irving [1989] and Manlove [2013].
59
Allocation of indivisible items with endowments
(Shapley-Scarf) Housing market: simple model with endow- ments
(N,O,≻,e)
• |N|=|O|
• ei = {o} iff o is owned by i ∈ N.
• Agents have strict preferences over items
• Each agent owns and is allocated one item.
60
(Shapley-Scarf) Housing market: simple model with endow- ments
Example
Housing market (N, O, e, ≻) such that
• N = {1,...,5}, O = {o1,...,o5},
• ei = {oi} for all i ∈ {1,...,5}
• and preferences ≻ are defined as follows:
agent 12345
preferences o2 o3 o4 o1 o2 o1 o2 o3 o5 o4 o4 o5
61
Individual rationality
An allocation X is individually rational if no agent minds participating in the allocation procedure:
∀i∈N: Xiiei
If an agent does not have any endowment, her allocation is individually rational if her allocation is acceptable (at least as preferred as the empty allocation).
An agent can express an allocation or an item as unacceptable by simply not lising it in the preference list.
62
Allocation with endowments: Core
An allocation X is core stable if there exists no S ⊆ N such that there exists an allocation Y of the items in i∈S ei to the agents in S such that
∀i∈S: Yi≻iXi
Fact
A core stable allocation is individually rational.
63
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
Input : Housing Market Instance Output: Allocation X
1: ConstructthecorrespondingdirectedgraphG()=(V,E) where V = N ∪ H and E is specified as follows: each house points to its owner and each agent points to the most preferred house in the graph.
2: while G is not empty do
3: Start from an agent and walk arbitrarily along the edges
until a cycle is completed.
64
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
4:
5:
Remove the cycle is removed from G(). Within the removed cycle, each agent gets the house he was pointing to in G.
The graph G() is adjusted so that the remaining agents point to the most preferred houses among the remaining houses.
6: end while 7: Return X.
65
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
• Each item points to its owner.
• Each agent points to her most preferred item in the graph.
• Find a cycle, allocate to each agent in the cycle the item she was pointing to. Remove the agents and items in the cycle. Adjust the graph so the agents in the graph point to their most preferred item in the graph.
• Repeat until the graph is empty.
66
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
agents
item owned
agents
1 2
o1 o2 1 2
1
preferences o2 o1 o2 o1 o2
o1
2
67
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
• Each item points to its owner.
• Each agent points to her most preferred item in the graph.
• Find a cycle, allocate to each agent in the cycle the item she
was pointing to. Remove the agents and items in the cycle. Adjust the graph so the agents in the graph point to their most preferred item in the graph.
• Repeat until the graph is empty. agents12 1
item owned o1 o2 agents 1 2
preferences o2 o1 o2 o1 o2
o1
2
68
Housing Market Example
Example
Housing market M = (N, O, e, ≻) such that
• N = {1,...,5}, O = {o1,...,o5},
• ei = {oi} for all i ∈ {1,...,5}
• and preferences ≻ are defined as follows:
agent 12345
preferences o2 o3 o4 o1 o2 o1 o2 o3 o5 o4 o4 o5
69
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
agent 12345
2
o3
o2
1
o1 5
o5
preferences
o2 o3 o4 o1 o2 3
o1 o2 o3 o5 o4
o4 o5
o4
4
70
Example: TTC
agent 12345
2
o3
o2
1
o1 5
o5
preferences
o2 o3 o4 o1 o2 3
o1 o2 o3 o5 o4
o4 o5
o4
4
70
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
2
o2
1
o1 5
o5
o3 o1 o2 o3 o5 o4
o4 o5
o4
agent 12345
preferences
o2 o3 o4 o1 o2 3
4
70
Housing Markets: Gale’s Top Trading Cycles (TTC) Algorithm
2
o2
1
o1 5
o5
o3 o1 o2 o3 o5 o4
o4 o5
o4
agent 12345
preferences
o2 o3 o4 o1 o2 3
4
70
TTC (Top Trading Cycles)
Theorem (Shapley and Scarf [1974] and Roth and Postlewaite [1977])
For housing markets (with strict preferences), TTC is strategyproof, individually rational, Pareto optimal and core stable.
Theorem (Ma [1994])
For housing markets (with strict preferences), a mechanism is strategyproof, individually rational and Pareto optimal iff it is TTC.
71
General Exchange Market with Dichotomous Preferences
An exchange market is a tuple I = (N, O, e, D) where
N = {1,...,n} be a set of n agents and O be the set of items.
• The vector e = (e1,...,en) specifies the endowment ei ⊂ O of each agent i ∈ N. Agents have disjoint endowments.
• Each agent has a demand set Di ⊂ 22O . [Di is a set of subsets of O]
Each element of Di is a bundle of items that satisfies agent i. [Can be viewed as a disjunction of goals]
72
General Exchange Market with Dichotomous Preferences
An exchange market is a tuple I = (N, O, e, D) where
N = {1,...,n} be a set of n agents and O be the set of items.
• Any allocation X = (X1, . . . , Xn) specifies the allocated bundleXi ⊂Oofeachagenti∈N.
We say that allocation X satisfies agent i if Xi ⊇ d for some d ∈ Di .
Example
Di ={{a},{b,c}}
Xi = {a, b} satisfies agent i .
73
Generality of the Model
• If|ei|=1foreachi∈Nand|d|=1foreachd∈Di,the market can model a kidney exchange market
• If|ei|=2foreachi∈Nand|d|=2foreachd∈Di,the market can model a lung exchange market
• It can also model a multi-organ exchange market
• Can model altruistic donors
74
Strongly Individually Rationality
An allocation X is strongly individually rational (S-IR) if Xi ⊇ ei or Xi ⊇d,forsomed∈Di.
An agent will only give away some of her possession
if she is satisfied in return.
75
Conditional Utilitatian Priority Mechanism
If an agent i is satisfied, her utility ui (X ) is 1. Otherwise, it is 0. ρ(I) is the set of feasible allocations.
Take any permutation π of N.
CUP(I,ρ,π) = argmaxX∈ρ(I)(ui(X),uπ(1)(X),...,uπ(n)(X)). i∈N
76
Conditional Utilitatian Priority Mechanism
Theorem (Aziz [2020])
For any feasibility restriction on the set of S-IR allocations, CUP is strategyproof.
77
Allocation of divisible items
Allocation of divisible items: AW (Adjusted Winner)
Agent 1 and 2 are each given C utility points that they can use for
acquiring m items. Let xi be the number of points used by 1 on item i
and yi be the number of points used by 2 on item i. Call xi the ratio of yi
item i.
1: Each item is assigned to the agent that values it the most. Ties are
broken in favour of agent 1.
2: while agent 1 gets strictly more utility than agent 2 do
3: Consider an item with the smallest ratio that agent 1 gets partially
or fully. Transfer as much of the item to agent 2 while ensuring
agent 1 gets at least as much utility as agent 2.
4: end while
5: Return the allocation
78
Allocation of divisible items: AW (Adjusted Winner)
xxxxx k1 ≥ k2 ≥···≥ ki ≥≥ ki+1 ≥···≥ km
yk1 yk2 yki yki+1 ykm
Allocation of agent 1 Allocation of agent 2
79
Allocation of divisible items: AW (Adjusted Winner)
o1 o2 o3 1 67 6 27
2 34 5 61
• Initially, agent 1 gets 73 points; Agent 2 gets 61 points
• o2 is given from agent 1 to agent 2
• o1 must be partially given to agent 2. Agent 2 gets 1/101 of o1 and
agent 1 gets 100/101 so that both get 67 × 100 ≈ 66.3366337 points. 101
80
Allocation of divisible items: AW (Adjusted Winner)
o1 o2 o3
1 100/101 67 6 27 2 1/10134 5 61
81
Allocation of divisible items: AW (Adjusted Winner)
Equitability: all agents get the same utility.
Theorem (Brams and Taylor [1996])
AW is Pareto optimal, equitable, envy-free, and proportional, and requires at most one item to be split.
Theorem (Aziz et al. [2015])
For two agents, AW is the only Pareto optimal and equitable rule that requires at most one item to be split.
82
Allocation of divisible items: Proportional Allocation Rule
Both agents are given equal number of points that they can allocate to the items. Let xi be the number of points used by 1 on item i and yi be the number of points used by 2 on item i. Then agent1gets xi oftheitemoi and2gets yi oftheitemoi
xi +yi
Theorem (Brams and Taylor [1996])
The Proportional Allocation Rule is equitable and envy-free but not necessarily Pareto optimal.
Argument for equitability:
Utility of agent 1 is m (xi × xi
m(yi×yi ). i=1 xi+yi
). Utility of agent 2 is
xi +yi
i=1 xi+yi
83
Allocation of divisible items: Proportional Allocation Rule
mmmmm xi2 − yi2 (xi − yi )(xi + yi )
x +y = x +y = (xi−yi)= xi− yi =0. i=1iii=1 ii i=1 i=1i=1
84
Allocation of divisible items
Theorem (Zhou [1990])
If fractional allocations are allowed and agents have additive cardinal utilities, then strategyproofness, Pareto optimality and envy-freeness are incompatible.
Note that any two of the properties are easy to achieve:
• strategyproofness and Pareto optimality: dictatorship
• strategyproofness and envy-freeness: null allocation
• envy-freeness and Pareto optimality: Nash welfare maximizing allocation.
85
PA (Partial Allocation) mechanism for allocation of divisible items
• Compute the Nash welfare maximizing allocation X∗ based on the reported valuations.
• For each agent i, remove the agent and compute the Nash welfare maximizing allocation X∗−i that would arise when i does not exist.
• Allocate to each agent i a fraction fi of everything i receives according to X∗ where
i′̸=i[ui′(X∗)] fi =′ [ui′(X∗ )].
Theorem (Cole et al. [2013])
PA is strategyproof, envy-free and each agent gets 1/e of the utility she would get in a Nash welfare maximizing allocation.
i ̸=i −i
86
Survey and Further Reading
• Most relevant resource: book chapter by Bouveret et al. [2016] in the Handbook of Computational Social Choice. http://www.cse.unsw.edu.au/~haziz/comsoc.pdf
• Brandt et al. [2016] especially chapters 11-14
• Brams and Taylor [1996]
• Robertson and Webb [1998]
• Moulin [2003]
• Endriss [2010]
• Roth and Sotomayor [1990]
• Gusfield and Irving [1989]
• Manlove [2013]
• Chalkiadakis et al. [2011]
87
Contact
• haziz@cse.unsw.edu.au
88
References
A. Abdulkadiro ̆glu and T. S ̈onmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689–701, 1998.
H. Aziz. Strategyproof multi-item exchange under single-minded dichotomous preferences. Autonomous Agents and Multi-Agent Systems, 34(1):3, 2020.
H. Aziz, S. Brˆanzei, S. Frederiksen, and A. Filos-Ratsikas. The adjusted winner procedure: Characterizations and equilibria. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 454–460, 2015.
89
J. Bartholdi, III, C. A. Tovey, and M. A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227–241, 1989.
S. Bouveret, Y. Chevaleyre, and N. Maudet. Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 12. Cambridge University Press, 2016.
S. J. Brams and A. D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.
F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.
90
G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Cooperative Game Theory, volume 5 of Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool, 2011.
R. Cole, V. Gkatzelis, and G. Goel. Mechanism design for fair division: allocating divisible items without payments. In Proceedings of the 14th ACM Conference on Electronic Commerce (ACM-EC), pages 251–268. ACM Press, 2013.
S. Demko and T. P. Hill. Equitable distribution of indivisible objects. Mathematical Social Sciences, 16:145–158, 1988.
U. Endriss. Lecture notes on fair division. 2010.
D. Gusfield and R. W. Irving. The stable marriage problem: Structure and algorithms. MIT Press, Cambridge, MA, USA, 1989.
91
D. A. Kohler and R. Chandrasekaran. A class of sequential games. Operations Research, 19(2):270–277, 1971.
R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (ACM-EC), pages 125–131. ACM Press, 2004.
J. Ma. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory, 23(1): 75–83, 1994.
D. Manlove. Algorithmics of Matching Under Preferences. World Scientific Publishing Company, 2013.
H. Moulin. Fair Division and Collective Welfare. The MIT Press, 2003.
92
J. M. Robertson and W. A. Webb. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters, 1998.
A. E. Roth and A. Postlewaite. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2):131–137, 1977.
A. E. Roth and M. A. O. Sotomayor. Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge University Press, 1990.
L. S. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1(1):23–37, 1974.
L.-G. Svensson. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4):557–567, 1999.
L. Zhou. On a conjecture by Gale about one-sided matching problems. Journal of Economic Theory, 52(1):123–135, 1990.
93