path: root/wasserstein/include/auction_runner_fr.hpp

/*

Copyright (c) 2016, M. Kerber, D. Morozov, A. Nigmetov
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

You are under no obligation whatsoever to provide any bug fixes, patches, or
upgrades to the features, functionality or performance of the source code
(Enhancements) to anyone; however, if you choose to make your Enhancements
available either publicly, or directly to copyright holder,
without imposing a separate written license agreement for such Enhancements,
then you hereby grant the following license: a  non-exclusive, royalty-free
perpetual license to install, use, modify, prepare derivative works, incorporate
into other computer software, distribute, and sublicense such enhancements or
derivative works thereof, in binary and source code form.

  */

#ifndef AUCTION_RUNNER_FR_HPP
#define AUCTION_RUNNER_FR_HPP

#include <cassert>
#include <algorithm>
#include <functional>
#include <iterator>

#include "def_debug_ws.h"

#include "auction_runner_fr.h"

#ifdef FOR_R_TDA
#include "Rcpp.h"
#undef DEBUG_FR_AUCTION
#endif


namespace hera {
namespace ws {


// *****************************
// AuctionRunnerFR
// *****************************

template<class R, class AO>
AuctionRunnerFR<R, AO>::AuctionRunnerFR(const std::vector<DgmPoint>& A,
                                          const std::vector<DgmPoint>& B,
                                          const Real q,
                                          const Real _delta,
                                          const Real _internal_p,
                                          const Real _initial_epsilon,
                                          const Real _eps_factor,
                                          const int _max_num_phases,
                                          const Real _gamma_threshold,
                                          const size_t _max_bids_per_round) :
    bidders(A),
    items(B),
    num_bidders(A.size()),
    num_items(A.size()),
    items_to_bidders(A.size(), k_invalid_index),
    bidders_to_items(A.size(), k_invalid_index),
    wasserstein_power(q),
    delta(_delta),
    internal_p(_internal_p),
    initial_epsilon(_initial_epsilon),
    epsilon_common_ratio(_eps_factor == 0.0 ? 5.0 : _eps_factor),
    max_num_phases(_max_num_phases),
    forward_bid_table(A.size(), std::make_pair(k_invalid_index, k_lowest_bid_value) ),
    reverse_bid_table(B.size(), std::make_pair(k_invalid_index, k_lowest_bid_value) ),
    forward_oracle(bidders, items, q, _internal_p),
    reverse_oracle(items, bidders, q, _internal_p),
    max_bids_per_round(_max_bids_per_round),
    total_items_persistence(std::accumulate(items.begin(),
                                            items.end(),
                                            R(0.0),
                                            [_internal_p, q](const Real& ps, const DgmPoint& item)
                                                { return ps + std::pow(item.persistence_lp(_internal_p), q); }
                                           )),
    total_bidders_persistence(std::accumulate(bidders.begin(),
                                              bidders.end(),
                                              R(0.0),
                                              [_internal_p, q](const Real& ps, const DgmPoint& bidder)
                                                  { return ps + std::pow(bidder.persistence_lp(_internal_p), q); }
                                             )),
    partial_cost(0.0),
    unassigned_bidders_persistence(total_bidders_persistence),
    unassigned_items_persistence(total_items_persistence),
    gamma_threshold(_gamma_threshold)
{
    assert(A.size() == B.size());
    for(const auto& p : bidders) {
        if (p.is_normal()) {
            num_normal_bidders++;
            num_diag_items++;
        } else {
            num_normal_items++;
            num_diag_bidders++;
        }
    }

#ifdef ORDERED_BY_PERSISTENCE
    for(size_t bidder_idx = 0; bidder_idx < num_bidders; ++bidder_idx) {
        unassigned_bidders_by_persistence.insert(std::make_pair(bidders[bidder_idx].persistence_lp(1.0), bidder_idx));
    }

    for(size_t item_idx = 0; item_idx < num_items; ++item_idx) {
        unassigned_items_by_persistence.insert(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx));
    }
#endif

    // for experiments
    unassigned_threshold = bidders.size() / 200;
    unassigned_threshold = 0;

#ifdef ORDERED_BY_PERSISTENCE
    batch_size = 5000;
#endif
}

template<class R, class AO>
typename AuctionRunnerFR<R, AO>::Real
AuctionRunnerFR<R, AO>::get_cost_to_diagonal(const DgmPoint& pt) const
{
    if (1.0 == wasserstein_power) {
        return pt.persistence_lp(internal_p);
    } else {
        return std::pow(pt.persistence_lp(internal_p), wasserstein_power);
    }
}


template<class R, class AO>
typename AuctionRunnerFR<R, AO>::Real
AuctionRunnerFR<R, AO>::get_gamma() const
{
    if (1.0 == wasserstein_power) {
        return unassigned_items_persistence + unassigned_bidders_persistence;
    } else {
        return std::pow(unassigned_items_persistence + unassigned_bidders_persistence,
                        1.0 / wasserstein_power);
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::reset_phase_stat()
{
    num_rounds_non_cumulative = 0;
}


template<class R, class AO>
void AuctionRunnerFR<R, AO>::reset_round_stat()
{
    num_forward_bids_submitted = 0;
    num_reverse_bids_submitted = 0;
}


template<class R, class AO>
void AuctionRunnerFR<R, AO>::assign_forward(IdxType item_idx, IdxType bidder_idx)
{
    sanity_check();
    // only unassigned bidders submit bids
    assert(bidders_to_items[bidder_idx] == k_invalid_index);

    IdxType old_item_owner = items_to_bidders[item_idx];

    // set new owner
    bidders_to_items[bidder_idx] = item_idx;
    items_to_bidders[item_idx] = bidder_idx;

    // remove bidder and item from the sets of unassigned bidders/items
    remove_unassigned_bidder(bidder_idx);

    if (k_invalid_index != old_item_owner) {
        // old owner of item becomes unassigned
        bidders_to_items[old_item_owner] = k_invalid_index;
        add_unassigned_bidder(old_item_owner);
        // existing edge was removed, decrease partial_cost
        partial_cost -= get_item_bidder_cost(item_idx, old_item_owner);
    } else {
        // item was unassigned before
        remove_unassigned_item(item_idx);
    }

    // new edge was added to matching, increase partial cost
    partial_cost += get_item_bidder_cost(item_idx, bidder_idx);


    sanity_check();
}


template<class R, class AO>
void AuctionRunnerFR<R, AO>::assign_reverse(IdxType item_idx, IdxType bidder_idx)
{
    // only unassigned items submit bids in reverse phase
    assert(items_to_bidders[item_idx] == k_invalid_index);

    IdxType old_bidder_owner = bidders_to_items[bidder_idx];

    // set new owner
    bidders_to_items[bidder_idx] = item_idx;
    items_to_bidders[item_idx] = bidder_idx;

    // remove bidder and item from the sets of unassigned bidders/items
    remove_unassigned_item(item_idx);

    if (k_invalid_index != old_bidder_owner) {
        // old owner of item becomes unassigned
        items_to_bidders[old_bidder_owner] = k_invalid_index;
        add_unassigned_item(old_bidder_owner);
        // existing edge was removed, decrease partial_cost
        partial_cost -= get_item_bidder_cost(old_bidder_owner, bidder_idx);
    } else {
        // item was unassigned before
        remove_unassigned_bidder(bidder_idx);
    }

    // new edge was added to matching, increase partial cost
    partial_cost += get_item_bidder_cost(item_idx, bidder_idx);
}

template<class R, class AO>
typename AuctionRunnerFR<R, AO>::Real
AuctionRunnerFR<R, AO>::get_item_bidder_cost(const size_t item_idx, const size_t bidder_idx) const
{
    if (wasserstein_power == 1.0) {
        return dist_lp(bidders[bidder_idx], items[item_idx], internal_p);
    } else {
        return std::pow(dist_lp(bidders[bidder_idx], items[item_idx], internal_p),
                            wasserstein_power);
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::assign_to_best_bidder(IdxType item_idx)
{
    assert( item_idx >= 0 and item_idx < static_cast<IdxType>(num_items) );
    assert( forward_bid_table[item_idx].first != k_invalid_index);

    auto best_bidder_idx = forward_bid_table[item_idx].first;
    auto best_bid_value = forward_bid_table[item_idx].second;
    assign_forward(item_idx, best_bidder_idx);
    forward_oracle.sanity_check();
    forward_oracle.set_price(item_idx,  best_bid_value, true);
    forward_oracle.sanity_check();
    auto new_bidder_price = -get_item_bidder_cost(item_idx, best_bidder_idx) - best_bid_value;
    reverse_oracle.set_price(best_bidder_idx, new_bidder_price, false);
    check_epsilon_css();
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::assign_to_best_item(IdxType bidder_idx)
{
    check_epsilon_css();
    assert( bidder_idx >= 0 and bidder_idx < static_cast<IdxType>(num_bidders) );
    assert( reverse_bid_table[bidder_idx].first != k_invalid_index);
    auto best_item_idx = reverse_bid_table[bidder_idx].first;
    auto best_bid_value = reverse_bid_table[bidder_idx].second;
    // both assign_forward and assign_reverse take item index first, bidder index second!
    assign_reverse(best_item_idx, bidder_idx);
    reverse_oracle.sanity_check();
    reverse_oracle.set_price(bidder_idx,  best_bid_value, true);
    reverse_oracle.sanity_check();
    auto new_item_price = -get_item_bidder_cost(best_item_idx, bidder_idx) - best_bid_value;
    forward_oracle.set_price(best_item_idx, new_item_price, false);
    check_epsilon_css();
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::clear_forward_bid_table()
{
    auto item_iter = items_with_bids.begin();
    while(item_iter != items_with_bids.end()) {
        auto item_with_bid_idx = *item_iter;
        forward_bid_table[item_with_bid_idx].first = k_invalid_index;
        forward_bid_table[item_with_bid_idx].second = k_lowest_bid_value;
        item_iter = items_with_bids.erase(item_iter);
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::clear_reverse_bid_table()
{
    auto bidder_iter = bidders_with_bids.begin();
    while(bidder_iter != bidders_with_bids.end()) {
        auto bidder_with_bid_idx = *bidder_iter;
        reverse_bid_table[bidder_with_bid_idx].first = k_invalid_index;
        reverse_bid_table[bidder_with_bid_idx].second = k_lowest_bid_value;
        bidder_iter = bidders_with_bids.erase(bidder_iter);
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::submit_forward_bid(IdxType bidder_idx, const IdxValPairR& bid)
{
    IdxType best_item_idx = bid.first;
    Real bid_value = bid.second;
    assert( best_item_idx >= 0 );

    auto value_in_bid_table = forward_bid_table[best_item_idx].second;
    bool new_bid_wins = (value_in_bid_table < bid_value);
    // if we have tie, lower persistence wins
//    if (value_in_bid_table == bid_value) {
//
//        assert(forward_bid_table.at(best_item_idx).first != k_invalid_index);
//        assert(&bidders.at(forward_bid_table.at(best_item_idx).first));
//
//        auto bidder_in_bid_table = bidders[forward_bid_table[best_item_idx].first];
//        new_bid_wins = bidders[best_item_idx].persistence_lp(internal_p) < bidder_in_bid_table.persistence_lp(internal_p);
//    }

    if (new_bid_wins) {
        forward_bid_table[best_item_idx].first = bidder_idx;
        forward_bid_table[best_item_idx].second = bid_value;
    }

    items_with_bids.insert(best_item_idx);

}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::submit_reverse_bid(IdxType item_idx, const IdxValPairR& bid)
{
    assert( items.at(item_idx).is_diagonal() or items.at(item_idx).is_normal() );
    IdxType best_bidder_idx = bid.first;
    assert( bidders.at(best_bidder_idx).is_diagonal() or bidders.at(best_bidder_idx).is_normal() );
    Real bid_value = bid.second;
    assert(bid_value > k_lowest_bid_value);
    auto value_in_bid_table = reverse_bid_table[best_bidder_idx].second;
    bool new_bid_wins = (value_in_bid_table < bid_value);
    // if we have tie, lower persistence wins
//    if (value_in_bid_table == bid_value) {
//        assert(reverse_bid_table[best_bidder_idx].first != k_invalid_index);
//        auto bidder_in_bid_table = bidders[reverse_bid_table[best_bidder_idx].first];
//        new_bid_wins = bidders[best_bidder_idx].persistence_lp(internal_p) < bidder_in_bid_table.persistence_lp(internal_p);
//    }
    if (new_bid_wins) {
        reverse_bid_table[best_bidder_idx].first = item_idx;
        reverse_bid_table[best_bidder_idx].second = bid_value;
    }
    bidders_with_bids.insert(best_bidder_idx);

}


template<class R, class AO>
void AuctionRunnerFR<R, AO>::print_debug()
{
#ifdef DEBUG_FR_AUCTION
    std::cout << "**********************" << std::endl;
    std::cout << "Current assignment:" << std::endl;
    for(size_t idx = 0; idx < bidders_to_items.size(); ++idx) {
        std::cout << idx << " <--> " << bidders_to_items[idx] << std::endl;
    }
    std::cout << "Weights: " << std::endl;
    //for(size_t i = 0; i < num_bidders; ++i) {
        //for(size_t j = 0; j < num_items; ++j) {
            //std::cout << oracle.weight_matrix[i][j] << " ";
        //}
        //std::cout << std::endl;
    //}
    std::cout << "Bidder prices: " << std::endl;
    for(const auto price : forward_oracle.get_prices()) {
        std::cout << price << std::endl;
    }
    std::cout << "**********************" << std::endl;
#endif
}


template<class R, class AO>
typename AuctionRunnerFR<R,AO>::Real
AuctionRunnerFR<R, AO>::get_relative_error(const bool debug_output) const
{
    Real result;
    Real gamma = get_gamma();
    // cost minus n epsilon
    Real reduced_cost = partial_cost - num_bidders * get_epsilon();
    if ( reduced_cost < 0) {
        result = k_max_relative_error;
    } else {
        Real denominator = std::pow(reduced_cost, 1.0 / wasserstein_power) - gamma;
        if (denominator <= 0) {
            result = k_max_relative_error;
        } else {
            Real numerator = 2 * gamma +
                             std::pow(partial_cost, 1.0 / wasserstein_power) -
                             std::pow(reduced_cost, 1.0 / wasserstein_power);

            result = numerator / denominator;
        }
    }
    return result;
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::flush_assignment()
{
    for(auto& b2i : bidders_to_items) {
        b2i = k_invalid_index;
    }
    for(auto& i2b : items_to_bidders) {
        i2b = k_invalid_index;
    }

    // all bidders and items become unassigned
    for(size_t bidder_idx = 0; bidder_idx < num_bidders; ++bidder_idx) {
        unassigned_bidders.insert(bidder_idx);
    }

    // all items and items become unassigned
    for(size_t item_idx = 0; item_idx < num_items; ++item_idx) {
        unassigned_items.insert(item_idx);
    }


    //forward_oracle.adjust_prices();
    //reverse_oracle.adjust_prices();

    partial_cost = 0.0;
    unassigned_bidders_persistence = total_bidders_persistence;
    unassigned_items_persistence = total_items_persistence;

#ifdef ORDERED_BY_PERSISTENCE
    for(size_t bidder_idx = 0; bidder_idx < num_bidders; ++bidder_idx) {
        unassigned_bidders_by_persistence.insert(std::make_pair(bidders[bidder_idx].persistence_lp(1.0), bidder_idx));
    }

    for(size_t item_idx = 0; item_idx < num_items; ++item_idx) {
        unassigned_items_by_persistence.insert(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx));
    }
#endif
    check_epsilon_css();
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::set_epsilon(Real new_val)
{
    assert(new_val > 0.0);
    epsilon = new_val;
    forward_oracle.set_epsilon(new_val);
    reverse_oracle.set_epsilon(new_val);
}


template<class R, class AO>
bool AuctionRunnerFR<R, AO>::continue_forward(const size_t original_unassigned_bidders, const size_t min_forward_matching_increment)
{
//    if (unassigned_threshold == 0) {
//        return not unassigned_bidders.empty() and get_relative_error(false) > delta;
//    }
    //return unassigned_bidders.size() > unassigned_threshold and
           //static_cast<int>(unassigned_bidders.size()) >= static_cast<int>(original_unassigned_bidders) - static_cast<int>(min_forward_matching_increment);
    return unassigned_bidders.size() > unassigned_threshold and
           static_cast<int>(unassigned_bidders.size()) >= static_cast<int>(original_unassigned_bidders) - static_cast<int>(min_forward_matching_increment) and
           get_relative_error() >= delta;
//    return not unassigned_bidders.empty() and
//           static_cast<int>(unassigned_bidders.size()) >= static_cast<int>(original_unassigned_bidders) - static_cast<int>(min_forward_matching_increment) and
//           get_relative_error() >= delta;
}


template<class R, class AO>
bool AuctionRunnerFR<R, AO>::continue_reverse(const size_t original_unassigned_items, const size_t min_reverse_matching_increment)
{
    //return unassigned_items.size() > unassigned_threshold and
           //static_cast<int>(unassigned_items.size()) >= static_cast<int>(original_unassigned_items) - static_cast<int>(min_reverse_matching_increment);
    return unassigned_items.size() > unassigned_threshold and
           static_cast<int>(unassigned_items.size()) >= static_cast<int>(original_unassigned_items) - static_cast<int>(min_reverse_matching_increment) and
           get_relative_error() >= delta;
//    return not unassigned_items.empty() and
//           static_cast<int>(unassigned_items.size()) >= static_cast<int>(original_unassigned_items) - static_cast<int>(min_reverse_matching_increment) and
//           get_relative_error() >= delta;
}


template<class R, class AO>
bool AuctionRunnerFR<R, AO>::continue_phase()
{
    //return not unassigned_bidders.empty();
    return unassigned_bidders.size() > unassigned_threshold and get_relative_error() >= delta;
//    return not never_assigned_bidders.empty() or
//           not never_assigned_items.empty() or
//           unassigned_bidders.size() > unassigned_threshold and get_relative_error() >= delta;
}



template<class R, class AO>
void AuctionRunnerFR<R, AO>::run_auction_phase()
{
    num_phase++;
    while(continue_phase()) {
        forward_oracle.recompute_top_diag_items(true);
        forward_oracle.sanity_check();
        run_forward_auction_phase();
        reverse_oracle.recompute_top_diag_items(true);
        reverse_oracle.sanity_check();
        run_reverse_auction_phase();
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::run_auction_phases(const int max_num_phases, const Real _initial_epsilon)
{
    set_epsilon(_initial_epsilon);
    assert( forward_oracle.get_epsilon() > 0 );
    assert( reverse_oracle.get_epsilon() > 0 );
    for(int phase_num = 0; phase_num < max_num_phases; ++phase_num) {
        flush_assignment();

        run_auction_phase();
        Real current_result = partial_cost;

        if (get_relative_error(true) <= delta) {
            break;
        }
        // decrease epsilon for the next iteration
        decrease_epsilon();

        unassigned_threshold = std::floor( static_cast<double>(unassigned_threshold) / 1.1 );

        if (phase_can_be_final()) {
            unassigned_threshold = 0;
        }
    }
}

template<class R, class AO>
bool AuctionRunnerFR<R, AO>::phase_can_be_final() const
{
    Real estimated_error;
    // cost minus n epsilon
    Real reduced_cost = partial_cost - num_bidders * get_epsilon();
    if (reduced_cost <= 0.0) {
        return false;
    } else {
        Real denominator = std::pow(reduced_cost, 1.0 / wasserstein_power);
        if (denominator <= 0) {
            return false;
        } else {
            Real numerator = std::pow(partial_cost, 1.0 / wasserstein_power) -
                             std::pow(reduced_cost, 1.0 / wasserstein_power);

            estimated_error = numerator / denominator;
            return estimated_error <= delta;
        }
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::run_auction()
{
    double init_eps = ( initial_epsilon > 0.0 ) ? initial_epsilon : std::min(forward_oracle.max_val_, reverse_oracle.max_val_) / 4.0 ;
    assert(init_eps > 0.0);
    run_auction_phases(max_num_phases, init_eps);
    is_distance_computed = true;
    wasserstein_cost = partial_cost;
    if (get_relative_error() > delta) {
#ifndef FOR_R_TDA
            std::cerr << "Maximum iteration number exceeded, exiting. Current result is: ";
            std::cerr << get_wasserstein_distance() << std::endl;
#endif
            throw std::runtime_error("Maximum iteration number exceeded");
    }
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::add_unassigned_bidder(const size_t bidder_idx)
{
    const DgmPoint& bidder = bidders[bidder_idx];
    unassigned_bidders.insert(bidder_idx);
    unassigned_bidders_persistence += get_cost_to_diagonal(bidder);

#ifdef ORDERED_BY_PERSISTENCE
    unassigned_bidders_by_persistence.insert(std::make_pair(bidder.persistence_lp(1.0), bidder_idx));
#endif

}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::add_unassigned_item(const size_t item_idx)
{
    const DgmPoint& item = items[item_idx];
    unassigned_items.insert(item_idx);
    unassigned_items_persistence += get_cost_to_diagonal(item);

#ifdef ORDERED_BY_PERSISTENCE
    unassigned_items_by_persistence.insert(std::make_pair(item.persistence_lp(1.0), item_idx));
#endif

}


template<class R, class AO>
void AuctionRunnerFR<R, AO>::remove_unassigned_bidder(const size_t bidder_idx)
{
    unassigned_bidders_persistence -= get_cost_to_diagonal(bidders[bidder_idx]);

    unassigned_bidders.erase(bidder_idx);
    never_assigned_bidders.erase(bidder_idx);

#ifdef ORDERED_BY_PERSISTENCE
    unassigned_bidders_by_persistence.erase(std::make_pair(bidders[bidder_idx].persistence_lp(1.0), bidder_idx));
#endif

}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::remove_unassigned_item(const size_t item_idx)
{
    unassigned_items_persistence -= get_cost_to_diagonal(items[item_idx]);

    never_assigned_items.erase(item_idx);
    unassigned_items.erase(item_idx);

#ifdef ORDERED_BY_PERSISTENCE
    unassigned_items_by_persistence.erase(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx));
#endif

}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::decrease_epsilon()
{
    auto eps_diff = 1.01 * get_epsilon() * (epsilon_common_ratio - 1.0 ) / epsilon_common_ratio;
    reverse_oracle.adjust_prices( -eps_diff );
    set_epsilon( get_epsilon() / epsilon_common_ratio );
    cumulative_epsilon_factor *= epsilon_common_ratio;
}



template<class R, class AO>
void AuctionRunnerFR<R, AO>::run_reverse_auction_phase()
{
    size_t original_unassigned_items = unassigned_items.size();
//    const size_t min_reverse_matching_increment = std::max( static_cast<size_t>(1), static_cast<size_t>(original_unassigned_items / 10));
    size_t min_reverse_matching_increment = 1;

    while (continue_reverse(original_unassigned_items, min_reverse_matching_increment)) {
        num_rounds++;
        num_rounds_non_cumulative++;

        check_epsilon_css();

        reset_round_stat();
        // bidding
#ifdef ORDERED_BY_PERSISTENCE
        std::vector<size_t> active_items;
        active_items.reserve(batch_size);
        for(auto iter = unassigned_items_by_persistence.begin();
                iter != unassigned_items_by_persistence.end(); ++iter) {
            active_items.push_back(iter->second);
            if (active_items.size() >= batch_size) {
                break;
            }
        }
        run_reverse_bidding_step(active_items);
#else
        //if (not never_assigned_items.empty())
            //run_reverse_bidding_step(never_assigned_items);
        //else
            //run_reverse_bidding_step(unassigned_items);
        run_reverse_bidding_step(unassigned_items);
#endif

        // assignment phase
        for(auto bidder_idx : bidders_with_bids ) {
            assign_to_best_item(bidder_idx);
        }

        check_epsilon_css();
    }
}

template<class R, class AO>
template<class Range>
void AuctionRunnerFR<R, AO>::run_forward_bidding_step(const Range& active_bidders)
{
    clear_forward_bid_table();
    for(const auto bidder_idx : active_bidders) {
        submit_forward_bid(bidder_idx, forward_oracle.get_optimal_bid(bidder_idx));
        if (++num_forward_bids_submitted >= max_bids_per_round) {
            break;
        }
    }
}

template<class R, class AO>
template<class Range>
void AuctionRunnerFR<R, AO>::run_reverse_bidding_step(const Range& active_items)
{
    clear_reverse_bid_table();

    assert(bidders_with_bids.empty());
    assert(std::all_of(reverse_bid_table.begin(), reverse_bid_table.end(),
                [ki = k_invalid_index, kl = k_lowest_bid_value](const IdxValPairR& b) { return static_cast<size_t>(b.first) == ki and b.second == kl; }));

    for(const auto item_idx : active_items) {
        submit_reverse_bid(item_idx, reverse_oracle.get_optimal_bid(item_idx));
        if (++num_reverse_bids_submitted >= max_bids_per_round) {
            break;
        }
    }
}


template<class R, class AO>
void AuctionRunnerFR<R, AO>::run_forward_auction_phase()
{
    const size_t original_unassigned_bidders = unassigned_bidders.size();
//    const size_t min_forward_matching_increment = std::max( static_cast<size_t>(1), static_cast<size_t>(original_unassigned_bidders / 10));
    const size_t min_forward_matching_increment = 1;
    while (continue_forward(original_unassigned_bidders, min_forward_matching_increment)) {
        check_epsilon_css();
        num_rounds++;

        reset_round_stat();
        // bidding step
#ifdef ORDERED_BY_PERSISTENCE
        std::vector<size_t> active_bidders;
        active_bidders.reserve(batch_size);
        for(auto iter = unassigned_bidders_by_persistence.begin();
                iter != unassigned_bidders_by_persistence.end(); ++iter) {
            active_bidders.push_back(iter->second);
            if (active_bidders.size() >= batch_size) {
                break;
            }
        }
        run_forward_bidding_step(active_bidders);
#else

        //if (not never_assigned_bidders.empty())
            //run_forward_bidding_step(never_assigned_bidders);
        //else
            //run_forward_bidding_step(unassigned_bidders);
        run_forward_bidding_step(unassigned_bidders);
#endif

        // assignment step
        for(auto item_idx : items_with_bids ) {
            assign_to_best_bidder(item_idx);
        }

        check_epsilon_css();

    } ;

}
template<class R, class AO>
void AuctionRunnerFR<R, AO>::assign_diag_to_diag()
{
    size_t n_diag_to_diag = std::min(num_diag_bidders, num_diag_items);
    if (n_diag_to_diag < 2)
        return;
    for(size_t i = 0; i < n_diag_to_diag; ++i) {
    }
}

template<class R, class AO>
typename AuctionRunnerFR<R, AO>::Real
AuctionRunnerFR<R, AO>::get_wasserstein_distance()
{
    assert(is_distance_computed);
    return std::pow(wasserstein_cost, 1.0 / wasserstein_power);
}

template<class R, class AO>
typename AuctionRunnerFR<R, AO>::Real
AuctionRunnerFR<R, AO>::get_wasserstein_cost()
{
    assert(is_distance_computed);
    return wasserstein_cost;
}



template<class R, class AO>
void AuctionRunnerFR<R, AO>::sanity_check()
{
#ifdef DEBUG_FR_AUCTION
    assert(partial_cost >= 0);


    assert(num_diag_items == num_normal_bidders);
    assert(num_diag_bidders == num_normal_items);
    assert(num_diag_bidders + num_normal_bidders == num_bidders);
    assert(num_diag_items + num_normal_items == num_items);
    assert(num_items == num_bidders);


    for(size_t b = 0; b < num_bidders; ++b) {
        assert( is_bidder_diagonal(b) == bidders.at(b).is_diagonal() );
        assert( is_bidder_normal(b) == bidders.at(b).is_normal() );
    }

    for(size_t i = 0; i < num_items; ++i) {
        assert( is_item_diagonal(i) == items.at(i).is_diagonal() );
        assert( is_item_normal(i) == items.at(i).is_normal() );
    }

    // check matching consistency
    assert(bidders_to_items.size() == num_bidders);
    assert(items_to_bidders.size() == num_bidders);

    assert(std::count(bidders_to_items.begin(), bidders_to_items.end(), k_invalid_index)  == std::count(items_to_bidders.begin(), items_to_bidders.end(), k_invalid_index));

    Real true_partial_cost = 0.0;

    for(size_t bidder_idx = 0; bidder_idx < num_bidders; ++bidder_idx) {
        if (bidders_to_items[bidder_idx] != k_invalid_index) {
            assert(items_to_bidders.at(bidders_to_items[bidder_idx]) == static_cast<int>(bidder_idx));
            true_partial_cost += get_item_bidder_cost(bidders_to_items[bidder_idx], bidder_idx);
        }
    }

    assert(fabs(partial_cost - true_partial_cost) < 0.00001);

    for(size_t item_idx = 0; item_idx < num_items; ++item_idx) {
        if (items_to_bidders[item_idx] != k_invalid_index) {
            assert(bidders_to_items.at(items_to_bidders[item_idx]) == static_cast<int>(item_idx));
        }
    }

#ifdef ORDERED_BY_PERSISTENCE
    assert(unassigned_bidders.size() == unassigned_bidders_by_persistence.size());
    assert(unassigned_items.size() == unassigned_items_by_persistence.size());

    for(size_t bidder_idx = 0; bidder_idx < num_bidders; ++bidder_idx) {
        if (bidders_to_items[bidder_idx] == k_invalid_index) {
            assert(unassigned_bidders.count(bidder_idx) == 1);
            assert(unassigned_bidders_by_persistence.count(std::make_pair(bidders[bidder_idx].persistence_lp(1.0), bidder_idx)) == 1);
        } else {
            assert(unassigned_bidders.count(bidder_idx) == 0);
            assert(unassigned_bidders_by_persistence.count(std::make_pair(bidders[bidder_idx].persistence_lp(1.0), bidder_idx)) == 0);
        }
    }

    for(size_t item_idx = 0; item_idx < num_items; ++item_idx) {
        if (items_to_bidders[item_idx] == k_invalid_index) {
            assert(unassigned_items.count(item_idx) == 1);
            assert(unassigned_items_by_persistence.count(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx)) == 1);
        } else {
            assert(unassigned_items.count(item_idx) == 0);
            assert(unassigned_items_by_persistence.count(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx)) == 0);
        }
    }
#endif


#endif
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::check_epsilon_css()
{
#ifdef DEBUG_FR_AUCTION
    sanity_check();

    std::vector<double> b_prices = reverse_oracle.get_prices();
    std::vector<double> i_prices = forward_oracle.get_prices();
    double eps = forward_oracle.get_epsilon();

    for(size_t b = 0; b < num_bidders; ++b) {
        for(size_t i = 0; i < num_items; ++i) {
            if(((is_bidder_normal(b) and is_item_diagonal(i)) or (is_bidder_diagonal(b) and is_item_normal(i))) and b != i)
                continue;
            assert(b_prices[b] + i_prices[i] + eps >= -get_item_bidder_cost(i, b) - 0.000001);
        }
    }

    for(size_t b = 0; b < num_bidders; ++b) {
        auto i = bidders_to_items[b];
        if (i != k_invalid_index) {
            assert( fabs(b_prices[b] + i_prices[i] + get_item_bidder_cost(i, b)) < 0.000001 );
        }
    }
#endif
}

template<class R, class AO>
void AuctionRunnerFR<R, AO>::print_matching()
{
#ifdef DEBUG_FR_AUCTION
    sanity_check();
    for(size_t bidder_idx = 0; bidder_idx < bidders_to_items.size(); ++bidder_idx) {
        if (bidders_to_items[bidder_idx] >= 0) {
            auto pA = bidders[bidder_idx];
            auto pB = items[bidders_to_items[bidder_idx]];
            std::cout <<  pA << " <-> " << pB << "+" << pow(dist_lp(pA, pB, internal_p), wasserstein_power) << std::endl;
        } else {
            assert(false);
        }
    }
#endif
}

} // ws
} // hera

#endif