Prof. Sarne's Lab
Prof. David Sarne, a Bar-Ilan University alumnus, is a Senior Lecturer in the Department of Computer Science. After spending several years in the Israeli hi-tech industry, he completed a post-doctoral position at Harvard University and then returned to Bar-Ilan University.
In Sarne's lab, research focuses on increasing the power of autonomous agents by providing them with capabilities for reasoning in environments in which the resource costs of reasoning about different available actions must be taken into account.
Sarne and his group have made significant contributions, both theoretical and practical, to the development of methods that improve bounded-rational agents' search, including such fundamental aspects of search-based multi-agent settings as the value of information (in particular for scheduling and planning systems), social and individual welfare and stability, matching throughput, and game theoretic aspects of the strategies.
These methods address the resource costs challenge by effectively optimizing goal functions that combine both outcome and the resources spent achieving that outcome.
The results of his research have led to improved search and matching algorithms and methods, and they apply directly to market design, mediators and service providers, as well as buyers and other kinds of agents that incorporate search in their reasoning about action outcomes.
Combining Search Theory and eCommerce
In collaboration with Prof. Sanmay Das of Rensselaer Polytechnic Institute, Sarne's group is studying new algorithms for comparison shopping agents (CSAs), and equilibria that arise in electronic marketplaces mediated by CSAs. Current models of e-commerce marketplaces are almost exclusively two-sided, considering direct interactions between buyers and sellers.
In reality, the presence of intermediaries can have significant effects on buyer and seller strategies, especially through the incentives they are willing to offer to the intermediaries.
The group's recent work explores the concept of expert-mediated search and how the presence of the expert changes the consumer's search process, and the role that can be played by a market designer or regulator in increasing social welfare in such markets.
In another related project in this field, Sarne and his group have demonstratedhow multi-agent decision making based on self-interested comparison shopping agents can in some cases result in both lower expense to buyers and higher net revenues to sellers.
Restructuring Decisions for the Benefit of Decision Makers
In many settings and for various reasons, people fail to make optimal decisions. These factors also influence the agents people design to act on their behalf in such virtual environments as eCommerce and distributed operating systems, so that the agents also act sub-optimally despite their greater computational capabilities.
In some decision making situations it is theoretically possible to supply the optimal strategy to people or their agents, but this optimal strategy may be non-intuitive, and providing a convincing explanation of optimality may be complex.
Sarne’s group explores an alternative approach to improving the performance of a decision-maker in such settings: instead of attempting to change a decision-maker’s strategy directly so that it aligns better with the optimal one, the decision making problem itself is restructured.
Within this framework, different types of generic and adaptive heuristics for manipulating the data on choices are developed to guide decision makers to a strategy that is closer to optimal. Promising results of the new approach have been demonstrated within the job-scheduling in distributed settings domain.
Finding a Way in Dynamic Ad-hoc Settings
In highly dynamic environments, where no stable communication infrastructure is available (e.g., rescue), finding a subscriber, and establishing a communication route to it, can be a substantially resource consuming task.
One of the ways of controlling the overhead associated with this process is through the use of Expanding Ring Search (ERS).
In ERS the source node searches for the target in a multi ring scheme instead of an one-to-all scheme. This is achieved by increasing the TTL value from an initial value to a predefined threshold to expand the radius of the search linearly.
This method was first presented for DSR and then proposed also for AODV. Sarne’s group is taking the ERS notion a step forward, taking advantage of statistical information concerning the minimum hop-count distribution to the destination node for extracting the optimal expanding-ring sequence. As part of this research effort, the group has shown that the minimum hop-count can be modeled in many cases as a stationary ergodic process.
Furthermore, it has been shown that the search, in some realistic cases, should not necessarily expand but also retreat in its extent as a function of the time elapsed and the mobility model followed by the different nodes. The applicability of this research is enhanced by complementary mechanisms for distributed learning of the minimum hop-count distribution and location-aided expanding-ring search, which were developed by Sarne and his group.