More Like this

1. Delegated Search Approximates Efficient Search

   https://doi.org/10.1145/3219166.3219205  

   Kleinberg, Jon; Kleinberg, Robert (June 2018, Proceedings of the 2018 ACM Conference on Economics and Computation)

   There are many settings in which a principal performs a task by delegating it to an agent, who searches over possible solutions and proposes one to the principal. This describes many aspects of the workflow within organizations, as well as many of the activities undertaken by regulatory bodies, who often obtain relevant information from the parties being regulated through a process of delegation. A fundamental tension underlying delegation is the fact that the agent's interests will typically differ -- potentially significantly -- from the interests of the principal, and as a result the agent may propose solutions based on their own incentives that are inefficient for the principal. A basic problem, therefore, is to design mechanisms by which the principal can constrain the set of proposals they are willing to accept from the agent, to ensure a certain level of quality for the principal from the proposed solution. In this work, we investigate how much the principal loses -- quantitatively, in terms of the objective they are trying to optimize -- when they delegate to an agent. We develop a methodology for bounding this loss of efficiency, and show that in a very general model of delegation, there is a family of mechanisms achieving a universal bound on the ratio between the quality of the solution obtained through delegation and the quality the principal could obtain in an idealized benchmark where they searched for a solution themself. Moreover, it is possible to achieve such bounds through mechanisms with a natural threshold structure, which are thus structurally simpler than the optimal mechanisms typically considered in the literature on delegation. At the heart of our framework is an unexpected connection between delegation and the analysis of prophet inequalities, which we leverage to provide bounds on the behavior of our delegation mechanisms. 

   more » « less
2. Rectangle Search: An Anytime Beam Search

   https://doi.org/10.1609/aaai.v38i18.30063  

   Lemons, Sofia; Ruml, Wheeler; Holte, Rob; Linares_Lopez, Carlos (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   Anytime heuristic search algorithms try to find a (potentially suboptimal) solution as quickly as possible and then work to find better and better solutions until an optimal solution is obtained or time is exhausted. The most widely-known anytime search algorithms are based on best-first search. In this paper, we propose a new algorithm, rectangle search, that is instead based on beam search, a variant of breadth-first search. It repeatedly explores alternatives at all depth levels and is thus best-suited to problems featuring deep local minima. Experiments using a variety of popular search benchmarks suggest that rectangle search is competitive with fixed-width beam search and often performs better than the previous best anytime search algorithms. 

   more » « less
3. Triangle Search: An Anytime Beam Search

   Lemons, Sofia; Ruml, Wheeler; Linares López, Carlos; Holte, Robert C. (January 2023, Proceedings of the ICAPS-23 Workshop on Heuristics and Search for Domain-Independent Planning)
4. Search versus Search for Collapsing Electoral Control Types (extended abstract)

   Carleton, B.; Chavrimootoo, Michael C.; Hemaspaandra, Lane A.; Narvaez, D.; Taliancich, C.; Welles, H. (May 2023, Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems)

   Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election sys- tem coincide as sets (i.e., they are collapsing pairs), which had pre- viously gone undetected in the literature. While both members of a collapsing pair certainly have the same decision complexity, there is no guarantee that the associated search problems also have the same complexity. For practical purposes, search problems are more relevant than decision problems. Our work focuses on exploring the relationships between the search versions of collapsing pairs. We do so by giving a framework that relates the complexity of search problems via efficient reduc- tions that transform a solution from one problem to a solution of the other problem on the same input. We not only establish that the known decision collapses carry over to the search model, but also refine our results by determining for the concrete systems plurality, veto, and approval whether collapsing search-problem pairs are polynomial-time computable or NP-hard. 

   more » « less
5. Multi-Objective Neural Architecture Search by Learning Search Space Partitions

   Zhao, Yiyang; Wang, Linnan; Guo, Tian (June 2024, Journal of Machine Learning Research)