BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Guido Schäfer

Guido Schäfer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2022arXiv

Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents

We consider budget feasible mechanisms for procurement auctions with additive valuation functions. For the divisible case, where agents can be allocated fractionally, there exists an optimal mechanism with approximation guarantee $e/(e-1)$ under the small bidder assumption. We study the divisible case without the small bidder assumption, but assume that the true costs of the agents are bounded by the budget. This setting lends itself to modeling economic situations in which the goods represent time and the agents' true costs are not necessarily small compared to the budget. Non-trivially, we give a mechanism with an approximation guarantee of 2.62, improving the result of 3 for the indivisible case. Additionally, we give a lower bound on the approximation guarantee of 1.25. We then study the problem in more competitive markets and assume that the agents' value over cost efficiencies are bounded by some $θ\ge 1$. For $θ\le 2$, we give a mechanism with an approximation guarantee of 2 and a lower bound of 1.18. Both results can be extended to settings with different agent types with a linear capped valuation function for each type. Finally, if each agent type has a concave valuation, we give a mechanism for which the approximation guarantee grows linearly with the number of agent types.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

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

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Inefficiency of Standard Multi-Unit Auctions

We study two standard multi-unit auction formats for allocating multiple units of a single good to multi-demand bidders. The first one is the Discriminatory Auction, which charges every winner his winning bids. The second is the Uniform Price Auction, which determines a uniform price to be paid per unit. Variants of both formats find applications ranging from the allocation of state bonds to investors, to online sales over the internet, facilitated by popular online brokers. For these formats, we consider two bidding interfaces: (i) standard bidding, which is most prevalent in the scientific literature, and (ii) uniform bidding, which is more popular in practice. In this work, we evaluate the economic inefficiency of both multi-unit auction formats for both bidding interfaces, by means of upper and lower bounds on the Price of Anarchy for pure Nash equilibria and mixed Bayes-Nash equilibria. Our developments improve significantly upon bounds that have been obtained recently in [Markakis, Telelis, ToCS 2014] and [Syrgkanis, Tardos, STOC 2013] for submodular valuation functions. Moreover, we consider for the first time bidders with subadditive valuation functions for these auction formats. Our results signify that these auctions are nearly efficient, which provides further justification for their use in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games

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 which are taken into account by the players. The quality deterioration caused by such deviations is assessed by the $\textit{Deviation Ratio}$, i.e., the worst-case ratio of the cost of a Nash flow with respect to deviated latencies and the cost of a Nash flow with respect to the unaltered latencies. This notion is inspired by the $\textit{Price of Risk Aversion}$ recently studied by Nikolova and Stier-Moses. Here we generalize their model and results. In particular, we derive tight bounds on the Deviation Ratio for multi-commodity instances with a common source and arbitrary non-negative and non-decreasing latency functions. These bounds exhibit a linear dependency on the size of the network (besides other parameters). In contrast, we show that for general multi-commodity networks an exponential dependency is inevitable. We also improve recent smoothness results to bound the Price of Risk Aversion.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Efficient Equilibria in Polymatrix Coordination Games

We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study $α$-approximate $k$-equilibria of these games, i.e., outcomes where no group of at most $k$ players can deviate such that each member increases his payoff by at least a factor $α$. We prove that for $α\ge 2$ these games have the finite coalitional improvement property (and thus $α$-approximate $k$-equilibria exist), while for $α< 2$ this property does not hold. Further, we derive an almost tight bound of $2α(n-1)/(k-1)$ on the price of anarchy, where $n$ is the number of players; in particular, it scales from unbounded for pure Nash equilibria ($k = 1)$ to $2α$ for strong equilibria ($k = n$). We also settle the complexity of several problems related to the verification and existence of these equilibria. Finally, we investigate natural means to reduce the inefficiency of Nash equilibria. Most promisingly, we show that by fixing the strategies of $k$ players the price of anarchy can be reduced to $n/k$ (and this bound is tight).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Bounding the Inefficiency of Altruism Through Social Contribution Games

We introduce a new class of games, called social contribution games (SCGs), where each player&#39;s individual cost is equal to the cost he induces on society because of his presence. Our results reveal that SCGs constitute useful abstractions of altruistic games when it comes to the analysis of the robust price of anarchy. We first show that SCGs are altruism-independently smooth, i.e., the robust price of anarchy of these games remains the same under arbitrary altruistic extensions. We then devise a general reduction technique that enables us to reduce the problem of establishing smoothness for an altruistic extension of a base game to a corresponding SCG. Our reduction applies whenever the base game relates to a canonical SCG by satisfying a simple social contribution boundedness property. As it turns out, several well-known games satisfy this property and are thus amenable to our reduction technique. Examples include min-sum scheduling games, congestion games, second price auctions and valid utility games. Using our technique, we derive mostly tight bounds on the robust price of anarchy of their altruistic extensions. For the majority of the mentioned game classes, the results extend to the more differentiated friendship setting. As we show, our reduction technique covers this model if the base game satisfies three additional natural properties.

0 citations0 reviewsNo code linkedOpen access