You selected price.pl
me( 'market with indivisibilities by prolog'
, 'with an introductory reading and references.'
, 'price01.pl (developed on SWI-prolog 5.0.9)'
, '2005.8.19-9.10;19-26,28;10.7 17:25 pm'
, 'By Kenryo INDO (Kanto Gakuen University)'
).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% preface
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CAUTION!! This system comes with absolutely no warranty.
% Theoretical misunderstanding or bugs of programming may remain.
% It is not intended that this code used for any practical or
% serious purposes, but for the individual study.
% Execuse me for my poor English.
% revision (2005.9.18-19.)
% 1. The title has changed appropriately to the contents.
% 2. Correction. solve_wep_1/2 (and f/3, k/4, k_N/3) to reflect d_star/3,
% the minimal demand correspondence.
% 3. Revision. preference analysis sections, models and tools.
% 4. Correction. utilities for job_matching_1 and job_matching_2 (u(k,[1]) and u(k,[3])).
% revision (2005.9.20-25.)
% 5. Extention. game analysis with utility or disutility of co-workers.
% revision (2005.9.26.)
% 6. Modification. pp/2 by adding warn_user_if_no_p_slant_2_clause/0.
% 7. Correct. Paragraph above. And a reference [21].
% revision (2005.10.7.)
% 8. Correct. the title of this section, some sentences below, and a reference [6].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% model base
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% For the setting models in this system the reader is
% referred to `model management tool' section below
% by text search with a word `(MMT).'
% Example. A unit demand case of job assignment market game in Leonard(1983).
model( assign_1, agents:[firm,worker_1,worker_2], items:[job_a,job_b],
'owner of unsold item': firm, % a dummy firm
endowments:[
e(firm,0,[job_a,job_b]),
e(worker_1,0,[]),
e(worker_2,0,[])
],
utilities:[
u(firm,_)=0,
u(worker_1,[job_a])=12,
u(worker_1,[job_b])=7,
u(worker_1,[job_a, job_b])=12,
u(worker_2,[job_a])=11,
u(worker_2,[job_b])=4,
u(worker_2,[job_a, job_b])=11]
).
% Note: If u(worker_1,[job_a, job_b])=12+e,e>0 or
% u(worker_2,[job_a, job_b])=11+f,f>0 then
% the minimal equilibrium price does not equal
% the incentive compatible payments for each purchased item.
% See also the game analysis section below.
% Example. A unit demand case of job assignment market game in Leonard(1983).
model( assign_2,
agents:[firm(a),firm(b),worker(1),worker(2)],
items:[job_a,job_b],
'owner of unsold item': firm(_), % a dummy firm
endowments:[
e(firm(a),0,[job_a]),
e(firm(b),0,[job_b]),
e(worker(1),0,[]),
e(worker(2),0,[])
],
utilities:[
u(firm(_),_)=0,
u(worker(1),[job_a])=12,
u(worker(1),[job_b])=7,
u(worker(1),[job_a, job_b])=12,
u(worker(2),[job_a])=11,
u(worker(2),[job_b])=4,
u(worker(2),[job_a, job_b])=11]
).
% Example. The parametric unit demand job assignment.
model( assign_0(X), agents:[firm,worker_1,worker_2], items:[job_a,job_b],
'owner of unsold item': firm, % a dummy firm
endowments:[
e(firm,0,[job_a,job_b]),
e(worker_1,0,[]),
e(worker_2,0,[])
],
utilities:[
u(firm,_)=0,
u(worker_1,[job_a])=U1,
u(worker_1,[job_b])=U2,
u(worker_1,[job_a, job_b])=U3,
u(worker_2,[job_a])=U4,
u(worker_2,[job_b])=U5,
u(worker_2,[job_a, job_b])=U6]
):-
X=[A,U1,U2,U3,U4,U5,U6],
positive_number(10,2,U1),
positive_number(10,2,U2),
positive_number(10,2,U3),
positive_number(10,2,U4),
positive_number(10,2,U5),
positive_number(10,2,U6),
(A == repeat ->true ; A= cut, !).
% Example. Gul and Stacchetti(2000).
model( auction_1, agents:[i,j,k], items:[a,b],
'owner of unsold item': i,
endowments:[e(i,0,[a,b]),e(j,0,[]),e(k,0,[])],
utilities:[
u(i,_)=0,
u(j,[a])=8,
u(j,[b])=9,
u(j,[a, b])=12,
u(k,[a])=6,
u(k,[b])=8,
u(k,[a, b])=14]
).
% k-replica economy with k(=#I+1=3) times copied for I and N.
model( auction_1_r3,
agents:[i,j(1),k(1),j(2),k(2),j(3),k(3)],
items:ITEMS,
'owner of unsold item': i,
endowments:[
e(i,0,[a(1),a(2),a(3),b(1),b(2),b(3)]),
e(j(1),0,[]),
e(k(1),0,[]),
e(j(2),0,[]),
e(k(2),0,[]),
e(j(3),0,[]),
e(k(3),0,[])
],
utilities:[ u(i,_)=0 | ReplicaUtilities ]
):-
ITEMS =[a(1),b(1),a(2),b(2),a(3),b(3)],
findall( u(J,B)=V,
(
subset_of(B,_,ITEMS),
member(R,[1,2,3]),
member(J,[j(R),k(R)]),
intersection(B,[a(_),b(_)],Br),
% Br \=[],
(Br=[]->V=0;true),
(J=j(R),Br=[a(_)]->V=8;true),
(J=j(R),Br=[b(_)]->V=9;true),
(J=j(R),Br=[a(_),b(_)]->V=12;true),
(J=k(R),Br=[a(_)]->V=6;true),
(J=k(R),Br=[b(_)]->V=8;true),
(J=k(R),Br=[a(_),b(_)]->V=14;true)
),
ReplicaUtilities ).
/*
?- intersection([b(1),a(1),a(2)],[a(_),b(_)],B).
B = [b(1), a(1)] ;
*/
% Example in the proof of theorem 6 of Gul and Stacchetti(2000).
model( auction_2(X,Y), agents:[0,1,2,3], items:[a,b,c,d],
'owner of unsold item': 0,
endowments:[e(0,0,[a,b,c,d]),e(1,0,[]),e(2,0,[]),e(3,0,[])],
utilities:Utilities
):-
UBOX=[
([],0,0,0),
([a],8,6,Y),
([b],8,6,0),
([c],8,X,6),
([d],8,0,6),
([a, b],9,12,Y),
([a, c],16,6,6),
([b, d],16,6,6),
([c, d],9,X,12)
],
member(X,[1,2,3]),
member(Y,[1,2,3]),
ITEMS =[a,b,c,d],
findall( u(J,B)=V,
(
subset_of(B,_,ITEMS),
member(J,[1,2,3]),
intersection(B,[a,b],BR1),
intersection(B,[c,d],BR2),
intersection(B,[a,c],BC1),
intersection(B,[b,d],BC2),
(J=1->member((BR1,V1,_,_),UBOX);true),
(J=2->member((BC1,_,V1,_),UBOX);true),
(J=3->member((BC1,_,_,V1),UBOX);true),
(J=1->member((BR2,V2,_,_),UBOX);true),
(J=2->member((BC2,_,V2,_),UBOX);true),
(J=3->member((BC2,_,_,V2),UBOX);true),
V is V1 +V2
),
Utilities ).
% Example in Bikichandani et al.(2002), Table 1.
model( auction_3, agents:[0,1,2,3], items:[a,b,c,d],
'owner of unsold item': 0,
endowments:[e(0,0,[a,b,c,d]),e(1,0,[]),e(2,0,[]),e(3,0,[])],
utilities:Utilities
):-
UBOX=[
([],[0,0,0]),
([a],[10,4,2]),
([b],[10,7,2]),
([c],[10,9,2]),
([d],[10,8,4])
],
ITEMS =[a,b,c,d],
findall( u(J,B)=V,
(
subset_of(B,_,ITEMS),
member(J,[1,2,3]),
intersection(B,[X,Y],BR1),
(BR1=[X]
-> (member(([X],U123),UBOX),
nth1(J,U123,V)
)
;true
),
(BR1=[_,_|_]
->
max(U,(
subset_of([X,Y],2,BR1),
member(([X],U123),UBOX),
nth1(J,U123,V1),
member(([Y],U123),UBOX),
nth1(J,U123,V2),
U is V1 + V2
))
;true
)
),
Utilities ).
% demo (preview)
/*
?- set_model(auction_3),coalition(S1),
agents_are_substitutes(_:S1,T,false,_:([B|_],[_|E])).
S1 = []
T = 23-0>=27
B = 23
E = [27, [4, 10, 9, 4]]
No
?-
*/
% a parameterized job matching problem:
% Kelso and Crawford(1982), also see Ma(1998).
% workers: 1,2,3
% firms: i(=dummy),j,k
model(job_matching_1([E,E1,E2]),
agents:[i,j,k],
items:[1,2,3],
'owner of unsold item': i,
endowments:[e(i,0,[1,2,3]),e(j,0,[]),e(k,0,[])],
utilities:[
u(i,_)=0,
u(j,[1])=4,
u(j,[2])=4,
u(j,[3])=4+E1,
u(j,[1,2])=7+E,
u(j,[1,3])=7,
u(j,[2,3])=7,
u(j,[1,2,3])=9,
u(k,[1])=4+E2,
u(k,[2])=4,
u(k,[3])=4,
u(k,[1,2])=7,
u(k,[1,3])=7,
u(k,[2,3])=7+E,
u(k,[1,2,3])=9]
):-
% perturbations of utilities.
P = 0.25,
change_precision(P),
nonnegative_number([0,3],P,E1),
nonnegative_number([0,3],P,E2),
nonnegative_number([0,1],P,E).
% another form of the job matching:
% Kelso and Crawford(1982), also see Ma(1998).
% workers: 1,2,3
% firms: i1,i2,i3(=dummies),j,k
model(job_matching_2([E,E1,E2]),
agents:[i1,i2,i3,j,k],
items:[1,2,3],
'owner of unsold item': i1, % also i2 and i3
endowments:[
e(i1,0,[1]),
e(i2,0,[2]),
e(i3,0,[3]),
e(j,0,[]),
e(k,0,[])],
utilities:[
u(i1,_)=0,
u(i2,_)=0,
u(i3,_)=0,
u(j,[1])=4,
u(j,[2])=4,
u(j,[3])=4+E1,
u(j,[1,2])=7+E,
u(j,[1,3])=7,
u(j,[2,3])=7,
u(j,[1,2,3])=9,
u(k,[1])=4+E2,
u(k,[2])=4,
u(k,[3])=4,
u(k,[1,2])=7,
u(k,[1,3])=7,
u(k,[2,3])=7+E,
u(k,[1,2,3])=9]
):-
% perturbations of utilities.
P = 0.25,
change_precision(P),
nonnegative_number([0,3],P,E1),
nonnegative_number([0,3],P,E2),
nonnegative_number([0,1],P,E).
% precision ==> MMT
nonnegative_number([L,_],_,L).
nonnegative_number([L,U],P,N):-
D is U -L,
positive_number(D,P,M),
N is L + M.
% about positive_number/3, see numerical tools
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% model of economy : money and exchange
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% x: allocation of items (agent-oriented)
% e: initially endowed
% Both above are collections of tuple, (agent, money, items), over agents.
% a: allocation of item (item-oriented)
% o: initial owner of item
% t: transfers of an item, t:e->x
% p: market price. pp: price vector.
% c: cost/value of payment under the price c(p,x)=
% u: utility function (see sections `model base' and `model management')
%%%%
:- dynamic e/3, x/3, p/2.
% a preset for auction_1
%-----------------------------------------
/*
e( i, 0, [a,b]).
e( j, 1000, []).
e( k, 1000, []).
x( i, 1300, []).
x( j, 400, [a]).
x( k, 300, [b]).
p( a, 600).
p( b, 700).
*/
% a preset for job_match_1
%-----------------------------------------
/*
e( i, 0, [1,2,3]).
e( j, 1000, []).
e( k, 1000, []).
x( i, 1700, []).
x( j, 100, [1]).
x( k, 200, [2,3]).
p( 1, 900).
p( 2, 300).
p( 3, 500).
*/
% a preset for auction_1_r3
%-----------------------------------------
/*
e( i, 0, [a(1),b(1),a(2),b(2),a(3),b(3)]).
e( j(R), 1000, []):- member(R,[1,2,3]).
e( k(R), 1000, []):- member(R,[1,2,3]).
x( i(R), 1300, []):- member(R,[1,2,3]).
x( j(R), 400, [a(R)]):- member(R,[1,2,3]).
x( k(R), 300, [b(R)]):- member(R,[1,2,3]).
p( a(R), 600):- member(R,[1,2,3]).
p( b(R), 700):- member(R,[1,2,3]).
*/
% profiles
%-----------------------------------------
% revised: 26 Sep 2005 (added warn_user_if_no_p_slant_2_clause/0)
pp(PP):-
warn_user_if_no_p_slant_2_clause,
set_of_all_items(O),pp0(O,PP).
pp0([],[]).
pp0([X|O],[(X->P)|Q]):- pp0(O,Q),p(X,P).
warn_user_if_no_p_slant_2_clause:-
clause( p(_,_),_),
!.
warn_user_if_no_p_slant_2_clause:-
\+ clause( p(_,_),_) ,
!,
nl,
write( ' I looked for some p/2s, but there was none asserted. '),
nl,
write( ' Would you let zero prices?. (y/n)>'),
read(U),
(U=y->set_0_prices; fail).
% revised: 20 Sep 2005
bundle( A):-
bundle( A,_,_).
bundle( A,Ia,L):-
set_of_all_items( O),
list_projection( Ia,O,A),
length( A, L).
% an earlier code (abolish)
% bundle(A):- var(A),set_of_all_items(O),subset_of(A,_,O).
% bundle(A):- \+ var(A),set_of_all_items(O),subset(A,O).
o(Item -> Owner):- e(Owner,_, E), member(Item, E).
a(Item -> Owner):- x(Owner,_, X), member(Item, X).
xx(XX):- findall((O->J),a(O->J),XX).
% free disposal (with u(O,A)=0 forall items A)
%-----------------------------------------
% dependency: owner_of_unsold_items/1.
unsold_items( X0):- owner_of_unsold_items( J0), x( J0, _, X0).
unsold_item( A):- unsold_items( X0), member(A, X0).
% cost/wealth analysis
%-----------------------------------------
c(P,A,C):-
(var(P)->pp(P);true),
(var(A)->bundle(A);true),
c_0(P,A,C).
c_0(_,[],0).
c_0(P,[A|B],C):-
c_0(P,B,D),
member((A->Pa),P),
C is D + Pa.
% demo
%-----------------------------------------
/*
?- c(P,[1,2,3],Q).
P = [900, 300, 500]
Q = 1700 ;
No
?- c(P,[1,3],Q).
P = [900, 500]
Q = 1400
Yes
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% a simulation of trading
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
t(1,i->j).
t(2,i->k).
t(3,i->k).
tt(TT):- findall((O,T),t(O,T),TT).
tJget(J,TT):- T=(J->_),findall((O,T),t(O,T),TT).
tJput(J,TT):- T=(_->J),findall((O,T),t(O,T),TT).
% a naiive simulation of trade process
%-----------------------------------------
:- dynamic temp_x/3, temp_t/2.
go_t:-
initialize_t_x,
fail.
go_t:-
temp_t( not_yet, T ),
T = [_O,I->J],
transaction_data( T, Tid, S_Data, B_Data ),
retract( temp_t(not_yet, T) ),
Tid1 is Tid + 1,
assert( temp_t(done(t=Tid1), T) ),
update_allocation_for_buyer( Tid, J, B_Data ),
update_allocation_for_seller( Tid, I, S_Data ),
fail.
go_t:-
finalize_t_x.
initialize_t_x:-
abolish( temp_x/3 ),
abolish( temp_t/2 ),
C1 = temp_x( 0, (I,M,E), [] ),
C2 = temp_t(not_yet, [O,I->J]),
forall( e(I,M,E), assert(C1) ),
forall( t(O,I->J), assert(C2) ).
transaction_data([O,I->J], Tid, S_Data, B_Data):-
temp_x(Tid, (I,Wi,Ei), Hi),
temp_x(Tid, (J,Wj,Ej), Hj),
check_feasibility(O,_Po,[Ei,Ej,Wi,Wj],[Wi1,Wj1]),
append(Ej,[O],Ej1),
subtract(Ei,[O],Ei1),
Tid1 is Tid + 1,
S_Data = [Tid1, (I, Wi1, Ei1), [(O,to(J))|Hi]],
B_Data = [Tid1, (J, Wj1, Ej1), [(O,from(I))|Hj]],
!.
check_feasibility(O,P,[Ei,_Ej,Wi,Wj],[Wi1,Wj1]):-
member(O, Ei),
p(O, P),
Wi1 is Wi + P,
Wj1 is Wj - P.
% Wj1 >=0.
update_allocation_for_buyer(Tid, J, B_Data):-
retract(temp_x(Tid, (J,_,_), _)),
CB =.. [temp_x|B_Data],
assert(CB),
!.
update_allocation_for_seller(Tid, I, S_Data):-
retract(temp_x(Tid, (I,_,_), _)),
SB =.. [temp_x|S_Data],
assert(SB),
!.
finalize_t_x:-
write( complete ),
listing( temp_t ),
listing( temp_x ).
% demo
%-----------------------------------------
/*
?- go_t.
complete
:- dynamic temp_t/1.
:- dynamic temp_t/2.
temp_t(done(t=1), [1, (i->j)]).
temp_t(done(t=1), [2, (i->k)]).
temp_t(done(t=2), [3, (i->k)]).
:- dynamic temp_x/3.
temp_x(0, (j, 0, []), []).
temp_x(0, (k, 0, []), []).
temp_x(1, (j, 100, [1]), [ (1, from(i))]).
temp_x(1, (i, 300, [1, 3]), [ (2, to(k))]).
temp_x(2, (k, 200, [2, 3]), [ (3, from(i)), (2, from(i))]).
temp_x(2, (i, 1400, [2]), [ (3, to(k)), (1, to(j))]).
Yes
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% competitive equilibrium
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vt: trading profit function (characteristic function, the value of asset)
% d: demand correspomdence
% wep: competitive equilibrium and the price (Walrasian equilibrium / price)
% xds: excess demand set
%%%%
:- dynamic utility_scale/1.
utility_scale(100).
% trading profit function
%-----------------------------------------
vt(J,A,P,V):-
vt(J,A,P,_,V).
vt(J,A,P,W1+W2=W,V):-
(var(P)->pp(P);true),
u(J,A,U),
c(P,A,C),
e(J,W1,O),
c(P,O,W2),
W is W1 + W2,
utility_scale( H),
V is H * U + W - C.
% demand correspondence
%-----------------------------------------
d(J,P,D):-
agent(J),
pp(P),
setof(A,
max(V,vt(J,A,P,V)),
D).
dd(W):-
findall(J->D, d(J,_,D),W).
% minimal demand correspondence
%-----------------------------------------
% to be used for computing auction prices.
d_star(J,P,D_star):-
agent(J),
% pp(P),
MLen = (member(A,D),length(A,K)),
setof(A,
min( K, (d(J,P,D),MLen) ),
D_star).
% competitive equilibrium
%-----------------------------------------
% def. (p,X) is Walrasian ( competitive) equilibrium
% if allocation X consists of Xi in the demand set Di
% for each agent ( and =0)
wep(P, Y):-
pp(P),
feasible_allocation(Y),
wep_0(P,Y),
complementarity_condition.
wep_0(_,[]).
wep_0(P,[A->J|Y]):-
wep_0(P,Y),
d(J,P,Dj),
member(A,Dj).
complementarity_condition:-
sumall(P,(unsold_item(A),p(A,P)),0).
% feasible allocation (i.e., partition of items)
%-----------------------------------------
feasible_allocation(X):-
feasible_allocation(_,_,X).
feasible_allocation(N,O,Y):-
set_of_all_agents(N),
set_of_all_items(O),
feasible_allocation_0(item,N,O,X),
transform_into_allocation( X, Y).
feasible_allocation_0(_,_,[],[]).
feasible_allocation_0(item,I,[A|O],[A->J|X]):-
feasible_allocation_0(item,I,O,X),
item(A),
agent(J),
member(J,I).
transform_into_allocation( X, Y):-
findall(Xj->J,
(
agent(J),
findall(A, member(A->J,X), Xj)
),
Y).
% display only nonempty assignments given a feasible allocation.
%-----------------------------------------
% It may be a help, despite current uses of this rule
% occurs only in extended game analysis later.
nonempty_assignments(Y->Ya):-
forall( member(X,Y), (\+ var(X),X=(_->_))),
findall(A,
(
member(A,Y),
A \= ([]->_)
),
Ya).
% support
%-----------------------------------------
% (p,X) is equilibrium iff p supports X and =0
wep_1(P, X):-
price_supports_allocation( P, X),
complementarity_condition.
out_of_demand_set_at_price( P, I, Xi, Di):-
x(I, _, Xi),
d(I, P, Di),
\+ member( Xi, Di).
price_supports_allocation( P, X):-
\+ out_of_demand_set_at_price( P, _I, _Xi, _Di),
pp(P),
xx(X).
price_supports_bundle( P, X):-
bundle(A),
price_supports_allocation( P, X),
unsold_items( X0),
set_of_all_items( OX),
subtract( OX, A, Ac),
set_equivalent( X0, Ac).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% excess demand
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The key block for updating prices in dynamic auctions.
% Gul and Stacchetti(2000) developed the algorithm
% based on matroid theory.
% revised: 18-19 Sep 2005
% requirement function
%-----------------------------------------
% dual rank function, k(=ro^#), in matroid theory,
% if the SI property has satisfied.
% k is bounded, monotone, and supermodular.
k( J, B, P, K):-
bundle(B),
d( J, P, Dp),
min( K,
(
member(A, Dp),
intersection(A,B,C),
length(C,K)
)
),
!.
k_star( J, B, P, K):-
bundle(B),
d_star( J, P, Dp),
min( K,
(
member(A, Dp),
intersection(A,B,C),
length(C,K)
)
),
!.
k_N( B, P, KN):-
bundle(B),
pp(P),
sumall(K, (agent(J),k( J, B, P, K)), KN).
k_star_N( B, P, KN):-
bundle(B),
pp(P),
sumall(K, (agent(J),k_star( J, B, P, K)), KN).
% demanded bundles
%-----------------------------------------
:- dynamic f/3.
f_1( A, P, F):-
k_N( A, P, KN),
length(A, L),
F is KN -L.
f( A, P, F):-
k_star_N( A, P, KN),
length(A, L),
F is KN -L.
% By the Corollary of Theorem 3 of Gull & Stacchetti(2000),
% wep(P, _) -> f(A) =< 0 forall bundle A.
% ch_f/1: change f -> f1 or vice versa (recover f).
% => see MMT section.
% max-demanded bundles at prices p
%-----------------------------------------
% the collection of max-demaded O is a lattice for each P.
% (Lemma 5 of Gull & Stacchetti(2000), p.76.)
max_demanded_bundle( P, A :F):-
max(F, f( A, P, F)).
% excess demand set (over-demanded items)
%-----------------------------------------
% the smallest element of the lattice is called
% the `excess demand set.'
xds( P, B : F):-
excess_demand_set( P, B : F).
excess_demand_set( P, B : F):-
min(K,
(
max_demanded_bundle( P, A : F),
length( A, K)
)
),
B = A.
excess_demand_item(P,A):-
item(A),
excess_demand_set( P, B : _F),
member(A, B).
show_excess_demand_items:-
pp(P),
nl,
write(prices:P:' excess demand set: '),
forall(excess_demand_set(_P,O:_),
(
write( O)
)
).
% another correspondence in the proof
%-----------------------------------------
% added: 19 Sep 2005
% member(A, D_hat(p)) -> member(C,D(p)), subset(C,A).
% (Lemma 1 of GS00, p.72)
d_hat(J,P,D_hat):-
agent(J),
pp(P),
MLen = (intersection(A,B,C),length(C,L)),
setof(A,
(
bundle(A),
forall(
bundle(B),
(k(J,B, P,K),MLen, L >= K )
)
),
D_hat).
% a test for the requirement function
%-----------------------------------------
/*
?- set_model(job_matching_1([0.5,1,0])).
Yes
?- ch_f(A).
A = use:f1
Yes
?- solve_wep_1(P,Y).
init p:[ (1->0), (2->0), (3->0)];xds:[1, 2, 3]
p:[ (1->150), (2->150), (3->150)];xds:[1, 2, 3]->[2]
p:[ (1->150), (2->200), (3->150)];xds:[2]->[1, 2, 3]
p:[ (1->200), (2->250), (3->200)];xds:[1, 2, 3]->[]
I can`t update prices, because
there is no excess demand item.
P = [ (1->200), (2->250), (3->200)]
Y = _G158
Yes
?- display_goals((agent(J),bundle(B),k(J,B,P,K),
k_star(J,B,P,K1),K1\=K)).
agent(j), bundle([3]), k(j, [3], [ (1->200), (2->250), (3->200)], 0),
k_star(j, [3], [ (1->200), (2->250), (3->200)], 1), 1\=0
J = _G160
B = _G162
P = _G166
K = _G167
K1 = _G172
Yes
?- display_goals(d(_,_,_)).
d(i, [ (1->200), (2->250), (3->200)], [[]])
d(j, [ (1->200), (2->250), (3->200)], [[1, 2], [1, 3], [3]])
d(k, [ (1->200), (2->250), (3->200)], [[1, 3], [2, 3]])
Yes
?- display_goals(d_star(_,_,_)).
d_star(i, [ (1->200), (2->250), (3->200)], [[]])
d_star(j, [ (1->200), (2->250), (3->200)], [[3]])
d_star(k, [ (1->200), (2->250), (3->200)], [[1, 3], [2, 3]])
Yes
?- display_goals(d_hat(_,_,_)).
d_hat(i, [ (1->200), (2->250), (3->200)], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]])
d_hat(j, [ (1->200), (2->250), (3->200)], [[1, 2], [1, 2, 3], [1, 3], [2, 3], [3]])
d_hat(k, [ (1->200), (2->250), (3->200)], [[1, 2, 3], [1, 3], [2, 3]])
Yes
?- display_goals(vt(j,_,_,_)).
vt(j, [3], [ (1->200), (2->250), (3->200)], 300)
vt(j, [2], [ (1->200), (2->250), (3->200)], 150)
vt(j, [2, 3], [ (1->200), (2->250), (3->200)], 250)
vt(j, [1], [ (1->200), (2->250), (3->200)], 200)
vt(j, [1, 3], [ (1->200), (2->250), (3->200)], 300)
vt(j, [1, 2], [ (1->200), (2->250), (3->200)], 300)
vt(j, [1, 2, 3], [ (1->200), (2->250), (3->200)], 250)
vt(j, [], [ (1->200), (2->250), (3->200)], 0)
Yes
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% a solver for equilibrium
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% See last section and references.
% a naive wep-solver
%-----------------------------------------
% backtrack with `price revision tools' below.
solve_wep(P, Y):-
generate_price_vector(P),
wep(P, Y).
tell_solve_wep:-
tell_goal('solve_wep.txt',
display_goals(solve_wep_0(P, Y),[P:Y])
),
fail.
tell_solve_wep:-
current_stream('solve_wep.txt',write,S),
close(S).
% demo
%-----------------------------------------
% In this example, the minimal (smallest) Walrasian price is,
% p_min = (6,7).
% And the corrsponding efficient allocation X is
% X =([a]->j;[b]->k),
% both consists the equilibrium, (p,X).
% As experimental data shown below, the (discrete)
% Warlasian price vectors forms a triangular region
% consists of the grid points whose vertices are
% (6,6), (6,7), and (7,7)
% in (Pa,Pb) of the two dimensional coordinates.
/*
% file output start time , [date(2005/8/26), time(22:49:45)]
%---------- start from here ------------%
[ (a->600), (b->700)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->600), (b->710)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->610), (b->710)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->600), (b->720)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->610), (b->720)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->620), (b->720)]:[ ([]->i), ([a]->j), ([b]->k)];
(...)
[ (a->690), (b->790)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->600), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->610), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->620), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->630), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->640), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->650), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->660), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->670), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->680), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->690), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
[ (a->700), (b->800)]:[ ([]->i), ([a]->j), ([b]->k)];
*/
% a wep-solver with simple stopping rule
%-----------------------------------------
% Stop1 <= true : if find a wep then stop.
% Stop1 <= fail : continue search totally.
% Stop2 <= fail : continuation.
% Stop2 <= (C->true;fail) : certain truncation rule.
solve_wep(P, Y, Stop1, Stop2):-
generate_price_vector(P),
(wep(P, Y)
->(nl,write(P:Y:'equilibrium!'),Stop1)
; (nl,write(P:'fail'),Stop2)
).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% auction as solver for equilibrium
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% solve_wep_1/2.
% the ascending auction based wep-solver
%-----------------------------------------
% The code below implements the `English auction game'
% algorithm by Gull & Stacchetti(2000). This can be explained
% as a primal-dual algorithm (See Bikhchandani et al., 2002).
% bugfix. (18 Sep 2005) solve_wep_1/2. simplified the stopping rule.
% bugfix. (19 Sep 2005 6:47am-- 22:00pm) model: job_matching_1(E).
% You can try out an earlier version of the rule
% by means of ch_f/1 => See MMT section.
% On revisoning for solve_wep_1/2
%-----------------------------------------
% phenomena.
% E=[0.25,0,0],[0.75,0,0],[0.25,0.25,0]
% ... were the cases of anomal termination.
% A wep/2 used in advance of the stopping rule in earlier
% version causes them.
% diagnosis.
% The problem accompanied with the code for excess demand set
% (xds) and function k, f, and so on.
% The bidding process stops only when the xds become empty,
% even if not yet an equilibrium. But a failure of preceeding
% wep/2 may deter it, so does not terminate.
% treatment.
% (1) simplification of the stopping rule.
% By means of this, even if not reached an equilibrium,
% the bidding stops when xds become empty.
% (2) using d_star, k_star, f_star instead.
% This avoides the wrong premature stoppings. The right
% cases are of no competitive equilibrium.
% Caveat.(apology)
% The second part of above treatment is NOT
% a literal interpretation of the GS algorithm.
% At the present time of development of code, either
% their lemma 2 or the modeling code seems dubious.
% an outlook of the algorithm.
%-----------------------------------------
% Adjusting prices upwards directed toward in the excess demand set,
% the algorithm has option to stop at T1, the first time when
% a competitive allocation is possible (and the excess demand set
% simultaneously become empty). This means the minimal Walrasian price.
% The algorithm must stop at T, the first time when
% the excess demand set becomes empty.
% The algorithm can compute (minimal) Walrasian prices
% by Theorem 4 of Gull & Stacchetti(2000), p.77.
% Let p(T1) the price at first optional stop time T1 of a EAG,
% and p_we is Walrasian equilibrium price of the game. Then
% p(T1)= min(p_we),
% T1=T.
solve_wep_1( P, Y):-
abolish(p/2),
set_0_prices,
stopping_rule_for_wep( P, Y).
solve_wep_1( P, Y):-
price_revision_on_excess_demand_set(P),
stopping_rule_for_wep( P, Y),
!.
% stopping rules for solve_wep_1
%-----------------------------------------
stopping_rule_for_wep( P, Y):-
wep(P, Y),
nl,
write( ' equilibrium ! ').
stopping_rule_for_wep( P,_):-
\+ excess_demand_item( P,_A),
nl,
nl,
write( 'I can`t update prices, because '),
nl,
write( 'there is no excess demand item. ').
stopping_rule_for_wep(_,_):-
it_has_been_reached_max_prices,
nl,
nl,
write( 'I can`t update prices, because '),
nl,
write( 'of the boundedness of prices.').
it_has_been_reached_max_prices:-
pp(PP),
forall( member(Item->P, PP),
(
max_price( Item, Pmax),
P >= Pmax
)
).
% ex post analysis
%-----------------------------------------
display_revision_data:-
display_recorded_excess_demand_set(t),
display_recorded_demand_set(t).
display_recorded_excess_demand_set(Y):-
(var(Y)->Y=t;true),
Op =(Y=t->O\=O1;true),
forall(
(temp_price_revision(N,[P,O,O1,_]),Op),
(nl,write([N]),write(P:O->O1))
).
display_recorded_demand_set(Y):-
(var(Y)->Y=t;true),
Op =(Y=t->O\=O1;true),
forall(
(temp_price_revision(N,[_P,O,O1,D]),Op),
(nl,write([N]),write(D))
).
recover_prices_recorded(N,P):-
temp_price_revision(N,[P|_]),
generate_price_vector(P).
verify_upper_min_wep(Q,Y):-
temp_price_revision(70,[P|_]),
generate_price_vector(Q),
\+ (member((X->Qx),Q),member((X->Px),P),Px > Qx),
\+ wep(Q,Y).
% demo
%-----------------------------------------
/*
?- set_model(auction_1).
Yes
?- stopwatch(solve_wep_1(P,Y),T).
init p:[ (a->0), (b->0)];xds:[a, b]
p:[ (a->300), (b->300)];xds:[a, b]->[b]
p:[ (a->300), (b->400)];xds:[b]->[a, b]
p:[ (a->600), (b->700)];xds:[a, b]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
% time elapsed (sec): 0.188
P = [ (a->600), (b->700)]
Y = [ ([]->i), ([a]->j), ([b]->k)]
T = 0.188
Yes
?- display_recorded_excess_demand_set(t).
[30][ (a->300), (b->300)]:[a, b]->[b]
[40][ (a->300), (b->400)]:[b]->[a, b]
[70][ (a->600), (b->700)]:[a, b]->[]
Yes
?- display_recorded_demand_set(t).
[30][ (i->[[]]), (j->[[a, b], [b]]), (k->[[a, b]])]
[40][ (i->[[]]), (j->[[a], [a, b], [b]]), (k->[[a, b]])]
[70][ (i->[[]]), (j->[[a], [b]]), (k->[[a, b], [b]])]
Yes
?- dd(I).
I = [ (i->[[]]), (j->[[a], [b]]), (k->[[a, b], [b]])]
Yes
?- display_goals((recover_prices_recorded(N,P),wep(P,Y)),[N:P:Y]).
70:[ (a->600), (b->700)]:[ ([]->i), ([a]->j), ([b]->k)];
No
?-
% p=(6,7) is the minimal competitive price vector in this example.
% (utility scale= x1000)
*/
% no gap condition is satisfied for the
% k-replica economy with k=#I+1 times copied for I and N
% and the extended utility functions.
% (See Gul and Stacchetti(1999), Theorem 9.)
% demo
%-----------------------------------------
% for auction_1_r3 the 3-replica economy of auction_1.
% note: A run below took about 24 minutes (1437.3 sec).
% (Windows XP Pro SP2, Celeron 1.4GHz, 504MB RAM.)
/*
?- set_model(auction_1_r3).
Yes
?- solve_wep_1(P,Y).
init p:[ (a(1)->0), (b(1)->0), (a(2)->0), (b(2)->0), (a(3)->0), (b(3)->0)];xds:[a(1), a(2), a(3), b(1), b(2), b(3)]
p:[ (a(1)->300), (b(1)->300), (a(2)->300), (b(2)->300), (a(3)->300), (b(3)->300)];xds:[a(1), a(2), a(3), b(1), b(2), b(3)]->[b(1), b(2), b(3)]
p:[ (a(1)->300), (b(1)->400), (a(2)->300), (b(2)->400), (a(3)->300), (b(3)->400)];xds:[b(1), b(2), b(3)]->[a(1), a(2), a(3), b(1), b(2), b(3)]
p:[ (a(1)->600), (b(1)->700), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)];xds:[a(1), a(2), a(3), b(1), b(2), b(3)]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
P = [ (a(1)->600), (b(1)->700), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)]
Y = [ ([]->i), ([a(3)]->j(1)), ([b(3)]->k(1)), ([a(2)]->j(2)), ([b(2)]->k(2)), ([a(1)]->j(3)), ([b(1)]->k(3))]
Yes
?- Y = [ ([]->i), ([a(1)]->j(1)), ([b(1)]->k(1)), ([a(2)]->j(2)), ([b(2)]->k(2)), ([a(3)]->j(3)), ([b(3)]->k(3))] ,
P = [ (a(1)->600), (b(1)->700), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)],
display_goals((member((A->J),Y),c(P,A,C),u(J,A,U)),[A->J,c=C,u=U]).
[]->i; c=0; u=0;
[b(1)]->k(1); c=700; u=8;
[a(2)]->j(2); c=600; u=8;
[b(2)]->k(2); c=700; u=8;
[a(3)]->j(3); c=600; u=8;
[b(3)]->k(3); c=700; u=8;
No
?-
*/
% demo
%-----------------------------------------
% job matching model in Kelso and Crawford(1982).
% See also Ma(1998, 2001).
% revised: 19-20 Sep 2005.
% As it has alleged in the literature(Kelso and Crawford,1982),
% that the game model: job_matching_1([0.5,0.25,0.25])
% has no competitive equilibrium.
% The rule solve_wep_1/2, incorporated the EAG algorithm,
% to stop at a price vector below.
/*
?- set_model(job_matching_1([0.5,0.25,0.25])).
Yes
?- solve_wep_1(P,Y).
init p:[ (1->0), (2->0), (3->0)];xds:[1, 2, 3]
p:[ (1->150), (2->150), (3->150)];xds:[1, 2, 3]->[2]
p:[ (1->150), (2->200), (3->150)];xds:[2]->[1, 2, 3]
p:[ (1->280), (2->330), (3->280)];xds:[1, 2, 3]->[]
I can`t update prices, because
there is no excess demand item.
P = [ (1->280), (2->330), (3->280)]
Y = _G161
Yes
?- display_goals(d_star(_,_,_)).
d_star(i, [ (1->280), (2->330), (3->280)], [[]])
d_star(j, [ (1->280), (2->330), (3->280)], [[3]])
d_star(k, [ (1->280), (2->330), (3->280)], [[1]])
Yes
?- display_goals(d(_,_,_)).
d(i, [ (1->280), (2->330), (3->280)], [[]])
d(j, [ (1->280), (2->330), (3->280)], [[3]])
d(k, [ (1->280), (2->330), (3->280)], [[1]])
Yes
?- xds(O,Y).
O = [ (1->280), (2->330), (3->280)]
Y = []:0
Yes
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% price revison tools
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% price adjustment rules for solve_wep_1
%-----------------------------------------
price_revision_on_excess_demand_set(P):-
excess_demand_set(P,O:_),
assert(temp_price_revision(0,[P,O,start])),
nl,write('init p':P;xds:O),
O =[], % exit and exceute the rules of check & stop.
!.
price_revision_on_excess_demand_set(Q):-
repeat,
excess_demand_set(P,Op:_),
Op \= [],
price_increment_for_bundle(Op, 1, P->Q),
excess_demand_set(Q,Oq:_),
dd(D),
record_price_revision([Q,Op,Oq,D]),
warn_user_if_xds_changed(Q,Op,Oq),
Oq \= Op.
warn_user_if_xds_changed(_,Op,Op):-!.
warn_user_if_xds_changed(Q,Op,Oq):-
nl,write(p:Q;xds:Op->Oq).
set_0_prices:-
abolish( p/2),
abolish( temp_price_revision/2),
initialize_uid,
forall( item(X), assert(p(X,0))).
% recorder of revisioning prices / demands
%-----------------------------------------
:- dynamic temp_price_revision/2, temp_uid/1.
record_price_revision(Data):-
update_uid(_->N),
assert(temp_price_revision(N,Data)).
tem_uid(0).
initialize_uid:-
abolish(temp_uid/1),
assert(temp_uid(0)).
update_uid(Prev->Next):-
retract(temp_uid(Prev)),
Next is Prev +1,
assert(temp_uid(Next)).
% another code ( not effective)
%-----------------------------------------
/*
% caution: if you backtrack this,
% cumulative side-effects on your goal stack.
price_revision_on_excess_demand_set_0:-
price_revision_on_excess_demand_set_0(_,_,_, stop).
price_revision_on_excess_demand_set_0([],O,P,Sea):-
excess_demand_set(P,O:_),
(O \= [] ->Sea = continue ; (!,Sea=stop)).
price_revision_on_excess_demand_set_0([Op|X],Oq,Q, Sea) :-
price_revision_on_excess_demand_set_0(X,Op,P, continue),
price_increment_for_bundle(Op, 1, P->Q),
excess_demand_set(Q,Oq:_),
% debug %
nl,write( rev_p_xds(Q;Op->Oq)),
(Oq = Op -> Sea =continue; (!, Sea =stop)).
*/
% possible prices
%-----------------------------------------
:- dynamic max_price/2, min_price/2, price_discretional_step/2.
max_price(_anyItem,1000).
min_price(_,0).
price_incremental_step(_,10).
max_number_of_steps(Item, K):-
max_price(Item,U),
min_price(Item,L),
price_incremental_step(Item,D),
K is int( U-L)/D.
generate_price_vector(P):-
possible_price_vector(P),
abolish(p/2),
forall(
member((X->Px),P),
assert(p(X,Px))
).
possible_price_vector(P):-
set_of_all_items(O),
possible_price_vector_0(O,P).
possible_price_vector_0([],[]).
possible_price_vector_0([X|O],[X->Px|P]):-
possible_price_vector_0(O,P),
possible_price(X,_,Px).
possible_price(X,[L,U],P):-
item(X),
max_price(X,U),
min_price(X,L),
price_incremental_step(X,D),
nonnegative_number([L,U],D,P).
% increasing price by a unit
%-----------------------------------------
price_increment(A, Pa->Pa1):-
price_increment(A, 1, Pa->Pa1).
price_increment(A, K, Pa->Pa1):-
retract( p( A, Pa)),
price_incremental_step( A, Delta),
Pa1 is Pa + K * Delta,
assert( p( A, Pa1)).
price_increment_for_bundle(S, K, P->P1):-
pp(P),
(var(K)->K=1;true),
bundle(S),
forall(member(A,S),
price_increment(A, K, _)
),
pp(P1).
% increasing price other than a subset of the all items
%-----------------------------------------
% (to be used for analyzing the gross substitutes condition.)
% revised: 19 Sep 2005
price_increment_other_than(S, P->Q):-
pp(P),
set_of_all_items(O),
no_less_than_price_vector_0(O,P,Q, S),
generate_price_vector(Q).
no_less_than_price_vector_0([],[], [], []).
no_less_than_price_vector_0([X|O],[X->Px|P],[X->Qx|Q],S1):-
no_less_than_price_vector_0(O,P, Q, S),
possible_price(X,_,Px),
possible_price(X,_,Qx),
Px =< Qx,
( Px=Qx -> S1 =[X|S]; S1=S).
% a naive code ( which will be inefficient depends on the use)
price_increment_other_than_1(S, P->Q):-
price_no_greater_than( P =< Q),
same_price_items( P, Q, S).
same_price_items( P, Q, S):-
intersection( P, Q, MP),
findall( Item, member( (Item-> _), MP), S).
price_no_greater_than( P =< Q):-
possible_price_vector(P),
possible_price_vector(Q),
findall( Item-> Pi,
(
member( (Item->Pi), P),
member( (Item->Qi), Q),
Pi =< Qi
),
P).
% old rules which were used in gs condition (abolish).
unit_price_increment_other_than(S, P->P1):-
price_increment_other_than(S, 1, P->P1).
k_unit_price_increment_other_than(S, K, P->P1):-
set_of_all_items(O),
bundle(S),
subtract(O,S,C),
price_increment_for_bundle(C, K, P->P1).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% VCG mechanism and replica economy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% added: 30 Aug 2005
% preliminary :
% maximizing surplus of coalition of bidders
% with restricted items
%-----------------------------------------
%
% For any subset S of N, and any subset (a bundle) Q of I,
% let V(S;Q) is the maximum surplus of a coalition of bidders
% with restricited items. More precisely,
% V(S;Q):= max Sum_over_S( u_j(b) | b is a member of x(Q)),
% where x(Q) represents an allocation of I retricted to Q,
% a* := argmax V(N;I) = argmax sum_over_N(u_j),
% and I will omit the second argument if Q=I.
%
% Theorem. (maximal and minimal Warlasian price vectors)
% When agent's utility functions are monotone and SI then
% for each bundle A,
% for item `a' in A,
% max (Warlasian price of item a) = V(S)-V(S;Q-a),
% and for item `a' not in A,
% min (supprting price of A) =V(S;A+a)-V(S;A),
% especially,
% min (Warlasian price of item a) = V(S;I+a)-V(S).
% (See Gul and Stacchetti(1999), Theorem 4 and Theorem 5.)
coalition(S):-
coalition(S, _, _).
coalition(S,[K,Sc,N]):-
coalition(S, K, N),
subtract( N, S, Sc).
% revised: 20-21 Sep 2005
coalition(S, K, N):-
find_subset(I, agent(I), N, S),
length(S, K).
% a tool of partial collection
%-----------------------------------------
% a generalization for alternative codes below.
find_subset(Item, Goal, F, C):-
findall( Item, Goal, F),
list_projection( _, F, C).
%% alt.
%(1)
/*
coalition(S, K, N):-
set_of_all_agents(N),
coalition_0(S, K, N).
coalition_0([], 0, []).
coalition_0(S, K, [J|N]):-
coalition_0(S, K, N),
agent(J).
coalition_0([J|S], K1, [J|N]):-
coalition_0(S, K, N),
agent(J),
K1 is K + 1.
*/
%(2)
% coalition(S, K, N):-
% set_of_all_agents(N),
% list_projection(_, N, S),
% length(S,K).
% optimal allocation
%-----------------------------------------
% revised: 8, 24 Sep 2005
% without backtrack
a_star( V, Y):- a_star_0( V, Y), !.
max_surplus_of_coalition( V, Y, S ):-
max_surplus_of_coalition_0( V, Y, S), !.
% with backtrack
a_star_0( V, Y):-
set_of_all_agents(N),
max_surplus_of_coalition_0( V, Y, N ).
max_surplus_of_coalition_0( V, Y, S ):-
set_of_all_items(I),
max_surplus_of_coalition_0( V, Y, S, I).
max_surplus_of_coalition( V, Y, S, Q):-
max_surplus_of_coalition_0( V, Y, S, Q),
!.
max_surplus_of_coalition_0( V, Y, S, Q):-
coalition(S),
S\=[],
bundle(Q),
max( V,
surplus_of_coalition_restricted_to_items( V, Y, S, Q)
).
max_surplus_of_coalition_0( 0, _, [], _).
surplus_of_coalition_restricted_to_items( V, Y, S, Q):-
feasible_allocation_restricted_to( Y, _:S, _:Q),
sumall( Vj, (member( A -> J, Y ), u(J,A,Vj)), V).
feasible_allocation_restricted_to( Y, agents:S, items:Q):-
coalition(S),
%S\=[],
bundle(Q),
feasible_allocation_0(item,S,Q,X),
transform_into_allocation( X, Y).
% VCG prices in sealed bid auctions
%-----------------------------------------
% definition: VCG payment q_i(Xi) is
% q_i(Xi) = V(N-i;I) - V(N-i;I-Xi)
% = V(N-i) - (V(N) - u_i(a*))
% = V(N-i) - Surplus of other than i.
% (See the definition by Gul and Stacchetti(1999) and
% compare it with that of Leonard(1986) for unit demand case.
% Also confer Bikhchandani et al.(2002).)
% Therefore individual's net benefit equals the marginal product,
% u_i(a*) -q_i(Xi) = V(N)-V(N-i).
vcg_payment( J, [Qf, Y, A], Q):-
coalition(S,[_,[J],_N]),
max_surplus_of_coalition( V, Y, S ),
a_star( Va, A),
member( Aj->J, A),
u( J, Aj, Uaj),
Qf = V - ( Va - Uaj),
Q is Qf.
% The VCG payment q_i(Xi) gives a lower bound of that of
% Warlasian equilibrium (p, X). That is
% q_i(Xi) =<
% (Gul and Stacchetti, 1999).
% (A classical theorem)
% unit demand preferences => vcg for i q_i=
% where p is the minimal equilibrium price.
% For example, see Leonard(1983), Demange et al. (1986).
% Gul and Stacchetti(1999) has proved for the replica economy
% of monotone SI preferences.
% note: the price vector 'minimal' in the sense that
% every other Walrasian price vector weakly dominates it.
% demo
%-----------------------------------------
% part 1.
/*
?- set_model(auction_1).
Yes
?- a_star(Y,V).
Y = 16
V = [ ([]->i), ([a]->j), ([b]->k)] ;
No
?- display_goals(max_surplus_of_coalition( V, Y, S),[V,Y,S]).
14; [ ([]->i), ([]->j), ([a, b]->k)]; [k];
12; [ ([]->i), ([a, b]->j), ([]->k)]; [j];
16; [ ([]->i), ([a]->j), ([b]->k)]; [j, k];
0; [ ([a, b]->i), ([]->j), ([]->k)]; [i];
14; [ ([]->i), ([]->j), ([a, b]->k)]; [i, k];
12; [ ([]->i), ([a, b]->j), ([]->k)]; [i, j];
16; [ ([]->i), ([a]->j), ([b]->k)]; [i, j, k];
No
?- display_goals(vcg_payment(J,[Qf,Y,A],Q),[Q,Qf,J,A,Y]).
0; 16- (16-0); i; [ ([]->i), ([a]->j), ([b]->k)]; [ ([]->i), ([a]->j), ([b]->k)];
6; 14- (16-8); j; [ ([]->i), ([a]->j), ([b]->k)]; [ ([]->i), ([]->j), ([a, b]->k)];
4; 12- (16-8); k; [ ([]->i), ([a]->j), ([b]->k)]; [ ([]->i), ([a, b]->j), ([]->k)];
No
?- display_goals((wep(P,Y),member(A->J,Y),c(P,A,C)),[A->J,C]).
[]->i; 0;
[a]->j; 600;
[b]->k; 700;
No
?- display_goals((wep(P,Y),member(A->J,Y),u(J,A,V)),[A->J,V]).
[]->i; 0;
[a]->j; 8;
[b]->k; 8;
No
*/
% demo
%-----------------------------------------
% part 2. VCG payment from definition and solve_wep_1.
% For a replica-economy case, vcg_payment/3 (and a_star/2, wep/2, etc.)
% will consume much time or cause a global stack over.
% The way shown below is slow but feasible in the case.
/*
?- set_model_without_agent(J,M).
J = j
M = auction_1
Yes
?- solve_wep_1(P,Y).
equilibrium!
P = [ (a->0), (b->0)]
Y = [ ([]->i), ([a, b]->k)]
Yes
?- display_goals((wep(P,Y),member(A->J,Y),u(J,A,V)),[A->J,V]).
[]->i; 0;
[a, b]->k; 14;
No
?- set_model_without_agent(J,auction_1_r3).
J = j(1)
Yes
?- solve_wep_1(P,Y).
init p:[ (a(1)->0), (b(1)->0), (a(2)->0), (b(2)->0), (a(3)->0), (b(3)->0)];xds:[a(2), a(3), b(2), b(3)]
p:[ (a(1)->0), (b(1)->0), (a(2)->300), (b(2)->300), (a(3)->300), (b(3)->300)];xds:[a(2), a(3), b(2), b(3)]->[b(2), b(3)]
p:[ (a(1)->0), (b(1)->0), (a(2)->300), (b(2)->400), (a(3)->300), (b(3)->400)];xds:[b(2), b(3)]->[a(2), a(3), b(2), b(3)]
p:[ (a(1)->0), (b(1)->0), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)];xds:[a(2), a(3), b(2), b(3)]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
P = [ (a(1)->0), (b(1)->0), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)]
Y = [ ([]->i), ([a(1), b(1)]->k(1)), ([a(2)]->j(2)), ([b(2)]->k(2)), ([a(3)]->j(3)), ([b(3)]->k(3))]
Yes
?- P = [ (a(1)->600), (b(1)->700), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)],
Y = [ ([]->i), ([a(3),b(3)]->k(1)), ([a(2)]->j(2)), ([b(2)]->k(2)), ([a(1)]->j(3)), ([b(1)]->k(3))],
display_goals((member((A->J),Y),c(P,A,C),u(J,A,U)),[A->J,c=C,u=U]).
[]->i; c=0; u=0;
[a(3), b(3)]->k(1); c=1300; u=14;
[a(2)]->j(2); c=600; u=8;
[b(2)]->k(2); c=700; u=8;
[a(1)]->j(3); c=600; u=8;
[b(1)]->k(3); c=700; u=8;
No
?- Vj1 is ( 14 - 8).
Vj1 = 6
Yes
?- set_model_without_agent(k(1),auction_1_r3).
Yes
?- P = [ (a(1)->600), (b(1)->700), (a(2)->600), (b(2)->700), (a(3)->600), (b(3)->700)],
Y = [ ([]->i), ([b(3)]->j(1)), ([a(3)]->j(2)), ([a(2), b(2)]->k(2)), ([a(1)]->j(3)), ([b(1)]->k(3))],
display_goals((member((A->J),Y),c(P,A,C),u(J,A,U)),[A->J,c=C,u=U]).
[]->i; c=0; u=0;
[b(3)]->j(1); c=700; u=9;
[a(3)]->j(2); c=600; u=8;
[a(2), b(2)]->k(2); c=1300; u=14;
[a(1)]->j(3); c=600; u=8;
[b(1)]->k(3); c=700; u=8;
No
?- Vk1 is ( 9 - 8 ) + ( 14 - 8 ).
Vj1 = 7
Yes
*/
% demo
%-----------------------------------------
% part 3.
% model: s 2x2 Job assignment problem in Leonard(1983).
% added: 8 Sep 2005
% revised: 9 Sep 2005
/*
?- set_model(assign_1),
solve_wep_1(P,Y),
display_goals(vcg_payment(A,[B|_],C),[A,B,C]).
init p:[ (job_a->0), (job_b->0)];xds:[job_a]
p:[ (job_a->500), (job_b->0)];xds:[job_a]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
firm; 18- (18-0); 0;
worker_1; 11- (18-7); 0;
worker_2; 12- (18-11); 5;
No
?- set_model(assign_2),
solve_wep_1(P,Y),
display_goals(vcg_payment(A,[B|_],C),[A,B,C]).
init p:[ (job_a->0), (job_b->0)];xds:[job_a]
p:[ (job_a->500), (job_b->0)];xds:[job_a]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
firm(a); 18- (18-0); 0;
firm(b); 18- (18-0); 0;
worker(1); 11- (18-7); 0;
worker(2); 12- (18-11); 5;
No
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% `agents are substitutes' condition
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% added: 3-4 Sep 2005.
% revised: 7-8 Sep 2005.
% For SI and monotone preferences (=> see next section),
% the following condition is necessary and sufficient for
% the dual solution of the primal-dual algorithm
% ( ascending auction) yields VCG payments.
%
% Def. (The `agents are substitutes' condition)
% V(N)-V(S) >= Sum_over_i_not_in_S( V(N)-V(N-[i]) )
% = Sum_over_i_not_in_S( v_i(N)-q_i ).
% Meaning: The contribution of a group is not less than
% the sum of each individual contribution out of the group.
% See Bikhchandani et al.(2002).
% model 1: direct verification
%-----------------------------------------
% however not effective except for small sized models.
:- dynamic temp_agtsbst/2.
agents_are_substitutes(coalition:S,T,R,values:([V|D],[Dv|E])):-
(var(V)->a_star( V, Y); true),
(var(Dv)->collect_individual_contributions(V, Y, Dv,Lv,Cv); true),
!,
coalition(S,[_,Sc,N]),
contribution_of_individuals_except_for_coalition(S,Sc,Dv,Cvsc),
( S=N -> (Vs=V, Ys=Y)
;
max_surplus_of_coalition( Vs, Ys, S )
),
T = (V - Vs >= Cvsc),
VData =([V|D],[Dv|E]),
D= [Vs,Cvsc,Y,Ys],
E= [Cv,Lv],
judge_agtsbst_condition_for_coalition(S,T,R, VData).
collect_individual_contributions(V,Y,Dv,Lv,Cv):-
(var(V)->a_star( V, Y); true),
findall((J,Vj =V - Vrj,Yrj),
(
coalition(Nrj,[_,[J],_N]),
max_surplus_of_coalition( Vrj, Yrj, Nrj ),
Vj is V - Vrj
),
Dv),
findall(Vj, member((_,Vj=_,_),Dv),Lv),
sum(Lv,Cv).
contribution_of_individuals_except_for_coalition(S,Sc,Dv,Vsc):-
(
( var(Dv) ; (member(D,Dv),var(D) ) )
->collect_individual_contributions(_,_,Dv,_,_)
; true
),
(var(S)->coalition(S,[_,Sc,_N]);true),
sumall(Vj,
(
member(J,Sc),
member((J,Vj=_,_),Dv)
),
Vsc).
judge_agtsbst_condition_for_coalition(S,T,R, VData):-
VData =([V,Vs,Cvsc|_],_),
T = (V - Vs >= Cvsc),
(T -> R=true ;R=false),
current_model(M),
(
clause( temp_agtsbst(M,[R,S|X]),true )
-> retract( temp_agtsbst(M,[R,S|X]) )
; true
),
assert( temp_agtsbst(M,[R,S,T,VData]) ).
% demo
%-----------------------------------------
% model: auction_1
/*
?- collect_individual_contributions(V,Y,[D1,D2,D3],Lv,Cv).
V = 16
Y = [ ([]->i), ([a]->j), ([b]->k)]
D1 = i, 0=16-16, [ ([]->i), ([a]->j), ([b]->k)]
D2 = j, 2=16-14, [ ([]->i), ([]->j), ([a, b]->k)]
D3 = k, 4=16-12, [ ([]->i), ([a, b]->j), ([]->k)]
Lv = [0, 2, 4]
Cv = 6
Yes
?- contribution_of_individuals_except_for_coalition(S,Sc,Dv,Vsc),
forall_nl_write(Dv).
i, 0=16-16, [ ([]->i), ([a]->j), ([b]->k)]
j, 2=16-14, [ ([]->i), ([]->j), ([a, b]->k)]
k, 4=16-12, [ ([]->i), ([a, b]->j), ([]->k)]
S = []
Sc = [i, j, k]
Dv = [ (i, 0=16-16, [ ([]->i), ([a]->j), ([b]->k)]),
(j, 2=16-14, [ ([]->i), ([]->j), ([a|...]->k)]),
(k, 4=16-12, [ ([]->i), ([a|...]->j), ([]->k)])]
Vsc = 6
Yes
?- display_goals( agents_are_substitutes(_:S,T,R,_),[R,S,T]).
true; []; 16-0>=6;
true; [k]; 16-14>=2;
true; [j]; 16-12>=4;
true; [j, k]; 16-16>=0;
true; [i]; 16-0>=6;
true; [i, k]; 16-14>=2;
true; [i, j]; 16-12>=4;
true; [i, j, k]; 16-16>=0;
No
?- temp_agtsbst(M,[R,S,T,([_,_,_,F,G],_)]),write([M,R,S,G]),nl,fail.
[auction_1, true, [], _G178]
[auction_1, true, [k], [ ([]->i), ([]->j), ([a, b]->k)]]
[auction_1, true, [j], [ ([]->i), ([a, b]->j), ([]->k)]]
[auction_1, true, [j, k], [ ([]->i), ([a]->j), ([b]->k)]]
[auction_1, true, [i], [ ([a, b]->i), ([]->j), ([]->k)]]
[auction_1, true, [i, k], [ ([]->i), ([]->j), ([a, b]->k)]]
[auction_1, true, [i, j], [ ([]->i), ([a, b]->j), ([]->k)]]
[auction_1, true, [i, j, k], [ ([]->i), ([a]->j), ([b]->k)]]
No
?- coalition(S),\+ agents_are_substitutes(_:S,_,_,_).
No
?-
*/
% model 2: using solve_wep_1
%-----------------------------------------
% another code for the `agents are substitutes' codition.
:- dynamic temp_asubst/2.
agents_are_substitutes_1( coalition: S,T,R,values:([V|D],[Dv|E]) ):-
( var(V) ->a_star( V, Y); true),
( var(Dv) ->collect_individual_contributions_1(V, Y, Dv,Lv,Cv); true),
!,
coalition(S,[_,Sc,N]),
contribution_of_individuals_except_for_coalition_1(S,Sc,Dv,Cvsc),
( S=N -> Vs=V, Ys=Y
; max_surplus_of_coalition_1( _, Vs, Ys, (S,Sc) )
),
T = (V - Vs >= Cvsc),
VData =([V|D],[Dv|E]),
D= [Vs,Cvsc,Y,Ys],
E= [Cv,Lv],
judge_agtsbst_condition_for_coalition(S,T,R, VData).
collect_individual_contributions_1(V,Y,Dv,Lv,Cv):-
(var(V)->a_star( V, Y); true),
check_model(M),
findall((J,Vj=V - Vrj,Yrj),
(
coalition(Nrj,[_,[J],_N]),
max_surplus_of_coalition_1(M, Vrj, Yrj, (Nrj,[J]) ),
Vj is V - Vrj
),
Dv),
findall(Vj, member((_,Vj=_,_),Dv),Lv),
sum(Lv,Cv).
check_model(M):-
current_model(M0),
clause(model(M,_,_,_,_,_),_),
( M0=M-_S ; M0=M ),
M \= auction_1_r3.
a_star_1( V,Y):-
collect_surplus_via_solve_wep_1(_P,Y,V).
max_surplus_of_coalition_1( _, 0, _, ([],_) ):-!.
max_surplus_of_coalition_1( M, V, Y, (S,Sc) ):-
check_model(M),
coalition(S,[_,Sc,_]),
S \= [],
set_model_without_coalition(Sc,M),
collect_surplus_via_solve_wep_1( _P,Y,V),
set_model(M),
!.
max_surplus_of_coalition_1( M, _, _, _ ):-
set_model(M).
collect_surplus_via_solve_wep_1( P,Y,V):-
solve_wep_1( P, Y),
sumall(U,
(
member((A->I),Y),
u(I,A,U)
),
V).
contribution_of_individuals_except_for_coalition_1(S,Sc,Dv,Vsc):-
(
( var(Dv) ; (member(D,Dv),var(D) ) )
->collect_individual_contributions_1(_,_,Dv,_,_)
; true
),
(var(S)->coalition(S,[_,Sc,_N]);true),
contribution_of_individuals_except_for_coalition(S,Sc,Dv,Vsc).
% demo
%-----------------------------------------
% model: auction_1
% a reproduction of former code.
/*
?- collect_individual_contributions_1(V,Y,[D1,D2,D3],Lv,Cv).
init p:[ (a->0), (b->0)];xds:[a, b]
p:[ (a->300), (b->300)];xds:[a, b]->[b]
p:[ (a->300), (b->400)];xds:[b]->[a, b]
p:[ (a->600), (b->700)];xds:[a, b]->[] equilibrium!
I can`t update prices, because
there is no excess demand item. equilibrium! equilibrium!
V = 16
Y = [ ([]->i), ([a]->j), ([b]->k)]
D1 = i, 0=16-16, [ ([]->i), ([a]->j), ([b]->k)]
D2 = j, 2=16-14, [ ([]->i), ([]->j), ([a, b]->k)]
D3 = k, 4=16-12, [ ([]->i), ([a, b]->j), ([]->k)]
Lv = [0, 2, 4]
Cv = 6
Yes
?- contribution_of_individuals_except_for_coalition_1(S,Sc,Dv,Vsc),
forall_nl_write(Dv).
init p:[ (a->0), (b->0)];xds:[a, b]
p:[ (a->300), (b->300)];xds:[a, b]->[b]
p:[ (a->300), (b->400)];xds:[b]->[a, b]
p:[ (a->600), (b->700)];xds:[a, b]->[] equilibrium!
I can`t update prices, because
there is no excess demand item. equilibrium! equilibrium!
i, 0=16-16, [ ([a]->j), ([b]->k)]
j, 2=16-14, [ ([]->i), ([a, b]->k)]
k, 4=16-12, [ ([]->i), ([a, b]->j)]
S = []
Sc = [i, j, k]
Dv = [ (i, 0=16-16, [ ([]->i), ([a]->j), ([b]->k)]),
(j, 2=16-14, [ ([]->i), ([]->j), ([a|...]->k)]),
(k, 4=16-12, [ ([]->i), ([a|...]->j), ([]->k)])]
Vsc = 6
Yes
?- display_goals( agents_are_substitutes(_:S,T,R,_),[R,S,T]).
init p:[ (a->0), (b->0)];xds:[a, b]
p:[ (a->300), (b->300)];xds:[a, b]->[b]
p:[ (a->300), (b->400)];xds:[b]->[a, b]
p:[ (a->600), (b->700)];xds:[a, b]->[] equilibrium!
I can`t update prices, because
there is no excess demand item. equilibrium! equilibrium!
true; []; 16-0>=6; equilibrium!
true; [k]; 16-14>=2; equilibrium!
true; [j]; 16-12>=4;
init p:[ (a->0), (b->0)];xds:[a, b]
p:[ (a->300), (b->300)];xds:[a, b]->[b]
p:[ (a->300), (b->400)];xds:[b]->[a, b]
p:[ (a->600), (b->700)];xds:[a, b]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
true; [j, k]; 16-16>=0; equilibrium!
true; [i]; 16-0>=6; equilibrium!
true; [i, k]; 16-14>=2; equilibrium!
true; [i, j]; 16-12>=4;
true; [i, j, k]; 16-16>=0;
No
?- temp_agtsbst(M,[R,S,T,([_,_,_,F,G],_)]),write([M,R,S,G]),nl,fail.
[auction_1, true, [], _G181]
[auction_1, true, [k], [ ([a, b]->k)]]
[auction_1, true, [j], [ ([a, b]->j)]]
[auction_1, true, [j, k], [ ([a]->j), ([b]->k)]]
[auction_1, true, [i], [ ([a, b]->i)]]
[auction_1, true, [i, k], [ ([]->i), ([a, b]->k)]]
[auction_1, true, [i, j], [ ([]->i), ([a, b]->j)]]
[auction_1, true, [i, j, k], [ ([]->i), ([a]->j), ([b]->k)]]
No
?- coalition(S),\+ agents_are_substitutes_1(_:S,_,_,_).
(...omit...)
No
?-
*/
% demo
%-----------------------------------------
% model: auction_3 (a violation.)
/*
?- set_model(auction_3),coalition(S1),
agents_are_substitutes(_:S1,T,false,_:([B|_],[_|E])).
S1 = []
T = 23-0>=27
B = 23
E = [27, [4, 10, 9, 4]]
No
?-
*/
% demo
%-----------------------------------------
% model: assign_0 with parameterized utilities.
/*
?- set_model(assign_0([repeat|X])),coalition(S),
agents_are_substitutes(_:S,T,false,_:([B|_],[_|E])).
No
?-
*/
% Caveat: It is not easy to generate negative cases.
% Experimentally using some small parameterized models
% such as assign_0 and job_matching_1.
% for larger models, checking condition per se
% would be demanding task in our code.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% preference models and analysis
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% model 1: monotonicity
%-----------------------------------------
preference_model( 'weakly monotone', Quant,Case, Def):-
Quant = forall,
Case = (agent(J),bundle(S),bundle(S1),DiffUtil),
DiffUtil = (u(J,S,U), u(J,S1,U1),DU is U1 - U),
Def = (subset(S,S1) -> DU >= 0; true).
% model 2: unit demand preference
%-----------------------------------------
preference_model( 'a unit demand', Quant,Case, Cond):-
Quant = forall,
Case = (agent(J),bundle(S),u(J,S,U),Unit),
Cond = (S =[] -> Def1 ;Def2),
Def1 = ( 0 is U),
Unit = (member(A,S), u(J,[A],U1)),
Def2 = (max(U1, Unit), 0 is U1 - U).
% model 3: additively separable preference
%-----------------------------------------
preference_model( 'additively separable', Quant,Case, Def):-
Quant = forall,
Case = (agent(J),bundle(S),u(J,S,U),Usum),
Usum = sumall(Ua,(member(A,S), u(J,[A],Ua)), U1),
Def = ( 0 is U1 - U).
% model 4: submodularity
%-----------------------------------------
% monotone SI u -> u and vt are submodular
% (Gul and Stacchetti(1999), Theorem 5)
% u(i)'s are monotone and SI => the linear relaxation yields the optimal.
% (Bikhchandani et al.(2002), Theorem 4, p.90)
preference_model( 'submodular u', Quant,Case, Def):-
Quant = forall,
Case = ( agent(J),u(J,A,Ua),u(J,B,Ub), UI),
UI= ( union(A,B,C1),sort(C1,C),intersection(A,B,D1),sort(D1,D)),
Def = ( u(J,C,Uc),u(J,D,Ud),0 >= (Uc+Ud) -(Ua+Ub)).
% demo
%-----------------------------------------
/*
?- analyze_preference(A,D,(B,C)).
A = 'weakly monotone'
D = subset([3], [2, 3])->0>=7- (4+0);true
B = no
C = agent(j), bundle([3]), bundle([2, 3]), u(j, [3], 4+0), u(j, [2, 3], 7) ;
A = 'a unit demand'
D = [2, 3]=[]->0 is 7;max(4, (member(2, [2, 3]), u(j, [2], 4))), 0 is 4-7
B = no
C = agent(j), bundle([2, 3]), u(j, [2, 3], 7), member(2, [2, 3]), u(j, [2], 4) ;
A = 'additively separable'
D = 0 is 8-7
B = no
C = agent(j), bundle([2, 3]), u(j, [2, 3], 7), sumall(_G283, (member(_G290, [2, 3]), u(j, [_G290], _G283)), 8) ;
(...)
No
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% gross substitutes (GS) condition
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorem (Gul and Stacchetti,1999)
% u is monotone => ( GS <=> SI <=> NC ).
% model 5: NC condition : no complementarities
%-----------------------------------------
preference_model( 'no complementarities', Quant,Case, Def):-
Quant = forall( P),
Case = ( agent(J),d(J,P,Dp),member(A,Dp),member(B,Dp),Xab),
Xab = ( asymmetric_differences(A,B,(C1,C2)),bundle(X),subset(X,C1) ),
Axy = ( subtract(A,X,W),union(W,Y,Z) ),
Def = ( bundle(Y),subset(Y,C2), Axy,member(Z, Dp) ).
% model 6: SI condition : single improvement property
%-----------------------------------------
preference_model( 'single improvement', Quant,Case, Def):-
Quant = forall( P),
Case = ( agent(J),d(J,P,Dp),bundle(A), \+ member(A,Dp),vt(J,A,P,Va)),
Improved = ( bundle(B),vt(J,B,P,Vb),Vb > Va ),
Def = ( Improved, no_more_single_difference(A,B) ).
% model 8 : GS condition
%-----------------------------------------
% It would consume time to complete.
preference_model( 'gross substitutes', Quant,Case, Def):-
Quant = forall( P),
Case = ( agent(J),d(J,P,Dp),member(A,Dp),NewPrice, d(J, Q, Dq) ),
NewPrice = ( price_increment_other_than(S, P->Q) ),
Def = ( member(B, Dq), intersection(S,A,S1),subset(S1, B) ).
no_more_single_difference(A,B):-
asymmetric_differences(A,B,(C1,C2)),
length(C1,N1),
N1=<1,
length(C2,N2),
N2=<1.
% Addendum.
% a test of supermodularity for the requirement function k given a price vector.
/*
?- agent(J),bundle(A),bundle(B),subset(A,B),
k(J,A,P,Ka),k(J,B,P,Kb),intersection(A,B,C),
union(A,B,D),k(J,C,P,Kc),k(J,D,P,Kd),
Ka+Kb > Kc+Kd.
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% preference analysis tools
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% background parameter for preference analysis
%-----------------------------------------
% option_for_analyze_preferences( OPT).
% If OPT =given_price, then pp(P), the current price vector,
% otherwise generate_price_vector(P), create new vector.
% (ch_apo/1 ==> MMT section)
% analyzer 1 : Quantifier= forall
%-----------------------------------------
analyze_preference( Condition, Def, Result):-
preference_model( Condition, forall, Case, Def),
(
(Case, \+ Def)
-> Result=(no,Case)
; Result=(yes,no_violation)
).
analyze_preference( (Condition,OPT:P), Def, Result):-
preference_model( Condition, forall(P), Case, Def),
option_for_analyze_preferences( OPT),
( OPT =given_price -> pp(P) ; generate_price_vector(P) ),
(
(Case, \+ Def)
-> Result=(no,Case)
; Result=(yes,no_violation)
).
% analyzer 2 : Quantifier= exisit
%-----------------------------------------
analyze_preference( Name, Def, Result):-
preference_model( Name, exisit, Case, Def),
(
(Case, Def)
-> Result=(yes,Case)
; Result=(no,no_support)
).
analyze_preference( (Condition,OPT:P), Def, Result):-
preference_model( Condition, exisit(P), Case, Def),
option_for_analyze_preferences( OPT),
( OPT =given_price -> pp(P) ; generate_price_vector(P) ),
(
(Case, Def)
-> Result=(yes,Case)
; Result=(no,no_support)
).
% analyzer 3: Case based
%-----------------------------------------
analyze_case_of_preference( Condition, Def, Result):-
preference_model( Condition, forall, Case, Def),
Case,
(Def
-> Result=(yes,Case)
; Result=(no,Case)
).
analyze_case_of_preference( (Condition,OPT:P), Def, Result):-
preference_model( Condition, forall(P), Case, Def),
option_for_analyze_preferences( OPT),
( OPT =given_price -> pp(P) ; generate_price_vector(P) ),
Case,
(Def
-> Result=(yes,Case)
; Result=(no,Case)
).
% demo
%-----------------------------------------
/*
% model: defalt (auction_1)
?- set_0_prices.
Yes
?- analyze_preference(A,D,(B,C)).
(...)
A = 'submodular u'
D = u(_G269, _G296, _G313), u(_G269, _G306, _G320), 0>=_G313+_G320- (_G276+_G283)
B = yes
C = no_violation ;
A = 'no complementarities', given_price:[ (a->1000), (b->1000)]
D = bundle(_G326), subset(_G326, _G308), (subtract(_G291, _G313, _G323), union(_G323, _G326, _G327)), member(_G327, _G286)
B = yes
C = no_violation ;
A = 'single improvement', given_price:[ (a->1000), (b->1000)]
D = (bundle(_G309), vt(_G279, _G309, [ (a->1000), (b->1000)], _G317), _G317>_G304), no_more_single_difference(_G291, _G309)
B = yes
C = no_violation ;
A = 'gross substitutes', given_price:[ (a->1000), (b->1000)]
D = member(_G310, _G299), intersection(_G301, _G291, _G318), subset(_G318, _G310)
B = yes
C = no_violation ;
No
?- A='single improvement',analyze_case_of_preference(A,(I,D),(B,C)).
A = 'single improvement'
O = given_price:[ (a->1000), (b->1000)]
I = bundle([]), vt(i, [], [ (a->1000), (b->1000)], 2000), 2000>1000
D = no_more_single_difference([b], [])
B = yes
C = agent(i), d(i, [ (a->1000), (b->1000)], [[]]), bundle([b]), \+member([b], [[]]), vt(i, [b], [ (a->1000), (b->1000)], 1000) ;
(...)
A = 'single improvement'
O = given_price:[ (a->1000), (b->1000)]
I = bundle([b]), vt(k, [b], [ (a->1000), (b->1000)], -200), -200> -600
D = no_more_single_difference([a, b], [b])
B = yes
C = agent(k), d(k, [ (a->1000), (b->1000)], [[]]), bundle([a, b]), \+member([a, b], [[]]), vt(k, [a, b], [ (a->1000), (b->1000)], -600) ;
No
?-
% model: assign_1 (bilateral, unit demand)
?- set_model(assign_1).
Yes
?- generate_price_vector(P),
A='single improvement',\+ analyze_preference((A,O),D,(B,C)).
No
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% cooperative game modeling
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- dynamic coop/2.
% charactristic functions ( transferable utility assumed )
%-----------------------------------------
% corresponding model: assign_1
% job assignment problem of Leonard(1983)
coop(assign_1,[
v([firm])=0,
v([worker_1])=0,
v([worker_2])=0,
v([worker_1,worker_2])=0,
v([firm,worker_2])=11,
v([firm,worker_1])=12,
v([firm,worker_1,worker_2])=18]
).
% NOTE: In above case, the core - wep is empty.
% In fact, a vector (5,7,6) with q(=p)=(5,0) is the incentive compatible,
% and is minimal equilibrium which we have already verified.
% As Ma(1998) proved, by adding dummy sellers (firms) resolve this.
% Similar for the following example provided by Ma.
coop(assign_2,[
v([firm(a)])=0,
v([firm(b)])=0,
v([worker(1)])=0,
v([worker(2)])=0,
v([worker(1),worker(2)])=0,
v([firm(a),firm(b)])=0,
v([firm(a),worker(2)])=11,
v([firm(a),worker(1)])=12,
v([firm(b),worker(2)])=4,
v([firm(b),worker(1)])=7,
v([firm(a),worker(1),worker(2)])=12,
v([firm(b),worker(1),worker(2)])=7,
v([firm(a),firm(b),worker(1)])=12,
v([firm(a),firm(b),worker(2)])=11,
v([firm(a),firm(b),worker(1),worker(2)])=18]
).
% no-firm model (Ma(1998), Kelso and Crawford(1982))
coop(job_matching_1(LE),[
v([i])=0,
v([j])=0,
v([k])=0,
v([j,k])=0,
v([i,j])=9,
v([i,k])=9,
v([i,j,k])=11+E3]
):-
LE=[E,E1,E2],
% alt % model(job_matching_1(LE),_,_,_,_),
current_model(job_matching_1(LE)),
constraint_of_perturb(E3,E,E1,E2).
coop(job_matching_2(LE),[
v([i1])=0,
v([i2])=0,
v([i3])=0,
v([j])=0,
v([k])=0,
v([i1,i2])=0,
v([i1,i3])=0,
v([i2,i3])=0,
v([j,k])=0,
v([i1,j])=4,
v([i1,k])=4+E2,
v([i2,j])=4,
v([i2,k])=4,
v([i3,j])=4+E1,
v([i3,k])=4,
v([i1,i2,j])=7+E,
v([i1,i2,k])=7,
v([i1,i3,j])=7,
v([i1,i3,k])=7,
v([i2,i3,j])=7,
v([i2,i3,k])=7+E,
v([i1,i2,i3,j])=9,
v([i1,i2,i3,k])=9,
v([i1,i2,i3,j,k])=11+E3]
):-
LE=[E,E1,E2],
current_model(job_matching_2(LE)),
constraint_of_perturb(E3,E,E1,E2).
constraint_of_perturb(E3,E,E1,E2):-
max_of(E3,[E,E1,E2]).
% demo
%-----------------------------------------
/*
constraint_of_perturb(E,E,E1,E2):-
0 =< E1,
E1 =< E,
0 =< E2,
E2 =< E.
constraint_of_perturb(E1,E,E1,E2):-
E2 =< E1,
E =< E1.
constraint_of_perturb(E2,E,E1,E2):-
E1 =< E2,
E =< E2.
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% game model analysis
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% you can compute discrete core of the game,
% optionally, by using coop.pl(Feb 2003).
% :- ['gt/coop.pl'].
% I'm afraid you have not copied one.
% Please include manually.
% Then reload this program.
% ?- [price].
%%%%
% :- dynamic game/4.
% game infomation (by coop/2) which is pegged at the current model.
game(G,GF,GP,PC):-
current_model( G),
GF =form(characteristic),
GP =players(NL),
PC =coalitions(CL),
coop(G,CValues),
setof(C, V^member(v(C)=V,CValues), CL),
flatten(CL, NL1),
sort(NL1, NL).
% the characteristic function
game(G,value,Coalition,V):-
coop(G,CValues),
member(v(Coalition)=V1, CValues),
% alt. % V is V1.
adjust_with_precision(Scale),
V is Scale * V1.
adjust_with_precision(Scale):-
precision(P),
Scale is integer(1 /P).
display_game(M):-
(var(M)->current_model(M);true),
model(M,Agents,Items,_,_),
nl,write('****** game for the model *******'),
nl,write(M),
forall(member(P,[Agents,Items]),(nl,write(P))),
coop(M,CFs),
nl,write('characteristic functions:'),
forall(member(V,CFs),(nl,tab(2),write(V))).
display_core(G):-
%set_game(G),
display_goals(
core(G,players(N),payoff(X)),
[G,N,X]
).
% demo
%-----------------------------------------
% model: assign_2
/*
?- set_model(assign_2).
Yes
?- change_precision(1).
Yes
?- core(game(assign_2),players(N),payoff(U)).
N = [firm(a), firm(b), worker(1), worker(2)]
U = [11, 6, 1, 0] ;
N = [firm(a), firm(b), worker(1), worker(2)]
U = [11, 5, 2, 0]
Yes
?- min(Z,(
core(game(assign_2),players(N),payoff(U)),
U=[A,B,_,_], Z is A+B)).
Z = 5
N = [firm(a), firm(b), worker(1), worker(2)]
U = [5, 0, 7, 6]
A = 5
B = 0 ;
No
?-
*/
% demo
%-----------------------------------------
% model: assign_1
/*
?- core(G,players(N),payoff(X)),nl,write(G:X),fail.
game(assign_2):[11, 6, 1, 0]
game(assign_2):[11, 5, 2, 0]
game(assign_2):[11, 4, 3, 0]
game(assign_2):[10, 5, 2, 1]
game(assign_2):[10, 4, 3, 1]
game(assign_2):[10, 3, 4, 1]
game(assign_2):[9, 4, 3, 2]
game(assign_2):[9, 3, 4, 2]
game(assign_2):[9, 2, 5, 2]
game(assign_2):[8, 3, 4, 3]
game(assign_2):[8, 2, 5, 3]
game(assign_2):[8, 1, 6, 3]
game(assign_2):[7, 2, 5, 4]
game(assign_2):[7, 1, 6, 4]
game(assign_2):[7, 0, 7, 4]
game(assign_2):[6, 1, 6, 5]
game(assign_2):[6, 0, 7, 5]
game(assign_2):[5, 0, 7, 6]
No
?- min(Z,(
core(G,players(N),payoff(V)),
V=[Va,Vb|_],
Z is Va + Vb)).
Z = 5
G = game(assign_2)
N = [firm(a), firm(b), worker(1), worker(2)]
V = [5, 0, 7, 6]
Va = 5
Vb = 0
Yes
?-
*/
% demo
%-----------------------------------------
% model: job_matching_1
% This game is a reformulation by Ma(1998) of
% one-sided job market game in Kelso and Crawford(1982)
% there exists a gap between the core allocations and
% the competitive equilibria.
% Here, we aloso can observe the gap between
% incentive compatible pricing (VCG payments)
% and the equilibrium.
% Ma(1998) proved that the former gap vanishes by adding
% dummy sellers with 0 utilities for each item.
/*
% without adjusting the precision (i.e., precision(1)).
% (coop.pl could not handle fraction.)
?- E=[0,0,0],set_model(job_matching_2(E)).
Yes
?- change_precision(1).
Yes
?- core(G,players(N),payoff(X)),nl,write(G:N:X),fail.
game(job_matching_1([0, 0, 0])):[i, j, k]:[11, 0, 0]
game(job_matching_1([0, 0, 0])):[i, j, k]:[10, 1, 0]
game(job_matching_1([0, 0, 0])):[i, j, k]:[9, 2, 0]
game(job_matching_1([0, 0, 0])):[i, j, k]:[10, 0, 1]
game(job_matching_1([0, 0, 0])):[i, j, k]:[9, 1, 1]
game(job_matching_1([0, 0, 0])):[i, j, k]:[8, 2, 1]
game(job_matching_1([0, 0, 0])):[i, j, k]:[9, 0, 2]
game(job_matching_1([0, 0, 0])):[i, j, k]:[8, 1, 2]
game(job_matching_1([0, 0, 0])):[i, j, k]:[7, 2, 2]
No
?- min(Z,(
core(game(job_matching_1(E)),players(N),payoff(U)),
U=[A,B,_], Z is A+B)).
Z = 9
E = [0, 0, 0]
N = [i, j, k]
U = [7, 2, 2]
A = 7
B = 2
Yes
?- vcg_payment(A,_,C),nl,write(A:C),fail.
i:0:11- (11-0)
j:2:9- (11-4)
k:5:9- (11- (7+0))
No
*/
% demo
%-----------------------------------------
% model: job_matching_2
/*
?- set_model(job_matching_2(E)), solve_wep_1(P,Y).
init p:[ (1->0), (2->0), (3->0)];xds:[1, 2, 3]
p:[ (1->300), (2->300), (3->300)];xds:[1, 2, 3]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
E = [0, 0, 0]
P = [ (1->300), (2->300), (3->300)]
Y = [ ([]->i1), ([]->i2), ([]->i3), ([2, 3]->j), ([1]->k)]
Yes
?- core(game(job_matching_2(E)),players(N),payoff(U)).
E = [0, 0, 0]
N = [i1, i2, i3, j, k]
U = [3, 3, 3, 1, 1] ;
No
?- vcg_payment(A,[B|_],C),nl,write(A:C:B),fail.
i1:0:11- (11-0)
i2:0:11- (11-0)
i3:0:11- (11-0)
j:2:9- (11-4)
k:5:9- (11- (7+0))
No
?-
*/
% demo
%-----------------------------------------
% model: job_matching_1
% a test of the predicates loaded from coop.pl
% after adjustment of the precision( 0.25).
% Let's verify that [v(N)-2,1,1] is always core allocation
% in job_matching_1([E,E1,E2]),
% a claim by Ma(1998).
/*
?- abolish(precision/1),assert(precision(0.01)).
Yes
?- set_model(G),
game(G,value,[i,j,k],VN),A is VN -200,
core(game(G),_,payoff([A,100,100])).
G = job_matching_1([0, 0, 0])
VN = 1100
A = 900 ;
start generating positive numbers:1:0.01
G = job_matching_1([0, 0, 0])
VN = 1100
A = 900 ;
G = job_matching_1([0.01, 0, 0])
VN = 1101
A = 901
Yes
?- abolish(precision/1),assert(precision(0.25)).
Yes
?- set_model(G),
game(G,value,[i,j,k],VN),A is VN -8,
\+ core(game(G),_,payoff([A,4,4])).
No
?-
% Notice (*): Prolog system tend to check the exisitence of clauses
% before processing queries.
% You may have a need to avoid `undifined procedure'.
?- forall(set_model(G),true),
max(B,(core(game(G),_,payoff(X)),X=[A,B,C])).
B = 5
G = job_matching_1([0, 0, 3])
X = [4, 5, 5]
A = 4
C = 5
Yes
?- forall(set_model(G),true),
tell_goal('core_a.txt',forall(set_model(G),
display_goals(
max(B,(core(game(G),_,payoff(X)),X=[A,B,C])),
[G,X,B]
)
)).
?- change_precision(1),forall(set_model(G),true),
forall(set_model(G),
display_goals(
(
max(B,
(core(game(G),_,payoff(X)), X=[A,B,C])
),
!
),
[G,X,B]
)
).
start generating positive numbers:1:1start generating positive numbers:3:1
job_matching_1([0, 0, 0]); [7, 2, 2]; 2;
job_matching_1([1, 0, 0]); [6, 3, 3]; 3;
job_matching_1([0, 0, 1]); [6, 3, 3]; 3;
job_matching_1([1, 0, 1]); [6, 3, 3]; 3;
job_matching_1([0, 0, 2]); [5, 4, 4]; 4;
job_matching_1([1, 0, 2]); [5, 4, 4]; 4;
job_matching_1([0, 0, 3]); [4, 5, 5]; 5;
job_matching_1([1, 0, 3]); [4, 5, 5]; 5;
job_matching_1([0, 1, 0]); [6, 3, 3]; 3;
job_matching_1([1, 1, 0]); [6, 3, 3]; 3;
job_matching_1([0, 1, 1]); [6, 3, 3]; 3;
job_matching_1([1, 1, 1]); [6, 3, 3]; 3;
job_matching_1([0, 1, 2]); [5, 4, 4]; 4;
job_matching_1([1, 1, 2]); [5, 4, 4]; 4;
job_matching_1([0, 1, 3]); [4, 5, 5]; 5;
job_matching_1([1, 1, 3]); [4, 5, 5]; 5;
job_matching_1([0, 2, 0]); [5, 4, 4]; 4;
job_matching_1([1, 2, 0]); [5, 4, 4]; 4;
job_matching_1([0, 2, 1]); [5, 4, 4]; 4;
job_matching_1([1, 2, 1]); [5, 4, 4]; 4;
job_matching_1([0, 2, 2]); [5, 4, 4]; 4;
job_matching_1([1, 2, 2]); [5, 4, 4]; 4;
job_matching_1([0, 2, 3]); [4, 5, 5]; 5;
job_matching_1([1, 2, 3]); [4, 5, 5]; 5;
job_matching_1([0, 3, 0]); [4, 5, 5]; 5;
job_matching_1([1, 3, 0]); [4, 5, 5]; 5;
job_matching_1([0, 3, 1]); [4, 5, 5]; 5;
job_matching_1([1, 3, 1]); [4, 5, 5]; 5;
job_matching_1([0, 3, 2]); [4, 5, 5]; 5;
job_matching_1([1, 3, 2]); [4, 5, 5]; 5;
job_matching_1([0, 3, 3]); [4, 5, 5]; 5;
job_matching_1([1, 3, 3]); [4, 5, 5]; 5;
G = _G157
B = _G175
X = _G166
A = _G172
C = _G178
Yes
?- change_precision(1),forall(set_model(G),true),
forall(set_model(G),
display_goals(
(
max(A,
(core(game(G),_,payoff(X)), X=[A,B,C])
),
!
),
[G,X,B]
)
).
job_matching_1([0, 0, 0]); [11, 0, 0]; 0;
job_matching_1([1, 0, 0]); [12, 0, 0]; 0;
job_matching_1([0, 0, 1]); [12, 0, 0]; 0;
job_matching_1([1, 0, 1]); [12, 0, 0]; 0;
job_matching_1([0, 0, 2]); [13, 0, 0]; 0;
job_matching_1([1, 0, 2]); [13, 0, 0]; 0;
job_matching_1([0, 0, 3]); [14, 0, 0]; 0;
job_matching_1([1, 0, 3]); [14, 0, 0]; 0;
job_matching_1([0, 1, 0]); [12, 0, 0]; 0;
job_matching_1([1, 1, 0]); [12, 0, 0]; 0;
job_matching_1([0, 1, 1]); [12, 0, 0]; 0;
job_matching_1([1, 1, 1]); [12, 0, 0]; 0;
job_matching_1([0, 1, 2]); [13, 0, 0]; 0;
job_matching_1([1, 1, 2]); [13, 0, 0]; 0;
job_matching_1([0, 1, 3]); [14, 0, 0]; 0;
job_matching_1([1, 1, 3]); [14, 0, 0]; 0;
job_matching_1([0, 2, 0]); [13, 0, 0]; 0;
job_matching_1([1, 2, 0]); [13, 0, 0]; 0;
job_matching_1([0, 2, 1]); [13, 0, 0]; 0;
job_matching_1([1, 2, 1]); [13, 0, 0]; 0;
job_matching_1([0, 2, 2]); [13, 0, 0]; 0;
job_matching_1([1, 2, 2]); [13, 0, 0]; 0;
job_matching_1([0, 2, 3]); [14, 0, 0]; 0;
job_matching_1([1, 2, 3]); [14, 0, 0]; 0;
job_matching_1([0, 3, 0]); [14, 0, 0]; 0;
job_matching_1([1, 3, 0]); [14, 0, 0]; 0;
job_matching_1([0, 3, 1]); [14, 0, 0]; 0;
job_matching_1([1, 3, 1]); [14, 0, 0]; 0;
job_matching_1([0, 3, 2]); [14, 0, 0]; 0;
job_matching_1([1, 3, 2]); [14, 0, 0]; 0;
job_matching_1([0, 3, 3]); [14, 0, 0]; 0;
job_matching_1([1, 3, 3]); [14, 0, 0]; 0;
G = _G157
A = _G172
X = _G166
B = _G175
C = _G178
Yes
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% extended game modeling
% with soio-psychological motives
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% added: 19-25 Sep 2005
% About this section of modeling with utility or
% disutility of co-workers, see Ma(2001).
%-----------------------------------------
% Part I. Utility Function With Coworkers
%-----------------------------------------
% utility or disutility of co-workers
%-----------------------------------------
% Zero settings of u_cw/5, the modeling without
% coworkers effect on utility function
% is available by ch_ucw/1 (=>MMT section)
:- dynamic u_cw/6.
% u_cw/5 specified for model job_matching_2(LE),
% and the cases are stored as u_cw/6.
% case 1
% a case of empty core, Example 1 in Ma(2001).
u_cw( case_1, job_matching_2(_), i1, [i1,i2], j, 1).
u_cw( case_1, job_matching_2(_), i2, [i2,i3], k, 1).
% case 2
% a case of nonempty core, but the core equivalence fails,
% Example 7 in Ma(2001).
u_cw( case_2, job_matching_2(_), i1, [i1,i2], j, 0.3).
u_cw( case_2, job_matching_2(_), i2, [i1,i2], j, 0.2).
u_cw( case_2, job_matching_2(_), i2, [i2,i3], k, 0.3).
u_cw( case_2, job_matching_2(_), i3, [i2,i3], k, 0.2).
% the default value is set to zero.
u_cw( M, J, C, I, U):-
case_for_u_cw( Case, on),
u_cw( Case, M, J, C, I, U).
u_cw( M, J, C, I, 0):-
u_cw_is_not_specified_for( M, J, C, I).
% u_cw/4 (without explicit model term)
u_cw( Worker, Coworkers, Firm, Utility):-
current_model( M),
u_cw( M, Worker, Coworkers, Firm, Utility).
% case switcher for u_cw
%-----------------------------------------
% case_for_u_cw/2 => MMT
% workers and firms
%-----------------------------------------
% workers and firms (without explicit model term )
worker( J):- current_model(M), worker( M, J).
firm( I):- current_model(M), firm( M, I).
% workers in the model
worker( job_matching_2(_), i1). % <-- item( 1)
worker( job_matching_2(_), i2). % <-- item( 2)
worker( job_matching_2(_), i3). % <-- item( 3)
% the exceptional case is left to refer below.
worker( M, J):-
worker_if_not_defined_for_model(M, J).
% firms in the model
firm( job_matching_2(_), j).
firm( job_matching_2(_), k).
firm( M, J):-
firm_if_not_defined_for_model(M, J).
% possible colleagues
%-----------------------------------------
is_possible_colleagues_of( Worker, Coworkers):-
find_subset( I, worker(I), _, Coworkers),
member( Worker, Coworkers).
% rules for default or exception
%-----------------------------------------
% utility or disutility in other models
u_cw_is_not_specified_for( M, Worker, Coworkers, Firm):-
current_model( M),
is_possible_colleagues_of( Worker, Coworkers),
firm( Firm),
\+ clause(
u_cw( M, Worker, Coworkers, Firm, _),
true
).
% workers and firms in other models
% default worker := dummy seller.
worker_if_not_defined_for_model(M, J):-
current_model(M),
\+ clause( worker(M, _), true),
owner_of_unsold_items( J).
firm_if_not_defined_for_model(M, J):-
current_model(M),
\+ clause( firm(M, _), true),
owner_of_unsold_items( O),
agent( J),
J \= O.
% aggregated utility of (co-)workers at a firm
%-----------------------------------------
total_effect_of_coworkers_at_firm(Firm,Coworkers,Ucw):-
firm( Firm),
setof(U,
Worker^(
is_possible_colleagues_of( Worker, Coworkers),
u_cw( Worker, Coworkers, Firm, U)
),
Lucw),
sum(Lucw, Ucw).
% demo
%-----------------------------------------
/*
?- display_goals(total_effect_of_coworkers_at_firm(_,_,_)).
total_effect_of_coworkers_at_firm(j, [i3], 0)
total_effect_of_coworkers_at_firm(j, [i2], 0)
total_effect_of_coworkers_at_firm(j, [i2, i3], 0)
total_effect_of_coworkers_at_firm(j, [i1], 0)
total_effect_of_coworkers_at_firm(j, [i1, i3], 0)
total_effect_of_coworkers_at_firm(j, [i1, i2], 1)
total_effect_of_coworkers_at_firm(j, [i1, i2, i3], 0)
total_effect_of_coworkers_at_firm(k, [i3], 0)
total_effect_of_coworkers_at_firm(k, [i2], 0)
total_effect_of_coworkers_at_firm(k, [i2, i3], 1)
total_effect_of_coworkers_at_firm(k, [i1], 0)
total_effect_of_coworkers_at_firm(k, [i1, i3], 0)
total_effect_of_coworkers_at_firm(k, [i1, i2], 0)
total_effect_of_coworkers_at_firm(k, [i1, i2, i3], 0)
Yes
?-
*/
% worker-item table
%-----------------------------------------
item_worker_table( job_matching_2(_), 1, i1).
item_worker_table( job_matching_2(_), 2, i2).
item_worker_table( job_matching_2(_), 3, i3).
item_worker_table( Model, Item, Owner):-
current_model( Model),
\+ clause( item_worker_table( Model,_,_),true),
owner_of_unsold_items( Owner),
!,
item( Item).
item_worker_table( Item, Owner):-
current_model( Model),
item_worker_table( Model, Item, Owner).
% items-workers mapping
%-----------------------------------------
% Items <=> Coworkers (initial belongings)
% case 1: Items -> Workers
items_workers_map( Items, '->', Workers):-
\+ var( Items),
bundle( Items),
% (var( Workers) ; \+ var( Workers)),
items_workers_map_0( Items, Workers0),
sort( Workers0, Workers).
% case 2: Items <- Workers
items_workers_map( Items, '<-', Workers):-
var( Items),
\+ var( Workers),
forall( member( Y, Workers), worker(Y)),
findall(X,
(
member(Y, Workers),
item_worker_table( X, Y)
),
Items).
items_workers_map_0( [], []).
items_workers_map_0( [X|Items], [Y|Workers]):-
items_workers_map_0( Items, Workers),
item_worker_table( X, Y).
% firms-workers coalition and the items
%-----------------------------------------
% 21 Sep 2005 19:18 pm
items_for_coalition( Model, T, Items):-
(var(T)->coalition( T);true),
(var(Model)->current_model( Model);true),
findall( Item,
(
member( Worker, T ),
item_worker_table( Model,Item, Worker)
),
Items).
workers_for_coalition( T, Items, Workers):-
current_model( Model),
items_for_coalition( Model, T, Items),
% bidirection
items_workers_map( Items, _, Workers).
% firms-workers coalition and
%-----------------------------------------
% firms-workers coalition
firms_workers_coalition( T, Firms,Workers,Items):-
workers_for_coalition( T, Items, Workers),
subtract( T, Workers, Firms).
% demo
%-----------------------------------------
/*
?- set_model(job_matching_1([0,0,0])).
Yes
?- display_goals((
firms_workers_coalition( T, Fc,Wc,Ic)),
[T;Fc;Wc;Ic]).
[];[];[];[];
[k];[k];[];[];
[j];[j];[];[];
[j, k];[j, k];[];[];
[i];[];[i];[1, 2, 3];
[i, k];[k];[i];[1, 2, 3];
[i, j];[j];[i];[1, 2, 3];
[i, j, k];[j, k];[i];[1, 2, 3];
No
?-
*/
% feasible allocations in firms-workers coalition
%-----------------------------------------
% Firstly, assign a new owner (a firm or a worker)
% for each item (worker) in the coalition.
% Then, embed the partial-plan into a full allocation.
feasible_allocation_in_f_w_coalition( T,(F,W,O),Y):-
firms_workers_coalition( T, F,W,O),
feasible_allocation_0( item,T,O,X),
transform_into_allocation( X, Y).
% showing just non-empty cells.
feasible_allocation_in_f_w_coalition_1( T,(F,W,O),Ya):-
feasible_allocation_in_f_w_coalition( T,(F,W,O),Y),
nonempty_assignments( Y ->Ya).
% demo
%-----------------------------------------
/*
?- set_model( job_matching_1([0, 0, 0]) ).
Yes
?- display_goals(
feasible_allocation_in_f_w_coalition_1([i,j,k],(F,W,I),Y),
[F;W;Y]).
[j, k];[i];[ ([1, 2, 3]->i)];
[j, k];[i];[ ([2, 3]->i), ([1]->j)];
[j, k];[i];[ ([2, 3]->i), ([1]->k)];
[j, k];[i];[ ([1, 3]->i), ([2]->j)];
[j, k];[i];[ ([3]->i), ([1, 2]->j)];
[j, k];[i];[ ([3]->i), ([2]->j), ([1]->k)];
[j, k];[i];[ ([1, 3]->i), ([2]->k)];
[j, k];[i];[ ([3]->i), ([1]->j), ([2]->k)];
[j, k];[i];[ ([3]->i), ([1, 2]->k)];
[j, k];[i];[ ([1, 2]->i), ([3]->j)];
[j, k];[i];[ ([2]->i), ([1, 3]->j)];
[j, k];[i];[ ([2]->i), ([3]->j), ([1]->k)];
[j, k];[i];[ ([1]->i), ([2, 3]->j)];
[j, k];[i];[ ([1, 2, 3]->j)];
[j, k];[i];[ ([2, 3]->j), ([1]->k)];
[j, k];[i];[ ([1]->i), ([3]->j), ([2]->k)];
[j, k];[i];[ ([1, 3]->j), ([2]->k)];
[j, k];[i];[ ([3]->j), ([1, 2]->k)];
[j, k];[i];[ ([1, 2]->i), ([3]->k)];
[j, k];[i];[ ([2]->i), ([1]->j), ([3]->k)];
[j, k];[i];[ ([2]->i), ([1, 3]->k)];
[j, k];[i];[ ([1]->i), ([2]->j), ([3]->k)];
[j, k];[i];[ ([1, 2]->j), ([3]->k)];
[j, k];[i];[ ([2]->j), ([1, 3]->k)];
[j, k];[i];[ ([1]->i), ([2, 3]->k)];
[j, k];[i];[ ([1]->j), ([2, 3]->k)];
[j, k];[i];[ ([1, 2, 3]->k)];
No
?- set_model(job_matching_2([0,0,0])).
Yes
?- display_goals(
feasible_allocation_in_f_w_coalition_1(C,(F,[i1,i2],I),Y),
[C;Y]).
[i1, i2];[ ([1, 2]->i1)];
[i1, i2];[ ([2]->i1), ([1]->i2)];
[i1, i2];[ ([1]->i1), ([2]->i2)];
[i1, i2];[ ([1, 2]->i2)];
[i1, i2, k];[ ([1, 2]->i1)];
[i1, i2, k];[ ([2]->i1), ([1]->i2)];
[i1, i2, k];[ ([2]->i1), ([1]->k)];
[i1, i2, k];[ ([1]->i1), ([2]->i2)];
[i1, i2, k];[ ([1, 2]->i2)];
[i1, i2, k];[ ([2]->i2), ([1]->k)];
[i1, i2, k];[ ([1]->i1), ([2]->k)];
[i1, i2, k];[ ([1]->i2), ([2]->k)];
[i1, i2, k];[ ([1, 2]->k)];
[i1, i2, j];[ ([1, 2]->i1)];
[i1, i2, j];[ ([2]->i1), ([1]->i2)];
[i1, i2, j];[ ([2]->i1), ([1]->j)];
[i1, i2, j];[ ([1]->i1), ([2]->i2)];
[i1, i2, j];[ ([1, 2]->i2)];
[i1, i2, j];[ ([2]->i2), ([1]->j)];
[i1, i2, j];[ ([1]->i1), ([2]->j)];
[i1, i2, j];[ ([1]->i2), ([2]->j)];
[i1, i2, j];[ ([1, 2]->j)];
[i1, i2, j, k];[ ([1, 2]->i1)];
[i1, i2, j, k];[ ([2]->i1), ([1]->i2)];
[i1, i2, j, k];[ ([2]->i1), ([1]->j)];
[i1, i2, j, k];[ ([2]->i1), ([1]->k)];
[i1, i2, j, k];[ ([1]->i1), ([2]->i2)];
[i1, i2, j, k];[ ([1, 2]->i2)];
[i1, i2, j, k];[ ([2]->i2), ([1]->j)];
[i1, i2, j, k];[ ([2]->i2), ([1]->k)];
[i1, i2, j, k];[ ([1]->i1), ([2]->j)];
[i1, i2, j, k];[ ([1]->i2), ([2]->j)];
[i1, i2, j, k];[ ([1, 2]->j)];
[i1, i2, j, k];[ ([2]->j), ([1]->k)];
[i1, i2, j, k];[ ([1]->i1), ([2]->k)];
[i1, i2, j, k];[ ([1]->i2), ([2]->k)];
[i1, i2, j, k];[ ([1]->j), ([2]->k)];
[i1, i2, j, k];[ ([1, 2]->k)];
No
?-
*/
%-----------------------------------------
% Part II. The Products of F-W Coalition
%-----------------------------------------
% production of a firm with co-workers effect.
%-----------------------------------------
% New production function
% u_f'(i; Si) = u_f(i; Si)
% + Sum_over_coworkers( u_w( j, Si; i)).
% The product of a firm-workers coalition
% is the sum of its product and utility
% or disutility generated
% in the workplace when it hires a group of workers.
% (Ma(2001) p.98)
% This transformation does not change the coalitional
% form game.
product_of_firm_workers_coalition( Firm,Coworkers,Items,Qc+Uc,Vc):-
total_effect_of_coworkers_at_firm( Firm, Coworkers, Uc),
items_workers_map( Items, _,Coworkers ),
u( Firm, Items, Qc),
Vc is Qc + Uc.
% demo
%-----------------------------------------
/*
?- set_model( job_matching_1([0, 0, 0]) ).
Yes
?- display_goals(
product_of_firm_workers_coalition(Firm,Coworkers,Items,Qc+Uc,Vc),
[Vc=Qc+Uc:Firm-Coworkers:Items]).
9=9+0:j-[i]:[1, 2, 3];
9=9+0:k-[i]:[1, 2, 3];
No
?- display_goals(( bundle( Items),
product_of_firm_workers_coalition(Firm,Coworkers,Items,Qc+Uc,Vc)
),[Vc=Qc+Uc:Firm-Coworkers:Items]).
4=4+0+0:j-[i]:[3];
4=4+0:k-[i]:[3];
4=4+0:j-[i]:[2];
4=4+0:k-[i]:[2];
7=7+0:j-[i]:[2, 3];
7=7+0+0:k-[i]:[2, 3];
4=4+0:j-[i]:[1];
4=4+0+0:k-[i]:[1];
7=7+0:j-[i]:[1, 3];
7=7+0:k-[i]:[1, 3];
7=7+0+0:j-[i]:[1, 2];
7=7+0:k-[i]:[1, 2];
9=9+0:j-[i]:[1, 2, 3];
9=9+0:k-[i]:[1, 2, 3];
No
?- set_model( job_matching_2([0, 0, 0]) ).
Yes
?- display_goals(del(job_matching_2([0,0,0])).
product_of_firm_workers_coalition(Firm,Coworkers,Items,Qc+Uc,Vc),
[Vc=Qc+Uc:Firm-Coworkers:Items]).
-4=4+0+0:j-[i3]:[3];
4=4+0:j-[i2]:[2];
7=7+0:j-[i2, i3]:[2, 3];
4=4+0:j-[i1]:[1];
7=7+0:j-[i1, i3]:[1, 3];
8=7+0+1:j-[i1, i2]:[1, 2];
9=9+0:j-[i1, i2, i3]:[1, 2, 3];
4=4+0:k-[i3]:[3];
4=4+0:k-[i2]:[2];
8=7+0+1:k-[i2, i3]:[2, 3];
4=4+0+0:k-[i1]:[1];
7=7+0:k-[i1, i3]:[1, 3];
7=7+0:k-[i1, i2]:[1, 2];
9=9+0:k-[i1, i2, i3]:[1, 2, 3];
No
?-
*/
% aggregated production function for firms-workers coalition.
%-----------------------------------------
% a pache for representing allocation.
% nonempty_assignments(Y->Ya).
total_products_of_firms_workers_coalition( T, [Y,(Cf,Cw,Ci),Lfwv], V):-
feasible_allocation_in_f_w_coalition( T, (Cf,Cw,Ci), Y),
findall((Firm,Workers,Vi),
(
member( Firm, Cf),
member( (Items->Firm), Y),
product_of_firm_workers_coalition( Firm,Workers,Items,_,Vi)
),
Lfwv),
sumall( Vi, member((_,_,Vi),Lfwv),V).
% demo
%-----------------------------------------
/*
?- set_model( job_matching_1([0.5, 1, 0]) ).
Yes
?- display_goals((
total_products_of_firms_workers_coalition( [i,k], [Y|_], V),0, nonempty_assignments(Y->Ya)
V>0, nonempty_assignments(Y->Ya)
),[V;Ya]).
4;[ ([2, 3]->i), ([1]->k)];
4;[ ([1, 3]->i), ([2]->k)];
7;[ ([3]->i), ([1, 2]->k)];
4;[ ([1, 2]->i), ([3]->k)];
7;[ ([2]->i), ([1, 3]->k)];
7.5;[ ([1]->i), ([2, 3]->k)];
9;[ ([1, 2, 3]->k)];
No
?- a_star(V_star,Y),total_products_of_firms_workers_coalition( T, [Y|Dv], V).
V_star = 11
Y = [ ([]->i), ([1]->j), ([2, 3]->k)]
T = [i, j, k]
Dv = [ ([j, k], [i], [1, 2, 3]), [ (j, [i], 5), (k, [i], 7)]]
V = 12
Yes
?- display_goals((
firms_workers_coalition( T, Fc,Wc,Ic),
Dv=[Y,(Fc,Wc,Ic),_Lv],
max( V,
total_products_of_firms_workers_coalition( T, Dv, V)
),nonempty_assignments(Y->Ya)),[V:T:Ya]).
0:[]:[];
0:[k]:[];
0:[j]:[];
0:[j, k]:[];
0:[i]:[ ([1, 2, 3]->i)];
9:[i, k]:[ ([1, 2, 3]->k)];
9:[i, j]:[ ([1, 2, 3]->j)];
12:[i, j, k]:[ ([3]->j), ([1, 2]->k)];
No
?- set_model( job_matching_2([0, 0, 0]) ).
Yes
?- findall((V,T),(
firms_workers_coalition( T, _,_,_),
max( V,
total_products_of_firms_workers_coalition( T, _, V)
)),MTV),sort(MTV,MTV1),forall_nl_write(MTV1),fail.
0, []
0, [i1]
0, [i1, i2]
0, [i1, i2, i3]
0, [i1, i3]
0, [i2]
0, [i2, i3]
0, [i3]
0, [j]
0, [j, k]
0, [k]
4, [i1, j]
4, [i1, j, k]
4, [i1, k]
4, [i2, j]
4, [i2, j, k]
4, [i2, k]
4, [i3, j]
4, [i3, j, k]
4, [i3, k]
7, [i1, i2, k]
7, [i1, i3, j]
7, [i1, i3, k]
7, [i2, i3, j]
8, [i1, i2, j]
8, [i1, i2, j, k]
8, [i1, i3, j, k]
8, [i2, i3, j, k]
8, [i2, i3, k]
9, [i1, i2, i3, j]
9, [i1, i2, i3, k]
12, [i1, i2, i3, j, k]
No
?- set_model( job_matching_2([0.5, 1, 0]) ).
Yes
?- findall((V,T),(el(job_matching_2([0.5,1,0])).
firms_workers_coalition( T, _,_,_),
max( V,
total_products_of_firms_workers_coalition( T, _, V)
)),MTV),sort(MTV,MTV1),forall_nl_write(MTV1),fail.
0, []
0, [i1]
0, [i1, i2]
0, [i1, i2, i3]
0, [i1, i3]
0, [i2]
0, [i2, i3]
0, [i3]
0, [j]
0, [j, k]
0, [k]
4, [i1, j]
4, [i1, j, k]
4, [i1, k]
4, [i2, j]
4, [i2, j, k]
4, [i2, k]
4, [i3, k]
5, [i3, j]
5, [i3, j, k]
7, [i1, i2, k]
7, [i1, i3, j]
7, [i1, i3, k]
7, [i2, i3, j]
8.5, [i1, i2, j]
8.5, [i1, i2, j, k]
8.5, [i2, i3, k]
9, [i1, i2, i3, j]
9, [i1, i2, i3, k]
9, [i1, i3, j, k]
9, [i2, i3, j, k]
12.5, [i1, i2, i3, j, k]
No
?-
*/
%-----------------------------------------
% Part III. Automated Game Design
%-----------------------------------------
% transforming model/6 to coop/2
% with/without utility of co-workers
% characterisitic function of the game
%-----------------------------------------
% v(T):= Max_feasible_allocation_S_in_coalition_T( F )
% where F = Sum_over_firms_in_T( u_f'(i; Si) )
% See Ma(2001).
:- dynamic coop_0/3.
:- dynamic temp_warn_no_optimal/2.
value_of_firms_workers_coalition( Model, Dv,T-> V):-
current_model( Model),
clause(
coop_0( Model, Dv, (T->V)),
true
).
value_of_firms_workers_coalition( Model, Dv, T->V):-
current_model( Model),
\+ clause(
coop_0( Model, _,_),
true
),
firms_workers_coalition( T, Fc,Wc,Ic),
Dv=[_Y,(Fc,Wc,Ic),_Lv],
max_total_products_of_fw_coalition( T, Dv, V),
assert(
coop_0( Model,Dv, (T->V))
).
max_total_products_of_fw_coalition( T, Dv, V):-
(var(T)->firms_workers_coalition( T, Fc,Wc,Ic);true),
Dv=[_Y,(Fc,Wc,Ic),_Lv],
(
max( V,
total_products_of_firms_workers_coalition( T, Dv, V)
)
-> true
; nl,write('no optimal solution for'),write(T),
assert( temp_warn_no_optimal(T,Dv))
).
% setting the characterisitic functions
%-----------------------------------------
:- dynamic temp_coop/2.
transform_coop( Model):-
current_model( Model ),
initialize_transform_coop( Model),
abolish( temp_warn_no_optimal/2),
findall( v( T)=Vcw,
(
value_of_firms_workers_coalition( Model,_,T->Vcw)
),
NewValues),
assert( coop( Model, NewValues)).
transform_coop( Model):-
current_model( Model ),
\+ clause( coop(Model,_), _),
recovery_coop(Model).
initialize_transform_coop( Model):-
abolish( temp_coop/2),
set_model( Model),
keep_current_coop( Model),
!.
keep_current_coop( Model):-
\+ clause( coop(Model,_), _).
keep_current_coop( Model):-
clause( coop(Model,V), B),
retract( (coop(Model, V):-B)),
assert( (temp_coop(Model, V):-B)).
recovery_coop( Model):-
current_model( Model ),
clause( temp_coop( Model, Vb), B),
clause( coop( Model, Va), A ),
retract( (coop( Model, Va):-A) ),
assert( (coop( Model, Vb):-B) ).
% demo
%-----------------------------------------
% A verification for Example 7 in Ma(2001)
% by using new model management tools.
% Modification. For each firm's utility
% (production) function, modify it as loaded with
% co-workers effect in the firm-workers coalition.
% This leads to the core equivalent competitive
% equilibrium (see below), and the several
% tie-breaking outcomes vanish
% (which can be shown by using a_star_0/2)
% for the job market model (M)
% which is named job_matching_2([0,0,0])
% in our modelbase.
% fact to verify (1)
%-----------------------
% the model job_matching_2([0.5,1,0]))
% without coworkers effect
% has a nonempty core.
% fact to verify (2)
%-----------------------
% the model job_matching_2([0.5,1,0]))
% with coworkers effect,
% of the case 1 u_cw/4,
% has NO nonempty core.
% fact to verify (3)
%-----------------------
% the model job_matching_2([0,0,0]))
% with coworkers effect,
% of the case 2 u_cw/4,
% which is loaded in production function of firms,
% has a nonempty core,
% but the competitive price does NOT exists.
% fact to verify (4)
%-----------------------
% the model job_matching_2([0,0,0]))
% with coworkers effect,
% of the case 2 u_cw/4,
% which is loaded in production function of firms,
% has a nonempty core,
% and the competitive price does exists.
%-----------------------
% before above checking,
% a preliminary exam.
%-----------------------
/*
?- set_model(job_matching_1([0,0,0])),
abolish(coop_0/3),transform_coop( Model),
current_model(A),coop(A,B),forall_nl_write(B).
v([])=0
v([k])=0
v([j])=0
v([j, k])=0
v([i])=0
v([i, k])=9
v([i, j])=9
v([i, j, k])=11
A = job_matching_1([0, 0, 0])
B = [v([])=0, v([k])=0, v([j])=0, v([j, k])=0, v([i])=0, v([i|...])=9, v([...|...])=9, v(...)=11]
Yes
?- min(U,(core(G,_,P),P=payoff([U,_,_]))).
U = 28
G = game(job_matching_1([0, 0, 0]))
P = payoff([28, 8, 8])
Yes
?- set_model(job_matching_1([0.5,1,0])),).
abolish(coop_0/3),transform_coop( Model),
current_model(A),coop(A,B),forall_nl_write(B).
v([])=0
v([k])=0
v([j])=0
v([j, k])=0
v([i])=0
v([i, k])=9
v([i, j])=9
v([i, j, k])=12
Model = job_matching_1([0.5, 1, 0])
A = job_matching_1([0.5, 1, 0])
B = [v([])=0, v([k])=0, v([j])=0, v([j, k])=0, v([i])=0, v([i|...])=9, v([...|...])=9, v(...)=12]
Yes
?- min(U,(core(G,_,P),P=payoff([U,_,_]))).
U = 24
G = game(job_matching_1([0.5, 1, 0]))
P = payoff([24, 12, 12]) ;
No
*/
%-----------------------
% checking fact (2).
%-----------------------
/*
?- set_model(job_matching_2([0.5,1,0])),
abolish(coop_0/3), transform_coop( Model),
current_model(A),coop(A,B),forall_nl_write(B).
v([])=0
v([k])=0
v([j])=0
v([j, k])=0
v([i3])=0
v([i3, k])=4
v([i3, j])=5;
v([i3, j, k])=5
v([i2])=0
v([i2, k])=4
v([i2, j])=4
v([i2, j, k])=4
v([i2, i3])=0
v([i2, i3, k])=8.5
v([i2, i3, j])=7
v([i2, i3, j, k])=9
v([i1])=0
v([i1, k])=4
v([i1, j])=4
v([i1, j, k])=4
v([i1, i3])=0
v([i1, i3, k])=7
v([i1, i3, j])=7
v([i1, i3, j, k])=9
v([i1, i2])=0
v([i1, i2, k])=7
v([i1, i2, j])=8.5
v([i1, i2, j, k])=8.5
v([i1, i2, i3])=0
v([i1, i2, i3, k])=9
v([i1, i2, i3, j])=9
v([i1, i2, i3, j, k])=12.5
A = job_matching_2([0.5, 1, 0])
B = [v([])=0, v([k])=0, v([j])=0, v([j, k])=0, v([i3])=0, v([i3|...])=4, v([...|...])=5, v(...)=5, ... =...|...]
Yes
?- min(U,(core(G,_,P),P=payoff([A,B,C,_,_]),U is A+B+C)).
No
*/
%-----------------------
% checking fact (1).
%-----------------------
/*
?- ch_u_cw(I).
I = on->off
Yes
?- set_model(job_matching_2([0.5,1,0])),
abolish(coop_0/3),transform_coop( Model),
current_model(A),coop(A,B),forall_nl_write(B).
v([])=0
v([k])=0
v([j])=0
v([j, k])=0
v([i3])=0
v([i3, k])=4
v([i3, j])=5
v([i3, j, k])=5
v([i2])=0
v([i2, k])=4
v([i2, j])=4
v([i2, j, k])=4
v([i2, i3])=0
v([i2, i3, k])=7.5
v([i2, i3, j])=7
v([i2, i3, j, k])=9
v([i1])=0
v([i1, k])=4
v([i1, j])=4
v([i1, j, k])=4
v([i1, i3])=0
v([i1, i3, k])=7
v([i1, i3, j])=7
v([i1, i3, j, k])=9
v([i1, i2])=0
v([i1, i2, k])=7
v([i1, i2, j])=7.5
v([i1, i2, j, k])=8
v([i1, i2, i3])=0
v([i1, i2, i3, k])=9
v([i1, i2, i3, j])=9
v([i1, i2, i3, j, k])=12
Model = job_matching_2([0.5, 1, 0])
A = job_matching_2([0.5, 1, 0])
B = [v([])=0, v([k])=0, v([j])=0, v([j, k])=0, v([i3])=0, v([i3|...])=4, v([...|...])=5, v(...)=5, ... =...|...]
Yes
?- min(U,(core(G,_,P),P=payoff([A,B,C,_,_]),U is A+B+C)).
U = 34
G = game(job_matching_2([0.5, 1, 0]))
P = payoff([10, 12, 12, 8, 6])
A = 10
B = 12
C = 12
Yes
?-
*/
% Summary of (1) and (2)
%-----------------------------------------
% Fact 2. For
% Model = job_matching_1([0.5,1,0])
% CW_Effect = off
% Ucw_Case = all zero
% the generated coop/2 yields No core outcome.
% Fact 1. For
% Model = job_matching_1([0.5,1,0])
% CW_Effect = on
% Ucw_Case = case_1
% the generated coop/2 yields a core outcome
% [2.5, 4, 4, 2, 1.5]
% which is minimal in the sense that
% it minimizes the total of offerd wages for workers.
%-----------------------
% checking fact (3).
%-----------------------
/*
?- set_model(job_matching_2([0,0,0])),
select_case_of_u_cw(_->case_2 ),
cwe_model_status( model:M,cwe:CWE, case:CASE).
u_cw(i1, [i1, i2], j, 0.3), 0.3\=0
u_cw(i2, [i1, i2], j, 0.2), 0.2\=0
u_cw(i2, [i2, i3], k, 0.3), 0.3\=0
u_cw(i3, [i2, i3], k, 0.2), 0.2\=0
M = job_matching_2([0, 0, 0])
CWE = on
CASE = case_2
Yes
?- abolish(coop_0/3),transform_coop( Model),
current_model(A),coop(A,B),forall_nl_write(B).
v([])=0
v([k])=0
v([j])=0
v([j, k])=0
v([i3])=0
v([i3, k])=4
v([i3, j])=4
v([i3, j, k])=4
v([i2])=0
v([i2, k])=4
v([i2, j])=4
v([i2, j, k])=4
v([i2, i3])=0
v([i2, i3, k])=7.5
v([i2, i3, j])=7
v([i2, i3, j, k])=8
v([i1])=0
v([i1, k])=4
v([i1, j])=4
v([i1, j, k])=4
v([i1, i3])=0
v([i1, i3, k])=7
v([i1, i3, j])=7
v([i1, i3, j, k])=8
v([i1, i2])=0
v([i1, i2, k])=7
v([i1, i2, j])=7.5
v([i1, i2, j, k])=8
v([i1, i2, i3])=0
v([i1, i2, i3, k])=9
v([i1, i2, i3, j])=9
v([i1, i2, i3, j, k])=11.5
Model = job_matching_2([0, 0, 0])
A = job_matching_2([0, 0, 0])
B = [v([])=0, v([k])=0, v([j])=0, v([j, k])=0, v([i3])=0, v([i3|...])=4, v([...|...])=4, v(...)=4, ... =...|...]
Yes
?- precision(A).
A = 0.25
Yes
?- display_goals(core(G,_,P),[G:P]).
game(job_matching_2([0, 0, 0])):payoff([14, 14, 14, 2, 2]);
game(job_matching_2([0, 0, 0])):payoff([13, 14, 13, 3, 3]);
game(job_matching_2([0, 0, 0])):payoff([12, 14, 12, 4, 4]);
No
?- solve_wep_1(P,Y).
init p:[ (1->0), (2->0), (3->0)];xds:[1, 2, 3]
p:[ (1->300), (2->300), (3->300)];xds:[1, 2, 3]->[]
equilibrium !
P = [ (1->300), (2->300), (3->300)]
Y = [ ([]->i1), ([]->i2), ([]->i3), ([2, 3]->j), ([1]->k)]
Yes
?- display_goals((a_star_0(V,Y),
nonempty_assignments(Y->Y1)),[V;Y1]).
11;[ ([1]->j), ([2, 3]->k)];
11;[ ([1, 2]->j), ([3]->k)];
11;[ ([1, 3]->j), ([2]->k)];
11;[ ([2]->j), ([1, 3]->k)];
11;[ ([2, 3]->j), ([1]->k)];
11;[ ([3]->j), ([1, 2]->k)];
No
?-
*/
%-----------------------
% checking fact (4).
%-----------------------
/*
?- set_model(job_matching_2([0,0,0])),
select_case_of_u_cw(_->case_2 ),
cwe_model_status( model:M,cwe:CWE, case:CASE).
u_cw(i1, [i1, i2], j, 0.3), 0.3\=0
u_cw(i2, [i1, i2], j, 0.2), 0.2\=0
u_cw(i2, [i2, i3], k, 0.3), 0.3\=0
u_cw(i3, [i2, i3], k, 0.2), 0.2\=0
M = job_matching_2([0, 0, 0])
CWE = on
CASE = case_2
Yes
?- ch_m_u_cw(I).
complete transformation.
I = u_f->u_f+u_cw
Yes
?- cwe_model_status( model:M,cwe:CWE, case:CASE).
u_cw(i1, [i1, i2], j, 0.3), 0.3\=0
u_cw(i2, [i1, i2], j, 0.2), 0.2\=0
u_cw(i2, [i2, i3], k, 0.3), 0.3\=0
u_cw(i3, [i2, i3], k, 0.2), 0.2\=0
M = job_matching_2([0, 0, 0])
CWE = off
CASE = case_2
Yes
?- display_goals((u(_,_,D),D>0)).
u(j, [3], 4+0+0), 4+0+0>0
u(j, [2], 4+0), 4+0>0
u(j, [2, 3], 7+0), 7+0>0
u(j, [1], 4+0), 4+0>0
u(j, [1, 3], 7+0), 7+0>0
u(j, [1, 2], 7+0+0.5), 7+0+0.5>0
u(j, [1, 2, 3], 9+0), 9+0>0
u(k, [3], 4+0), 4+0>0
u(k, [2], 4+0), 4+0>0
u(k, [2, 3], 7+0+0.5), 7+0+0.5>0
u(k, [1], 4+0+0), 4+0+0>0
u(k, [1, 3], 7+0), 7+0>0
u(k, [1, 2], 7+0), 7+0>0
u(k, [1, 2, 3], 9+0), 9+0>0
D = _G162
Yes
?- display_non_zero_coworkers_effects.
j;[1, 2];7+0+0.5+0.5;
k;[2, 3];7+0+0.5+0.5;
No
?- a_star_0(V,Y),
nonempty_assignments(Y->Ya),nl,write(V;Ya),fail.
11.5;[ ([1]->j), ([2, 3]->k)]
11.5;[ ([1, 2]->j), ([3]->k)]
No
?- solve_wep_1(P,Y),
nonempty_assignments(Y->Ya).
init p:[ (1->0), (2->0), (3->0)];xds:[1, 2, 3]
p:[ (1->150), (2->150), (3->150)];xds:[1, 2, 3]->[2]
p:[ (1->150), (2->200), (3->150)];xds:[2]->[1, 2, 3]
p:[ (1->300), (2->350), (3->300)];xds:[1, 2, 3]->[]
equilibrium !
P = [ (1->300), (2->350), (3->300)]
Y = [ ([]->i1), ([]->i2), ([]->i3), ([1, 2]->j), ([3]->k)]
Ya = [ ([1, 2]->j), ([3]->k)]
Yes
?- abolish(coop_0/3),transform_coop( Model),e(B).
current_model(A),coop(A,B),forall_nl_write(B).
v([])=0
v([k])=0
v([j])=0
v([j, k])=0
v([i3])=0
v([i3, k])=4
v([i3, j])=4
v([i3, j, k])=4
v([i2])=0
v([i2, k])=4
v([i2, j])=4
v([i2, j, k])=4
v([i2, i3])=0
v([i2, i3, k])=7.5
v([i2, i3, j])=7
v([i2, i3, j, k])=8
v([i1])=0
v([i1, k])=4
v([i1, j])=4
v([i1, j, k])=4
v([i1, i3])=0
v([i1, i3, k])=7
v([i1, i3, j])=7
v([i1, i3, j, k])=8
v([i1, i2])=0
v([i1, i2, k])=7
v([i1, i2, j])=7.5
v([i1, i2, j, k])=8
v([i1, i2, i3])=0
v([i1, i2, i3, k])=9
v([i1, i2, i3, j])=9
v([i1, i2, i3, j, k])=11.5
Model = job_matching_2([0, 0, 0])
A = job_matching_2([0, 0, 0])
B = [v([])=0, v([k])=0, v([j])=0, v([j, k])=0, v([i3])=0, v([i3|...])=4, v([...|...])=4, v(...)=4, ... =...|...]
Yes
?-
*/
% Summary of (3) and (4)
%-----------------------------------------
% Fact 3. For
% Model = job_matching_2([0,0,0])
% CW_Effect = on
% Ucw_Case = case_2
% the generated coop/2 yields a core outcome
% [3, 3.5, 3, 1, 1],
% but the equilibrium price solve_wep_1/2 was
% [3, 3, 3].
% Fact 4. For
% Model = job_matching_2([0,0,0])
% CW_Effect = off
% Ucw_Case = case_2
% the equilibrium price solve_wep_1/2 is
% [3, 3, 3],
% and the efficient allocation plan
% [ ([1, 2]->j), ([3]->k)] or
% [ ([1]->j), ([2, 3]->k)]
% with the total surplus 11.5.
% NOTE:
% The fact 4 above implies the core equivalence.
% Because by using ch_m_u_cw/1 we set zero for
% each worker, as well as each firm,
% in effect it is equivalent of assuming
% the taxes/subsidies schemes (Ma(2001), Shapley
% and Subik(1969))such that
% t(j, Si; i)= u(j, Si; i),
% so it suffices the result.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mathematical tools
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
positive_number_1(U,P,N):-
IP is integer(U / P),
length(L,IP),
nth1(K,L,_),
N is K*P.
positive_number(U,P,_):-
\+ clause(positive_number_0(U,P,_),true),
generate_positive_numbers(U,P),
fail.
positive_number(U,P,N):-
clause(positive_number_0(U,P,N),true).
:-dynamic positive_number_0/3.
generate_positive_numbers(U,P):-
write('start generating positive numbers':U:P),
abolish(positive_number_0/1),
forall(
positive_number_1(U,P,N),
assert(positive_number_0(U,P,N))
).
% cited from math1.pl
%---------------------------------------------------%
% revised: 21 Sep 2005
% rename. sumof/3->sumall/3,
sumall(X,Goal,S):-
findall(X,Goal,Z),
sum(Z,S).
sum([],0).
sum([X|Members],Sum):-
sum(Members,Sum1),
%number(X),
Sum is Sum1 + X.
product([],1).
product([X|Members],Z):-
product(Members,Z1),
%number(X),
Z is Z1 * X.
product_sum([],[],[],0).
product_sum([P|Q],[A|B],[E|F],V):-
length(Q,N),
length(B,N),
product_sum(Q,B,F,V1),
E is P * A,
V is V1 + E.
% max,min
% ----------------------------------------------------------- %
max_of(X,[X]).
max_of(Z,[X|Y]):-
max_of(Z1,Y),
(X > Z1 -> Z=X; Z=Z1).
min_of(X,[X]).
min_of(Z,[X|Y]):-
min_of(Z1,Y),
(X < Z1 -> Z=X; Z=Z1).
% another rule for max / min without backtrack
amax_of(A,L):-
setof(X,(member(X,L),number(X)),S),
last(A,S).
amin_of(A,L):-
setof(X,(member(X,L),number(X)),[A|_]).
% a solver : maximization of goal wrt arguments
% ----------------------------------------------------------- %
% X: the objective variable,
% Goal: the objective function and constraints,
min(X,Goal):-
max(Z,(Goal,Z is -X)).
max(X,Goal):-
max_1(X,Goal).
%max_2(X,Goal).
%max_3(X,Goal).
% This code is not fast in simple iterations. (see demo below.)
% But the performance was robust for solve_wep_1/2 on auction_1_r3.
max_1(X,Goal):-
setof((X,Goal),Goal,Z),
member((X,Goal),Z),
\+ (
member((Y,_),Z),
Y > X
).
% The following codes works fastly in simple predicates. (see demo below.)
% But it was not effective for my solve_wep_1/2.(by g. stack over)
max_2(X,Goal):-
setof((Goal,W),(Goal,W is -X),Z),
select_minimal(Z,Goal),
member((Goal,Value),Z),
X is -Value.
% select_minimal: a code in Shoham's book (the section of id3)
%-----------------------------------------
select_minimal( [FirstPair|Remain], Best):-
select_minimal_0( Remain, FirstPair, Best).
select_minimal_0( [ ], (A, _), A). % A is the survived.
select_minimal_0( [ (A, Value) | More ], ( _, Incumbent), Best) :-
Value < Incumbent,
!,
select_minimal_0( More, (A, Value), Best).
% allowing local minima.
% whether this or not would affects solve_wep_1/2.
select_minimal_0( [ (A, Value) | More ], ( _, Incumbent), Best) :-
Value = Incumbent,
select_minimal_0( More, (A, Value), Best).
select_minimal_0( [ _P | More ], (A, Value), Best) :-
select_minimal_0( More, (A, Value), Best ).
% another solver :
%-----------------------------------------
:- dynamic temp_max/3,uid_max/2.
max_3(X,G):-
clause(temp_max(_,X,G),true),
!.
max_3(X,G):-
\+ clause(temp_max(_,X,G),true),
max_3(_,X,G).
max_3(Mid,X,G):-
get_time(Mid),
init_max(Mid,(X,G)),
fail.
max_3(Mid,X,Goal):-
Goal,
uid_max(Mid,(X,Goal)),
temp_max(Mid,Y,_),
(X > Y->update_max(Mid,'>',X,Goal);true),
(X = Y->update_max(Mid,'=',X,Goal);fail),
fail.
max_3(Mid,X,G):-
uid_max(Mid,(X,G)),
temp_max(Mid,X,G).
init_max(Mid,(X,G)):-
forall(retract(temp_max(Mid,_,_)),true),
assert(temp_max(Mid,-10^15,_)),
assert(uid_max(Mid,(X,G))).
update_max( Mid, '>',X, G):-
retract( temp_max(Mid, _, _)),
assert( temp_max(Mid, X, G)).
update_max( Mid, '=',X, G):-
\+ clause( temp_max(Mid, X, G),true),
assert( temp_max(Mid, X, G)).
% demo
%---------------------------------------------------%
% comparing the peformances.
/*
?- stopwatch(
max_1(X,positive_number_1(10000,1,X)),T).
% time elapsed (sec): 25.063
X = 10000
T = 25.063
Yes
?- stopwatch(
max_2(X,positive_number_1(10000,1,X)),T).
% time elapsed (sec): 0.063
X = 10000
T = 0.063
Yes
?- stopwatch(
max_3(X,positive_number_1(10000,1,X)),T).
% time elapsed (sec): 0.062
X = 10000
T = 0.062
Yes
?- max_1(X,positive_number_1(100000,1,X)).
ERROR: Out of global stack
?- max_2(X,positive_number_1(100000,1,X)).
ERROR: Out of global stack
?- stopwatch(
max_3(X,positive_number_1(100000,1,X)),T).
% time elapsed (sec): 0.672
X = 100000
T = 0.672
Yes
?-
*/
% set theoretical operations
%---------------------------------------------------%
% cited from set.pl
bag0([],_A,0).
bag0([C|B],A,N):-
length([C|B],N),
bag0(B,A,_N1),
member(C,A).
zeros(Zero,N):-bag0(Zero,[0],N).
ones(One,N):-bag0(One,[1],N).
list_projection([],[],[]).
list_projection([X|Y],[_A|B],C):-
X = 0,
list_projection(Y,B,C).
list_projection([X|Y],[A|B],[A|C]):-
X = 1,
list_projection(Y,B,C).
c_list_projection([],[],[]).
c_list_projection([X|Y],[_A|B],C):-
X = 1,
c_list_projection(Y,B,C).
c_list_projection([X|Y],[A|B],[A|C]):-
X = 0,
c_list_projection(Y,B,C).
subset_of(A,N,As):-
var(A),
length(As,L),
length(D,L),
list_projection(D,As,B),
length(B,N),
sort(B,A).
subset_of(A,N,As):-
\+ var(A),
length(A,N),
subset(A,As).
% complement and symmetric complement
% ----------------------------------------------------------- %
complement(AC,A,As):-
subset_of(A,_N,As),
subtract(As,A,AC).
complement_1(AC,A,As):-
list_projection(P,As,A),
c_list_projection(P,As,AC).
symmetric_complement(AC,A,As):-
list_projection(P,As,A),
c_list_projection(P,As,AC),
list_projection(P1,As,AC),
P @< P1.
intersection_of_lists([],_).
intersection_of_lists([X|H],Z):-
intersection_of_lists(H,Y),
intersection(X,Y,Z).
asymmetric_differences(A,B,D):-
subtract(A,B,D1),
subtract(B,A,D2),
D=(D1,D2).
set_equivalence(A,B):-
asymmetric_differences(A,B,([],[])).
% permutation.
% ----------------------------------------------------------- %
% reference:
% L. Sterling and E. Shapiro (1994).
% The Art of Prolog. 2nd edition. MIT Press, p.68.
permutation([],[]).
permutation(Q,[A|R]):-
select(A,Q,Q1),
% subtract(Q,[A],Q1) is not valid for multiple-occurence.
permutation(Q1,R).
% allocation
% ----------------------------------------------------------- %
% cited from math1.pl
allocation(N,A,[X|Y]):-
allocation(N,A,A,[X|Y]).
allocation(0,_,0,[]).
allocation(N,A,B,[X|Y]):-
integer(A),
length([X|Y],N),
allocation(_N1,A,B1,Y),
K is A - B1 + 1,
length(L,K),
nth0(X,L,X),
B is B1 + X.
% generating partitons
%-----------------------------------------
partition([S],1,S):-
\+ var(S),
length(S,_).
partition([H|H1],N,S):-
\+ var(S),
length(S,_),
symmetric_complement(H,S1,S),
\+ member([], [H,S1]),
partition(H1,N1,S1),
N is N1 + 1,
all_elements(S1,_,H1).
all_elements([],0,[]).
all_elements(A,N,[H|S]):-
\+ var(S),
length(S,_),
\+ var(H),
length(H,K),
all_elements(B,N1,S),
append(H,B,A),
N is N1 + K.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% tools for output and statistics
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% cited from mainly : menu.pl
% display specified terms separated by semicorons
% for each successful goals.
%--------------------------------
% added: 21 Aug 2005.
% game(G,value,B,C),nl,write(B:C),fail.
% a generalization.
display_goals( Goal, Values):-
clause(Goal,_),!,
length(Values,_),
forall( Goal,
(
nl,
forall(member(X,Values),
(write(X),write('; '))
)
)
),
bagof(X,(member(X,Values),X=complete),Values).
% display all successful goals (with the count).
%--------------------------------
display_goals(G):-
(\+ var(G)->true;G=empty),
forall(G,(nl,write(G))).
display_goals(_).
% goal counting.
%--------------------------------
:- dynamic temp_count/1.
count_goals(_G,0):-
abolish(temp_count/1),
assert(temp_count(0)),
nl,
write('counter initialized.'),
nl,
fail.
count_goals(G,N1):-
G,
update_counter(N1),
% for debug % write([N1,G]),
fail.
count_goals(_G,N):-
temp_count(N),
nl,
write(N),
tab(1),
write('successful goals have been found.').
update_counter(N1):-
retract(temp_count(N)),
N1 is N +1,
assert(temp_count(N1)),
!.
% iteratively writing the goals
%--------------------------------
forall_write(A):- forall(member(X,A),write(X)).
forall_nl_write(A):- forall(member(X,A),(nl,write(X))).
forall_write_goals(A,B):- B,nl,write(A),fail.
forall_write_goals(_,_):- nl,write(complete).
% Save data to a file
%--------------------------------
tell_goal(File,G):-
(current_stream(File,write,S0)->close(S0);true),
open(File,write,S),
tell(File),
nl,
tstamp('% file output start time ',_),
nl,
write('%---------- start from here ------------%'),
nl,
G,
nl,
write('%---------- end of data ------------%'),
nl,
tstamp('% file output end time ',_),
tell(user),
close(S),
% The following is to cope with the duplicated stream problem.
(current_stream(File,write,S1)->close(S1);true).
% save all successful goals to file.
%--------------------------------
tell_goal(File,forall,G):-
G0 = (nl,write(G),write('.')),
G1 = forall(G,G0),
tell_goal(File,G1).
% the conditionalized version
% Aug 2003.
tell_goal(File,forall_such_that,G,Condition):-
% G should be occurred in the Condition.
WRITE = (nl,write(G),write('.')),
G1 = forall(Condition,WRITE),
tell_goal(File,G1).
% time stamp
%--------------------------------
tstamp(no,T):-
get_time(U),
convert_time(U,A,B,C,D,E,F,_G),
T = [date(A/B/C), time(D:E:F)],
nl.
tstamp(Word,T):-
\+ var(Word),
Word \= no,
get_time(U),
convert_time(U,A,B,C,D,E,F,_G),
T = [date(A/B/C), time(D:E:F)],
% format('~`.t~t~a~30|~`.t~t~70|~n',[Word]),
write((Word,T)),
nl.
% measuring time consumption
%--------------------------------
stopwatch_0(Goal,TD):-
get_time(TS),
Goal,
get_time(TF),
TD is TF - TS.
stopwatch(Goal,TD):-
stopwatch_0(Goal,TD),
nl,
write('% time elapsed (sec): '),
write(TD),
nl.
stopwatch_of_iterated_goals(_Goal,0,0,Display):-
rule_of_display_number_in_stopwatch(Display,JOB),
JOB.
stopwatch_of_iterated_goals(Goal,TD,Iteration,Display):-
number(Iteration),
Iteration > 0,
init_count_of_display,
rule_of_display_number_in_stopwatch(Display,JOB),
stopwatch(
forall(
(
Goal, %write(Goal),
update_count_of_display(K),
(K>Iteration->!,fail;true)
),
JOB
),
TD
).
rule_of_display_number_in_stopwatch(no,true):-
!.
rule_of_display_number_in_stopwatch(yes,display_counter).
% a display of counter for iterated goals.
%---------------------------------------
:- dynamic temp_count_of_display/1.
temp_count_of_display(0).
init_count_of_display:-
abolish(temp_count_of_display/1),
assert(temp_count_of_display(0)).
update_count_of_display(K):-
retract(temp_count_of_display(K0)),
K is K0 + 1,
assert(temp_count_of_display(K)).
update_and_display_counter:-
update_count_of_display(_),
display_counter.
display_counter:-
temp_count_of_display(K),
nl,
write([K]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% model management tools (MMT)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- dynamic precision/1.
precision(1).
change_precision(New):-
change_precision(_,New).
change_precision(Current,New):-
member(New,[0.25, 0.5, 1, 0.025, 0.1]),
retract(precision(Current)),
assert(precision(New)).
:- dynamic u/3, agent/1, item/1, e/3, current_model/1,
owner_of_unsold_items/1.
model_predicate( u/3).
model_predicate( agent/1).
model_predicate( item/1).
model_predicate( e/3).
:- dynamic set_of_all_agents/1,set_of_all_items/1.
set_model(M):-
model(M,
agents:N,
items:O,
'owner of unsold item': Doi,
endowments:E,
utilities:U
),
% ---% nl,write( 'now setting the model':M),
abolish( current_model/1),
assert( current_model(M)),
abolish( set_of_all_agents/1),
assert( set_of_all_agents(N)),
abolish( set_of_all_items/1),
assert( set_of_all_items(O)),
abolish( owner_of_unsold_items/1),
assert( owner_of_unsold_items(Doi)),
forall( model_predicate(MP), abolish(MP)),
forall( member(I,N), assert(agent(I))),
forall( member(X,O), assert(item(X))),
forall( (agent(J),member(e(J,Cash,Y),E)), assert(e(J,Cash,Y))),
forall( (agent(J),bundle(S),S\=[],member(u(J,S)=V,U)), assert(u(J,S,V))),
param_of_NFL_condition(NFL),
impose_NFL_condition(NFL).
set_model(M):-
\+ clause( model(M,_,_,_,_,_),_),
nl,
write('Sorry, Sir. I could not find it in model base.').
% no-free-lunch condition
:- dynamic param_of_NFL_condition/1.
param_of_NFL_condition( yes).
% the following invoked by set_model/1.
impose_NFL_condition(no).
impose_NFL_condition(yes):-
forall( agent(J), assert( u(J,[],0) ) ).
ask_user_about_NFL:-
abolish(param_of_NFL_condition/1),
nl,write('impose NFL condititon ? (y/n) >'),
read(User),
(member(User,[y,'Y',yes,'Yes','YES'])->W=yes;W=no),
assert(param_of_NFL_condition( W)),
!.
display_model(M):-
(var(M)->current_model(M);true),
model(M,Agents,Items,Doi, _:Endowments,_:Utilities),
nl,write('****** model *******'),
nl,write(M),
forall(member(P,[Agents,Items,Doi]),(nl,write(P))),
nl,write('endowmens (agent, cash, items):'),
forall(member(X,Endowments),(nl,tab(2),write(X))),
nl,write('utility functions:'),
forall(member(V,Utilities),(nl,tab(2),write(V))).
% for models without a single agent.
display_model(M):-
(var(M)->current_model(M-Jr);true),
model(M,agents:N,Items,Doi, _:Endowments,_:Utilities),
subtract(N,[Jr],Nr),
set_of_all_agents(Nr),
nl,write('****** model *******'),
nl,write(M-Jr),
forall(member(P,[agents:Nr,Items,Doi]),(nl,write(P))),
nl,write('endowmens (agent, cash, items):'),
forall((member(X,Endowments),X\=e(Jr,_,_)),(nl,tab(2),write(X))),
nl,write('utility functions:'),
forall((member(V,Utilities),V\=(u(Jr,_)=_)),(nl,tab(2),write(V))).
% for models retracted agents in a colation.
display_model(M):-
(var(M)->current_model(M-S);true),
model(M,agents:N,Items,Doi, _:Endowments,_:Utilities),
set_of_all_agents(CurrentAgents),
subtract(N,S,CurrentAgents),
nl,write('****** model *******'),
nl,write(M-S),
forall(member(P,[agents:CurrentAgents,Items,Doi]),(nl,write(P))),
nl,write('endowmens (agent, cash, items):'),
forall(
(member(X,Endowments),X=e(J,_,_),\+member(J,S)),
(nl,tab(2),write(X))
),
nl,write('utility functions:'),
forall(
(member(V,Utilities),V=(u(J,_)=_),\+member(J,S)),
(nl,tab(2),write(V))
).
% model without a single agent
%---------------------------------------
% for computing the VCG payments
set_model_without_agent(J,M):-
set_model_without_coalition([J],M).
set_model_without_coalition(S,M):-
current_model(M-S),
!.
set_model_without_coalition(S,M):-
model(M,
agents:N,
items:O,
'owner of unsold item': Doi,
endowments:E,
utilities:U
),
% ---% nl,write( 'now setting the model':M),
coalition(S),
subtract(N,S,Nr),
abolish( current_model/1),
assert( current_model((M-S))),
abolish( set_of_all_agents/1),
assert( set_of_all_agents(Nr)),
abolish( set_of_all_items/1),
assert( set_of_all_items(O)),
abolish( owner_of_unsold_items/1),
assert( owner_of_unsold_items(Doi)),
forall( model_predicate(MP), abolish(MP)),
forall( member(I,Nr), assert(agent(I))),
forall( member(X,O), assert(item(X))),
forall( (agent(J),\+member(J,S),member(e(J,Cash,Y),E)), assert(e(J,Cash,Y))),
forall(
(
agent(J),
bundle(B),
B\=[],
member(u(J,B)=V,U),
\+ member(J,S)
),
assert(u(J,B,V))
),
param_of_NFL_condition(NFL),
impose_NFL_condition(NFL).
set_model_without_coalition(_,M):-
\+ clause( model(M,_,_,_,_,_),_),
nl,
write('Sorry, Sir. I could not find it in model base.').
%%%% game assertion %%%% (abolished)
% see game model section.
%---------------------------------------
% model swithing tools (MST/MMT)
%---------------------------------------
% changing function f
% (for solve_wep_1 the English auction game algorithm)
%---------------------------------------
% added: 19 Sep 2005
% You can try out an earlier rule of auction algorithm
% solve_wep_1/2 and its belonging functions.
% Before query a solve_wep_1/2, by means of ch_f/1
% once again, a flip-flop, you can switch the
% version of the rule.
:- dynamic temp_f/3.
ch_f( use: f1):-
\+ clause( temp_f(J,A,B), _),
clause( f(J,A,B),T),
assert( (temp_f(J,A,B):-T)),
abolish( f/3),
clause( f_1(J,A,C),T1),
assert( (f(J,A,C):-T1)).
ch_f( use: f):-
clause( temp_f(J,A,B),T),
abolish( temp_f/3),
abolish( f/3),
assert( (f(J,A,B):-T)).
% background parameter for preference analysis
%-----------------------------------------
% revised: 19 Sep 2005
:- dynamic option_for_analyze_preferences/1.
option_for_analyze_preferences( given_price).
%option_for_analyze_preferences( variate_prices).
% a flip-flop
ch_apo( OPT->OPT1):-
retract(option_for_analyze_preferences( OPT)),
member( (given_price,variate_price),
[(OPT,OPT1),(OPT1,OPT)]
),
assert(option_for_analyze_preferences( OPT1)).
% switching u_cw/5 on/off the co-workers effect
%-----------------------------------------
% ch_ucw/1 a flip-flop of the parameter
% for the modeling with/without co-workers effect
% given the current model.
:- dynamic option_for_coworkers_effect/1.
option_for_coworkers_effect( on).
%option_for_coworkers_effect( off).
:- dynamic temp_u_cw/5.
% ch_u_cw/1 merely move/add them to the temporary clauses
% because of the fact-based nature u_cw/5.
% `setting each u_cw/5 to zero' option
ch_u_cw( on ->off):-
option_for_coworkers_effect( on),
current_model( M),
Ucw = u_cw( M, J, C, I, U),
Temp = temp_u_cw( M, J, C, I, U),
\+ clause( Temp, _),
clause( Ucw, true),
assert( Temp),
retract( Ucw),
fail.
ch_u_cw( on ->off):-
option_for_coworkers_effect( on),
abolish( option_for_coworkers_effect/1),
assert( option_for_coworkers_effect(off)).
% recovery. (re)activate co-workers effect.
ch_u_cw( off -> on):-
option_for_coworkers_effect( off),
current_model( M),
clause( temp_u_cw( M, J, C, I, U), true),
retract( temp_u_cw( M, J, C, I, U)),
assert( u_cw( M, J, C, I, U)),
fail.
ch_u_cw( off -> on):-
option_for_coworkers_effect( off),
abolish( option_for_coworkers_effect/1),
assert( option_for_coworkers_effect(on)).
% (enforcing or confirmation).
ch_u_cw( B -> A):-
\+ var(A),
ch_u_cw_0( B -> A),
option_for_coworkers_effect( B).
ch_u_cw_0( on -> on).
ch_u_cw_0( off -> off).
% case switcher for u_cw
%-----------------------------------------
% case_for_u_cw/2 => (MMT)
:- dynamic case_for_u_cw/2.
case_for_u_cw( case_1, on).
case_for_u_cw( case_2, off).
select_case_of_u_cw( C->D):-
case_for_u_cw( C, on),
forall(
retract( case_for_u_cw( E, on)),
assert( case_for_u_cw( E, off))
),
case_for_u_cw( D, off),
D \= C,
retract( case_for_u_cw( D, _)),
assert( case_for_u_cw( D, on)).
% switching the modeling of co-workers effect
%-----------------------------------------
ch_m_u_cw( U_old -> U_new):-
ch_m_u_cw( U_old -> U_new, _).
ch_m_u_cw( u_f -> u_f + u_cw, Cmt):-
Cmt ='new u/3 with co-workers effect',
option_for_coworkers_effect( on),
H = product_of_firm_workers_coalition,
Product =..[H, Firm,_,Coworkers1,Qc+Uc,_],
forall(
(
firm( Firm),
Product
),
(
retract( u( Firm, Coworkers1, _)),
assert( u( Firm, Coworkers1, Qc+Uc))
)
),
ch_u_cw( on -> off),
nl,
write( 'complete transformation.').
ch_m_u_cw( u_f + u_cw -> u_f, Cmt):-
Cmt = 'recovered u/3 without co-workers effect',
option_for_coworkers_effect( off),
ch_u_cw( off -> on),
current_model(M),
set_model(M).
% summary of modeling satus of co-workers effect
%-----------------------------------------
cwe_model_status( model:M,cwe:CWE, case:CASE):-
current_model(M),
option_for_coworkers_effect( CWE),
case_for_u_cw(CASE,on),
display_goals((u_cw(_,_,_,D),D\=0)).
display_non_zero_coworkers_effect.
display_non_zero_coworkers_effects:-
display_goals(
(
firm(Firm),
H = product_of_firm_workers_coalition,
Product =..[H, Firm,_,Coworkers1,Qc+Uc,_],
Product,
Uc \= 0
),
[Firm;Coworkers1;Qc+Uc]
).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% startup script
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
hl:-
nl,length(L,50),forall(member(_,L),write('=')).
explain_me:-
me(T,T1,P,D,A),
hl,
nl,tab(2),write('title ':T),
nl,tab(2),write( T1),
nl,tab(2),write('code ':P),
nl,tab(2),write('date ':D),
nl,tab(2),write('author ':A),
hl.
% default model : job_matching_1([0,0,0])
:- explain_me,
abolish( temp_agtsbst/2),
abolish( temp_max/3),
abolish( uid_max/2),
%ask_user_about_NFL,
%abolish( coop_0/3),
set_model(auction_1).
% demo
%-----------------------------------------
/*
?- [price].
==================================================
title :assignment market games on prolog
code :price.pl (developed on SWI-prolog 5.0.9)
date :2005.8.19-26
author :By Kenryo INDO
==================================================
% price compiled 0.00 sec, 75,800 bytes
Yes
?- set_model(auction_1).
Yes
?- solve_wep_1(P,Y).
init p:[ (a->0), (b->0)];xds:[a, b]
p:[ (a->300), (b->300)];xds:[a, b]->[b]
p:[ (a->300), (b->400)];xds:[b]->[a, b]
p:[ (a->600), (b->700)];xds:[a, b]->[] equilibrium!
I can`t update prices, because
there is no excess demand item.
P = [ (a->600), (b->700)]
Y = [ ([]->i), ([a]->j), ([b]->k)] ;
No
?- pp(A). % the price vector for items.
A = [ (a->600), (b->700)]
Yes
?- xx(I). % the allocation of items.
I = [ (a->j), (b->k)]
Yes
?- d(J,A,B). % the individuals demand set under the price.
J = i
A = [ (a->600), (b->700)]
B = [[]] ;
J = j
A = [ (a->600), (b->700)]
B = [[a], [b]] ;
J = k
A = [ (a->600), (b->700)]
B = [[a, b], [b]] ;
No
?- wep(P,Y). % the Walrasian price vector and the equilibrium outcome.
P = [ (a->600), (b->700)]
Y = [ ([]->i), ([a]->j), ([b]->k)]
Yes
?- xds(P,X). % the excess demand set X : the value of max f.
P = [ (a->600), (b->700)]
X = []:0 ;
No
?-
*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% related literature:
% an introductory reading
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 26-30 Aug 2005
% revised: 8 Sep 2005
% Some basic notations
%-----------------------------------------
% (skim if the reader familiar with the theory)
% Let O=[a,b,...] a finite set of `item's
% and I=[1,...,n] a finite set of `agent's.
% P=[Pa,Pb,...] a point of E^#O is called price (price vector).
% (For convenience, suppose that a special agent identified by, 0,
% the disposal or inventory, is already included in the set I.)
% A subset of G, including empty set, called a `bundle.'
% A partition, X=[X1,...,Xn], of G would be called `allocation'
% if it can be interpreted so that each bundle in Xi corresponds
% to the ownership of agent i.
% We use a notation the payment of agent i under the pair (P,X),
% as the literature, where represents summation of A over B.
% Precisely, the dot product of,
% P, a price vector and, B(Xi,X), a bit sequence in [0,1]^n
% which is the indicator vector of Xi.
% Similar for each agents, we get, , the vector of payments.
% Each agent has preference over bundles which can be represented
% by, u_i(Y), the utility of agent i for a bundle Y.
% So the net value of agent i under an allocation (P,X)
% is computed as v_i(Y,P):= u_i(Yi) -.
% An allocation is called `efficient', or `competitive', if it
% maximizes the total net utility aggregated over the agent set.
% We say a competitive price vector (or Walrasian price vector )
% supports the efficient allocation when each i-th
% element of the partition is the best bundle for the i-th agent.
% A competitive equilibrium, (P, X), is a pair of price vector and
% the partition supported by it, and =0.
% Cooperative game with indivisibilities and core
%-----------------------------------------
% (skim if the reader familiar with the theory)
% I provide rather informally the definitions in brief.
% More precisely, the reader should refer Shapley and Scarf(1974),
% Kaneko(1982), or other substantial text book of game theory.
% def. game:- characteristic function defined over
% subsets of N= [1,2,....,n], the set of players,
% other than enction defined over
% subsets of N= [1,2,....,n], the set of players,
% other than empty set [].
% def. characteristic function :-
% % game of with side payments (transferable utility)
% v: 2^N -[] -> R.
% def. characteristic function (transferable utility):-
% % game of with side payments (transferable utility)
% V: 2^N -[] -> 2^(E^n), E^n is the payoff space
% (1) V(S) is closed, (2) if x is not in V(S), there is at least
% one j in S who's payoff is improved upon for any y in V(S).
% (3) (V(S)- U_i_inS int(V([i])) meet E^S is noempty and bounded.
% def. feasibility :-
% x is included in V(N), where N is all agents.
% imputation :-
% feasible and indivisually rational vector,
% i.e., allocation x in ( V(N)- U_i int(V([i])).
% def. core :-
% feasible allocation which can not
% be (strictly) improved upon by any coalition S,
% i.e., in interior of V(S).
% Alternatively,
% core :- x is in V(N)- U_s int V(S).
% p.s. transferable utility assumption:
% cases of additively separable utility (no income effect).
% assginment games with sidepayments, V(i, C) = v(C).
% See Kaneko(1982), p.208 and p.222.
% About market game analysis
%-----------------------------------------
% Game analysis of market economy with indivisible goods
% was a generalization of the prevailed normative thinking that
% decentralization by prices is good mechanism which attains
% an efficient resource allocation.
% So to say, the efficient allocation is expected to be a reasonable
% outcome of the game played by the participants of market
% with prices as the unified signal.
% Conventionally with the relevant coalitional form games,
% the existence of competitive equilibrium was argued via
% the existence and the coincidence of `core'
% which is the set of `cannot improved upon' outcomes.
% (=>see game analysis section)
% (Shapley and Scarf(1974), Shapley and Shubik(1972), Kaneko(1982),
% Quinzii(1986), Gale(1986), Ma(1999),Gul and Stacchetti(1999)).
% Not along these vein, other more algorithm-oriented research
% matching /auction market game analysis originated in Gale and Shapley(1962),
% has been integrated into the market game analysis (Crawford and Knoer(1981),
% Kelso and Crawford(1982), Leonard(1983), Demange et al.(1986),
% Kaneko and Yamamoto(1986),Bikhchandani et al.(2002), Ausubel(2004)).
% About known theorems
%-----------------------------------------
% It had proven that the set of monotone and gross substitutes (GS)
% preferences is the maximal
% class including of `unit demand' preferences where
% competitive equilibrium (Walrasian equilibrium) exists
% (see Gul and Stacchetti(1999), Kelso and Crawford(1982)).
% Assuming monotone utility functions, Gul and Stacchetti (1999) provide
% equivalent conditions to the GS condition, the single improvement (SI)
% condition and the no-complementarity (NC) condition, which have both
% the natural economic interpretation and the lower complexity than GS .
% For many classical assignment / exchange models the VCG prices
% coincides with the minimal of the lattice of Walrasian prices,
% which naturally interpreted as the dual variables
% (i.e., shadow prices, or marginal product)
% (Leonard(1983), Demange et al.(1986), Gul and Stacchetti(1999), etc)
% On the behalf of introducing the later part of this article,
% I will summarizes the result with respect to multi-item auctions.
% In the literature of economics, some dynamic auctions expected to
% converge into the minimal Walrasian price vector.
% note: the price vector 'minimal' in the sense that
% every other Walrasian price vector weakly dominates it.
% And it implements VCG payments in many useful preference models
% despite the impossibility of ascending auction has proved
% (Gul and Stachetti, 2000).
% It is conjectured by Bikchandani et al. that we can design
% a mechanism which implements the VCG prices as an
% ascending auction is possible
% if and only if their 'agents are substitutes'
% condition is satisfied (Bikhchandani et al., 2002).
% Also the theory has also links to both the duality theorem of
% linear programming and the primal-dual algorithms in
% combinatorial optimization theory (Shapley and Shubik(1972),
% Leonard(1983), Bikhchandani and Mamer(1997), Bikhchandani et al. (2002)).
% Lastly, we will refer about the bounded rationality perspective
% its relation to auction mechanisms.
% About dynamic (ascending) auction and VCG prices
%-----------------------------------------
% As a normative thought of economics, if not exact in discrete,
% heterogeneous, multi-item environment, price based mechanisms
% (such as a market or an auction)
% expectedly leads to the effective allocation.
% The formal approach first appeared in Crawford and Knoer(1981),
% `salary adjustment process' of Kelso and Crawford(1992),
% and `exact' and `approximate' auctions of Demange et al.(1986).
% English auction algorithm by Gul and Stacchetti(2000) is
% a generalization by using excess demand set.
% These auctions can be seen as primal-dual algorithms,
% variants of the discrete generalization of a classic one,
% Kuhn's Hangarian method
% for assignment problem, with Hall's theorem.
% As well known, the VCG (Vickrey-Clarke-Groves)
% mechanism provides incentive compatibility and yields
% an efficient outcome in sealed bid auctions. Further,
% from which other demand revealing mechanisms has been developed.
% These mechanisms commonly enforce each bidder a fee
% as following. (Also see the VCG mechanism section of my code.)
% definition: VCG payment q_i(Xi) is
% q_i(Xi) = V(N-i) - Sum_other_than_i(u_j(a*)),
% where a* is efficient and V(S):= max Sum_over_S(u_j(a)).
% for a subset S of N.
% The intended applications of VCG mechanism are, for example,
% the performance measurement in business/industrial enterprise,
% the congestion control of traffic of network
% (including internet TCP/IP protocol), as well as the
% sealed bid auction originally the studied by Vickrey in 1961 paper,
% the public project selection (such as providing public goods),
% by Clarke in 1972 paper, the evaluating and budgeting team
% performance by Groves in 1978 paper.
% By rule of VCG payment, V(N)-V(N-j), the marginal product of
% a bidder equals his or her net benefit
% (See Bikhchandani et al.(2002)).
% The VCG payment q_i(Xi) gives a lower bound of that of
% Walrasian equilibrium (p, X). That is q_i(Xi) =<
% (See Gul and Stacchetti(1999)).
% In the English auction game proposed by Gul and Stacchetti,
% at any stage of auction t, q(t) is computed by the auctioneer,
% as well as the (estimated) excess demand set,
% given the profile of reported individual demand sets.
% Whereas the VCG payments are attained by ascending bid auctions
% under monotone GS preferences in the sense that the honest
% reporting of demand set is
% Perfect Bayesian-Nash strategy (Gull and Stacchetti, 2000).
% But they also provided a theorem that GS
% preferences can not generally be implemented VCG
% payments by using dynamic auctions.
% So, the `no gap' condition was needed.
% Further, they proved an impossibility result that there
% is no ascending auction which implements the Vickrey payment
% for every possible GS preferences when more than or equal to
% 3 agents and more than or equal to 4 items
%(Thoerem 6 of Gul and Stacchetti(2000)).
% About auction as primal-dual algorithm
%-----------------------------------------
% The dynamic price adjustment processes has been developed
% can be seen as the primal-dual algorithms for network/
% combinatorial optimization problems.
% Interestingly, in the case of unit demand preferences it
% can be reduced to a network optimization (shortest path problem)
% and the `no negative cycle' condition [*]
% to check the existence of competitive equilibrium
% (Quinzii, 1986). Gale(1986) provided a generalization
% of Quinzii's result by KKM combinatorial theory.
% --[*] It has been used as the simplex criteria of other
% non-primal-dual algorithms, such as a Kline method starting with
% a spanning tree, which solves minimal cost flow ---
% Conversely, auction can be seen as a decentralized solver
% system which embodied primal-dual algorithm
% for various network optimization problems.
% It starts finding an optimal assignment of relaxation problems
% for each agent and for which the mechanism iteratively
% strength them keeping the dual optimality with `price' vectors---
% the dual variables or the potential
% (see Bikhchandani et al.(2002)).
% So also it would be generalized in terms of matroid theory
% or of submodular systems (Gul and Stacchetti(2000),
% Fujishige(1991)).
% However, the solution of relaxation dual of the original
% (combinatorial) assignment problem may fail to exist,
% so the auction process can not attain it
% (Ausubel (2004), Bikhchandani et al. (2002), Gul and Stacchetti (2000)).
% Bikhchandani and Ostroy(see Bikhchandani et al.(2002))
% established the necessary and sufficient
% condition of this class of preferences,
% the `agents are substitutes' condition:
% for all coalition of agents,
% v(N)-v(S) >= Sum_over_i_other_than_S( v(N)-v(N-[i]) ).
% Intuitively, the contribution of any group is not less than
% the sum of each individual contribution out of the group.
% About e-auction, bounded rationality and social emotions
%-----------------------------------------
% Computational aspect/implementation of the market /auction
% mechanisms and their design have been directed attention of
% researchers of multi-agent system(distributed AI) or e-commerce.
% (For example, Nisan and Ronen(2001). Also `Mathematics of the internet:
% e-auction and markets' (Dietrich and Vohra eds., 2002, Springer Verlag)
% which includes Bikhchandani et al.(2002). )
% More generally, game theory draws attention in the context of
% network computing because of the strategic analysis
% for e-business and e-marketplace, the mechanism design for
% network trafic congenstion control,
% and the computational realization of game mechanisms
% with more efficient algorithm for the solution
% such as the winner determination of combinatorial
% e-auction.
% As well known, combinatorial auction, bundling equilibrium,
% automated mechanism design, and so on are recently topics
% in these researches and the related fields.
% Further, it seems promising that with respect to the development of
% boundedly rational modeling, not as the mere computational limit,
% but the endogenous explanation by
% cognitively or sociologically oriented perspectives.
% The perspectives incorporate societal utility as well as satisficing
% principle (or cognitive limitation), for example `spite', `envy', `hostility',
% `harassment' or even `trust' into the game and their effect on the solutions,
% the dynamics.
% Above perspective has been investigated mainly by the experimental
% decision/game theorists.
% Recently, it also draws attention of researchers of e-auctions or mutili-agent
% systems. Morgan et al.(2003) and Brandt et al.(2005) are both
% argued the effect of `spite' on the single-item auction outcome
% and on the VCG payments.
% Some impossibility results of implementation in mechansim
% design theory have been showed, including above English auction result,
% may be remedied by so called `anomalies' in experimental
% decision and game theory.
% As conventional way of justifying the normative theory of
% economics (or management science/operationas research),
% peoples in action are not rational as in these theories,
% therefore an adequate normative (or prescriptive) theory
% for the decision making and the judgment would be required.
% But there may exist an another point. They are not so ego-centric,
% in the theory, who have motievs, rather distributed, not always centralized,
% driven by the socio-emotional factors,
% and so they also have the intentional device (the consciousness)
% which rationalize conflicts among them, not merely
% executing the reservation-level adjusting
% for which many researchers frequently mentioned as `the satisficing'
% following Herb. Simon.
% Modeling for co-workers effect
%-----------------------------------------
% By the way, modeling of societal emotion does not necessarily reqire
% a totally new technique, since there are many cases
% where game with externalities can be applied.
% Ma(2001) has extended the model so as to incorporate co-workers (dis)utility,
% and so complementarity between workers (and firms).
% As well as it integrates with the privious modeling technique,
% it involves with the modeling of soio-psychological motivations.
% For this labor market model, earlier results for usual market game analysis
% may not work.
% Indeed, Ma showed examples where by adding (dis)utility of co-workers
% to a job market nonempty core vanishes.
% As a result, the sufficinet conditions for a nonempty core
% (the gross substitutes condition in Kelso and Crawford(1982),
% or the single improvement condition Gul and Stacchetti(1999) and so on)
% preserves by extending production function as follows.
% According to the way which Shapley and Shubik(1969) used for modeling for
% game with externality, Ma(2001) transformed it as
% u_f'(i; Si) = u_f(i; Si)
% + Sum_over_coworker_j_in_Si( u_cw(j, Si, i) )
% for each firm i.
% That is `the matter of concern' with respect to
% co-workers effect is moved to each firm from the workers
% who the firm hires,
% therefore a labaor market `as if no disutility or disutility of co-workers .'
%
% Also, it may be seen as a degenerate form of combinatorial auction
% which is restricted to the pooled pricing strategy,
% in that no pricing strategy of bundle(co-workers)-dependent
% is permited whereas the agent's evaluation may be.
% Because this transformation does not change the coalitional
% form game, the nonempty core property preserves (Theorem 1 and Theorem 2).
% Togather with two other moderate assumptions (u_f'([])=0 and
% existence of the optimal u_f' for all firms and partitions of workers),
% the labor market of this new production function has also
% the sufficient for the nonempty core in usual analysis,
% so the gross substitutes condition is ( Theorem 3).
% The proof is provided by means of a modification of
% the `salary-adjustment process' by Kelso and Crawford(1982) ).
% And togather with the linear programming duality theorem,
% the dual linear relaxation problem provides
% the necessary and sufficient condition of nonempty core(Theorem 4).
% Nonliner pricing for co-workers effect
%-----------------------------------------
% On the other hand, the core equivalence theorem, as for the competitive
% equilibrium, the balancedness condition (Ma,1998) which is necessary
% and sufficient in standard model, does not preserve since
% the assumed pricing system is independent of the wffect of
% co-workers.
% The failure above mentioned can be restored only if
% one uses a nonlinear pricing where the wage offer profiles
% depend on the firm-workers coalition.
% Ma argued a job market model augmented with the
% taxation and subsidization scheme in Shapley and Shubik(1969),
% which transfer t
% for example, by setting t(j,Si; i) = u_cw(j,Si; i),
% from the worker j to the firm i,
% preserves both the nonemptiness of the t-core (Theorem 8) and
% the core equivalence (as for the competitive equilibrium)
% (Theorem 9 ).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% references
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% [1] Ausubel, L.M. (2004). An efficient ascending-bid auction
% for multiple objects.
% American Economic Review 94(5), 1452-75.
% [2] Bikhchandani, S. and Mamer, J.W. (1997).
% Comptitive equilibrium in an exchange economy with indivisibilities.
% Journal of Economic Theory 74, 385-413.
% *[3] Bikhchandani, S. and De Vries, S., Schummer, J., and Vohra, R.V. (2002).
% Linear programming and Vickrey auctions.
% In Dietrich, B. and Vohra, R.V. (eds.),
% Mathmetics of the internet: e-auction and markets,
% Springer Verlag, pp. 75-115.
% [4] Brandt, F., Sandholm, T., and Shoham, Y. (2005).
% Spiteful bidding an sealed-bid auctions.
% In proccedings of GTDT workshop at IJCAI conference 2005.
% (downloadable from author's homepage. http://www.cs.cmu.edu/~sandholm/)
% [5] Demange, G., Gale, D., and Sotomayor, M. (1986).
% Multi-item auctions.
% Journal of Political Economy 94(4), 863-72.
% [6] Fujishige, S. (2005).
% Submodular Functions and Optimization. 2nd Edition.
% North-Holland. (The first edition was published in 1991.)
% [7] Gale, D. (1984).
% Equilibrium in a discrete exchange economy with money.
% International Journal of Game Theory 13(1), 61-64.
% [8] Gale, D. and Shapley, L. (1962).
% College admissions and the stability of marriage.
% American Mathematical Monthly 69, 9-15.
% *[9] Gul, F. and Stacchetti, E. (2000).
% The English auction with differentiated commodities.
% Journal of Economic Theory 92, 66-95.
% *[10] Gul, F. and Stacchetti, E. (1999).
% Walrasian equilibrium with gross substitutes.
% Journal of Economic Theory 87, 95-124.
% [11] Kaneko, M. (1982).
% The central assignment game and the assignment markets.
% Journal of Mathematical Economics 10, 205-232.
% [12] Kaneko, M. and Yamamoto, Y. (1986).
% The existence and computation of competitive equilibria in markets
% with an indivisible commodity.
% Journal of Economic Theory 38(1), 118-136.
% *[13] Kelso, A.S. and Crawford, V.P. (1982).
% Job matching, coalition formation, and gross substitutes.
% Econometrica 50, 1483-504.
% *[14] Leonard,H.B.(1983).
% Elicitation of honest preferences for the assignment of
% indivisuals to positions.
% Journal of Political Economy 91(3), 461-479.
% *[15] Ma, J. (1998). Competitive equilibrium with indivisibilities.
% Journal of Economic Theory 82, 458-68.
% *[16] Ma, J. (2001). Job matching and coalition formation with
% utility or disutility od co-workers.
% Games and Economic Behavior 34, 83-103.
% [17] Morgan, J., Steiglitz, K., and Reis, G. (2004).
% The spite motive and equilibrium behavior in auction.
% Contributions to Economic Analysis and Policy 2(1),
% article 5. (The B.E. Journals in Economic Analysis & Policy,
% downloadable from http://www.bepress.com/bejeap)
% [18] Nisan N. and Ronen, A. (2001).
% Algorithmic mechanism design.
% Games and Economic Behavior 35, 166-96.
% [19] Quinzii, M. (1984).
% Core and competitive equilibria with indivisibilities.
% International Journal of Game Theory 13(1), 41-60.
% [20] Shapley, L. and Scarf, H. (1974).
% On cores and indivisibility.
% Journal of Mathematical Economics 1, 23-37.
% [21] Shapley, L. and Shubik, M. (1969).
% On the core of an economic system with externalities.
% American Economic Review, 59(4), 678-684.
% [22] Shapley, L. and Shubik, M. (1972).
% The assignment game I: the core.
% International Journal of Game Theory 1, 111-30.
%
% Our model base includes examples in above * marked references.
return to front page.