Zusammenfassung
This survey outlines a general and modular theory for proving approximation
guarantees for equilibria of auctions in complex settings. This theory
complements traditional economic techniques, which generally focus on exact and
optimal solutions and are accordingly limited to relatively stylized settings.
We highlight three user-friendly analytical tools: smoothness-type
inequalities, which immediately yield approximation guarantees for many auction
formats of interest in the special case of complete information and
deterministic strategies; extension theorems, which extend such guarantees to
randomized strategies, no-regret learning outcomes, and incomplete-information
settings; and composition theorems, which extend such guarantees from simpler
to more complex auctions. Combining these tools yields tight worst-case
approximation guarantees for the equilibria of many widely-used auction
formats.
Nutzer