This website stores cookies on your computer. These cookies are used to collect information about how you interact with our website and allow us to remember your browser. We use this information to improve and customize your browsing experience, for analytics and metrics about our visitors both on this website and other media, and for marketing purposes. By using this website, you accept and agree to be bound by UVic’s Terms of Use and Protection of Privacy Policy. If you do not agree to the above, you must not use this website.

Skip to main content
People Departments Maps Buildings Rooms A-Z
University
of Victoria
Apply Library
Sign in Online tools Sign out
Faculty of Graduate Studies

Kevin Hsu

  • MSc (University of Victoria, 2020)

  • BSc Hons. (University of Victoria, 2018)

Notice of the Final Oral Examination for the Degree of Doctor of Philosophy

Topic

Fair Division of Indivisible Items

Department of Computer Science

Date & location

  • Tuesday, September 2, 2025

  • 11:00 A.M.

  • Engineering & Computer Science Building

  • Room 468

Reviewers

Supervisory Committee

  • Dr. Valerie King, Department of Computer Science, University of Victoria (Supervisor)

  • Dr. Yun Lu, Department of Computer Science, UVic (Member)

  • Dr. Jonathan Noel, Department of Mathematics and Statistics, UVic (Outside Member) 

External Examiner

  • Dr. Nisarg Shah, Department of Computer Science, University of Toronto 

Chair of Oral Examination

  • Dr. Mihai Sima, Department of Electrical and Computer Engineering, UVic

     

Abstract

We study the fair division of indivisible items. In the general model, the goal is to find a way to allocate  indivisible items to  agents, while satisfying some fairness criteria. We are particularly interested in the fairness criteria of maximin share (MMS), envyfreeness up to one item (EF1), and envy-freeness up to any item (EFX). Additionally, we study a recently-introduced graphical model that represents the fair division problem as a multigraph, in which vertices correspond to agents and edges correspond to items. The graphical model stipulates that an item can have non-zero marginal utility to an agent only if its corresponding edge is incident to the agent’s corresponding vertex, capturing the idea of proximity between agents and items. It is desirable to allocate edges only to their endpoints. Such allocations are called orientations, as they correspond naturally to graph orientations.

Our first contribution concerns MMS allocations of mixed manna (i.e. a mixture of goods and chores) in the general model. It is known that MMS allocations of goods exist when . We generalize this result by showing that when , MMS allocations of mixed manna exist as long as , there is an agent whose MMS threshold is non-negative, or every item is a chore. Remarkably, our result leaves only the case in which every agent has a negative MMS threshold unanswered.

Our second contribution concerns EFX orientations of multigraphs of goods. We show that deciding whether EFX orientations exist for multigraphs is NP-complete, even for symmetric and bi-valued multigraphs. Complementary to this, we show symmetric bivalued multigraphs that do not contain non-trivial odd multitrees have EFX orientations that can be found in polynomial time.

Our third contribution concerns EF1 and EFX orientations of graphs and multigraphs of chores. We obtain polynomial-time algorithms for deciding whether such graphs have EF1 and EFX orientations, resolving a previous conjecture and showing a fundamental difference between goods and chores division. In addition, we show that the analogous problems for multigraphs is NP-hard.

Back to oral exams