Arrow Research search

Author name cluster

Guido Schäfer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

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.

PDF Details DOI

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.

PDF

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.

Details

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.

Details