Carleman's condition: Difference between revisions
en>Helpful Pixie Bot m Dated {{Clarify}}{{Primary sources}}. (Build KF) |
en>Eumolpo m orthographic |
||
| Line 1: | Line 1: | ||
{{Multiple issues|context =October 2009|one source =November 2009}} | |||
The '''Zeuthen strategy''' is a negotiation strategy used by some artificial agents. Its purpose is to measure the ''willingness to risk conflict''. An agent will be more willing to risk conflict if the difference in utility between its current proposal and the conflict deal is low. | |||
When used by both agents in the [[Monotonic Concession Protocol]], the Zeuthen strategy leads the agents to agree upon the deal in the negotiation set, the set of all conflict free deals which are [[Individually rational]] and [[Pareto optimal]] plus the conflict deal, which maximizes the [[Nash product]]. | |||
==Risk== | |||
: <math> | |||
\text{Risk}(i,t)= | |||
\begin{cases} | |||
1 & U_{i}(\delta(i,t))=0 \\ | |||
\frac{U_{i}(\delta(i,t))-U_{i}(\delta(j,t))}{U_{i}(\delta(i,t))} & \text{otherwise} | |||
\end{cases} | |||
</math> | |||
<br /> | |||
Risk(A,t) is a measurement of agent A's willingness to risk conflict. The risk function formalizes the notion that an agent's willingness to risk conflict is the ratio of the utility that agent would lose by accepting the other agent's proposal to the utility that agent would lose by causing a conflict. Agent A is said to be using a rational negotiation strategy if at any step ''t'' + 1 that agent A sticks to his last proposal, Risk(A,t) > Risk(B,t). | |||
==Sufficient concession== | |||
If agent A makes a sufficient concession in the next step, then, assuming that agent B is using a rational negotiation strategy, if agent B does not concede in the next step, he must do so in the step after that. The set of all sufficient concessions of agent A at step t is denoted SC(''A'', ''t''). | |||
==Minimal sufficient concession== | |||
: <math>\delta'=\arg\max_{\delta\in{SC(A,t)}}\{U_{A}(\delta)\}</math> | |||
is the minimal sufficient concession of agent A in step t. | |||
==Zeuthen strategy== | |||
Agent A begins the negotiation by proposing | |||
: <math>\delta(A,0)=\arg\max_{\delta\in{NS}}U_{A}(\delta)</math> | |||
and will make the minimal sufficient concession in step t+1 if and only if Risk(A,t) ≤ Risk(B,t). | |||
'''Theorem''' | |||
If both agents are using Zeuthen strategies, then they will agree on | |||
: <math>\delta=\arg\max_{\delta'\in{NS}}\{\pi(\delta')\},</math> | |||
that is, the deal which maximizes the Nash product. (Harsanyi 56) | |||
'''Proof''' | |||
Let δ<sub>A</sub> = δ(A,t). | |||
Let δ<sub>B</sub> = δ(B,t). | |||
According to the Zeuthen strategy, agent A will concede at step <math>t</math> if and only if | |||
: <math>Risk(A,t)\leq Risk(B,t).</math> | |||
That is, if and only if | |||
: <math>\frac{U_{A}(\delta_{A})-U_{A}(\delta_{B})}{U_{A}(\delta_{A})}\leq \frac{U_{B}(\delta_{B})-U_{B}(\delta_{A})}{U_{B}(\delta_{B})}</math> | |||
: <math>U_{B}(\delta_{B})(U_{A}(\delta_{A})-U_{A}(\delta_{B}))\leq | |||
U_{A}(\delta_{A})(U_{B}(\delta_{B})-U_{B}(\delta_{A}))</math> | |||
: <math>U_{A}(\delta_{A})U_{B}(\delta_{B})-U_{A}(\delta_{B})U_{B}(\delta_{B})\leq | |||
U_{A}(\delta_{A})U_{B}(\delta_{B})-U_{A}(\delta_{A})U_{B}(\delta_{A})</math> | |||
: <math>-U_{A}(\delta_{B})U_{B}(\delta_{B})\leq -U_{A}(\delta_{A})U_{B}(\delta_{A})</math> | |||
: <math>U_{A}(\delta_{A}) U_{B}(\delta_{A})\leq U_{A}(\delta_{B}) U_{B}(\delta_{B})</math> | |||
: <math>\pi(\delta_{A})\leq \pi(\delta_{B})</math> | |||
Thus, Agent A will concede if and only if <math>\delta_{A}</math> does not yield the larger product of utilities. | |||
Therefore, the Zeuthen strategy guarantees a final agreement that maximizes the Nash Product. | |||
==References== | |||
{{reflist}} | |||
* {{cite book | |||
|title= Rules of encounter: designing conventions for automated negotiation among computers Artificial intelligence – The MIT Press series in artificial intelligence | |||
|last= Rosenschein & Zlotkin | |||
|first= | |||
|authorlink= | |||
|coauthors= Jeffrey S. Rosenschein, Gilad Zlotkin | |||
|year= 1994 | |||
|publisher= MIT Press | |||
|location= | |||
|isbn= 0-262-18159-2 | |||
|page= | |||
|pages= 229 | |||
|url= http://books.google.com/books?id=4ZhPMk3ftpoC&dq=Zeuthen+Strategy&client=firefox-a&source=gbs_navlinks_s}} | |||
[[Category:Artificial intelligence]] | |||
[[Category:Economics]] | |||
Revision as of 08:50, 2 March 2013
The Zeuthen strategy is a negotiation strategy used by some artificial agents. Its purpose is to measure the willingness to risk conflict. An agent will be more willing to risk conflict if the difference in utility between its current proposal and the conflict deal is low.
When used by both agents in the Monotonic Concession Protocol, the Zeuthen strategy leads the agents to agree upon the deal in the negotiation set, the set of all conflict free deals which are Individually rational and Pareto optimal plus the conflict deal, which maximizes the Nash product.
Risk
Risk(A,t) is a measurement of agent A's willingness to risk conflict. The risk function formalizes the notion that an agent's willingness to risk conflict is the ratio of the utility that agent would lose by accepting the other agent's proposal to the utility that agent would lose by causing a conflict. Agent A is said to be using a rational negotiation strategy if at any step t + 1 that agent A sticks to his last proposal, Risk(A,t) > Risk(B,t).
Sufficient concession
If agent A makes a sufficient concession in the next step, then, assuming that agent B is using a rational negotiation strategy, if agent B does not concede in the next step, he must do so in the step after that. The set of all sufficient concessions of agent A at step t is denoted SC(A, t).
Minimal sufficient concession
is the minimal sufficient concession of agent A in step t.
Zeuthen strategy
Agent A begins the negotiation by proposing
and will make the minimal sufficient concession in step t+1 if and only if Risk(A,t) ≤ Risk(B,t).
Theorem If both agents are using Zeuthen strategies, then they will agree on
that is, the deal which maximizes the Nash product. (Harsanyi 56)
Proof Let δA = δ(A,t). Let δB = δ(B,t). According to the Zeuthen strategy, agent A will concede at step if and only if
That is, if and only if
Thus, Agent A will concede if and only if does not yield the larger product of utilities.
Therefore, the Zeuthen strategy guarantees a final agreement that maximizes the Nash Product.
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534