The market economy deals with many interacting agents such as buyers and sellers who are autonomous intelligent agents pursuing their own interests. One such multi-agent system (MAS) that plays an important role in auctions is the combinatorial auctioning system (CAS). We use this framework to define our concept of fairness in terms of what we call as "basic fairness" and "extended fairness". The assumptions of quasilinear preferences and dominant strategies are taken into consideration while explaining fairness. We give an algorithm to ensure fairness in a CAS using a Generalized Vickrey Auction (GVA). We use an algorithm of Sandholm to achieve optimality. Basic and extended fairness are then analyzed according to the dominant strategy solution concept.
A concept of verifiable fairness in Internet auctions has been proposed by Liao and Hwang @cite_17 . This was to promote trust in Internet auctions. The scheme proposed provides evidence regarding policies implemented so that the confidence of bidders increases and they consider it to be fair. Most of these auctions see transparency in the auctioning process and rules as the basis for ensuring fairness in the system, but clarity regarding fairness still remains wanting.
@cite_17
2055445578 2084685902 2404718321 2138043622
Describes a novel Internet auction model achieving verifiable fairness, a requirement aimed at enhancing the trust of bidders in auctioneers. Distrust in remote auctioneers prevents bidders from participating in Internet auctioning. According to proposed survey reports, this study presents four characteristics that render the Internet untrustworthy for bidders. These intrinsic properties suggest that auction sites not only follow auction policies, but provide customers with evidence validating that the policies are applied fairly. Evidence of verifiable fairness provides bidders with a basis for confidence in Internet auctions. Cryptographic techniques are also applied herein to establish a novel auction model with evidence to manifest and verify every step of the auctioneer. Analysis results demonstrate that the proposed model satisfies various requirements regarding fairness and privacy. Moreover, in the proposed model, the losing bids remain sealed. We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option. For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1 e ≈ 0.368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0.5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design. We also ask whether better approximation ratios are possible in more restricted settings. In particular, motivated by the massive privatization auction in the Czech republic in the early 90s we provide another mechanism for additive linear valuations that works really well when all the items are highly demanded. We consider the problem of maximizing revenue in prior-free auctions for general single parameter settings. The setting is modeled by an arbitrary downward-closed set system, which captures many special cases such as single item, digital goods and single-minded combinatorial auctions. We relax the truthfulness requirement by the solution concept of Nash equilibria. Implementation by Nash equilibria is a natural and relevant framework in many applications of computer science, where auctions are run repeatedly and bidders can observe others’ strategies, but the auctioneer needs to design a mechanism in advance and cannot use any information on the bidders’ private valuations. We introduce a worst-case revenue benchmark which generalizes the second price of single item auction and the F2 benchmark, introduced by , for digital goods. We design a mechanism whose Nash equilibria obtains at least a constant factor of this benchmark and prove that no truthful mechanisms can achieve a constant approximation. We analyze the problem of designing a truthful pay-per-click auction where the click-through-rates (CTR) of the bidders are unknown to the auction. Such an auction faces the classic explore exploit dilemma: while gathering information about the click through rates of advertisers, the mechanism may loose revenue; however, this gleaned information may prove valuable in the future for a more profitable allocation. In this sense, such mechanisms are prime candidates to be designed using multi-armed bandit techniques. However, a naive application of multi-armed bandit algorithms would not take into account the strategic considerations of the players -- players might manipulate their bids (which determine the auction's revenue) in a way as to maximize their own utility. Hence, we consider the natural restriction that the auction be truthful. The revenue that we could hope to achieve is the expected revenue of a Vickrey auction that knows the true CTRs, and we define the truthful regret to be the difference between the expected revenue of the auction and this Vickrey revenue. This work sharply characterizes what regret is achievable, under a truthful restriction. We show that this truthful restriction imposes statistical limits on the achievable regret -- the achievable regret is Θ(T2 3), while for traditional bandit algorithms (without the truthful restriction) the achievable regret is Θ(T1 2) (where T is the number of rounds). We term the extra T1 6 factor, the price of truthfulness'.