Making Markets and Democracy Work: A Story of Incentives and Computing

Tuomas SandholmIJCAI 2003 · OpenReview

Abstract

Collective choice settings are the heart of society. Game theory provides a basis for engineering the incentives into the interaction mechanism (e.g., rules of an election or auction) so that a desirable system-wide outcome (e.g., president, resource allocation, or task allocation) is chosen even though every agent acts based on self-interest. However, there are a host of computer science issues not traditionally addressed in game theory that have to be addressed in order to make mechanisms work in the real world. Those computing, communication, and privacy issues are deeply intertwined with the economic incentive issues. For example, the fact that agents have limited computational capabilities to determine their own (and others') preferences ruins the incentive properties of established auction mechanisms, and gives rise to new issues. On the positive side, computational complexity can be used as a barrier to strategic behavior in settings where economic mechanism design falls short.

Introduction

This paper, a summary of Thomas Sandholm’s 2003 Computers and Thought Award lecture, explores the powerful intersection of game theory and computer science. It details how we can design markets and voting systems that remain efficient and fair even when participants are self-interested, computationally limited, and protective of their privacy. Sandholm demonstrates that by treating economic mechanism design as a computational problem, we can create "expressive" markets and voting systems that handle real-world complexity.

The Challenge of Real-World Agents

Traditional game theory often assumes "perfectly rational" agents with infinite computing power who can easily reveal all their preferences. In the real world, this is a fantasy. For example, a trucking company bidding on a "bundle" of routes must solve an NP-hard routing problem just to know what that bundle is worth to them.

Furthermore, simple market rules often fail in complex settings. In sequential auctions (selling items one by one), a bidder might win a "right shoe" but fail to get the "left shoe," leaving them with a useless item—a problem known as exposure risk. Sandholm tackles the challenge of designing mechanisms that work when computation is expensive, communication is limited, and agents might try to "game the system."

Algorithmic and Game-Theoretic Methods

The paper synthesizes several novel algorithmic and game-theoretic approaches to bridge the gap between theory and practice:

Combinatorial Auctions & Exchanges

Instead of bidding on single items, agents bid on "bundles" using expressive languages like OR-of-XORs. This allows them to express synergies (items worth more together) and substitutions (wanting only one of several options).

An example of the OR-of-XORs bidding language, allowing bidders to express complex synergies and substitutions.

Specialized Search and Elicitation

  • CABOB Algorithm: A sophisticated "branch-on-bids" search algorithm designed to find the optimal winners in these complex auctions quickly, despite the problem being NP-complete.
  • Preference Elicitation: An incremental querying process where a mediator asks agents for only the specific information needed to find the optimal outcome, preserving privacy and reducing the agent's "valuation effort."
  • Automated Mechanism Design (AMD): Rather than using "one-size-fits-all" rules, Sandholm proposes using algorithms to automatically create the best possible rules (the "mechanism") for a specific situation and objective (e.g., maximizing social welfare or revenue).

Key Insights and Ideas

  • Expressive Competition: Markets shouldn't just be about price. By allowing bidders to express complex side constraints (e.g., "I can only produce 60 tons total" or "I'll give a 2% discount if I win $9M of business"), the market becomes more efficient and easier for humans to use.
  • Strategic Computing: Sandholm identifies a new phenomenon where computationally limited agents might spend their CPU cycles trying to guess other people's preferences to bid strategically, rather than refining their own valuations.
  • Complexity as a Feature: While we usually want algorithms to be fast, Sandholm suggests making voting rules NP-hard to manipulate. If it's computationally impossible for a voter to figure out how to "cheat" the system, they are more likely to vote truthfully.

Results and Impact

The algorithms developed (like CABOB) proved capable of solving massive, real-world reverse auctions to optimality, handling hundreds of thousands of bids and constraints. These techniques were applied in over 70 commercial markets for large-scale industrial procurement. In practice, the preference elicitation methodology often finds the provably optimal outcome while asking for only a "vanishing fraction" of the agents' total possible preference data. Furthermore, the automated mechanism design approach successfully "reinvented" famous theoretical results, such as the Myerson auction, and solved long-standing open problems in revenue-maximizing auctions.

Limitations and Future Work

While NP-hardness is used as a barrier to manipulation, the author acknowledges that "worst-case" hardness isn't enough; future work needs to focus on mechanisms that are hard to manipulate on average. Additionally, there is a need for better normative models to predict how self-interested agents with limited CPU time will actually behave, moving toward a more robust understanding of bounded rationality in economic systems.

Summary updated

Abstract

Collective choice settings are the heart of society. Game theory provides a basis for engineering the incentives into the interaction mechanism (e.g., rules of an election or auction) so that a desirable system-wide outcome (e.g., president, resource allocation, or task allocation) is chosen even though every agent acts based on self-interest. However, there are a host of computer science issues not traditionally addressed in game theory that have to be addressed in order to make mechanisms work in the real world. Those computing, communication, and privacy issues are deeply intertwined with the economic incentive issues. For example, the fact that agents have limited computational capabilities to determine their own (and others') preferences ruins the incentive properties of established auction mechanisms, and gives rise to new issues. On the positive side, computational complexity can be used as a barrier to strategic behavior in settings where economic mechanism design falls short. Novel computational approaches also enable new economic institutions. For example, market clearing technology with specialized search algorithms is enabling a form of interaction that I call expressive competition. As another example, selective incremental preference elicitation can determine the optimal outcome while requiring the agents to determine and reveal only a small portion of their preferences. Furthermore, automated mechanism design can yield better mechanisms than the best known to date.
BibTeX
@inproceedings{sandholm2003making,
  author = {Tuomas Sandholm},
  title = {{Making Markets and Democracy Work: A Story of Incentives and Computing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
  url = {https://openreview.net/forum?id=r1ZcdmMu-S},
}
Figure