Project topics and materials
Get Complete Project Material File(s) Now! »
Algorithmic Game Theory
As argued in [120], the birth of Algorithmic Game Theory (AGT) is often equated with the following three seminal papers, cited in [56] for laying the foundation of growth in AGT:
Koutsoupias, Papadimitriou,Worst-case Equilibria. STACS 1999: 404-413 [74], introduced the notion of “price of anarchy”, a measure of the extent to which competition approximates cooperation, quantifying how much utility is lost due to selfish behaviors on the Internet, which operates without a system designer or monitor striving to achieve the social optimum.
Roughgarden, Tardos: How Bad is Selfish Routing? FOCS 2000: 93-102 [100], studied the power and depth of the “price of anarchy” as it applies to routing traffic in large-scale communications networks to optimize the performance of a congested network.
Nisan, Ronen: Algorithmic Mechanism Design. STOC 1999: 129-140 [91], studied classical mechanism design from algorithmic and complexitytheoretic perspectives.
Topological Banach-Mazur Games
The infinite positional games of perfect information were discovered and initially studied in Poland around the ’30s. In 1935 Stefan Banach started a notebook, called the Scottish Book, where the mathematicians residing in or visiting Lw´ow proposed various mathematical problems, or conjectures, and also indicated their partial or complete solutions. In the same year Stanisław Mazur proposed an infinite combinatorial game. The game is described in Problem 43 of the Scottish Book; its solution, given by Banach, is dated August 4, 1935. Hence, the game became known as the Banach-Mazur Game. Mazur discovered the game in 1928; however, later on, Ulam [114] gives the year 1935 for its complete solution, referring to a conversation in the Scottisch Caf´e, where “Mazur proposed the first examples of infinite mathematical games”). Later on Ulam prepared an English translation of the Scottish Book, see [115]. Definition 1.9 (Banach-Mazur Games on R). In a Banach-Mazur Game, played on the real line, the winning condition is given by a set Win R of real numbers; in the first move, Player 0 selects an interval d0 on the real line, then Player 1 chooses an interval d1 ( d0, then Player 0 chooses a further refinement d2 ( d1 and so on. Thus a play forms an infinite (proper) chain sequence: d0 .
Background and Notation
The reader is referred to Subsection 1.2.2, Chapter 1, where we introduce some definitions, notations and well-know results about graphs and conservative graphs; moreover, where we recalled the relation between the consistency property of STNs and the conservative property of weighted graphs. In this chapter, we also deal with directed weighted hypergraphs.
Definition 2.1 (Hypergraph). A hypergraph H is a pair (V,A), where V is the set of nodes, and A is the set of hyperarcs. Each hyperarc A 2 A is either a multi-head or a multi-tail hyperarc.
A multi-head hyperarc A = (tA,HA,wA) has a distinguished node tA, called the tail of A, and a nonempty set HA V n ftAg containing the heads of A; to each head v 2 HA is associated a weight wA(v) 2 R. Fig. 2.5a depicts a possible representation of a multi-head hyperarc: the tail is connected to each head by a dashed arc labeled by the name of the hyperarc and the weight associated to the considered head. A multi-tail hyperarc A = (TA, hA,wA) has a distinguished node hA, called the head of A, and a nonempty set TA V n fhAg containing the tails of A; to each tail v 2 TA is associated a weight wA(v) 2 R. Fig. 2.5b depicts a possible representation of a multi-tail hyperarc: the head is connected to each tail by a dotted arc labeled by the name of the hyperarc and the weight associated to the considered tail.
Mean Payoff Games
In this section, we propose an introduction to Mean Payoff Games (MPGs) tailored to the needs of the present work. MPGs represent a well-studied model for representing some kinds of two-player dynamics and we will show in Section 6 that there is a substantial equivalence between the MPG and the HyTN model, which will allow us to exploit some important algorithmic and structural results. An MPG is a weighted directed graph G = (V0 [ V1,E) whose node set V is partitioned into two disjoint sets V0 and V1, where, for p = 0, 1, the nodes in Vp are those under control of Player p. Even with these graphs we have no loops and no parallel arcs. It is also assumed that every node has at least one outgoing arc. Notice that, in general, (V0,V1) does not need to be a bipartiton of G, i.e., E may contain arcs with both endpoints in V0, or with both endpoints in V1. An example is shown in Fig. 2.8, where nodes in V0 are white and those in V1 are filled in black.
Table of contents :
1 Introduction and Context
1.1 Contributions and Organization
1.2 Constraint Satisfaction Problems
1.2.1 Temporal Constraint Networks
1.2.2 Simple Temporal Networks
1.3 Algorithmic Game Theory
1.3.1 Topological Banach-Mazur Games
1.3.2 Gale-Stewart Games
1.3.3 Borel Determinacy Theorem
1.4 Modal m-calculus, w-Regular and Mean-Payoff Games
1.4.1 Syntax and Semantics of the Modal m-calculus
1.4.2 w-Regular Games
1.4.3 From model-checking of Lm to parity games
1.4.4 Mean-payoff games
1.4.5 From parity games to mean-payoff games
I Temporal Constraint Networks
2 Hyper Temporal Networks
2.1 Introduction
2.1.1 Contribution
2.1.2 Organization
2.2 Motivating Examples
2.3 Background and Notation
2.4 HyTN and Consistency Property
2.5 Mean Payoff Games
2.6 The Reductions
2.7 Computational Experiments
2.8 Related Works
2.9 Conclusion
3 Checking Dynamic Consistency of Conditional Hyper Temporal Networks via Mean Payoff Games
3.1 Introduction and Motivation
3.1.1 Contribution
3.1.2 Organization
3.2 Background and Notation
3.2.1 Simple Temporal Networks
3.2.2 Hyper Temporal Networks
3.3 Conditional Simple / Hyper Temporal Networks
3.4 Algorithmics of Dynamic Consistency
3.4.1 e-Dynamic Consistency
3.4.2 A (pseudo) Singly-Exponential Time Algorithm for DC and CHyTN-DC
3.5 Bounding Analysis on the Reaction Time ˆe
3.6 Related Works
4 Instantaneous Reaction-Time in Dynamic Consistency Checking of Conditional Simple Temporal Networks
4.1 Introduction and Motivation
4.1.1 Contribution
4.2 Background and Notation
4.2.1 #-Dynamic-Consistency
4.3 DC with Instantaneous Reaction-Time
4.3.1 The ps-tree: “skeleton” structure for p-dynamic p-ESs
4.3.2 Verifying a c-ps-tree.
4.3.3 A Singly-Exponential Time p-DC-Checking Algorithm
4.4 Related Works
4.5 Conclusion
II Infinite Games on Graphs
5 Linear Time Algorithm for Update Games via Strongly-Trap-Connected Components
5.1 Introduction
5.1.1 Background and Notation
5.2 Trap-Reachability
5.3 Strongly-Trap-Connectedness
5.4 TR-Depth-First-Search
5.5 Linear Time Algorithm for STCCs
5.5.1 Proof of Correctness of Algo.
5.6 Application to Update Games
5.7 Application to Explicit McNaughton-M¨ uller Games
5.8 Conclusion
6 Improved Pseudo-Polynomial Upper Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games
6.1 Introduction
6.1.1 Contribution
6.1.2 Organization
6.2 Background and Notation
6.3 Values and Optimal Positional Strategies from Reweightings
6.3.1 On Optimal Values
6.3.2 On Optimal Positional Strategies
6.4 A Q(jVj2jEjW) time Algorithm for solving the Value Problem and Optimal Strategy Synthesis in MPGs
6.4.1 Description of the Algorithm
6.4.2 Proof of Correctness
6.4.3 Complexity Analysis
6.5 Conclusions
7 Faster O(jVj2jEjW)-Time Energy Algorithm for Optimal Strategy Synthesis in Mean Payoff Games
7.1 Introduction
7.1.1 Contribution
7.1.2 Organization
7.2 Background and Notation
7.3 A Faster O(jVj2jEjW)-Time Algorithm for MPGs by Jumping through Reweighted EGs
7.3.1 Description of Algorithm 15
7.3.2 Correctness of Algorithm 15
7.3.3 Complexity of Algorithm 15
7.3.4 An Experimental Evaluation of Algorithm 15
7.4 Conclusion
8 The Energy Structure of Optimal Positional Strategies in MPGs
8.1 Introduction
8.1.1 Contribution
8.1.2 Organization
8.2 An Energy-Lattice Decomposition of optGSM
8.3 A Recursive Enumeration of X
