Dongmo Zhang

AAMAS Conference 2024 Conference Paper

Extended Abstract: Price of Anarchy of Traffic Assignment with Exponential Cost Functions

• Jianglin Qiao
• Dave de Jonge
• Dongmo Zhang
• Simeon Simoff
• Carles Sierra
• Bo Du

This paper is an extended abstract version of "Price of Anarchy of Traffic Assignment with Exponential Cost Functions [5]". We study a routing game where vehicles, selfish agents, independently choose routes to minimize travel delays from road congestion. We focus on exponential latency functions, unlike prior research using polynomial functions like BPR. We calculate a tight upper bound for the price of anarchy and compare it with the BPR function. Results indicate that the exponential function has a lower upper bound for traffic volumes below road capacity than the BPR function. Numerical analysis using real-world data shows that the exponential function closely approximates road latency with even tighter parameters, resulting in a relatively lower upper bound.

AAMAS Conference 2022 Conference Paper

GDL as a Unifying Domain Description Language for Declarative Automated Negotiation

• Dave de Jonge
• Dongmo Zhang

We show that Game Description Language (GDL) can be used to describe some of the most commonly used test-beds in the automated negotiations literature, namely Genius and Colored Trails. This opens up an entirely new, declarative, approach to automated negotiation, in which a single algorithm can negotiate over a very broad class of different negotiation domains. We formally prove that the set of possible agreements of any negotiation domain from Genius (either linear or non-linear) can be modeled as a set of strategies over a deterministic extensive-form game that can be described efficiently in GDL. Furthermore, we show experimentally that, given only this GDL description, we can explore the agreement space efficiently using entirely generic domain-independent algorithms. In addition, we show that the same also holds for negotiation domains in the Colored Trails framework. This means we have the basic ingredients to implement a single negotiating agent that is capable of negotiating over many different kinds of negotiation domains, including Genius and Colored Trails.

AIJ Journal 2021 Journal Article

Epistemic GDL: A logic for representing and reasoning about imperfect information games

• Guifei Jiang
• Dongmo Zhang
• Laurent Perrussel
• Heng Zhang

This paper proposes a logical framework for representing and reasoning about imperfect information games. We first extend Game Description Language (GDL) with the standard epistemic operators and provide it with a semantics based on the epistemic state transition model. We then demonstrate how to use the language to represent the rules of an imperfect information game and formalize common game properties as well as epistemic properties. We also show how to use the framework to reason about players' own and each others' knowledge during game playing. Furthermore, we prove that the model-checking problem of the framework is in Δ 2 P, even though its lower bound is Θ 2 P. These results indicate that the framework makes a good balance between expressive power and computational efficiency. Finally we provide a sound and complete axiomatic system for this logic. With action, temporal and epistemic operators, the completeness proof requires a novel combination of techniques used for completeness of dynamic logic and epistemic temporal logics. The proof theory provides a feasible tool to analyze properties of a family of games.

JAAMAS Journal 2021 Journal Article

GDL as a unifying domain description language for declarative automated negotiation

• Dave de Jonge
• Dongmo Zhang

Abstract Recently, it has been proposed that Game Description Language (GDL) could be used to define negotiation domains. This would open up an entirely new, declarative, approach to Automated Negotiations in which a single algorithm could negotiate over any domain, as long as that domain is expressible in GDL. However, until now, the feasibility of this approach has only been demonstrated on a few toy-world problems. Therefore, in this paper we show that GDL is a truly unifying language that can also be used to define more general and more complex negotiation domains. We demonstrate this by showing that some of the most commonly used test-beds in the Automated Negotiations literature, namely Genius and Colored Trails, can be described in GDL. More specifically, we formally prove that the set of possible agreements of any negotiation domain from Genius (either linear or non-linear) can be modeled as a set of strategies over a deterministic extensive-form game. Furthermore, we show that this game can be effectively described in GDL and we show experimentally that, given only this GDL description, we can explore the agreement space efficiently using entirely generic domain-independent algorithms. In addition, we show that the same holds for negotiation domains in the Colored Trails framework. This means that one could indeed implement a single negotiating agent that is capable of negotiating over a broad class of negotiation domains, including Genius and Colored Trails.

JAAMAS Journal 2019 Journal Article

Strategic negotiations for extensive-form games

• Dave de Jonge
• Dongmo Zhang

Abstract When studying extensive-form games it is commonly assumed that players make their decisions individually. One usually does not allow the possibility for the players to negotiate their respective strategies and formally commit themselves to future moves. As a consequence, many non-zero-sum games have been shown to have equilibrium outcomes that are suboptimal and arguably counter-intuitive. For this reason we feel there is a need to explore a new line of research in which game-playing agents are allowed to negotiate binding agreements before they make their moves. We analyze what happens under such assumptions and define a new equilibrium solution concept to capture this. We show that this new solution concept indeed yields solutions that are more efficient and, in a sense, closer to what one would expect in the real world. Furthermore, we demonstrate that our ideas are not only theoretical in nature, but can also be implemented on bounded rational agents, with a number of experiments conducted with a new algorithm that combines techniques from Automated Negotiations, (Algorithmic) Game Theory, and General Game Playing. Our algorithm, which we call Monte Carlo Negotiation Search, is an adaptation of Monte Carlo Tree Search that equips the agent with the ability to negotiate. It is completely domain-independent in the sense that it is not tailored to any specific game. It can be applied to any non-zero-sum game, provided that its rules are described in Game Description Language. We show with several experiments that it strongly outperforms non-negotiating players, and that it closely approximates the theoretically optimal outcomes, as defined by our new solution concept.

AAMAS Conference 2017 Conference Paper

Automated Negotiations for General Game Playing

• Dave de Jonge
• Dongmo Zhang

In this paper we present a new algorithm for negotiations in non-zero-sum games. Although games have been studied extensively, most game playing algorithms have been developed under the assumption that players do not communicate. Many real-world problems, however, can be modeled as non-zero-sum games in which players may mutually benefit if they coordinate their actions, which requires negotiation. The field of Automated Negotiations is another important topic in AI, but in this field one usually assumes that utility functions have explicit expressions and can therefore be calculated easily. Traditional approaches do not apply to domains in which the utility values are instead determined by the rules of a complex game. In this paper we aim to bridge the gap between General Game Playing and Automated Negotiations. Our algorithm is an adaptation of Monte Carlo Tree Search that allows players to negotiate. It is completely domain-independent in the sense that it is not tailored to any specific game. It can be applied to any non-zero-sum game, provided that its rules are described in Game Description Language.

LORI Conference 2017 Conference Paper

On Axiomatization of Epistemic GDL

• Guifei Jiang
• Laurent Perrussel
• Dongmo Zhang

Abstract The Game Description Language (GDL) has been introduced as an official language for specifying games in the AAAI General Game Playing Competition since 2005. It was originally designed as a declarative language for representing rules of arbitrary games with perfect information. More recently, an epistemic extension of GDL, called EGDL, has been proposed for representing and reasoning about imperfect information games. In this paper, we develop an axiomatic system for a variant of EGDL and prove its soundness and completeness with respect to the semantics based on the epistemic state transition model. With a combination of action symbols, temporal modalities and epistemic operators, the completeness proof requires novel combinations of techniques used for completeness of propositional dynamic logic and epistemic temporal logic. We demonstrate how to use the proof theory for inferring game properties from game rules.

IJCAI Conference 2016 Conference Paper

Epistemic GDL: A Logic for Representing and Reasoning about Imperfect Information Games

• Guifei Jiang
• Dongmo Zhang
• Laurent Perrussel
• Heng Zhang

This paper proposes a logical framework for representing and reasoning about imperfect information games. We first extend the game description language (GDL) with the standard epistemic operators and provide it with a semantics based on the epistemic state transition model. We then demonstrate how to use the language to represent the rules of an imperfect information game and formalize its epistemic properties. We also show how to use the framework to reason about player's own as well as other players' knowledge during game playing. Finally we prove that the model-checking problem of the framework is in Δ 2 p, which is the lowest among the existing similar frameworks, even though its lower bound is Θ 2 p. These results indicate that the framework makes a good balance between expressive power and computational efficiency.

JELIA Conference 2016 Conference Paper

Refinement of Intentions

• Andreas Herzig
• Laurent Perrussel
• Zhanhao Xiao
• Dongmo Zhang

Abstract According to Bratman, future-directed intentions are high-level plans. We view such plans as high-level actions that can typically not be executed directly: they have to be progressively refined until executable basic actions are obtained. Higher- and lower-level actions are linked by the means-end relation, alias instrumentality relation. In this paper we extend Shoham’s database perspective of Bratman’s theory by the notions of refinement and instrumentality.

AAAI Conference 2015 Conference Paper

A Logic for Reasoning About Game Strategies

• Dongmo Zhang
• Michael Thielscher

This paper introduces a modal logic for reasoning about game strategies. The logic is based on a variant of the well-known game description language for describing game rules and further extends it with two modalities for reasoning about actions and strategies. We develop an axiomatic system and prove its soundness and completeness with respect to a specific semantics based on the state transition model of games. Interestingly, the completeness proof makes use of forgetting techniques that have been widely used in the KR&R literature. We demonstrate how general game-playing systems can apply the logic to develop game strategies.

LORI Conference 2013 Conference Paper

Judgment Aggregation with Abstentions: A Hierarchical Approach

• Guifei Jiang
• Dongmo Zhang
• Xiaojia Tang

Abstract This paper presents a quasi-lexicographic judgment aggregation rule based on the hierarchy of judges. We do not assume completeness at both individual and collective levels, which means that a judge can abstain from a proposition and the collective judgment on a proposition can be undetermined. We prove that the proposed rule is (weakly) oligarchic. This is by no means a negative result. In fact, our result demonstrates that with abstentions, oligarchic aggregation is not necessarily a single level determination but can be a multiple-level democracy, which partially explains its pervasiveness in the real world.

ECAI Conference 2012 Conference Paper

Multi-unit Double Auction under Group Buying

• Dengji Zhao
• Dongmo Zhang
• Laurent Perrussel

Group buying is a business model in which a number of buyers join together to make an order of a product in a certain quantity in order to gain a desirable discounted price. Such a business model has recently received significant attention from researchers in economics and computer science, mostly due to its successful application in online businesses, such as Groupon. This paper deals with the market situation when multiple sellers sell a product to a number of buyers with discount for group buying. We model this problem as a multi-unit double auction. We first examine two deterministic mechanisms that are budget balanced, individually rational and only one-sided truthful, i. e. it is truthful for either buyers or sellers. Then we find that, although there exists a "trivial" (non-deterministic) mechanism that is (weakly) budget balanced, individually rational and truthful for both buyers and sellers, such a mechanism is not achievable if we further require that both the trading size and the payment are neither seller-independent nor buyer-independent. In addition, we show that there is no budget balanced, individually rational and truthful mechanism that can also guarantee a reasonable trading size.

JELIA Conference 2012 Conference Paper

Relevant Minimal Change in Belief Update

• Laurent Perrussel
• Jerusa Marchi
• Jean-Marc Thévenin
• Dongmo Zhang

Abstract The notion of relevance was introduced by Parikh in the belief revision field for handling minimal change. It prevents the loss of beliefs that do not have connections with the epistemic input. But, the problem of minimal change and relevance is still an open issue in belief update. In this paper, a new framework for handling minimal change and relevance in the context of belief update is introduced. This framework goes beyond relevance in Parikh’s sense and enforces minimal change by first rewriting the Katzuno-Mendelzon postulates for belief update and second by introducing a new relevance postulate. We show that relevant minimal change can be characterized by setting agent’s preferences on beliefs where preferences are indexed by subsets of models of the belief set. Each subset represents a prime implicant of the belief set and thus stresses the key propositional symbols for representing the belief set.

AAAI Conference 2011 Conference Paper

Language Splitting and Relevance-Based Belief Change in Horn Logic

• Maonia Wu
• Dongmo Zhang
• Mingyi Zhang

This paper presents a framework for relevance-based belief change in propositional Horn logic. We firstly establish a parallel interpolation theorem for Horn logic and show that Parikh’s Finest Splitting Theorem holds with Horn formulae. By reformulating Parikh’s relevance criterion in the setting of Horn belief change, we construct a relevance-based partial meet Horn contraction operator and provide a representation theorem for the operator. Interestingly, we find that this contraction operator can be fully characterised by Delgrande and Wassermann’s postulates for partial meet Horn contraction as well as Parikh’s relevance postulate without requiring any change on the postulates, which is qualitatively different from the case in classical propositional logic.

IJCAI Conference 2011 Conference Paper

Mechanism Design for Double Auctions with Temporal Constraints

• Dengji Zhao
• Dongmo Zhang
• Laurent Perrussel

This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in this model can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a Vickrey-Clarke-Groves (VCG) mechanism in this model and demonstrate the advantages of the payment compared with the classical VCG payment (the Clarke pivot payment). We also show that the algorithms for both allocation and payment calculation run in polynomial time. It is expected that the method and results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.

AIJ Journal 2010 Journal Article

A logic-based axiomatic model of bargaining

• Dongmo Zhang

This paper introduces an axiomatic model for bargaining analysis. We describe a bargaining situation in propositional logic and represent bargainers' preferences in total pre-orders. Based on the concept of minimal simultaneous concessions, we propose a solution to n-person bargaining problems and prove that the solution is uniquely characterized by five logical axioms: Consistency, Comprehensiveness, Collective rationality, Disagreement, and Contraction independence. This framework provides a naive solution to multi-person, multi-issue bargaining problems in discrete domains. Although the solution is purely qualitative, it can also be applied to continuous bargaining problems through a procedure of discretization, in which case the solution coincides with the Kalai–Smorodinsky solution.

AAAI Conference 2010 Conference Paper

Dynamic Auction: A Tractable Auction Procedure

• Dongmo Zhang
• Laurent Perrussel

Dynamic auctions are trading mechanisms for discovering market-clearing prices and efficient allocations based on price adjustment processes. This paper studies the computational issues of dynamic auctions for selling multiple indivisible items. Although the decision problem of efficient allocations in a dynamic auction in general is intractable, it can be solved in polynomial time if the economy under consideration satisfies the condition of Gross Substitutes and Complements, which is known as the most general condition that guarantees the existence of Walrasian equilibrium. We propose a polynomial algorithm that can be used to find efficient allocations and introduce a double-direction auction procedure to discover a Walrasian equilibrium in polynomial time.

IJCAI Conference 2009 Conference Paper

• Dongmo Zhang

This paper presents an axiomatic analysis of negotiation problems within task-oriented domains (TOD). We start by applying three classical bargaining solutions of Nash, Kalai-Smorodinsky and Egalitarian to the domains of problems with a preprocess of randomization on possible agreements. We find out that these three solutions coincide within any TOD and can be characterized by the same set of axioms, which specify a solution of task oriented negotiation as an outcome of dualprocess of maximizing cost reduction and minimizing workload imbalance. This axiomatic characterization is then used to produce an approximate solution to the domain of problems without randomization on possible agreements.

AAAI Conference 2007 Conference Paper

Reasoning about Bargaining Situations

• Dongmo Zhang

This paper presents a logical axiomatization of bargaining solutions. A bargaining situation is described in propositional logic and the bargainers’ preferences are quantified in terms of the logical structure of the bargaining situation. A solution to the n-person bargaining problems is proposed based on the maxmin rule over the degrees of bargainers’ satisfaction. We show that the solution is uniquely characterized by four natural and intuitive axioms as well as three other fundamental assumptions. All the axioms and assumptions are represented in logical statements and most of them have a game-theoretic counterpart. The framework would help us to identify the logical and numerical reasoning behind bargaining processes.

AAAI Conference 2006 Conference Paper

A Computational Model of Logic-Based Negotiation

• Dongmo Zhang

This paper presents a computational model of negotiation based on Nebel’s syntax-based belief revision. The model guarantees a unique bargaining solution for each bargaining game without using lotteries. Its game-theoretic properties are discussed against the existence and uniqueness of Nash equilibrium and subgame perfect equilibrium. We also study essential computational properties in relation to our negotiation model. In particular, we show that the deal membership checking is DP-complete and the corresponding agreement inference problem is ΠP 2 -hard.

AAMAS Conference 2005 Conference Paper

Negotiation Mechanism for TAC SCM Component Market

• Dongmo Zhang

KR Conference 2004 Conference Paper

Logical foundations of negotiation: strategies and preferences

• Norman Foo
• Rex Kwok
• Thomas Meyer
• Dongmo Zhang

This paper is a contribution towards the body of literature which views negotiation in a qualitative light. It builds on an existing logical framework for negotiation between rational, cooperative, truthful agents proposed by Meyer et al. We show that agents equipped with negotiation strategies corresponding to basic AGM belief revision operations are capable of reaching exactly the permissible deals defined and discussed in previous work. Each agent has to present a set of weakened demands to the other party who, in return, is obliged to accept all weakened demands. The acceptance of demands is modelled by basic AGM belief revision. We extend the logical framework of Meyer et al. by considering scenarios in which the initial demand sets of agents may vary. We show that it forces agents to limit their negotiation strategies to AGM belief revision satisfying the supplementary AGM postulates. This leads to the redefinition of a negotiation strategy as a reference relation on demands. This extended framework provides a description of the deals that an agent ought to consider as reasonable, but provides no information on how it should go about choosing a particular deal. We conclude with suggestions on how negotiation strategies can be used to do so.

AAAI Conference 2004 Conference Paper

Negotiation as Mutual Belief Revision

• Dongmo Zhang
• Thomas Meyer

This paper presents a logical framework for negotiation based on belief revision theory. We consider that a negotiation process is a course or multiple courses of mutual belief revision. A set of AGM-style postulates are proposed to capture the rationality of competitive and cooperative behaviors of negotiation. We first show that the AGM revision and its iterated extension is a special case of negotiation function. Then we show that a negotiation function can be constructed by two related iterated belief revision functions under a certain coordination mechanism. This provides a qualitative method for constructing negotiation space and rational concessions. It also shows a glimpse of how to express game-theoretical concepts in logical framework.

JELIA Conference 2002 Conference Paper

Interpolation Properties of Action Logic: Lazy-Formalization to the Frame Problem

• Dongmo Zhang
• Norman Y. Foo

Abstract This paper makes a contribution to the meta-theory of reasoning about action. We present two interpolation properties of action logic. We show that the frame axioms which are required for answering a query involve only the objects which are relevant to the query and action description. Moreover, if the action description is expressed by normal form, the required frame axioms depend on only the query itself. Therefore the frame problem may be mitigated by localizing descriptions and postponing the listing of frame axioms till a query occurs. This offers a pragmatic solution to the frame problem. This solution does not rest on any meta-hypotheses most existing solutions to the frame problem rely on.

IJCAI Conference 1997 Conference Paper

Nonmonotonic Reasoning and Multiple Belief Revision

• Dongmo Zhang
• Shiju Chen
• Wujia Zhu
• Hongbing Li

IJCAI Conference 1997 Conference Paper

Representation Theorems for Multiple Belief Changes

• Dongmo Zhang
• Shiju Chen
• Wujia Zhu
• Zhaoqian Chen

This paper aims to develop further and systemize the theory of multiple belief change based on the previous work on the package contraction, developed by [Fuhrmann and Hansson 1994] and the general belief changes, developed by [Zhang 1996]. Two main representation theorems for general contractions are given, one is based on partial meet models and the other on nice-ordered partition models. An additional principle, called Limit Postulate, for the general belief changes is introduced which specifies properties of infinite belief changes. The results of this paper provides a foundation for investigating the connection between infinite nonmonotonic reasoning and multiple belief revision.