Publication - Self-interested Database Managers Playing The View Maintenance Game

Authors: Mostafa, Hala; Lesser, Victor; and Miklau, Gerome
Title: Self-interested Database Managers Playing The View Maintenance Game
Abstract: A database view is a dynamic virtual table composed of the result set of a query, often executed over different underlying databases. The view maintenance problem concerns how a view is refreshed when the data sources are updated. We study the view maintenance problem when self-interested database managers from different institutions are involved, each concerned about the privacy of its database. We regard view maintenance as an incremental, sequential process where an action taken at a stage affects what happens at later stages. The contribution of this paper is twofold. First, we formulate the view maintenance problem as a sequential game of incomplete information where at every stage, each database manager decides what information to disclose, if any, without knowledge of the number or nature of updates at other managers. This allows us to adopt a satisficing approach where the final view need not reflect 100% of the databases updates. Second, we present an anytime algorithm for calculating ²-Bayes-Nash equilibria that allows us to solve the large games which our problem translates to. Our algorithm is not restricted to games originating from the view maintenance problem; it can be used to solve general games of incomplete information. In addition, experimental results demonstrate our algorithm’s attractive anytime behavior which allows it to find good-enough solutions to large games within reasonable amounts of time.
Keywords: Search, Self-Interested Negotiation, Uncertainty
Publication: Proceedings of the Seventh International Conference on Autonomous Agents and Multi-Agent Systems, pp. 871 - 878
Editor: Padgham, Parkes, Müller and Parsons
Location: Estoril, Portugal
Publisher: IFMAAS
Date: May 2008
Sources: PDF: /Documents/mostafa_aamas2008.pdf
Notes: (Full paper)
Reference: Mostafa, Hala; Lesser, Victor; and Miklau, Gerome. Self-interested Database Managers Playing The View Maintenance Game. Proceedings of the Seventh International Conference on Autonomous Agents and Multi-Agent Systems, Padgham, Parkes, Müller and Parsons, ed., IFMAAS, pp. 871-878. May 2008. (Full paper)
bibtex: 
@inproceedings{Mostafa-439,
  author    = "Hala Mostafa and Victor Lesser and Gerome Miklau",
  title     = "{Self-interested Database Managers Playing The View
               Maintenance Game}",
  booktitle = "Proceedings of the Seventh International
               Conference on Autonomous Agents and Multi-Agent
               Systems",
  editor    = "Parkes Padgham and ller Mu\̈ and Parsons",
  publisher = "IFMAAS",
  pages     = "871-878",
  month     = "May",
  year      = "2008",
  address   = "Estoril, Portugal",
  url       = "http://mas.cs.umass.edu/paper/439",
}