Allan Borodin

AIJ Journal 2024 Journal Article

Primarily about primaries

• Allan Borodin
• Omer Lev
• Nisarg Shah
• Tyrone Strangway

Much of the social choice literature examines direct voting systems, in which voters submit their ranked preferences over candidates and a voting rule picks a winner. Real-world elections and decision-making processes are often more complex and involve multiple stages. For instance, one popular voting system filters candidates through primaries: first, voters affiliated with each political party vote over candidates of their own party and the voting rule picks a set of candidates, one from each party, who then compete in a general election. We present a model to analyze such multi-stage elections, and conduct what is, to the best of our knowledge, the first quantitative comparison of the direct and primary voting systems in terms of the quality of the elected candidate, using the metric of distortion, which attempts to quantify how far from the optimal winner is the actual winner of an election. Our main theoretical result is that voting rules (which are independent of party affiliations, of course) are guaranteed to perform in the primary system within a constant factor of the direct, single stage setting. Surprisingly, the converse does not hold: we show settings in which there exist voting rules that perform significantly better under the primary system than under the direct system. Using simulations, we see that plurality benefits significantly from using a primary system over a direct one, while Condorcet-consistent rules do not.

IJCAI Conference 2022 Conference Paper

Distortion in Voting with Top-t Preferences

• Allan Borodin
• Daniel Halpern
• Mohamad Latifian
• Nisarg Shah

A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identifies near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.

AAMAS Conference 2022 Conference Paper

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution

• Allan Borodin
• Omer Lev
• Nisarg Shah
• Tyrone Strangway

Gerrymandering is the process of creating electoral districts for partisan advantage, allowing a party to win more seats than what is reasonable for their vote. While research on gerrymandering has recently grown, many issues are still not fully understood such as what influences the degree to which a party can gerrymander and what techniques can be used to counter it. One commonly suggested (and, in some US states, mandated) requirement is that districts be “geographically compact”. However, there are many competing compactness definitions and the impact of compactness on the gerrymandering abilities of the parties is not well understood. Also not well understood is how the growing urban-rural divide between supporters of different parties impacts redistricting. We develop a modular, scalable, and efficient algorithm that can design districts for various criteria. We confirm its effectiveness on several US states by pitting it against maps “hand-drawn” by political experts. Using real data from US political elections we use our algorithm to study the interaction between population distribution, partisanship, and geographic compactness. We find that compactness can lead to more fair plans (compared to implemented plans) and limit gerrymandering potential, but there is a consistent asymmetry where the party with rural supporters has an advantage. We also show there are plans which are fair from a partisan perspective, but they are far from optimally compact.

AAMAS Conference 2019 Conference Paper

Efficient Allocation of Free Stuff

• Yossi Azar
• Allan Borodin
• Michal Feldman
• Amos Fiat
• Kineret Segal

We study online matching settings with selfish agents when everything is free. Inconsiderate agents break ties arbitrarily amongst equal maximal value available choices, even if the maximal value is equal to zero. Even for the simplest case of zero/one valuations, where agents arrive online in an arbitrary order, and agents are restricted to taking at most one item, the resulting social welfare may be negligible for a deterministic algorithm. This may be surprising when contrasted with the 1/2 approximation of the greedy algorithm, analogous to this setting, except that agents are considerate (i. e. , they don’t take zero-valued items). We overcome this challenge by introducing a new class of algorithms, which we refer to as prioritization algorithms. We show that upgrading a random subset of the agents to “business class" already improves the approximation to a constant. For more general valuations, we achieve a constant approximation using logn priority classes, when the valuations are known in advance. We extend these results to settings where agents have additive valuations and are restricted to taking up to some q ≥ 1 items. Our results are tight up to a constant.

AAAI Conference 2019 Conference Paper

Primarily about Primaries

• Allan Borodin
• Omer Lev
• Nisarg Shah
• Tyrone Strangway

Much of the social choice literature examines direct voting systems, in which voters submit their ranked preferences over candidates and a voting rule picks a winner. Real-world elections and decision-making processes are often more complex and involve multiple stages. For instance, one popular voting system filters candidates through primaries: first, voters affiliated with each political party vote over candidates of their own party and the voting rule picks a candidate from each party, which then compete in a general election. We present a model to analyze such multi-stage elections, and conduct the first quantitative comparison (to the best of our knowledge) of the direct and primary voting systems with two political parties in terms of the quality of the elected candidate. Our main result is that every voting rule is guaranteed to perform almost as well (i. e. , within a constant factor) under the primary system as under the direct system. Surprisingly, the converse does not hold: we show settings in which there exist voting rules that perform significantly better under the primary system than under the direct system.

IJCAI Conference 2018 Conference Paper

Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering

• Allan Borodin
• Omer Lev
• Nisarg Shah
• Tyrone Strangway

Gerrymandering is the process by which parties manipulate boundaries of electoral districts in order to maximize the number of districts they can win. Demographic trends show an increasingly strong correlation between residence and party affiliation; some party’s supporters congregate in cities, while others stay in more rural areas. We investigate both theoretically and empirically the effect of this trend on a party's ability to gerrymander in a two-party model ("urban party" and "rural party"). Along the way, we propose a definition of the gerrymandering power of a party, and an algorithmic approach for near-optimal gerrymandering in large instances. Our results suggest that beyond a fairly small concentration of urban party's voters, the gerrymandering power of a party depends almost entirely on the level of concentration, and not on the party's share of the population. As partisan separation grows, the gerrymandering power of both parties converge so that each party can gerrymander to get only slightly more than what its voting share warrants, bringing about, ultimately, a more representative outcome. Moreover, there seems to be an asymmetry between the gerrymandering power of the parties, with the rural party being more capable of gerrymandering.

AAMAS Conference 2018 Conference Paper

Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life

• Atiyeh Ashari Ghomi
• Allan Borodin
• Omer Lev

We consider a “price-committment model” where a single seller announces prices for some extended period of time. More specifically, we examine the case of items with a limited shelf-life where storing an item (before consumption) may carry a cost to a buyer (or distributor). For example, eggs, milk, or Groupon coupons have a fixed expiry date, and seasonal goods can suffer a decrease in value. We show how this setting contrasts with recent results by Berbeglia et al [4] for items with infinite shelf-life. We prove tight bounds on the seller’s profits showing how they relate to the items’ shelf-life. We show, counterintuitively, that in our limited shelf-life setting, increasing storage costs can sometimes lead to less profit for the seller which cannot happen when items have unlimited shelf-life. We also provide an algorithm that calculates optimal prices. Finally, we examine empirically the relationship between profits and buyer utility as the storage cost and shelf-life duration change, and observe properties, some of which are unique to the limited shelf-life setting.

AAMAS Conference 2016 Conference Paper

Budgetary Effects on Pricing Equilibrium in Online Markets

• Allan Borodin
• Omer Lev
• Tyrone Strangway

Following the work of Babaioff et al [4], we consider the pricing game with strategic vendors and a single buyer, modeling a scenario in which multiple competing vendors have very good knowledge of a buyer, as is common in online markets. We add to this model the realistic assumption that the buyer has a fixed budget and does not have unlimited funds. When the buyer’s valuation function is additive, we are able to completely characterize the different possible pure Nash Equilibria (PNE) and in particular obtain a necessary and sufficient condition for uniqueness. Furthermore, we characterize the market clearing (or Walresian) equilibria for all submodular valuations. Surprisingly, for certain monotone submodular function valuations, we show that the pure NE can exhibit some counterintuitive phenomena; namely, there is a valuation such that the pricing will be market clearing and within budget if the buyer does not reveal the budget but will result in a smaller set of allocated items (and higher prices for items) if the buyer does reveal the budget. It is also the case that the conditions that guarantee market clearing in Babaioff et al [4] for submodular functions are not necessarily market clearing when there is a budget. Furthermore, with respect to social welfare, while without budgets all equilibria are optimal (i. e. POA = POS = 1), we show that with budgets the worst equilibrium may only achieve 1 n−2 of the best equilibrium.

TCS Journal 2012 Journal Article

On sum coloring and sum multi-coloring for restricted families of graphs

• Allan Borodin
• Ioana Ivan
• Yuli Ye
• Bryce Zimny

We consider the sum coloring (chromatic sum) problem and the sum multi-coloring problem for restricted families of graphs. In particular, we consider the graph classes of proper intersection graphs of axis-parallel rectangles, proper interval graphs, and unit disk graphs. All the above-mentioned graph classes belong to a more general graph class of ( k + 1 ) -clawfree graphs (respectively, for k = 4, 2, 5 ). We prove that sum coloring is NP-hard for penny graphs and unit square graphs which implies NP-hardness for unit disk graphs and proper intersection graphs of axis-parallel rectangles. We show a 2-approximation algorithm for unit square graphs, with the assumption that the geometric representation of the graph is given. For sum multi-coloring, we confirm that the greedy first-fit coloring, after ordering vertices by their demands, achieves a k -approximation for the preemptive version of sum multi-coloring on ( k + 1 ) -clawfree graphs. Finally, we study priority algorithms as a model for greedy algorithms for the sum coloring problem and the sum multi-coloring problem. We show various inapproximation results under several natural input representations.

SAT Conference 2010 Conference Paper

On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem

• Denis Pankratov
• Allan Borodin

Abstract Algorithms based on local search are popular for solving many optimization problems including the maximum satisfiability problem (MAX-SAT). With regard to MAX-SAT, the state of the art in performance for universal (i. e. non specialized solvers) seems to be variants of Simulated Annealing (SA) and MaxWalkSat (MWS), stochastic local search methods. Local search methods are conceptually simple, and they often provide near optimal solutions. In contrast, it is relatively rare that local search algorithms are analyzed with respect to the worst-case approximation ratios. In the first part of the paper, we build on Mastrolilli and Gambardella’s work [14] and present a worst-case analysis of tabu search for the MAX- k -SAT problem. In the second part of the paper, we examine the experimental performance of determinstic local search algorithms (oblivious and non-oblivious local search, tabu search) in comparison to stochastic methods (SA and MWS) on random 3-CNF and random k -CNF formulas and on benchmarks from MAX-SAT competitions. For random MAX-3-SAT, tabu search consistently outperforms both oblivious and non-oblivious local search, but does not match the performance of SA and MWS. Initializing with non-oblivious local search improves both the performance and the running time of tabu search. The better performance of the various methods that escape local optima in comparison to the more basic oblivious and non-oblivious local search algorithms (that stop at the first local optimum encountered) comes at a cost, namely a significant increase in complexity (which we measure in terms of variable flips). The performance results observed for the unweighted MAX-3-SAT problem carry over to the weighted version of the problem, but now the better performance of MWS is more pronounced. In contrast, as we consider MAX- k -SAT as k is increased, MWS loses its advantage. Finally, on benchmark instances, it appears that simulated annealing and tabu search initialized with non-oblivious local search outperform the other methods on most instances.

SODA Conference 2010 Conference Paper

Price of Anarchy for Greedy Auctions

• Brendan Lucier
• Allan Borodin

We study mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, and others. We focus on the problem of designing mechanisms that approximately optimize social welfare at every Bayes-Nash equilibrium (BNE), which is the standard notion of equilibrium in settings of incomplete information. For a broad class of greedy approximation algorithms, we give a general black-box reduction to deterministic mechanisms with almost no loss to the approximation ratio at any BNE. We also consider the special case of Nash equilibria in full-information games, where we obtain tightened results. This solution concept is closely related to the well-studied price of anarchy. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for our mechanisms. For many problems, the approximation factors we obtain at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for general combinatorial auctions that obtains an approximation at every BNE.

TCS Journal 2010 Journal Article

Priority algorithms for graph optimization problems

• Allan Borodin
• Joan Boyar
• Kim S. Larsen
• Nazanin Mirmohammadi

We continue the study of priority or “greedy-like” algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”.

TCS Journal 2010 Journal Article

Randomized priority algorithms

• Spyros Angelopoulos
• Allan Borodin

Borodin, Nielsen and Rackoff [13] introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling.

NeurIPS Conference 2003 Conference Paper

Can We Learn to Beat the Best Stock

• Allan Borodin
• Ran El-Yaniv
• Vincent Gogan

A novel algorithm for actively trading stocks is presented. While tradi- tional universal algorithms (and technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of techni- cal trading can “beat the market” and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning. 1 Introduction: The Portfolio Selection Problem The portfolio selection (PS) problem is a challenging problem for machine learning, online algorithms and, of course, computational finance. As is well known (e. g. see Lugosi [1]) sequence prediction under the log loss measure can be viewed as a special case of portfo- lio selection, and perhaps more surprisingly, from a certain worst case minimax criterion, portfolio selection is not essentially any harder (than prediction) as shown in [2] (see also [1], Thm. 20 & 21). But there seems to be a qualitative difference between the practical utility of “universal” sequence prediction and universal portfolio selection. Simply stated, universal sequence prediction algorithms under various probabilistic and worst-case mod- els work very well in practice whereas the known universal portfolio selection algorithms do not seem to provide any substantial benefit over a naive investment strategy (see Sec. 4). A major pragmatic question is whether or not a computer program can consistently out- perform the market. A closer inspection of the interesting ideas developed in information theory and online learning suggests that a promising approach is to exploit the natural volatility in the market and in particular to benefit from simple and rather persistent statis- tical relations between stocks rather than to try to predict stock prices or “winners”. We present a non-universal portfolio selection algorithm1, which does not try to predict win- ners. The motivation behind our algorithm is the rationale behind constant rebalancing algorithms and the worst case study of universal trading introduced by Cover [3]. Not only does our proposed algorithm substantially “beat the market” on historical markets, it also beats the best stock. So why are we presenting this algorithm and not just simply making money? There are, of course some caveats and obstacles to utilizing the algorithm. But for large investors the possibility of a goose laying silver (if not golden) eggs is not impossible. 1Any PS algorithm can be modified to be universal by investing any fixed fraction of the initial wealth in a universal algorithm.

SODA Conference 2002 Conference Paper

(Incremental) priority algorithms

• Allan Borodin
• Morten N. Nielsen
• Charles Rackoff

SODA Conference 2001 Conference Paper

Stability preserving transformations: packet routing networks with edge capacities and speeds

• Allan Borodin
• Rafail Ostrovsky
• Yuval Rabani

STOC Conference 1999 Conference Paper

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems

• Allan Borodin
• Rafail Ostrovsky
• Yuval Rabani

I&C Journal 1999 Journal Article

On Randomization in On-Line Computation

• Allan Borodin
• Ran El-Yaniv

This paper concerns two fundamental but somewhat neglected issues, both related to the design and analysis of randomized on-line algorithms. Motivated by early results in game theory we define several types of randomized on-line algorithms, discuss known conditions for their equivalence, and give a natural example distinguishing between two kinds of randomizations. In particular, we show thatmixedrandomized memoryless paging algorithms can achieve strictly better competitive performance thanbehavioralrandomized algorithms. Next we summarize known—and derive new—“Yao principle” theorems for lower bounding competitive ratios of randomized on-line algorithms. This leads to four different theorems for bounded/unbounded and minimization/maximization problems.

STOC Conference 1999 Conference Paper

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces

• Allan Borodin
• Rafail Ostrovsky
• Yuval Rabani

STOC Conference 1996 Conference Paper

Adversarial Queueing Theory

• Allan Borodin
• Jon M. Kleinberg
• Prabhakar Raghavan
• Madhu Sudan 0001
• David P. Williamson

I&C Journal 1996 Journal Article

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata

• Paul Beame
• Allan Borodin
• Prabhakar Raghavan
• Walter L. Ruzzo
• Martin Tompa

We investigate time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff's “Jumping Automata for Graphs. ” Our strongest tradeoff is a quadratic lower bound on the product of time and space for graph traversal. For example, achieving linear time requires linear space, implying that depth-first search is optimal. Since our bound in fact applies to nondeterministic algorithms fornonconnectivity, it also implies that closure under complementation of nondeterministic space-bounded complexity classes is achieved only at the expense of increased time. To demonstrate that these structured models are realistic, we also investigate their power. In addition to admitting well known algorithms such as depth-first search and random walk, we show that one simple variant of this model is nearly as powerful as a Turing machine. Specifically, for general undirected graph problems, it can simulate a Turing machine with only a constant factor increase in space and a polynomial factor increase in time.

STOC Conference 1993 Conference Paper

How much can hardware help routing?

• Allan Borodin
• Prabhakar Raghavan
• Baruch Schieber
• Eli Upfal

STOC Conference 1991 Conference Paper

Competitive Paging with Locality of Reference (Preliminary Version)

• Allan Borodin
• Sandy Irani
• Prabhakar Raghavan
• Baruch Schieber

STOC Conference 1990 Conference Paper

On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version)

• Allan Borodin
• Prasoon Tiwari

STOC Conference 1990 Conference Paper

On the Power of Randomization in Online Algorithms (Extended Abstract)

• Shai Ben-David
• Allan Borodin
• Richard M. Karp
• Gábor Tardos
• Avi Wigderson

FOCS Conference 1990 Conference Paper

Time-Space Tradeoffs for Undirected Graph Traversal

• Paul Beame
• Allan Borodin
• Prabhakar Raghavan
• Walter L. Ruzzo
• Martin Tompa

Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A. Z. Broder et al. (1989). The models used are variants of S. A. Cook and C. W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated. >

STOC Conference 1989 Conference Paper

Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract)

• Allan Borodin
• Walter L. Ruzzo
• Martin Tompa

TCS Journal 1988 Journal Article

A tradeoff between search and update time for the implicit dictionary problem

• Allan Borodin
• Faith E. Fich
• Friedhelm Meyer auf der Heide
• Eli Upfal
• Avi Wigderson

This paper proves a tradeoff between the time it takes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time is Ω(nε) for some constant ε>0.

STOC Conference 1987 Conference Paper

An Optimal Online Algorithm for Metrical Task Systems

• Allan Borodin
• Nati Linial
• Michael E. Saks

STOC Conference 1983 Conference Paper

Bounds for Width Two Branching Programs

• Allan Borodin
• Danny Dolev
• Faith Ellen
• Wolfgang J. Paul

FOCS Conference 1982 Conference Paper

Fast Parallel Matrix and GCD Computations

• Allan Borodin
• Joachim von zur Gathen
• John E. Hopcroft

We present parallel algorithms to compute the determinant and characteristic polynomial of n×n-matrices and the gcd of polynomials of degree ≤n. The algorithms use parallel time O(log2n) and a polynomial number of processors. We also give a fast parallel Las Vegas algorithm for the rank of matrices. All algorithms work over arbitrary fields.

STOC Conference 1982 Conference Paper

Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract)

• Allan Borodin
• John E. Hopcroft

STOC Conference 1980 Conference Paper

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation

• Allan Borodin
• Stephen A. Cook

FOCS Conference 1979 Conference Paper

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines

• Allan Borodin
• Michael J. Fischer
• David G. Kirkpatrick
• Nancy A. Lynch
• Martin Tompa

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

FOCS Conference 1979 Conference Paper

Resource Allocation with Immunity to Limited Process Failure (Preliminary Report)

• Michael J. Fischer
• Nancy A. Lynch
• James E. Burns
• Allan Borodin

Upper and lower bounds are proved for the shared space requirements for solution of several problems involving resource allocation among asynchronous processes. Controlling the degradation of performance when a limited number of processes fail is of particular interest.

STOC Conference 1974 Conference Paper

On the Number of Additions to Compute Specific Polynomials (Preliminary Version)

• Allan Borodin
• Stephen A. Cook

STOC Conference 1969 Conference Paper

Complexity Classes of Recursive Functions and the Existence of Complexity Gaps

• Allan Borodin