Source author record

Zhenghui Wang

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 Computational Complexity Information Theory math.IT math.PR

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Gini Index based Initial Coin Offering Mechanism

As a fundraising method, Initial Coin Offering (ICO) has raised billions of dollars for thousands of startups in the past two years. Existing ICO mechanisms place more emphasis on the short-term benefits of maximal fundraising while ignoring the problem of unbalanced token allocation, which negatively impacts subsequent fundraising and has bad effects on introducing new investors and resources. We propose a new ICO mechanism which uses the concept of Gini index for the very first time as a mechanism design constraint to control allocation inequality. Our mechanism maintains an elegant and straightforward structure. It allows the agents to modify their bids as a price discovery process, while limiting the bids of whales. We analyze the agents' equilibrium behaviors under our mechanism. Under natural technical assumptions, we show that most agents have simple dominant strategies and the equilibrium revenue approaches the optimal revenue asymptotically in the number of agents. We verify our mechanism using real ICO dataset we collected, and confirm that our mechanism performs well in terms of both allocation fairness and revenue.

preprint2012arXiv

Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming

Three decades of research in communication complexity have led to the invention of a number of techniques to lower bound randomized communication complexity. The majority of these techniques involve properties of large submatrices (rectangles) of the truth-table matrix defining a communication problem. The only technique that does not quite fit is information complexity, which has been investigated over the last decade. Here, we connect information complexity to one of the most powerful "rectangular" techniques: the recently-introduced smooth corruption (or "smooth rectangle") bound. We show that the former subsumes the latter under rectangular input distributions. We conjecture that this subsumption holds more generally, under arbitrary distributions, which would resolve the long-standing direct sum question for randomized communication. As an application, we obtain an optimal $Ω(n)$ lower bound on the information complexity---under the {\em uniform distribution}---of the so-called orthogonality problem (ORT), which is in turn closely related to the much-studied Gap-Hamming-Distance (GHD). The proof of this bound is along the lines of recent communication lower bounds for GHD, but we encounter a surprising amount of additional technical detail.

preprint2011arXiv

Lower Bound for Envy-Free and Truthful Makespan Approximation on Related Machines

We study problems of scheduling jobs on related machines so as to minimize the makespan in the setting where machines are strategic agents. In this problem, each job $j$ has a length $l_{j}$ and each machine $i$ has a private speed $t_{i}$ . The running time of job $j$ on machine $i$ is $t_{i}l_{j}$ . We seek a mechanism that obtains speed bids of machines and then assign jobs and payments to machines so that the machines have incentive to report true speeds and the allocation and payments are also envy-free. We show that 1. A deterministic envy-free, truthful, individually rational, and anonymous mechanism cannot approximate the makespan strictly better than $2-1/m$ , where $m$ is the number of machines. This result contrasts with prior work giving a deterministic PTAS for envy-free anonymous assignment and a distinct deterministic PTAS for truthful anonymous mechanism. 2. For two machines of different speeds, the unique deterministic scalable allocation of any envy-free, truthful, individually rational, and anonymous mechanism is to allocate all jobs to the quickest machine. This allocation is the same as that of the VCG mechanism, yielding a 2-approximation to the minimum makespan. 3. No payments can make any of the prior published monotone and locally efficient allocations that yield better than an $m$ -approximation for $\qcmax$ \cite{aas, at,ck10, dddr, kovacs} a truthful, envy-free, individually rational, and anonymous mechanism.

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.