GERAD Seminar joint with the Canada Excellence Research Chair in Data Science for Real-Time Decision-Making

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

Speaker: 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!