Arrow Research search

Author name cluster

Allan Borodin

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.

35 papers
2 author rows

Possible papers

35

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.

PDF Details DOI

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.

PDF

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.

PDF

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.

PDF Details

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.

PDF Details

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.

PDF

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.

PDF

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.

Details

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.

PDF Details

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. >

Details

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.

Details

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.

Details