Optimization Online


Minimum cost subset selection with two competing agents

Claudia Marini(nicosia***at***dia.uniroma3.it)
Gaia Nicosia(nicosia***at***dia.uniroma3.it)
Andrea Pacifici(andrea.pacifici***at***uniroma2.it)
Ulrich Pferschy(pferschy***at***uni-graz.at)

Abstract: We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item that may be included in its solution set. We study two natural rules to decide which item between the two will be included and, for both rules, we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria. Moreover, we address the problem from a strategic point of view, that is finding the best moves for one agent against the opponent, in two distinct scenarios. We consider preventive or minimax strategies, optimizing the objective of the agent in the worst case, and best-response strategies, where the items submitted by the opponent are known in advance in each round.

Keywords: Multi-agent optimization, Combinatorial game theory, Pareto optimality, Computational complexity, Minimax strategies, Online algorithms.

Category 1: Combinatorial Optimization

Category 2: Other Topics (Game Theory )

Citation: Technical Report RT-DIA-179-2010, Dipartimento di Informatica e Automazione, Universit\`a Roma Tre.

Download: [PDF]

Entry Submitted: 11/11/2010
Entry Accepted: 11/11/2010
Entry Last Modified: 11/11/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society