Krzysztof Rogowski

kr418382@mimuw.edu.pl

Room 5020

ul. Banacha 2,

02-097 Warsaw, Poland

I am a PhD student at the University of Warsaw, Faculty of Mathematics, Informatics and Mechanics. My supervisor is Marcin Dziubiński, and I am part of the AI and Economics research group.

I study facility location problems through the lens of mechanism design. My current research focuses on the approximation guarantees of randomized, strategyproof mechanisms on graphs with cycles.

I enjoy coding and always look for opportunities to learn yet another computer-based tool or framework. Currently those include mostly Python’s math libraries, LP solvers, and LaTeX alternatives. Some years back, I spent a lot of time on web development, building hobby projects such as online platforms for playing Neuroshima Hex (polish board game) or website for learning languages. Although I no longer code websites as often, I try to stay in the loop by teaching the subject to students.

selected publications

IJCAI
Improved Approximation Ratio for Strategyproof Facility Location on a Cycle

Krzysztof Rogowski and Marcin Dziubiński

In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25, Aug 2025

Main Track

Abs DOI arXiv Bib HTML PDF

We study the problem of design of strategyproof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of n agents. We show that there exists an SP mechanism that attains an approximation ratio of 7/4 with respect to the sum of costs of the agents, thus improving the best known upper bound of 2-2/n in the cases of n≥5. The mechanism obtaining the bound randomizes between two mechanisms known in the literature: the Random Dictator (RD) and the Proportional Circle Distance (PCD) mechanism of Meir (2019). To prove the result, we propose a cycle-cutting technique that allows for estimating the problem on a cycle by a problem on a line.
@inproceedings{rogowski2025, title = {Improved Approximation Ratio for Strategyproof Facility Location on a Cycle}, author = {Rogowski, Krzysztof and Dziubiński, Marcin}, booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, {IJCAI-25}}, publisher = {International Joint Conferences on Artificial Intelligence Organization}, editor = {Kwok, James}, pages = {4032--4039}, year = {2025}, month = aug, note = {Main Track}, doi = {10.24963/ijcai.2025/449}, url = {https://doi.org/10.24963/ijcai.2025/449}, }