Chapter 14 Introduction To Multiagent Systems

Front 1

resource allocation

Back 1

na

Front 2

common value

Back 2

A type of auction in which every participant values a good in the same way.

Front 3

private value

Back 3

A type of auction in which agents have their own valuation for goods, which they do not necessarily share with others.

Front 4

correlated value

Back 4

A type of auction in which agent's valuations are related to one another, but not necessarily common value.

Front 5

first-price auction

Back 5

A type of auction in which the amount the auction winner pays for a good is the amount of the highest bid.

Front 6

second-price auction

Back 6

An auction in which the winner of the resource pays the amount of the second highest bid (aka Vickrey auction) - bidding truthfully is a dominant strategy in second price auctions.

Front 7

open cry

Back 7

A type of auction in which every agent gets to see the bids of every other agent.

Front 8

sealed bid

Back 8

A type of auction: in a sealed bid auction, bidders submit bids in private to the auctioneer ( in contrast to open cry auctions).

Front 9

one-shot auction

Back 9

An auction in which there is a single round of bids.

Front 10

ascending auction

Back 10

An ascending auction is one in which bids start low and get progressively higher.

Front 11

english auctions

Back 11

A type of auction in which bidding starts at some low reserve value, and then bidders submit increasing bids until no bidders are willing to go higher.

Front 12

winner's curse

Back 12

The idea that if you win in an auction, then you probably overestimated the value of the good, since nobody else was willing to bid as much as you.

Front 13

dutch auction

Back 13

A type of auction in which bidding starts with a high value, and is then reduced by an auctioneer until som participant is willing to bid.

Front 14

vickrey auction

Back 14

Another name for a second-price auction.

Front 15

valuation function

Back 15

na

Front 16

free disposal

Back 16

The idea of having more of a particular resource is never worse than having less.

Front 17

winner determination problem

Back 17

In combinatorial auctions, winner determination amounts to findinf an allocation of goods that maximizes value - an NP-hard problem.

Front 18

bidding languages

Back 18

In combinatorial auctions, a language that is used by bidders to express their valuation functions - OR and XOR languages are the best known.

Front 19

atomic bids

Back 19

In combinatorial auctions, a key problem is that of concisely expressing the preferences agents have over bundles of goods: bidding languages are used to express these preferences, and are composed of atomic bids, typically using OR or XOR operators.

Front 20

XOR bids

Back 20

A type of bidding language for combinatorial auctions, in which a valuation function is defined as the 'exclusive or' of a number of atomic bids.

Front 21

OR bids

Back 21

A type of bidding language for combinatorial auctions, in which a valuation function is defined as the 'disjunction' of a number of atomic bids.

Front 22

dummy goods

Back 22

na

Front 23

heuristic winner determination

Back 23

In combinatorial auctions, finding an optimal allocation (winner determination) is computationally complex - heuristic approaches aim to find a (not necessarily optimal) allocation quickly, using rules of thumb (heuristics).

Front 24

approximate winner determination

Back 24

In combinatorial auctions, the winner determination problem is a computationally intractable problem, involving finding an optimal allocation of goods to bidders: in approximate winner determination, we aim to find an allocation that may not be optimal, but is within some known bound of the optimal.

Front 25

integer linear programming

Back 25

A type of optimization problem, in which we want to find integer values for some unknown variables, where constraints on these variables are expressed as linear inequalities over them.

Front 26

objective function

Back 26

In linear programs, the objective function defines what is to be maximized (or minimized).

Front 27

incentive compatible

Back 27

A voting protocol (or more generally, social choice mechanism) is incentive compatible if no agent can benefit by misrepresenting their preferences, i.e., if truth-telling is a rational choice.

Front 28

VCG mechanism

Back 28

Vickrey-Clark-Groves mechanism: a generalization of Vickrey auctions used in combinatorial auction settings, which has the property that bidding to one's true valuation is a dominant strategy (i.e., it is incentive compatible).

Front 29

mechanism design

Back 29

The process of designing a game so that, if the participants in the game act rationally, some desirable overall objective will be achieved.

Front 30

implementation theory

Back 30

The part of game theory concerned with with designing games to satisfy certain properties.

Front 31

algorithmic game theory

Back 31

A part of theoretical computer science that studies computational aspects of game theory, such as the complexity of computing solution concepts, and the applications of mechanism design in computer science.

Front 32

auction bots

Back 32

Simple software agents that bid on behalf of their owner in an online auction.

Front 33

electronic marketplace

Back 33

na

Front 34

proxy bidding

Back 34

The idea of having a proxy (a program or a person) submit bids on our behalf in an online auction

Front 35

sniping

Back 35

In an online auction such as eBay, sniping is the behaviour whereby bidders try to submit bids at the last possible moment.

Front 36

TAC

Back 36

The Trading Agent Competition - a competition intended to test the ability of computer programs to automatically trade goods and services.

Front 37

continuous double auction

Back 37

An auction in which participants buy and sell simultaneously - used in the Trading Agent Competition.