In the field of auction theory, the Price of Anarchy (PoA) is a measure of the inefficiency that arises when self-interested agents participate in auctions. While previous literature on simple auctions has focused on the assumption of no-overbidding, recent empirical studies have highlighted the phenomenon of no-underbidding, where bidders refrain from bidding their true valuations for fear of overpaying. In this paper, authors Michal Feldman and Galia Shabtai provide a theoretical foundation for the no-underbidding phenomenon and study its impact on simultaneous 2nd price auctions (S2PA). The authors introduce a new natural condition called "no underbidding," which assumes that bidders never bid less than their marginal values. They establish improved bounds on the PoA of S2PA under this condition for various valuation classes, including unit-demand, submodular, XOS, subadditive, and general monotone valuations in both full-information and incomplete information settings. To derive their results, they introduce a new parameterized property of auctions called $(\gamma,\delta)$-revenue guaranteed, which guarantees a PoA of at least $\gamma/(1+\delta)$. This guarantee extends to coarse correlated equilibria (CCE) in full information settings and to Bayesian PoA (BPoA) in settings with incomplete information and arbitrary distributions. The authors show that S2PA are $(1,1)$-revenue guaranteed with respect to bids satisfying no underbidding. This implies a PoA of at least $1/2$ for general monotone valuation which extends to BPOA with arbitrary correlated distributions. Their findings have significant implications for the performance of S2PA relative to simultaneous 1st price auctions. The no underbidding assumption sheds new light on the inefficiencies that arise in auctions and provides a more accurate model for real-world scenarios. Overall, this paper contributes to our understanding of auction theory and provides valuable insights into the behavior of self-interested agents in auctions.
The Price of Anarchy (PoA) measures how inefficient auctions are when people bid for things they want. No-underbidding means that some people don't bid as much as they really want to because they're afraid of paying too much. Two authors, Michal Feldman and Galia Shabtai, studied this phenomenon in auctions where the second-highest bidder wins. They found that if bidders never bid less than what something is worth to them, the auction works better. They also found ways to make these auctions work even better for different types of things people might want to buy. This research helps us understand how auctions work in real life and how we can make them work better.
Definitions
- Price of Anarchy (PoA): a measure of inefficiency in auctions with self-interested agents
- No-underbidding: when bidders refrain from bidding their true valuations for fear of overpaying
- Simultaneous 2nd price auctions (S2PA): an auction where the second-highest bidder wins
- Marginal values: the value a person places on one additional unit or item
- Valuation classes: different types of things people might want to buy with different rules for how much they're worth
- Full-information and incomplete information settings: whether everyone knows everything about the thing being sold or not
- $(\gamma,\delta)$-revenue guaranteed: a parameterized property of auctions used to derive results guaranteeing a
Auction Theory and the Price of Anarchy: An Overview of Michal Feldman and Galia Shabtai's Research
In the field of auction theory, the Price of Anarchy (PoA) is a measure used to quantify the inefficiency that arises when self-interested agents participate in auctions. Previous literature on simple auctions has focused largely on the assumption of no-overbidding, where bidders refrain from bidding more than their true valuations for fear of overpaying. However, recent empirical studies have highlighted an additional phenomenon known as no-underbidding, where bidders may also refrain from bidding their true valuations out of fear of underpaying.
In this paper, authors Michal Feldman and Galia Shabtai provide a theoretical foundation for the no-underbidding phenomenon and study its impact on simultaneous 2nd price auctions (S2PA). Through their research, they introduce a new natural condition called "no underbidding," which assumes that bidders never bid less than their marginal values. They then establish improved bounds on the PoA for various valuation classes including unit-demand, submodular, XOS, subadditive and general monotone valuations in both full information and incomplete information settings.
The $(\gamma , \delta)$ Revenue Guarantee
To derive these results, Feldman and Shabtai introduce a new parameterized property called $(\gamma , \delta)$ revenue guaranteed which guarantees a PoA of at least $\frac{\gamma}{1+\delta}$. This guarantee extends to coarse correlated equilibria (CCE) in full information settings as well as Bayesian PoA (BPoA) in settings with incomplete information and arbitrary distributions. The authors show that S2PA are $(1 , 1)$ revenue guaranteed with respect to bids satisfying no underbidding; this implies a PoA of at least $1/2$ for general monotone valuation which extends to BPOA with arbitrary correlated distributions.
Implications For Auction Performance
The findings presented by Feldman and Shabtai have significant implications for our understanding of auction performance relative to simultaneous 1st price auctions. Their research sheds new light on the potential inefficiencies that arise when self-interested agents participate in auctions while providing valuable insights into how bidder behavior can affect outcomes within real world scenarios.
Overall, this paper contributes greatly to our understanding of auction theory by introducing novel concepts such as “no underbidding” along with parameters like $(\gamma , \delta )$ revenue guarantee which can be used to analyze auction performance more accurately than ever before.
The literature on the Price of Anarchy (PoA) of simple auctions employs a no-overbidding assumption but has completely overlooked the no-underbidding phenomenon, which is evident in empirical studies on variants of the second price auction. In this work, we provide a theoretical foundation for the no-underbidding phenomenon. We study the PoA of simultaneous 2nd price auctions (S2PA) under a new natural condition of {\em no underbidding}, meaning that agents never bid on items less than their marginal values. We establish improved (mostly tight) bounds on the PoA of S2PA under no underbidding for different valuation classes (including unit-demand, submodular, XOS, subadditive, and general monotone valuations), in both full-information and incomplete information settings. To derive our results, we introduce a new parameterized property of auctions, termed $(\gamma,\delta)$-revenue guaranteed, which implies a PoA of at least $\gamma/(1+\delta)$. Via extension theorems, this guarantee extends to coarse correlated equilibria (CCE) in full information settings, and to Bayesian PoA (BPoA) in settings with incomplete information and arbitrary (correlated) distributions. We then show that S2PA are $(1,1)$-revenue guaranteed with respect to bids satisfying no underbidding. This implies a PoA of at least $1/2$ for general monotone valuation, which extends to BPOA with arbitrary correlated distributions. Moreover, we show that $(\lambda,\mu)$-smoothness combined with $(\gamma,\delta)$-revenue guaranteed guarantees a PoA of at least $(\gamma+\lambda)/(1+\delta+\mu)$. This implies a host of results, such as a tight PoA of $2/3$ for S2PA with submodular (or XOS) valuations, under no overbidding and no underbidding. Beyond establishing improved bounds for S2PA, the no underbidding assumption sheds new light on the performance of S2PA relative to simultaneous 1st price auctions.
