Back to search

Athens University Economics and Business (AUEB)

Algorithmic and mechanism design aspects of problems with limited -or no - payments

Abstract

dc:description

The most notable distinction between algorithm design and mechanism design is the notion of truthfulness. Typically, one of the goals of the mechanism designer is to ensure that the agents participating in the mechanism will not have any incentive to misreport their private information. Towards this goal, the payments made to the agents by the mechanism are crucial. However, there is an abundance of scenarios in microeconomics where the payments are restricted (e.g., via budget constraints) or even completely undesirable. This thesis focuses on two such problems that are indicative of the challenges that arise when the payments are limited or absent. In particular, fair division of indivisible items and reverse auctions with hard budget constraints are studied, both from the game-theoretic and the algorithmic point of view. In the first part of the thesis, we study the problem of computing allocations with maximin share guarantees, a recently introduced fairness notion. Given a set of agents and a set of goods, the objective is to find a partition so that each agent is guaranteed an approximation of his maximin share. Our main algorithmic result is a 2/3-approximation algorithm, that runs in polynomial time for any number of agents and items. Furthermore, we undertake a probabilistic analysis and provide a theoretical justification of the experimental evidence reported in the literature indicating that better approximations almost always exist.From the mechanism design point of view, this is a setting where no monetary transfers are allowed. Even for two agents and a few items, the problem becomes strictly harder than its algorithmic counterpart, and the limitations imposed by truthfulness on the approximability of the problem become apparent. We focus on the case of two players and our main result is a complete characterization of truthful mechanisms that allocate all the items. Applying this result, we derive several consequences on the design of mechanisms with fairness guarantees, such as maximin share fairness and envy-freeness up to one item.In the second part of the thesis, we study a family of reverse auctions with a budget constraint. The general algorithmic problem is to purchase a set of resources, which come at a cost, so as not to exceed a given budget and at the same time maximize a given valuation function. This framework captures the budgeted version of several well-known optimization problems, and when the resources are owned by strategic agents the goal is to design truthful and budget-feasible mechanisms.We obtain mechanisms with significantly improved approximation ratios for several subclasses of submodular valuation functions, like coverage functions and cut functions. We then provide a general scheme for designing deterministic and randomized mechanisms for a subclass of XOS problems which contains problems whose feasible set forms an independence system. Some representative problems include, among others, finding maximum weighted matchings and maximum weighted matroid members. For most of the above, only randomized mechanisms with very high approximation ratios were known prior to our results. A purely algorithmic byproduct of our work is a polynomial-time 2e/(e-1)-approximation algorithm for symmetric submodular maximization subject to a budget constraint. This is the best known factor achieved by a deterministic algorithm assuming only a value oracle for the objective function.

Degree

thesis:*
Grantor dc:publisher
Athens University Economics and Business (AUEB)
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Amanatidis, Georgios
  • Αμανατίδης, Γεώργιος

Subjects

dc:subject × 10

Rights

dc:rights
Statement dc:rights
  • BY_NC_SA
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/41712

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Amanatidis, Georgios; Αμανατίδης, Γεώργιος. Algorithmic and mechanism design aspects of problems with limited -or no - payments. Athens University Economics and Business (AUEB), 2017. http://hdl.handle.net/10442/hedi/41712