Contextually Private Mechanisms
What this paper finds — and why it matters
Haupt and Hitzig introduce a framework for comparing the privacy properties of different mechanism protocols. The core research question is: when a designer commits to implementing a social choice rule, how much superfluous private information must they inevitably learn about agents, and how should they design the elicitation protocol to minimize that exposure?
The setting is a finite-player extensive-form game in which a designer elicits agents’ private types through a dynamic protocol to compute a social choice function. The authors explicitly exclude cryptographic tools and trusted mediators, working under the minimal assumption that the designer learns information if and only if an agent discloses it. This assumption is motivated by the historical prevalence of live dynamic auction formats — ascending formats at Sotheby’s, descending formats at Aalsmeer, oral ascending formats used by the U.S. Forest Service for timber, multi-round clock auctions for radio-spectrum allocation — and by settings where mediating technology is unavailable or costly.
The central object is the contextual privacy violation. A protocol produces a contextual privacy violation for agent i at type profile θ if the designer can distinguish θ_i from some alternative type θ’_i while holding other agents’ types fixed, yet the social choice rule assigns the same outcome at both profiles. Violations are defined at the level of individual agent–state pairs, not aggregated ex ante. A protocol is fully contextually private if it produces no violations; it is maximally contextually private if its set of violations is inclusion-minimal among all protocols that implement the same rule.
The main characterization result (Theorem 1) connects privacy to pivotality: a social choice function admits a fully contextually private protocol if and only if, on every product subset of the type space where agents are collectively pivotal, at least one agent is individually pivotal. The contrapositive is what drives the paper’s impossibility results: whenever a rule contains a region where no single agent’s report changes the outcome but a group’s joint report does, any implementing protocol must produce contextual privacy violations.
Using this characterization, the authors establish that the first-price auction rule (Proposition 2) and serial dictatorship (Proposition 3) admit fully contextually private protocols. Conversely, k-item Vickrey auction rules (Proposition 4) and any stable school-choice rule (Proposition 5) do not admit fully contextually private protocols, because these rules contain type-space regions where agents are only collectively — not individually — pivotal.
For k-item Vickrey auctions, the authors study maximally contextually private protocols. They establish (Proposition 6) that, for a class of social choice rules on totally ordered type spaces that contains k-item Vickrey auctions, it is without loss to consider only protocols consisting of threshold queries that are monotonically increasing or decreasing after an initial guess. This reduction identifies two key design dimensions: the initial query posed to each agent, and the order in which agents are queried.
The main constructive result (Theorem 2) proves that an ascending-join protocol is maximally contextually private for the k-item Vickrey auction. Proposition 7 formalizes the sense in which this protocol protects privacy by delaying queries to certain bidders — it repeatedly asks agents whether they can rule out a particular outcome, and postpones questioning agents whose privacy it is protecting.
The authors also show (Proposition 19) that the ascending-join protocol is minimally relatively informative among protocols that are maximally contextually private. Extensions cover group contextual privacy (Proposition 11) and individual contextual privacy (Proposition 8), showing that individual contextual privacy violations equal the union of contextual privacy violations and nonbossiness violations.
Q: What is a contextual privacy violation, precisely? A: A protocol produces a contextual privacy violation for agent i at type profile θ if the designer can distinguish θ_i from some alternative type θ’_i — holding all other agents’ types fixed — yet the social choice rule assigns the same outcome at both profiles. The violation is defined at the level of individual agent–state pairs. A single additional superfluous distinction at the same (i, θ) pair does not register as a second violation; the framework records whether any unnecessary disclosure occurs for that agent at that state, not the degree of overexposure.
Q: How does contextual privacy differ from relative informativeness? A: Relative informativeness compares two protocols by whether one distinguishes every pair of type profiles the other does, treating all disclosures as equally undesirable. Contextual privacy conditions the notion of a “violation” on the social choice rule: a distinction between θ_i and θ’_i counts as a violation only when the rule assigns the same outcome at both profiles. Relative informativeness thus penalizes the designer for learning information that is necessary to implement the rule, whereas contextual privacy imposes no penalty for learning pivotal information.
Q: What is the pivotality characterization (Theorem 1)? A: A social choice function admits a fully contextually private protocol if and only if, on every product subset of the type space where agents are collectively pivotal, at least one agent is individually pivotal. The necessity direction shows that if a collectively pivotal set exists where no agent is individually pivotal, any implementing iterative partition must contain an earliest node that distinguishes two type profiles leading to the same outcome. The sufficiency direction constructs a contextually private protocol inductively by always querying an individually pivotal agent, ensuring every distinction implies a different outcome.
Q: Which social choice rules admit fully contextually private protocols? A: The first-price auction rule (Proposition 2) and serial dictatorship (Proposition 3) admit fully contextually private protocols. The authors use Theorem 1 to show this: in both rules, any collectively pivotal region contains an individually pivotal agent. By contrast, k-item Vickrey auction rules (Proposition 4), any stable school-choice rule (Proposition 5), efficient allocations in housing assignment, and generalized median voting rules (Section B) do not admit fully contextually private protocols.
Q: Why do k-item Vickrey auctions fail full contextual privacy? A: Proposition 4 shows that k-item Vickrey auctions for k ≥ 1 do not admit fully contextually private protocols. The argument uses the necessary conditions from Theorem 1 (Corollaries 1 and 2): the Vickrey payment rule creates type-space regions where multiple agents together determine the price but no single agent is individually pivotal over the price, so any protocol implementing the Vickrey rule must produce violations for at least some agents at some type profiles.
Q: What is the ascending-join protocol and what does Theorem 2 establish? A: The ascending-join protocol is a specific dynamic elicitation protocol for k-item Vickrey auctions that repeatedly asks agents whether they can rule out a particular outcome, structured as threshold queries ascending from an initial guess. Theorem 2 proves that the ascending-join protocol is maximally contextually private for the k-item Vickrey auction. Proposition 7 formalizes the protection mechanism: the protocol delays queries to the bidders whose privacy it is protecting, querying them only when their responses become necessary for determining the outcome.
Q: What does Proposition 6 establish about the structure of maximally contextually private protocols? A: For a class of social choice rules on totally ordered type spaces that contains k-item Vickrey auctions, Proposition 6 shows it is without loss of generality to consider only protocols consisting of threshold queries that are monotonically increasing or decreasing in the threshold after an initial guess. This result serves as a theoretical reduction (enabling proofs that certain protocols are maximally private) and as a practical design principle (identifying the initial query and the ordering of agents as the two key design dimensions).
Q: How does contextual privacy relate to obviously dominant strategies? A: The paper treats privacy properties and incentive properties as largely orthogonal questions, to be analyzed separately. For the ascending-join protocol specifically, the authors verify obvious dominance — the most demanding incentive notion they consider — which requires that at every history, the worst-case payoff from the equilibrium action exceeds the best-case payoff from any deviation. This analysis proceeds after the contextual privacy properties of the protocol are established.
Q: What is group contextual privacy and why do the authors focus on individual-level violations instead? A: Group contextual privacy requires that whenever the designer learns any property of the joint type profile, that property must affect the outcome. The authors show (Proposition 11) that a protocol is fully group contextually private if and only if every query rules out at least one outcome. They argue this standard is extremely demanding and produces a very coarse partial order: improving in the group privacy order requires restructuring the entire protocol tree rather than making agent- or state-specific improvements. They also note that normative accounts of privacy, including Nissenbaum’s contextual integrity theory, center on individual rather than group information.
Q: How does individual contextual privacy relate to nonbossiness? A: Individual contextual privacy (Proposition 8) requires that if two type profiles differing only in agent i’s type are distinguished, they must lead to different allocations for agent i — presuming a private allocation domain. The paper shows that the set of individual contextual privacy violations equals the union of contextual privacy violations and nonbossiness violations: individual contextual privacy is violated precisely when either (a) agent i’s superfluous type information is revealed, or (b) agent i is “bossy” — able to change others’ outcomes without changing their own.
Q: What is the relationship between the ascending-join protocol and minimal relative informativeness? A: Proposition 19 shows that the ascending-join protocol is not only maximally contextually private but also minimally relatively informative among protocols that are maximally contextually private. That is, among all maximally contextually private protocols, the ascending-join protocol reveals the smallest total amount of information about the type profile in the relative informativeness order. This establishes relative informativeness as a useful refinement for selecting among contextually privacy-equivalent protocols.
Q: What motivates the exclusion of cryptographic tools and trusted mediators from the framework? A: The authors work under the minimal assumption that the designer learns information if and only if an agent directly discloses it — no commitment to forget, anonymize, or cryptographically conceal. They motivate this on two grounds: first, many real-world auction formats are live and dynamic with no mediating technology; second, advanced cryptography is often costly in time, money, or computation, and studying the no-mediator benchmark can explain the historical prevalence of dynamic protocols and inform auction design in environments where cryptography may become unavailable (for example, due to quantum computing). The authors cite a Danish sugar-beet auction as a case where designers themselves questioned whether full multiparty computation was necessary.
Contextual privacy violation: A protocol produces a contextual privacy violation for agent i at type profile θ if the designer can distinguish θ_i from some alternative type θ’_i — holding other agents’ types fixed — yet the social choice rule assigns the same outcome at both profiles. The violation is assigned at the level of individual agent–state pairs.
Maximally contextually private protocol: A protocol whose set of contextual privacy violations is inclusion-minimal among all protocols that implement the same social choice rule — equivalently, a protocol that lies on the Pareto frontier of implementation and contextual privacy, such that no other implementing protocol weakly reduces every violation and strictly reduces at least one.
Iterative partition: A directed rooted tree whose nodes are subsets of the type space, where each non-leaf node is split into children by partitioning on a single agent’s type. Any protocol is equivalent (in terms of what the designer learns) to a partitional protocol induced by an iterative partition (Proposition 1).
Individual pivotality: On a product set of type profiles, agent i is individually pivotal if there exist two subsets of agent i’s types such that every type profile from one subset leads to a different outcome than every type profile from the other subset, holding others’ types fixed.
Collective pivotality: Agents are collectively pivotal on a product set if there exist two type profiles in that set with different outcomes. Collective pivotality without any agent being individually pivotal is precisely the condition that forces contextual privacy violations (Theorem 1).
Ascending-join protocol: A specific dynamic protocol for k-item Vickrey auctions that poses threshold queries in ascending order after an initial guess, repeatedly asking agents whether they can rule out a particular outcome. It is maximally contextually private (Theorem 2) and minimally relatively informative among maximally contextually private protocols (Proposition 19), and it achieves privacy protection by delaying queries to agents whose privacy it protects (Proposition 7).
Relative informativeness: A partial order on protocols defined by: protocol P is less relatively informative than P’ if every pair of type profiles P distinguishes is also distinguished by P’. Unlike contextual privacy, relative informativeness treats all disclosures as equally undesirable and does not condition on the social choice rule. The paper positions it as a useful refinement for selecting among contextually privacy-equivalent protocols.