Strong Equilibrium in Cost-Sharing Connection Game (2007)
Epstein, Amir, Feldman, Michal, Mansour, Yishay
In this work we study cost sharing connection games, where each player has a source and sink he would like to connect, and the cost of the edges is either shared equally (fair con- nection games) or...
The Communication Complexity of Uncoupled Nash Equilibrium Procedures (2007)
We study the question of how long it takes players to reach a Nash equilibrium in uncoupled setups, where each player initially knows only his own payo® function. We derive lower bounds on the...
Regret to the Best vs. Regret to the average. (2007)
Even-Dar, Eyal, Kearns, Michael, Mansour, Yishay, Wortman, Jenn
We study online regret minimization algorithms in a bicriteria setting, examining not only the standard notion of regret to the best expert, but also the regret to the average of all experts, the...
Improved Second-Order Bounds for Prediction with Expert Advice (2006)
Cesa-Bianchi, Nicolo, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting...
Improved Second-Order Bounds for Prediction with Expert Advice (2006)
Cesa-Bianchi, Nicolo, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting...
The Value of Observation for Monitoring Dynamic Systems (2006)
Even-Dar, Eyal, Kakade, Sham, Mansour, Yishay
We consider the fundamental problem of tracking the belief state in a POMDP, when the model is only approximately correct and the initial belief state might be unknown. In this general setting where...
Active Sampling for Multiple Output Identification (2006)
We study functions with multiple output values, and use active sampling to identify an example for each of the possible output values. Our results for this setting include: (1) Efficient active...
(In)Stability Properties of Limit Order Dynamics (2006)
Even-Dar, Eyal, Kakade, Sham, Kearns, Mchael, Mansour, Yishay
We study the stability properties of the dynamics of the standard continuous limit-order mechanism that is used in modern equity markets. We ask whether such mechanisms are susceptible to ``butterfly...
A Sufficient Condition for Truthfulness with Single Parameter Agents (2006)
Andelman, Nir, Mansour, Yishay
We consider the task of designing truthful mechanisms for single parameter agents. We prove a general sufficient condition for truthfulness when each agent's valuation function for each possible...
Online Trading Algorithms and Robust Option Pricing (2006)
De Marzo, Peter, Kremer, Ilan, Mansour, Yishay
In this work we show how to use efficient online trading algorithms to price the current value of financial instruments, such as an option. We derive both upper and lower bounds for pricing an...
Improved Second-Order Bounds for Prediction with Expert Advice (2006)
Cesa-Bianchi, Nicolo, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting...
Improved Second-Order Bounds for Prediction with Expert Advice (2006)
Cesa-Bianchi, Nicolo, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting...
Improved Second-Order Bounds for Prediction with Expert Advice (2006)
Cesa-Bianchi, Nicolo, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting...
On Nash Equilibria for a Network Creation Game (2006)
Albers, Susanne, Eilts, Stefan, Even-Dar, Eyal, Mansour, Yishay, Roditty, Liam
We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of...
Strong Price of Anarchy (2006)
Andelman, Nir, Feldman, Michal, Mansour, Yishay
A strong equilibrium (Aumann 1959) is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy to be the ratio of the worst case strong...
Improved Second-Order Bounds for Prediction with Expert Advice (2006)
Cesa-Bianchi, Nicolò, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting...
Agnostically Learning Halfspaces (2005)
Kalai, Adam, Klivans, Adam, Mansour, Yishay, Servedio, Rocco
We give the first algorithm that (under distributional assumptions) efficiently learns halfspaces in the notoriously difficult {\em agnostic} framework of Kearns, Schapire, \& Sellie\ignore{I've been...
Mechanism Design via Machine Learning (2005)
Balcan, Maria-Florina, Blum, Avrim, Hartline, Jason, Mansour, Yishay
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing...
Reinforcement Learning in POMDPs Without Resets (2005)
Even-Dar, Eyal, Kakade, Sham, Mansour, Yishay
We consider the most realistic reinforcement learning setting in which an agent starts in an unknown environment (the POMDP) and must follow one continuous and uninterrupted chain of experience with...
Planning in POMDPS using Multiplicity Automata (2005)
Even-Dar, Eyal, Kakade, Sham, Mansour, Yishay
Planning and learning in Partially Observable MDPs (POMDPs) are among the most challenging tasks in both the AI and Operation Research communities. Although solutions to these problems are...
From External to Internal Regret (2005)
External regret compares the performance of an online algorithm, selecting among $N$ actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an...
Improved Second-Order Bounds for Prediction with Expert Advice (2005)
Cesa-Bianchi, Nicolò, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with arbitrary payoffs (positive or negative). External regret measures the difference between the payoff obtained by the forecasting...
Learning with Attribute Costs (2005)
Kaplan, Haim, Kushilevitz, Eyal, Mansour, Yishay
We study an extension of the ``standard'' learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model...
Fast Convergence of Selfish Routing (2005)
Even-Dar, Eyal, Mansour, Yishay
We consider $n$ anonymous selfish users that route their communication through $m$ parallel links. The users are allowed to reroute, concurrently, from overloaded links to underloaded links. The...
Fast Convergence of Selfish Rerouting (2005)
Even-Dar, Eyal, Mansour, Yishay
We consider $n$ identical selfish users that route their communication using $m$ parallel links. The users are allowed to reroute, concurrently, from overloaded links to underloaded links. The...
Improved second-order bounds for prediction with expert advice (2005)
Cesa-Bianchi, Nicolo, Mansour, Yishay, Stoltz, Gilles
This work studies external regret in sequential prediction games with arbitrary payoffs (nonnegative or non-positive). External regret measures the difference between the payoff obtained by the...
Experts in a Markov Decision Process (2004)
Even-Dar, Eyal, Kakade, Sham, Mansour, Yishay
We consider the MDP setting in which the reward function is chosen arbitrarily (possibly by an adversary) during each time step of play, yet the dynamics remain fixed. Similar to the experts setting,...
Experts in a Markov Decision Process (2004)
Even-Dar, Eyal, Kakade, Sham, Mansour, Yishay
We consider the MDP setting in which the reward function is chosen arbitrarily (possibly by an adversary) during each time step of play, yet the dynamics remain fixed. Similar to the experts setting,...
Generalization bounds for averaged classifiers (2004)
Freund, Yoav, Mansour, Yishay, Schapire, Robert E.
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, that is, the hypothesis that minimizes the training error, our...
Generalization bounds for averaged classifiers (2004)
Freund, Yoav, Mansour, Yishay, Schapire, Robert E.
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, that is, the hypothesis that minimizes the training error, our...
Concentration Bounds for Unigrams Language Model (2004)
Drukh, Evgeny, Mansour, Yishay
We show several PAC-style concentration bounds for learning unigrams language model. One interesting quantity is the probability of all words appearing exactly $k$ times in a sample of size $m$. A...
Concentration Bounds for Unigrams Language Model (2004)
We show several PAC-style concentration bounds for learning unigrams language model. One interesting quantity is the probability of all words appearing exactly k times in a sample of size m. A...
From External to Internal Regret (2004)
External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an...
Improved Combination of Online Algorithms for Acceptance and Rejection (2004)
David P. Bunde, Yishay Mansour
Given two admission control algorithms that are cA-accept- competitive and cR-reject-competitive respectively, we give two ways to make an algorithm that is simultaneously O(cA )- accept-competitive...
Competitive Algorithms for VWAP (2004)
Sham M. Kakade, Michael Kearns, Yishay Mansour, Luis E. Ortiz
We introduce new online models for two important aspects of modern financial markets: Volume Weighted Average Price trading and limit order books. We provide an extensive study of competitive...
Slide - The Key to Polynomial End-to-End Communication (2004)
Yehuda Afek, Baruch Awerbuch, Eli Gafni, Yishay Mansour, Nir Shavit
We consider the basic task of of end-to-end communication in dynamic networks, that is, delivery in finite time, of data items generated on-line by a sender, to a receiver, in order and without...
Competitive Queue Policies for Differentiated Services (2004)
William A. Aiello, Yishay Mansour, S. Rajagopolan
We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet...
Competitive Access Time via Dynamic Storage (2004)
We model the problem of storing items in some warehouse (modeled as an undirected graph) where a server has to visit items over time, with the goal of minimizing the total distance traversed by the...
Buffer Overflow Management in QoS Switches (2004)
Kesselmann,Alexander, Lotker,Zvi, Mansour,Yishay, Patt-Shamir,Boaz, Schieber,Baruch, Sviridenko,Maxim
Buffer Overflow Management in QoS Switches (2004)
Kesselmann, Alexander, Lotker, Zvi, Mansour, Yishay, Patt-Shamir, Boaz, Schieber, Baruch, Sviridenko, Maxim
Combining Online Algorithms for Rejection and Acceptance (2003)
Yossi Azar, Avrim Blum, Yishay Mansour
Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under...
Combining Online Algorithms for Rejection and Acceptance (2003)
Yossi Azar, Avrim Blum, Yishay Mansour
Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under...
Loss-Bounded Analysis for Differentiated Services. (2003)
Alexander Kesselman, Yishay Mansour
We consider a network providing Differentiated Services (Diffserv) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus...
QoS-Competitive Video Buffering (2003)
Many multimedia applications require transmission of streaming video from a server to a client across an internetwork. In many cases loss may be unavoidable due to congestion or heterogeneous nature...
Centralized Broadcast in Multihop Radio Networks (2003)
We show that for any radio network there exists a schedule of a broadcast whose time is O(D+log n),whereD is the diameter and n is the number of nodes. (This result implies an optimal broadcast to...
Loss-Bounded Analysis for Differentiated Services. (2003)
We consider a network providing Differentiated Services (DiffServ) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus...
QoS-Competitive Video Buffering (2003)
Alexander Kesselman, Yishay Mansour
Many multimedia applications require transmission of streaming video from a server to a client across an internetwork. In many cases loss may be unavoidable due to congestion or heterogeneous nature...
Competitive Buffer Management for Shared-Memory Switches (2003)
William Aiello, Ellen L. Hahne, Alexander Kesselman, Yishay Mansour
We consider buer management policies for shared memory packet switches supporting Quality of Service (QoS). There are two interesting dimensions in which the setting may dierent. The rst is the...
Harmonic Buffer Management Policy for Shared Memory Switches (2003)
Alexander Kesselman, Yishay Mansour
We introduce a new general scheme for shared memory non-preemptive scheduling policies. Our scheme utilizes a system of inequalities and thresholds and accepts a packet if it does not violate any of...
Convergence Time to Nash Equilibria (2003)
Eyal Even-dar, Alex Kesselman, Yishay Mansour
We study the number of steps required to reach a pure Nash Equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost.
Buer Over ow Management in QoS Switches (2003)
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko
We consider two types of buering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be transmitted in the order they arrive; the constraint...
Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Yishay Mansour, Yishay Mansourll, ...
Layered communication protocols frequently implement a FIFO message facility On top of an unreliable non-FIFO service such as that provided by a packet-switching network. This paper investigates the...
On Diffusing Updates in a Byzantine Environment (2002)
Dahlia Malkhi, Yishay Mansour, Michael K. Reiter
We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than t replicas...
The Data Link Layer: Two Impossibility Results (2002)
Nancy Lynch, Yishay Mansour, Alan Fekete
The data link layer in a layered communication network is designed to ensure reliable data transfer over a noisy physical channel. Formal specifications are given for physical channels and data...
Competitive Queueing Policies for QoS Switches (2002)
Nir Andelman, Yishay Mansour, An Zhu
We consider packet scheduling in a network providing di#erentiated services, where each packet is assigned a value. We study various queueing models for supporting QoS (Quality of Service). In the...
Almost K-Wise Independence Versus K-Wise Independence (2002)
Noga Alon, Oded Goldreich, Yishay Mansour
We say that a distribution over f0; 1g is almost k-wise independent if its restriction to every k coordinates results in a distribution that is close to the uniform distribution. A natural question...
Predicting and Bypassing End-to-End Internet Service Degradations (2002)
Anat Bremler-barr, Edith Cohen, Haim Kaplan, Yishay Mansour
We study the patterns and predictability of Internet End-to-End service degradations, where a degradation is a significant deviation of the round trip time between a client and a server. We use...
Almost K-Wise Independence Versus K-Wise Independence (2002)
Noga Alon, Oded Goldreich, Yishay Mansour
We say that a distribution over f0; 1g is almost k-wise independent if its restriction to every k coordinates results in a distribution that is close to the uniform distribution. A natural question...
The Computational Complexity of Universal Hashing (2002)
Yishay Mansour, Noam Nisan, Prasoon Tiwari
Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS = nm). The bound holds in the general boolean branching program model,...
AdaVegas: Adaptive Control for TCP Vegas (2002)
In this paper we introduce AdaVegas, an adaptive congestion control mechanism based on TCP Vegas. TCP Vegas has several parameters which control the way it increases the sending rate. While TCP Vegas...
Efficient Nash Computation in Large Population Games (2002)
Michael Kearns, Yishay Mansour
We introduce a general representation of largepopulation games in which each player's influence on the others is centralized and limited, but may otherwise be arbitrary. This representation...
Harmonic Buffer Management Policy for Shared Memory Switches (2002)
We introduce a new general scheme for shared memory nonpreemptive scheduling policies. Our scheme utilizes a system of inequalities and thresholds and accepts a packet if it does not violate any of...
Diffusion Without False Rumors: (2002)
Dahlia Malkhi, Yishay Mansour, Michael K. Reiter
We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than t replicas...
Convergence of Optimistic and Incremental Q- Learning (2002)
We show the convergence of two deterministic variants of Qlearning.
Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis (2001)
Avrim Blum, Merrick Furst, Michael Kearns, Yishay Mansour, Tel-aviv U, Steven Rudich, ...
We present new results on the well-studied problem of learning DNF expressions. We prove that an algorithm due to Kushilevitz and Mansour [13] can be used to weakly learn DNF formulas with membership...
Competitive Buffer Management for Shared-Memory Switches (2001)
Ellen L. Hahne, Alexander Kesselman, Yishay Mansour
We consider buer management policies for shared memory packet switches supporting Quality of Service (QoS). There are two interesting dimensions in which the setting may different. The rst is the...
A Sparse Sampling Algorithm for Near-Optimal (2001)
Michael Kearns, Yishay Mansour, Andrew Y. Ng
A critical issue for the application of Markov decision processes (MDPs) to realistic problems is how the complexity of planning scales with the size of the MDP. In stochastic environments with very...
Shai Ben-david, Philip M. Long, Yishay Mansour
. We extend the boosting paradigm to the realistic setting of agnostic learning, that is, to a setting where the training sample is generated by an arbitrary (unknown) probability distribution over...
Shai Ben-david, Philip M. Long, Yishay Mansour
. We extend the boosting paradigm to the realistic setting of
QoS-Competitive Video Buffering (2001)
Alexander Kesselman, Yishay Mansour
Many multimedia applications require transmission of streaming
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes (2001)
Michael Kearns, Yishay Mansour, Andrew Y. Ng
An issue that is critical for the application of Markov decision processes (MDPs) to realistic problems is how the complexity of planning scales with the size of the MDP. In stochastic environments...
QoS-Competitive Video Buffering (2001)
Alexander Kesselman, Yishay Mansour
Many multimedia applications require transmission of streaming video from a server to a client across an internetwork. In many cases loss may be unavoidable due to congestion or heterogeneous nature...
Competitive Buffer Management for Shared-Memory Switches (2001)
Ellen L. Hahne, Alexander Kesselman, Yishay Mansour
We consider buer management policies for shared memory packet switches supporting Quality of Service (QoS). There are two interesting dimensions in which the setting may different. The rst is the...
Simple Learning Algorithms for Decision Trees and Multivariate Polynomials (2001)
Nader H. Bshouty, Yishay Mansour
In this paper we develop a new approach for learning decision trees and multivariate
Jitter Control in QoS Networks (2001)
Yishay Mansour, Boaz Patt-shamir
We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: We propose on-line algorithms that control jitter and compare their...
Buffer Overflow Management in QoS Switches (2001)
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko
We consider two types of buffering policies that are used in network switches supporting QoS (Quality
Learning rates for Q-Learning (2001)
In this paper we derive convergence rates for Q-learning. We show an interesting relationship between the convergence rate and the learning rate used in the Q-learning. For a polynomial learning...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
On the Boosting Ability of Top-Down (2001)
Michael Kearns, Yishay Mansour
We analyze the performance of top-down algorithms for decision tree learning, such as those employed by the widely used C4.5 and CART software packages. Our main result is a proof that such...
Exact Inference of Hidden Structure (2001)
Michael Kearns, Yishay Mansour
this paper, we will restrict our attention to distributions obtained by setting all of the p i to some common value p, and we shall denote the resulting joint distribution on the outputs Y j by N p