Allan Borodin

Allan Borodin, Christodoulos Karavasilis, David Zhang

Interest in the random-order model (ROM) leads us to initiate a study of utilizing random-order arrivals to extract random bits with the goal of derandomizing algorithms. Besides producing simple algorithms, simulating random bits through random arrivals enhances our understanding of the comparative strength of randomized online algorithms (with adversarial input sequences) and deterministic algorithms in the ROM. We consider three $1$-bit randomness extraction processes. Our best extraction process returns a bit with a worst-case bias of $2 - \sqrt{2} \approx 0.585$ and operates under the mild assumption that there exist at least two distinct items in the input. We motivate the applicability of this process by using it to simulate a number of barely random algorithms for weighted interval selection (single-length with arbitrary weights, as well as monotone, C-benevolent and D-benevolent weighted instances), the proportional and general knapsack problems, job throughput scheduling, and makespan minimization. It is well known that there are many applications where a deterministic ROM algorithm significantly outperforms any randomized online algorithm (in terms of competitive ratios). The classic example is that of the secretary problem. We ask the following fundamental question: Is there any application for which a randomized algorithm outperforms any deterministic ROM algorithm? Motivated by this question, we view our randomness extraction applications as a constructive approach toward understanding the relationship between randomized online algorithms and deterministic algorithms in the ROM.

Allan Borodin, Tristan Lueger

We study online temporal voting, where a group of voters submit 0/1 approvals on sets of alternatives that arrive online over multiple rounds and a single alternative is chosen in each round. We introduce online variants of two well-known game theoretic properties, strategyproofness (SP) and independence of irrelevant alternatives. We show that online independence of irrelevant alternatives (OIIA) is a sufficient condition for online strategyproofness (OSP), and that several known online voting rules satisfy OIIA and thus OSP, but that they are not SP. In particular, we show that Perpetual Phragmen, the only known online voting rule to satisfy PJR, satisfies OSP. The Method of Equal Shares (MES), a semi-online voting rule knwon to satisfy wEJR, also satisfies OSP. We then introduce the price of manipulability, which quantifies the effect of strategic behaviour on proportional representation guarantees. Finally, we introduce asymptotic satisfaction of proportional representation and show that an online voting rule, Serial Dictator, is fully strategyproof and satisfies proportional justified representation (PJR) up to an additive constant.

Allan Borodin, Aadhar Jain, Hyun Chul Lee et al.

Result diversification is an important aspect in web-based search, document summarization, facility location, portfolio management and other applications. Given a set of ranked results for a set of objects (e.g. web documents, facilities, etc.) with a distance between any pair, the goal is to select a subset $S$ satisfying the following three criteria: (a) the subset $S$ satisfies some constraint (e.g. bounded cardinality); (b) the subset contains results of high "quality"; and (c) the subset contains results that are "diverse" relative to the distance measure. The goal of result diversification is to produce a diversified subset while maintaining high quality as much as possible. We study a broad class of problems where the distances are a metric, where the constraint is given by independence in a matroid, where quality is determined by a monotone submodular function, and diversity is defined as the sum of distances between objects in $S$. Our problem is a generalization of the {\em max sum diversification} problem studied in \cite{GoSh09} which in turn is a generaliztion of the {\em max sum $p$-dispersion problem} studied extensively in location theory. It is NP-hard even with the triangle inequality. We propose two simple and natural algorithms: a greedy algorithm for a cardinality constraint and a local search algorithm for an arbitary matroid constraint. We prove that both algorithms achieve constant approximation ratios.