{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/90167"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/90167","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Algorithms for strategic agents","abstract":"In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents with interests of their own? The unique challenge stems from the fact that the agents may choose to lie about the input in order to manipulate the behavior of the algorithm for their own interests, and tools from Game Theory are therefore required in order to predict how these agents will behave. We develop a new algorithmic framework with which to study such problems. Specifically, we provide a computationally efficient black-box reduction from solving any optimization problem on \"strategic input,\" often called algorithmic mechanism design to solving a perturbed version of that same optimization problem when the input is directly given, traditionally called algorithm design. We further demonstrate the power of our framework by making significant progress on several long-standing open problems. First, we extend Myerson's celebrated characterization of single item auctions to multiple items, providing also a computationally efficient implementation of optimal auctions. Next, we design a computationally efficient 2-approximate mechanism for job scheduling on unrelated machines, the original problem studied in Nisan and Ronen's paper introducing the field of Algorithmic Mechanism Design. This matches the guarantee of the best known computationally efficient algorithm when the input is directly given. Finally, we provide the first hardness of approximation result for optimal mechanism design.","abstract_html":"In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents with interests of their own? The unique challenge stems from the fact that the agents may choose to lie about the input in order to manipulate the behavior of the algorithm for their own interests, and tools from Game Theory are therefore required in order to predict how these agents will behave. We develop a new algorithmic framework with which to study such problems. Specifically, we provide a computationally efficient black-box reduction from solving any optimization problem on "strategic input," often called algorithmic mechanism design to solving a perturbed version of that same optimization problem when the input is directly given, traditionally called algorithm design. We further demonstrate the power of our framework by making significant progress on several long-standing open problems. First, we extend Myerson's celebrated characterization of single item auctions to multiple items, providing also a computationally efficient implementation of optimal auctions. Next, we design a computationally efficient 2-approximate mechanism for job scheduling on unrelated machines, the original problem studied in Nisan and Ronen's paper introducing the field of Algorithmic Mechanism Design. This matches the guarantee of the best known computationally efficient algorithm when the input is directly given. Finally, we provide the first hardness of approximation result for optimal mechanism design.","abstract_has_math":false,"creators":["Weinberg, S. Matthew (Seth Matthew)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Constantinos Daskalakis."],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-07-22T22:21:59Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/90167","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Constantinos Daskalakis."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Weinberg, S. Matthew (Seth Matthew)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-09-19T21:43:43Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-09-19T21:43:43Z"]},{"key":"dc:date.issued","label":"Date","values":["2014"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/90167"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D. in Computer Science, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 123-135)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents with interests of their own? The unique challenge stems from the fact that the agents may choose to lie about the input in order to manipulate the behavior of the algorithm for their own interests, and tools from Game Theory are therefore required in order to predict how these agents will behave. We develop a new algorithmic framework with which to study such problems. Specifically, we provide a computationally efficient black-box reduction from solving any optimization problem on \"strategic input,\" often called algorithmic mechanism design to solving a perturbed version of that same optimization problem when the input is directly given, traditionally called algorithm design. We further demonstrate the power of our framework by making significant progress on several long-standing open problems. First, we extend Myerson's celebrated characterization of single item auctions to multiple items, providing also a computationally efficient implementation of optimal auctions. Next, we design a computationally efficient 2-approximate mechanism for job scheduling on unrelated machines, the original problem studied in Nisan and Ronen's paper introducing the field of Algorithmic Mechanism Design. This matches the guarantee of the best known computationally efficient algorithm when the input is directly given. Finally, we provide the first hardness of approximation result for optimal mechanism design."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D. in Computer Science"]},{"key":"dc:title","label":"Title","values":["Algorithms for strategic agents"]}]}],"canonical_facts":{"dc:contributor.advisor":["Constantinos Daskalakis."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Weinberg, S. Matthew (Seth Matthew)"],"dc:date.accessioned":["2014-09-19T21:43:43Z"],"dc:date.available":["2014-09-19T21:43:43Z"],"dc:date.issued":["2014"],"dc:description":["Thesis: Ph. D. in Computer Science, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 123-135)."],"dc:description.abstract":["In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents with interests of their own? The unique challenge stems from the fact that the agents may choose to lie about the input in order to manipulate the behavior of the algorithm for their own interests, and tools from Game Theory are therefore required in order to predict how these agents will behave. We develop a new algorithmic framework with which to study such problems. Specifically, we provide a computationally efficient black-box reduction from solving any optimization problem on \"strategic input,\" often called algorithmic mechanism design to solving a perturbed version of that same optimization problem when the input is directly given, traditionally called algorithm design. We further demonstrate the power of our framework by making significant progress on several long-standing open problems. First, we extend Myerson's celebrated characterization of single item auctions to multiple items, providing also a computationally efficient implementation of optimal auctions. Next, we design a computationally efficient 2-approximate mechanism for job scheduling on unrelated machines, the original problem studied in Nisan and Ronen's paper introducing the field of Algorithmic Mechanism Design. This matches the guarantee of the best known computationally efficient algorithm when the input is directly given. Finally, we provide the first hardness of approximation result for optimal mechanism design."],"dc:description.degree":["Ph. D. in Computer Science"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/90167"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Algorithms for strategic agents"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:59Z"}