Ari | Last updated: Wed 6 Mar 2024 17:39:15 GMT

Algorithmic Foundations Of Collective Decision Making @ Oxford, Hilary 2024

Solutions To Tutorials

My Notes/Corrections (Use at your own peril )

These are some notes I made to assist with tutoring for Edith’s course. They are not endorsed by the university, and may have typos and errors.

Problem 5 Tutorial 4 Correction: The rule is not monotone as per the definitions of the class. This was the example I was given. All outputs have the same score, so it’s very unsatisfying because lots of ties.

Smallest example seems to have m = 4, n = 6,

P: ((2, 3, 1, 0), (3, 2, 1, 0), (0, 2, 3, 1), (1, 0, 3, 2), (0, 3, 1, 2), (1, 2, 0, 3))

Output: [(0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 3, 1, 0), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 1, 0) ]

Reinforcing 2 to get P': ((2, 3, 1, 0), (3, 2, 1, 0), (2, 0, 3, 1), (1, 0, 3, 2), (0, 3, 1, 2), (1, 2, 0, 3))

New Output: [(1, 2, 0, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 3, 1, 0), (3, 1, 2, 0) (3, 2, 1, 0) ]

Below 2 in output but not in new output: 1 look at the first element of output for lex tiebreak previously 2 beats 1, after strengthening it doesn’t.

Single Peakedness over Trees: There was some confusion about what it means to be single peaked on a tree for sheet 5. A good place to start is to read Pages 25-27 of Edith’s survey where there are nice pictures of what it means to be single peaked on a tree. Pictures are always good.