MasterBib.bib

@inproceedings{Knaster46,
  title={Sur le probleme du partage pragmatique de H. Steinhaus},
  author={Knaster, Bronislaw},
  booktitle={Annales de la Societ{\'e} Polonaise de Mathematique},
  volume={19},
  pages={228--230},
  year={1946}
}

@inproceedings{SpielmanT04,
  title={Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems},
  author={Spielman, Daniel A and Teng, Shang-Hua},
  booktitle={Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
  pages={81--90},
  year={2004},
  organization={ACM}
}

@inproceedings{HartlineL10,
  author    = {Jason D. Hartline and
               Brendan Lucier},
  title     = {Bayesian algorithmic mechanism design},
  booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
               2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
  pages     = {301--310},
  year      = {2010},
  crossref  = {DBLP:conf/stoc/2010},
  url       = {http://doi.acm.org/10.1145/1806689.1806732},
  doi       = {10.1145/1806689.1806732},
  timestamp = {Fri, 12 Oct 2012 12:16:22 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/HartlineL10},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{FeldmanFR18,
  author    = {Michal Feldman and
               Ophir Friedler and
               Aviad Rubinstein},
  title     = {99{\%} Revenue via Enhanced Competition},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {443--460},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219202},
  doi       = {10.1145/3219166.3219202},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/FeldmanFR18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{KalyanasundaramP00,
  author    = {Bala Kalyanasundaram and
               Kirk Pruhs},
  title     = {Speed is as powerful as clairvoyance},
  journal   = {J. {ACM}},
  volume    = {47},
  number    = {4},
  pages     = {617--643},
  year      = {2000},
  url       = {http://doi.acm.org/10.1145/347476.347479},
  doi       = {10.1145/347476.347479},
  timestamp = {Thu, 20 Nov 2003 12:28:13 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jacm/KalyanasundaramP00},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{RoughgardenT02,
  author    = {Tim Roughgarden and
               {\'{E}}va Tardos},
  title     = {How bad is selfish routing?},
  journal   = {J. {ACM}},
  volume    = {49},
  number    = {2},
  pages     = {236--259},
  year      = {2002},
  url       = {http://doi.acm.org/10.1145/506147.506153},
  doi       = {10.1145/506147.506153},
  timestamp = {Thu, 20 Nov 2003 12:28:21 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jacm/RoughgardenT02},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Mitchell99,
  author    = {Joseph S. B. Mitchell},
  title     = {Guillotine Subdivisions Approximate Polygonal Subdivisions: {A} Simple
               Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and
               Related Problems},
  journal   = {{SIAM} J. Comput.},
  volume    = {28},
  number    = {4},
  pages     = {1298--1309},
  year      = {1999},
  url       = {https://doi.org/10.1137/S0097539796309764},
  doi       = {10.1137/S0097539796309764},
  timestamp = {Sat, 27 May 2017 14:22:58 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/siamcomp/Mitchell99},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{SleatorT85,
  author    = {Daniel Dominic Sleator and
               Robert Endre Tarjan},
  title     = {Amortized Efficiency of List Update and Paging Rules},
  journal   = {Commun. {ACM}},
  volume    = {28},
  number    = {2},
  pages     = {202--208},
  year      = {1985},
  url       = {http://doi.acm.org/10.1145/2786.2793},
  doi       = {10.1145/2786.2793},
  timestamp = {Tue, 07 Jun 2011 16:51:41 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/cacm/SleatorT85},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Arora98,
  author    = {Sanjeev Arora},
  title     = {Polynomial Time Approximation Schemes for Euclidean Traveling Salesman
               and other Geometric Problems},
  journal   = {J. {ACM}},
  volume    = {45},
  number    = {5},
  pages     = {753--782},
  year      = {1998},
  url       = {http://doi.acm.org/10.1145/290179.290180},
  doi       = {10.1145/290179.290180},
  timestamp = {Thu, 20 Nov 2003 12:28:00 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jacm/Arora98},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{VegaL81,
  author    = {Wenceslas Fernandez de la Vega and
               George S. Lueker},
  title     = {Bin packing can be solved within 1+epsilon in linear time},
  journal   = {Combinatorica},
  volume    = {1},
  number    = {4},
  pages     = {349--355},
  year      = {1981},
  url       = {https://doi.org/10.1007/BF02579456},
  doi       = {10.1007/BF02579456},
  timestamp = {Thu, 18 May 2017 09:53:26 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/combinatorica/VegaL81},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{SpielmanT09,
  title={Smoothed analysis: an attempt to explain the behavior of algorithms in practice},
  author={Spielman, Daniel A and Teng, Shang-Hua},
  journal={Communications of the ACM},
  volume={52},
  number={10},
  pages={76--84},
  year={2009},
  publisher={ACM}
}
@article{IbarraK75,
  author    = {Oscar H. Ibarra and
               Chul E. Kim},
  title     = {Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems},
  journal   = {J. {ACM}},
  volume    = {22},
  number    = {4},
  pages     = {463--468},
  year      = {1975},
  url       = {http://doi.acm.org/10.1145/321906.321909},
  doi       = {10.1145/321906.321909},
  timestamp = {Thu, 26 Jan 2012 17:31:32 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jacm/IbarraK75},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@Inbook{KolliopoulosS98,
author="Kolliopoulos, Stavros G.
and Stein, Clifford",
editor="Bixby, Robert E.
and Boyd, E. Andrew
and R{\'i}os-Mercado, Roger Z.",
title="Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs",
bookTitle="Integer Programming and Combinatorial Optimization: 6th International IPCO Conference Houston, Texas, June 22--24, 1998 Proceedings",
year="1998",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="153--168",
isbn="978-3-540-69346-8",
doi="10.1007/3-540-69346-7_12",
url="http://dx.doi.org/10.1007/3-540-69346-7_12"
}

@inproceedings{BriestKV05,
	Author = {Patrick Briest and Piotr Krysta and Berthold V{\"o}cking},
	Booktitle = {the 37th Annual ACM Symposium on Theory of Computing (STOC)},
	Title = {Approximation techniques for utilitarian mechanism design},
	Year = {2005}}

@inproceedings{Rubinstein16,
title = {Settling the Complexity of computing approximate two-player Nash Equillibria},
author = {Aviad Rubinstein},
year = {2016},
booktitle = {FOCS}
}

@article{Raghavan88,
 author = {Raghavan, Prabhakar},
 title = {Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs},
 journal = {J. Comput. Syst. Sci.},
 issue_date = {October 1988},
 volume = {37},
 number = {2},
 month = oct,
 year = {1988},
 issn = {0022-0000},
 pages = {130--143},
 numpages = {14},
 url = {http://dx.doi.org/10.1016/0022-0000(88)90003-7},
 doi = {10.1016/0022-0000(88)90003-7},
 acmid = {53815},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
} 

@inproceedings{DobzinskiN07,
	Author = {Shahar Dobzinski and Noam Nisan},
	Booktitle = {the 8th ACM Conference on Electronic Commerce (EC)},
	Title = {Mechanisms for Multi-Unit Auctions},
	Year = {2007}}

@inproceedings{DobzinskiV12a,
	Author = {Shahar Dobzinski and Jan Vondrak},
	Booktitle = {Proceedings of the ACM Conference on Electronic Commerce (EC)},
	Title = {{The Computational Complexity of Truthfulness in Combinatorial Auctions}},
	Year = {2012}}



@inproceedings{MirrokniSV08,
  author    = {Vahab S. Mirrokni and
               Michael Schapira and
               Jan Vondr{\'{a}}k},
  title     = {Tight information-theoretic lower bounds for welfare maximization
               in combinatorial auctions},
  booktitle = {Proceedings 9th {ACM} Conference on Electronic Commerce (EC-2008),
               Chicago, IL, USA, June 8-12, 2008},
  pages     = {70--77},
  year      = {2008},
  crossref  = {DBLP:conf/sigecom/2008},
  url       = {http://doi.acm.org/10.1145/1386790.1386805},
  doi       = {10.1145/1386790.1386805},
  timestamp = {Mon, 24 Feb 2014 16:09:47 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/MirrokniSV08},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@INPROCEEDINGS{FeigeV06,
    author = {Uriel Feige and Jan Vondrak},
    title = {The allocation problem with submodular utility functions},
    booktitle = {In Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS},
    year = {2006}
}


@inproceedings{Yao:1979:CQR:800135.804414,
 author = {Yao, Andrew Chi-Chih},
 title = {Some Complexity Questions Related to Distributive Computing(Preliminary Report)},
 booktitle = {Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing},
 series = {STOC '79},
 year = {1979},
 location = {Atlanta, Georgia, USA},
 pages = {209--213},
 numpages = {5},
 url = {http://doi.acm.org/10.1145/800135.804414},
 doi = {10.1145/800135.804414},
 acmid = {804414},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{Nisan:1993:RCC:152322.152386,
 author = {Nisan, Noam and Wigderson, Avi},
 title = {Rounds in Communication Complexity Revisited},
 journal = {SIAM J. Comput.},
 issue_date = {Feb. 1993},
 volume = {22},
 number = {1},
 month = feb,
 year = {1993},
 issn = {0097-5397},
 pages = {211--219},
 numpages = {9},
 url = {http://dx.doi.org/10.1137/0222016},
 doi = {10.1137/0222016},
 acmid = {152386},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {communication complexity, information, monotone circuits, rounds},
} 

@inproceedings{Papadimitriou:1982:CC:800070.802192,
 author = {Papadimitriou, Christos H. and Sipser, Michael},
 title = {Communication Complexity},
 booktitle = {Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing},
 series = {STOC '82},
 year = {1982},
 isbn = {0-89791-070-2},
 location = {San Francisco, California, USA},
 pages = {196--200},
 numpages = {5},
 url = {http://doi.acm.org/10.1145/800070.802192},
 doi = {10.1145/800070.802192},
 acmid = {802192},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{Duris:1984:LBC:800057.808668,
 author = {Duris, Pavol and Galil, Zvi and Schnitger, Georg},
 title = {Lower Bounds on Communication Complexity},
 booktitle = {Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing},
 series = {STOC '84},
 year = {1984},
 isbn = {0-89791-133-4},
 pages = {81--91},
 numpages = {11},
 url = {http://doi.acm.org/10.1145/800057.808668},
 doi = {10.1145/800057.808668},
 acmid = {808668},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{DobzinskiNO14,
	Author = {Shahar Dobzinski and Noam Nisan and Sigal Oren},
	Booktitle = {the 46th annual ACM symposium on Theory of computing (STOC)},
	Title = {Economic Efficiency Requires Interaction},
	Year = {2014}}

@article{BabaiGKL03,
  author    = {L{\'{a}}szl{\'{o}} Babai and
               Anna G{\'{a}}l and
               Peter G. Kimmel and
               Satyanarayana V. Lokam},
  title     = {Communication Complexity of Simultaneous Messages},
  journal   = {{SIAM} J. Comput.},
  volume    = {33},
  number    = {1},
  pages     = {137--166},
  year      = {2003},
  url       = {http://dx.doi.org/10.1137/S0097539700375944},
  doi       = {10.1137/S0097539700375944},
  timestamp = {Mon, 12 Sep 2011 16:10:10 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/siamcomp/BabaiGKL03},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}


@inproceedings{Feige06,
 author = {Feige, Uriel},
 title = {On Maximizing Welfare when Utility Functions Are Subadditive},
 booktitle = {Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing},
 series = {STOC '06},
 year = {2006},
 isbn = {1-59593-134-1},
 location = {Seattle, WA, USA},
 pages = {41--50},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1132516.1132523},
 doi = {10.1145/1132516.1132523},
 acmid = {1132523},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {combinatorial auctions, randomized rounding},
} 



@inproceedings{DobzinskiS06,
 author = {Dobzinski, Shahar and Schapira, Michael},
 title = {An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders},
 booktitle = {Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm},
 series = {SODA '06},
 year = {2006},
 isbn = {0-89871-605-5},
 location = {Miami, Florida},
 pages = {1064--1073},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1109557.1109675},
 acmid = {1109675},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@inproceedings{Dobzinski07,
	Author = {Dobzinski, Shahar},
	Booktitle = {Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques},
	Pages = {89--103},
	Title = {Two Randomized Mechanisms for Combinatorial Auctions},
	Year = {2007}}

@inproceedings{Dobzinski16a,
 author = {Dobzinski, Shahar},
 title = {Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders},
 booktitle = {Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing},
 series = {STOC 2016},
 year = {2016},
 isbn = {978-1-4503-4132-5},
 location = {Cambridge, MA, USA},
 pages = {940--948},
 numpages = {9},
 url = {http://doi.acm.org/10.1145/2897518.2897569},
 doi = {10.1145/2897518.2897569},
 acmid = {2897569},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Approximation Algorithms, Auctions, Submodular Valuations},
} 

@inproceedings{DobzinskiNS06,
	Author = {Dobzinski, Shahar and Nisan, Noam and Schapira, Michael},
	Booktitle = {Proceedings of the thirty-eighth annual ACM symposium on Theory of computing},
	Organization = {ACM},
	Pages = {644--652},
	Title = {Truthful randomized mechanisms for combinatorial auctions},
	Year = {2006}}

@incollection{KrystaV13,
	Author = {Krysta, Piotr and V{\"o}cking, Berthold},
	Booktitle = {Automata, Languages, and Programming},
	Pages = {636--647},
	Publisher = {Springer},
	Title = {Online mechanism design (randomized rounding on the fly)},
	Year = 2012}

@inproceedings{DobzinskiV12b,
	Author = {Shahar Dobzinski and Jan Vondr{\'a}k},
	Booktitle = {Proceedings of the 44th Symposium on Theory of Computing (STOC)},
	Title = {From query complexity to computational complexity},
	Year = {2012}}

@inproceedings{DughmiV11,
	Author = {Shaddin Dughmi and Jan Vondrak},
	Booktitle = {52nd Annual Symposium on Foundations of Computer Science (FOCS)},
	Title = {{Limitations of Randomized Mechanisms for Combinatorial Auctions}},
	Year = {2011}}

@inproceedings{Vondrak08,
  author    = {Jan Vondr{\'{a}}k},
  title     = {Optimal approximation for the submodular welfare problem in the value
               oracle model},
  booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
               Victoria, British Columbia, Canada, May 17-20, 2008},
  pages     = {67--74},
  year      = {2008},
  crossref  = {DBLP:conf/stoc/2008},
  url       = {http://doi.acm.org/10.1145/1374376.1374389},
  doi       = {10.1145/1374376.1374389},
  timestamp = {Sat, 19 Jun 2010 14:44:24 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/stoc/Vondrak08},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}
@inproceedings{LehmannLN01,
Author = {Benny Lehmann and Daniel Lehmann and Noam Nisan},
	Booktitle = {the 3rd Annual ACM Conference on Electronic Commerce (EC)},
	Title = {Combinatorial Auctions with Decreasing Marginal Utilities},
	Year = {2001}}

@inproceedings{FeldmanGL14,
 author = {Feldman, Michal and Gravin, Nick and Lucier, Brendan},
 title = {Combinatorial Auctions via Posted Prices},
 booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '15},
 year = {2015},
 location = {San Diego, California},
 pages = {123--135},
 numpages = {13},
 url = {http://dl.acm.org/citation.cfm?id=2722129.2722139},
 acmid = {2722139},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@inproceedings{DughmiRY11,
	Author = {Shaddin Dughmi and Tim Roughgarden and Qiqi Yan},
	Booktitle = {Proceedings of the 43rd ACM Symposium on the Theory of Computing (STOC)},
	Title = {From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions},
	Year = {2011}}

@inproceedings{DughmiHN14,
  author    = {Shaddin Dughmi and
               Li Han and
               Noam Nisan},
  title     = {Sampling and Representation Complexity of Revenue Maximization},
  booktitle = {Web and Internet Economics - 10th International Conference, {WINE}
               2014, Beijing, China, December 14-17, 2014. Proceedings},
  pages     = {277--291},
  year      = {2014},
  crossref  = {DBLP:conf/wine/2014},
  url       = {http://dx.doi.org/10.1007/978-3-319-13129-0_22},
  doi       = {10.1007/978-3-319-13129-0_22},
  timestamp = {Wed, 26 Nov 2014 14:31:47 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/wine/DughmiHN14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{ChenDT09,
  author    = {Xi Chen and
               Xiaotie Deng and
               Shang{-}Hua Teng},
  title     = {Settling the complexity of computing two-player Nash equilibria},
  journal   = {J. {ACM}},
  volume    = {56},
  number    = {3},
  year      = {2009},
  url       = {http://doi.acm.org/10.1145/1516512.1516516},
  doi       = {10.1145/1516512.1516516},
  timestamp = {Wed, 20 May 2009 11:30:31 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jacm/ChenDT09},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{DaskalakisGP09,
  author    = {Constantinos Daskalakis and
               Paul W. Goldberg and
               Christos H. Papadimitriou},
  title     = {The Complexity of Computing a Nash Equilibrium},
  journal   = {{SIAM} J. Comput.},
  volume    = {39},
  number    = {1},
  pages     = {195--259},
  year      = {2009},
  url       = {http://dx.doi.org/10.1137/070699652},
  doi       = {10.1137/070699652},
  timestamp = {Wed, 03 Feb 2010 09:05:39 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/siamcomp/DaskalakisGP09},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@inproceedings{ChawlaM16,
  author    = {Shuchi Chawla and
               J. Benjamin Miller},
  title     = {Mechanism Design for Subadditive Agents via an Ex Ante Relaxation},
  booktitle = {Proceedings of the 2016 {ACM} Conference on Economics and Computation,
               {EC} '16, Maastricht, The Netherlands, July 24-28, 2016},
  pages     = {579--596},
  year      = {2016},
  crossref  = {DBLP:conf/sigecom/2016},
  url       = {http://doi.acm.org/10.1145/2940716.2940756},
  doi       = {10.1145/2940716.2940756},
  timestamp = {Fri, 22 Jul 2016 09:44:16 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/ChawlaM16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@techreport{nayak2015stubborn,
  title={Stubborn mining: Generalizing selfish mining and combining with an eclipse attack},
  author={Nayak, Kartik and Kumar, Srijan and Miller, Andrew and Shi, Elaine},
  year={2015},
  institution={IACR Cryptology ePrint Archive 2015}
}

@misc{Nakamoto08,
  title={Bitcoin: A peer-to-peer electronic cash system},
  author={Nakamoto, Satoshi},
  year={2008}
}

@inproceedings{KiayiasKKT16,
title = {Blockchain Mining Games},
author = {Aggelos Kiayias and Elias Koutsoupias and Maria Kyropoulou and Yiannis Tselekounis},
booktitle = {ACM Conference on Economics and Computation (EC)},
year = {2016}
}

@inproceedings{GarayKL15,
  author    = {Juan A. Garay and
               Aggelos Kiayias and
               Nikos Leonardos},
  title     = {The Bitcoin Backbone Protocol: Analysis and Applications},
  booktitle = {Advances in Cryptology - {EUROCRYPT} 2015 - 34th Annual International
               Conference on the Theory and Applications of Cryptographic Techniques,
               Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part {II}},
  pages     = {281--310},
  year      = {2015},
  crossref  = {DBLP:conf/eurocrypt/2015-2},
  url       = {http://dx.doi.org/10.1007/978-3-662-46803-6_10},
  doi       = {10.1007/978-3-662-46803-6_10},
  timestamp = {Tue, 14 Apr 2015 13:59:22 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/eurocrypt/GarayKL15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{CourtoisB14,
  author    = {Nicolas T. Courtois and
               Lear Bahack},
  title     = {On Subversive Miner Strategies and Block Withholding Attack in Bitcoin
               Digital Currency},
  journal   = {CoRR},
  volume    = {abs/1402.1718},
  year      = {2014},
  url       = {http://arxiv.org/abs/1402.1718},
  timestamp = {Wed, 05 Mar 2014 14:43:44 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/CourtoisB14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{HartMC00,
authors = {Sergiu Hart and Andreu Mas-Colell},
title = {A simple adaptive procedure leading to correlated equilibrium},
journal = {Econometrica},
year = {2000},
volume = {68},
number = {5},
pages = {1127-1150}
}

@article{BlumM07,
  author    = {Avrim Blum and
               Yishay Mansour},
  title     = {From External to Internal Regret},
  journal   = {Journal of Machine Learning Research},
  volume    = {8},
  pages     = {1307--1324},
  year      = {2007},
  url       = {http://dl.acm.org/citation.cfm?id=1314543},
  timestamp = {Thu, 15 Dec 2011 15:52:06 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jmlr/BlumM07},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{FosterV97,
authors = {Dean P Foster and Rakesh V Vohra},
title = {Calibrated Learning and Correlated Equilibrium},
journal = {Games and Economic Behavior},
year = {1997},
volume = {21},
number = {1},
pages = {40-55}
}

Dean P Foster and Rakesh V Vohra. Calibrated learning and correlated equilibrium. Games and
Economic Behavior, 21(1):40–55, 1997.

@article{LittlestoneW94,
  author    = {Nick Littlestone and
               Manfred K. Warmuth},
  title     = {The Weighted Majority Algorithm},
  journal   = {Inf. Comput.},
  volume    = {108},
  number    = {2},
  pages     = {212--261},
  year      = {1994},
  url       = {http://dx.doi.org/10.1006/inco.1994.1009},
  doi       = {10.1006/inco.1994.1009},
  timestamp = {Wed, 06 Jul 2011 21:23:53 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/iandc/LittlestoneW94},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{Rosenfeld11,
  author    = {Meni Rosenfeld},
  title     = {Analysis of Bitcoin Pooled Mining Reward Systems},
  journal   = {CoRR},
  volume    = {abs/1112.4980},
  year      = {2011},
  url       = {http://arxiv.org/abs/1112.4980},
  timestamp = {Wed, 10 Oct 2012 21:28:45 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/abs-1112-4980},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@inproceedings{MoserB15,
  author    = {Malte M{\"{o}}ser and
               Rainer B{\"{o}}hme},
  title     = {Trends, Tips, Tolls: {A} Longitudinal Study of Bitcoin Transaction
               Fees},
  booktitle = {Workshop on Bitcoin Research},
  pages     = {19--33},
  year      = {2015},
  crossref  = {DBLP:conf/fc/2015w},
  url       = {http://dx.doi.org/10.1007/978-3-662-48051-9_2},
  doi       = {10.1007/978-3-662-48051-9_2},
  timestamp = {Sat, 05 Sep 2015 14:27:36 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/fc/MoserB15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}


@misc{forbes,
title = {Bitcoin is not Broken},
author = {Kashmir Hill},
year = {2013},
howpublished = {Forbes},
note = {\url{http://www.forbes.com/sites/kashmirhill/2013/11/06/bitcoin-is-not-broken/#55d4a8812568}}
}

@incollection{EyalS14,
  title={Majority is not enough: Bitcoin mining is vulnerable},
  author={Eyal, Ittay and Sirer, Emin G{\"u}n},
  booktitle={Financial Cryptography and Data Security},
  pages={436--454},
  year={2014},
  publisher={Springer}
}

@inproceedings{taylor2013bitcoin,
  title={Bitcoin and the age of bespoke silicon},
  author={Taylor, Michael Bedford},
  booktitle={Proceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems},
  pages={16},
  year={2013},
  organization={IEEE Press}
}

@article{AuerCFS02,
author = {P. Auer and N. Cesa-Bianchi and Y. Freund and R. E. Schapire},
title = {The nonstochastic multiarmed bandit problem},
journal = {SIAM Journal of Computing},
volume = {32},
number = {1},
year = {2002},
pages = {48-77}
}

@inproceedings{SapirshteinSZ16,
title = {Optimal Selfish Mining Strategies in Bitcoin},
author = {Ayelet Sapirshtein and Yonatan Sompolinsky and Aviv Zohar},
booktitle = {Financial Cryptography and Data Security},
year = {2016}
}

@inproceedings{NayakKMS16,
title = {Stubborn Mining: Generalizing Selfish Mining and Combining with an Eclipse Attack},
author = {Kartik Nayak and Srijan Kumar and Andrew Miller and Elaine Shi},
booktitle = {IEEE European Symposium on Security and Privacy (EuroS\&P)},
year = {2016}
}



@inproceedings{KDF13,
  title={The Economics of Bitcoin Mining, or Bitcoin in the Presence of Adversaries},
  author={Joshua A. Kroll and Ian C. Davey and Edward W. Felten},
  booktitle={Proceedings of the Twelfth Annual Workshop on the Economics of Information Security (WEIS)},
  year={2013}
}

@inproceedings{JohnsonLGVM14,
  title={Game-theoretic Analysis of DDoS attacks against Bitcoin Mining pools},
  author={Benjamin Johnson and Aron Laszka and Jens Grossklags and Mari Vasek and Tyler Moore},
  booktitle={Proceedings of the First Workshop on Bitcoin Research},
  year={2014}
}

@inproceedings{EmpiricalDDoS,
  title={Empirical Analysis of denial-of-service attacks in the Bitcoin ecosystem},
  author={Marie Vasek and Micha Thornton and Tyler Moore},
  booktitle={Proceedings of the First Workshop on Bitcoin Research},
  year={2014}
}

@inproceedings{demystifying2015,
  title={Demystifying Incentives in the Consensus Computer},
  author={Loi Luu and Jason Teutsch and Raghav Kulkarni and Prateek Saxena},
  booktitle={Proceedings of the ACM Conference on Computer and Communications Security (CCS)},
  year={2015}
}

@inproceedings{decker2013information,
  title={Information propagation in the bitcoin network},
  author={Decker, Christian and Wattenhofer, Roger},
  booktitle={Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on},
  pages={1--10},
  year={2013},
  organization={IEEE}
}

@inproceedings{privacysimulator,
  title={Evaluating User Privacy in Bitcoin},
  author={Elli Androulaki and Ghassan O. Karame and Marc Roeschlin and Tobias Scherer and Srdjan Capkun},
  booktitle={Proceedings of Financial Cryptography},
  year={2013}
}

@article{peter2015transaction,
  title={A Transaction Fee Market Exists Without a Block Size Limit},
  author={Peter, R},
  year={2015}
}

@article{Houy14,
  title={The Economics of Bitcoin Transaction Fees},
  author={Nicolas Houy},
  year={2014},
  journal = {Working Paper GATE 2014-07. halshs-00951358.}
}

@inproceedings{shadow,
title =  {Shadow-bitcoin:
scalable simulation via direct execution of multithreaded
applications},
author = {Andrew Miller and Rob Jansen},
booktitle = {Proceedings of the eighth workshop on Cybersecurity Experimentations and Test (CSET)},
year = {2015}
}

@article{CKN,
title = {Mind the Gap: Security Implications of the Evolution of Bitcoin Mining},
author = {Miles Carlsten and Harry Kalodner and Arvind Naryanan},
year = {2015},
journal = {Bitcoin Scalability Workshops (presentation)},
year = {2015},
notes = {https://scalingbitcoin.org/montreal2015/presentations/Day1/13-miles-carlsten-Mind-the-Gap.pdf}
}

@inproceedings{SoK,
title = {SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies. },
author = {Andrew Miller and Jeremy Clark and Arvind Narayanan and Joshua A. Kroll and Edward W. Felten},
year = {2015},
booktitle = {Proceedings of the 36th IEEE Symposium on Security and Privacy (S\&P)},
year = {2015}
}

@inproceedings{EdenFFTW17a,
  author    = {Alon Eden and
               Michal Feldman and
               Ophir Friedler and
               Inbal Talgam{-}Cohen and
               S. Matthew Weinberg},
  title     = {A Simple and Approximately Optimal Mechanism for a Buyer with Complements:
               Abstract},
  booktitle = {Proceedings of the 2017 {ACM} Conference on Economics and Computation,
               {EC} '17, Cambridge, MA, USA, June 26-30, 2017},
  pages     = {323},
  year      = {2017},
  crossref  = {DBLP:conf/sigecom/2017},
  url       = {http://doi.acm.org/10.1145/3033274.3085116},
  doi       = {10.1145/3033274.3085116},
  timestamp = {Wed, 21 Jun 2017 09:41:38 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/EdenFFTW17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{EdenFFTW17b,
  author    = {Alon Eden and
               Michal Feldman and
               Ophir Friedler and
               Inbal Talgam{-}Cohen and
               S. Matthew Weinberg},
  title     = {The Competition Complexity of Auctions: {A} Bulow-Klemperer Result
               for Multi-Dimensional Bidders},
  booktitle = {Proceedings of the 2017 {ACM} Conference on Economics and Computation,
               {EC} '17, Cambridge, MA, USA, June 26-30, 2017},
  pages     = {343},
  year      = {2017},
  crossref  = {DBLP:conf/sigecom/2017},
  url       = {http://doi.acm.org/10.1145/3033274.3085115},
  doi       = {10.1145/3033274.3085115},
  timestamp = {Wed, 21 Jun 2017 09:41:38 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/EdenFFTW17a},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DevanurW17,
  author    = {Nikhil R. Devanur and
               S. Matthew Weinberg},
  title     = {The Optimal Mechanism for Selling to a Budget Constrained Buyer: The
               General Case},
  booktitle = {Proceedings of the 2017 {ACM} Conference on Economics and Computation,
               {EC} '17, Cambridge, MA, USA, June 26-30, 2017},
  pages     = {39--40},
  year      = {2017},
  crossref  = {DBLP:conf/sigecom/2017},
  url       = {http://doi.acm.org/10.1145/3033274.3085132},
  doi       = {10.1145/3033274.3085132},
  timestamp = {Wed, 21 Jun 2017 09:41:38 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/DevanurW17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BravermanMW18,
  author    = {Mark Braverman and
               Jieming Mao and
               S. Matthew Weinberg},
  title     = {On Simultaneous Two-player Combinatorial Auctions},
  booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
  pages     = {2256--2273},
  year      = {2018},
  crossref  = {DBLP:conf/soda/2018},
  url       = {https://doi.org/10.1137/1.9781611975031.146},
  doi       = {10.1137/1.9781611975031.146},
  timestamp = {Thu, 04 Jan 2018 13:55:11 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/soda/BravermanMW18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{SaxenaSW18,
  author    = {Raghuvansh R. Saxena and
               Ariel Schvartzman and
               S. Matthew Weinberg},
  title     = {The menu complexity of "one-and-a-half-dimensional" mechanism design},
  booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
  pages     = {2026--2035},
  year      = {2018},
  crossref  = {DBLP:conf/soda/2018},
  url       = {https://doi.org/10.1137/1.9781611975031.132},
  doi       = {10.1137/1.9781611975031.132},
  timestamp = {Thu, 04 Jan 2018 13:55:11 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/soda/SaxenaSW18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BabaioffGN17,
  author    = {Moshe Babaioff and
               Yannai A. Gonczarowski and
               Noam Nisan},
  title     = {The menu-size complexity of revenue approximation},
  booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
  pages     = {869--877},
  year      = {2017},
  crossref  = {DBLP:conf/stoc/2017},
  url       = {http://doi.acm.org/10.1145/3055399.3055426},
  doi       = {10.1145/3055399.3055426},
  timestamp = {Sat, 17 Jun 2017 18:46:57 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/BabaioffGN17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{RubinsteinSW18,
  author    = {Aviad Rubinstein and
               Tselil Schramm and
               S. Matthew Weinberg},
  title     = {Computing Exact Minimum Cuts Without Knowing the Graph},
  booktitle = {9th Innovations in Theoretical Computer Science Conference, {ITCS}
               2018, January 11-14, 2018, Cambridge, MA, {USA}},
  pages     = {39:1--39:16},
  year      = {2018},
  crossref  = {DBLP:conf/innovations/2018},
  url       = {https://doi.org/10.4230/LIPIcs.ITCS.2018.39},
  doi       = {10.4230/LIPIcs.ITCS.2018.39},
  timestamp = {Sat, 13 Jan 2018 00:04:27 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/innovations/RubinsteinSW18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{KiayiasKKT16,
  author    = {Aggelos Kiayias and
               Elias Koutsoupias and
               Maria Kyropoulou and
               Yiannis Tselekounis},
  title     = {Blockchain Mining Games},
  booktitle = {Proceedings of the 2016 {ACM} Conference on Economics and Computation,
               {EC} '16, Maastricht, The Netherlands, July 24-28, 2016},
  pages     = {365--382},
  year      = {2016},
  crossref  = {DBLP:conf/sigecom/2016},
  url       = {http://doi.acm.org/10.1145/2940716.2940773},
  doi       = {10.1145/2940716.2940773},
  timestamp = {Fri, 22 Jul 2016 09:44:16 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/KiayiasKKT16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{KiayiasRDO17,
  author    = {Aggelos Kiayias and
               Alexander Russell and
               Bernardo David and
               Roman Oliynykov},
  title     = {Ouroboros: {A} Provably Secure Proof-of-Stake Blockchain Protocol},
  booktitle = {Advances in Cryptology - {CRYPTO} 2017 - 37th Annual International
               Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017,
               Proceedings, Part {I}},
  pages     = {357--388},
  year      = {2017},
  crossref  = {DBLP:conf/crypto/2017-1},
  url       = {https://doi.org/10.1007/978-3-319-63688-7\_12},
  doi       = {10.1007/978-3-319-63688-7\_12},
  timestamp = {Mon, 14 Aug 2017 14:34:46 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/crypto/KiayiasRDO17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{SapirshteinSZ16,
  author    = {Ayelet Sapirshtein and
               Yonatan Sompolinsky and
               Aviv Zohar},
  title     = {Optimal Selfish Mining Strategies in Bitcoin},
  booktitle = {Financial Cryptography and Data Security - 20th International Conference,
               {FC} 2016, Christ Church, Barbados, February 22-26, 2016, Revised
               Selected Papers},
  pages     = {515--532},
  year      = {2016},
  crossref  = {DBLP:conf/fc/2016},
  url       = {https://doi.org/10.1007/978-3-662-54970-4\_30},
  doi       = {10.1007/978-3-662-54970-4\_30},
  timestamp = {Wed, 17 May 2017 11:13:47 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/fc/SapirshteinSZ16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{CarlstenKWN16,
  author    = {Miles Carlsten and
               Harry A. Kalodner and
               S. Matthew Weinberg and
               Arvind Narayanan},
  title     = {On the Instability of Bitcoin Without the Block Reward},
  booktitle = {Proceedings of the 2016 {ACM} {SIGSAC} Conference on Computer and
               Communications Security, Vienna, Austria, October 24-28, 2016},
  pages     = {154--167},
  year      = {2016},
  crossref  = {DBLP:conf/ccs/2016},
  url       = {http://doi.acm.org/10.1145/2976749.2978408},
  doi       = {10.1145/2976749.2978408},
  timestamp = {Mon, 24 Oct 2016 18:57:12 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ccs/CarlstenKWN16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{arora2012multiplicative,
  title={The Multiplicative Weights Update Method: a Meta-Algorithm and Applications.},
  author={Arora, Sanjeev and Hazan, Elad and Kale, Satyen},
  journal={Theory of Computing},
  volume={8},
  number={1},
  pages={121--164},
  year={2012}
}

@inproceedings{Dobzinski16b,
 author = {Dobzinski, Shahar},
 title = {Computational Efficiency Requires Simple Taxation},
 booktitle = {FOCS},
 year = {2016},
} 

@inproceedings{DanielySS15,
  author    = {Amit Daniely and
               Michael Schapira and
               Gal Shahaf},
  title     = {Inapproximability of Truthful Mechanisms via Generalizations of the
               {VC} Dimension},
  booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
               of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
  pages     = {401--408},
  year      = {2015},
  crossref  = {DBLP:conf/stoc/2015},
  url       = {http://doi.acm.org/10.1145/2746539.2746597},
  doi       = {10.1145/2746539.2746597},
  timestamp = {Wed, 10 Jun 2015 17:20:57 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/stoc/DanielySS15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}


@inproceedings{LaviS05,
	Author = {Ron Lavi and Chaitanya Swamy},
	Booktitle = {Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
	Title = {Truthful and Near-Optimal Mechanism Design via Linear Programming},
	Year = {2005}}

@article{Roughgarden15,
  author    = {Tim Roughgarden},
  title     = {Intrinsic Robustness of the Price of Anarchy},
  journal   = {J. {ACM}},
  volume    = {62},
  number    = {5},
  pages     = {32:1--32:42},
  year      = {2015},
  url       = {http://doi.acm.org/10.1145/2806883},
  doi       = {10.1145/2806883},
  timestamp = {Fri, 09 Dec 2016 13:15:44 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jacm/Roughgarden15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{Roughgarden09,
  author    = {Tim Roughgarden},
  title     = {Intrinsic robustness of the price of anarchy},
  booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
               {STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
  pages     = {513--522},
  year      = {2009},
  crossref  = {DBLP:conf/stoc/2009},
  url       = {http://doi.acm.org/10.1145/1536414.1536485},
  doi       = {10.1145/1536414.1536485},
  timestamp = {Fri, 05 Jun 2009 09:34:35 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/Roughgarden09},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{BulowK96,
	Author = {Bulow, Jeremy and Klemperer, Paul},
	Date-Added = {2014-10-05 16:31:30 +0000},
	Date-Modified = {2014-10-05 16:31:53 +0000},
	Journal = {The American Economic Review},
	Pages = {180--194},
	Publisher = {JSTOR},
	Title = {Auctions Versus Negotiations},
	Year = {1996}}

@article{HartlineL15,
	Author = {Jason Hartline and Brendan Lucier},
	Journal = {The American Economic Review},
	Pages = {3102-3124},
	Title = {Non-Optimal Mechanism Design},
	Year = {2015}}


@inproceedings{ChenDOPSY15,
  author    = {Xi Chen and
               Ilias Diakonikolas and
               Anthi Orfanou and
               Dimitris Paparas and
               Xiaorui Sun and
               Mihalis Yannakakis},
  title     = {On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms},
  booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
               2015, Berkeley, CA, USA, 17-20 October, 2015},
  pages     = {1464--1479},
  year      = {2015},
  crossref  = {DBLP:conf/focs/2015},
  url       = {http://dx.doi.org/10.1109/FOCS.2015.93},
  doi       = {10.1109/FOCS.2015.93},
  timestamp = {Mon, 04 Jan 2016 13:44:40 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/focs/ChenDOPSY15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@book{GusfieldI89,
  title={The stable marriage problem: structure and algorithms},
  author={Dan Gusfield and Robert W. Irving},
  year={1989},
  publisher={MIT Press}
}

@incollection{CaiDW16e,
  author    = {Yang Cai and
               Constantinos Daskalakis and
               S. Matthew Weinberg},
  title     = {Reducing Bayesian Mechanism Design to Algorithm Design},
  booktitle = {Encyclopedia of Algorithms},
  pages     = {1801--1808},
  year      = {2016},
  url       = {http://dx.doi.org/10.1007/978-1-4939-2864-4_787},
  doi       = {10.1007/978-1-4939-2864-4_787},
  timestamp = {Thu, 06 Oct 2016 09:41:42 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/reference/algo/CaiDW16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{CaiDW11s,
  author    = {Yang Cai and
               Constantinos Daskalakis and
               S. Matthew Weinberg},
  title     = {On optimal multidimensional mechanism design},
  journal   = {SIGecom Exchanges},
  volume    = {10},
  number    = {2},
  pages     = {29--33},
  year      = {2011},
  url       = {http://doi.acm.org/10.1145/1998549.1998555},
  doi       = {10.1145/1998549.1998555},
  timestamp = {Thu, 06 Oct 2016 09:41:42 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/sigecom/CaiDW11},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{BabaioffILW14s,
  author    = {Moshe Babaioff and
               Nicole Immorlica and
               Brendan Lucier and
               S. Matthew Weinberg},
  title     = {A simple and approximately optimal mechanism for an additive buyer},
  journal   = {SIGecom Exchanges},
  volume    = {13},
  number    = {2},
  pages     = {31--35},
  year      = {2014},
  url       = {http://doi.acm.org/10.1145/2728732.2728736},
  doi       = {10.1145/2728732.2728736},
  timestamp = {Fri, 10 Apr 2015 16:47:13 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/sigecom/BabaioffILW14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{CaiDW16s,
  author    = {Yang Cai and Nikhil Devanur and S. Matthew Weinberg},
  title     = {A Duality Based Unified Approach to Bayesian Mechanism Design},
  journal   = {SIGecom Exchanges},
  year      = {2016}
}

@article{PsomasSW18,
author = {Christos-Alexandros Psomas and Ariel Schvartzman and S. Matthew Weinberg},
title = {Beyond Worst-Case Analysis of Multi-Item Auctions for Correlated Bidders},
journal = {Manuscript},
year = {2018}
}

@article{HoyIL16,
author = {Darrell Hoy and Nicole Immorlica and Brendan Lucier},
title = {On-Demand or Spot? Selling the Cloud to Risk-Averse Customers},
journal = {Manuscript},
year = {2016}
}

@article{Ellsberg61,
author = {Daniel Ellsberg},
title = {Risk, Ambiguity, and the Savage Axioms},
journal = {Quarterly Journal of Economics},
year = {1961},
volume = {75},
number = {4},
pages = {643--669}
}

@article{Allais53,
author = {Maurice Allais},
title = {Le Comportement de l'Homme Rationnel devant le Risque: Critique des Postulats et Axiomes de l'Ecole Americaine},
journal = {Econometrica},
year = {1953},
volume = {21},
number = {4},
pages = {503--546}
}

@inproceedings{DughmiHN14,
  author    = {Shaddin Dughmi and
               Li Han and
               Noam Nisan},
  title     = {Sampling and Representation Complexity of Revenue Maximization},
  booktitle = {Web and Internet Economics - 10th International Conference, {WINE}
               2014, Beijing, China, December 14-17, 2014. Proceedings},
  pages     = {277--291},
  year      = {2014},
  crossref  = {DBLP:conf/wine/2014},
  url       = {https://doi.org/10.1007/978-3-319-13129-0\_22},
  doi       = {10.1007/978-3-319-13129-0\_22},
  timestamp = {Tue, 27 Mar 2018 13:23:49 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/wine/DughmiHN14},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{FiatGKK16,
  author    = {Amos Fiat and
               Kira Goldner and
               Anna R. Karlin and
               Elias Koutsoupias},
  title     = {The FedEx Problem},
  booktitle = {Proceedings of the 2016 {ACM} Conference on Economics and Computation,
               {EC} '16, Maastricht, The Netherlands, July 24-28, 2016},
  pages     = {21--22},
  year      = {2016},
  crossref  = {DBLP:conf/sigecom/2016},
  url       = {http://doi.acm.org/10.1145/2940716.2940752},
  doi       = {10.1145/2940716.2940752},
  timestamp = {Fri, 22 Jul 2016 09:44:16 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/FiatGKK16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{ChawlaGMP18,
  author    = {Shuchi Chawla and
               Kira Goldner and
               J. Benjamin Miller and
               Emmanouil Pountourakis},
  title     = {Revenue Maximization with an Uncertainty-Averse Buyer},
  booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
  pages     = {2050--2068},
  year      = {2018},
  crossref  = {DBLP:conf/soda/2018},
  url       = {https://doi.org/10.1137/1.9781611975031.134},
  doi       = {10.1137/1.9781611975031.134},
  timestamp = {Thu, 04 Jan 2018 13:55:11 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/soda/0001GMP18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DevanurGSSW18,
author = {Nikhil Devanur and Kira Goldner and Raghuvansh Saxena and Ariel Schvartzman and S. Matthew Weinberg},
title = {Selling Partially-Ordered Items: Exploring the space between single- and multi-dimensional mechanism design},
journal = {Manuscript},
year = {2018}
}

@article{MaS15,
author = {Will Ma and David Simchi-Levi},
title = {Reaping the Benefits of Bundling under High Production Costs},
journal = {Manuscript},
year = {2015}
}

@inproceedings{Eyal15,
  author    = {Ittay Eyal},
  title     = {The Miner's Dilemma},
  booktitle = {2015 {IEEE} Symposium on Security and Privacy, {SP} 2015, San Jose,
               CA, USA, May 17-21, 2015},
  pages     = {89--103},
  year      = {2015},
  crossref  = {DBLP:conf/sp/2015},
  url       = {https://doi.org/10.1109/SP.2015.13},
  doi       = {10.1109/SP.2015.13},
  timestamp = {Fri, 26 May 2017 00:50:06 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sp/Eyal15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Feige09,
  author    = {Uriel Feige},
  title     = {On Maximizing Welfare When Utility Functions Are Subadditive},
  journal   = {{SIAM} J. Comput.},
  volume    = {39},
  number    = {1},
  pages     = {122--142},
  year      = {2009},
  url       = {https://doi.org/10.1137/070680977},
  doi       = {10.1137/070680977},
  timestamp = {Sat, 27 May 2017 14:22:58 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/siamcomp/Feige09},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{Feige06,
  author    = {Uriel Feige},
  title     = {On maximizing welfare when utility functions are subadditive},
  booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
               Seattle, WA, USA, May 21-23, 2006},
  pages     = {41--50},
  year      = {2006},
  crossref  = {DBLP:conf/stoc/2006},
  url       = {http://doi.acm.org/10.1145/1132516.1132523},
  doi       = {10.1145/1132516.1132523},
  timestamp = {Thu, 28 Sep 2006 09:38:26 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/Feige06},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DobzinskiNS10,
  author    = {Shahar Dobzinski and
               Noam Nisan and
               Michael Schapira},
  title     = {Approximation Algorithms for Combinatorial Auctions with Complement-Free
               Bidders},
  journal   = {Math. Oper. Res.},
  volume    = {35},
  number    = {1},
  pages     = {1--13},
  year      = {2010},
  url       = {https://doi.org/10.1287/moor.1090.0436},
  doi       = {10.1287/moor.1090.0436},
  timestamp = {Sun, 28 May 2017 13:24:37 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/mor/DobzinskiNS10},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DobzinskiNS05,
  author    = {Shahar Dobzinski and
               Noam Nisan and
               Michael Schapira},
  title     = {Approximation algorithms for combinatorial auctions with complement-free
               bidders},
  booktitle = {Proceedings of the 37th Annual {ACM} Symposium on Theory of Computing,
               Baltimore, MD, USA, May 22-24, 2005},
  pages     = {610--618},
  year      = {2005},
  crossref  = {DBLP:conf/stoc/2005},
  url       = {http://doi.acm.org/10.1145/1060590.1060681},
  doi       = {10.1145/1060590.1060681},
  timestamp = {Wed, 15 Feb 2006 09:55:49 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/DobzinskiNS05},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{SyrgkanisT13,
  author    = {Vasilis Syrgkanis and
               {\'{E}}va Tardos},
  title     = {Composable and efficient mechanisms},
  booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
               USA, June 1-4, 2013},
  pages     = {211--220},
  year      = {2013},
  crossref  = {DBLP:conf/stoc/2013},
  url       = {http://doi.acm.org/10.1145/2488608.2488635},
  doi       = {10.1145/2488608.2488635},
  timestamp = {Sun, 26 May 2013 10:49:33 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/SyrgkanisT13},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BabaioffGMM18,
  author    = {Moshe Babaioff and
               Yannai A. Gonczarowski and
               Yishay Mansour and
               Shay Moran},
  title     = {Are Two (Samples) Really Better Than One?},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {175},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219187},
  doi       = {10.1145/3219166.3219187},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/BabaioffGMM18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{RoughgardenS16,
  author    = {Tim Roughgarden and
               Okke Schrijvers},
  title     = {Ironing in the Dark},
  booktitle = {Proceedings of the 2016 {ACM} Conference on Economics and Computation,
               {EC} '16, Maastricht, The Netherlands, July 24-28, 2016},
  pages     = {1--18},
  year      = {2016},
  crossref  = {DBLP:conf/sigecom/2016},
  url       = {http://doi.acm.org/10.1145/2940716.2940723},
  doi       = {10.1145/2940716.2940723},
  timestamp = {Fri, 22 Jul 2016 09:44:16 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/RoughgardenS16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{SchrijversBBR16,
  author    = {Okke Schrijvers and
               Joseph Bonneau and
               Dan Boneh and
               Tim Roughgarden},
  title     = {Incentive Compatibility of Bitcoin Mining Pool Reward Functions},
  booktitle = {Financial Cryptography and Data Security - 20th International Conference,
               {FC} 2016, Christ Church, Barbados, February 22-26, 2016, Revised
               Selected Papers},
  pages     = {477--498},
  year      = {2016},
  crossref  = {DBLP:conf/fc/2016},
  url       = {https://doi.org/10.1007/978-3-662-54970-4\_28},
  doi       = {10.1007/978-3-662-54970-4\_28},
  timestamp = {Wed, 17 May 2017 11:13:47 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/fc/SchrijversBBR16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{HartlineHT14,
  author    = {Jason D. Hartline and
               Darrell Hoy and
               Sam Taggart},
  title     = {Price of anarchy for auction revenue},
  booktitle = {{ACM} Conference on Economics and Computation, {EC} '14, Stanford
               , CA, USA, June 8-12, 2014},
  pages     = {693--710},
  year      = {2014},
  crossref  = {DBLP:conf/sigecom/2014},
  url       = {http://doi.acm.org/10.1145/2600057.2602878},
  doi       = {10.1145/2600057.2602878},
  timestamp = {Wed, 02 Jul 2014 09:44:36 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/HartlineHT14},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{HartlineT16,
  author    = {Jason D. Hartline and
               Samuel Taggart},
  title     = {Non-Revelation Mechanism Design},
  journal   = {CoRR},
  volume    = {abs/1608.01875},
  year      = {2016},
  url       = {http://arxiv.org/abs/1608.01875},
  archivePrefix = {arXiv},
  eprint    = {1608.01875},
  timestamp = {Wed, 07 Jun 2017 14:40:49 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/corr/HartlineT16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@misc{TeutschR17,
  title={A scalable verification solution for blockchains},
  author={Jason Teutsch and Christian Reitwießner},
  year={2017},
  month={03},
  day={07},
  url={https://truebit.io/},
journal = {https://truebit.io/},
note = {https://truebit.io/}
}

@inproceedings{GiladHMVZ17,
  author    = {Yossi Gilad and
               Rotem Hemo and
               Silvio Micali and
               Georgios Vlachos and
               Nickolai Zeldovich},
  title     = {Algorand: Scaling Byzantine Agreements for Cryptocurrencies},
  booktitle = {Proceedings of the 26th Symposium on Operating Systems Principles,
               Shanghai, China, October 28-31, 2017},
  pages     = {51--68},
  year      = {2017},
  crossref  = {DBLP:conf/sosp/2017},
  url       = {http://doi.acm.org/10.1145/3132747.3132757},
  doi       = {10.1145/3132747.3132757},
  timestamp = {Thu, 19 Oct 2017 21:48:10 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sosp/GiladHMVZ17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{PassS17,
  author    = {Rafael Pass and
               Elaine Shi},
  title     = {FruitChains: {A} Fair Blockchain},
  booktitle = {Proceedings of the {ACM} Symposium on Principles of Distributed Computing,
               {PODC} 2017, Washington, DC, USA, July 25-27, 2017},
  pages     = {315--324},
  year      = {2017},
  crossref  = {DBLP:conf/podc/2017},
  url       = {http://doi.acm.org/10.1145/3087801.3087809},
  doi       = {10.1145/3087801.3087809},
  timestamp = {Fri, 21 Jul 2017 13:32:16 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/podc/PassS17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{LuuTKS15,
  author    = {Loi Luu and
               Jason Teutsch and
               Raghav Kulkarni and
               Prateek Saxena},
  title     = {Demystifying Incentives in the Consensus Computer},
  booktitle = {Proceedings of the 22nd {ACM} {SIGSAC} Conference on Computer and
               Communications Security, Denver, CO, USA, October 12-16, 2015},
  pages     = {706--719},
  year      = {2015},
  crossref  = {DBLP:conf/ccs/2015},
  url       = {http://doi.acm.org/10.1145/2810103.2813659},
  doi       = {10.1145/2810103.2813659},
  timestamp = {Wed, 11 Apr 2018 11:09:28 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/ccs/LuuTKS15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{ImmorlicaLPT17,
  author    = {Nicole Immorlica and
               Brendan Lucier and
               Emmanouil Pountourakis and
               Samuel Taggart},
  title     = {Repeated Sales with Multiple Strategic Buyers},
  booktitle = {Proceedings of the 2017 {ACM} Conference on Economics and Computation,
               {EC} '17, Cambridge, MA, USA, June 26-30, 2017},
  pages     = {167--168},
  year      = {2017},
  crossref  = {DBLP:conf/sigecom/2017},
  url       = {http://doi.acm.org/10.1145/3033274.3085130},
  doi       = {10.1145/3033274.3085130},
  timestamp = {Wed, 21 Jun 2017 09:41:38 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/ImmorlicaLPT17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DevanurHP16,
  author    = {Nikhil R. Devanur and
               Zhiyi Huang and
               Christos{-}Alexandros Psomas},
  title     = {The sample complexity of auctions with side information},
  booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
  pages     = {426--439},
  year      = {2016},
  crossref  = {DBLP:conf/stoc/2016},
  url       = {http://doi.acm.org/10.1145/2897518.2897553},
  doi       = {10.1145/2897518.2897553},
  timestamp = {Fri, 10 Jun 2016 10:47:01 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/Devanur0P16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{PapadimitriouPPR16,
  author    = {Christos H. Papadimitriou and
               George Pierrakos and
               Christos{-}Alexandros Psomas and
               Aviad Rubinstein},
  title     = {On the Complexity of Dynamic Mechanism Design},
  booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
  pages     = {1458--1475},
  year      = {2016},
  crossref  = {DBLP:conf/soda/2016},
  url       = {https://doi.org/10.1137/1.9781611974331.ch100},
  doi       = {10.1137/1.9781611974331.ch100},
  timestamp = {Wed, 24 May 2017 08:31:21 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/soda/PapadimitriouPP16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{ColeR14,
  author    = {Richard Cole and
               Tim Roughgarden},
  title     = {The sample complexity of revenue maximization},
  booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
               May 31 - June 03, 2014},
  pages     = {243--252},
  year      = {2014},
  crossref  = {DBLP:conf/stoc/2014},
  url       = {http://doi.acm.org/10.1145/2591796.2591867},
  doi       = {10.1145/2591796.2591867},
  timestamp = {Wed, 29 Mar 2017 16:45:26 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/ColeR14},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DhangwatnotaiRY15,
  author    = {Peerapong Dhangwatnotai and
               Tim Roughgarden and
               Qiqi Yan},
  title     = {Revenue maximization with a single sample},
  journal   = {Games and Economic Behavior},
  volume    = {91},
  pages     = {318--333},
  year      = {2015},
  url       = {https://doi.org/10.1016/j.geb.2014.03.011},
  doi       = {10.1016/j.geb.2014.03.011},
  timestamp = {Thu, 18 May 2017 09:52:38 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/geb/DhangwatnotaiRY15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{MorgensternR15,
  author    = {Jamie Morgenstern and
               Tim Roughgarden},
  title     = {On the Pseudo-Dimension of Nearly Optimal Auctions},
  booktitle = {Advances in Neural Information Processing Systems 28: Annual Conference
               on Neural Information Processing Systems 2015, December 7-12, 2015,
               Montreal, Quebec, Canada},
  pages     = {136--144},
  year      = {2015},
  crossref  = {DBLP:conf/nips/2015},
  url       = {http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions},
  timestamp = {Fri, 08 Apr 2016 19:32:53 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/nips/MorgensternR15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BalcanSV18,
  author    = {Maria{-}Florina Balcan and
               Tuomas Sandholm and
               Ellen Vitercik},
  title     = {A General Theory of Sample Complexity for Multi-Item Profit Maximization},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {173--174},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219217},
  doi       = {10.1145/3219166.3219217},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/BalcanSV18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{MorgensternR16,
  author    = {Jamie Morgenstern and
               Tim Roughgarden},
  title     = {Learning Simple Auctions},
  booktitle = {Proceedings of the 29th Conference on Learning Theory, {COLT} 2016,
               New York, USA, June 23-26, 2016},
  pages     = {1298--1318},
  year      = {2016},
  crossref  = {DBLP:conf/colt/2016},
  url       = {http://jmlr.org/proceedings/papers/v49/morgenstern16.html},
  timestamp = {Wed, 13 Jul 2016 17:28:13 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/colt/MorgensternR16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{Rubinstein16a,
  author    = {Aviad Rubinstein},
  title     = {On the Computational Complexity of Optimal Simple Mechanisms},
  booktitle = {Proceedings of the 2016 {ACM} Conference on Innovations in Theoretical
               Computer Science, Cambridge, MA, USA, January 14-16, 2016},
  pages     = {21--28},
  year      = {2016},
  crossref  = {DBLP:conf/innovations/2016},
  url       = {http://doi.acm.org/10.1145/2840728.2840736},
  doi       = {10.1145/2840728.2840736},
  timestamp = {Mon, 18 Jan 2016 19:48:30 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/innovations/Rubinstein16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{CaiD11,
  author    = {Yang Cai and
               Constantinos Daskalakis},
  title     = {Extreme-Value Theorems for Optimal Multidimensional Pricing},
  booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
               2011, Palm Springs, CA, USA, October 22-25, 2011},
  pages     = {522--531},
  year      = {2011},
  crossref  = {DBLP:conf/focs/2011},
  url       = {https://doi.org/10.1109/FOCS.2011.76},
  doi       = {10.1109/FOCS.2011.76},
  timestamp = {Fri, 19 May 2017 01:25:59 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/focs/CaiD11},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{CaiD15,
  author    = {Yang Cai and
               Constantinos Daskalakis},
  title     = {Extreme value theorems for optimal multidimensional pricing},
  journal   = {Games and Economic Behavior},
  volume    = {92},
  pages     = {266--305},
  year      = {2015},
  url       = {https://doi.org/10.1016/j.geb.2015.02.003},
  doi       = {10.1016/j.geb.2015.02.003},
  timestamp = {Thu, 18 May 2017 09:52:37 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/geb/CaiD15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{FuLLT18,
  author    = {Hu Fu and
               Christopher Liaw and
               Pinyan Lu and
               Zhihao Gavin Tang},
  title     = {The Value of Information Concealment},
  booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
  pages     = {2533--2544},
  year      = {2018},
  crossref  = {DBLP:conf/soda/2018},
  url       = {https://doi.org/10.1137/1.9781611975031.162},
  doi       = {10.1137/1.9781611975031.162},
  timestamp = {Thu, 04 Jan 2018 13:55:11 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/soda/FuLLT18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{BrownCohenNPW18,
author = {Jonah Brown-Cohen and Arvind Narayanan and Christos-Alexandros Psomas and S. Matthew Weinberg},
title = {Formal Barriers to Longest-Chain Proof-of-Stake Protocols},
journal = {Manuscript},
year = {2018}
}

@article{DaianPS17,
  author    = {Phil Daian and
               Rafael Pass and
               Elaine Shi},
  title     = {Snow White: Provably Secure Proofs of Stake},
  journal   = {{IACR} Cryptology ePrint Archive},
  volume    = {2016},
  pages     = {919},
  year      = {2016},
  url       = {http://eprint.iacr.org/2016/919},
  timestamp = {Thu, 08 Jun 2017 14:26:43 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/iacr/BentovPS16a},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{ChenM16,
author = {Jing Chen and Silvio Micali},
title = {Algorand},
journal = {Manuscript},
year = {2016}
}

@inproceedings{LiuP18,
  author    = {Siqi Liu and
               Christos{-}Alexandros Psomas},
  title     = {On the Competition Complexity of Dynamic Mechanism Design},
  booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
  pages     = {2008--2025},
  year      = {2018},
  crossref  = {DBLP:conf/soda/2018},
  url       = {https://doi.org/10.1137/1.9781611975031.131},
  doi       = {10.1137/1.9781611975031.131},
  timestamp = {Thu, 04 Jan 2018 13:55:11 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/soda/LiuP18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BrustleCWZ17,
  author    = {Johannes Brustle and
               Yang Cai and
               Fa Wu and
               Mingfei Zhao},
  title     = {Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms},
  booktitle = {Proceedings of the 2017 {ACM} Conference on Economics and Computation,
               {EC} '17, Cambridge, MA, USA, June 26-30, 2017},
  pages     = {589--590},
  year      = {2017},
  crossref  = {DBLP:conf/sigecom/2017},
  url       = {http://doi.acm.org/10.1145/3033274.3085148},
  doi       = {10.1145/3033274.3085148},
  timestamp = {Wed, 01 Nov 2017 09:38:36 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/BrustleCWZ17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{BeyhaghiW18,
author = {Hedyeh Beyhaghi and S. Matthew Weinberg},
title = {Benchmark-Optimal Competition Complexity for Additive Buyers},
journal = {Manuscript},
year = {2018}
}

@article{DaskalakisDT17,
  author    = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title     = {Strong Duality for a Multiple-Good Monopolist},
  journal   = {Econometrica},
  volume    = {85},
  pages     = {735-767},
  year      = {2017},
  number = {3}
}

@article{HartN17,
  author    = {Sergiu Hart and
               Noam Nisan},
  title     = {Approximate revenue maximization with multiple items},
  journal   = {J. Economic Theory},
  volume    = {172},
  pages     = {313--347},
  year      = {2017},
  url       = {https://doi.org/10.1016/j.jet.2017.09.001},
  doi       = {10.1016/j.jet.2017.09.001},
  timestamp = {Tue, 28 Nov 2017 16:10:57 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jet/HartN17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{AuerCFS02,
author = {P. Auer and N. Cesa-Bianchi and Y. Freund and R. E. Schapire},
title = {The nonstochastic multiarmed bandit problem},
journal = {SIAM Journal of Computing},
volume = {32},
number = {1},
year = {2002},
pages = {48-77}
}

@INPROCEEDINGS{Hannan57,
    author = {James Hannan},
    title = {Approximation to bayes risk in repeated play},
    booktitle = {Contributions to the Theory of Games},
    year = {1957},
    pages = {3:97-139}
}

@article{RoughgardenST17,
  author    = {Tim Roughgarden and
               Vasilis Syrgkanis and
               {\'{E}}va Tardos},
  title     = {The Price of Anarchy in Auctions},
  journal   = {J. Artif. Intell. Res.},
  volume    = {59},
  pages     = {59--101},
  year      = {2017},
  url       = {https://doi.org/10.1613/jair.5272},
  doi       = {10.1613/jair.5272},
  timestamp = {Wed, 21 Jun 2017 14:58:47 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/jair/RoughgardenST17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{HassidimKMN11,
  author    = {Avinatan Hassidim and
               Haim Kaplan and
               Yishay Mansour and
               Noam Nisan},
  title     = {Non-price equilibria in markets of discrete goods},
  booktitle = {Proceedings 12th {ACM} Conference on Electronic Commerce (EC-2011),
               San Jose, CA, USA, June 5-9, 2011},
  pages     = {295--296},
  year      = {2011},
  crossref  = {DBLP:conf/sigecom/2011},
  url       = {http://doi.acm.org/10.1145/1993574.1993619},
  doi       = {10.1145/1993574.1993619},
  timestamp = {Mon, 24 Feb 2014 16:09:47 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/HassidimKMN11},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{FeldmanFGL13,
  author    = {Michal Feldman and
               Hu Fu and
               Nick Gravin and
               Brendan Lucier},
  title     = {Simultaneous auctions are (almost) efficient},
  booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
               USA, June 1-4, 2013},
  pages     = {201--210},
  year      = {2013},
  crossref  = {DBLP:conf/stoc/2013},
  url       = {http://doi.acm.org/10.1145/2488608.2488634},
  doi       = {10.1145/2488608.2488634},
  timestamp = {Sun, 26 May 2013 10:49:33 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/FeldmanFGL13},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BhawalkarR11,
  author    = {Kshipra Bhawalkar and
               Tim Roughgarden},
  title     = {Welfare Guarantees for Combinatorial Auctions with Item Bidding},
  booktitle = {Proceedings of the Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2011, San Francisco, California, USA, January 23-25,
               2011},
  pages     = {700--709},
  year      = {2011},
  crossref  = {DBLP:conf/soda/2011},
  url       = {https://doi.org/10.1137/1.9781611973082.55},
  doi       = {10.1137/1.9781611973082.55},
  timestamp = {Wed, 24 May 2017 08:31:21 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/soda/BhawalkarR11},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{KalaiV05,
 author = {Kalai, Adam and Vempala, Santosh},
 title = {Efficient Algorithms for Online Decision Problems},
 journal = {J. Comput. Syst. Sci.},
 issue_date = {October 2005},
 volume = {71},
 number = {3},
 month = oct,
 year = {2005},
 issn = {0022-0000},
 pages = {291--307},
 numpages = {17},
 url = {http://dx.doi.org/10.1016/j.jcss.2004.10.016},
 doi = {10.1016/j.jcss.2004.10.016},
 acmid = {1113189},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 keywords = {Decision theory, Hannan's algorithm, Online algorithms, Optimization},
} 

@INPROCEEDINGS{KalaiV02,
    author = {Adam Kalai and Santosh Vempala},
    title = {Geometric Algorithms for Online Optimization},
    booktitle = {Journal of Computer and System Sciences},
    year = {2002},
    pages = {26--40}
}

@inproceedings{NekipelovST15,
 author = {Nekipelov, Denis and Syrgkanis, Vasilis and Tardos, Eva},
 title = {Econometrics for Learning Agents},
 booktitle = {Proceedings of the Sixteenth ACM Conference on Economics and Computation},
 series = {EC '15},
 year = {2015},
 isbn = {978-1-4503-3410-5},
 location = {Portland, Oregon, USA},
 pages = {1--18},
 numpages = {18},
 url = {http://doi.acm.org/10.1145/2764468.2764522},
 doi = {10.1145/2764468.2764522},
 acmid = {2764522},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {econometrics, no-regret learning, sponsored search, value inference},
} 


@article{AroraHK12,
 author = {Arora, Sanjeev and Hazan, Elad and Kale, Satyen},
 title = {The Multiplicative Weights Update Method: a Meta-Algorithm and Applications},
 year = {2012},
 pages = {121--164},
 doi = {10.4086/toc.2012.v008a006},
 publisher = {Theory of Computing},
 journal = {Theory of Computing},
 volume = {8},
 number = {6},
 URL = {http://www.theoryofcomputing.org/articles/v008a006},
}
@article{BubeckC12,
  author    = {S{\'{e}}bastien Bubeck and
               Nicol{\`{o}} Cesa{-}Bianchi},
  title     = {Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit
               Problems},
  journal   = {Foundations and Trends in Machine Learning},
  volume    = {5},
  number    = {1},
  pages     = {1--122},
  year      = {2012},
  url       = {http://dx.doi.org/10.1561/2200000024},
  doi       = {10.1561/2200000024},
  timestamp = {Fri, 21 Dec 2012 13:23:38 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/ftml/BubeckC12},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@inproceedings{BravermanMSW18,
  author    = {Mark Braverman and
               Jieming Mao and
               Jon Schneider and
               Matt Weinberg},
  title     = {Selling to a No-Regret Buyer},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {523--538},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219233},
  doi       = {10.1145/3219166.3219233},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/BravermanMSW18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{KalodnerGCWF18,
title ={Arbitrum: Scalable Smart Contracts},
author = {Harry Kalodner and Steven Goldfeder and Xiaoqi Chen and S. Matthew Weinberg and Edward W. Felten},
booktitle = {Proceedings of the 27th USENIX Security Symposium (USENIX)},
year = {2018}
}



@inproceedings{HuangWZJC17,
  author    = {Zhe Huang and
               S. Matthew Weinberg and
               Liang Zheng and
               Carlee Joe{-}Wong and
               Mung Chiang},
  title     = {Discovering valuations and enforcing truthfulness in a deadline-aware
               scheduler},
  booktitle = {2017 {IEEE} Conference on Computer Communications, {INFOCOM} 2017,
               Atlanta, GA, USA, May 1-4, 2017},
  pages     = {1--9},
  year      = {2017},
  crossref  = {DBLP:conf/infocom/2017},
  url       = {https://doi.org/10.1109/INFOCOM.2017.8056975},
  doi       = {10.1109/INFOCOM.2017.8056975},
  timestamp = {Wed, 11 Oct 2017 15:10:57 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/infocom/HuangWZJC17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{CharlesDS16,
  author    = {Denis Xavier Charles and
               Nikhil R. Devanur and
               Balasubramanian Sivan},
  title     = {Multi-Score Position Auctions},
  booktitle = {Proceedings of the Ninth {ACM} International Conference on Web Search
               and Data Mining, San Francisco, CA, USA, February 22-25, 2016},
  pages     = {417--425},
  year      = {2016},
  crossref  = {DBLP:conf/wsdm/2016},
  url       = {http://doi.acm.org/10.1145/2835776.2835822},
  doi       = {10.1145/2835776.2835822},
  timestamp = {Mon, 08 Feb 2016 15:38:27 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/wsdm/CharlesDS16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@inproceedings{ImpagliazzoK10,
  author    = {Russell Impagliazzo and
               Valentine Kabanets},
  editor    = {Maria J. Serna and
               Ronen Shaltiel and
               Klaus Jansen and
               Jos{\'{e}} D. P. Rolim},
  title     = {Constructive Proofs of Concentration Bounds},
  booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
               and Techniques, 13th International Workshop, {APPROX} 2010, and 14th
               International Workshop, {RANDOM} 2010, Barcelona, Spain, September
               1-3, 2010. Proceedings},
  series    = {Lecture Notes in Computer Science},
  volume    = {6302},
  pages     = {617--631},
  publisher = {Springer},
  year      = {2010},
  url       = {http://dx.doi.org/10.1007/978-3-642-15369-3_46},
  doi       = {10.1007/978-3-642-15369-3_46},
  timestamp = {Sun, 29 Aug 2010 20:35:26 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/approx/ImpagliazzoK10},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{PanconesiS97,
  author    = {Alessandro Panconesi and
               Aravind Srinivasan},
  title     = {Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding
               Bounds},
  journal   = {{SIAM} J. Comput.},
  volume    = {26},
  number    = {2},
  pages     = {350--368},
  year      = {1997},
  url       = {http://dx.doi.org/10.1137/S0097539793250767},
  doi       = {10.1137/S0097539793250767},
  timestamp = {Mon, 12 Sep 2011 16:10:08 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/siamcomp/PanconesiS97},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@inproceedings{Gonczarowski14,
author = {Yannai Gonczarowski},
title = {Manipulation of Stable Matchings using Minimal Blacklists},
booktitle = {ACM Conference on Economics and Computation (EC)},
year = {2014}
}

@article{GonczarowskiF13,
author = {Yannai Gonczarowski and Ehud Friedgut},
title = {Sisterhood in the Gale-Shapley Matching Algorithm},
journal = {The Electronic Journal of Combinatorics},
volume = {20},
number = {2},
year = {2013}
}

@article{AshlagiKL16,
title = {Unbalanced Random Matching Markets: the Stark Effect of Competition}, 
journal = {Journal of Political Economy},
year = {Forthcoming},
author = {Itai Ashlagi, Yash Kanoria, and Jacob Leshno}
}

@article{GaleS62,
author = {D. Gale and Lloyd S. Shapley},
title = {College Admissions and the Stability of Marriage},
journal = {American Mathematical Monthly},
volume = {69},
pages = {9-14},
year = {1962}
}

@article{McVitieW71,
title = {The stable marriage problem},
volume = {14},
number = {7},
year = {1971},
author = {D. G. McVitie and L. B. Wilson},
journal = {Communications of the ACM}
}

@article{Roth82,
author = {Alvin E. Roth},
title = {The economics of matching: stability and incentives},
journal = {Mathematics of Operations Research},
volume = {7},
number = {4},
year = {1982},
pages = {617-628}
}

@article{Knuth76,
author = {D.E. Knuth},
title = {Mariages Stables et leurs relations avec d'autres probl\`{e}mes combinatoires},
year = {1976},
journal = {Montr\'{e}al: Les presses de l'Universit\'{e} de Montr\'{e}al}
}

@article{Roth84,
author = {Alvin E. Roth},
title = {The evolution of the labor market for medical interns and residents: A case study in game theory},
journal = {Journal of Political Economy},
year = {1984},
volume = {92},
pages = {991-1016}
}

@article{GaleS85,
author = {David Gale and Marilda Sotomayor},
volume = {11},
number = {3},
title = {Some remarks on the stable matching problem},
journal = {Discrete Applied Mathematics},
pages = {223-232},
year = {1985}
}


@article{PiniRVW11,
author = {M.S. Pini and F. Rossi and K. B. Venable and T. Walsh},
title = {Manipulation complexity and gender neutrality in stable marriage procedures},
journal = {Autonomous Agents and Multi-Agent Systems},
volume = {22},
number = {1},
pages = {183-199},
year = {2011}
}

@article{EzraFNTW18,
author = {Tomer Ezra and Michal Feldman and Eric Neyman and Inbal Talgam-Cohen and S. Matthew Weinberg},
title = {Two Player Combinatorial Auctions are Hard},
year = {2018},
journal = {Manuscript}
}

@article{PatelW18,
author = {Yash Patel and S. Matthew Weinberg},
title = {Accounting for Currency Devaluation in Cryptocurrency Selfish Mining},
year = {2018},
journal = {Manuscript}
}

@article{ArnostiJK15,
author = {Nick Arnosti and Ramesh Johari and Yash Kanoria},
title = {Managing Congestion in Dynamic Matching Markets},
year = {2015},
journal = {Manuscript},
misc = {\url{http://ssrn.com/abstract=2427960}}
}

@article{AshlagiS14,
author = {Itai Ashlagi and Peng Shi},
title = {Optimal Allocation Without Money: An Engineeringn Approach},
journal = {Management Science},
pages = {1078-1097},
year = {2014}
}

@article{KobayashiM09,
title = {Successful Manipulation in Stable Marriage Model with Complete Preference Lists},
journal = {IEIC Transactions on Information and Systems},
author = {H. Kobayashi and T. Matsui},
year = {2009}
}

@article{KojimaP09,
author = {Fujito Kojima and Parag A. Pathak},
journal = {American Economic Review},
title = {Incentives and Stability in Large Two-Sided Matching Markets},
year = {2009}
}

@article{ColesCLNRS10,
author = {Peter Coles and John Cawley and Phillip B. Levine and Muriel Niederle and Alvin E. Roth and John J. Siegfried},
year = {2010},
title = {The job market for new economists: A market design perspective.},
journal = {Journal of Economic Perspectives},
volume = {24}, 
number = {4},
pages = {187-206}
}

@article{HalaburdaPPY16,
author = {Hanna Halaburda and Mikolaj Jan Piskorski and Pinar Yildrim},
title = {Competing by Restricting Choice: The Case of Search Platforms},
year = {2016},
journal = {Harvard Business School Strategy Unit Working Paper No. 10-098},
misc = {\url{http://ssrn.com/abstract=1610187}}
}

@article{RothX97,
author = {Alvin E. Roth and Xiaolin Xing},
title = {Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists},
journal = {Journal of Political Economy},
year = {1997},
volume = {105},
pages = {184-329}
}
@article{CheK15,
author = {Yeon-Koo Che and Youngwoo Koh},
title = {Decentalized College Admissions},
journal = {Journal of Political Economy},
year = {Forthcoming}
}

@inproceedings{AshlagiN16,
author = {Itai Ashlagi and Afshin Nikzad},
title = {What matters in tie-breaking rules? How Competition guides design},
year = {2016},
booktitle = {ACM Conference on Economics and Computation (EC)}
}

@inproceedings{AshlagiNR15,
author = {Itai Ashlagi and Afshin Nikzad and Assaf Romm},
title = {Assigning more students to their top choices: A tiebreaking rule comparison},
booktitle = {ACM Conference on Economics and Computation (EC)},
year = {2015}
}

@article{ImmorlicaM15,
author = {Nicole Immorlica and Mohammad Mahdian},
journal = {Transactions on Economics and Computation},
year = {2015},
title = {Incentives in Large Random Two-Sided Markets}
}

@article{LeeNKK11,
author = {Soohyung Lee and Muriel Niederle and Hye-Rim Kim and Woo-Keum Kim},
title = {Propose With a Rose? Signaling in Internet Dating Markets},
journal = {National Bureau of Economic Research Working Paper 17340},
Year = {2011}
}
@article{LeeN15,
author = {Soohyung Lee and Muriel Niederle},
title = {Propose with a Rose? Signaling in Internet Dating Markets},
journal = {Experimental Economics},
year = {2015},
volume = {18},
number = {4},
pages = {731-755}
}

@article{Pittel89,
author = {Boris Pittel},
year = {1989},
title = {The average number of stable matchings},
journal = {SIAM Journal on Discrete Mathematics},
volume = {2},
number = {4},
pages = {530-549}
}

@article{Arnosti16,
author = {Nick Arnosti},
title = {Centralized Clearinghouse Design: A Quantity-Quality Tradeoff},
year = {2016},
journal = {Job Market Paper},
misc = {\url{http://ssrn.com/abstract=2571527}}
}

@inproceedings{KnuthMP90,
author = {Don E. Knuth and Rajeev Motwani and Boris Pittel},
title = {Stable Husbands},
booktitle = {Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {1990}
}

@inproceedings{BateniHSZ13,
  author    = {MohammadHossein Bateni and
               Nima Haghpanah and
               Balasubramanian Sivan and
               Morteza Zadimoghaddam},
  title     = {Revenue Maximization with Nonexcludable Goods},
  booktitle = {the 9th International Conference on Web and Internet Economics (WINE)},
  year = {2013}
  }


@inproceedings{SchneiderSW17,
  author    = {Jon Schneider and
               Ariel Schvartzman and
               S. Matthew Weinberg},
  title     = {Condorcet-Consistent and Approximately Strategyproof Tournament Rules},
  booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
               2017, January 9-11, 2017, Berkeley, CA, {USA}},
  pages     = {35:1--35:20},
  year      = {2017},
  crossref  = {DBLP:conf/innovations/2017},
  url       = {https://doi.org/10.4230/LIPIcs.ITCS.2017.35},
  doi       = {10.4230/LIPIcs.ITCS.2017.35},
  timestamp = {Wed, 29 Nov 2017 11:44:43 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/innovations/SchneiderSW17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BravermanMW16,
  author    = {Mark Braverman and
               Jieming Mao and
               S. Matthew Weinberg},
  title     = {Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial
               Auctions},
  booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
  pages     = {1444--1457},
  year      = {2016},
  crossref  = {DBLP:conf/soda/2016},
  url       = {https://doi.org/10.1137/1.9781611974331.ch99},
  doi       = {10.1137/1.9781611974331.ch99},
  timestamp = {Wed, 24 May 2017 08:31:21 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/soda/BravermanMW16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DevanurMSW15,
  author    = {Nikhil R. Devanur and
               Jamie Morgenstern and
               Vasilis Syrgkanis and
               S. Matthew Weinberg},
  title     = {Simple Auctions with Simple Strategies},
  booktitle = {Proceedings of the Sixteenth {ACM} Conference on Economics and Computation,
               {EC} '15, Portland, OR, USA, June 15-19, 2015},
  pages     = {305--322},
  year      = {2015},
  crossref  = {DBLP:conf/sigecom/2015},
  url       = {http://doi.acm.org/10.1145/2764468.2764484},
  doi       = {10.1145/2764468.2764484},
  timestamp = {Sun, 14 Jun 2015 19:51:57 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/DevanurMSW15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BravermanMW16,
  author    = {Mark Braverman and
               Jieming Mao and
               S. Matthew Weinberg},
  title     = {Parallel algorithms for select and partition with noisy comparisons},
  booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
  pages     = {851--862},
  year      = {2016},
  crossref  = {DBLP:conf/stoc/2016},
  url       = {http://doi.acm.org/10.1145/2897518.2897642},
  doi       = {10.1145/2897518.2897642},
  timestamp = {Fri, 10 Jun 2016 10:47:01 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/BravermanMW16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{FeldmanILW14,
  author    = {Michal Feldman and
               Nicole Immorlica and
               Brendan Lucier and
               S. Matthew Weinberg},
  title     = {Reaching Consensus via Non-Bayesian Asynchronous Learning in Social
               Networks},
  booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
               and Techniques, {APPROX/RANDOM} 2014, September 4-6, 2014, Barcelona,
               Spain},
  pages     = {192--208},
  year      = {2014},
  crossref  = {DBLP:conf/approx/2014},
  url       = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.192},
  doi       = {10.4230/LIPIcs.APPROX-RANDOM.2014.192},
  timestamp = {Tue, 23 May 2017 01:11:00 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/approx/FeldmanILW14},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{HaghpanahIMM11,
  author    = {Nima Haghpanah and
               Nicole Immorlica and
               Vahab S. Mirrokni and
               Kamesh Munagala},
  title     = {Optimal auctions with positive network externalities},
  booktitle = {the 12th ACM Conference on Electronic Commerce (EC)},
  year      = {2011}
}

@inproceedings{AzarKW14,
  author    = {Pablo D. Azar and Robert Kleinberg and S. Matthew Weinberg},
  title     = {{Prophet Inequalities with Limited Information}},
  booktitle = {the Twenty-Fifth Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2014}
}

@inproceedings{Yao15,
  author    = {Andrew Chi-Chih Yao},
  title     = {{An n-to-1 bidder reduction for multi-item auctions and its applications}},
  booktitle = {the Twenty-Sixth Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2015}
}


@inproceedings{AsadpourFS08,
  author    = {Arash Asadpour and
               Uriel Feige and
               Amin Saberi},
  title     = {Santa Claus Meets Hypergraph Matchings},
  booktitle = {the 12th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM)},
  year      = {2008}
}

@inproceedings{BansalS06,
  title={The santa claus problem},
  author={Bansal, Nikhil and Sviridenko, Maxim},
  booktitle={the 38th annual ACM symposium on Theory of computing (STOC)},
  pages={31--40},
  year={2006}
}
@inproceedings{BabaioffILW14,
  author    = {Moshe Babaioff and Nicole Immorlica and Brendan Lucier and S. Matthew Weinberg},
  title     = {A Simple and Approximately Optimal Mechanism for an Additive Buyer},
  booktitle = {the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2014}
}

@inproceedings{KhotP07,
  title={Approximation algorithms for the max-min allocation problem},
  author={Khot, Subhash and Ponnuswami, Ashok Kumar},
  booktitle={the 11th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM)},
  year={2007}
}

@article{LiY13,
	Author = {Xinye Li and Andrew Chi-Chih Yao},
	Date-Added = {2014-09-23 20:55:29 +0000},
	Date-Modified = {2014-09-23 20:58:34 +0000},
	Journal = {Proceedings of the National Academy of Sciences},
	Number = {28},
	Pages = {11232-11237},
	Title = {On Revenue Maximization for Selling Multiple Independently Distributed Items},
	Volume = {110},
	Year = {2013}}

@inproceedings{BateniCG09,
  title={Maxmin allocation via degree lower-bounded arborescences},
  author={Bateni, MohammadHossein and Charikar, Moses and Guruswami, Venkatesan},
  booktitle={the 41st annual ACM symposium on Theory of Computing (STOC)},
  pages={543--552},
  year={2009}
}
@article{BravermanMW15,
  author    = {Mark Braverman and Jieming Mao and S. Matthew Weinberg},
  title     = {Parallel Algorithms for Select and Partition with Noisy Comparisons},
  journal = {In Submission},
  year      = {2015}
}

@inproceedings{BateniDHS15,
author = {MohammadHossein Bateni and Sina Dehghani and MohammadTaghi Hajiaghayi and Saeed Seddighin},
title = {Revenue Maximization for Selling Multiple Correlated Items},
booktitle = {the 23rd Annual European Symposium on Algorithms (ESA)},
year = {2015}
}

@inproceedings{ChakrabartyCK09,
  title={On allocating goods to maximize fairness},
  author={Chakrabarty, Deeparnab and Chuzhoy, Julia and Khanna, Sanjeev},
  booktitle={50th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year={2009}
}

@book{BramsT96,
  title={Fair Division: From cake-cutting to dispute resolution},
  author={Brams, Steven J and Taylor, Alan D},
  year={1996},
  publisher={Cambridge University Press}
}

@article{Steinhaus48,
  title={The problem of fair division},
  author={Steinhaus, Hugo},
  journal={Econometrica},
  volume={16},
  number={1},
  year={1948}
}

@article{ShmoysT93b,
  title={An approximation algorithm for the generalized assignment problem},
  author={Shmoys, David B and Tardos, {\'E}va},
  journal={Mathematical Programming},
  volume={62},
  number={1-3},
  pages={461--474},
  year={1993},
  publisher={Springer}
}

@inproceedings{AsadpourS07,
  author    = {Arash Asadpour and Amin Saberi},
  title     = {An approximation algorithm for max-min fair allocation of indivisible goods},
  booktitle = {the 39th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2007}
}

@article{BezakovaD05,
  author    = {Ivona Bez{\'a}kov{\'a} and
               Varsha Dani},
  title     = {Allocating indivisible goods},
  journal   = {SIGecom Exchanges},
  volume    = {5},
  number    = {3},
  year      = {2005},
  pages     = {11-18}
}

@article{AshlagiDL12,
  title={Optimal lower bounds for anonymous scheduling mechanisms},
  author={Ashlagi, Itai and Dobzinski, Shahar and Lavi, Ron},
  journal={Mathematics of Operations Research},
  volume={37},
  number={2},
  pages={244--258},
  year={2012},
  publisher={INFORMS}
}

@inproceedings{ChristodoulouK10,
  author    = {George Christodoulou and
               Annam{\'a}ria Kov{\'a}cs},
  title     = {{A Deterministic Truthful PTAS for Scheduling Related Machines}},
  booktitle = {the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2010}
}

@inproceedings{ChristodoulouKK07,
  author    = {George Christodoulou and
               Elias Koutsoupias and
               Annam{\'a}ria Kov{\'a}cs},
  title     = {{Mechanism Design for Fractional Scheduling on Unrelated
               Machines}},
  booktitle = {the 34th International Colloquium on Automata, Languages and Programming (ICALP)},
  year      = {2007}
}

@inproceedings{LuY08a,
  author    = {Pinyan Lu and Changyuan Yu},
  title     = {{An Improved Randomized Truthful Mechanism for Scheduling
               Unrelated Machines}},
  booktitle = {the 25th Annual Symposium on Theoretical Aspects
               of Computer Science (STACS)},
  year      = {2008}
  }

@inproceedings{LuY08b,
  author    = {Pinyan Lu and
               Changyuan Yu},
  title     = {{Randomized Truthful Mechanisms for Scheduling Unrelated
               Machines}},
  booktitle = {the 4th International Workshop on Internet and Network Economics (WINE)},
  year      = {2008}
}


@inproceedings{Lu09,
  author    = {Pinyan Lu},
  title     = {{On 2-Player Randomized Mechanisms for Scheduling}},
  booktitle = {the 5th International Workshop on Internet and Network Economics (WINE)},
  year      = {2009}
}

@inproceedings{MualemS07,
  author    = {Ahuva Mu'alem and
               Michael Schapira},
  title     = {Setting lower bounds on truthfulness: extended abstract},
  booktitle = {the 18th Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2007}
}



@inproceedings{DhangwatnotaiDDR08,
  author    = {Peerapong Dhangwatnotai and
               Shahar Dobzinski and
               Shaddin Dughmi and
               Tim Roughgarden},
  title     = {{Truthful Approximation Schemes for Single-Parameter Agents}},
  booktitle = {the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2008}
}

@inproceedings{ArcherT01,
  author    = {Aaron Archer and
               {\'E}va Tardos},
  title     = {{Truthful Mechanisms for One-Parameter Agents}},
  booktitle = {the 42nd Annual Symposium on Foundations of Computer Science (FOCS)},
  year      = {2001}
}

@inproceedings{KarpP80,
  author    = {Richard M. Karp and Christos H. Papadimitriou},
  title     = {{On Linear Characterizations of Combinatorial Optimization Problems}},
  booktitle = {the 21st Annual Symposium on Foundations of Computer Science (FOCS)},
  year      = {1980}
}



@article{GrotschelLS81,
  author    = {Martin Gr{\"o}tschel and
               L{\'a}szl{\'o} Lov{\'a}sz and
               Alexander Schrijver},
  title     = {{The Ellipsoid Method and its Consequences in Combinatorial Optimization}},
  journal   = {Combinatorica},
  volume    = {1},
  number    = {2},
  year      = {1981},
  pages     = {169-197}
}

@book{Hochbaum96,
  title={{Approximation algorithms for NP-hard problems}},
  author={Hochbaum, Dorit S},
  year={1996},
  publisher={PWS Publishing Co.}
}

@article{RochetC98,
author = {Jean-Charles Rochet and Philippe Chone},
title = {Ironing, Sweeping, and Multidimensional Screening},
journal = {Econometrica},
year = {1998},
volume = {66},
number = {4},
pages = {783-826}
}

@article{Thanassoulis04,
author = {John Thanassoulis},
title = {Haggling over substitutes},
journal = {Journal of Economic Theory},
volume = {117},
pages = {217-245},
year = {2004}
}

@article{GulS99,
author = {Farak Gul and Ennio Stacchetti},
title = {Walrasian Equilibrium with Gross Substitutes},
journal = {Journal of Economic Theory},
year = {1999}
}

@inproceedings{AKV,
  author    = {Timothy G. Abbott and Daniel Kane and Paul Valiant},
  title     = {On the {C}omplexity of {T}wo-{P}layer {W}in-{L}ose {G}ames},
  booktitle = {the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2005}
}

@article{HartR15,
  author = {Sergiu Hart and Philip J. Reny},
  title = {{Maximizing Revenue with Multiple Goods: Nonmonotonicity and Other Observations}},
  journal = {Theoretical Economics},
  year = {2015},
	volume = {10},
number = {3},
pages = {893-922}
}

@inproceedings{HartlineR09,
	Author = {Jason D. Hartline and Tim Roughgarden},
	Booktitle = {ACM Conference on Electronic Commerce},
	Date-Added = {2014-10-03 16:37:36 +0000},
	Date-Modified = {2014-10-03 16:37:36 +0000},
	Pages = {225-234},
	Title = {Simple versus optimal mechanisms},
	Year = {2009}}

@ARTICLE{HartR11, 
    AUTHOR={Sergiu Hart and Philip J. Reny}, 
    TITLE={{Implementation of Reduced Form Mechanisms: A Simple Approach and a New Characterization}}, 
    JOURNAL={Economic Theory Bulletin}, 
	volume = {3},
number = {1},
pages = {1-8},
    YEAR={2015}
} 

@inproceedings{AbrahamBDR12,
  author    = {Ittai Abraham and
               Moshe Babaioff and
               Shaddin Dughmi and
               Tim Roughgarden},
  title     = {Combinatorial auctions with restricted complements},
  booktitle = {13th ACM Conference on Electronic Commerce (EC)},
  year      = {2012}
}

@ARTICLE{Groves73, 
    AUTHOR={Theodore Groves}, 
    TITLE={{Incentives in Teams}}, 
    JOURNAL={Econometrica}, 
    YEAR={1973}, 
    VOLUME= {41},
    NUMBER = {4}, 
    PAGES={617-631}
} 

@article{adler,
  author    = {Ilan Adler and Sushil Verma},
  title     = {{The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD}},
  journal = {Manuscript},
  year      = {2007}
}

@inproceedings{Ajtai,
  author    = {Mikl{\'o}s Ajtai},
  title     = {{Generating Hard Instances of Lattice Problems (Extended Abstract)}},
  booktitle = {the 28th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {1996}
}

@inproceedings{Alaei11,
  author    = {Saeed Alaei},
  title     = {{Bayesian Combinatorial Auctions: Expanding Single Buyer
               Mechanisms to Many Buyers}},
  booktitle = {the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2011}
  }

@techreport{Carroll15,
	Author = {Carroll, Gabriel},
	Date-Added = {2016-10-17 04:06:15 +0000},
	Date-Modified = {2016-10-17 04:06:15 +0000},
	Institution = {Stanford University Working Paper},
	Title = {Robustness and Separation in Multidimensional Screening},
	Year = {2015}}

@inproceedings{GiannakopoulosK14,
	Author = {Yiannis Giannakopoulos and Elias Koutsoupias},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/GiannakopoulosK14},
	Booktitle = {{ACM} Conference on Economics and Computation, {EC} '14, Stanford , CA, USA, June 8-12, 2014},
	Crossref = {DBLP:conf/sigecom/2014},
	Doi = {10.1145/2600057.2602883},
	Pages = {259--276},
	Timestamp = {Wed, 02 Jul 2014 09:44:36 +0200},
	Title = {Duality and optimality of auctions for uniform distributions},
	Url = {http://doi.acm.org/10.1145/2600057.2602883},
	Year = {2014},
	Bdsk-Url-1 = {http://doi.acm.org/10.1145/2600057.2602883},
	Bdsk-Url-2 = {http://dx.doi.org/10.1145/2600057.2602883}}

@inproceedings{GiannakopoulosK15,
	Author = {Yiannis Giannakopoulos and Elias Koutsoupias},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/icalp/GiannakopoulosK15},
	Booktitle = {Automata, Languages, and Programming - 42nd International Colloquium, {ICALP} 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part {II}},
	Crossref = {DBLP:conf/icalp/2015-2},
	Doi = {10.1007/978-3-662-47666-6_52},
	Pages = {650--662},
	Timestamp = {Mon, 22 Jun 2015 12:04:57 +0200},
	Title = {Selling Two Goods Optimally},
	Url = {http://dx.doi.org/10.1007/978-3-662-47666-6_52},
	Year = {2015},
	Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-662-47666-6_52}}

@article{Giannakopoulos14a,
	Author = {Yiannis Giannakopoulos},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/journals/corr/Giannakopoulos14a},
	Journal = {CoRR},
	Timestamp = {Wed, 01 Oct 2014 15:00:05 +0200},
	Title = {A Note on Optimal Auctions for Two Uniformly Distributed Items},
	Url = {http://arxiv.org/abs/1409.6925},
	Volume = {abs/1409.6925},
	Year = {2014},
	Bdsk-Url-1 = {http://arxiv.org/abs/1409.6925}}

@inproceedings{HartlineH15,
	Author = {Nima Haghpanah and Jason Hartline},
	Booktitle = {Proceedings of the Sixteenth {ACM} Conference on Economics and Computation, {EC} '15, Portland, OR, USA, June 15-19, 2015},
	Title = {Reverse Mechanism Design},
	Year = {2015}}


%\bibitem{arrow-debreu} K.~J.~Arrow and G.~Debreu.
%\newblock Existence of an Equilibrium for a Competitive Economy.
%\newblock {\em Econometrica,} 22(3): 265--290, 1954.

@inproceedings{AlaeiFHHM12,
  author    = {Saeed Alaei and Hu Fu and Nima Haghpanah and Jason Hartline and Azarakhsh Malekian},
  title = {{Bayesian Optimal Auctions via Multi- to Single-agent Reduction}},
  booktitle = {the 13th ACM Conference on Electronic Commerce (EC)},
  year = {2012}
  }

@inproceedings{AlaeiFHH13,
author    = {Saeed Alaei and Hu Fu and Nima Haghpanah and Jason Hartline },
  title = {{The Simple Economics of Approximately Optimal Auctions}},
  booktitle = {the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year = {2013}
}
  
%  note = {{Posted to arXiv on March 22, 2012: http://arxiv.org/abs/1203.5099}}	

@article{AD54,
  author    = {Kenneth~J.~Arrow and Gerard Debreu},
  title     = {{Existence of an Equilibrium for a Competitive Economy}},
  journal   = {Econometrica},
  volume    = {22},
  number    = {3},
  year      = {1954},
  pages     = {265-290}
}

%\bibitem{Interview with Dantzig} D.~J.~Albers, C.~Reid and G.~B.~Dantzig. ``An Interview with George B. Dantzig: The Father of Linear Programming,'' {\em The College Mathematics Journal}, 17(4):293--314, 1986.
%

@article{Interview_with_Dantzig,
  author    = {Donald~J.~Albers and Constance Reid},
  title     = {An {I}nterview with {G}eorge {B.} {D}antzig: {T}he {F}ather of {L}inear {P}rogramming},
  journal   = {The College Mathematics Journal},
  volume    = {17},
  number    = {4},
  year      = {1986},
  pages     = {293-314}
}
@article{Pavlov11,
author = {Gregory Pavlov},
title = {Optimal Mechanism for Selling Two Goods},
journal = {The B.E. Journal of Theoretical Economics},
volume = {11},
number = {3},
year = {2011}
}

@inproceedings{BabaioffLP06,
  author    = {Moshe Babaioff and
               Ron Lavi and
               Elan Pavlov},
  title     = {Single-value combinatorial auctions and implementation in
               undominated strategies},
  booktitle = {the Seventeenth Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2006}
}



%\bibitem{BarbourLindvall} A.~D. Barbour and T.~Lindvall.
%\newblock Translated Poisson Approximation for Markov Chains.
%\newblock {\em Journal of Theoretical Probability}, 19(3), July 2006.

@article{BarbourLindvall,
  author    = {Andrew D. Barbour and Torgny Lindvall},
  title     = {{Translated Poisson Approximation for Markov Chains}},
  journal   = {Journal of Theoretical Probability},
  volume    = {19},
  number    = {3},
  year      = {2006},
  pages     = {609-630}
}


@BOOK{barbour, 
   AUTHOR={Andrew~D. Barbour}, 
   TITLE={{Multivariate Poisson-Binomial Approximation Using Stein's Method}}, 
   PUBLISHER={A.~D. Barbour and L.~H.~Y.~Chen (editors), Lecture Notes Series No. 4, Institute for Mathematical Sciences, National University of Singapore, Singapore University Press and World Scientific}, 
   YEAR = {2005} 
 } 


%\bibitem{BarbourChen}
%A.~D. Barbour and L.~H.~Y.~Chen.
%An Introduction to Stein's Method.
%{\em In A.~D. Barbour and L.~H.~Y.~Chen, eds, Lecture Notes Series No. 4, Institute for Mathematical Sciences, National University of Singapore, Singapore University Press and World Scientific,} 2005.

@BOOK{BarbourChen, 
   AUTHOR={Andrew~D. Barbour and Louis H. Y. Chen}, 
   TITLE={An {I}ntroduction to {S}tein's {M}ethod}, 
   PUBLISHER={A.~D. Barbour and L.~H.~Y.~Chen (editors), Lecture Notes Series No. 4, Institute for Mathematical Sciences, National University of Singapore, Singapore University Press and World Scientific}, 
   YEAR = {2005} 
 } 

%\bibitem{BarbourEtAl:book} A.~D.~Barbour, L.~Holst and S.~Janson.
%\newblock Poisson Approximation.
%\newblock {\em Oxford University Press,} New York, 1992.

@BOOK{BarbourEtAl:book, 
   AUTHOR={Andrew D. Barbour and Lars Holst and Svante Janson}, 
   TITLE={{Poisson Approximation}}, 
   PUBLISHER={Oxford University Press}, 
   YEAR = {1992} 
 } 



@article{BCEIT,
  author    = {Paul Beame and Stephen A. Cook and Jeff Edmonds and Russell Impagliazzo and Toniann Pitassi},
  title     = {The {R}elative {C}omplexity of {NP} {S}earch {P}roblems},
  journal   = {Journal of Computer and System Sciences},
  volume    = {57},
  number    = {1},
  year      = {1998},
  pages     = {3-19}
}

@inproceedings{LewenbergSZ15,
  author    = {Yoad Lewenberg and
               Yonatan Sompolinsky and
               Aviv Zohar},
  title     = {Inclusive Block Chain Protocols},
  booktitle = {Financial Cryptography and Data Security - 19th International Conference,
               {FC} 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected
               Papers},
  pages     = {528--547},
  year      = {2015},
  crossref  = {DBLP:conf/fc/2015},
  url       = {http://dx.doi.org/10.1007/978-3-662-47854-7_33},
  doi       = {10.1007/978-3-662-47854-7_33},
  timestamp = {Mon, 20 Jul 2015 10:36:38 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/fc/LewenbergSZ15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@inproceedings{HeilmanKZG15,
  author    = {Ethan Heilman and
               Alison Kendler and
               Aviv Zohar and
               Sharon Goldberg},
  title     = {Eclipse Attacks on Bitcoin's Peer-to-Peer Network},
  booktitle = {24th {USENIX} Security Symposium, {USENIX} Security 15, Washington,
               D.C., USA, August 12-14, 2015.},
  pages     = {129--144},
  year      = {2015},
  crossref  = {DBLP:conf/uss/2015},
  url       = {https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/heilman},
  timestamp = {Fri, 19 Aug 2016 15:38:03 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/uss/HeilmanKZG15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{BravermanMW17,
	Author = {Mark Braverman and Jieming Mao and S. Matthew Weinberg},
	Journal = {Manuscript},
	Title = {Simultaneous Communication Complexity of Two Player Combinatorial Auctions},
	Year = {2016}}

@article{EdenFFTW16a,
	Author = {Alon Eden and Michal Feldman and Ophir Friedler and Inbal Talgam-Cohen and S. Matthew Weinberg},
	Journal = {Manuscript},
	Title = {A simple and approximately optimal mechanism for a buyer with complements},
	Year = {2016}}

@inproceedings{BeiH11,
  author    = {Xiaohui Bei and Zhiyi Huang},
  title     = {{Bayesian Incentive Compatibility via Fractional Assignments}},
  booktitle = {the Twenty-Second Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2011}
}

@inproceedings{CaiZ17,
  author    = {Yang Cai and
               Mingfei Zhao},
  title     = {Simple mechanisms for subadditive buyers via duality},
  booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
  pages     = {170--183},
  year      = {2017},
  crossref  = {DBLP:conf/stoc/2017},
  url       = {http://doi.acm.org/10.1145/3055399.3055465},
  doi       = {10.1145/3055399.3055465},
  timestamp = {Wed, 01 Nov 2017 09:38:38 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/CaiZ17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{EdenFFTW16b,
	Author = {Alon Eden and Michal Feldman and Ophir Friedler and Inbal Talgam-Cohen and S. Matthew Weinberg},
	Journal = {Manuscript},
	Title = {The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders},
	Year = {2016}}


@inproceedings{BhattacharyaGGM10,
  author    = {Sayan Bhattacharya and
               Gagan Goel and
               Sreenivas Gollapudi and
               Kamesh Munagala},
  title     = {{Budget Constrained Auctions with Heterogeneous Items}},
  booktitle = {the 42nd ACM Symposium on Theory of Computing (STOC)},
  year      = {2010}
}





%\bibitem{Bha} R.~N.~Bhattacharya.
%On Errors of Normal Approximation.
%{\em The Annals of Probability}, 3(5): 815--828, 1975.

@ARTICLE{Bha, 
    AUTHOR={Rabindra~N.~Bhattacharya}, 
    TITLE={{On Errors of Normal Approximation}}, 
    JOURNAL={The Annals of Probability}, 
    YEAR={1975}, 
    VOLUME= {3}, 
    PAGES={815-828}, 
    NUMBER={5}
} 


%\bibitem{Blonskia} M.~Blonski.
%\newblock Anonymous Games with Binary Actions.
%\newblock {\em Games and Economic Behavior}, 28(2): 171--180, 1999.

@ARTICLE{Blonski99, 
    AUTHOR={Matthias Blonski}, 
    TITLE={{A}nonymous {G}ames with {B}inary {A}ctions}, 
    JOURNAL={Games and Economic Behavior}, 
    YEAR={1999}, 
    VOLUME= {28}, 
    PAGES={171-180}, 
    NUMBER={2}
} 


%\bibitem{Blonskib} M.~Blonski.
%\newblock The women of Cairo: Equilibria in large anonymous games.
%\newblock {\em Journal of Mathematical Economics,} 41(3): 253--264, 2005.

@ARTICLE{Blonski05, 
    AUTHOR={Matthias Blonski}, 
    TITLE={{T}he {W}omen of {C}airo: {E}quilibria in {L}arge {A}nonymous {G}ames}, 
    JOURNAL={Journal of Mathematical Economics}, 
    YEAR={2005}, 
    VOLUME= {41}, 
    PAGES={253-264}, 
    NUMBER={3}
} 


%\bibitem{BCIKMP}
%C.~Borgs, J.~Chayes, N.~Immorlica, A.~T.~Kalai, V.~Mirrokni and C.~H.~Papadimitriou.
%``The Myth of the Folk Theorem,''
%{\em In the 40th ACM Symposium on Theory of Computing,} STOC 2008.

@article{Border91,
author = {Kim C. Border},
title = {Implementation of Reduced Form Auctions: A Geometric Approach},
journal = {Econometrica},
year = {1991},
volume = {59},
number = {4},
pages = {1175-1187}
}

@ARTICLE{Border07, 
    AUTHOR={Kim C. Border}, 
    TITLE={{Reduced Form Auctions Revisited}}, 
    JOURNAL={Economic Theory}, 
    YEAR={2007}, 
    VOLUME= {31}, 
    PAGES={167-181}, 
} 

@inproceedings{BCIKMP,
  author    = {Christian Borgs and Jennifer T. Chayes and Nicole Immorlica and Adam Tauman Kalai and Vahab S. Mirrokni and Christos H. Papadimitriou},
  title     = {The {M}yth of the {F}olk {T}heorem},
  booktitle = {the 40th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2008}
}


%\bibitem{BBM}
%H.~Bosse, J.~Byrka and E.~Markakis.
%``New Algorithms for Approximate Nash Equilibria in Bimatrix Games,''
%{\em In the 3rd International Workshop on Internet and Network Economics,} WINE 2007.

@inproceedings{BBM,
  author    = {Hartwig Bosse and Jaroslaw Byrka and Evangelos Markakis},
  title     = {New {A}lgorithms for {A}pproximate {N}ash {E}quilibria in {B}imatrix {G}ames},
  booktitle = {the 3rd International Workshop on Internet and Network Economics (WINE)},
  year      = {2007}
}


@inproceedings{BhalgatGM13,
  author    = {Anand Bhalgat and Sreenivas Gollapudi and Kamesh Munagala },
  title     = {{Optimal Auctions via the Multiplicative Weight Method}},
  booktitle = {the 14th ACM Conference on Economics and Computation (EC)},
  year      = {2013}
}

@inproceedings{DaskalakisDW15,
author = {Constantinos Daskalakis and Nikhil Devanur and S. Matthew Weinberg},
title = {Revenue Maximization and Ex-Post Budget Constraints},
booktitle = {the 16th ACM Conference on Economics and Computation (EC)},
year = {2015}
}

@inproceedings{BriestCKW10,
  author    = {Patrick Briest and
               Shuchi Chawla and
               Robert Kleinberg and
               S. Matthew Weinberg},
  title     = {{Pricing Randomized Allocations}},
  booktitle = {the Twenty-First Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2010}
}

@inproceedings{BriestK07,
  author    = {Patrick Briest and
               Piotr Krysta},
  title     = {{Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing}},
  booktitle = {the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2007}
}

@inproceedings{Briest08,
  author    = {Patrick Briest},
  title     = {{Uniform Budgets and the Envy-Free Pricing Problem}},
  booktitle = {the 35th International Colloquium in Automata, Languages and Programming (ICALP)},
  year      = {2008}
}


@inproceedings{BriestKV05,
  author    = {Patrick Briest and Piotr Krysta and Berthold V{\"o}cking},
  title     = {Approximation techniques for utilitarian mechanism design},
  booktitle = {the 37th Annual ACM Symposium on Theory of
               Computing (STOC)},
  year      = {2005}
}


@inproceedings{vN:symmetric,
  author    = {George~W.~Brown and {John von} Neumann},
  title     = {{Solutions of Games by Differential Equations}},
  booktitle = {H.~W.~Kuhn and A.~W.~Tucker (editors), Contributions to the Theory of Games},
  year      = {1950},
  volume = {1},
  pages = {73-79},
  publisher = {Princeton University Press}
}


%\bibitem{Bubelis} V.~Bubelis.
%``On Equilibria in Finite Games,''
%{\em International Journal of Game Theory},~8(2):65--79, 1979.

@ARTICLE{Bubelis79, 
    AUTHOR={Valentinas Bubelis}, 
    TITLE={On {E}quilibria in {F}inite {G}ames}, 
    JOURNAL={International Journal of Game Theory}, 
    YEAR={1979}, 
    VOLUME= {8}, 
    PAGES={65-79}, 
    NUMBER={2}
} 


@inproceedings{BuchfuhrerDFKMPSSU10,
  author    = {David Buchfuhrer and
               Shaddin Dughmi and
               Hu Fu and
               Robert Kleinberg and
               Elchanan Mossel and
               Christos H. Papadimitriou and
               Michael Schapira and
               Yaron Singer and
               Christopher Umans},
  title     = {{Inapproximability for VCG-Based Combinatorial Auctions}},
  booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium
               on Discrete Algorithms (SODA)},
  year      = {2010}
}


%\bibitem{colorings} G.~J.~Chang, W.~Ke, D.~Kuo, D.~D.~Liu and R.~K.~Yeh.
%``On L(d, 1)-Labelings of Graphs,'' {\em Discrete
%Mathematics},~220(1--3):~57--66, 2000.

@inproceedings{CaiD11,
  author    = {Yang Cai and Constantinos Daskalakis},
  title     = {{Extreme-Value Theorems for Optimal Multidimensional Pricing}},
  booktitle = {the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2011}
}

@inproceedings{CaiDW12a,
  author    = {Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg},
  title     = {{An Algorithmic Characterization of Multi-Dimensional Mechanisms}},
  booktitle = {the 44th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2012}
}
%  note = {Posted to arXiv on Dec 20, 2011: http://arxiv.org/abs/1112.4572}



@inproceedings{CaiDW12b,
  author    = {Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg},
  title     = {{Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization}},
  booktitle = {the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2012}
}

@article{CaiDW12bfull,
  author    = {Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg},
  title     = {{Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization}},
  journal = {arxiv report},
  year      = {2012},
  note = {http://arxiv.org/abs/1207.5518}
}

@article{youTubeOutage1,
  author    = {Declan McCullagh},
  title     = {{How Pakistan knocked YouTube offline (and how to make sure it never happens again)}},
  journal = {CNET},
  year      = {2008},
  note = {http://news.cnet.com/8301-10784_3-9878655-7.html}
}

@article{youTubeOutage2,
  author    = {Robert McMillan},
  title     = {Weekend YouTube outage underscores big Internet problem},
  journal = {Macworld},
  year      = {2008},
  note = {http://www.macworld.com/article/1132256/networking.html}
}

@inproceedings{CaiDW13a,
  author    = {Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg},
  title     = {{Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations}},
  booktitle = {the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2013}
}

@inproceedings{CaiDW13b,
  author    = {Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg},
  title     = {{Understanding Incentives: Mechanism Design becomes Algorithm Design}},
  booktitle = {the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2013}
}


@inproceedings{CaiH13,
  author    = {Yang Cai and Zhiyi Huang},
  title     = {{Simple and Nearly Optimal Multi-Item Auctions}},
  booktitle = {the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2013}
}

@article{colorings,
  author    = {Gerard J. Chang and Wen-Tsai Ke and David Kuo and Daphne Der-Fen Liu and Roger K. Yeh},
  title     = {On {\it L}({\it d}, 1)-{L}abelings of {G}raphs},
  journal   = {Discrete Mathematics},
  volume    = {220},
  number    = {1-3},
  year      = {2000},
  pages     = {57-66}
}



@inproceedings{ChawlaHMS10,
  author    = {Shuchi Chawla and Jason D. Hartline and David L. Malec and Balasubramanian Sivan},
  title     = {{Multi-Parameter Mechanism Design and Sequential Posted Pricing}},
  booktitle = {the 42nd ACM Symposium on Theory of Computing (STOC)},
  year      = {2010}
}


@inproceedings{ChawlaHK07,
  author    = {Shuchi Chawla and Jason D. Hartline and Robert D. Kleinberg},
  title     = {{Algorithmic Pricing via Virtual Valuations}},
  booktitle = {the 8th ACM Conference on Electronic Commerce (EC)},
  year      = {2007}
}

@article{Clarke71,
  author    = {Edward H. Clarke},
  title     = {{Multipart Pricing of Public Goods}},
  journal   = {Public Choice},
  volume    = {11},
  number    = {1},
  year      = {1971},
  pages     = {17-33}
}


@inproceedings{ChawlaMS10,
  author    = {Shuchi Chawla and David L. Malec and Balasubramanian Sivan},
  title     = {{The Power of Randomness in Bayesian Optimal Mechanism Design}},
  booktitle = {the 11th ACM Conference on Electronic Commerce (EC)},
  year      = {2010}
}


@article{CheKM11,
  author    = {Yeon-Koo Che and Jinwoo Kim and Konrad Mierendorff},
  title     = {{Generalized Reduced-Form Auctions: A Network-Flow Approach.}},
  journal   = {Econometrica},
  year      = {2013}
}


%\bibitem{CD1}
%X.~Chen and X.~Deng. ``3-NASH is PPAD-Complete,'' {\em Electronic
%Colloquium in Computational Complexity}, TR05-134, 2005.

@article{CD06a,
  author    = {Xi Chen and Xiaotie Deng},
  title     = {3-{N}ASH is {PPAD}-{C}omplete},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  number    = {134},
  year      = {2005}
}


%\bibitem{CD2}
%X.~Chen and X.~Deng. ``Settling the Complexity of 2-Player
%Nash-Equilibrium,'' {\em In the 47th Annual IEEE Symposium on Foundations of Computer Science,} FOCS 2006.

@inproceedings{CD06b,
  author    = {Xi Chen and Xiaotie Deng},
  title     = {Settling the {C}omplexity of {T}wo-{P}layer {N}ash {E}quilibrium},
  booktitle = {the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2006}
}


%\bibitem{CDT}
%X.~Chen, X.~Deng and S.~Teng. ``Computing Nash Equilibria:
%Approximation and Smoothed Complexity,'' {\em In the 47th Annual IEEE Symposium on Foundations of Computer Science,} FOCS 2006.

@inproceedings{CDTa,
  author    = {Xi Chen and Xiaotie Deng and Shang-Hua Teng},
  title     = {Computing {N}ash {E}quilibria: {A}pproximation and {S}moothed {C}omplexity},
  booktitle = {the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2006}
}


@inproceedings{CDT06b,
  author    = {Xi Chen and Xiaotie Deng and Shang-Hua Teng},
  title     = {{Sparse Games Are Hard}},
  booktitle = {the 2nd International Workshop on Internet and Network Economics (WINE)},
  year      = {2006}
}


%\bibitem{CTValiant}
%X.~Chen, S.~Teng and P. Valiant. ``The Approximation Complexity of Win-Lose Games,'' {\em In the 18th Annual ACM-SIAM Symposium On Discrete Algorithms,} SODA 2007.

@inproceedings{CTV07,
  author    = {Xi Chen and Shang-Hua Teng and Paul Valiant},
  title     = {The {A}pproximation {C}omplexity of {W}in-{L}ose {G}ames},
  booktitle = {the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2007}
}

@inproceedings{CS07,
  author    = {Steve Chien and
               Alistair Sinclair},
  title     = {{Convergence to Approximate Nash Equilibria in Congestion Games}},
  booktitle = {the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2007}
}

@inproceedings{christodoulou2007lower,
  title={A lower bound for scheduling mechanisms},
  author={Christodoulou, George and Koutsoupias, Elias and Vidali, Angelina},
  booktitle={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
  pages={1163--1170},
  year={2007},
  organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{ChawlaHMS13,
  title={{Prior-Independent Mechanisms for Scheduling}},
  author={Shuchi Chawla and Jason Hartline and David Malec and Balasubramanian Sivan},
  booktitle={Proceedings of 45th ACM Symposium on Theory of Computing (STOC)},
  year={2013}
}

@inproceedings{ChawlaIL12,
  author    = {Shuchi Chawla and
               Nicole Immorlica and
               Brendan Lucier},
  title     = {On the limits of black-box reductions in mechanism design},
  booktitle = {Proceedings of the 44th Symposium on Theory of Computing (STOC)},
  year      = {2012}
}


%\bibitem{CSVY} B.~Codenotti, A.~Saberi, K.~Varadarajan and Y.~Ye.
%``Leontief Economies Encode Nonzero Sum Two-Player Games,'' {\em
%In the 17th Annual ACM-SIAM Symposium On Discrete Algorithms,} SODA 2006.

@inproceedings{CSVY06,
  author    = {Bruno Codenotti and Amin Saberi and Kasturi R. Varadarajan and Yinyu Ye},
  title     = {Leontief {E}conomies {E}ncode {N}onzero {S}um {T}wo-{P}layer {G}ames},
  booktitle = {the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2006}
}


%\bibitem{condon} A.~Condon. ``The Complexity of Stochastic Games,'' {\em Information and Computation,} 96(2):~203--224, 1992.

@article{Condon92,
  author    = {Anne Condon},
  title     = {The {C}omplexity of {S}tochastic {G}ames},
  journal   = {Information and Computation},
  volume    = {96},
  number    = {2},
  year      = {1992},
  pages     = {203-224}
}

%\bibitem{CS} V.~Conitzer and T.~Sandholm.
%``Complexity Results about Nash Equilibria,'' {\em In the 18th International Joint Conference on Artificial Intelligence,} IJCAI 2003.

@inproceedings{CS03,
  author    = {Vincent Conitzer and Tuomas Sandholm},
  title     = {Complexity {R}esults about {N}ash {E}quilibria},
  booktitle = {the 18th International Joint Conference on Artificial Intelligence (IJCAI)},
  year      = {2003}
  }

%\bibitem{CoverThomas}
%M.~Cover and J.~A.~Thomas.
%Elements of Information Theory.
%{\em Wiley} 2006.

@BOOK{CoverThomas, 
   AUTHOR = {Thomas M.~Cover and Joy A.~Thomas}, 
   TITLE = {{Elements of Information Theory}}, 
   PUBLISHER={Wiley}, 
   YEAR=2006
 } 

@article{CM85,
author = {Jacques Cremer and Richard P. McLean},
title = {Optimal Selling Strategies under Uncertainty for a Discriminating Monopolist When Demands Are Interdependent},
journal = {Econometrica},
year = {1985}, 
volume = {53},
number = {2},
pages = {345-361}
}

@article{CM88,
author = {Jacques Cremer and Richard P. McLean},
title = {Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions},
journal = {Econometrica},
year = {1988},
volume = {56},
number = {6}, 
pages = {1247-1257}
}
%\bibitem{Dantzig} G.~B.~Dantzig. {\it Linear Programming and
%Extensions}, Princeton University Press, 1963.

@BOOK{Dantzig63, 
   AUTHOR = {George~B.~Dantzig}, 
   TITLE = {Linear {P}rogramming and {E}xtensions}, 
   PUBLISHER={Princeton University Press}, 
   YEAR=1963
 } 

@inproceedings{Daskalakis11,
  author    = {Constantinos Daskalakis},
  title     = {{On the Complexity of Approximating a Nash Equilibrium}}, 
  booktitle = {the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2011}
}

@inproceedings{ChenDPSY14,
  author    = {Xi Chen and
               Ilias Diakonikolas and
               Dimitris Paparas and
               Xiaorui Sun and
               Mihalis Yannakakis},
  title     = {The Complexity of Optimal Multidimensional Pricing},
  booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
  pages     = {1319--1328},
  year      = {2014},
  crossref  = {DBLP:conf/soda/2014},
  url       = {http://dx.doi.org/10.1137/1.9781611973402.97},
  doi       = {10.1137/1.9781611973402.97},
  timestamp = {Wed, 12 Feb 2014 20:27:53 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/soda/ChenDPSY14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}



@inproceedings{DaskalakisDT12,
  author    = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title     = {{Optimal Pricing is Hard}}, 
  booktitle = {the 8th Workshop on Internet \& Network Economics (WINE)},
  year      = {2012}
}

@inproceedings{DaskalakisDT13,
  author    = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title     = {{Mechanism Design via Optimal Transport}},
booktitle = {The 14th ACM Conference on Electronic Commerce (EC)},
  year      = {2013}
}
@inproceedings{DaskalakisDT14,
  author    = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title     = {{The Complexity of Optimal Mechanism Design}},
booktitle = {the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2014}
}
@inproceedings{DaskalakisDT15,
  author    = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title     = {{Strong Duality for a Multiple-Good Monopolist}},
booktitle = {the 16th ACM Conference on Economics and Computation (EC)},
  year      = {2015}
}

@inproceedings{GopalanNR15,
  author    = {Parikshit Gopalan and Noam Nisan and Tim Roughgarden},
  title     = {Public projects, boolean functions and the borders of Border's theorem},
booktitle = {the 16th ACM Conference on Economics and Computation (EC)},
  year      = {2015}
}


%\bibitem{DFP}
%C.~Daskalakis, A.~Fabrikant and C.~H.~Papadimitriou. ``The Game
%World is Flat: The Complexity of Nash Equilibria in Succinct
%Games,'' {\em In the 33rd International Colloquium on Automata, Languages and Programming,} ICALP 2006.

@inproceedings{DFP06,
  author    = {Constantinos Daskalakis and Alex Fabrikant and Christos H. Papadimitriou},
  title     = {The {G}ame {W}orld {I}s {F}lat: {T}he {C}omplexity of {N}ash {E}quilibria in {S}uccinct {G}ames},
  booktitle = {the 33rd International Colloquium on Automata, Languages and Programming (ICALP)},
  year      = {2006}
}


%\bibitem{DGP}
%C.~Daskalakis, P.~W.~Goldberg and C.~H.~Papadimitriou. ``The
%Complexity of Computing a Nash Equilibrium,'' {\em In the 38th ACM Symposium on Theory of Computing,} STOC 2006.

@inproceedings{DGP06,
  author    = {Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou},
  title     = {The {C}omplexity of {C}omputing a {N}ash {E}quilibrium},
  booktitle = {the 38th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2006}
}

@article{DGP09,
  author    = {Constantinos Daskalakis and
               Paul W. Goldberg and
               Christos H. Papadimitriou},
  title     = {{The Complexity of Computing a Nash Equilibrium}},
  journal   = {SIAM Journal on Computing},
  volume    = {39},
  number    = {1},
  year      = {2009},
  pages     = {195-259}
}

@article{DGP09b,
  author    = {Constantinos Daskalakis and
               Paul W. Goldberg and
               Christos H. Papadimitriou},
  title     = {{The Complexity of Computing a Nash Equilibrium}},
  journal   = {Communications of the ACM},
  volume    = {52},
  number    = {2},
  year      = {2009},
  pages     = {89-97}
}



%\bibitem{DMP}
%C.~Daskalakis, A.~Mehta and C.~H.~Papadimitriou. ``A Note on
%Approximate Nash Equilibria,'' {\em In the 2nd international Workshop on Internet and Network Economics,} WINE 2006.

@inproceedings{DMP06,
  author    = {Constantinos Daskalakis and Aranyak Mehta and Christos H. Papadimitriou},
  title     = {A {N}ote on {A}pproximate {N}ash {E}quilibria},
  booktitle = {the 2nd International Workshop on Internet and Network Economics (WINE)},
  year      = {2006}
}


%\bibitem{DMP2}
%C.~Daskalakis, A.~Mehta and C.~H.~Papadimitriou. ``Progress in Approximate Nash Equilibria,'' {\em In the 8th ACM Conference on Electronic Commerce,} EC 2007.

@inproceedings{DMP07,
  author    = {Constantinos Daskalakis and Aranyak Mehta and Christos H. Papadimitriou},
  title     = {Progress in {A}pproximate {N}ash {E}quilibria},
  booktitle = {8th ACM Conference on Electronic Commerce (EC)},
  year      = {2007}
}


%\bibitem{DP}
%C.~Daskalakis and C.~H.~Papadimitriou. ``Three-Player Games Are
%Hard,'' {\em Electronic Colloquium in Computational Complexity},
%TR05-139, 2005.

@article{DP05,
  author    = {Constantinos Daskalakis and Christos H. Papadimitriou},
  title     = {Three-{P}layer {G}ames {A}re {H}ard},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  number    = {139},
  year      = {2005}
}


%\bibitem{DP_MRFs}
%C.~Daskalakis and C.~H.~Papadimitriou. ``Computing Pure Nash
%Equilibria via Markov Random Fields,'' {\em In the 7th ACM Conference on Electronic Commerce,} EC 2006.

@inproceedings{DP06,
  author    = {Constantinos Daskalakis and Christos H. Papadimitriou},
  title     = {Computing {P}ure {N}ash {E}quilibria in {G}raphical {G}ames via {M}arkov {R}andom {F}ields},
  booktitle = {the 7th ACM Conference on Electronic Commerce (EC)},
  year      = {2006}
}

%\bibitem{DP: anonymous 1}
%C.~Daskalakis and C.~H.~Papadimitriou.
%``Computing Equilibria in Anonymous Games,''
%{\em In the 48th Annual IEEE Symposium on Foundations of Computer Science,} FOCS 2007.

@inproceedings{DP07,
  author    = {Constantinos Daskalakis and Christos H. Papadimitriou},
  title     =  {{C}omputing {E}quilibria in {A}nonymous {G}ames},
  booktitle = {the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2007}
}


%\bibitem{DP: anonymous 2}
%C.~Daskalakis and C.~H.~Papadimitriou.
%``Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games,''
%{\em In the 49th Annual IEEE Symposium on Foundations of Computer Science,} FOCS 2008.

@inproceedings{DP08,
  author    = {Constantinos Daskalakis and Christos H. Papadimitriou},
  title     = {{D}iscretized {M}ultinomial {D}istributions and {N}ash {E}quilibria in {A}nonymous {G}ames},
  booktitle = {the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2008}
}

@article{CaiDW15,
  author    = {Yang Cai and Nikhil Devanur and S. Matthew Weinberg},
  title     = {A Unified Duality-Based Approach to Bayesian Mechanism Design},
  journal = {In Submission},
  year      = {2015}
}

@inproceedings{Daskalakis08,
  author    = {Constantinos Daskalakis},
  title     = {{An Efficient PTAS for Two-Strategy Anonymous Games}},
  booktitle = {the 4th International Workshop on Internet and Network Economics (WINE)},
  year      = {2008}
}




@article{Daskalakis08b,
  author    = {Constantinos Daskalakis},
  title     = {{An Efficient PTAS for Two-Strategy Anonymous Games}},
  journal   = {CoRR},
  volume    = {abs/0812.2277},
  year      = {2008},
  ee        = {http://arxiv.org/abs/0812.2277},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DaskalakisW15,
  author    = {Constantinos Daskalakis and S. Matthew Weinberg},
  title     = {{Bayesian Truthful for Job Scheduling from Bi-Criterion Approximation Algorithms}},
  booktitle = {the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2015}
}


@inproceedings{DP09,
  author    = {Constantinos Daskalakis and
               Christos H. Papadimitriou},
  title     = {{On Oblivious PTAS's for Nash Equilibrium}},
  booktitle = {the 41st Annual ACM Symposium on Theory of
               Computing (STOC)},
  year      = {2009}
}

@inproceedings{DaskalakisW12,
	author		= {Constantinos Daskalakis and S. Matthew Weinberg},
	title 		= {{Symmetries and Optimal Multi-Dimensional Mechanism Design}},
	booktitle = {the 13th ACM Conference on Electronic Commerce (EC)},
	year 			= {2012}
}
%	note = {Posted to arXiv on Dec 17, 2011: http://arxiv.org/abs/1112.4006}

@inproceedings{Dobzinski11,
  author    = {Shahar Dobzinski},
  title     = {{An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations}},
  booktitle = {Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC)},
  year      = {2011}
}



@inproceedings{DobzinskiFK11,
  author    = {Shahar Dobzinski and Hu Fu and Robert D. Kleinberg},
  title     = {{Optimal Auctions with Correlated Bidders are Easy}},
  booktitle = {the 43rd ACM Symposium on Theory of Computing (STOC)},
  year      = {2011}
}


@inproceedings{DughmiV11,
  author    = {Shaddin Dughmi and Jan Vondrak},
  title     = {{Limitations of Randomized Mechanisms for Combinatorial Auctions}},
  booktitle = {52nd Annual Symposium on Foundations of Computer Science (FOCS)},
  year      = {2011}
}


@inproceedings{DughmiR10,
  author    = {Shaddin Dughmi and Tim Roughgarden},
  title     = {Black-Box Randomized Reductions in Algorithmic Mechanism Design},
  booktitle = {51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2010}
}


%\bibitem{Eaves}
%B.~C.~Eaves. ``Homotopies for Computation of Fixed Points,'' {\em
%Mathematical Programming}, 3:~1--22, 1972.

@ARTICLE{Eaves, 
    AUTHOR={B.~Curtis~Eaves}, 
    TITLE={{Homotopies for Computation of Fixed Points}}, 
    JOURNAL={Mathematical Programming}, 
    YEAR={1972}, 
    VOLUME= {3}, 
    PAGES={1-22}
} 




%\bibitem{EGG}
%E.~Elkind, L.~A.~Goldberg and P.~W.~Goldberg. ``Nash Equilibria
%in Graphical Games on Trees Revisited,'' {\em In the 7th ACM Conference on Electronic Commerce,} EC 2006.

@inproceedings{EGG,
  author    = {Edith Elkind and Leslie Ann Goldberg and Paul W. Goldberg},
  title     = {{Nash Equilibria in Graphical Games on Trees Revisited}},
  booktitle = {the 7th ACM Conference on Electronic Commerce (EC)},
  year      = {2006}
}


%\bibitem{EY: fixed points}
%K.~Etessami and M.~Yannakakis.
%``On the Complexity of Nash Equilibria and Other Fixed Points,''
%{\em In the 48th Annual IEEE Symposium on Foundations of Computer Science,} FOCS 2007.

@inproceedings{EY:fixed_points,
  author    = {Kousha Etessami and Mihalis Yannakakis},
  title     = {On the {C}omplexity of {N}ash {E}quilibria and {O}ther {F}ixed {P}oints ({E}xtended {A}bstract)},
  booktitle = {the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2007}
}


%\bibitem{FNS}
%T.~Feder, H.~Nazerzadeh, and A.~Saberi.
%\newblock Approximating Nash Equilibria Using Small-Support Strategies.
%\newblock {\em EC}, 2007.

@inproceedings{FNS,
  author    = {Tom{\'a}s Feder and Hamid Nazerzadeh and Amin Saberi},
  title     = {Approximating {N}ash {E}quilibria {U}sing {S}mall-{S}upport {S}trategies},
  booktitle = {the 8th ACM Conference on Electronic Commerce (EC)},
  year      = {2007}
}


%\bibitem{FPT} A.~Fabrikant, C.H.~Papadimitriou and K.~Talwar.
%``The Complexity of Pure Nash Equilibria,'' {\em In the 36th ACM Symposium on Theory of Computing,} STOC 2004.

@inproceedings{FPT,
  author    = {Alex Fabrikant and Christos H. Papadimitriou and Kunal Talwar},
  title     = {{The Complexity of Pure Nash Equilibria}},
  booktitle = {the 36th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2004}
}

@BOOK{FudLev, 
   AUTHOR={Drew Fudenberg and David K. Levine}, 
   TITLE={{The Theory of Learning in Games}}, 
   PUBLISHER={The MIT Press}, 
   YEAR = {1999} 
 } 

%\bibitem{GaleKuhnTucker}
%D.~Gale, H.~W.~Kuhn, and A.~W.~Tucker. 
%\newblock On Symmetric Games.
%\newblock {\em In H. W. Kuhn and A. W. Tucker, 
%editors, Contributions to the Theory of Games}, 1:81--87, Princeton University Press, 1950.

@inproceedings{GaleKuhnTucker,
  author    = {David~Gale and Harold W. Kuhn and Albert~W.~Tucker},
  title     = {{On Symmetric Games}},
  booktitle = {H.~W.~Kuhn and A.~W.~Tucker (editors), Contributions to the Theory of Games},
  year      = {1950},
  volume = {1},
  pages = {81-87},
  publisher = {Princeton University Press}
}

@inproceedings{GGJ:geometric_problems,
  author    = {M. R. Garey and Ronald L. Graham and David S. Johnson},
  title     = {{S}ome {NP}-{C}omplete {G}eometric {P}roblems},
  booktitle = {the 8th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {1976}
}


%\bibitem{GarciaLemkeLuthi} Crisostomo B. Garcia and C.~E.~Lemke and H.~J.~Luthi. ``Simplicial Approximation of an Equilibrium Point of Noncooperative N-Person Games,'' {\em Mathematical Programming}, 4:~227--260, 1973.

@ARTICLE{GarciaLemkeLuthi, 
    AUTHOR={Crisostomo B. Garcia and Carlton E. Lemke and Hans-Jakob~L\"uthi}, 
    TITLE={{Simplicial Approximation of an Equilibrium Point of Noncooperative N-Person Games}}, 
    JOURNAL={Mathematical Programming}, 
    YEAR={1973}, 
    VOLUME= {4}, 
    PAGES={227-260}
} 



%\bibitem{Gean}
%J.~Geanakoplos. ``Nash and Walras Equilibrium via Brouwer,'' {\em
%Economic Theory},~21,~2003.

@ARTICLE{Gean, 
    AUTHOR={John Geanakoplos},
    TITLE={{Nash and Walras Equilibrium via Brouwer}},
    JOURNAL={Economic Theory},
    YEAR={2003},
    VOLUME= {21},
    NUMBER={2-3},
    PAGES={585-603}
} 


%\bibitem{GZ} I.~Gilboa and E.~Zemel.
%``Nash and Correlated Equilibria: Some Complexity
%Considerations,'' {\em Games and Economic Behavior}, 1(1):~80--93, 1989.

@ARTICLE{GZ, 
    AUTHOR={Itzhak Gilboa and Eitan Zemel},
    TITLE={{Nash and Correlated Equilibria: Some Complexity Considerations}},
    JOURNAL={Games and Economic Behavior},
    YEAR={1989},
    VOLUME= {1},
    NUMBER={1},
    PAGES={80-93}
} 

%\bibitem{Goe} F.~G\"otze.
%On the Rate of Convergence in the Multivariate CLT.
%{\em The Annals of Probability}, 19(2): 724--739, 1991.

@ARTICLE{Goe, 
    AUTHOR={Friedrich~G\"otze}, 
    TITLE={{On the Rate of Convergence in the Multivariate CLT}}, 
    JOURNAL={The Annals of Probability}, 
    YEAR={1991}, 
    VOLUME= {19},
    NUMBER = {2}, 
    PAGES={724-739}
} 


%\bibitem{GP}
%P.~W.~Goldberg and C.~H.~Papadimitriou. ``Reducibility Among
%Equilibrium Problems,'' {\em In the 38th ACM Symposium on Theory of Computing,} STOC 2006.

@inproceedings{GP,
  author    = {Paul W. Goldberg and Christos H. Papadimitriou},
  title     = {{Reducibility Among Equilibrium Problems}},
  booktitle = {the 38th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2006}
}

@inproceedings{HartlineL10,
  author    = {Jason D. Hartline and Brendan Lucier},
  title     = {{Bayesian Algorithmic Mechanism Design}},
  booktitle = {the 42nd ACM Symposium on Theory of Computing (STOC)},
  year      = {2010}
}

@inproceedings{HartlineKM11,
  author    = {Jason D. Hartline and Robert Kleinberg and Azarakhsh Malekian},
  title     = {{Bayesian Incentive Compatibility via Matchings}},
  booktitle = {the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2011}
}

@inproceedings{HartN12,
  author    = {Sergiu Hart and Noam Nisan},
  title     = {{Approximate Revenue Maximization with Multiple Items}},
  booktitle = {the 13th ACM Conference on Electronic Commerce (EC)},
  year      = {2012}
}

@inproceedings{HartN13,
author = {Sergiu Hart and Noam Nisan},
title = {The menu-size complexity of auctions},
 booktitle = {the 14th ACM Conference on Electronic Commerce (EC)},
  year      = {2013}
}

@article{Hoeffding63,
	author = {Wassily Hoeffding},
	title = {Probability Inequalities for Sums of Bounded Random Variables},
	journal = {Journal of the American Statistical Association},
	year = {1963},
	volume = {58},
	number = {301},
	pages = {13-30}
}

%\bibitem{HPV}
%M.~Hirsch, C.~H.~Papadimitriou and S. Vavasis. ``Exponential Lower
%Bounds for Finding Brouwer Fixpoints,'' {\em Journal of
%Complexity}, 5(4):~379--416, 1989.

@article{HPV,
  author    = {Michael D. Hirsch and Christos H. Papadimitriou and Stephen A. Vavasis},
  title     = {Exponential {L}ower {B}ounds for {F}inding {B}rouwer {F}ixed {P}oints},
  journal   = {Journal of Complexity},
  volume    = {5},
  number    = {4},
  year      = {1989},
  pages     = {379-416}
}


%\bibitem{JPY}
%D.~S.~Johnson, C.~H.~Papadimitriou and M.~Yannakakis. ``How Easy
%is Local Search?,'' {\em Journal of Computer and System
%Sciences},~37(1):~79--100,~1988.

@article{JPY,
  author    = {David S. Johnson and Christos H. Papadimitriou and Mihalis Yannakakis},
  title     = {{How Easy is Local Search?}},
  journal   = {Journal of Computer and System Sciences},
  volume    = {37},
  number    = {1},
  year      = {1988},
  pages     = {79-100}
}


@article{JohnsonDM60,
  author    = {Diane M. Johnson and A. L. Dulmage and N.~S.~Mendelsohn},
  title     = {{On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices}},
  journal   = {Canadian Mathematical Bulletin},
  volume    = {3},
  number    = {3},
  year      = {1960},
  pages     = {237-242}
}



%\bibitem{kalai}
%E.~Kalai.
%\newblock Partially-Specified Large Games.
%\newblock {\em WINE}, 2005. 

@INPROCEEDINGS{Kalai05, 
	AUTHOR={Ehud Kalai}, 
	TITLE={{P}artially-{S}pecified {L}arge {G}ames}, 
	BOOKTITLE={the 1st International Workshop on Internet and Network Economics (WINE)}, 
	YEAR={2005}
} 


@inproceedings{KT,
  author    = {Ravi Kannan and Thorsten Theobald},
  title     = {{Games of Fixed Rank: a Hierarchy of Bimatrix Games}},
  booktitle = {the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2007}
}


%\bibitem{K} M.~Kearns, M.~Littman and S.~Singh.
%``Graphical Models for Game Theory,'' {\em In the 17th Conference in Uncertainty in Artificial Intelligence,} UAI 2001.

@inproceedings{K,
  author    = {Michael J. Kearns and Michael L. Littman and Satinder P. Singh},
  title     = {Graphical {M}odels for {G}ame {T}heory},
  booktitle = {the 17th Conference in Uncertainty in Artificial Intelligence (UAI)},
  year      = {2001}
}



%\bibitem{Kh} L.~G.~Khachiyan. ``A Polynomial Algorithm in Linear
%Programming,'' {\em Soviet Mathematics Doklady}, 20(1):~191--194,
%1979.

@article{Khachiyan79,
  author    = {Leonid~G.~Khachiyan},
  title     = {{A Polynomial Algorithm in Linear Programming}},
  journal   = {Soviet Mathematics Doklady},
  volume = {20},
  number = {1},
  pages = {191-194},
  year      = {1979}
}

@inproceedings{KleinbergW12,
author = {Robert Kleinberg and S. Matthew Weinberg},
title = {{Matroid Prophet Inequalities}},
booktitle = {the 44th Annual ACM Symposium on Theory of Computing (STOC)},
year = {2012}
}
%note = {Posted to arXiv on Jan 23, 2012: http://arxiv.org/abs/1201.4764}


%\bibitem{Br} B.~Knaster, C.~Kuratowski and S.~Mazurkiewicz. ``Ein Beweis des
%Fixpunktsatzes f\"ur n-dimensionale Simplexe,'' {\em Fundamenta
%Mathematicae,} 14:~132--137, 1929.

@article{Br,
  author    = {Bronislaw Knaster and Casimir Kuratowski and Stefan Mazurkiewicz},
  title     = {Ein {B}eweis des {F}ixpunktsatzes f\"ur n-dimensionale {S}implexe},
  journal   = {Fundamenta Mathematicae},
  volume = {14},
  pages = {132-137},
  year      = {1929}
}


%\bibitem{KPS}
%S.~C. Kontogiannis, P.~N. Panagopoulou, and P.~G. Spirakis.
%\newblock Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games.
%\newblock {\em WINE}, 2006.

@inproceedings{KPS,
  author    = {Spyros C. Kontogiannis and Panagiota N. Panagopoulou and Paul G. Spirakis},
  title     = {Polynomial {A}lgorithms for {A}pproximating {N}ash {E}quilibria of {B}imatrix {G}ames},
  booktitle = {the 2nd International Workshop on Internet and Network Economics (WINE)},
  year      = {2006}
}

@inproceedings{KoutsoupiasV07,
  author    = {Elias Koutsoupias and Angelina Vidali},
  title     = {{A Lower Bound of $1+\phi$ for Truthful Scheduling Mechanisms}},
  booktitle = {the 32nd International Symposium on the Mathematical Foundations of Computer Science (MFCS)},
  year      = {2007}
}

@inproceedings{ChristodoulouKV07,
  author    = {George Christodoulou and Elias Koutsoupias and Angelina Vidali},
  title     = {{A Lower Bound for Scheduling Mechanisms}},
  booktitle = {the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2007}
}



%\bibitem{LaanTalmanSimplex} G.~van~der~Laan and A.~J.~J.~Talman. ``A Restart Algorithm for Computing Fixed Points Without an Extra Dimension,'' {\em Mathematical Programming}, 17:~74--84, 1979.

@article{LaanTalmanSimplex,
  author    = {{Gerard van der} Laan and Adolphus Johannes Jan Talman},
  title     = {{A Restart Algorithm for Computing Fixed Points Without an Extra Dimension}},
  journal   = {Mathematical Programming},
  volume = {17},
  number    = {1},
  pages = {74-84},
  year      = {1979}
}


%\bibitem{LaanTalmanProductOfSimplices} G.~van~der~Laan and A.~J.~J.~Talman. ``On the Computation of Fixed Points in the Product Space of Unit Simplices and an Application to Noncooperative N Person Games,'' {\em Mathematics of Operations Research}, 7(1):~1--13, 1982.

@article{LaanTalmanProductOfSimplices,
  author    = {{Gerard van der} Laan and Adolphus Johannes Jan Talman},
  title     = {{On the Computation of Fixed Points in the Product Space of Unit Simplices and an Application to Noncooperative N Person Games}},
  journal   = {Mathematics of Operations Research},
  volume = {7},
  number    = {1},
  pages = {1-13},
  year      = {1982}
}


%\bibitem{LH} C.~E.~Lemke and J.~T.~Howson,~Jr. ``Equilibrium Points of Bimatrix Games,'' {\em SIAM Journal on
%Applied Mathematics}, 12:~413--423, 1964.

@article{LH,
  author    = {Carlton E. Lemke and Joseph T. Howso{n, Jr.}},
  title     = {Equilibrium {P}oints of {B}imatrix {G}ames},
  journal   = {Journal of the Society for Industrial and Applied Mathematics},
  volume = {12},
  number    = {2},
  pages = {413-423},
  year      = {1964}
}


@inproceedings{LenstraST87,
  author    = {Jan Karel Lenstra and
               David B. Shmoys and
               {\'E}va Tardos},
  title     = {Approximation Algorithms for Scheduling Unrelated Parallel
               Machines},
  booktitle = {FOCS},
  year      = {1987}
}



%\bibitem{LM} R.~Lipton and E.~Markakis.
%``Nash Equilibria via Polynomial Equations,'' {\em In the 6th Latin American Symposium,}
%LATIN 2004.

@inproceedings{LM,
  author    = {Richard J. Lipton and Evangelos Markakis},
  title     = {Nash {E}quilibria via {P}olynomial {E}quations},
  booktitle = {6th Latin American Symposium (LATIN)},
  year      = {2004}
}


%\bibitem{LMM} R.~Lipton, E.~Markakis and A.~Mehta.
%``Playing Large Games Using Simple Strategies,''  {\em In the 4th ACM Conference on Electronic Commerce,} EC 2003.

@inproceedings{LiptonMM03,
  author    = {Richard J. Lipton and Evangelos Markakis and Aranyak Mehta},
  title     = {Playing {L}arge {G}ames {U}sing {S}imple {S}trategies},
  booktitle = {the 4th ACM Conference on Electronic Commerce (EC)},
  year      = {2003}
}


%\bibitem{LKS} M.~Littman, M.~Kearns and S.~Singh.
%``An Efficient, Exact Algorithm for Single Connected Graphical
%Games,'' {\em In the 15th Annual Conference on Neural Information Processing Systems}, NIPS 2001.

@inproceedings{LKS,
  author    = {Michael L. Littman and Michael J. Kearns and Satinder P. Singh},
  title     = {{An Efficient, Exact Algorithm for Solving Tree-Structured Graphical Games}},
  booktitle = {the 15th Annual Conference on Neural Information Processing Systems (NIPS)},
  year      = {2001}
}

@article{ManelliV10,
    AUTHOR={A.~M.~Manelli and D.~R.~Vincent}, 
    TITLE={{Bayesian and Dominant-Strrategy Implementation in the Independent Private-Values Model}}, 
    JOURNAL={Econometrica}, 
    YEAR={2010}, 
    VOLUME= {78},
    number={6}, 
    PAGES={1905-1938}
} 

@article{BriestCKW15,
  author    = {Patrick Briest and
               Shuchi Chawla and
               Robert Kleinberg and
               S. Matthew Weinberg},
  title     = {Pricing lotteries},
  journal   = {J. Economic Theory},
  volume    = {156},
  pages     = {144--174},
  year      = {2015},
  url       = {http://dx.doi.org/10.1016/j.jet.2014.04.011},
  doi       = {10.1016/j.jet.2014.04.011},
  timestamp = {Thu, 12 Feb 2015 12:31:26 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jet/BriestCKW15},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@article{RileyZ83,
  author = {John Riley and Richard Zeckhauser},
  title = {{Optimal Selling Strategies: {W}hen to Haggle, When to Hold Firm}},
  journal = {Quarterly J. Economics},
  volume = {98},
  number = {2},
  year = {1983},
  pages = {267--289}
}

@ARTICLE{ManelliV07, 
    AUTHOR={A.~M.~Manelli and D.~R.~Vincent}, 
    TITLE={{Multidimensional Mechanism Design: Revenue Maximization and the Multiple-Good Monopoly}}, 
    JOURNAL={Journal of Economic Theory}, 
    YEAR={2007}, 
    VOLUME= {137},
    number={1}, 
    PAGES={153-185}
} 

@article{MaskinR84,
	author	= {Eric Maskin and John Riley},
	title = {{Optimal Auctions with Risk Averse Buyers.}},
	journal = {Econometrica},
	year = {1984},
	volume = {52},
	number = {6},
	pages = {1473-1518}
}
%\bibitem{MegPap} N.~Megiddo and C.~H.~Papadimitriou. ``On Total Functions, Existence Theorems and Computational Complexity,'' {\em Theoretical Computer Science},
%81(2):~317--324, 1991.

@article{Matthews84,
	author = {Steven Matthews},
	title =  {{On the Implementability of Reduced Form Auctions.}},
	journal =  { Econometrica},
	year = {1984},
	volume = {52},
	number = {6},
	pages = {1519--1522}
	}

@article{MR92,
author = {R. Preston McAfee and Philip J. Reny},
title = {Correlated Information and Mechanism Design},
journal = {Econometrica},
year = {1992},
volume = {60},
number = {2},
pages = {395-421}
}

@article{MegPap,
  author    = {Nimrod Megiddo and Christos H. Papadimitriou},
  title     = {{On Total Functions, Existence Theorems and Computational Complexity}},
  journal   = {Theoretical Computer Science},
  volume    = {81},
  number    = {2},
  year      = {1991},
  pages     = {317-324}
}


%\bibitem{Mi} Igal Milchtaich.
%\newblock Congestion Games with Player-Specific Payoff Functions.
%\newblock {\em Games and Economic Behavior}, 13:111--124.

@ARTICLE{Milchtaich96, 
    AUTHOR={Igal Milchtaich}, 
    TITLE={Congestion {G}ames with {P}layer-{S}pecific {P}ayoff {F}unctions}, 
    JOURNAL={Games and Economic Behavior}, 
    YEAR={1996}, 
    VOLUME= {13}, 
    PAGES={111-124}
} 

@article{Vickrey61,
  author    = {William Vickrey},
  title     = {{Counterspeculations, Auctions, and Competitive Sealed Tenders}},
  journal   = {Journal of Finance},
  volume    = {16},
 year      = {1961},
  pages     = {8-37},
  number = {1}
}

@ARTICLE{MilgromS17, 
    AUTHOR={Paul Milgrom and Ilya Segal}, 
    TITLE={Deferred-Acceptance Clock Auctions and
Radio Spectrum Reallocation}, 
    JOURNAL={Working Paper}, 
    YEAR={2017}, 
    
} 

@ARTICLE{MilgromS13, 
    AUTHOR={Paul Milgrom and Ilya Segal}, 
    TITLE={Deferred-Acceptance Heuristic Auctions}, 
    JOURNAL={Working Paper}, 
    YEAR={2013}, 
    
} 

@article{Myerson81,
  author    = {Roger B. Myerson},
  title     = {{Optimal Auction Design}},
  journal   = {Mathematics of Operations Research},
  volume    = {6},
  number    = {1},
  year      = {1981},
  pages     = {58-73}
}

%\bibitem{myerson99} R.~B.~Myerson.
%\newblock Nash Equilibrium and the History of Economic Theory.
%\newblock {\em Journal of Economic Literature}, 37(3):1067--1082, 1999.

@ARTICLE{Myerson99, 
    AUTHOR={Roger B. Myerson}, 
    TITLE={{Nash Equilibrium and the History of Economic Theory}}, 
    JOURNAL={Journal of Economic Literature}, 
    YEAR={1999}, 
    VOLUME= {37},
    number    = {3}, 
    PAGES={1067-1082}
} 

%\bibitem{N} J.~Nash.
%``Non-Cooperative Games,'' {\em Annals of Mathematics},
%54(2):~286-295, 1951.

@ARTICLE{Nash51, 
    AUTHOR={John F. Nash}, 
    TITLE={Non-{C}ooperative {G}ames}, 
    JOURNAL={Annals of Mathematics}, 
    YEAR={1951}, 
    VOLUME = {54},
    NUMBER = {2},
    PAGES={286-295}
} 

@ARTICLE{Nash50, 
    AUTHOR={John F. Nash}, 
    TITLE={{Equilibrium Points in n-Person Games}}, 
    JOURNAL={Proceedings of the National Academy of Sciences}, 
    YEAR={1950}, 
    VOLUME = {36},
    NUMBER = {1},
    PAGES={48-49}
} 

%\bibitem{vN} J.~von~Neumann. ``Zur Theorie der Gesellshaftsspiele,'' {\em Mathematische Annalen}, 100:~295--320, 1928.

@ARTICLE{vN, 
    AUTHOR={{John von} Neumann}, 
    TITLE={{Zur Theorie der Gesellshaftsspiele}}, 
    JOURNAL={Mathematische Annalen}, 
    YEAR={1928}, 
    VOLUME = {100},
    PAGES={295-320}
} 


@ARTICLE{Li17, 
    AUTHOR={Shengwu Li}, 
    TITLE={Obviously Strategy-Proof Mechanisms}, 
    JOURNAL={Mathematische Annalen}, 
    YEAR={2017}, 
    VOLUME = {107},
    PAGES={3257--3287},
number = {11}
} 

@inproceedings{MirrokniLTZ16,
  author    = {Vahab S. Mirrokni and
               Renato Paes Leme and
               Pingzhong Tang and
               Song Zuo},
  title     = {Dynamic Auctions with Bank Accounts},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI} 2016, New York, NY, USA, 9-15 July
               2016},
  pages     = {387--393},
  year      = {2016},
  crossref  = {DBLP:conf/ijcai/2016},
  url       = {http://www.ijcai.org/Abstract/16/062},
  timestamp = {Fri, 15 Jul 2016 15:58:28 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/ijcai/MirrokniLTZ16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{AgrawalDMS18,
  author    = {Shipra Agrawal and
               Constantinos Daskalakis and
               Vahab S. Mirrokni and
               Balasubramanian Sivan},
  title     = {Robust Repeated Auctions under Heterogeneous Buyer Behavior},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {171},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219234},
  doi       = {10.1145/3219166.3219234},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/0001DMS18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{MirrokniLTZ18,
  author    = {Vahab S. Mirrokni and
               Renato Paes Leme and
               Pingzhong Tang and
               Song Zuo},
  title     = {Non-clairvoyant Dynamic Mechanism Design},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {169},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219224},
  doi       = {10.1145/3219166.3219224},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/MirrokniLTZ18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BalseiroML17,
  author    = {Santiago R. Balseiro and
               Vahab S. Mirrokni and
               Renato Paes Leme},
  title     = {Dynamic Mechanisms with Martingale Utilities},
  booktitle = {Proceedings of the 2017 {ACM} Conference on Economics and Computation,
               {EC} '17, Cambridge, MA, USA, June 26-30, 2017},
  pages     = {165},
  year      = {2017},
  crossref  = {DBLP:conf/sigecom/2017},
  url       = {http://doi.acm.org/10.1145/3033274.3084089},
  doi       = {10.1145/3033274.3084089},
  timestamp = {Wed, 21 Jun 2017 09:41:38 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/BalseiroML17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{AshlagiDH16,
  author    = {Itai Ashlagi and
               Constantinos Daskalakis and
               Nima Haghpanah},
  title     = {Sequential Mechanisms with Ex-post Participation Guarantees},
  booktitle = {Proceedings of the 2016 {ACM} Conference on Economics and Computation,
               {EC} '16, Maastricht, The Netherlands, July 24-28, 2016},
  pages     = {213--214},
  year      = {2016},
  crossref  = {DBLP:conf/sigecom/2016},
  url       = {http://doi.acm.org/10.1145/2940716.2940775},
  doi       = {10.1145/2940716.2940775},
  timestamp = {Fri, 22 Jul 2016 09:44:16 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/AshlagiDH16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DevanurPS15,
  author    = {Nikhil R. Devanur and
               Yuval Peres and
               Balasubramanian Sivan},
  title     = {Perfect Bayesian Equilibria in Repeated Sales},
  booktitle = {Proceedings of the Twenty-Sixth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2015, San Diego, CA, USA, January 4-6, 2015},
  pages     = {983--1002},
  year      = {2015},
  crossref  = {DBLP:conf/soda/2015},
  url       = {https://doi.org/10.1137/1.9781611973730.67},
  doi       = {10.1137/1.9781611973730.67},
  timestamp = {Wed, 24 May 2017 08:31:21 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/soda/DevanurPS15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{ChawlaDKS16,
  author    = {Shuchi Chawla and
               Nikhil R. Devanur and
               Anna R. Karlin and
               Balasubramanian Sivan},
  title     = {Simple Pricing Schemes For Consumers With Evolving Values},
  booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
  pages     = {1476--1490},
  year      = {2016},
  crossref  = {DBLP:conf/soda/2016},
  url       = {https://doi.org/10.1137/1.9781611974331.ch101},
  doi       = {10.1137/1.9781611974331.ch101},
  timestamp = {Sun, 17 Dec 2017 22:06:00 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/soda/ChawlaDKS16},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{FuHH13,
  author    = {Hu Fu and
               Jason D. Hartline and
               Darrell Hoy},
  title     = {Prior-independent auctions for risk-averse agents},
  booktitle = {{ACM} Conference on Electronic Commerce, {EC} '13, Philadelphia, PA,
               USA, June 16-20, 2013},
  pages     = {471--488},
  year      = {2013},
  crossref  = {DBLP:conf/sigecom/2013},
  url       = {http://doi.acm.org/10.1145/2482540.2482551},
  doi       = {10.1145/2482540.2482551},
  timestamp = {Mon, 27 Nov 2017 14:42:24 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/FuHH13},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

%\bibitem{vNM}
%J.~von Neumann and O.~Morgenstern. {\it Theory of Games and
%Economic Behavior}, Princeton University Press, 1944.

@BOOK{vonNeumannM44, 
   AUTHOR = {{John von} Neumann and Oskar Morgenstern}, 
   TITLE = {{Theory of Games and Economic Behavior}}, 
   PUBLISHER = {Princeton University Press}, 
   YEAR = {1944}
 } 


@BOOK{AGTbook, 
   EDITOR = {Noam Nisan and Tim Roughgarden and E.~Tardos and V.~V.~Vazirani}, 
   TITLE = {{Algorithmic Game Theory}}, 
   PUBLISHER = {Cambridge University Press}, 
   YEAR = {2007}
 } 
 
 @inproceedings{NisanR99,
  author    = {Noam Nisan and Amir Ronen},
  title     = {{Algorithmic Mechanism Design (Extended Abstract)}},
  booktitle = {Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {1999}
}

@inproceedings{RubinsteinW15,
title = {Simple Mechanisms for a subadditive buyer and applications to revenue monotonicity},
author = {Aviad Rubinstein and S. Matthew Weinberg},
booktitle = {Proceedings of the 16th ACM Conference on Electronic Commerce},
year = {2015}
}

@article{DantsinGHKKPRS02,
  author    = {Evgeny Dantsin and
               Andreas Goerdt and
               Edward A. Hirsch and
               Ravi Kannan and
               Jon M. Kleinberg and
               Christos H. Papadimitriou and
               Prabhakar Raghavan and
               Uwe Sch{\"{o}}ning},
  title     = {A deterministic (2-2/(k+1))\({}^{\mbox{n}}\) algorithm for k-SAT based
               on local search},
  journal   = {Theor. Comput. Sci.},
  volume    = {289},
  number    = {1},
  pages     = {69--83},
  year      = {2002},
  url       = {https://doi.org/10.1016/S0304-3975(01)00174-8},
  doi       = {10.1016/S0304-3975(01)00174-8},
  timestamp = {Thu, 08 Jun 2017 09:02:36 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/tcs/DantsinGHKKPRS02},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{Schoning99,
  author    = {Uwe Sch{\"{o}}ning},
  title     = {A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems},
  booktitle = {40th Annual Symposium on Foundations of Computer Science, {FOCS} '99,
               17-18 October, 1999, New York, NY, {USA}},
  pages     = {410--414},
  year      = {1999},
  crossref  = {DBLP:conf/focs/1999},
  url       = {https://doi.org/10.1109/SFFCS.1999.814612},
  doi       = {10.1109/SFFCS.1999.814612},
  timestamp = {Fri, 19 May 2017 01:25:58 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/focs/Schoning99},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{PaturiPSZ05,
  author    = {Ramamohan Paturi and
               Pavel Pudl{\'{a}}k and
               Michael E. Saks and
               Francis Zane},
  title     = {An improved exponential-time algorithm for \emph{k}-SAT},
  journal   = {J. {ACM}},
  volume    = {52},
  number    = {3},
  pages     = {337--364},
  year      = {2005},
  url       = {http://doi.acm.org/10.1145/1066100.1066101},
  doi       = {10.1145/1066100.1066101},
  timestamp = {Thu, 09 Feb 2006 13:34:10 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jacm/PaturiPSZ05},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{GonczarowskiN17,
  author    = {Yannai A. Gonczarowski and
               Noam Nisan},
  title     = {Efficient empirical revenue maximization in single-parameter auction
               environments},
  booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
  pages     = {856--868},
  year      = {2017},
  crossref  = {DBLP:conf/stoc/2017},
  url       = {http://doi.acm.org/10.1145/3055399.3055427},
  doi       = {10.1145/3055399.3055427},
  timestamp = {Sat, 17 Jun 2017 18:46:57 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/GonczarowskiN17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{Gonczarowski18,
  author    = {Yannai A. Gonczarowski},
  title     = {Bounding the menu-size of approximately optimal auctions via optimal-transport
               duality},
  booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
  pages     = {123--131},
  year      = {2018},
  crossref  = {DBLP:conf/stoc/2018},
  url       = {http://doi.acm.org/10.1145/3188745.3188786},
  doi       = {10.1145/3188745.3188786},
  timestamp = {Thu, 21 Jun 2018 08:27:49 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/Gonczarowski18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BabaioffNR18,
  author    = {Moshe Babaioff and
               Noam Nisan and
               Aviad Rubinstein},
  title     = {Optimal Deterministic Mechanisms for an Additive Buyer},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {429},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219188},
  doi       = {10.1145/3219166.3219188},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/BabaioffNR18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{HartlineKM11,
  author    = {Jason D. Hartline and
               Robert Kleinberg and
               Azarakhsh Malekian},
  title     = {Bayesian Incentive Compatibility via Matchings},
  booktitle = {Proceedings of the Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA} 2011, San Francisco, California, USA, January 23-25,
               2011},
  pages     = {734--747},
  year      = {2011},
  crossref  = {DBLP:conf/soda/2011},
  url       = {https://doi.org/10.1137/1.9781611973082.58},
  doi       = {10.1137/1.9781611973082.58},
  timestamp = {Wed, 24 May 2017 08:31:21 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/soda/HartlineKM11},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{GonczarowskiW18,
  author    = {Yannai A. Gonczarowski and S. Matthew Weinberg},
  title     = {The Sample Complexity of up-to-$\varepsilon$ multidimensional revenue maximization},
  booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}},
  year      = {2018},
}
@article{HartlineKM15,
  author    = {Jason D. Hartline and
               Robert Kleinberg and
               Azarakhsh Malekian},
  title     = {Bayesian incentive compatibility via matchings},
  journal   = {Games and Economic Behavior},
  volume    = {92},
  pages     = {401--429},
  year      = {2015},
  url       = {https://doi.org/10.1016/j.geb.2015.02.002},
  doi       = {10.1016/j.geb.2015.02.002},
  timestamp = {Thu, 18 May 2017 09:52:37 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/geb/HartlineKM15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DughmiHKN17,
  author    = {Shaddin Dughmi and
               Jason D. Hartline and
               Robert Kleinberg and
               Rad Niazadeh},
  title     = {Bernoulli factories and black-box reductions in mechanism design},
  booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
               of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
  pages     = {158--169},
  year      = {2017},
  crossref  = {DBLP:conf/stoc/2017},
  url       = {http://doi.acm.org/10.1145/3055399.3055492},
  doi       = {10.1145/3055399.3055492},
  timestamp = {Sat, 17 Jun 2017 18:46:57 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/stoc/DughmiHKN17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{NacuP05,
  author    = {Serban Nacu and
               Yuval Peres},
  title     = {Fast Simulation of New Coins From Old},
  journal   = {Annals of Applied Probability},
  volume    = {15},
  number    = {1A},
  pages     = {93--115},
  year      = {2005}
}

@article{MosselP05,
  author    = {Elchanan Mossel and
               Yuval Peres},
  title     = {New Coins From Old: Computing With Unknown Bias},
  journal   = {Combinatorica},
  volume    = {25},
  number    = {6},
  pages     = {707--724},
  year      = {2005},
  url       = {https://doi.org/10.1007/s00493-005-0043-1},
  doi       = {10.1007/s00493-005-0043-1},
  timestamp = {Mon, 05 Jun 2017 20:49:23 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/combinatorica/MosselP05},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{KeaneO94,
  author    = {M. S. Keane and
               George L. O'Brien},
  title     = {A Bernoulli Factory},
  journal   = {{ACM} Trans. Model. Comput. Simul.},
  volume    = {4},
  number    = {2},
  pages     = {213--219},
  year      = {1994},
  url       = {http://doi.acm.org/10.1145/175007.175019},
  doi       = {10.1145/175007.175019},
  timestamp = {Mon, 03 Apr 2006 11:18:57 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/tomacs/KeaneO94},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Valiant79,
  author    = {Leslie G. Valiant},
  title     = {The Complexity of Computing the Permanent},
  journal   = {Theor. Comput. Sci.},
  volume    = {8},
  pages     = {189--201},
  year      = {1979},
  url       = {https://doi.org/10.1016/0304-3975(79)90044-6},
  doi       = {10.1016/0304-3975(79)90044-6},
  timestamp = {Sun, 28 May 2017 13:20:05 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/tcs/Valiant79},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{CaiD17,
  author    = {Yang Cai and
               Constantinos Daskalakis},
  title     = {Learning Multi-Item Auctions with (or without) Samples},
  booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
               2017, Berkeley, CA, USA, October 15-17, 2017},
  pages     = {516--527},
  year      = {2017},
  crossref  = {DBLP:conf/focs/2017},
  url       = {https://doi.org/10.1109/FOCS.2017.54},
  doi       = {10.1109/FOCS.2017.54},
  timestamp = {Mon, 19 Feb 2018 16:01:50 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/focs/0001D17},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{BabaioffCGZ18,
  author    = {Moshe Babaioff and
               Yang Cai and
               Yannai A. Gonczarowski and
               Mingfei Zhao},
  title     = {The Best of Both Worlds: Asymptotically Efficient Mechanisms with
               a Guarantee on the Expected Gains-From-Trade},
  booktitle = {Proceedings of the 2018 {ACM} Conference on Economics and Computation,
               Ithaca, NY, USA, June 18-22, 2018},
  pages     = {373},
  year      = {2018},
  crossref  = {DBLP:conf/sigecom/2018},
  url       = {http://doi.acm.org/10.1145/3219166.3219203},
  doi       = {10.1145/3219166.3219203},
  timestamp = {Tue, 19 Jun 2018 08:48:43 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/sigecom/Babaioff0GZ18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{KleinbergW14,
  author    = {Robert Kleinberg and
               S. Matthew Weinberg},
  title     = {Matroid Prophet Inequalities and applications to multi-dimensional mechanism design},
  journal   = {Games and Economic Behavior},
  year      = {2014}
}

@article{BriestCKW15,
  author    = {Patrick Briest and
               Shuchi Chawla and
               Robert Kleinberg and
               S. Matthew Weinberg},
  title     = {Pricing lotteries},
  journal   = {J. Economic Theory},
  volume    = {156},
  pages     = {144--174},
  year      = {2015},
  url       = {https://doi.org/10.1016/j.jet.2014.04.011},
  doi       = {10.1016/j.jet.2014.04.011},
  timestamp = {Sun, 17 Dec 2017 22:06:00 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/jet/BriestCKW15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{ChawlaMS15,
  author    = {Shuchi Chawla and
               David L. Malec and
               Balasubramanian Sivan},
  title     = {The power of randomness in Bayesian optimal mechanism design},
  journal   = {Games and Economic Behavior},
  volume    = {91},
  pages     = {297--317},
  year      = {2015},
  url       = {https://doi.org/10.1016/j.geb.2012.08.010},
  doi       = {10.1016/j.geb.2012.08.010},
  timestamp = {Sun, 17 Dec 2017 22:06:00 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/geb/ChawlaMS15},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{CaiDW16,
title = {A Duality Based Unified Approach to Bayesian Mechanism Design},
author = {Yang Cai and Nikhil Devanur and S. Matthew Weinberg},
booktitle = {Proceedings of the 48th ACM Conference on Theory of Computation(STOC)},
year = {2016}
}

%\bibitem{OR}
%M.J.~Osborne and A.~Rubinstein. {\em A Course in Game Theory}, MIT
%Press,~1994.

@BOOK{OR, 
   AUTHOR = {Martin J.~Osborne and Ariel Rubinstein}, 
   TITLE = {{A Course in Game Theory}}, 
   PUBLISHER = {MIT Press}, 
   YEAR = {1994}
 } 



@article{Pap:euclidianTSP,
  author    = {Christos H. Papadimitriou},
  title     = {The {E}uclidean {T}raveling {S}alesman {P}roblem is {NP}-{C}omplete},
  journal   = {Theoretical Computer Science},
  volume    = {4},
  number    = {3},
  year      = {1977},
  pages     = {237-244},
}



%\bibitem{Pabook}
%C.~H.~Papadimitriou. {\it Computational Complexity}, Addison
%Wesley,~1994.

@BOOK{Pabook, 
   AUTHOR={Christos H. Papadimitriou}, 
   TITLE={Computational {C}omplexity}, 
   PUBLISHER={Addison-Wesley}, 
   YEAR=1994
 } 

%\bibitem{Pa}
%C.~H.~Papadimitriou. ``On the Complexity of the Parity Argument
%and Other Inefficient Proofs of Existence,'' {\em Journal of
%Computer and System Sciences},~48(3):~498--532, 1994.

@article{Pa,
  author    = {Christos H. Papadimitriou},
  title     = {{On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence}},
  journal   = {Journal of Computer and System Sciences},
  volume    = {48},
  number    = {3},
  year      = {1994},
  pages     = {498-532},
}


%\bibitem{P}
%C.~H.~Papadimitriou. ``Computing Correlated Equilibria in
%Multiplayer Games,'' {\em In the 37th ACM Symposium on Theory of Computing,} STOC 2005.

@inproceedings{Pa05,
  author    = {Christos H. Papadimitriou},
  title     = {{Computing Correlated Equilibria in Multi-Player Games}},
  booktitle = {the 37th Annual ACM Symposium on Theory of Computing (STOC)},
  year      = {2005}
}


@inproceedings{PapadimitriouP11,
  author    = {Christos H. Papadimitriou and George Pierrakos},
  title     = {{On Optimal Single-Item Auctions}},
  booktitle = {the 43rd ACM Symposium on Theory of Computing (STOC)},
  year      = {2011}
}


%\bibitem{PaRough}
%C.~H.~Papadimitriou and T.~Roughgarden. ``Computing Equilibria in
%Multi-Player Games,'' {\em In the 16th Annual ACM-SIAM Symposium On Discrete Algorithms,} SODA 2005.

@inproceedings{PR05,
  author    = {Christos H. Papadimitriou and Tim Roughgarden},
  title     = {{Computing Equilibria in Multi-Player Games}},
  booktitle = {the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year      = {2005},
  pages     = {82-91}
}


@inproceedings{PapadimitriouSS08,
  author    = {Christos H. Papadimitriou and
               Michael Schapira and
               Yaron Singer},
  title     = {On the Hardness of Being Truthful},
  booktitle = {Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2008}
}



%\bibitem{Rollin:translatedPoissonApproximations}
%A.~R\"ollin.
%\newblock Translated Poisson Approximation Using Exchangeable Pair Couplings.
%\newblock {\em arXiv Report} 2006.

@ARTICLE{Rollin:translatedPoissonApproximations, 
    AUTHOR={Adrian~R\"ollin}, 
    TITLE={{Translated Poisson Approximation Using Exchangeable Pair Couplings}}, 
    JOURNAL={Annals of Applied Probability}, 
    YEAR={2007}, 
    VOLUME= {17},
    PAGES={1596-1614}
} 

%\bibitem{RoosPoisson} B.~Roos.
%Metric Multivariate Poisson Approximation of the Generalized Multinomial Distribution.
%{\em Theory of Probability and its Applications}, 43(2), 306--315, 1998.

@ARTICLE{RoosPoisson, 
    AUTHOR={Bero Roos}, 
    TITLE={{Metric Multivariate Poisson Approximation of the Generalized Multinomial Distribution}}, 
    JOURNAL={Theory of Probability and its Applications}, 
    YEAR={1998}, 
    VOLUME= {43},
    NUMBER={2},
    PAGES={306-315}
} 



%\bibitem{Rosen} J.~Rosenm\"uller. ``On a Generalization of the Lemke--Howson Algorithm to Noncooperative N-Person Games,'' {\em SIAM
%Journal on Applied Mathematics}, 21(1):~73--79, 1971.

@article{Rosen,
  author    = {Joachim Rosenm\"uller},
  title     = {{On a Generalization of the Lemke-Howson Algorithm to Noncooperative N-Person Games}},
  journal   = {SIAM Journal on Applied Mathematics},
  volume    = {21},
  number    = {1},
  year      = {1971},
  pages     = {73-79},
}

@ARTICLE{Rosenthal, 
    AUTHOR={Robert W. Rosenthal},
    TITLE={{A Class of Games Possessing Pure-Strategy Nash Equilibria}},
    JOURNAL={International Journal of Game Theory},
    YEAR={1973},
    VOLUME= {2},
    NUMBER={1},
    PAGES={65-67}
} 

@inproceedings{RoughgardenTY12,
  author    = {Tim Roughgarden and
               Inbal Talgam-Cohen and
               Qiqi Yan},
  title     = {Supply-limiting mechanisms},
  booktitle = {13th ACM Conference on Electronic Commerce (EC)},
  year      = {2012}
}

%\bibitem{Rubinstein} A.~Rubinstein. ``Equilibrium in Supergames with the Overtaking Criterion,'' {\em Journal of Economic Theory,} 21:~1--9, 1979.

@article{Rubinstein,
  author    = {Ariel Rubinstein},
  title     = {{Equilibrium in Supergames with the Overtaking Criterion}},
  journal   = {Journal of Economic Theory},
  volume    = {21},
 year      = {1979},
  pages     = {1-9},
}


%\bibitem{SVS}
%R.~Savani and B.~von~Stengel. ``Exponentially Many Steps for
%Finding a Nash Equilibrium in a Bimatrix Game,'' {\em In the 45th Annual IEEE Symposium on Foundations of Computer Science,} FOCS 2004.

@inproceedings{SVS,
  author    = {Rahul Savani and {Bernhard von} Stengel},
  title     = {{Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game}},
  booktitle = {the 45th Symposium on Foundations of Computer Science (FOCS)},
  year      = {2004}
}



%\bibitem{Scarf}
%H.~E.~Scarf. ``The Approximation of Fixed Points of a Continuous
%Mapping,'' {\em SIAM Journal on Applied Mathematics},
%15(5):~1328--1343, 1967.

@article{Scarf,
  author    = {Herbert E. Scarf},
  title     = {{The Approximation of Fixed Points of a Continuous Mapping}},
  journal   = {SIAM Journal on Applied Mathematics},
  volume    = {15},
 year      = {1967},
  pages     = {1328-1343},
  number = {5}
}




%\bibitem{SV}
%G.~Schoenebeck and S.~Vadhan. ``The Computational Complexity of
%Nash Equilibria in Concisely Represented Games,'' {\em In the 7th ACM Conference on Electronic Commerce,} EC 2006.

@inproceedings{SV,
  author    = {Grant Schoenebeck and Salil P. Vadhan},
  title     = {{The Computational Complexity of Nash Equilibria in Concisely Represented Games}},
  booktitle = {the 7th ACM Conference on Electronic Commerce (EC)},
  year      = {2006}
}


@inproceedings{ShmoysT93,
  author    = {David B. Shmoys and {\'E}va Tardos},
  title     = {{Scheduling Unrelated Machines with Costs}},
  booktitle = {the 4th Symposium on Discrete Algorithms (SODA)},
  year      = {1993}
}


%P.~Shor. 
%``Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,'' 
%{\em SIAM Journal of Computing,} 26(5):1484�1509, 1997.

@article{Shor,
  author    = {Peter Shor},
  title     = {{Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer}},
  journal   = {SIAM Journal of Computing},
  volume    = {26},
 year      = {1997},
  pages     = {1484-1509},
  number = {5}
}

@book{Sipser2006,
    address = {Boston},
    author = {Sipser, Michael},
    edition = {2},
    publisher = {PWS Pub.},
    title = {{Introduction to the Theory of Computation: Second Edition}},
    year = {2006}
}

%\bibitem{TS}
%H.~Tsaknakis and P.~G.~Spirakis.
%``An Optimization Approach for Approximate Nash Equilibria,''
%{\em In the 3rd International Workshop on Internet and Network Economics,} WINE 2007.

@inproceedings{TS,
  author    = {Haralampos Tsaknakis and Paul G. Spirakis},
  title     = {An {O}ptimization {A}pproach for {A}pproximate {N}ash {E}quilibria},
  booktitle = {the 3rd International Workshop on Internet and Network Economics (WINE)},
  year      = {2007}
}

@article{vetta:random_games,
  author    = {Imre B{\'a}r{\'a}ny and
               Santosh Vempala and
               Adrian Vetta},
  title     = {Nash equilibria in random games},
  journal   = {Random Structures and Algorithms},
  volume    = {31},
  number    = {4},
  year      = {2007},
  pages     = {391-405}
}

%\bibitem{Wilson}  R.~Wilson. ``Computing Equilibria of N-Person Games,'' {\em SIAM Journal on Applied Mathematics}, 21:~80--87, 1971.

@article{Wilson,
  author    = {Robert Wilson},
  title     = {{Computing Equilibria of N-Person Games}},
  journal   = {SIAM Journal on Applied Mathematics},
  volume    = {21},
 year      = {1971},
  pages     = {80-87},
  number = {1}
}







@article{Shamir:1992:IP:146585.146609,
 author = {Shamir, Adi},
 title = {{IP = PSPACE}},
 journal = {J. ACM},
 issue_date = {Oct. 1992},
 volume = {39},
 number = {4},
 month = oct,
 year = {1992},
 issn = {0004-5411},
 pages = {869--877},
 numpages = {9},
 url = {http://doi.acm.org/10.1145/146585.146609},
 doi = {10.1145/146585.146609},
 acmid = {146609},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {IP, PSPACE, interactive proofs},
} 

@article{DBLP:journals/cc/BabaiFL91,
  author    = {L{\'a}szl{\'o} Babai and
               Lance Fortnow and
               Carsten Lund},
  title     = {{Non-Deterministic Exponential Time has Two-Prover Interactive
               Protocols}},
  journal   = {Computational Complexity},
  volume    = {1},
  year      = {1991},
  pages     = {3-40},
  ee        = {http://dx.doi.org/10.1007/BF01200056},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@InProceedings{NisanPackCover02,
  author="Nisan, Noam",
  title="The Communication Complexity of Approximate Set Packing and Covering",
  booktitle="International Colloquium on Automata, Languages and Programming",
  year="2002",
  publisher="Springer Berlin Heidelberg",
  address="Berlin, Heidelberg",
  pages="868--875",
  abstract="We consider a setting where k players are each holding some
    collection of subsets of 1..n. We consider the communication complexity of
    approximately solving two problems: The cover number: the minimal number of
    sets (in the union of their collections) whose union is 1...n and the
    packing number: the maximum number of sets (in the union of their
    collections) that are pair-wise disjoint.",
  isbn="978-3-540-45465-6"
}