Economical Graph Discovery

Noga Alon (), Yuval Emek (), Michal Feldman () and Moshe Tennenholtz ()
Additional contact information
Noga Alon: Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel; Institute for Advanced Study, Princeton, New Jersey 08540; and Microsoft Research Israel, Herzeliya 4672513, Israel
Yuval Emek: Faculty of Industrial Engineering and Management, Technion–Israel Institute of Technology, Haifa 3200003, Israel
Michal Feldman: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel; and Microsoft Reserach Israel, Herzeliya 4672513, Israel
Moshe Tennenholtz: Faculty of Industrial Engineering and Management, Technion–Israel Institute of Technology, Haifa 3200003, Israel; and Microsoft Research Israel, Herzeliya 4672513, Israel

Operations Research, 2014, vol. 62, issue 6, 1236-1246

Abstract: We consider the problem of graph discovery in settings where the graph topology is known and the edge weights are hidden. The setting consists of a weighted graph G with n vertices and m edges and with designated source s and destination t . We study two different discovery problems, namely, (i) edge weight discovery, where the goal is to discover all edge weights, and (ii) shortest path discovery, where the goal is to discover a shortest ( s , t )-path. This discovery is done by means of agents that traverse different ( s , t )-paths in multiple rounds and report back the total cost they incurred. Three cost models are considered, differing from each other in their approach to congestion effects. In particular, we consider congestion-free models as well as models with positive and negative congestion effects. We seek bounds on the number of rounds and the number of agents required to complete the edge weights or the shortest path discovery. Several results concerning such bounds for both directed and undirected graphs are established. Among these results, we show that (1) for undirected graphs, all edge weights can be discovered within a single round consisting of m agents, (2) discovering a shortest path in either undirected or directed acyclic graphs requires at least m − n + 1 agents, and (3) the edge weights in a directed acyclic graph can be discovered in m rounds with m + n − 2 agents under congestion-aware cost models. Our study introduces a new setting of graph discovery under uncertainty and provides fundamental understanding of the problem.

Keywords: graph discovery; shortest path; congestion; cost sharing (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2014.1313 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:6:p:1236-1246

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().