{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113013"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113013","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Search and optimization with randomness in computational economics: equilibria, pricing, and decisions","abstract":"In this thesis we study search and optimization problems from computational economics with primarily stochastic inputs. The results are grouped into two categories: First, we address the smoothed analysis of Nash equilibrium computation. Second, we address two pricing problems in mechanism design, and solve two economically motivated stochastic optimization problems. Computing Nash equilibria is a central question in the game-theoretic study of economic systems of agent interactions. The worst-case analysis of this problem has been studied in depth, but little was known beyond the worst case. We study this problem in the framework of smoothed analysis, where adversarial inputs are randomly perturbed. We show that computing Nash equilibria is hard for 2-player games even when input perturbations are large. This is despite the existence of approximation algorithms in a similar regime. In doing so, our result disproves a conjecture relating approximation schemes to smoothed analysis. Despite the hardness results in general, we also present a special case of co-operative games, where we show that the natural greedy algorithm for finding equilibria has polynomial smoothed complexity. We also develop reductions which preserve smoothed analysis. In the second part of the thesis, we consider optimization problems which are motivated by economic applications. We address two stochastic optimization problems. We begin by developing optimal methods to determine the best among binary classifiers, when the objective function is known only through pairwise comparisons, e.g. when the objective function is the subjective opinion of a client. Finally, we extend known algorithms in the Pandora's box problem --- a classic optimal search problem --- to an order-constrained setting which allows for richer modelling. The remaining chapters address two pricing problems from mechanism design. First, we provide an approximately revenue-optimal pricing scheme for the problem of selling time on a server to jobs whose parameters are sampled i.i.d. from an unknown distribution. We then tackle the problem of fairly dividing chores among a collection of economic agents via a competitive equilibrium, which balances assigned tasks with payouts. We give efficient algorithms to compute such an equilibrium.","abstract_html":"In this thesis we study search and optimization problems from computational economics with primarily stochastic inputs. The results are grouped into two categories: First, we address the smoothed analysis of Nash equilibrium computation. Second, we address two pricing problems in mechanism design, and solve two economically motivated stochastic optimization problems. Computing Nash equilibria is a central question in the game-theoretic study of economic systems of agent interactions. The worst-case analysis of this problem has been studied in depth, but little was known beyond the worst case. We study this problem in the framework of smoothed analysis, where adversarial inputs are randomly perturbed. We show that computing Nash equilibria is hard for 2-player games even when input perturbations are large. This is despite the existence of approximation algorithms in a similar regime. In doing so, our result disproves a conjecture relating approximation schemes to smoothed analysis. Despite the hardness results in general, we also present a special case of co-operative games, where we show that the natural greedy algorithm for finding equilibria has polynomial smoothed complexity. We also develop reductions which preserve smoothed analysis. In the second part of the thesis, we consider optimization problems which are motivated by economic applications. We address two stochastic optimization problems. We begin by developing optimal methods to determine the best among binary classifiers, when the objective function is known only through pairwise comparisons, e.g. when the objective function is the subjective opinion of a client. Finally, we extend known algorithms in the Pandora's box problem --- a classic optimal search problem --- to an order-constrained setting which allows for richer modelling. The remaining chapters address two pricing problems from mechanism design. First, we provide an approximately revenue-optimal pricing scheme for the problem of selling time on a server to jobs whose parameters are sampled i.i.d. from an unknown distribution. We then tackle the problem of fairly dividing chores among a collection of economic agents via a competitive equilibrium, which balances assigned tasks with payouts. We give efficient algorithms to compute such an equilibrium.","abstract_has_math":false,"creators":["Boodaghians, Shant"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Mehta, Ruta","Chekuri, Chandra","Har-Peled, Sariel","Cai, Yang"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-07-12","date_published":"2021-07-12","updated_at":"2026-07-22T22:24:52Z","subjects":["Algorithms","Theory","Game theory","Allocation","Randomized Algorithms"],"languages":["en"],"rights":["Copyright 2021 Shant Boodaghians"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113013","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mehta, Ruta","Chekuri, Chandra","Har-Peled, Sariel","Cai, Yang"]},{"key":"dc:creator","label":"Author","values":["Boodaghians, Shant"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-07-12","2022-01-12T21:45:33Z","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Algorithms","Theory","Game theory","Allocation","Randomized Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Shant Boodaghians"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113013"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis we study search and optimization problems from computational economics with primarily stochastic inputs. The results are grouped into two categories: First, we address the smoothed analysis of Nash equilibrium computation. Second, we address two pricing problems in mechanism design, and solve two economically motivated stochastic optimization problems. Computing Nash equilibria is a central question in the game-theoretic study of economic systems of agent interactions. The worst-case analysis of this problem has been studied in depth, but little was known beyond the worst case. We study this problem in the framework of smoothed analysis, where adversarial inputs are randomly perturbed. We show that computing Nash equilibria is hard for 2-player games even when input perturbations are large. This is despite the existence of approximation algorithms in a similar regime. In doing so, our result disproves a conjecture relating approximation schemes to smoothed analysis. Despite the hardness results in general, we also present a special case of co-operative games, where we show that the natural greedy algorithm for finding equilibria has polynomial smoothed complexity. We also develop reductions which preserve smoothed analysis. In the second part of the thesis, we consider optimization problems which are motivated by economic applications. We address two stochastic optimization problems. We begin by developing optimal methods to determine the best among binary classifiers, when the objective function is known only through pairwise comparisons, e.g. when the objective function is the subjective opinion of a client. Finally, we extend known algorithms in the Pandora's box problem --- a classic optimal search problem --- to an order-constrained setting which allows for richer modelling. The remaining chapters address two pricing problems from mechanism design. First, we provide an approximately revenue-optimal pricing scheme for the problem of selling time on a server to jobs whose parameters are sampled i.i.d. from an unknown distribution. We then tackle the problem of fairly dividing chores among a collection of economic agents via a competitive equilibrium, which balances assigned tasks with payouts. We give efficient algorithms to compute such an equilibrium.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Shant Boodaghians, accepted the attached license on 2021-07-09 at 19:39.","The student, Shant Boodaghians, submitted this Dissertation for approval on 2021-07-09 at 19:47.","This Dissertation was approved for publication on 2021-07-12 at 10:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16844 on 2022-01-12 at 12:44:49","Made available in DSpace on 2022-01-12T21:45:33Z (GMT). No. of bitstreams: 3 BOODAGHIANS-DISSERTATION-2021.pdf: 1148186 bytes, checksum: ba8642f9eae66614b469a04cd57b3a28 (MD5) thesis-source.zip: 12329082 bytes, checksum: 529cd56550935fe9c42a753514109427 (MD5) LICENSE.txt: 4214 bytes, checksum: 490a40acd0d14a98d0380586a12a8ba2 (MD5) Previous issue date: 2021-07-12"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Search and optimization with randomness in computational economics: equilibria, pricing, and decisions"]}]}],"canonical_facts":{"dc:contributor":["Mehta, Ruta","Chekuri, Chandra","Har-Peled, Sariel","Cai, Yang"],"dc:creator":["Boodaghians, Shant"],"dc:date":["2021-07-12","2022-01-12T21:45:33Z","2021-08"],"dc:description":["In this thesis we study search and optimization problems from computational economics with primarily stochastic inputs. The results are grouped into two categories: First, we address the smoothed analysis of Nash equilibrium computation. Second, we address two pricing problems in mechanism design, and solve two economically motivated stochastic optimization problems. Computing Nash equilibria is a central question in the game-theoretic study of economic systems of agent interactions. The worst-case analysis of this problem has been studied in depth, but little was known beyond the worst case. We study this problem in the framework of smoothed analysis, where adversarial inputs are randomly perturbed. We show that computing Nash equilibria is hard for 2-player games even when input perturbations are large. This is despite the existence of approximation algorithms in a similar regime. In doing so, our result disproves a conjecture relating approximation schemes to smoothed analysis. Despite the hardness results in general, we also present a special case of co-operative games, where we show that the natural greedy algorithm for finding equilibria has polynomial smoothed complexity. We also develop reductions which preserve smoothed analysis. In the second part of the thesis, we consider optimization problems which are motivated by economic applications. We address two stochastic optimization problems. We begin by developing optimal methods to determine the best among binary classifiers, when the objective function is known only through pairwise comparisons, e.g. when the objective function is the subjective opinion of a client. Finally, we extend known algorithms in the Pandora's box problem --- a classic optimal search problem --- to an order-constrained setting which allows for richer modelling. The remaining chapters address two pricing problems from mechanism design. First, we provide an approximately revenue-optimal pricing scheme for the problem of selling time on a server to jobs whose parameters are sampled i.i.d. from an unknown distribution. We then tackle the problem of fairly dividing chores among a collection of economic agents via a competitive equilibrium, which balances assigned tasks with payouts. We give efficient algorithms to compute such an equilibrium.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Shant Boodaghians, accepted the attached license on 2021-07-09 at 19:39.","The student, Shant Boodaghians, submitted this Dissertation for approval on 2021-07-09 at 19:47.","This Dissertation was approved for publication on 2021-07-12 at 10:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16844 on 2022-01-12 at 12:44:49","Made available in DSpace on 2022-01-12T21:45:33Z (GMT). No. of bitstreams: 3 BOODAGHIANS-DISSERTATION-2021.pdf: 1148186 bytes, checksum: ba8642f9eae66614b469a04cd57b3a28 (MD5) thesis-source.zip: 12329082 bytes, checksum: 529cd56550935fe9c42a753514109427 (MD5) LICENSE.txt: 4214 bytes, checksum: 490a40acd0d14a98d0380586a12a8ba2 (MD5) Previous issue date: 2021-07-12"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113013"],"dc:language":["en"],"dc:rights":["Copyright 2021 Shant Boodaghians"],"dc:subject":["Algorithms","Theory","Game theory","Allocation","Randomized Algorithms"],"dc:title":["Search and optimization with randomness in computational economics: equilibria, pricing, and decisions"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}