Zhechen Li

Zhechen Li, Ao Liu, Lirong Xia et al.

Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the well-known Condorcet method, and focus on three classes of voting rules in this family: Laplacian Condorcet method ($\CMLAP_λ$), exponential Condorcet method ($\CMEXP_λ$), and randomized response Condorcet method ($\CMRR_λ$), where $λ$ represents the level of noise. We prove that all of our rules satisfy absolute monotonicity, lexi-participation, probabilistic Pareto efficiency, approximate probabilistic Condorcet criterion, and approximate SD-strategyproofness. In addition, $\CMRR_λ$ satisfies (non-approximate) probabilistic Condorcet criterion, while $\CMLAP_λ$ and $\CMEXP_λ$ satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.

Xinlun Zhang, Zhechen Li, Yongzhi Cao et al.

A diffusion auction refers to a selling process conducted over a social network, where each participant submits a bid and may invite other potential buyers to join the auction. Although various mechanisms have been proposed, none of them can simultaneously achieve incentive compatibility, non-negative revenue, and approximate efficiency with a constant approximation bound. In this paper, we propose the Probabilistic Diffusion Mechanism (PDM), a novel mechanism tailored for path graphs, which satisfies all three desired properties. We further extend PDM to general network structures through a map $f$, resulting in the $f$-PDM mechanism, which preserves the key properties of the original design. Beyond these, when $f$ satisfies properties such as breadth-first order, $f$-PDM also ensures Sybil-proofness and provides approximate revenue. Furthermore, to address buyer collusion, we introduce a modified version of the mechanism that balances collusion-proofness with revenue approximation. Finally, we extend the design to multi-unit diffusion auctions -- a more challenging setting -- and propose a simple yet effective mechanism, Multi-Unit PDM (MUPDM), that achieves approximate efficiency while maintaining IC. Moreover, we design Sybil-Proof MUPDM (SP-MUPDM) to resist Sybil attacks in the multi-item scenario.