Abstract:  A switched dynamical system consists of a finite set of interacting linear or nonlinear subsystems. The interaction of the constituent subsystems is made possible by a supervisory switching signal that can be exogenous, state-driven, event-driven, time-driven, deterministic, or even totally random. This talk will concern the identification of switched linear systems from input-output data. The main challenge with this problem lies in the fact that the collected measurements are available only as a mixture of observations generated by different subsystems. That is, since the switching signal is unknown, one does not know a priori which subsystem has generated which data.
To overcome this difficulty, we present in this work a sparse optimization approach inspired by very recent developments from the community of compressed sensing. The application of the proposed method does not require any prior classification of the data according to their respective generating-submodels. We formally pose the problem of identifying each linear as a combinatorial L0 norm optimization problem that fits all the data to a single parameter vector. However as such, the problem is known to be NP-hard. Nevertheless it can be interestingly relaxed into a convex L1-norm minimization problem. Applying this idea leads to a final algorithm that allows us to extract one after another, the parameter vectors associated with the different subsystems, by means of convex optimization.

 

June 15, 16:00
Michel Grabisch,  Sorbonne Economic Centre, Université Paris 1 (Panthéon-Sorbonne)
A coalition formation value
Abstract:  Coalition formation is an important topic related to game theory, multi-agent systems and economics. Supposing that coalitions earn some benefit or pay some cost for using goods or services, a central problem is how to determine the allocation of the benefit or cost among all participating players/agents. Our talk will consist of two parts, dealing with two particular situations. We put N, the set of all players, of cardinality n.
The first part considers the case of games with externalities, best modelled under partition function form game: it is assumed that the worth of a coalition depends on the organization of the society of the remaining players. Furthermore, we suppose that the starting point is the society of all individual players (no coalition is formed), and that step by step this society evolves till attaining the grand coalition (all players are in a single coalition). We introduce the notion of scenario and process. A process is a sequence of partitions  of players, starting from the finest partition (the society of all individual players) and finishing at the coarsest partition, that is, the set of players itself, and between two steps, there is one and only one merging of two blocks of the current partition. Each process gives rise to n scenarios, one per player, which are simply the process under the viewpoint of a given player. The original point of our approach is to define a value for scenarios, considered as an elementary brick, then from this a value for process, and finally for the game itself. We propose two axiomatizations of the scenario value, reflecting well the idea of coalition formation.
In the second part, we do not consider externalities, but coalitions can be formed completely freely. That is, the sequence of coalitions is arbitrary, and in particular need not be a chain.  The model behind  this is  a  Markovian approach of coalition formation,  i.e., coalitions are viewed as states  and therefore from the transition matrix, we can compute for each sequence of coalitions its probability of occurrence.  Such sequences with positive probabilities correspond to scenarios of the first part. We define a value for scenarios, and the value of the game under a given Markov process is the expectation of all scenario values. We give also axiomatizations of the scenario value.

 

June 9, 16.00
Bettina Klaus, Department of Economics, University of Lausanne, Switzerland
Allocation via Deferred-Acceptance under Responsive Priorities.
Abstract:  In many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource-monotonicity with two-agent consistent conflict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.

 

January 25, 16.00
Robert P. Gilles, Queen's University Belfast, UK
Partial Cooperation and Pollution Abatement: A Game Theoretic Approach
Abstract:  We consider a normal form game in which there is a single coalition of cooperating players who can write a binding agreement. The coalition under consideration only writes a binding agreement with regard to a particular (collective) action, while the other actions remain under the complete, individual control of the players. Two equilibrium concepts are developed and analyzed.
First, we extend the standard Nash equilibrium to this case of partial cooperation in which all players and the coalition of cooperators make simultaneous decisions. Second, we consider a leadership equilibrium in which the coalition of cooperators writes a contract concerning the collective action before all players decide about their individual choices. The latter extends a similar concept developed by Malozzi and Tijs. For both equilibrium concepts we provide existence theorems.
We apply this game theoretic framework to the issue of pollution abatement. We consider the development of green production technologies under sharing agreements. We consider Nash equilibrium as well as the two newly introduced equilibrium concepts to analyze the adoption of green production technologies.

 

January 25, 14:00
Michael Rovatsos, University of Edinburgh, UK
Towards a "Strategic" Web
Abstract:  Strategic reasoning and decision making, i.e. reasoning in environments in which one is interacting with other agents who may have conflicting views or objectives, is ubiquitous in large-scale multiagent environments such as the Web. Yet, in the current Web landscape, users are not supported by existing Web technologies in the process of managing their strategic interactions, and this constitutes a major technological barrier to better exploitation of  the "strategic layer" of the Web.
In this talk, I will present a vision of what could be termed the "Strategic" Web, i.e. knowledge-based methods based on multiagent systems, AI planning, and game theory that may have the potential of scaling up sufficiently well to be used in real-world applications in complex domains of strategic interaction.
I will present some recent contributions, both from our own work as from the literature that give a flavour for the kinds of techniques that could be relevant, and discuss the main challenges of potential future work.