nep-des New Economics Papers
on Economic Design
Issue of 2021‒03‒29
two papers chosen by
Alex Teytelboym
University of Oxford

  1. Stable matching: An integer programming approach By Chao Huang
  2. Two-Person Fair Division of Indivisible Items when Envy-Freeness Is Impossible By Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian

  1. By: Chao Huang
    Abstract: This paper develops an integer programming approach on two-sided many-to-one matching by investigating stable integral matchings of a fictitious continuum market induced from the original matching market. Each stable integral matching of the continuum market corresponds to a stable matching of the original matching market. We show that a stable matching exists in the original matching market when firms' preference profile satisfies a unimodularity condition. Our result indicates that a stable matching is guaranteed to exist with various forms of complementary preferences.
    Date: 2021–03
  2. By: Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian
    Abstract: Assume two players, A and B, must divide a set of indivisible items that each strictly ranks from best to worst. If the number of items is even, assume that the players desire that the allocations be balanced (each player gets half the items), item-wise envy-free (EF), and Pareto-optimal (PO). Meeting this ideal is frequently impossible. If so, we find a balanced maximal partial allocation of items to the players that is EF, though it may not be PO. Then we show how to augment it in a way that makes it a complete allocation that is EF for one player (say, A) and almost-EF for the other player (B) in the sense that it is EF for B except for one item – it would be EF for B if a specific item assigned to A were removed. Moreover, we show how low-ranked that exceptional item can be for B, thereby finding an almost-EF allocation that is as close as possible to EF – as well as complete, balanced, and PO. We provide algorithms to find such almost-EF allocations, adapted from algorithms that apply when complete balanced EF-PO allocations are possible.
    Keywords: 2-person fair division, indivisible items, envy-freeness up to one item, Pareto-optimality
    JEL: C61 C72 D63
    Date: 2021–03

This nep-des issue is ©2021 by Alex Teytelboym. It is provided as is without any express or implied warranty. It may be freely redistributed in whole or in part for any purpose. If distributed in part, please include this notice.
General information on the NEP project can be found at For comments please write to the director of NEP, Marco Novarese at <>. Put “NEP” in the subject, otherwise your mail may be rejected.
NEP’s infrastructure is sponsored by the School of Economics and Finance of Massey University in New Zealand.