集合行為の効率性と公平性

1、The Design of Desired Collectives with Multi-Agent Simulation,Akira Namatame Dept. of Computer Science National Defense Academy, Japan namanda.ac.jp,2,Collectives of Interacting Agents,Collective of interacting agents is complex with the following properties: (1) Non-linearity and path-dependency (2

2、) Self-organization (3) Emergence (4) Unintended consequence,We propose the approach of designing desired collectives with the agent-based simulation,3,preference,interest,goal,Agent,Collective,Agents Behavior Based on the Logic of Minority, Agents gain if they take the same action as minority does.

3、,(1) Purposive decision Decision based on preference or interest (2) Contingent decision Decision based on what others are doing,4,Highlights of The Talk, Characterize the inverse and forward problems to self-organize desired collectives Propose the interactive design with multi-agent simulation.,5,

4、Logic of Minority: Symmetric Problem (1),At each time step,agents make a binary choice : Agents on the minority side get more payoffs than those who are the majority side.,Minority games El Farol bar problem,U(S1)=a(1-n/N) U(S2)=b(n/N),6,Logic of Minority: Asymmetric Problems,Congestion problem,Mark

5、et entry games,Market,S1 : use a car S2 : use a train,payoff=benefit - time,7,Reasons for Undesirable Outcomes, (1) Bounded rationality of agents (2) Inconsistency between individual rationality and group rationality (1) Agents behave with false rules How do agents learn desirable rules? (2) Agents

6、behave with inappropriate utility functions. How do agent should modify their own utility functions?,8,Symmetric Problem vs. Asymmetric Problem,U(S1)= U(S2),(1) Nash equilibrium:,(2) Pareto optimal:,Average utility E=pU(S1)+(1-p)U(S2) =(a+b)(p-p2) Average utility is maximized at p=0.5,Average utilit

7、y is maximized,Average utility E=pU(S1)+(1-p)U(S2) =a(p-p2)+b Average utility is maximized at p=a/2(a+b),9,Decomposition to Pair-wise Problems,U(S1)= a(1-n/N) U(S2)= b(n/N),(1) Symmetric problem,(2)Asymmetric problem,U(S1)= a(1-n/N) U(S2)= b,q=a/(a+b),1-q,10,Desirable Collective: Stability, Efficien

8、cy, Fairness,Stability: Desirable collective need to be equilibrium of underlying games Efficiency: Desirable collective need to be efficient of underlying games Fairness Since there are many equilibria, the criteria of stability and efficiency are not enough, and fairness is evolutions solution to

9、the equilibrium selection problem,11,Characterization of Learning Models,(1) Learning models without coupling with others Reinforcement learning Agents reinforce the strategy which gains the payoff Evolutionary learning Agents evolve strategy of interaction (2) Learning models with coupling Best-res

10、ponse learning Agents adapt based on the best-response strategy,12,Agents Make Choices without Coupling,There is no coupling,agent has several randomly generated strategies of memory m. A each step, the player uses the strategy that would have maximized its gains over the entire history.,Most common

11、 learning model in minority games,13,Coupling of Agents,(1) Coupling with collectives (2) Coupling with neighbors,14,Coupling Rule between Two,Agents make choice based on the past two history,Coupling rule between agents,15,The Performances of Evolutional Learning,Noise=0%,Noise=5%,Max,Min,Ave,Max,M

12、in,Ave,16,What Agents Acquired with Evolutinary Learning ?,400 agents with different rules at the beginning evolved to share one of 15 coupling rules.,The number of agents,17,Commonality of Acquired Rules,The 15 meta-rules shared by all agents have the commonality,18,Coupling with Local Neighbors,S1

13、,: The proportion of neighbors to choose,The behavioral rule as give-and-tale,19,Simulation Results,Efficient and equitable dynamic orders are emerged with give-and-take,S1,S2,20,Coupling Agents with Collectives,(1)The action variable of agent Ai , a1(t) = 1 : S1 (Go) a1(t) = 0 : S2 (Stay) (2)The St

14、atus of the Bar,The bar is crowded at time t,The bar is not crowded at time t,(3) Rules of give-and-take,If gain, then yields, if no gain, chooses randomly,21,Simulation Results （=0.5）,Blue line;S1, Red line;S2,All agents choose Nash strategies,Payoff distribution,Give & Take Learning,22,Efficient U

15、tilization of Limited Resource with Too Many Contestants,Market entry games El Farol bar problem,The capacity of resource: q The capacity of resource: q/2,How limited resource is maximally utilized under an efficient and equitable situation?,Payoff,23,How to Solve Inverse Problem?,(1)Design right be

16、havioral rules Interacting agents need to develop right behavioral rules for desirable collectives (2) Design right utility functions Agents need to modify their endogenous utility functions for desirable collectives.,24,Exogenous Design with Subsidy or Tax,How should utility functions be redesigned

17、 with subsidy or tax?,Payoff,U(S1)=1-n/N U(S2)=1-q,U(S1)=1-n/N (n/N)q/(2-q),(n/N)q/(2-q): Tax,Nash equilibrium: n/N=q Pareto-optimal: n/N= q/2,U(S2)=1-q + q/2,q/2: Subsidy,25,Endogenous Design with Give&Take,The capacity of resource (bar) : Nq,(Case 2) Agents who chose S1(enter), choose S2(stay) A p

18、art of agents who chose S2(stay) choose S2(stay) again,The number of agent who stayed at time t,(Case 1) Agents who chose S2(Stay), choose S1(Enter) A part of agents who chose S1(Enter), choose S1(Enter) again.,26,Solving Inverse Problems with Agent-based Simulation (ABS),Evolutionary Design with Agent-Based Simulation,27,Conclusion: Achieving Desired Collectives,We showed that collective behavior with the logic of minority is much