Guido Schäfer

AAAI Conference 2026 Conference Paper

Breaking Barriers, Finding Boundaries: Not Obviously Manipulable Budget-Feasible Mechanism Design

• Bart De Keijzer
• Guido Schäfer
• Artem Tsikiridis
• Carmine Ventre

Strategyproofness has been the holy grail in mechanism design for decades, providing strong incentive compatibility guarantees under the assumption of perfectly rational agents. However, this assumption is questionable when agents exhibit bounded rationality. Moreover, strategyproofness often imposes strong impossibility results that prevent mechanisms from surpassing certain approximation barriers. We study this tension in budget-feasible mechanism design, where a designer wants to procure services of maximum value from agents subject to a budget constraint. Here, strategyproofness imposes approximation barriers of 2.41 and 2 for deterministic and randomized mechanisms, respectively. We investigate how much we can potentially gain under bounded rationality. We adopt the weaker notion of not obviously manipulable (NOM), which only prevents "obvious" strategic deviations. We fully resolve the achievable approximation guarantees under NOM: We derive a deterministic 2-approximate NOM mechanism under the general class of monotone subadditive valuations. We also show that this bound is tight (even for additive valuations). Additionally, we provide a simple randomized NOM mechanism that is approximately optimal. These results demonstrate a clear separation between strategyproof and NOM mechanisms. Our mechanisms use Golden Tickets and Wooden Spoons as natural design primitives, arising from our characterization of NOM mechanisms.

AAMAS Conference 2022 Conference Paper

Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions

• Andries van Beek
• Ruben Brokkelkamp
• Guido Schäfer

We initiate the study of the social welfare loss caused by corrupt auctioneers, both in single-item and multi-unit auctions. In our model, the auctioneer may collude with the winning bidders by letting them lower their bids in exchange for a (possibly bidder-dependent) fraction 𝛾 of the surplus. We consider different corruption schemes. In the most basic one, all winning bidders lower their bid to the highest losing bid. We show that this setting is equivalent to a 𝛾-hybrid auction in which the payments are a convex combination of first-price and the second-price payments. More generally, we consider corruption schemes that can be related to 𝛾-approximate first-price auctions (𝛾-FPA), where the payments recover at least a 𝛾-fraction of the first-price payments. Our goal is to obtain a precise understanding of the robust price of anarchy (POA) of such auctions. If no restrictions are imposed on the bids, we prove a bound on the robust POA of 𝛾-FPA which is tight (over the entire range of 𝛾) for the single-item and the multi-unit auction setting. On the other hand, if the bids satisfy the no-overbidding assumption a more fine-grained landscape of the price of anarchy emerges, depending on the auction setting and the equilibrium notion. Albeit being more challenging, we derive (almost) tight bounds for both auction settings and several equilibrium notions, basically leaving open some (small) gaps for the coarse-correlated price of anarchy only.

TCS Journal 2019 Journal Article

Tight inefficiency bounds for perception-parameterized affine congestion games

• Pieter Kleer
• Guido Schäfer

We introduce a new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ ≥ 0, while the system designer estimates that each player perceives the load of all others by an extent of σ ≥ 0. For specific choices of ρ and σ, we obtain extensions such as altruistic player behavior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ = 0. 625 (instead of 1 in the standard setting) the price of anarchy reduces from 2. 5 to 2. 155 and this is best possible.

MFCS Conference 2016 Conference Paper

The Ground-Set-Cost Budgeted Maximum Coverage Problem

• Irving van Heuven van Staereling
• Bart de Keijzer
• Guido Schäfer

We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph G = (V, E), where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set of hyperedges T subseteq E such that the total cost of the vertices covered by T is at most B and the total profit of all covered vertices is maximized. Besides being a natural generalization of the well-studied maximum coverage problem, our motivation for investigating this problem originates from its application in the context of bid optimization in sponsored search auctions, such as Google AdWords. It is easily seen that this problem is strictly harder than budgeted max coverage, which means that the problem is (1-1/e)-inapproximable. The difference of our problem to the budgeted maximum coverage problem is that the costs are associated with the covered vertices instead of the selected hyperedges. As it turns out, this difference refutes the applicability of standard greedy approaches which are used to obtain constant factor approximation algorithms for several other variants of the maximum coverage problem. Our main results are as follows: - We obtain a (1 - 1/sqrt(e))/2-approximation algorithm for graphs. - We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i. e. , the hypergraph is Berge-acyclic). We also extend this result to incidence graphs with a fixed-size feedback hyperedge node set. - We give a (1-epsilon)/(2d^2)-approximation algorithm for every epsilon > 0, where d is the maximum degree of a vertex in the hypergraph.

SODA Conference 2008 Conference Paper

Approximating connected facility location problems via random facility sampling and core detouring

• Friedrich Eisenbrand
• Fabrizio Grandoni 0001
• Thomas Rothvoss
• Guido Schäfer

TCS Journal 2008 Journal Article

Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems

• Janina Brenner
• Guido Schäfer

Classical results in economics show that no truthful mechanism can achieve budget balance and efficiency simultaneously. Roughgarden and Sundararajan recently proposed an alternative efficiency measure, which was subsequently used to exhibit that many previously known cost sharing mechanisms approximate both budget balance and efficiency. In this work, we investigate cost sharing mechanisms for combinatorial optimization problems using this novel efficiency measure, with a particular focus on scheduling problems. Our contribution is threefold: First, for a large class of optimization problems that satisfy a certain cost-stability property, we prove that no budget balanced Moulin mechanism can approximate efficiency better than Ω ( log n ), where n denotes the number of players in the universe. Second, we present a group-strategyproof cost sharing mechanism for the minimum makespan scheduling problem that is tight with respect to budget balance and efficiency. Finally, we show a general lower bound on the budget balance factor for cost sharing methods, which can be used to prove a lower bound of Ω ( n ) on the budget balance factor for completion and flow time scheduling objectives.

SODA Conference 2007 Conference Paper

An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem

• Anupam Gupta 0001
• Jochen Könemann
• Stefano Leonardi 0001
• R. Ravi 0001
• Guido Schäfer

STOC Conference 2006 Conference Paper

Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree

• Lisa Fleischer
• Jochen Könemann
• Stefano Leonardi 0001
• Guido Schäfer

SODA Conference 2005 Conference Paper

A group-strategyproof mechanism for Steiner forests

• Jochen Könemann
• Stefano Leonardi 0001
• Guido Schäfer

TCS Journal 2005 Journal Article

Topology matters: Smoothed competitiveness of metrical task systems

• Guido Schäfer
• Naveen Sivadasan

Borodin et al. (J. ACM 39 (1992) 745) introduced metrical task systems, a framework to model a large class of online problems. Metrical task systems can be described as follows. We are given a graph G = ( V, E ) with n nodes and a positive edge length λ ( e ) for every edge e ∈ E. An online algorithm resides in G and has to service a sequence of tasks that arrive online. A task τ specifies for each node v ∈ V a request cost r ( v ) ∈ R 0 + ∪ { ∞ }. If the algorithm resides in node u before the arrival of task τ, the cost to service task τ in node v is equal to the shortest path distance from u to v plus the request cost r ( v ). The objective is to service all tasks at minimum total cost. Borodin et al. showed that every deterministic online algorithm has a competitive ratio of at least 2 n - 1, independent of the underlying metric. Moreover, they presented an online work function algorithm (WFA) that achieves this competitive ratio. We present a smoothed competitive analysis of WFA. That is, given an adversarial task sequence, we randomly perturb the request costs and analyze the competitive ratio of WFA on the perturbed sequence. Here, we are mainly interested in the asymptotic behavior of WFA. Our analysis reveals that the smoothed competitive ratio of WFA is much better than O ( n ) and that it depends on several topological parameters of the underlying graph G, such as the minimum edge length λ min, the maximum degree Δ, the edge diameter e max, etc. For example, if the ratio between the maximum and the minimum edge length of G is bounded by a constant, the smoothed competitive ratio of WFA is O ( e max ( λ min / σ + log ( Δ ) ) ) and O ( n · ( λ min / σ + log ( Δ ) ) ), where σ denotes the standard deviation of the smoothing distribution. That is, already for perturbations with σ = Θ ( λ min ) the competitive ratio reduces to O ( log ( n ) ) on a clique and to O ( n ) on a line. Furthermore, we provide lower bounds on the smoothed competitive ratio of any deterministic algorithm. We prove two general lower bounds that hold independently of the underlying metric. Moreover, we show that our upper bounds are asymptotically tight for a large class of graphs. We also provide the first average case analysis of WFA. We prove that WFA has O ( log ( Δ ) ) expected competitive ratio if the request costs are chosen randomly from an arbitrary non-increasing distribution with standard deviation σ = Θ ( λ min ).

TCS Journal 2004 Journal Article

Cross-monotonic cost sharing methods for connected facility location games

• Stefano Leonardi
• Guido Schäfer

We present cost sharing methods for connected facility location games that are cross-monotonic and competitive and that recover a constant fraction of the cost of the constructed solution. The novelty of this paper is that we use randomized algorithms and that we share the expected cost among the participating users. As a consequence, our cost sharing methods are simple and achieve attractive approximation ratios. We also provide a primal-dual cost sharing method for the connected facility location game with opening costs.

FOCS Conference 2003 Conference Paper

Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm

• Luca Becchetti
• Stefano Leonardi 0001
• Alberto Marchetti-Spaccamela
• Guido Schäfer
• Tjark Vredeveld

In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng (2001) to explain the behavior of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2/sup K/] We use a partial bit randomization model, where the initial processing times are smoothened by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2/sup k///spl sigma/)/sup 3/ + (2/sup k///spl sigma/)/sup 2/2/sup K-k/), where /spl sigma/ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of O(2/sup K-k/) if /spl sigma/ = /spl Theta/(2/sup k/). We also prove an /spl Omega/(2/sup K-k/) lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, we give a higher lower bound of /spl Omega/(2/sup K/). A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.