Uri Nadav

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
    Alex Psomas
    Aviad Rubinstein
    Advances in Neural Information Processing Systems (2020)
    Preview abstract We consider the fundamental problem of selecting k out of n random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e.g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e.g., costly retrieval or model computation) allow the participation of only k out of n bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid). We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the k random variables with the largest 1/\sqrt{k} top quantile value, is a constant approximation to the expected highest and second highest value, simultaneously. View details
    Bid-Limited Targeting
    Patrick Hummel
    Proceedings of the 2018 World Wide Web Conference (WWW), pp. 1329-1338
    Preview abstract This paper analyzes a mechanism for selling items in auctions in which the auctioneer specifies a cap on the ratio between the maximum and minimum bids that bidders may use. Such a mechanism is widely used in the online advertising business through the caps that companies impose on the minimum and maximum bid multipliers that advertisers may use in targeting. When bidders’ values are independent and identically distributed, using this mechanism results in higher revenue than allowing bidders to condition their bids on the targeting information in an arbitrary way and also almost always results in higher revenue than not allowing bidders to target. Choosing the optimal cap on the ratio between the maximum bid and the minimum bid can also be more important than introducing additional competition in the auction. However, if bidders’ values are not identically distributed, pure-strategy equilibria may fail to exist. View details
    Ad auctions with data
    Hu Fu
    Patrick R. Jordan
    Inbal Talgam-Cohen
    INFOCOM Workshops (2012), pp. 184-189
    Preview
    Bid optimization for broad match ad auctions
    Eyal Even-Dar
    S. Muthukrishnan
    Yishay Mansour
    WWW (2009), pp. 231-240
    Preview
    On the Convergence of Regret Minimization Dynamics in Concave Games
    Eyal Even-Dar
    Yishay Mansour
    41st Annual ACM Symposium on Theory of Computing, STOC, ACM (2009), pp. 523-532
    Preview abstract We consider standard regret minimization setting where at each time step the decision maker has to choose a distribution over k alternatives, and then observes the loss of each alternative. The setting is very similar to the classical online job scheduling setting with three major differences: Information model: in the regret minimization setting losses are only observed after the actions (assigning the job to a machine) is performed and not observed before the action selection, as assumed in the classical online job scheduling setting, The comparison class: in regret minimization the comparison class is the best static algorithm (i.e., distribution over alternatives) and not the optimal offline solution. Performance measure: In regret minimization we measure the additive difference to the optimal solution in the comparison class, in contrast to the ratio used in online job scheduling setting. Motivated by load balancing and job scheduling, we consider a global cost function (over the losses incur by each alternative/machine), rather than simply a summation of the instantaneous losses as done traditionally in regret minimization. Such global cost functions include the makespan (the maximum over the alternatives/machines) and the Ld norm (over the alternatives/machines). The major contribution of this work is to design a novel regret minimization algorithm based on calibration that guarantees a vanishing average regret, where the regret is measured with respect to the best static decision maker, who selects the same distribution over alternatives at every time step. Our results hold for a wide class of global cost functions. which include the makespan and the Ld norms, for d>1. In contrast, we show that for concave global cost functions, such as Ld norms for d<1, the worst-case average regret does not vanish. In addition to the general calibration based algorithm, we provide simple and efficient algorithms for special interesting cases. View details