Showing 2022Show all
2 papers · 1 filter
cs.GT2022
Better Approximation for Interdependent SOS Valuations
Pinyan Lu, Enze Sun, Chenghan Zhou
Submodular over signal (SOS) defines a family of interesting functions for which there exist truthful mechanisms with constant approximation to the social welfare for agents with i…
cs.DS2022
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Nick Gravin, Enze Sun, Zhihao Gavin Tang
We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of go…