3 papers
cs.GT2026
Algorithms for Robbins' Problem using Markov Decision Processes
Léonard Brice, F. Thomas Bruss, Anirban Majumdar +1
In this paper, we consider Robbins' problem, which is a full information variant of the well-known secretary selection problem. In this version of the problem, the goal is to minim…
cs.GT2024
Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents
Léonard Brice, Jean-François Raskin, Mathieu Sassolas +2
Fairness is a desirable and crucial property of many protocols that handle, for instance, exchanges of message. It states that if at least one agent engaging in the protocol is hon…
cs.GT2022
The Complexity of SPEs in Mean-payoff Games
Léonard Brice, Jean-François Raskin, Marie van den Bogaard
We establish that the subgame perfect equilibrium (SPE) threshold problem for mean-payoff games is NP-complete. While the SPE threshold problem was recently shown to be decidable (…