7 papers
Scaling Reasoning Tokens via RL and Parallel Thinking: Evidence From Competitive Programming
Qianfan Zhang, Tianyu Guo, Xuandi Ren +4
We study how to scale reasoning token budgets for competitive programming through two complementary approaches: training-time reinforcement learning (RL) and test-time parallel thi…
The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders
Frederick V. Qiu, S. Matthew Weinberg, Qianfan Zhang
We study the communication complexity of welfare maximization in combinatorial auctions with bidders from either a standard valuation class (which require exponential communication…
From Best Responses to Learning: Investment Efficiency in Dynamic Environment
Ce Li, Qianfan Zhang, Weiqiang Zheng
We study the welfare of a mechanism in a dynamic environment where a learning investor can make a costly investment to change her value. In many real-world problems, the common ass…
Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
Aadityan Ganesh, Qianfan Zhang
We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li (2020) argue that any revenue-optimal, truthfu…
A Bicriterion Concentration Inequality and Prophet Inequalities for -Fold Matroid Unions
Noga Alon, Nick Gravin, Tristan Pollner +4
We investigate prophet inequalities with competitive ratios approaching , seeking to generalize -uniform matroids. We first show that large girth does not suffice: for all $k…
Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
Shiri Ron, Clayton Thomas, S. Matthew Weinberg +1
We study the communication complexity of truthful combinatorial auctions, and in particular the case where valuations are either subadditive or single-minded, which we denote with…