Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFairness in Combinatorial Auctioning Systems
121
0
0.0
(
0
)
Added by
Shrisha Rao
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
One of the Multi-Agent Systems that is widely used by various government agencies, buyers and sellers in a market economy, in such a manner so as to attain optimized resource allocation, is the Combinatorial Auctioning System (CAS). We study another important aspect of resource allocations in CAS, namely fairness. We present two important notions of fairness in CAS, extended fairness and basic fairness. We give an algorithm that works by incorporating a metric to ensure fairness in a CAS that uses the Vickrey-Clark-Groves (VCG) mechanism, and uses an algorithm of Sandholm to achieve optimality. Mathematical formulations are given to represent measures of extended fairness and basic fairness.
rate research
Read More
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.
Classic mechanism design often assumes that a bidders action is restricted to report a type or a signal, possibly untruthfully. In todays digital economy, bidders are holding increasing amount of private information about the auctioned items. And due to legal or ethical concerns, they would demand to reveal partial but truthful information, as opposed to report untrue signal or misinformation. To accommodate such bidder behaviors in auction design, we propose and study a novel mechanism design setup where each bidder holds two kinds of information: (1) private emph{value type}, which can be misreported; (2) private emph{information variable}, which the bidder may want to conceal or partially reveal, but importantly, emph{not} to misreport. We show that in this new setup, it is still possible to design mechanisms that are both emph{Incentive and Information Compatible} (IIC). We develop two different black-box transformations, which convert any mechanism $mathcal{M}$ for classic bidders to a mechanism $mathcal{M}$ for strategically reticent bidders, based on either outcome of expectation or expectation of outcome, respectively. We identify properties of the original mechanism $mathcal{M}$ under which the transformation leads to IIC mechanisms $mathcal{M}$. Interestingly, as corollaries of these results, we show that running VCG with expected bidder values maximizes welfare whereas the mechanism using expected outcome of Myersons auction maximizes revenue. Finally, we study how regulation on the auctioneers usage of information may lead to more robust mechanisms.
Consider N cooperative but non-communicating players where each plays one out of M arms for T turns. Players have different utilities for each arm, representable as an NxM matrix. These utilities are unknown to the players. In each turn players select an arm and receive a noisy observation of their utility for it. However, if any other players selected the same arm that turn, all colliding players will all receive zero utility due to the conflict. No other communication or coordination between the players is possible. Our goal is to design a distributed algorithm that learns the matching between players and arms that achieves max-min fairness while minimizing the regret. We present an algorithm and prove that it is regret optimal up to a $loglog T$ factor. This is the first max-min fairness multi-player bandit algorithm with (near) order optimal regret.
Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike supply is reshaped to better match the dynamic bike demand. When the bike-sharing company or platform is able to predict the revenue of each reposition task based on historic data, an additional constraint is to cap the payment for each task below its predicted revenue. In this paper, we propose an incentive mechanism called {em TruPreTar} to incentivize users to park bicycles at locations desired by the platform toward rebalancing supply and demand. TruPreTar possesses four important economic and computational properties such as truthfulness and budget feasibility. Furthermore, we prove that even when the payment budget is tight, the total revenue still exceeds or equals the budget. Otherwise, TruPreTar achieves 2-approximation as compared to the optimal (revenue-maximizing) solution, which is close to the lower bound of at least $sqrt{2}$ that we also prove. Using an industrial dataset obtained from a large bike-sharing company, our experiments show that TruPreTar is effective in rebalancing bike supply and demand and, as a result, generates high revenue that outperforms several benchmark mechanisms.
In this paper, we study fairness in committee selection problems. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voters strictly prefer the new committee to the existing one. Our main contribution is to extend this definition to stability of a distribution (or lottery) over committees. We consider two canonical voter preference models: the Approval Set setting where each voter approves a set of candidates and prefers committees with larger intersection with this set; and the Ranking setting where each voter ranks committees based on how much she likes her favorite candidate in a committee. Our main result is to show that stable lotteries always exist for these canonical preference models. Interestingly, given preferences of voters over committees, the procedure for computing an approximately stable lottery is the same for both models and therefore extends to the setting where some voters have the former preference structure and others have the latter. Our existence proof uses the probabilistic method and a new large deviation inequality that may be of independent interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
