Arrow Research search

Author name cluster

Joel Oren

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.

10 papers
2 author rows

Possible papers

10

PRL Workshop 2021 Workshop Paper

SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems

  • Joel Oren
  • Chana Ross
  • Maksym Lefarov
  • Felix Richter
  • Ayal Taitler
  • Zohar Feldman Zohar Feldman
  • Dotan Di Castro
  • Christian Daniel

We study combinatorial problems with real world applications such as machine scheduling, routing, and assignment. We propose a method that combines Reinforcement Learning (RL) and planning. This method can equally be applied to both the offline, as well as online, variants of the combinatorial problem, in which the problem components (e. g. , jobs in scheduling problems) are not known in advance, but rather arrive during the decision-making process. Our solution is quite generic, scalable, and leverages distributional knowledge of the problem parameters. We frame the solution process as an MDP, and take a Deep Q-Learning approach wherein states are represented as graphs, thereby allowing our trained policies to deal with arbitrary changes in a principled manner. Though learned policies work well in expectation, small deviations can have substantial negative effects in combinatorial settings. We mitigate these drawbacks by employing our graph-convolutional policies as non-optimal heuristics in a compatible search algorithm, Monte Carlo Tree Search, to significantly improve overall performance. We demonstrate our method on two problems: Machine Scheduling and Capacitated Vehicle Routing. We show that our method outperforms custom-tailored mathematical solvers, state of the art learning-based algorithms, and common heuristics, both in computation time and performance.

PDF Details

SoCS Conference 2021 Conference Paper

SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems

  • Joel Oren
  • Chana Ross
  • Maksym Lefarov
  • Felix Richter 0001
  • Ayal Taitler
  • Zohar Feldman
  • Dotan Di Castro
  • Christian G. Daniel

We study combinatorial problems with real world applications such as machine scheduling, routing, and assignment. We propose a method that combines Reinforcement Learning (RL) and planning. This method can equally be applied to both the offline, as well as online, variants of the combinatorial problem, in which the problem components (e. g. , jobs in scheduling problems) are not known in advance, but rather arrive during the decision-making process. Our solution is quite generic, scalable, and leverages distributional knowledge of the problem parameters. We frame the solution process as an MDP, and take a Deep Q-Learning approach wherein states are represented as graphs, thereby allowing our trained policies to deal with arbitrary changes in a principled manner. Though learned policies work well in expectation, small deviations can have substantial negative effects in combinatorial settings. We mitigate these drawbacks by employing our graph-convolutional policies as non-optimal heuristics in a compatible search algorithm, Monte Carlo Tree Search, to significantly improve overall performance. We demonstrate our method on two problems: Machine Scheduling and Capacitated Vehicle Routing. We show that our method outperforms custom-tailored mathematical solvers, state of the art learning-based algorithms, and common heuristics, both in computation time and performance.

Details

AAAI Conference 2019 Conference Paper

Generating Character Descriptions for Automatic Summarization of Fiction

  • Weiwei Zhang
  • Jackie Chi Kit Cheung
  • Joel Oren

Summaries of fictional stories allow readers to quickly decide whether or not a story catches their interest. A major challenge in automatic summarization of fiction is the lack of standardized evaluation methodology or high-quality datasets for experimentation. In this work, we take a bottomup approach to this problem by assuming that story authors are uniquely qualified to inform such decisions. We collect a dataset of one million fiction stories with accompanying author-written summaries from Wattpad, an online story sharing platform. We identify commonly occurring summary components, of which a description of the main characters is the most frequent, and elicit descriptions of main characters directly from the authors for a sample of the stories. We propose two approaches to generate character descriptions, one based on ranking attributes found in the story text, the other based on classifying into a list of pre-defined attributes. We find that the classification-based approach performs the best in predicting character descriptions.

PDF Details

JAAMAS Journal 2019 Journal Article

Strategic behavior and learning in all-pay auctions: an empirical study using crowdsourced data

  • Yoram Bachrach
  • Ian A. Kash
  • Joel Oren

Abstract We analyze human behavior in crowdsourcing contests using an all-pay auction model where all participants exert effort, but only the highest bidder receives the reward. We let workers sourced from Amazon Mechanical Turk participate in an all-pay auction, and contrast the game theoretic equilibrium with the choices of the humans participants. We examine how people competing in the contest learn and adapt their bids, comparing their behavior to well-established online learning algorithms in a novel approach to quantifying the performance of humans as learners. For the crowdsourcing contest designer, our results show that a bimodal distribution of effort should be expected, with some very high effort and some very low effort, and that humans have a tendency to overbid. Our results suggest that humans are weak learners in this setting, so it may be important to educate participants about the strategic implications of crowdsourcing contests.

Details DOI

IJCAI Conference 2016 Conference Paper

A Characterization of Voting Power for Discrete Weight Distributions

  • Yoram Bachrach
  • Yuval Filmus
  • Joel Oren
  • Yair Zick

Weighted voting games model decision-making bodies where decisions are made by a majority vote. In such games, each agent has a weight, and a coalition of agents wins the game if the sum of the weights of its members exceeds a certain quota. The Shapley value is used as an index for the true power held by the agents in such games. Earlier work has studied the implications of setting the value of the quota on the agents' power under the assumption that the game is given with a fixed set of agent weights. We focus on a model where the agent weights originate from a stochastic process, resulting in weight uncertainty. We analyze the expected effect of the quota on voting power given the weight generating process. We examine two extreme cases of the balls and bins model: uniform and exponentially decaying probabilities. We show that the choice of a quota may have a large influence on the power disparity of the agents, even when the governing distribution is likely to result in highly similar weights for the agents. We characterize various interesting repetitive fluctuation patterns in agents' power as a function of the quota.

PDF Details

AAAI Conference 2015 Conference Paper

The Pricing War Continues: On Competitive Multi-Item Pricing

  • Omer Lev
  • Joel Oren
  • Craig Boutilier
  • Jeffrey Rosenschein

We study a game with strategic vendors (the agents) who own multiple items and a single buyer with a submodular valuation function. The goal of the vendors is to maximize their revenue via pricing of the items, given that the buyer will buy the set of items that maximizes his net payoff. We show this game may not always have a pure Nash equilibrium, in contrast to previous results for the special case where each vendor owns a single item. We do so by relating our game to an intermediate, discrete game in which the vendors only choose the available items, and their prices are set exogenously afterwards. We further make use of the intermediate game to provide tight bounds on the price of anarchy for the subset games that have pure Nash equilibria; we find that the optimal PoA reached in the previous special cases does not hold, but only a logarithmic one. Finally, we show that for a special case of submodular functions, efficient pure Nash equilibria always exist.

PDF Details

AAAI Conference 2014 Conference Paper

A Game-Theoretic Analysis of Catalog Optimization

  • Joel Oren
  • Nina Narodytska
  • Craig Boutilier

Vendors of all types face the problem of selecting a slate of product offerings—their assortment or catalog—that will maximize their profits. The profitability of a catalog is determined by both customer preferences and the offerings of their competitors. We develop a game-theoretic model for analyzing the vendor catalog optimization problem in the face of competing vendors. We show that computing a best response is intractable in general, but can be solved by dynamic programming given certain informational or structural assumptions about consumer preferences. We also analyze conditions under which pure Nash equilibria exist and provide several price of anarchy/stability results

PDF Details

AAAI Conference 2014 Conference Paper

Online (Budgeted) Social Choice

  • Joel Oren
  • Brendan Lucier

We consider a classic social choice problem in an online setting. In each round, a decision maker observes a single agent’s preferences over a set of m candidates, and must choose whether to irrevocably add a candidate to a selection set of limited cardinality k. Each agent’s (positional) score depends on the candidates in the set when he arrives, and the decisionmaker’s goal is to maximize average (over all agents) score. We prove that no algorithm (even randomized) can achieve an approximation factor better than O(log log m log m ). In contrast, if the agents arrive in random order, we present a (1− 1 e −o(1))approximate algorithm, matching a lower bound for the offline problem. We show that improved performance is possible for natural input distributions or scoring rules. Finally, if the algorithm is permitted to revoke decisions at a fixed cost, we apply regret-minimization techniques to achieve approximation 1− 1 e −o(1) even for arbitrary inputs.

PDF Details

AAAI Conference 2014 Conference Paper

Robust Winners and Winner Determination Policies under Candidate Uncertainty

  • Craig Boutilier
  • Jérôme Lang
  • Joel Oren
  • Héctor Palacios

We consider voting situations in which some candidates may turn out to be unavailable. When determining availability is costly (e. g. , in terms of money, time, or computation), voting prior to determining candidate availability and testing the winner’s availability after the vote may be beneficial. However, since few voting rules are robust to candidate deletion, winner determination requires a number of such availability tests. We outline a model for analyzing such problems, defining robust winners relative to potential candidate unavailability. We assess the complexity of computing robust winners for several voting rules. Assuming a distribution over availability, and costs for availability tests/queries, we describe algorithms for computing optimal query policies, which minimize the expected cost of determining true winners.

PDF Details

IJCAI Conference 2013 Conference Paper

Efficient Vote Elicitation under Candidate Uncertainty

  • Joel Oren
  • Yuval Filmus
  • Craig Boutilier

Top-k voting is an especially natural form of partial vote elicitation in which only length k prefixes of rankings are elicited. We analyze the ability of top-k vote elicitation to correctly determine true winners, with high probability, given probabilistic models of voter preferences and candidate availability. We provide bounds on the minimal value of k required to determine the correct winner under the plurality and Borda voting rules, considering both worst-case preference profiles and profiles drawn from the impartial culture and Mallows probabilistic models. We also derive conditions under which the special case of zero-elicitation (i. e. , k = 0) produces the correct winner. We provide empirical results that confirm the value of top-k voting.

PDF Details DOI