Name
Abstract | ||
|---|---|---|
Machine learning can provide powerful tools for the design and analysis of multi-agent systems, as well as a novel lens on important questions in the area. In this talk I will focus on the use of machine learning for understanding submodular functions, an important class of discrete functions that model laws of diminishing returns and enjoy many important applications in multi-agent settings. For example, submodular functions are commonly used to model valuation functions for bidders in auctions, the influence of various subsets of agents in social networks, and the benefits of performing different actions in a variety of situations. Traditionally it is assumed that these functions are known to the decision maker; however, for large scale systems, in the age of big data, it is often the case they must be learned from observations. In this talk, I will discuss a recent line of work on studying the learnability of submodular functions, and highlight its applications to the analysis of multi-agent systems. I will discuss both general algorithms for learning such functions, as well as even better guarantees that can be achieved for important classes appearing in multi-agent scenarios that exhibit additional structure. These classes include: probabilistic coverage functions that can be used to model the influence function in classic models of information diffusion in networks; functions with bounded complexity used in modeling bidder valuation functions in auctions, including XOS and gross-substitutes; and classes of functions appearing in cooperative game theory for expressing the values of various types of coalitions. I will additionally discuss a large scale application of our algorithms for learning the influence functions in social networks, that significantly outperforms existing approaches empirically in both synthetic and real world data. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.5555/2772879.2772882 | Autonomous Agents and Multi-Agent Systems |
Keywords | Field | DocType |
Diminishing returns, learning submodular functions, influence of agents in social networks, valuation functions in auctions, values of coalitions | Computer science,Submodular set function,Multi-agent system,Cooperative game theory,Common value auction,Artificial intelligence,Probabilistic logic,Big data,Learnability,Machine learning,Bounded function | Conference |
Citations | PageRank | References |
3 | 0.38 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria-Florina Balcan | 1 | 1445 | 105.01 |