5 papers
Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online
Georgios Amanatidis, Pieter Kleer, Guido Schäfer
The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constra…
Comparing the Switch and Curveball Markov Chains for Sampling Binary Matrices with Fixed Marginals
Corrie Jacobien Carstens, Pieter Kleer
The Curveball algorithm is a variation on well-known switch-based Markov chain approaches for uniformly sampling binary matrices with fixed row and column sums. Instead of a switch…
Path deviations outperform approximate stability in heterogeneous congestion games
Pieter Kleer, Guido Schäfer
We consider non-atomic network congestion games with heterogeneous players where the latencies of the paths are subject to some bounded deviations. This model encompasses several w…
Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games
Pieter Kleer, Guido Schäfer
Congestion games constitute an important class of non-cooperative games which was introduced by Rosenthal in 1973. In recent years, several extensions of these games were proposed…
The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games
Pieter Kleer, Guido Schäfer
We introduce a unifying model to study the impact of worst-case latency deviations in non-atomic selfish routing games. In our model, latencies are subject to (bounded) deviations…