BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

David Manlove

David Manlove contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputer Science and Game TheoryArtificial IntelligenceLogic in Computer Science

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2020arXiv

A 3/2-approximation algorithm for the Student-Project Allocation problem

The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) comprises three sets of agents, namely students, projects and lecturers, where students have preferences over projects and lecturers have preferences over students. In this scenario we seek a stable matching, that is, an assignment of students to projects such that there is no student and lecturer who have an incentive to deviate from their assignee/s. We study SPA-ST, the extension of SPA-S in which the preference lists of students and lecturers need not be strictly ordered, and may contain ties. In this scenario, stable matchings may be of different sizes, and it is known that MAX SPA-ST, the problem of finding a maximum stable matching in SPA-ST, is NP-hard. We present a linear-time 3/2-approximation algorithm for MAX SPA-ST and an Integer Programming (IP) model to solve MAX SPA-ST optimally. We compare the approximation algorithm with the IP model experimentally using randomly-generated data. We find that the performance of the approximation algorithm easily surpassed the 3/2 bound, constructing a stable matching within 92% of optimal in all cases, with the percentage being far higher for many instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A General Framework for Stable Roommates Problems using Answer Set Programming

The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are motivated by applications (e.g., the preference lists may be incomplete (SRI) and involve ties (SRTI)), and that try to find a more fair solution (e.g., Egalitarian SR). Unlike the Stable Marriage problem, every SR instance is not guaranteed to have a solution. For that reason, there are also variations of SR that try to find a good-enough solution (e.g., Almost SR). Most of these variations are NP-hard. We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set Programming, that is provable and general enough to solve many of such variations of SR. Our empirical analysis shows that SRTI-ASP is also promising for applications. This paper is under consideration for acceptance in TPLP.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algorithms for new types of fair stable matchings

We study the problem of finding "fair" stable matchings in the Stable Marriage problem with Incomplete lists (SMI). For an instance $I$ of SMI there may be many stable matchings, providing significantly different outcomes for the sets of men and women. We introduce two new notions of fairness in SMI. Firstly, a regret-equal stable matching minimises the difference in ranks of a worst-off man and a worst-off woman, among all stable matchings. Secondly, a min-regret sum stable matching minimises the sum of ranks of a worst-off man and a worst-off woman, among all stable matchings. We present two new efficient algorithms to find stable matchings of these types. Firstly, the Regret-Equal Degree Iteration Algorithm finds a regret-equal stable matching in $O(d_0 nm)$ time, where $d_0$ is the absolute difference in ranks between a worst-off man and a worst-off woman in the man-optimal stable matching, $n$ is the number of men or women, and $m$ is the total length of all preference lists. Secondly, the Min-Regret Sum Algorithm finds a min-regret sum stable matching in $O(d_s m)$ time, where $d_s$ is the difference in the ranks between a worst-off man in each of the woman-optimal and man-optimal stable matchings. Experiments to compare several types of fair optimal stable matchings were conducted and show that the Regret-Equal Degree Iteration Algorithm produces matchings that are competitive with respect to other fairness objectives. On the other hand, existing types of "fair" stable matchings did not provide as close an approximation to regret-equal stable matchings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Super-stability in the Student-Project Allocation Problem with Ties

The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) involves assigning students to projects based on student preferences over projects, lecturer preferences over students, and the maximum number of students that each project and lecturer can accommodate. This classical model assumes that each project is offered by one lecturer and that preference lists are strictly ordered. Here, we study a generalisation of SPA-S where ties are allowed in the preference lists of students and lecturers, which we refer to as the Student-Project Allocation problem with lecturer preferences over Students with Ties (SPA-ST). We investigate stable matchings under the most robust definition of stability in this context, namely super-stability. We describe the first polynomial-time algorithm to find a super-stable matching or to report that no such matching exists, given an instance of SPA-ST. Our algorithm runs in $O(L)$ time, where $L$ is the total length of all the preference lists. Finally, we present results obtained from an empirical evaluation of the linear-time algorithm based on randomly-generated SPA-ST instances. Our main finding is that, whilst super-stable matchings can be elusive when ties are present in the students' and lecturers' preference lists, the probability of such a matching existing is significantly higher if ties are restricted to the lecturers' preference lists.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Two-sided profile-based optimality in the stable marriage problem

We study the problem of finding "fair" stable matchings in the Stable Marriage problem with Incomplete lists (SMI). In particular, we seek stable matchings that are optimal with respect to profile, which is a vector that indicates the number of agents who have their first-, second-, third-choice partner, etc. In a rank maximal stable matching, the maximum number of agents have their first-choice partner, and subject to this, the maximum number of agents have their second-choice partner, etc., whilst in a generous stable matching $M$, the minimum number of agents have their $d$th-choice partner, and subject to this, the minimum number of agents have their $(d-1)$th-choice partner, etc., where $d$ is the maximum rank of an agent's partner in $M$. Irving et al. [18] presented an $O(nm^2\log n)$ algorithm for finding a rank-maximal stable matching, which can be adapted easily to the generous stable matching case, where $n$ is the number of men / women and $m$ is the number of acceptable man-woman pairs. An $O(n^{0.5}m^{1.5})$ algorithm for the rank-maximal stable matching problem was later given by Feder [7]. However these approaches involve the use of weights that are in general exponential in $n$. In this paper we present an $O(nm^2\log n)$ algorithm for finding a rank-maximal stable matching using a vector-based approach that involves weights that are polynomially-bounded in $n$. We conduct an empirical evaluation, and show how this approach has a far reduced memory requirement (an estimated $100$-fold improvement for instances with $100, 000$ men or women) when compared to Irving et al.'s algorithm above. Additionally, we show how to adapt our algorithm for the generous case. Finally, we examine the complexity of the problem of finding profile-based optimal stable matchings in the Stable Roommates problem (SR).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Preference Elicitation in Matching Markets via Interviews: A Study of Offline Benchmarks

The stable marriage problem and its extensions have been extensively studied, with much of the work in the literature assuming that agents fully know their own preferences over alternatives. This assumption however is not always practical (especially in large markets) and agents usually need to go through some costly deliberation process in order to learn their preferences. In this paper we assume that such deliberations are carried out via interviews, where an interview involves a man and a woman, each of whom learns information about the other as a consequence. If everybody interviews everyone else, then clearly agents can fully learn their preferences. But interviews are costly, and we may wish to minimize their use. It is often the case, especially in practical settings, that due to correlation between agents' preferences, it is unnecessary for all potential interviews to be carried out in order to obtain a stable matching. Thus the problem is to find a good strategy for interviews to be carried out in order to minimize their use, whilst leading to a stable matching. One way to evaluate the performance of an interview strategy is to compare it against a naive algorithm that conducts all interviews. We argue however that a more meaningful comparison would be against an optimal offline algorithm that has access to agents' preference orderings under complete information. We show that, unless P=NP, no offline algorithm can compute the optimal interview strategy in polynomial time. If we are additionally aiming for a particular stable matching (perhaps one with certain desirable properties), we provide restricted settings under which efficient optimal offline algorithms exist.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Pareto Optimal Matchings in Many-to-Many Markets with Ties

We consider Pareto-optimal matchings (POMs) in a many-to-many market of applicants and courses where applicants have preferences, which may include ties, over individual courses and lexicographic preferences over sets of courses. Since this is the most general setting examined so far in the literature, our work unifies and generalizes several known results. Specifically, we characterize POMs and introduce the \emph{Generalized Serial Dictatorship Mechanism with Ties (GSDT)} that effectively handles ties via properties of network flows. We show that GSDT can generate all POMs using different priority orderings over the applicants, but it satisfies truthfulness only for certain such orderings. This shortcoming is not specific to our mechanism; we show that any mechanism generating all POMs in our setting is prone to strategic manipulation. This is in contrast to the one-to-one case (with or without ties), for which truthful mechanisms generating all POMs do exist.

0 citations0 reviewsNo code linkedOpen access