Solving the Traveling Salesman Problem? Not quite, but here are more research questions from the Office of Technology

Earlier this year, the Office of Technology (OT) published a list of research questions and made reference to the long history in mathematics of doling out questions that, as mathematician Paul Erdős put it, “can isolate an essential difficulty in a particular area, serving as a benchmark against which progress ... can be measured.”^[1]

In the spirit of posing complex questions, the Traveling Salesman Problem is a classic problem in the theory of computation that asks a seemingly simple question: given a list of cities and distances between them, what is the shortest possible route that visits each city exactly once and returns to the origin city?^[2] Even though computers are able to compute specific solutions to the Traveling Salesman Problem, the problem quickly gets unwieldy as the number of cities grow. In 1972, American computer scientist Richard Karp showed that the problem is provably unwieldy^[3]—there is no one magical idea that will solve the Traveling Salesman Problem in a quick and efficient way.^[4]

While Karp’s proof may seem discouraging, we believe it is quite the opposite. In fact, it presents a statement about computation and hard problems more generally. While abstract solutions to complex problems may be difficult to solve efficiently or with a single “silver bullet” solution, concrete approaches to specific problems can be achieved with time and effort. In the same way, OT staff believes that with resources, effort, and creativity, there are ways to address tractable problems in the marketplace. This can be done by targeting harm further upstream, being forward-looking in anticipating impacts of emerging technologies and nascent markets across sectors, and prioritizing technical experts at the table for enforcement work.

Given that, we wanted to highlight a new batch of questions that may be of interest to researchers, civil society organizations, practitioners, and consumers about technological issues facing the public. These new questions focus on how—regardless of the uncertainty in the world—upstream actions or ideas can prevent downstream harms from occurring.

This list of questions does not indicate a particular agency position on a given topic. The agency is not requesting submissions to the questions posed, nor is the agency commissioning research. OT is interested in learning more about these issues and recognizes that researchers can draw on a range of information including expertise from professional disciplines, practical and lived experience, and anecdotal evidence, as well as a variety of research methods.

A few issues of current interest are:

AI and Competition – On the impact to competition from important inputs into generative AI models:

1. How might firms who have acquired access to large datasets leverage that access to further strengthen their data advantages for AI model training—via repurposing in-house user generated content, striking contractual “deals” with rightsholders and online platforms, or repurposing data beyond its intended use? What are the impacts of these practices on consumers and workers (e.g., creative professionals)? What are the impacts of these practices on competition and consumer protection?
2. How are AI developers determining what constitutes “high-quality data” to use in AI model training? And how can these determinations impact outputs including speech and query results?
3. How might high-dollar “partnerships” across players in the AI marketplace, such as cloud service providers or operating system developers and AI developers, continue to evolve? How can outside organizations continue to best monitor these changes?
4. How are firms bundling existing products with AI offerings in ways that may affect competition? What practices may make it harder to switch to other providers?

AI Procurement – On the impact of AI to the large-scale purchase of goods and services for organizations:

5. How can procurement contracts encourage accountable, pro-competitive practices through their terms?
6. In what ways are large software providers allowing market entrants or smaller players to interoperate with their products or services—or not? What are the impacts of these design decisions?

Commercial Surveillance & Data Privacy – On tracking mechanisms and the surveillance economy:

7. Beyond data brokers, targeted advertisements, and surveillance pricing, what are emerging forms of commercial surveillance? In what ways are companies tracking and targeting consumers (including children) and workers based on data that can be linked back to an individual or household? What information is being collected and used? What are the impacts of this tracking on consumers?
8. How might firms be using claims around anti-fraud and security efforts as pretext to engage in more pervasive and harder-to-avoid methods of commercial surveillance?

Tech Investors – On the incentives of technology investors, such as private equity firms, venture capitalists, and tech accelerators:

9. How might investor incentives encourage consolidation in technology markets?
10. How might investors help early-stage companies compete with bigger, more established firms and drive the market in more innovative directions that allow for human flourishing?

Hardware & Manufacturing – On competition dynamics at the lower levels of the technology stack, such as computing infrastructure, servers, and chips, for critical infrastructure and goods:

11. What current market dynamics contribute to fragility of domestic supply chains for critical technology infrastructure and goods such as servers and chips? How does that affect a wide range of areas, including consumer goods, business products and services, and national security?

Building Digital Capacity – On building and growing digital capacity in tech regulatory organizations:

12. How might government regulatory and enforcement environments attract and retain technical talent in order to effectively evaluate the potential benefits and harms of technology products and services?