💻 computer science

Biprofile Deviation Logic: Report-Replacement Frames and Audit Witnesses

This paper introduces a sound and complete logical framework, $H_{\mathrm{bp}}$ , for modeling biprofile deviations in social choice where coalitions alter report profiles, and extends this abstract theory with a novel audit layer featuring typed manipulation witnesses and criteria for handling off-domain extensions and public deletions.

Original authors: Faruk Alpay, Baris Basaran

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Faruk Alpay, Baris Basaran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Two Worlds in One Room

Imagine a voting system as a room with two layers of reality happening at the same time:

The "True" World: This is how people actually feel. It's their honest preferences.
The "Reported" World: This is what people say they feel when they cast their vote.

Usually, we assume these two worlds are identical. But in strategic voting, people might lie. They might say, "I love Candidate B!" even though they actually prefer Candidate A, just to get a better result.

This paper introduces a new way to model that situation. Instead of treating a vote as a single snapshot, the authors treat every moment as a pair: (True World, Reported World).

The Core Idea: The "Report-Replacement" Game

The authors imagine a game where a group of people (a "coalition") can secretly swap their reported votes to see if they can get a better outcome, while their true feelings stay frozen in place.

The Analogy: Imagine a group of friends ordering pizza.
- True World: Everyone actually wants Pepperoni.
- Reported World: To get a discount, they all tell the waiter they want Cheese.
- The Magic Move: The authors define a "coalition modality" as a button that lets a specific group of friends change only their order slip (the report) without changing their actual stomachs (the true preference).

The paper proves that if you follow the rules of this game, you can mathematically predict exactly what happens when groups change their reports. They built a "rulebook" (a logic system) that is sound (it never lies) and complete (it can prove everything that is true in this specific game).

The "Audit" Layer: Checking the Receipts

The most practical part of the paper is the Audit Layer. Think of this as a forensic accountant for voting systems.

When a voting rule is certified as "fair" (meaning no one can manipulate it), the authors ask: "What happens if we change the rules slightly?"

They identified three specific ways a voting system can break, and they created a "witness record" (a digital receipt) to track exactly which part broke:

The "Edge-Deleted" Failure (Restricted Domain):
- Analogy: Imagine a menu where you can only order from a list of 5 items. If you try to order a 6th item, the system says "Error: Item not on menu."
- The Paper's Claim: If you restrict the types of votes allowed (e.g., only "single-peaked" preferences), a manipulation might disappear simply because the "bad" vote is no longer allowed. The audit checks if the "edge" (the path to the bad vote) was deleted.
The "Boundary-Row" Failure (Off-Domain Extension):
- Analogy: You have a safe menu of 5 items. You decide to add a 6th item to the menu. The audit says: "Don't check the whole menu again! Just check the new item."
- The Paper's Claim: If you expand the voting rules to allow new types of reports, you don't need to re-prove the whole system. You only need to check the "boundary"—the new, weird votes that were previously impossible. If the new vote creates a manipulation, the system breaks.
The "Missing Corner" Failure (Public Deletion):
- Analogy: Imagine a square table with four legs. If you remove one leg, the table might still stand, but it's wobbly. If you remove the "middle" support that connects the legs, the whole structure collapses mathematically, even if the corners look fine.
- The Paper's Claim: If you delete some voting options from a system, you might accidentally remove a "midpoint" needed to connect two other options. The system might still look like it works, but it loses its mathematical "rigidity" (called factor closure). The audit checks if the "middle" is missing.

The "Single-Peaked" Example

To prove their audit tools work, the authors used a classic voting scenario: The Median Voter Theorem.

Imagine a political spectrum from Left to Right.
If everyone's preferences are "single-peaked" (they like the center best and hate the extremes), a specific voting rule (the Median Rule) is known to be fair.
The authors showed that if you stick to this "center-only" world, the system is safe.
But if you let people vote for "weird" preferences (off the spectrum), the system might break.
Their audit tool successfully identified exactly where the break happened: it was a specific "boundary" vote that shouldn't have been allowed.

The "Toolbox" (Supplementary Material)

The paper isn't just theory; it comes with a digital toolkit to verify these claims:

A Certificate Checker: A script that checks if a voting system's "receipt" is valid.
Lean & Alloy Companions: Computer programs that act like "proof assistants." They double-check the math to ensure the authors didn't make a logical error in their small examples.
The "Witness Record": A standardized format for logging a manipulation. Instead of just saying "This system is broken," it says: "It's broken because Agent 3 changed their report from X to Y, and the outcome shifted from A to B."

Summary

This paper builds a mathematical microscope for voting systems.

It splits the world into Truth and Reports.
It proves that the logic of changing reports follows a strict, predictable pattern (like a game of chess with specific rules).
It creates an audit system that tells you exactly why a voting system fails if you change the rules:
- Did you block a path? (Edge-Deleted)
- Did you add a dangerous new path? (Boundary-Row)
- Did you remove a necessary support beam? (Missing Corner)

The authors don't claim to have invented a new voting method. Instead, they invented a diagnostic tool to help verify that existing voting methods stay fair when the rules of the game change.

Technical Summary: Biproprofile Deviation Logic: Report-Replacement Frames and Audit Witnesses

Problem Statement
The paper addresses the formalization of strategic social choice, specifically the distinction between a "true" preference profile ( $R$ ) that determines welfare comparisons and a "submitted" report profile ( $P$ ) that determines the outcome of a social choice rule. Traditional modal logic approaches often treat deviation as a generic graph edge or rely on general correspondence theory (e.g., Sahlqvist theorems) without explicitly modeling the algebraic structure of coalition-based report replacements. The authors identify a gap in providing a logic that treats the state as a pair $(R, P)$ , where modalities correspond strictly to changing the report coordinates of a specific coalition $C$ while leaving the true profile $R$ invariant. Furthermore, there is a need for an "audit layer" to verify how strategic properties (like strategy-proofness) behave when the domain of admissible reports is altered (e.g., restricted, extended, or publicly deleted) without re-proving classical impossibility theorems.

Methodology
The authors develop Biprofile Deviation Logic, a multimodal logic where states are pairs $(R, P)$ .

Semantics: The logic uses a class of frames $\text{Dev}(N)$ defined by a set of agents $N$ . The accessibility relations $E_C$ for a coalition $C$ represent the replacement of report coordinates for agents in $C$ . The core semantic constraint is the exact union-composition law: $E_C \circ E_D = E_{C \cup D}$ . This captures the intuition that independent report changes by disjoint coalitions compose to a change by their union.
Proof Theory: A Hilbert system $H_{bp}$ is defined with axioms for S5 behavior (reflexivity, transitivity, Euclidean property) for each coalition, an identity axiom for the empty coalition, inclusion axioms for coalition subsets, and a reduction axiom for the union of coalitions.
Completeness Proof: The paper provides a direct canonical completeness proof for $H_{bp}$ . A key technical step involves constructing a "midpoint" in the canonical model to prove the reverse inclusion of the composition axiom ( $R_{C \cup D} \subseteq R_C \circ R_D$ ), ensuring the canonical frame satisfies the exact union-composition law without presupposing a product structure.
Representation Separation: The authors distinguish between abstract frames satisfying $\text{Dev}(N)$ equations and concrete report-coordinate products. They prove that an additional coordinate separation condition is required to recover a genuine product structure from the abstract algebra.
Audit Framework: The paper translates classical social choice concepts (strategy-proofness, Gibbard–Satterthwaite, single-peakedness) into modal formulas. It then introduces "audit theorems" that diagnose how these properties change when the representation of the domain changes (e.g., off-domain extensions or public deletions).

Key Contributions

Modal Core (Theorem 1): The paper proves the soundness and completeness of $H_{bp}$ for the abstract frame class $\text{Dev}(N)$ . It explicitly isolates and proves the "midpoint" step required for the reverse composition axiom, which is the non-routine part of the canonical construction for this specific semilattice table.
Representation Boundary (Proposition 1): The authors demonstrate that satisfying the abstract $\text{Dev}(N)$ equations is insufficient to guarantee a coordinate-product structure. They identify coordinate separation as the necessary and sufficient condition to recover a concrete report-coordinate product from an abstract deviation frame.
Audit Theorems:
- Theorem 4 (Boundary-Row Criterion): Establishes that extending a rule to a larger report domain creates new manipulation witnesses only at the "boundary" (i.e., using reports that were previously inadmissible). This allows for incremental verification of strategy-proofness without re-checking the entire domain.
- Proposition 6 (Factor-Closure Criterion): Provides a necessary and sufficient condition for a public deletion (submodel) to preserve the $\text{Dev}(N)$ algebraic structure. The condition requires that the surviving states must be "factor closed," meaning any surviving edge $E_{C \cup D}$ must be factorizable through a surviving intermediate state.
Finite Audit Mechanisms: The paper introduces a typed certificate format and executable checkers (in Python, Lean, and Alloy) to verify finite instances of these logic properties. This includes a "witness replay" mechanism that classifies failures as edge-deleted, boundary-witnesses, or unsafe-updates based on which field of the witness record changed.

Results

Completeness: The system $H_{bp}$ is proven complete for $\text{Dev}(N)$ . The proof relies on a canonical model construction that explicitly realizes the union-composition law.
Translation of Classical Theorems: The Gibbard–Satterthwaite theorem and Moulin's median voter theorem are successfully translated into the biprofile language. The paper does not reprove these theorems but uses the new language to analyze their behavior under domain changes.
Case Study: A five-agent single-peaked median example is used to demonstrate the audit layer. The study shows how a single manipulation witness tuple $(R, P, C, Q, x, y)$ $(R, P, C, Q, x, y)$ is interpreted differently under three scenarios:
1. Restricted Domain: The witness is "edge-deleted" because the deviated report $Q$ is not generated by the restricted domain generator.
2. Off-Domain Extension: The witness is a "boundary-row" failure, created solely by the new admissible report $Q$ .
3. Public Deletion: The witness may survive (endpoints remain), but the update is "unsafe" because the deletion of a mixed midpoint breaks the factor-closure required for the $\text{Dev}(N)$ algebra.
Verification Complexity: Proposition 7 establishes that verifying a submitted finite typed certificate is polynomial in the size of the certificate for a fixed set of agents $N$ .

Significance and Claims
The paper claims significance primarily as a formal audit framework rather than a new impossibility theorem.

Separation of Concerns: It separates the proof-theoretic spine (completeness of the abstract algebra) from the representation boundary (recovering coordinates) and the application layer (auditing domain changes).
Operational Value: The authors argue that their "audit layer" provides a diagnostic interface for social choice mechanisms. Instead of re-running complex impossibility proofs when a domain is modified, verifiers can use the boundary-row theorem to check only new rows and the factor-closure criterion to check if a deletion preserves the necessary algebraic structure.
Modesty: The authors explicitly state that they do not provide a general satisfiability algorithm for $\text{Dev}(N)$ or a new complexity bound for succinctly represented rules. The completeness result is for the abstract frame class, and the finite checks are for explicitly supplied certificates. The work is presented as a "small but complete audit scenario" that clarifies where and why a representation change affects strategic properties, rather than offering a new solution to the fundamental problems of social choice.