1 Agents and Objects? similarities and differences
2 Different architectures of agents
(1) practical reasoning
what are the functionalities of each component?
how do they interact with each other?
commitments to ends and means
??? while not (empty(pi), or succeed(I, B), or impossible(I, B)) do
while not (empty(pi), or succeed(I, B), or believeimpossible(I, B)) do
(2) planner system
example-1 STRIPS planning problem
(3) BDI architecture
(4) subsumption architecture
(5) horizontal, vertical & hybrid architecture
example-1 Touring Machine
example-2 InterRRap
3 Specific case: Blocks World problem + vacuum machine problem
4 Payoff Matrices [WEEK 9 Multi-agent Interactions]
utilities and preference: u(w) >= u(w') <--> w )= w'
w - state of the world; u - utility function; a - actions, ai*aj --> w
(N, A, U) U - the set of players; A = A1*A2*...*An, Ai is the set of actions available to player i; U - the set of utility functions for each player, it can be enclosed in the payoff matrix.
payoff matrix 合并
* if it is the case of prisoner dilemma, the smaller utility the better, otherwise, the larger the better.
(0) Dominant strategies
Si is the dominant strategy for i if no matter what strategy j choose, i will do at least as well as choosing other strategies.
Dominant strategy 解法图示
(1) Nash equilibrium
s1 and s2 are in Nash equilibrium if: [1] under the assumption that agent i plays s1, agent j can do no better than playing s2 AND [2] under the assumption that agent j plays s2, agent i can do no better than playing s1.
Nash equilibrium 解法图示
(2) Pareto optimal
if there is no other outcome that makes one agent better off without making another agent worse off.
Pareto optimal 解法图示
(3) social welfare
social welfare 解法图示
5 Coalition games [WEEK 10 Coalition,Voting, Power, and Computational Social Choice]
the core is the set of outcomes for the grand coalition to which no coalition objects.
a coalition C objects to an outcome if there is some outcome for them that makes all of them strictly better off.
if the core is non-empty then the grand coalition is stable, since nobody can benefit from defection.
(1) Shapley value (- best known attempt to define how to divide the benefits of cooperation fairly, taking into account the contributions of each agent)
Shapley value definition
Example
(2) Representing coalition games
1-Induced subgraph
2-Marginal contribution nets
6 voting [WEEK 11 Social Choice]
(1) Plurality vote
the winner is C
(2) Sequential majority elections
the winner is ? at the root
(3) Majority Graph (Pairwise election)
the edge points from w to w' if a majority of voters rank w above w'
given the above votes
candidate C has the most victories wins
* A Condorcet Winner is a candidate that would beat every other candidate in a pairwise election.
(4) Borda count
assign points for each altermative
sum the points and the alternative with the highest total wins, B is the winner
7 Auction [WEEK 11 Reaching agreement]
(1) English
Each bidder raises freely his bid (in public), auction ends if no bidder is willing to raise his bid anymore
(2) Dutch = First-price sealed bid
Dutch (descending) auction: seller continuously lowers prices until one of the bidders accepts the price
(3) First-price sealed bid = Dutch
bidders submit bids so that only auctioneer can see them, highest bid wins (only one round of bidding)
(4) Vickrey
Second-price sealed bid: Highest bidder wins, but pays price of second-highest bid
English and Vickrey: some collusion agreements are self-enforcing.
none of them is fully collusion proof.
8 Working together [WEEK 12]
(1) contract net
1-recognition
2-announcement
3-bidding
4-awarding
5-expediting
(2) CDPS -cooperative distributed problem solving
1-problem decomposition
2-sub-problem distribution
3-sub-problem solution
4-answer synthesis
网友评论