Artificial Markets in Software Development: A New Paradigm

 
Software Development using
artificial markets of constructively
egoistic agents
 
Karl Lieberherr
 
1
 
SD-F09
 
Problem Solving Software
for computationally hard problems:
examples
 
Given a transportation task, find the optimal
way of carrying it out.
Given an employment market, find the
optimal assignment of workers to companies.
Given a Boolean formula, is it satisfiable?
Given a Boolean formula in conjunctive
normal form, find an assignment that
maximizes the fraction of satisfied clauses.
 
2
 
SD-F09
 
A new use of computers
 
Design an artificial market AM(X) for artificial
organisms (agents) that are developed by
humans. X is a problem solving domain
(optimization problem, decision problem).
Purpose of artificial market AM(X): Develop
good algorithms and useful knowledge about
a problem solving domain X. The market
leader has the best algorithm and the best
knowledge compared to all the other agents.
 
3
 
SD-F09
 
Traditional Approach
Human Developers
Develop new software
for problem solving domain X
Static Evaluation.
No competition.
Testing
  unit testing
  integration testing
Benchmark is used
to evaluate software
Users
Requirements for X
 
4
 
SD-F09
 
Why Software Development through
an artificial market?
Human Developers
Develop new software
for problem solving domain X
Artificial Market(X)
Erika-Patrick-agent
winning-agent
Evaluates fairly, frequently,
constructively and
dynamically.
Drives innovation.
Challenges humans.
Agents point humans to
what needs attention in
the software.
human1
human2
Erika
Patrick
Benchmark is used
to evaluate software
Users
Requirements for X
 
5
 
SD-F09
 
Erika-Patrick Agent
 
Surrogate of combined knowledge of Erika
and Patrick successfully transferred to agent.
Transfer knowledge by programming.
 
6
 
SD-F09
 
Agent design
 
How to design an artificial organism?
Has a basic need: maximize life energy, money.
Has a rhythm. Every round the same activity
happens.
Interacts with other agents by offering and buying
challenges. Offering and buying a challenge might
create a big win but it also makes the agent
vulnerable to a loss. There is uncertainty when
offering or buying a challenge.
 
7
 
SD-F09
 
Agent design
 
challenge = (belief, price)
Belief expresses a fact about problem solving domain
X believed to be true.
Belief is result of experiments with problem solving
algorithm.
If problem solving algorithm is not good (has bugs, is
inefficient compared to others), the belief can be
discounted by buyer/acceptor of challenge.
If belief is successfully discounted, the seller has to pay
more than the initial price to buyer.
If belief is not discounted, the buyer lost the price he paid.
 
8
 
SD-F09
 
Which means
 
Agents should only buy a challenge whose
belief they think they can discount.
Agents should only offer a challenge if they
can successfully support the belief against a
buyer.
 
9
 
SD-F09
 
Beliefs
 
Belief is supported: By giving problem in
domain X to buyer for which it cannot find a
solution that contradicts the belief.
Belief is discounted: By giving problem in
domain X to buyer for which it can find a
solution that contradicts the belief.
Belief language needs to be carefully chosen.
 
10
 
SD-F09
 
Agents are constructively egoistic
 
They have an ego. They can constructively
show that they are better than other agents
by playing the game.
They give constructive feedback to other
agents.
The social welfare consists of improving
software/algorithms.
 
11
 
SD-F09
 
SCG(X)
 
X: optimization problem.
Classic beliefs:
I believe that I can give you a problem satisfying
predicate pred so that you cannot find an assignment
satisfying the fraction q of all constraints. (exists p in
pred for all J fsat(p,J) < q)
I believe that for all problems satisfying predicate pred
I can find an assignment satisfying the fraction q of all
constraints. (for all p in pred exists J fsat(p,J) >= q)
Is one the negation of the other?
 
12
 
SD-F09
 
More beliefs
 
I believe that if you give me 10 problems of
kind X and you give me 10 problems of kind X,
I solve your problems better than you solve
mine. (time limit 1 minute for both).
We call this a duel belief.
 
SD-F09
 
13
 
More beliefs
 
I believe that if I give you an optimization
problem of kind X for which I have a secret
solution, you cannot find a solution that is at
least as good as mine (time limit 1 minute).
 
SD-F09
 
14
Slide Note
Embed
Share

Explore the innovative concept of utilizing artificial markets for software development, where constructively egoistic agents interact in problem-solving domains. Learn how artificial markets can lead to the development of advanced algorithms and valuable knowledge, revolutionizing traditional software development approaches. Witness the creation of artificial organisms and agents designed to optimize tasks through challenging interactions, offering a fresh perspective on problem-solving in computational environments.


Uploaded on May 12, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Software Development using artificial markets of constructively egoistic agents Karl Lieberherr SD-F09 1

  2. Problem Solving Software for computationally hard problems: examples Given a transportation task, find the optimal way of carrying it out. Given an employment market, find the optimal assignment of workers to companies. Given a Boolean formula, is it satisfiable? Given a Boolean formula in conjunctive normal form, find an assignment that maximizes the fraction of satisfied clauses. SD-F09 2

  3. A new use of computers Design an artificial market AM(X) for artificial organisms (agents) that are developed by humans. X is a problem solving domain (optimization problem, decision problem). Purpose of artificial market AM(X): Develop good algorithms and useful knowledge about a problem solving domain X. The market leader has the best algorithm and the best knowledge compared to all the other agents. SD-F09 3

  4. Traditional Approach Requirements for X Human Developers human1 human2 human3 human4 Testing unit testing integration testing Develop new software for problem solving domain X Benchmark is used to evaluate software Users SD-F09 4

  5. Why Software Development through an artificial market? Requirements for X Human Developers human1 human2 Erika Patrick Artificial Market(X) Erika-Patrick-agent winning-agent Develop new software for problem solving domain X Benchmark is used to evaluate software SD-F09 Users 5

  6. Erika-Patrick Agent Surrogate of combined knowledge of Erika and Patrick successfully transferred to agent. Transfer knowledge by programming. SD-F09 6

  7. Agent design How to design an artificial organism? Has a basic need: maximize life energy, money. Has a rhythm. Every round the same activity happens. Interacts with other agents by offering and buying challenges. Offering and buying a challenge might create a big win but it also makes the agent vulnerable to a loss. There is uncertainty when offering or buying a challenge. SD-F09 7

  8. Agent design challenge = (belief, price) Belief expresses a fact about problem solving domain X believed to be true. Belief is result of experiments with problem solving algorithm. If problem solving algorithm is not good (has bugs, is inefficient compared to others), the belief can be discounted by buyer/acceptor of challenge. If belief is successfully discounted, the seller has to pay more than the initial price to buyer. If belief is not discounted, the buyer lost the price he paid. SD-F09 8

  9. Which means Agents should only buy a challenge whose belief they think they can discount. Agents should only offer a challenge if they can successfully support the belief against a buyer. SD-F09 9

  10. Beliefs Belief is supported: By giving problem in domain X to buyer for which it cannot find a solution that contradicts the belief. Belief is discounted: By giving problem in domain X to buyer for which it can find a solution that contradicts the belief. Belief language needs to be carefully chosen. SD-F09 10

  11. Agents are constructively egoistic They have an ego. They can constructively show that they are better than other agents by playing the game. They give constructive feedback to other agents. The social welfare consists of improving software/algorithms. SD-F09 11

  12. SCG(X) X: optimization problem. Classic beliefs: I believe that I can give you a problem satisfying predicate pred so that you cannot find an assignment satisfying the fraction q of all constraints. (exists p in pred for all J fsat(p,J) < q) I believe that for all problems satisfying predicate pred I can find an assignment satisfying the fraction q of all constraints. (for all p in pred exists J fsat(p,J) >= q) Is one the negation of the other? SD-F09 12

  13. More beliefs I believe that if you give me 10 problems of kind X and you give me 10 problems of kind X, I solve your problems better than you solve mine. (time limit 1 minute for both). We call this a duel belief. SD-F09 13

  14. More beliefs I believe that if I give you an optimization problem of kind X for which I have a secret solution, you cannot find a solution that is at least as good as mine (time limit 1 minute). SD-F09 14

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#