@misc{BorndoerferHoang2008, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Fair Ticket Prices in Public Transport}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10999}, number = {08-46}, year = {2008}, abstract = {Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.}, language = {en} } @article{BorndoerferHoang2014, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Fair ticket pricing in public transport as a constrained cost allocation game}, volume = {226}, journal = {Annals of Operations Research}, doi = {10.1007/s10479-014-1698-z}, pages = {51 -- 68}, year = {2014}, abstract = {Ticket pricing in public transport usually takes a welfare maximization point of view. Such an approach, however, does not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and linear and integer programming. The ticket pricing problem is considered to be a constrained cost allocation game, which is a generalization of cost allocation games that allows to deal with constraints on output prices and on the formation of coalitions. An application to pricing railway tickets for the intercity network of the Netherlands is presented. The results demonstrate that the fairness of prices can be improved substantially in this way. A preliminary version of this paper appeared in the Proceedings of HPSC 2009 (Bornd{\"o}rfer and Hoang 2012). This journal article introduces better model and algorithms.}, language = {en} } @article{BlancoBorndoerferBrueckneretal.2015, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Br{\"u}ckner, Michael and Hoang, Nam-Dung and Schlechte, Thomas}, title = {On the Path Avoiding Forbidden Pairs Polytope}, volume = {50}, journal = {Electronic Notes in Discrete Mathematics}, doi = {10.1016/j.endm.2015.07.057}, pages = {343 -- 348}, year = {2015}, abstract = {Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.}, language = {en} }