Author name cluster

Jinzhao Wu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

STOC Conference 2023 Conference Paper

On the Optimal Fixed-Price Mechanism in Bilateral Trade

Yang Cai 0001
Jinzhao Wu

We study the problem of social welfare maximization in bilateral trade, where two agents, a buyer and a seller, trade an indivisible item. The seminal result of Myerson and Satterthwaite shows that no incentive compatible and budget balanced (i.e., the mechanism does not run a deficit) mechanism can achieve the optimal social welfare in bilateral trade. Motivated by this impossibility result, we focus on approximating the optimal social welfare. We consider arguably the simplest form of mechanisms – the fixed-price mechanisms, where the designer offers trade at a fixed price to the seller and buyer. Besides the simple form, fixed-price mechanisms are also the only dominant strategy incentive compatible and budget balanced mechanisms in bilateral trade.

Details

FOCS Conference 2023 Conference Paper

Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders

Yang Cai 0001
Ziyun Chen
Jinzhao Wu

We study revenue maximization in multi-item auctions, where bidders have subadditive valuations over independent items [48]. Providing a simple mechanism that is approximately revenue-optimal in this setting is a major open problem in mechanism design [20]. In this paper, we present the first simple mechanism whose revenue is at least a constant fraction of the optimal revenue in multi-item auctions with subadditive bidders. Our mechanism is a simultaneous auction that incorporates either a personalized entry fee or a personalized reserve price per item. We prove that for any simultaneous auction that satisfies c-efficiency– a new property we propose, its revenue is at least an $O(c)$-approximation to the optimal revenue. We further show that both the simultaneous first-price and the simultaneous all-pay auction are $\frac{1}{2}$-efficient. Providing revenue guarantees for non-truthful simple mechanisms, e. g. , simultaneous auctions, in multi-dimensional environments has been recognized by Roughgarden et al. [47] as an important open question. Prior to our result, the only such revenue guarantees are due to Daskalakis et al. [30] for bidders who have additive valuations over independent items. Our result significantly extends the revenue guarantees of these non-truthful simple auctions to settings where bidders have combinatorial valuations.

Details

STOC Conference 2022 Conference Paper

(Fractional) online stochastic matching via fine-grained offline statistics

Zhihao Gavin Tang
Jinzhao Wu
Hongxun Wu

Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochastic bipartite graph with offline vertices on one side and with i.i.d. online vertices on the other side. The algorithm knows the offline vertices and the distribution of the online vertices in advance. Upon the arrival of each online vertex, its type is realized and the algorithm immediately and irrevocably decides how to match it. In the vertex-weighted version of the problem, each offline vertex is associated with a weight and the goal is to maximize the total weight of the matching. In this paper, we generalize the model to allow non-identical online vertices and focus on the fractional version of the vertex-weighted stochastic matching. We design fractional algorithms that are 0.718-competitive and 0.731-competitive for non i.i.d. arrivals and i.i.d. arrivals respectively. We also prove that no fractional algorithm can achieve a competitive ratio better than 0.75 for non i.i.d. arrivals. Furthermore, we round our fractional algorithms by applying the recently developed multiway online correlated selection by Gao et al. (FOCS 2021) and achieve 0.666-competitive and 0.704-competitive integral algorithms for non i.i.d. arrivals and i.i.d. arrivals. Our results for non i.i.d. arrivals are the first algorithms beating the 1−1/ e ≈ 0.632 barrier of the classical adversarial setting. Our 0.704-competitive integral algorithm for i.i.d. arrivals slightly improves the state-of-the-art 0.701-competitive ratio by Huang and Shu (STOC 2021).

Details

NeurIPS Conference 2022 Conference Paper

Eliciting Thinking Hierarchy without a Prior

Yuqing Kong
Yunqi Li
Yubo Zhang
Zhihuan Huang
Jinzhao Wu

When we use the wisdom of the crowds, we usually rank the answers according to their popularity, especially when we cannot verify the answers. However, this can be very dangerous when the majority make systematic mistakes. A fundamental question arises: can we build a hierarchy among the answers without any prior where the higher-ranking answers, which may not be supported by the majority, are from more sophisticated people? To address the question, we propose 1) a novel model to describe people's thinking hierarchy; 2) two algorithms to learn the thinking hierarchy without any prior; 3) a novel open-response based crowdsourcing approach based on the above theoretic framework. In addition to theoretic justifications, we conduct four empirical crowdsourcing studies and show that a) the accuracy of the top-ranking answers learned by our approach is much higher than that of plurality voting (In one question, the plurality answer is supported by 74 respondents but the correct answer is only supported by 3 respondents. Our approach ranks the correct answer the highest without any prior); b) our model has a high goodness-of-fit, especially for the questions where our top-ranking answer is correct. To the best of our knowledge, we are the first to propose a thinking hierarchy model with empirical validations in the general problem-solving scenarios; and the first to propose a practical open-response-based crowdsourcing approach that beats plurality voting without any prior.

PDF Details