Related Research Articles
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.
Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
Avi Wigderson is an Israeli computer scientist and mathematician. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural networks. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science. He also received the 2023 Turing Award for his contributions to the understanding of randomness in the theory of computation.
Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects. It typically employs the analytic tools of theoretical computer science, such as worst case analysis and approximation ratios, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem. This often, for example, rules out the classic economic mechanism, the Vickrey–Clarke–Groves auction.
Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.
Shang-Hua Teng is a Chinese-American computer scientist. He is the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California. Previously, he was the chairman of the Computer Science Department at the Viterbi School of Engineering of the University of Southern California.
Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. He is the Dean of the College of Computing at the Illinois Institute of Technology.
Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.
Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Distinguished Professor and Department Chair of Applied Mathematics and Statistics and Research Professor of Computer Science at Stony Brook University.
Anna R. Karlin is an American computer scientist, the Microsoft Professor of Computer Science & Engineering at the University of Washington.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
Timothy Avelin Roughgarden is an American computer scientist and a professor of Computer Science at Columbia University. Roughgarden's work deals primarily with game theoretic questions in computer science.
Andrew Vladislav Goldberg is an American computer scientist working primarily on design, analysis, and experimental evaluation of algorithms. He also worked on mechanism design, computer systems, and complexity theory. Currently he is a Senior Principal Scientist at Amazon.com.
Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.
Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.
A knapsack auction is an auction in which several identical items are sold, and there are several bidders with different valuations interested in different amounts of items. The goal is to choose a subset of the bidders with a total demand, at most, the number of items and, subject to that, a maximum total value. Finding this set of bidders requires solving an instance of the knapsack problem, which explains the term "knapsack auction".
References
- ↑ "ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use — Association for Computing Machinery". acm.org. 2012-07-12. Archived from the original on 2012-07-12. Retrieved 2024-01-15.
- ↑ Nisan, Noam; Ronen, Amir (1999-05-01). "Algorithmic mechanism design (Extended abstract)". Proceedings of the thirty-first annual ACM symposium on Theory of Computing. STOC '99. New York, NY, US: Association for Computing Machinery. pp. 129–140. doi:10.1145/301250.301287. ISBN 978-1-58113-067-6.
- ↑ Nisan, Noam; Ronen, Amir (2001-04-01). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1): 166–196. doi:10.1006/game.1999.0790. ISSN 0899-8256.