Game-Theoretically Fair Leader Election Protocols Overview
Delve into the (Im)possibility of Game-Theoretically Fair Leader Election Protocols, exploring concepts like maximin fairness, commit-and-reveal protocols, and coalition dynamics. Dive deep into the complexities and challenges of achieving fairness in leader elections in a game-theoretic setting.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On the (Im)possibility of Game-Theoretically Fair Leader Election Protocols Ohad Klein, Ilan Komargodski, Chenzhi Zhu
Leader election * Broadcast channels Bob Agree on a leader Eve Alice * Malicious majority Unbiased output against colluded bad parties Hard: impossible in IT [Saks89,BN00], high round-complexity [Cleve86] Coin tossing Game-theoretic fairness [Blum83, CGK+18,CCWS20,KMSW22, ]
Game-theoretic fairness [CGK+18] A coalition of malicious parties: - can t harm honest parties utility (Maximin-fair) - can t increase their utility (CSP-fair) Coin-tossing [Blum83]: perfectly game-theoretically fair ???(?0) ???(?1) ${0,1} ${0,1} ?0 ?1 Open ?0 Open ?1 Win with at least 1/2 ?0 ?1, if no abort 1 ?, if ? aborts { Leader is
Prior upper/lower bounds ?: # of parties # of rounds Tournament tree ?(log?) [CCWS20] [KMSW22] log? loglog? O(loglog?) O(log ?) This work (1) coalition size ? ? ?? Any ? < 1 ? ? 1 ?? ?/2 ? ? loglog? log? Lower bounds: IT impossibility still holds [HO11,BHT18]: OWF necessary [CCWS20]: O(log?) tight for perfect fairness (for commit-and-reveal protocols) Question: Lower bounds for less than n-1
Our results For commit-and-reveal protocols: log ? log log ?rounds necessary for approximate fairness against (? ??) coalitions - Further tradeoff: log log ? log? rounds necessary for perfect fairness against ?? coalitions - Further tradeoff: log? rounds necessary ? coalition Any single-round?-party leader election protocol can t be better than (2 ? 1?)-fair against (? 1) coalitions - The bound is tight log ? log ? rounds necessary (? ?) coalitions
Commit-and-reveal protocols [CCWS20] $ ???(?1,?) ?1,? Open ?1,? Other parties Party ? ???(??,?) $ ??,? A ?-round, ?-party commit- and-reveal leader election: Open ??,? ??,?? ? ,? [?] ? ??,? if Party i aborts at round j Examples [Blum86], [KMSW22]
Maximin fairness Definition. is (? ?)-maximin-fair against coalitions of size ? if and only if ? ? , ? = ?,? ? ?, and any strategy of ?, Pr ? ?? ???????? 1 ? , ? where all parties in ? ? act honestly Any honest party wins with at least ? ??-maximin-fair
Single-round Theorem. Any ?-party leader election can t be better than (2 (? 1)?)-maximin-fair against ? 1 coalitions ??: party 3 is selected if ? aborts 1 1 Pr ?2 1/2 Pr 3 ?? ???????? Pr ?1 ?2 Pr ?1 Pr ?2 1 3 2 2 4 Pr ?1 1/2 ?1 and ?2 not independent? How to show Pr ?? 1/2?
Other results The bound is tight: there exists a n-party leader election protocol that is (2 (? 1)?)-fair. 1 A party winning all matches is selected Otherwise, an arbitrary party is selected [Blum83] Any honest party wins with at least 1/4 3 2 Extended to committee election: any ?-party ?-committee election can t be better than 2 ? 1 bound is tight. 2? 1? ?-maximin-fair. This
Multi-round log ? log log ?rounds necessary against (? 1) coalitions Theorem. for any constant ?-maximin-fair : ?-round, ?-party, ?-maximin-fair 1 2 n After the first round, ? is eliminated if Pr ? ???? ?/? 1/?2 1 2 n Lemma. #(remaining) > ?/log? : ? 1 -round, ?/log?-party, (? 1/?)-maximin-fair 1 2 n ? (log?/loglog?)
Lemma. ?1,1,,?1,?: #(remaining given ?1,1,,?1,?) > ?/log? Otherwise, #(remaining) ?/???? for any ?1,1, ,?1,? ?1,? ?1,2 ?1,1 1 2 n : 1-round, ?-party, ?/log?-committee-election 1 2 n Claim. is 1/?-maximin-fair Contradicts the single- round lower bounds ? is eliminated if Pr ? ???? ?/? ? given all other parties are corrupted
Open problems Lower bounds for general protocols, similar to Cleve s Round complexity given smaller coalition size, especially, constant-ratio Whether our lower bounds are tight Thank you!
