Auctions namespace. More...

Namespaces
	concepts
	Auctions Concepts namespace.

	detail
	concepts

Classes
struct	auction_traits
	Types associated with all auctions. More...

class	value_query_auction_traits
	Types associated with value query auction. More...

struct	demand_query_auction_traits
	Types associated with demand query auction. More...

class	gamma_oracle_auction_traits
	Types associated with gamma oracle auction. More...

Typedefs
using	base_auction_components = data_structures::components< bidders, items, data_structures::NameWithDefault< get_copies_num, utils::return_one_functor > >
	concepts More...

using	value_query_components = detail::add_to_base_auction< value_query >
	detail More...

template<typename... Args>
using	value_query_auction_components = typename value_query_components::type< Args...>
	value query auction components template alias More...

using	demand_query_components = detail::add_to_base_auction< demand_query >
	definition for the components class for a demand query auction

template<typename... Args>
using	demand_query_auction_components = typename demand_query_components::type< Args...>
	demand query auction components template alias More...

using	gamma_oracle_components = detail::add_to_base_auction< gamma_oracle, gamma >
	definition for the components class for a gamma oracle auction.

template<typename... Args>
using	gamma_oracle_auction_components = typename gamma_oracle_components::type< Args...>
	gamma oracle auction components template alias More...

Functions
template<typename... Args>
auto	make_value_query_auction_components (Args &&...args) -> decltype(value_query_components::make_components(std::forward< Args >(args)...))
	make function for value query components More...

template<typename... Args>
auto	make_demand_query_auction_components (Args &&...args)
	make function for demand query components More...

template<typename... Args>
auto	make_gamma_oracle_auction_components (Args &&...args) -> decltype(gamma_oracle_components::make_components(std::forward< Args >(args)...))
	make function for gamma oracle components More...

template<class Auction >
auto	items_number (Auction &&auction)
	Returns the number of different kinds of items in an auction. More...

template<class Auction >
auto	bidders_number (Auction &&auction)
	Returns the number of bidders in an auction. More...

template<class Auction >
paal::auctions::auction_traits < Auction >::copies_num_t	get_minimum_copies_num (Auction &&auction)
	Returns minimum number of copies of an item in an auction. More...

template<class DemandQueryAuction , class OutputIterator , class ItemToLpIdMap , class SeparationOracle = paal::lp::random_violated_separation_oracle>
void	fractional_determine_winners_in_demand_query_auction (DemandQueryAuction &&auction, OutputIterator result, ItemToLpIdMap item_to_id, double epsilon, SeparationOracle separation_oracle=SeparationOracle{})
	detail More...

template<class DemandQueryAuction , class OutputIterator >
void	fractional_determine_winners_in_demand_query_auction (DemandQueryAuction &&auction, OutputIterator result, double epsilon=1e-7)
	This is fractional determine winners in demand query auction and return assignment of fractional bundles to bidders. This is version with default ItemToLpIdMap using std::unordered_map and default epsilon. More...

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto	make_single_minded_to_value_query_auction (Bidders &&bidders, Items &&items, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_xor_bids_to_value_query_auction(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::get_bids(), get_value, get_items, get_copies_num))
	detail More...

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto	make_single_minded_to_demand_query_auction (Bidders &&bidders, Items &&items, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_xor_bids_to_demand_query_auction(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::get_bids(), get_value, get_items, get_copies_num))
	Create demand query auction from single minded valuations. More...

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto	make_single_minded_to_gamma_oracle_auction (Bidders &&bidders, Items &&items, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_xor_bids_to_gamma_oracle_auction(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::get_bids(), get_value, get_items, get_copies_num))
	Create gamma oracle auction from single minded valuations. More...

template<class Bidders , class GetItems , class OutputIterator >
void	extract_items_from_single_minded (Bidders &&bidders, GetItems get_items, OutputIterator output)
	Extract all items appearing in all bidders' bids. This function doesn't eliminate duplicates, this is left out to the caller. More...

template<class GammaOracleAuction , class OutputIterator , class PriceMap , class Epsilon >
void	determine_winners_in_gamma_oracle_auction (GammaOracleAuction &&auction, OutputIterator result, PriceMap price, Epsilon epsilon)
	detail More...

template<class GammaOracleAuction , class OutputIterator , class Epsilon = double>
void	determine_winners_in_gamma_oracle_auction (GammaOracleAuction &&auction, OutputIterator result, Epsilon epsilon=1e-8)
	This is determine winners in gamma oracle auction and return assignment of bidders to items. This is version with default PriceMap using std::unordered_map and default epsilon. More...

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto	make_xor_bids_to_value_query_auction (Bidders &&bidders, Items &&items, GetBids get_bids, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_value_query_auction_components(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::xor_bids_value_query< GetBids, GetValue, GetItems >(get_bids, get_value, get_items), get_copies_num))
	detail More...

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto	make_xor_bids_to_demand_query_auction (Bidders &&bidders, Items &&items, GetBids get_bids, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{})
	detail More...

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto	make_xor_bids_to_gamma_oracle_auction (Bidders &&bidders, Items &&items, GetBids get_bids, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_gamma_oracle_auction_components(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::xor_bids_gamma_oracle< GetBids, GetValue, GetItems >(get_bids, get_value, get_items), 1, get_copies_num))
	detail More...

template<class Bidders , class GetBids , class GetItems , class OutputIterator >
void	extract_items_from_xor_bids (Bidders &&bidders, GetBids get_bids, GetItems get_items, OutputIterator output)
	extract all items appearing in all bids. This function doesn't eliminate duplicates, this is left out to the caller. More...

Detailed Description

Auctions namespace.

Typedef Documentation

using paal::auctions::base_auction_components = typedef data_structures::components< bidders, items, data_structures::NameWithDefault<get_copies_num, utils::return_one_functor> >

concepts

Definition for the components class representing an auction. This class is not meant to be directly used, it is just a base for the more specialized components interfaces.

Definition at line 204 of file auction_components.hpp.

template<typename... Args>

using paal::auctions::demand_query_auction_components = typedef typename demand_query_components::type<Args...>

demand query auction components template alias

Template Parameters

Args

Definition at line 261 of file auction_components.hpp.

template<typename... Args>

using paal::auctions::gamma_oracle_auction_components = typedef typename gamma_oracle_components::type<Args...>

gamma oracle auction components template alias

Template Parameters

Args

Definition at line 292 of file auction_components.hpp.

template<typename... Args>

using paal::auctions::value_query_auction_components = typedef typename value_query_components::type<Args...>

value query auction components template alias

Template Parameters

Args

Definition at line 229 of file auction_components.hpp.

using paal::auctions::value_query_components = typedef detail::add_to_base_auction<value_query>

detail

definition for the components class for a value query auction.

Definition at line 221 of file auction_components.hpp.

Function Documentation

template<class Auction >

auto paal::auctions::bidders_number ( Auction && auction )

Returns the number of bidders in an auction.

Parameters

auction

Template Parameters

Auction

Definition at line 50 of file auction_utils.hpp.

template<class GammaOracleAuction , class OutputIterator , class PriceMap , class Epsilon >

void paal::auctions::determine_winners_in_gamma_oracle_auction	(	GammaOracleAuction &&	auction,
		OutputIterator	result,
		PriceMap	price,
		Epsilon	epsilon
	)

detail

This is determine winners in gamma oracle auction and return assignment of items to bidders.

Example:

int main()
{
   using Bidder = std::string;
   using Item = std::string;
   using Items = std::unordered_set<Item>;
   using Value = double;
   using Bid = std::pair<Items, Value>;
   using Bids = std::vector<Bid>;
   // create auction
   const std::unordered_map<Bidder, Bids> bids {
      {"John", {
         {{"ball", "kite"}, 2},
         {{"umbrella"}, 3},
         {{"orange"}, 1.75},
         {{"ball", "kite", "umbrella"}, 5},
         {{"ball", "kite", "orange", "umbrella"}, 6.75},
      }},
      {"Bob", {
         {{"orange"}, 1.5},
         {{"apple"}, 2.0},
         {{"apple", "orange"}, 4},
      }},
      {"Steve", {
         {{"apple"}, 1},
         {{"umbrella"}, 4},
         {{"apple", "umbrella"}, 5},
      }},
   };
   const std::vector<Bidder> bidders {"John", "Bob", "Steve"};
   const std::vector<Item> items {"apple", "ball", "orange", "kite", "umbrella"};
   auto get_bids = [&](const Bidder& bidder) -> const Bids& { return bids.at(bidder); };
   auto get_value = [](const Bid& bid) { return bid.second; };
   auto get_items = [](const Bid& bid) -> const Items& { return bid.first; };
   auto auction = paal::auctions::make_xor_bids_to_gamma_oracle_auction(
      bidders, items, get_bids, get_value, get_items
   );
   // determine winners
   Value social_welfare = 0;
   auto valuation = paal::auctions::make_xor_bids_to_value_query_auction(
      bidders, items, get_bids, get_value, get_items
   );
   paal::auctions::determine_winners_in_gamma_oracle_auction(
      auction,
      boost::make_function_output_iterator([&](std::pair<Bidder, Items> p)
      {
         auto bidder = p.first;
         auto& cur_items = p.second;
         social_welfare += valuation.call<paal::auctions::value_query>(bidder, cur_items);
         std::cout << bidder << " got bundle: ";
         boost::copy(cur_items, std::ostream_iterator<Item>(std::cout, ", "));
         std::cout << std::endl;
      })
   );
   std::cout << "social welfare: " << social_welfare << std::endl;
   return 0;
}

Complete example is winner_determination_in_MUCA_example.cpp.

Template Parameters

GammaOracleAuction
OutputIterator
PriceMap
Epsilon

Parameters

auction
result
price	Stores the current mapping of items to prices. These are prices just for the working purposes of the algorithm, not the prices to be paid by the bidders.
epsilon	Used for floating point comparison to ensure feasibility.

Definition at line 106 of file winner_determination_in_MUCA.hpp.

template<class GammaOracleAuction , class OutputIterator , class Epsilon = double>

void paal::auctions::determine_winners_in_gamma_oracle_auction	(	GammaOracleAuction &&	auction,
		OutputIterator	result,
		Epsilon	epsilon = `1e-8`
	)

This is determine winners in gamma oracle auction and return assignment of bidders to items. This is version with default PriceMap using std::unordered_map and default epsilon.

Template Parameters

GammaOracleAuction
OutputIterator
Epsilon

Parameters

auction
result
epsilon	Used for floating point comparison to ensure feasibility.

Definition at line 218 of file winner_determination_in_MUCA.hpp.

template<class Bidders , class GetItems , class OutputIterator >

void paal::auctions::extract_items_from_single_minded	(	Bidders &&	bidders,
		GetItems	get_items,
		OutputIterator	output
	)

Extract all items appearing in all bidders' bids. This function doesn't eliminate duplicates, this is left out to the caller.

Parameters

bidders
get_items
output

Template Parameters

Bidders
GetItems
OutputIterator

Definition at line 233 of file single_minded_auctions.hpp.

template<class Bidders , class GetBids , class GetItems , class OutputIterator >

void paal::auctions::extract_items_from_xor_bids	(	Bidders &&	bidders,
		GetBids	get_bids,
		GetItems	get_items,
		OutputIterator	output
	)

extract all items appearing in all bids. This function doesn't eliminate duplicates, this is left out to the caller.

Template Parameters

Bidders
GetBids
GetItems
OutputIterator

Parameters

bidders
get_bids
get_items
output

Definition at line 458 of file xor_bids.hpp.

template<class DemandQueryAuction , class OutputIterator , class ItemToLpIdMap , class SeparationOracle = paal::lp::random_violated_separation_oracle>

void paal::auctions::fractional_determine_winners_in_demand_query_auction	(	DemandQueryAuction &&	auction,
		OutputIterator	result,
		ItemToLpIdMap	item_to_id,
		double	epsilon,
		SeparationOracle	separation_oracle = `SeparationOracle{}`
	)

detail

This is fractional determine winners in demand query auction and return assignment of fractional bundles to bidders.

Example:

Complete example is fractional_winner_determination_in_MUCA_example.cpp

Template Parameters

DemandQueryAuction
OutputIterator
ItemToLpIdMap
SeparationOracle

Parameters

auction
result
item_to_id	Stores the current mapping of items to LP column ids.
epsilon	Used for floating point comparison.
separation_oracle	Separation Oracle Strategy for searching the bidder with violated inequality.

Definition at line 113 of file fractional_winner_determination_in_MUCA.hpp.

template<class DemandQueryAuction , class OutputIterator >

void paal::auctions::fractional_determine_winners_in_demand_query_auction	(	DemandQueryAuction &&	auction,
		OutputIterator	result,
		double	epsilon = `1e-7`
	)

This is fractional determine winners in demand query auction and return assignment of fractional bundles to bidders. This is version with default ItemToLpIdMap using std::unordered_map and default epsilon.

Template Parameters

DemandQueryAuction
OutputIterator

Parameters

auction
result
epsilon	Used for floating point comparison.

Definition at line 224 of file fractional_winner_determination_in_MUCA.hpp.

template<class Auction >

paal::auctions::auction_traits<Auction>::copies_num_t paal::auctions::get_minimum_copies_num ( Auction && auction )

Returns minimum number of copies of an item in an auction.

Parameters

auction

Template Parameters

Auction

Definition at line 62 of file auction_utils.hpp.

template<class Auction >

auto paal::auctions::items_number ( Auction && auction )

Returns the number of different kinds of items in an auction.

Parameters

auction

Template Parameters

Auction

Definition at line 39 of file auction_utils.hpp.

template<typename... Args>

auto paal::auctions::make_demand_query_auction_components ( Args &&... args )

make function for demand query components

Template Parameters

Args

Parameters

args

Returns: demand query components

Definition at line 272 of file auction_components.hpp.

template<typename... Args>

auto paal::auctions::make_gamma_oracle_auction_components ( Args &&... args ) -> decltype(gamma_oracle_components::make_components(std::forward<Args>(args)...))

make function for gamma oracle components

Template Parameters

Args

Parameters

args

Returns: gamma oracle components

Definition at line 303 of file auction_components.hpp.

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>

auto paal::auctions::make_single_minded_to_demand_query_auction	(	Bidders &&	bidders,
		Items &&	items,
		GetValue	get_value,
		GetItems	get_items,
		GetCopiesNum	get_copies_num = `GetCopiesNum{}`
	)		-> decltype(make_xor_bids_to_demand_query_auction( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::get_bids(), get_value, get_items, get_copies_num ))

Create demand query auction from single minded valuations.

Parameters

bidders
items
get_value
get_items
get_copies_num

Template Parameters

Bidders
Items
GetValue
GetItems
GetCopiesNum

Definition at line 148 of file single_minded_auctions.hpp.

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>

auto paal::auctions::make_single_minded_to_gamma_oracle_auction	(	Bidders &&	bidders,
		Items &&	items,
		GetValue	get_value,
		GetItems	get_items,
		GetCopiesNum	get_copies_num = `GetCopiesNum{}`
	)		-> decltype(make_xor_bids_to_gamma_oracle_auction( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::get_bids(), get_value, get_items, get_copies_num ))

Create gamma oracle auction from single minded valuations.

Parameters

bidders
items
get_value
get_items,@param	get_copies_num

Template Parameters

Bidders
Items
GetValue
GetItems
GetCopiesNum

Definition at line 195 of file single_minded_auctions.hpp.

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>

auto paal::auctions::make_single_minded_to_value_query_auction	(	Bidders &&	bidders,
		Items &&	items,
		GetValue	get_value,
		GetItems	get_items,
		GetCopiesNum	get_copies_num = `GetCopiesNum{}`
	)		-> decltype(make_xor_bids_to_value_query_auction( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::get_bids(), get_value, get_items, get_copies_num ))

detail

Create value query auction from single minded valuations.

Parameters

bidders
items
get_value
get_items
get_copies_num

Template Parameters

Bidders
Items
GetValue
GetItems
GetCopiesNum

Definition at line 98 of file single_minded_auctions.hpp.

template<typename... Args>

auto paal::auctions::make_value_query_auction_components ( Args &&... args ) -> decltype(value_query_components::make_components(std::forward<Args>(args)...))

make function for value query components

Template Parameters

Args

Parameters

args

Returns: value query components

Definition at line 240 of file auction_components.hpp.

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>

auto paal::auctions::make_xor_bids_to_demand_query_auction	(	Bidders &&	bidders,
		Items &&	items,
		GetBids	get_bids,
		GetValue	get_value,
		GetItems	get_items,
		GetCopiesNum	get_copies_num = `GetCopiesNum{}`
	)

detail

Create demand query auction from xor bids valuations.

Parameters

bidders
items
get_bids
get_value
get_items
get_copies_num

Template Parameters

Bidders
Items
GetBids
GetValue
GetItems
GetCopiesNum

Definition at line 264 of file xor_bids.hpp.

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>

auto paal::auctions::make_xor_bids_to_gamma_oracle_auction	(	Bidders &&	bidders,
		Items &&	items,
		GetBids	get_bids,
		GetValue	get_value,
		GetItems	get_items,
		GetCopiesNum	get_copies_num = `GetCopiesNum{}`
	)		-> decltype(make_gamma_oracle_auction_components( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::xor_bids_gamma_oracle<GetBids, GetValue, GetItems>(get_bids, get_value, get_items), 1, get_copies_num ))

detail

Create gamma oracle auction from xor bids valuations.

Parameters

bidders
items
get_bids
get_value
get_items
get_copies_num

Template Parameters

Bidders
Items
GetBids
GetValue
GetItems
GetCopiesNum

Definition at line 418 of file xor_bids.hpp.

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>

auto paal::auctions::make_xor_bids_to_value_query_auction	(	Bidders &&	bidders,
		Items &&	items,
		GetBids	get_bids,
		GetValue	get_value,
		GetItems	get_items,
		GetCopiesNum	get_copies_num = `GetCopiesNum{}`
	)		-> decltype(make_value_query_auction_components( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::xor_bids_value_query<GetBids, GetValue, GetItems>(get_bids, get_value, get_items), get_copies_num ))

detail

Create value query auction from xor bids valuations.

Parameters

bidders
items
get_bids
get_value
get_items
get_copies_num

Template Parameters

Bidders
Items
GetBids
GetValue
GetItems
GetCopiesNum

Definition at line 170 of file xor_bids.hpp.

Namespaces

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation