Back to activities
GERAD seminar

Integer programming formulations for the k-way (strongly) stable exchange problem


Jan 24, 2019   03:00 PM — 04:00 PM

Ana Viana INESC TEC, Polytechnic of Porto, Portugal

Barter exchange markets can be represented as directed graphs where agents are vertices and arcs indicate exchange opportunities. A solution consists of a set of disjoint cycles and an exchange that contains no cycle with length more than k is a k-way exchange.

In this work we consider the case where agents have preferences, represented by ranks on the outgoing arcs of the graph, and search for a k-way (strongly) stable exchange. An exchange is called stable if there is no blocking cycle where all the agents involved strictly prefer the new solution. It is strongly stable if no weakly blocking cycle exists, where at least one agent improves and neither of them gets a worse allocation. The problem of deciding existence is NP-hard for both problems.

We present three novel integer programming formulations for the above mentioned problems, which is a novel approach for this solution concept.

Joint work with X. Klimentova, P. Biró, V. Costa and J. P. Pedroso

Free entrance.
Welcome to everyone!

Andrea Lodi organizer


Room 4488
André-Aisenstadt Building
Université de Montréal Campus
2920, chemin de la Tour
Montréal QC H3T 1J4

Associated organization

Research Axes

Research application