Source author record

Edward Lui

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computer Science and Game Theory math.CO

Catalog footprint

Research overview

4works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Stronger Impossibility Results for Strategy-Proof Voting with i.i.d. Beliefs

The classic Gibbard-Satterthwaite theorem says that every strategy-proof voting rule with at least three possible candidates must be dictatorial. In \cite{McL11}, McLennan showed that a similar impossibility result holds even if we consider a weaker notion of strategy-proofness where voters believe that the other voters' preferences are i.i.d.~(independent and identically distributed): If an anonymous voting rule (with at least three candidates) is strategy-proof w.r.t.~all i.i.d.~beliefs and is also Pareto efficient, then the voting rule must be a random dictatorship. In this paper, we strengthen McLennan's result by relaxing Pareto efficiency to $ε$ -Pareto efficiency where Pareto efficiency can be violated with probability $ε$ , and we further relax $ε$ -Pareto efficiency to a very weak notion of efficiency which we call $ε$ -super-weak unanimity. We then show the following: If an anonymous voting rule (with at least three candidates) is strategy-proof w.r.t.~all i.i.d.~beliefs and also satisfies $ε$ -super-weak unanimity, then the voting rule must be $O(ε)$ -close to random dictatorship.

preprint2015arXiv

Voting with Coarse Beliefs

The classic Gibbard-Satterthwaite theorem says that every strategy-proof voting rule with at least three possible candidates must be dictatorial. Similar impossibility results hold even if we consider a weaker notion of strategy-proofness where voters believe that the other voters' preferences are i.i.d.~(independent and identically distributed). In this paper, we take a bounded-rationality approach to this problem and consider a setting where voters have "coarse" beliefs (a notion that has gained popularity in the behavioral economics literature). In particular, we construct good voting rules that satisfy a notion of strategy-proofness with respect to coarse i.i.d.~beliefs, thus circumventing the above impossibility results.

preprint2014arXiv

Bayesian Mechanism Design with Efficiency, Privacy, and Approximate Truthfulness

Recently, there has been a number of papers relating mechanism design and privacy (e.g., see \cite{MT07,Xia11,CCKMV11,NST12,NOS12,HK12}). All of these papers consider a worst-case setting where there is no probabilistic information about the players' types. In this paper, we investigate mechanism design and privacy in the \emph{Bayesian} setting, where the players' types are drawn from some common distribution. We adapt the notion of \emph{differential privacy} to the Bayesian mechanism design setting, obtaining \emph{Bayesian differential privacy}. We also define a robust notion of approximate truthfulness for Bayesian mechanisms, which we call \emph{persistent approximate truthfulness}. We give several classes of mechanisms (e.g., social welfare mechanisms and histogram mechanisms) that achieve both Bayesian differential privacy and persistent approximate truthfulness. These classes of mechanisms can achieve optimal (economic) efficiency, and do not use any payments. We also demonstrate that by considering the above mechanisms in a modified mechanism design model, the above mechanisms can achieve actual truthfulness.

preprint2010arXiv

More on the phi = beta Conjecture and Eigenvalues of Random Graph Lifts

Let $G$ be a connected graph, and let $λ_1$ and $ρ$ denote the spectral radius of $G$ and the universal cover of $G$ , respectively. In \cite{Fri03}, Friedman has shown that almost every $n$ -lift of $G$ has all of its new eigenvalues bounded by $O(λ_1^{1/2}ρ^{1/2})$ . In \cite{LP10}, Linial and Puder have improved this bound to $O(λ_1^{1/3}ρ^{2/3})$ . Friedman had conjectured that this bound can actually be improved to $ρ+ o_n(1)$ (e.g., see \cite{Fri03,HLW06}). In \cite{LP10}, Linial and Puder have formulated two new categorizations of formal words, namely $ϕ$ and $β$ , which assign a non-negative integer or infinity to each word. They have shown that for every word $w$ , $ϕ(w) = 0$ iff $β(w) = 0$ , and $ϕ(w) = 1$ iff $β(w) = 1$ . They have conjectured that $ϕ(w) = β(w)$ for every word $w$ , and have run extensive numerical simulations that strongly suggest that this conjecture is true. This conjecture, if proven true, gives us a very promising approach to proving a slightly weaker version of Friedman's conjecture, namely the bound $O(ρ)$ on the new eigenvalues (see \cite{LP10}). In this paper, we make further progress towards proving this important conjecture by showing that $ϕ(w) = 2$ iff $β(w) = 2$ for every word $w$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.