Fetching the paper…
Reading the bibliography…
This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings.
Iterative solution of games by fictitious play
Brown, G. W. (1951) · 1951
Earlier work this paper cites.
An iterative method of solving a game
Robinson, J. (1951) · 1951
Earlier work this paper cites.
Approximation to Bayes risk in repeated play
Hannan, J. (1957) · 1957
Earlier work this paper cites.
Counterspeculation, auctions, and competitive sealed tenders
Vickrey, W. (1961) · 1961
Earlier work this paper cites.
The assignment game I: The core
Shapley, L. S., and Shubik, M. (1971) · 1971
Earlier work this paper cites.
An example of a multi-object auction game
Engelbrecht-Wiggans, R., and Weber, R. J. (1979) · 1979
Earlier work this paper cites.
Optimal auction design
Myerson, R. B. (1981) · 1981
Earlier work this paper cites.
A Theory of Auctions and Competitive Bidding
Milgrom, P. R., and Weber, R. J. (1982) · 1982
Earlier work this paper cites.
Efficient mechanisms for bilateral trading
Myerson, R. B., and Satterthwaite, M. A. (1983) · 1983
Earlier work this paper cites.
Optimal auctions with risk averse buyers
Maskin, E., and Riley, J. (1984) · 1984
Earlier work this paper cites.
Multi-item auctions
Demange, G., Gale, D., and Sotomayor, M. (1986) · 1986
Earlier work this paper cites.
The weighted majority algorithm
Littlestone, N., and Warmuth, M. K. (1994) · 1994
Earlier work this paper cites.
Convergence to efficiency in a simple market with incomplete information
Rustichini, A., Satterthwaite, M. A., and Williams, S. R. (1994) · 1994
Earlier work this paper cites.
Gambling in a rigged casino: The adversarial multi-armed bandit problem
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (1995) · 1995
Earlier work this paper cites.
Asymmetric all-pay auctions with incomplete information: The two-player case
Amann, E., and Leininger, W. (1996) · 1996
Earlier work this paper cites.
The all-pay auction with complete information
Baye, M., Kovenock, D., and de Vries, C. (1996) · 1996
Earlier work this paper cites.
Communication Complexity
Kushilevitz, E., and Nisan, N. (1996) · 1996
Earlier work this paper cites.
Fictitious play property for games with identical interests
Monderer, D., and Shapley, L. S. (1996) · 1996
Earlier work this paper cites.
Combinatorial Optimization
Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., and Schrijver, A. (1997) · 1997
Earlier work this paper cites.
The Theory of Learning in Games
Fudenberg, D., and Levine, D. K. (1998) · 1998
Earlier work this paper cites.
Auctions of heterogeneous objects
Bikhchandani, S. (1999) · 1999
Earlier work this paper cites.
Adaptive game playing using multiplicative weights
Freund, Y., and Schapire, R. E. (1999) · 1999
Earlier work this paper cites.
Worst-case equilibria
Koutsoupias, E., and Papadimitriou, C. H. (1999) · 1999
Earlier work this paper cites.
A Theory of Auctions and Competitive Bidding, II
Milgrom, P. R., and Weber, R. J. (1999) · 1999
Earlier work this paper cites.
A simple adaptive procedure leading to correlated equilibrium
Hart, S., and Mas-Colell, A. (2000) · 2000
Earlier work this paper cites.
Asymmetric auctions
Maskin, E., and Riley, J. (2000) · 2000
Earlier work this paper cites.
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., and Nisan, N. (2001) · 2001
Earlier work this paper cites.
Efficiency of large private value auctions
Swinkels, J. M. (2001) · 2001
Earlier work this paper cites.
Auction Theory
Krishna, V. (2002) · 2002
Earlier work this paper cites.
The optimality of a simple market mechanism
Satterthwaite, M. A., and Williams, S. R. (2002) · 2002
Earlier work this paper cites.
Efficiency loss in a network resource allocation game
Johari, R., and Tsitsiklis, J. N. (2004) · 2004
Earlier work this paper cites.
Putting Auction Theory to Work
Milgrom, P. (2004) · 2004
Earlier work this paper cites.
Fictitious play in 2 × n 2\times n games
Berger, U. (2005) · 2005
Cited alongside, same era.
The clock-proxy auction: A practical combinatorial auction design
Ausubel, L., Cramton, P., and Milgrom, P. (2006) · 2006
Cited alongside, same era.
Prediction, Learning, and Games
Cesa-Bianchi, N., and Lugosi, G. (2006) · 2006
Cited alongside, same era.
Efficiency of large double auctions
Cripps, M. W., and Swinkels, J. M. (2006) · 2006
Cited alongside, same era.
All-pay auctions–an experimental study
Gneezy, U., and Smorodinsky, R. (2006) · 2006
Cited alongside, same era.
Mechanism design without money
Schummer, J., and Vohra, R. V. (2007) · 2007
Cited alongside, same era.
Crowdsourcing and all-pay auctions
Simultaneous auctions are (almost) efficient
Feldman, M., Fu, H., Gravin, N., and Lucier, B. (2013) · 2013
Later among the works it cites.
Prior-independent auctions for risk-averse agents
Fu, H., Hartline, J. D., and Hoy, D. (2013) · 2013
Later among the works it cites.
Composable and efficient mechanisms
Syrgkanis, V., and Tardos, E. (2013) · 2013
Later among the works it cites.
Simultaneous Bayesian auctions and computational complexity
Cai, Y., and Papadimitriou, C. (2014) · 2014
Later among the works it cites.
Welfare guarantees for proportional allocations
Caragiannis, I., and Voudouris, A. (2014) · 2014
Later among the works it cites.
Efficiency guarantees in auctions with budgets
Dobzinski, S., and Paes Leme, R. (2014) · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
DiPalantino, D., and Vojnovic, M. (2009) · 2009
Cited alongside, same era.
Approximate mechanism design without money
Procaccia, A. D., and Tennenholtz, M. (2009) · 2009
Cited alongside, same era.
Multi-parameter mechanism design and sequential posted pricing
Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. (2010) · 2010
Cited alongside, same era.
Approximation algorithms for combinatorial auctions with complement-free bidders
Dobzinski, S., Nisan, N., and Schapira, M. (2010) · 2010
Cited alongside, same era.
The submodular welfare problem with demand queries
Feige, U., and Vondrak, J. (2010) · 2010
Cited alongside, same era.
Price of anarchy for greedy auctions
Lucier, B., and Borodin, A. (2010) · 2010
Cited alongside, same era.
Price of anarchy for auction revenue
Hartline, J., Hoy, D., and Taggart, S. (2014) · 2014
Later among the works it cites.
Ranking asymmetric auctions: Filling the gap between a distributional shift and stretch
Kirkegaard, R. (2014) · 2014
Later among the works it cites.
Barriers to near-optimal equilibria
Roughgarden, T. (2014) · 2014
Later among the works it cites.
Asymmetric all-pay auctions with interdependent valuations
Siegel, R. (2014) · 2014
Later among the works it cites.
Efficiency of Mechanisms in Complex Markets
Syrgkanis, V. (2014) · 2014
Later among the works it cites.
On the efficiency of equilibria in generalized second price auctions
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Lucier, B., Paes Leme, R., and Tardos, É. (2015) · 2015
Later among the works it cites.
On the efficiency of all-pay mechanisms
Christodoulou, G., Sgouritsa, A., and Tang, B. (2015a) · 2015
Later among the works it cites.
On the efficiency of the proportional allocation mechanism for divisible resources
Christodoulou, G., Sgouritsa, A., and Tang, B. (2015b) · 2015
Later among the works it cites.
When does the price of anarchy tend to 1 in large Walrasian auctions and Fisher markets?
Cole, R., and Tao, Y. (2015) · 2015
Later among the works it cites.
Simple auctions with simple strategies
Devanur, N., Morgenstern, J., Syrgkanis, V., and Weinberg, S. M. (2015) · 2015
Later among the works it cites.
On the complexity of computing an equilibrium in combinatorial auctions
Dobzinski, S., Fu, H., and Kleinberg, R. D. (2015) · 2015
Later among the works it cites.
Algorithms against anarchy: Understanding non-truthful mechanisms
Dütting, P., and Kesselheim, T. (2015) · 2015
Later among the works it cites.
Algorithms as mechanisms: The price of anarchy of relax-and-round
Dütting, P., Kesselheim, T., and Tardos, É. (2015) · 2015
Later among the works it cites.
A unifying hierarchy of valuations with complements and substitutes
Feige, U., Feldman, M., Immorlica, N., Izsak, R., Lucier, B., and Syrgkanis, V. (2015) · 2015
Later among the works it cites.
No-regret learning in repeated bayesian games
Hartline, J., Syrgkanis, V., and Tardos, E. (2015) · 2015
Later among the works it cites.
Smooth online mechanisms: A game-theoretic problem in renewable energy markets
Kesselheim, T., Kleinberg, R., and Tardos, E. (2015) · 2015
Later among the works it cites.
Robust price of anarchy bounds via LP and Fenchel duality
Kulkarni, J., and Mirrokni, V. (2015) · 2015
Later among the works it cites.
Asymptotically tight bounds for inefficiency in risk-averse selfish routing
Lianeas, T., Nikolova, E., and Stier-Moses, N. E. (2015) · 2015
Later among the works it cites.
Greedy algorithms make efficient mechanisms
Lucier, B., and Syrgkanis, V. (2015) · 2015
Later among the works it cites.
Intrinsic robustness of the price of anarchy
Roughgarden, T. (2015) · 2015
Later among the works it cites.
On the economic efficiency of the combinatorial clock auction
Bousquet, N., Cai, Y., Hunkenschröder, C., and Vetta, A. (2016) · 2016
Closest in time.
Interpolating between truthful and non-truthful mechanisms for combinatorial auctions
Braverman, M., Mao, J., and Weinberg, S. M. (2016) · 2016
Closest in time.
Regret is hard, envy is easy
Daskalakis, C., and Syrgkanis, V. (2016) · 2016
Closest in time.
The price of anarchy in large games
Feldman, M., Immorlica, N., Lucier, B., Roughgarden, T., and Syrgkanis, V. (2016) · 2016
Closest in time.
Communication complexity (for algorithm designers)
Roughgarden, T. (2016) · 2016
Closest in time.