Fair Division CSE 516A: Multi-Agent Systems Sujoy Sikdar 1 Resource Allocation Problem A set of agents A set of resources Valuations Valuation of agent is Range is when resources are goods, when bads

Additive valuations: with Allocations , a partition of resources among the agents is a partial allocation if 2 Cake Cutting Resource: Heterogenous Divisible

Constraints: Full allocation (no waste) Each , where is the set of finite union of disjoint intervals Simple allocations Each agent is allocated a single interval Cuts cake at points 3 Fairness Desiderata Proportionality (Prop)

Every agent gets their fair share Envy-Freeness (EF) No agent wishes she had another agents allocation Equitability (EQ) All agent value their allocations equally No agent is jealous of another agents allocation 4 Relationship between Fairness Criteria

EF Prop , Sum over all other agents EQ incomparable to EF, Prop Eg. When every agent values her allocation at 0 (EQ), but values every other agents allocation at 1 (not EF or Prop) 5 Prop: Cut and Choose 1 divides cake in two pieces X, Y

2 chooses the piece she prefers 1 divides the cake so that The allocation is EF (therefore Prop) Discrete Continuous pieces Minimum number of cuts 6 Computational Aspects: What is the input? Time complexity for agents?

Valuations part of the input: how to encode them? s are functions May be infinite binary representation Want: Running time as function of 7 Robertson-Webb Model Query Complexity Access to restricted to two queries

returns returns s.t. How many queries for ? 2 8 Dubins-Spanier: Moving Knife Referee starts at 0 and moves knife to the right In rounds:

When the piece to the left of the knife is worth to a player, player shouts stop, gets the piece, exits Last player gets remaining piece How to implement using the two queries? 9 Dubins-Spanier: Query complexity What is the query complexity? Satisfies Prop EF?

Can we do better? Even-Paz Asymptotically optimal: Any Prop protocol needs queries [Edmonds & Pruhs] 10 Envy-Freeness? : Cut and Choose : Selfridge-Conway procedure

Discrete, number of cuts is not minimum Stromquist procedure Continuous, four simultaneous moving knives : No known procedure with continuous pieces Up to 5 cuts [Barbanel & Brams, 2004] : [Aziz & Mackenzie, 2016]: protocol!

11 Price of Fairness Social welfare (SW) of Price of EF: Worst case (over valuation functions) ratio between: SW of best allocation SW of EF allocation [Caragiannis et al., 2009]: Price of Prop is Price of EF is , upper bound?

Price of EQ is 12 Other Desiderata Pareto Optimality (PO) Notion of efficiency No obviously better allocation Strategyproofness (SP) / Incentive Compatibility No agent should be able to gain by misreporting their valuation 13

Pareto Optimality (+ EF) Always Exists [Weller, 1985] Nash-optimal allocation: Nash Welware: Nash optimal allocation (MNW): PO is easy to see EF is non-trivial to prove Hard to compute in general Polynomial time for piecewise constant valuations PO + EF + EQ not guaranteed to exist [Barbanel and Brams, 2011] 14

Strategyproofness Deterministic: [Menon & Larson, 2017]: No deterministic SP mechanism is (even approximately) proportional Randomized: [Chen et al., 2013, Mosel & Tamuz, 2010]: There is a randomized SP mechanisms that always returns an EF allocation 15

Perfect Partition Perfect partition [Lyapunov, 1940] of the cake such that That only cuts the cake at points [Alon, 1987] Black box to design SP-in-expectation + EF mechanism Assign the bundles to EF: Every agent values every bundle at SP-in-expectation: Agent is assigned a random bundle, expected utility is , irrespective of report

16 Fair Division of Indivisible Goods Resources: Set of indivisible goods Allocation: , a partition of some Valuations: EF allocation may not exist No Equal treatment of equals 17

Approximate Envy-Freeness Envy-free up to any (one) good (EFX): [Caragiannis et al. 2016] Envy is eliminated by removing any one good allocated to the envied agent Envy is eliminated by removing the least valued good allocated to the envied agent Existence unknown (See [Plaut & Roughgarden, 2018]) Envy-freeness up to one good (EF1): For every pair of agents , there exists a good such that may envy , but the envy can be eliminated by removing a single good from s bundle (or )

18 Round Robin Algorithm Fix order of agents Proceed in rounds: In each round , agent mod picks her favorite remaining item Envy-free up to the items selected in round 1 Not PO 19

Greedy Algorithm [Lipton et al., 2004] One by one: Allocate a good to an agent no one envies While there is an envy cycle: Pick a cycle Pass allocations along the cycle Ends in polynomial number of steps No change in edges involving agents outside cycle Possibly fewer outward edges from agents in the cycle Strictly fewer edges between agents in the cycle

20 Greedy algorithm is EF1 EF1: By remove the most recently added good from envied agent Bounded (by maximum marginal value) envy: Let denote (partial) allocation at round At any round , Suppose envy graph was acyclic in rounds Allocate to a source agent in the envy graph For every Eliminate any cycles at round

Not PO 21 Maximum Nash Welfare: EF1 + PO [Caragiannis et al., 2016] PO is easy to see EF1: By removing the most valued good from every agents bundle Up to which good? (Sketch) Any [Conitzer et al., 2019] A is MNW

Some algebra later: Let Sum over all , 22 More EF1 + PO [Barman et al., EC 2018]: Pseudo-polynomial time algorithm using Fisher markets [Barman et al., AAMAS 2018]: Polynomial time algorithm for MNW allocation for binary valuations

23 Envy Freeness through Information Withholding [Hosseini et al., 2019] Envy-freeness with hidden goods (HEF-): is envy-free up to hidden goods (HEF-) if there exists a set of at most goods such that for every pair of agents : Envy-free up to uniformly hidden goods (uHEF-) if for every agent : Satisfied by Round Robin, Envy Graph, MNW What is the smallest number of goods which must be hidden?

HEF--Verification: Given an allocation, can we eliminate envy by hiding at most goods? HEF--Existence: Does an HEF- allocation exist? 24 HEF in practice: Non-EF instances Binary valuations generate using a biased () coin See [Dickerson et al., 2014, Manurangsi & Suksompong, 2018] 25

HEF in practice: # hidden goods; worst-case Binary valuations generate using a biased () coin 26 HEF: Computatability HEF--Existence NP-complete even for identical valuations Reduction from Partition problem EF-Existence is NP-complete even for binary valuations Therefore HEF--Existence is NP-complete for

NP-hard to check if instance admits HEF- + PO allocation HEF--Verification NP-hard to approximate to within , even for binary valuations, where is aggregate envy Reduction from Hitting Set Standard greedy submodular maximization algorithm 27 Various EF1 Algorithms in Practice On data from Spliddit [Goldman & Procaccia, 2014] 28

(Approximately) Equitable Allocations Equitability up to one good (EQ1): For every pair there exists a good such that: Equitability up to any good (EQX): For every pair Always exists [Gourves et al., 2014] [Freeman et al., 2019]: EQ1+PO NP-hard to determine existence EQ1+EF1+PO in polynomial time for binary valuations whenever it exists 29

Proportionality up to One Good Proportionality up to one good (Prop1): for every , there exists a good , such that [Conitzer et al. 2017] Any algorithm which is EF1+PO is also Prop1+PO Can be computed in polynomial time [Barman & Krishnamoorthy, 2019] 30 Randomized Algorithms (for now)

Random Priority (RP) Order agents uniformly at random Each agent picks favorite remaining item in turn Probability share of item is probability with which it is consumed Probabilistic Serial (PS) [Bogomolnaia & Moulin, 2001] In rounds, Every agent eats their favorite remaining item simultaneously at a constant, uniform rate Probability shares equal to the fraction of item eaten Equal treatment of equals

31 Fair, Efficient, and Strategyproof Assignments? Assignment is a doubly stochastic matrix Row is -vector of agents allocation Stochastic dominance (sd) stochastically dominates if at every good , RSD is weak-sd-EF + sd-SP + ex-post PO

PS is sd-efficient, sd-EF, weak sd-SP 32 Acknowledgements These slides borrow heavily from: Tutorial on fair division by Nisarg Shah and Rupert Freeman, EC-19 http://www.cs.toronto.edu/~nisarg/papers/Fair-Division-Tutorial.pdf Lectures by Nisarg Shah http://www.cs.toronto.edu/~nisarg/teaching/2556s19/slides/2556s19-L6.pdf Lectures by Ariel Procaccia and Alex Psomas

http://www.cs.cmu.edu/~15896/slides/896f18-1.pdf http://www.cs.cmu.edu/~15896/slides/896f18-2.pdf http://www.cs.cmu.edu/~15896/slides/896f18-5.pdf Lectures by Lirong Xia No public link Lecture series on Fair Division https://www.youtube.com/watch?v=NQf_RqmJ9p8 and more 33